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