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

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

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

行番号 
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
15from Crypto.PublicKey import pubkey
16from Crypto.Util.number import *
17from Crypto.Hash import SHA
18
19class error (Exception):
20    pass
21
22HASHBITS = 160   # Size of SHA digests
23
24def 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
107def 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
119class 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
169object = qNEWobj
170
Note: リポジトリブラウザについてのヘルプは TracBrowser を参照してください。