[3] | 1 | |
---|
| 2 | # |
---|
| 3 | # DSA.py : Digital Signature Algorithm |
---|
| 4 | # |
---|
| 5 | # Part of the Python Cryptography Toolkit |
---|
| 6 | # |
---|
| 7 | # Distribute and use freely; there are no restrictions on further |
---|
| 8 | # dissemination and usage except those imposed by the laws of your |
---|
| 9 | # country of residence. This software is provided "as is" without |
---|
| 10 | # warranty of fitness for use or suitability for any purpose, express |
---|
| 11 | # or implied. Use at your own risk or not at all. |
---|
| 12 | # |
---|
| 13 | |
---|
| 14 | __revision__ = "$Id: DSA.py,v 1.16 2004/05/06 12:52:54 akuchling Exp $" |
---|
| 15 | |
---|
| 16 | from Crypto.PublicKey.pubkey import * |
---|
| 17 | from Crypto.Util import number |
---|
| 18 | from Crypto.Util.number import bytes_to_long, long_to_bytes |
---|
| 19 | from Crypto.Hash import SHA |
---|
| 20 | |
---|
| 21 | try: |
---|
| 22 | from Crypto.PublicKey import _fastmath |
---|
| 23 | except ImportError: |
---|
| 24 | _fastmath = None |
---|
| 25 | |
---|
| 26 | class error (Exception): |
---|
| 27 | pass |
---|
| 28 | |
---|
| 29 | def generateQ(randfunc): |
---|
| 30 | S=randfunc(20) |
---|
| 31 | hash1=SHA.new(S).digest() |
---|
| 32 | hash2=SHA.new(long_to_bytes(bytes_to_long(S)+1)).digest() |
---|
| 33 | q = bignum(0) |
---|
| 34 | for i in range(0,20): |
---|
| 35 | c=ord(hash1[i])^ord(hash2[i]) |
---|
| 36 | if i==0: |
---|
| 37 | c=c | 128 |
---|
| 38 | if i==19: |
---|
| 39 | c= c | 1 |
---|
| 40 | q=q*256+c |
---|
| 41 | while (not isPrime(q)): |
---|
| 42 | q=q+2 |
---|
| 43 | if pow(2,159L) < q < pow(2,160L): |
---|
| 44 | return S, q |
---|
| 45 | raise error, 'Bad q value generated' |
---|
| 46 | |
---|
| 47 | def generate(bits, randfunc, progress_func=None): |
---|
| 48 | """generate(bits:int, randfunc:callable, progress_func:callable) |
---|
| 49 | |
---|
| 50 | Generate a DSA key of length 'bits', using 'randfunc' to get |
---|
| 51 | random data and 'progress_func', if present, to display |
---|
| 52 | the progress of the key generation. |
---|
| 53 | """ |
---|
| 54 | |
---|
| 55 | if bits<160: |
---|
| 56 | raise error, 'Key length <160 bits' |
---|
| 57 | obj=DSAobj() |
---|
| 58 | # Generate string S and prime q |
---|
| 59 | if progress_func: |
---|
| 60 | progress_func('p,q\n') |
---|
| 61 | while (1): |
---|
| 62 | S, obj.q = generateQ(randfunc) |
---|
| 63 | n=(bits-1)/160 |
---|
| 64 | C, N, V = 0, 2, {} |
---|
| 65 | b=(obj.q >> 5) & 15 |
---|
| 66 | powb=pow(bignum(2), b) |
---|
| 67 | powL1=pow(bignum(2), bits-1) |
---|
| 68 | while C<4096: |
---|
| 69 | for k in range(0, n+1): |
---|
| 70 | V[k]=bytes_to_long(SHA.new(S+str(N)+str(k)).digest()) |
---|
| 71 | W=V[n] % powb |
---|
| 72 | for k in range(n-1, -1, -1): |
---|
| 73 | W=(W<<160L)+V[k] |
---|
| 74 | X=W+powL1 |
---|
| 75 | p=X-(X%(2*obj.q)-1) |
---|
| 76 | if powL1<=p and isPrime(p): |
---|
| 77 | break |
---|
| 78 | C, N = C+1, N+n+1 |
---|
| 79 | if C<4096: |
---|
| 80 | break |
---|
| 81 | if progress_func: |
---|
| 82 | progress_func('4096 multiples failed\n') |
---|
| 83 | |
---|
| 84 | obj.p = p |
---|
| 85 | power=(p-1)/obj.q |
---|
| 86 | if progress_func: |
---|
| 87 | progress_func('h,g\n') |
---|
| 88 | while (1): |
---|
| 89 | h=bytes_to_long(randfunc(bits)) % (p-1) |
---|
| 90 | g=pow(h, power, p) |
---|
| 91 | if 1<h<p-1 and g>1: |
---|
| 92 | break |
---|
| 93 | obj.g=g |
---|
| 94 | if progress_func: |
---|
| 95 | progress_func('x,y\n') |
---|
| 96 | while (1): |
---|
| 97 | x=bytes_to_long(randfunc(20)) |
---|
| 98 | if 0 < x < obj.q: |
---|
| 99 | break |
---|
| 100 | obj.x, obj.y = x, pow(g, x, p) |
---|
| 101 | return obj |
---|
| 102 | |
---|
| 103 | def construct(tuple): |
---|
| 104 | """construct(tuple:(long,long,long,long)|(long,long,long,long,long)):DSAobj |
---|
| 105 | Construct a DSA object from a 4- or 5-tuple of numbers. |
---|
| 106 | """ |
---|
| 107 | obj=DSAobj() |
---|
| 108 | if len(tuple) not in [4,5]: |
---|
| 109 | raise error, 'argument for construct() wrong length' |
---|
| 110 | for i in range(len(tuple)): |
---|
| 111 | field = obj.keydata[i] |
---|
| 112 | setattr(obj, field, tuple[i]) |
---|
| 113 | return obj |
---|
| 114 | |
---|
| 115 | class DSAobj(pubkey): |
---|
| 116 | keydata=['y', 'g', 'p', 'q', 'x'] |
---|
| 117 | |
---|
| 118 | def _encrypt(self, s, Kstr): |
---|
| 119 | raise error, 'DSA algorithm cannot encrypt data' |
---|
| 120 | |
---|
| 121 | def _decrypt(self, s): |
---|
| 122 | raise error, 'DSA algorithm cannot decrypt data' |
---|
| 123 | |
---|
| 124 | def _sign(self, M, K): |
---|
| 125 | if (K<2 or self.q<=K): |
---|
| 126 | raise error, 'K is not between 2 and q' |
---|
| 127 | r=pow(self.g, K, self.p) % self.q |
---|
| 128 | s=(inverse(K, self.q)*(M+self.x*r)) % self.q |
---|
| 129 | return (r,s) |
---|
| 130 | |
---|
| 131 | def _verify(self, M, sig): |
---|
| 132 | r, s = sig |
---|
| 133 | if r<=0 or r>=self.q or s<=0 or s>=self.q: |
---|
| 134 | return 0 |
---|
| 135 | w=inverse(s, self.q) |
---|
| 136 | u1, u2 = (M*w) % self.q, (r*w) % self.q |
---|
| 137 | v1 = pow(self.g, u1, self.p) |
---|
| 138 | v2 = pow(self.y, u2, self.p) |
---|
| 139 | v = ((v1*v2) % self.p) |
---|
| 140 | v = v % self.q |
---|
| 141 | if v==r: |
---|
| 142 | return 1 |
---|
| 143 | return 0 |
---|
| 144 | |
---|
| 145 | def size(self): |
---|
| 146 | "Return the maximum number of bits that can be handled by this key." |
---|
| 147 | return number.size(self.p) - 1 |
---|
| 148 | |
---|
| 149 | def has_private(self): |
---|
| 150 | """Return a Boolean denoting whether the object contains |
---|
| 151 | private components.""" |
---|
| 152 | if hasattr(self, 'x'): |
---|
| 153 | return 1 |
---|
| 154 | else: |
---|
| 155 | return 0 |
---|
| 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.y, self.g, self.p, self.q)) |
---|
| 168 | |
---|
| 169 | object=DSAobj |
---|
| 170 | |
---|
| 171 | generate_py = generate |
---|
| 172 | construct_py = construct |
---|
| 173 | |
---|
| 174 | class DSAobj_c(pubkey): |
---|
| 175 | keydata = ['y', 'g', 'p', 'q', 'x'] |
---|
| 176 | |
---|
| 177 | def __init__(self, key): |
---|
| 178 | self.key = key |
---|
| 179 | |
---|
| 180 | def __getattr__(self, attr): |
---|
| 181 | if attr in self.keydata: |
---|
| 182 | return getattr(self.key, attr) |
---|
| 183 | else: |
---|
| 184 | if self.__dict__.has_key(attr): |
---|
| 185 | self.__dict__[attr] |
---|
| 186 | else: |
---|
| 187 | raise AttributeError, '%s instance has no attribute %s' % (self.__class__, attr) |
---|
| 188 | |
---|
| 189 | def __getstate__(self): |
---|
| 190 | d = {} |
---|
| 191 | for k in self.keydata: |
---|
| 192 | if hasattr(self.key, k): |
---|
| 193 | d[k]=getattr(self.key, k) |
---|
| 194 | return d |
---|
| 195 | |
---|
| 196 | def __setstate__(self, state): |
---|
| 197 | y,g,p,q = state['y'], state['g'], state['p'], state['q'] |
---|
| 198 | if not state.has_key('x'): |
---|
| 199 | self.key = _fastmath.dsa_construct(y,g,p,q) |
---|
| 200 | else: |
---|
| 201 | x = state['x'] |
---|
| 202 | self.key = _fastmath.dsa_construct(y,g,p,q,x) |
---|
| 203 | |
---|
| 204 | def _sign(self, M, K): |
---|
| 205 | return self.key._sign(M, K) |
---|
| 206 | |
---|
| 207 | def _verify(self, M, (r, s)): |
---|
| 208 | return self.key._verify(M, r, s) |
---|
| 209 | |
---|
| 210 | def size(self): |
---|
| 211 | return self.key.size() |
---|
| 212 | |
---|
| 213 | def has_private(self): |
---|
| 214 | return self.key.has_private() |
---|
| 215 | |
---|
| 216 | def publickey(self): |
---|
| 217 | return construct_c((self.key.y, self.key.g, self.key.p, self.key.q)) |
---|
| 218 | |
---|
| 219 | def can_sign(self): |
---|
| 220 | return 1 |
---|
| 221 | |
---|
| 222 | def can_encrypt(self): |
---|
| 223 | return 0 |
---|
| 224 | |
---|
| 225 | def generate_c(bits, randfunc, progress_func=None): |
---|
| 226 | obj = generate_py(bits, randfunc, progress_func) |
---|
| 227 | y,g,p,q,x = obj.y, obj.g, obj.p, obj.q, obj.x |
---|
| 228 | return construct_c((y,g,p,q,x)) |
---|
| 229 | |
---|
| 230 | def construct_c(tuple): |
---|
| 231 | key = apply(_fastmath.dsa_construct, tuple) |
---|
| 232 | return DSAobj_c(key) |
---|
| 233 | |
---|
| 234 | if _fastmath: |
---|
| 235 | #print "using C version of DSA" |
---|
| 236 | generate = generate_c |
---|
| 237 | construct = construct_c |
---|
| 238 | error = _fastmath.error |
---|