# | |

# number.py : Number-theoretic functions | |

# | |

# 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: number.py,v 1.13 2003/04/04 18:21:07 akuchling Exp $" | |

bignum = long | |

try: | |

from Crypto.PublicKey import _fastmath | |

except ImportError: | |

_fastmath = None | |

# Commented out and replaced with faster versions below | |

## def long2str(n): | |

## s='' | |

## while n>0: | |

## s=chr(n & 255)+s | |

## n=n>>8 | |

## return s | |

## import types | |

## def str2long(s): | |

## if type(s)!=types.StringType: return s # Integers will be left alone | |

## return reduce(lambda x,y : x*256+ord(y), s, 0L) | |

def size (N): | |

"""size(N:long) : int | |

Returns the size of the number N in bits. | |

""" | |

bits, power = 0,1L | |

while N >= power: | |

bits += 1 | |

power = power << 1 | |

return bits | |

def getRandomNumber(N, randfunc): | |

"""getRandomNumber(N:int, randfunc:callable):long | |

Return an N-bit random number.""" | |

S = randfunc(N/8) | |

odd_bits = N % 8 | |

if odd_bits != 0: | |

char = ord(randfunc(1)) >> (8-odd_bits) | |

S = chr(char) + S | |

value = bytes_to_long(S) | |

value |= 2L ** (N-1) # Ensure high bit is set | |

assert size(value) >= N | |

return value | |

def GCD(x,y): | |

"""GCD(x:long, y:long): long | |

Return the GCD of x and y. | |

""" | |

x = abs(x) ; y = abs(y) | |

while x > 0: | |

x, y = y % x, x | |

return y | |

def inverse(u, v): | |

"""inverse(u:long, u:long):long | |

Return the inverse of u mod v. | |

""" | |

u3, v3 = long(u), long(v) | |

u1, v1 = 1L, 0L | |

while v3 > 0: | |

q=u3 / v3 | |

u1, v1 = v1, u1 - v1*q | |

u3, v3 = v3, u3 - v3*q | |

while u1<0: | |

u1 = u1 + v | |

return u1 | |

# Given a number of bits to generate and a random generation function, | |

# find a prime number of the appropriate size. | |

def getPrime(N, randfunc): | |

"""getPrime(N:int, randfunc:callable):long | |

Return a random N-bit prime number. | |

""" | |

number=getRandomNumber(N, randfunc) | 1 | |

while (not isPrime(number)): | |

number=number+2 | |

return number | |

def isPrime(N): | |

"""isPrime(N:long):bool | |

Return true if N is prime. | |

""" | |

if N == 1: | |

return 0 | |

if N in sieve: | |

return 1 | |

for i in sieve: | |

if (N % i)==0: | |

return 0 | |

# Use the accelerator if available | |

if _fastmath is not None: | |

return _fastmath.isPrime(N) | |

# Compute the highest bit that's set in N | |

N1 = N - 1L | |

n = 1L | |

while (n<N): | |

n=n<<1L | |

n = n >> 1L | |

# Rabin-Miller test | |

for c in sieve[:7]: | |

a=long(c) ; d=1L ; t=n | |

while (t): # Iterate over the bits in N1 | |

x=(d*d) % N | |

if x==1L and d!=1L and d!=N1: | |

return 0 # Square root of 1 found | |

if N1 & t: | |

d=(x*a) % N | |

else: | |

d=x | |

t = t >> 1L | |

if d!=1L: | |

return 0 | |

return 1 | |

# Small primes used for checking primality; these are all the primes | |

# less than 256. This should be enough to eliminate most of the odd | |

# numbers before needing to do a Rabin-Miller test at all. | |

sieve=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, | |

61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, | |

131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, | |

197, 199, 211, 223, 227, 229, 233, 239, 241, 251] | |

# Improved conversion functions contributed by Barry Warsaw, after | |

# careful benchmarking | |

import struct | |

def long_to_bytes(n, blocksize=0): | |

"""long_to_bytes(n:long, blocksize:int) : string | |

Convert a long integer to a byte string. | |

If optional blocksize is given and greater than zero, pad the front of the | |

byte string with binary zeros so that the length is a multiple of | |

blocksize. | |

""" | |

# after much testing, this algorithm was deemed to be the fastest | |

s = '' | |

n = long(n) | |

pack = struct.pack | |

while n > 0: | |

s = pack('>I', n & 0xffffffffL) + s | |

n = n >> 32 | |

# strip off leading zeros | |

for i in range(len(s)): | |

if s[i] != '\000': | |

break | |

else: | |

# only happens when n == 0 | |

s = '\000' | |

i = 0 | |

s = s[i:] | |

# add back some pad bytes. this could be done more efficiently w.r.t. the | |

# de-padding being done above, but sigh... | |

if blocksize > 0 and len(s) % blocksize: | |

s = (blocksize - len(s) % blocksize) * '\000' + s | |

return s | |

def bytes_to_long(s): | |

"""bytes_to_long(string) : long | |

Convert a byte string to a long integer. | |

This is (essentially) the inverse of long_to_bytes(). | |

""" | |

acc = 0L | |

unpack = struct.unpack | |

length = len(s) | |

if length % 4: | |

extra = (4 - length % 4) | |

s = '\000' * extra + s | |

length = length + extra | |

for i in range(0, length, 4): | |

acc = (acc << 32) + unpack('>I', s[i:i+4])[0] | |

return acc | |

# For backwards compatibility... | |

import warnings | |

def long2str(n, blocksize=0): | |

warnings.warn("long2str() has been replaced by long_to_bytes()") | |

return long_to_bytes(n, blocksize) | |

def str2long(s): | |

warnings.warn("str2long() has been replaced by bytes_to_long()") | |

return bytes_to_long(s) |