[3] | 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 Crypto.PublicKey import pubkey |
---|
| 16 | from Crypto.Util.number import * |
---|
| 17 | from 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 | |
---|