catacomb/__init__.py: Rewrite `kcdsaprime' to return the correct length.

[catacomb-python] / catacomb / __init__.py

diff --git a/catacomb/__init__.py b/catacomb/__init__.py
index d59d3f3..2b433cf 100644 (file)
--- a/catacomb/__init__.py
+++ b/catacomb/__init__.py
@@ -272,15 +272,12 @@ def secret_unbox(k, n, c):
 ###--------------------------------------------------------------------------
 ### Multiprecision integers and binary polynomials.
 
-def _split_rat(x):
-  if isinstance(x, BaseRat): return x._n, x._d
-  else: return x, 1
 class BaseRat (object):
   """Base class implementing fields of fractions over Euclidean domains."""
   def __new__(cls, a, b):
-    a, b = cls.RING(a), cls.RING(b)
+    a, b = cls.RING._implicit(a), cls.RING._implicit(b)
     q, r = divmod(a, b)
-    if r == 0: return q
+    if r == cls.ZERO: return q
     g = b.gcd(r)
     me = super(BaseRat, cls).__new__(cls)
     me._n = a//g
@@ -294,31 +291,34 @@ class BaseRat (object):
   def __repr__(me): return '%s(%s, %s)' % (_clsname(me), me._n, me._d)
   _repr_pretty_ = _pp_str
 
+  def _split_rat(me, x):
+    if isinstance(x, me.__class__): return x._n, x._d
+    else: return x, me.ONE
   def __add__(me, you):
-    n, d = _split_rat(you)
+    n, d = me._split_rat(you)
     return type(me)(me._n*d + n*me._d, d*me._d)
   __radd__ = __add__
   def __sub__(me, you):
-    n, d = _split_rat(you)
+    n, d = me._split_rat(you)
     return type(me)(me._n*d - n*me._d, d*me._d)
   def __rsub__(me, you):
-    n, d = _split_rat(you)
+    n, d = me._split_rat(you)
     return type(me)(n*me._d - me._n*d, d*me._d)
   def __mul__(me, you):
-    n, d = _split_rat(you)
+    n, d = me._split_rat(you)
     return type(me)(me._n*n, me._d*d)
   __rmul__ = __mul__
   def __truediv__(me, you):
-    n, d = _split_rat(you)
+    n, d = me._split_rat(you)
     return type(me)(me._n*d, me._d*n)
   def __rtruediv__(me, you):
-    n, d = _split_rat(you)
+    n, d = me._split_rat(you)
     return type(me)(me._d*n, me._n*d)
   if _sys.version_info < (3,):
     __div__ = __truediv__
     __rdiv__ = __rtruediv__
   def _order(me, you, op):
-    n, d = _split_rat(you)
+    n, d = me._split_rat(you)
     return op(me._n*d, n*me._d)
   def __eq__(me, you): return me._order(you, lambda x, y: x == y)
   def __ne__(me, you): return me._order(you, lambda x, y: x != y)
@@ -329,6 +329,7 @@ class BaseRat (object):
 
 class IntRat (BaseRat):
   RING = MP
+  ZERO, ONE = MP(0), MP(1)
   def __new__(cls, a, b):
     if isinstance(a, float) or isinstance(b, float): return a/b
     return super(IntRat, cls).__new__(cls, a, b)
@@ -336,6 +337,7 @@ class IntRat (BaseRat):
 
 class GFRat (BaseRat):
   RING = GF
+  ZERO, ONE = GF(0), GF(1)
 
 class _tmp:
   def negp(x): return x < 0
@@ -442,6 +444,8 @@ class _tmp:
       pp.pretty(me.a); pp.text(','); pp.breakable()
       pp.pretty(me.b)
     pp.end_group(ind, ')')
+  def fromstring(str): return _checkend(ECCurve.parse(str))
+  fromstring = staticmethod(fromstring)
   def frombuf(me, s):
     return ecpt.frombuf(me, s)
   def fromraw(me, s):
@@ -506,6 +510,8 @@ class _tmp:
     h ^=   hash(me.curve)
     h ^= 2*hash(me.G) & 0xffffffff
     return h
+  def fromstring(str): return _checkend(ECInfo.parse(str))
+  fromstring = staticmethod(fromstring)
   def group(me):
     return ECGroup(me)
 _augment(ECInfo, _tmp)
@@ -1180,13 +1186,19 @@ def findprimitive(mod, hh = [], exp = None, name = 'g', event = pgen_nullev):
 
 def kcdsaprime(pbits, qbits, rng = rand,
                event = pgen_nullev, name = 'p', nsteps = 0):
-  hbits = pbits - qbits
-  h = pgen(rng.mp(hbits, 1), name + ' [h]',
-           PrimeGenStepper(2), PrimeGenTester(),
-           event, nsteps, RabinMiller.iters(hbits))
-  q = pgen(rng.mp(qbits, 1), name, SimulStepper(2 * h, 1, 2),
-           SimulTester(2 * h, 1), event, nsteps, RabinMiller.iters(qbits))
-  p = 2 * q * h + 1
-  return p, q, h
+  hbits = pbits - qbits - 1
+  while True:
+    h = pgen(rng.mp(hbits, 1), name + ' [h]',
+             PrimeGenStepper(2), PrimeGenTester(),
+             event, nsteps, RabinMiller.iters(hbits))
+    while True:
+      q0 = rng.mp(qbits, 1)
+      p0 = 2*q0*h + 1
+      if p0.nbits == pbits: break
+    q = pgen(q0, name, SimulStepper(2*h, 1, 2),
+             SimulTester(2 * h, 1), event, nsteps, RabinMiller.iters(qbits))
+    p = 2*q*h + 1
+    if q.nbits == qbits and p.nbits == pbits: return p, q, h
+    elif nsteps: raise ValueError("prime generation failed")
 
 #----- That's all, folks ----------------------------------------------------