app/gdata/Crypto/PublicKey/DSA.py - soc - Git at Google


 #
 #   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

	#
	# 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.xr)) % 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 = (Mw) % self.q, (rw) % 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