Crypto/PublicKey/qNEW.py

   1 #
   2 #   qNEW.py : The q-NEW signature algorithm.
   3 #
   4 #  Part of the Python Cryptography Toolkit
   5 #
   6 # Distribute and use freely; there are no restrictions on further
   7 # dissemination and usage except those imposed by the laws of your
   8 # country of residence.    This software is provided "as is" without
   9 # warranty of fitness for use or suitability for any purpose, express
  10 # or implied. Use at your own risk or not at all.
  11 #
  12
  13 __revision__ = "$Id: qNEW.py,v 1.8 2003/04/04 15:13:35 akuchling Exp $"
  14
  15 from allmydata.Crypto.PublicKey import pubkey
  16 from allmydata.Crypto.Util.number import *
  17 from allmydata.Crypto.Hash import SHA
  18
  19 class error (Exception):
  20     pass
  21
  22 HASHBITS = 160   # Size of SHA digests
  23
  24 def generate(bits, randfunc, progress_func=None):
  25     """generate(bits:int, randfunc:callable, progress_func:callable)
  26
  27     Generate a qNEW key of length 'bits', using 'randfunc' to get
  28     random data and 'progress_func', if present, to display
  29     the progress of the key generation.
  30     """
  31     obj=qNEWobj()
  32
  33     # Generate prime numbers p and q.  q is a 160-bit prime
  34     # number.  p is another prime number (the modulus) whose bit
  35     # size is chosen by the caller, and is generated so that p-1
  36     # is a multiple of q.
  37     #
  38     # Note that only a single seed is used to
  39     # generate p and q; if someone generates a key for you, you can
  40     # use the seed to duplicate the key generation.  This can
  41     # protect you from someone generating values of p,q that have
  42     # some special form that's easy to break.
  43     if progress_func:
  44         progress_func('p,q\n')
  45     while (1):
  46         obj.q = getPrime(160, randfunc)
  47         #           assert pow(2, 159L)<obj.q<pow(2, 160L)
  48         obj.seed = S = long_to_bytes(obj.q)
  49         C, N, V = 0, 2, {}
  50         # Compute b and n such that bits-1 = b + n*HASHBITS
  51         n= (bits-1) / HASHBITS
  52         b= (bits-1) % HASHBITS ; powb=2L << b
  53         powL1=pow(long(2), bits-1)
  54         while C<4096:
  55             # The V array will contain (bits-1) bits of random
  56             # data, that are assembled to produce a candidate
  57             # value for p.
  58             for k in range(0, n+1):
  59                 V[k]=bytes_to_long(SHA.new(S+str(N)+str(k)).digest())
  60             p = V[n] % powb
  61             for k in range(n-1, -1, -1):
  62                 p= (p << long(HASHBITS) )+V[k]
  63             p = p+powL1         # Ensure the high bit is set
  64
  65             # Ensure that p-1 is a multiple of q
  66             p = p - (p % (2*obj.q)-1)
  67
  68             # If p is still the right size, and it's prime, we're done!
  69             if powL1<=p and isPrime(p):
  70                 break
  71
  72             # Otherwise, increment the counter and try again
  73             C, N = C+1, N+n+1
  74         if C<4096:
  75             break   # Ended early, so exit the while loop
  76         if progress_func:
  77             progress_func('4096 values of p tried\n')
  78
  79     obj.p = p
  80     power=(p-1)/obj.q
  81
  82     # Next parameter: g = h**((p-1)/q) mod p, such that h is any
  83     # number <p-1, and g>1.  g is kept; h can be discarded.
  84     if progress_func:
  85         progress_func('h,g\n')
  86     while (1):
  87         h=bytes_to_long(randfunc(bits)) % (p-1)
  88         g=pow(h, power, p)
  89         if 1<h<p-1 and g>1:
  90             break
  91     obj.g=g
  92
  93     # x is the private key information, and is
  94     # just a random number between 0 and q.
  95     # y=g**x mod p, and is part of the public information.
  96     if progress_func:
  97         progress_func('x,y\n')
  98     while (1):
  99         x=bytes_to_long(randfunc(20))
 100         if 0 < x < obj.q:
 101             break
 102     obj.x, obj.y=x, pow(g, x, p)
 103
 104     return obj
 105
 106 # Construct a qNEW object
 107 def construct(tuple):
 108     """construct(tuple:(long,long,long,long)|(long,long,long,long,long)
 109     Construct a qNEW object from a 4- or 5-tuple of numbers.
 110     """
 111     obj=qNEWobj()
 112     if len(tuple) not in [4,5]:
 113         raise error, 'argument for construct() wrong length'
 114     for i in range(len(tuple)):
 115         field = obj.keydata[i]
 116         setattr(obj, field, tuple[i])
 117     return obj
 118
 119 class qNEWobj(pubkey.pubkey):
 120     keydata=['p', 'q', 'g', 'y', 'x']
 121
 122     def _sign(self, M, K=''):
 123         if (self.q<=K):
 124             raise error, 'K is greater than q'
 125         if M<0:
 126             raise error, 'Illegal value of M (<0)'
 127         if M>=pow(2,161L):
 128             raise error, 'Illegal value of M (too large)'
 129         r=pow(self.g, K, self.p) % self.q
 130         s=(K- (r*M*self.x % self.q)) % self.q
 131         return (r,s)
 132     def _verify(self, M, sig):
 133         r, s = sig
 134         if r<=0 or r>=self.q or s<=0 or s>=self.q:
 135             return 0
 136         if M<0:
 137             raise error, 'Illegal value of M (<0)'
 138         if M<=0 or M>=pow(2,161L):
 139             return 0
 140         v1 = pow(self.g, s, self.p)
 141         v2 = pow(self.y, M*r, self.p)
 142         v = ((v1*v2) % self.p)
 143         v = v % self.q
 144         if v==r:
 145             return 1
 146         return 0
 147
 148     def size(self):
 149         "Return the maximum number of bits that can be handled by this key."
 150         return 160
 151
 152     def has_private(self):
 153         """Return a Boolean denoting whether the object contains
 154         private components."""
 155         return hasattr(self, 'x')
 156
 157     def can_sign(self):
 158         """Return a Boolean value recording whether this algorithm can generate signatures."""
 159         return 1
 160
 161     def can_encrypt(self):
 162         """Return a Boolean value recording whether this algorithm can encrypt data."""
 163         return 0
 164
 165     def publickey(self):
 166         """Return a new key object containing only the public information."""
 167         return construct((self.p, self.q, self.g, self.y))
 168
 169 object = qNEWobj
 170