root/galaxy-central/eggs/pycrypto-2.0.1-py2.6-macosx-10.6-universal-ucs2.egg/Crypto/PublicKey/DSA.py

リビジョン 3, 6.5 KB (コミッタ: kohda, 14 年 前)

Install Unix tools  http://hannonlab.cshl.edu/galaxy_unix_tools/galaxy.html

行番号 
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
16from Crypto.PublicKey.pubkey import *
17from Crypto.Util import number
18from Crypto.Util.number import bytes_to_long, long_to_bytes
19from Crypto.Hash import SHA
20
21try:
22    from Crypto.PublicKey import _fastmath
23except ImportError:
24    _fastmath = None
25
26class error (Exception):
27    pass
28
29def 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
47def 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
103def 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
115class 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
169object=DSAobj
170
171generate_py = generate
172construct_py = construct
173
174class 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
225def 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
230def construct_c(tuple):
231    key = apply(_fastmath.dsa_construct, tuple)
232    return DSAobj_c(key)
233
234if _fastmath:
235    #print "using C version of DSA"
236    generate = generate_c
237    construct = construct_c
238    error = _fastmath.error
Note: リポジトリブラウザについてのヘルプは TracBrowser を参照してください。