[3] | 1 | # |
---|
| 2 | # ElGamal.py : ElGamal encryption/decryption and signatures |
---|
| 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: ElGamal.py,v 1.9 2003/04/04 19:44:26 akuchling Exp $" |
---|
| 14 | |
---|
| 15 | from Crypto.PublicKey.pubkey import * |
---|
| 16 | from Crypto.Util import number |
---|
| 17 | |
---|
| 18 | class error (Exception): |
---|
| 19 | pass |
---|
| 20 | |
---|
| 21 | # Generate an ElGamal key with N bits |
---|
| 22 | def generate(bits, randfunc, progress_func=None): |
---|
| 23 | """generate(bits:int, randfunc:callable, progress_func:callable) |
---|
| 24 | |
---|
| 25 | Generate an ElGamal key of length 'bits', using 'randfunc' to get |
---|
| 26 | random data and 'progress_func', if present, to display |
---|
| 27 | the progress of the key generation. |
---|
| 28 | """ |
---|
| 29 | obj=ElGamalobj() |
---|
| 30 | # Generate prime p |
---|
| 31 | if progress_func: |
---|
| 32 | progress_func('p\n') |
---|
| 33 | obj.p=bignum(getPrime(bits, randfunc)) |
---|
| 34 | # Generate random number g |
---|
| 35 | if progress_func: |
---|
| 36 | progress_func('g\n') |
---|
| 37 | size=bits-1-(ord(randfunc(1)) & 63) # g will be from 1--64 bits smaller than p |
---|
| 38 | if size<1: |
---|
| 39 | size=bits-1 |
---|
| 40 | while (1): |
---|
| 41 | obj.g=bignum(getPrime(size, randfunc)) |
---|
| 42 | if obj.g < obj.p: |
---|
| 43 | break |
---|
| 44 | size=(size+1) % bits |
---|
| 45 | if size==0: |
---|
| 46 | size=4 |
---|
| 47 | # Generate random number x |
---|
| 48 | if progress_func: |
---|
| 49 | progress_func('x\n') |
---|
| 50 | while (1): |
---|
| 51 | size=bits-1-ord(randfunc(1)) # x will be from 1 to 256 bits smaller than p |
---|
| 52 | if size>2: |
---|
| 53 | break |
---|
| 54 | while (1): |
---|
| 55 | obj.x=bignum(getPrime(size, randfunc)) |
---|
| 56 | if obj.x < obj.p: |
---|
| 57 | break |
---|
| 58 | size = (size+1) % bits |
---|
| 59 | if size==0: |
---|
| 60 | size=4 |
---|
| 61 | if progress_func: |
---|
| 62 | progress_func('y\n') |
---|
| 63 | obj.y = pow(obj.g, obj.x, obj.p) |
---|
| 64 | return obj |
---|
| 65 | |
---|
| 66 | def construct(tuple): |
---|
| 67 | """construct(tuple:(long,long,long,long)|(long,long,long,long,long))) |
---|
| 68 | : ElGamalobj |
---|
| 69 | Construct an ElGamal key from a 3- or 4-tuple of numbers. |
---|
| 70 | """ |
---|
| 71 | |
---|
| 72 | obj=ElGamalobj() |
---|
| 73 | if len(tuple) not in [3,4]: |
---|
| 74 | raise error, 'argument for construct() wrong length' |
---|
| 75 | for i in range(len(tuple)): |
---|
| 76 | field = obj.keydata[i] |
---|
| 77 | setattr(obj, field, tuple[i]) |
---|
| 78 | return obj |
---|
| 79 | |
---|
| 80 | class ElGamalobj(pubkey): |
---|
| 81 | keydata=['p', 'g', 'y', 'x'] |
---|
| 82 | |
---|
| 83 | def _encrypt(self, M, K): |
---|
| 84 | a=pow(self.g, K, self.p) |
---|
| 85 | b=( M*pow(self.y, K, self.p) ) % self.p |
---|
| 86 | return ( a,b ) |
---|
| 87 | |
---|
| 88 | def _decrypt(self, M): |
---|
| 89 | if (not hasattr(self, 'x')): |
---|
| 90 | raise error, 'Private key not available in this object' |
---|
| 91 | ax=pow(M[0], self.x, self.p) |
---|
| 92 | plaintext=(M[1] * inverse(ax, self.p ) ) % self.p |
---|
| 93 | return plaintext |
---|
| 94 | |
---|
| 95 | def _sign(self, M, K): |
---|
| 96 | if (not hasattr(self, 'x')): |
---|
| 97 | raise error, 'Private key not available in this object' |
---|
| 98 | p1=self.p-1 |
---|
| 99 | if (GCD(K, p1)!=1): |
---|
| 100 | raise error, 'Bad K value: GCD(K,p-1)!=1' |
---|
| 101 | a=pow(self.g, K, self.p) |
---|
| 102 | t=(M-self.x*a) % p1 |
---|
| 103 | while t<0: t=t+p1 |
---|
| 104 | b=(t*inverse(K, p1)) % p1 |
---|
| 105 | return (a, b) |
---|
| 106 | |
---|
| 107 | def _verify(self, M, sig): |
---|
| 108 | v1=pow(self.y, sig[0], self.p) |
---|
| 109 | v1=(v1*pow(sig[0], sig[1], self.p)) % self.p |
---|
| 110 | v2=pow(self.g, M, self.p) |
---|
| 111 | if v1==v2: |
---|
| 112 | return 1 |
---|
| 113 | return 0 |
---|
| 114 | |
---|
| 115 | def size(self): |
---|
| 116 | "Return the maximum number of bits that can be handled by this key." |
---|
| 117 | return number.size(self.p) - 1 |
---|
| 118 | |
---|
| 119 | def has_private(self): |
---|
| 120 | """Return a Boolean denoting whether the object contains |
---|
| 121 | private components.""" |
---|
| 122 | if hasattr(self, 'x'): |
---|
| 123 | return 1 |
---|
| 124 | else: |
---|
| 125 | return 0 |
---|
| 126 | |
---|
| 127 | def publickey(self): |
---|
| 128 | """Return a new key object containing only the public information.""" |
---|
| 129 | return construct((self.p, self.g, self.y)) |
---|
| 130 | |
---|
| 131 | |
---|
| 132 | object=ElGamalobj |
---|