rsa_misc.py

#
# RSA TOOLKIT v.0.1a
#
import gmpy,string

ALPHABET=string.lowercase+" '"
#
# Factorization
#
def factorize(Num):
	''' Return the prime factorization of a number '''
	divisors=list()
	x=gmpy.next_prime(1)
	a=Num
	while a>=0 and x<=a:
		r = a % x
		if r==0:
			a=gmpy.mpz( a/x )
			divisors = addprime(x,divisors)
		else:
			x=gmpy.next_prime(x)
	return divisors
def factorize_composite(NN):
	''' Inefficiently factorize a composite number N=p*q '''
	p=1
	while p <= NN:
		p=gmpy.next_prime(p)
		q=1
		while q <= NN:
			q=gmpy.next_prime(q)
			if p*q == NN:
				return [p,q]
	return []
def factorize_composite_fast(NN):
	''' Try to factorize a composite number N=p*q assuming 
		dist(sqrt(N),p)=dist(sqrt(N),q) '''
	for i in range(1, gmpy.sqrt(NN) ):
		a=gmpy.sqrt(NN)+i
		x=gmpy.sqrt( pow(a,2)- NN )
		p=a-x
		q=a+x
		if (gmpy.is_prime(p) and gmpy.is_prime(q) and p*q == NN):
			return [p,q]
	return []
#
# RSA Crypto
#
def do_rsa( msg=[] , e=1, N=1):
	''' Encrypy an array of messages '''
	cyp=list()
	for i in range(0,len(msg)):
		cyp.append( pow( msg[i],e,N) )
	return cyp
def calculate_d(N,e):
	''' Try to calculate "d" after a factorization attemp on N '''
	[p,q]=factorize_composite_fast(N)
	return calculate__d(p,q,e)
def calculate__d (p, q, e):
	''' Calculate "d" exponent given p,q and e '''
	phiN = (p-1)*(q-1)
	f = factorize(phiN)
	phiphiN=1
	for (x,h) in f:
		phiphiN=( phiphiN*(pow(x,h,phiN)-pow(x,h-1,phiN)) ) % phiN
	d = pow( e , phiphiN-1 , phiN )
	return d
def bruteforce(n,e,c):
	''' RSA bruteforce. Effective in case of low "e" exponent) '''
	k=1
	while True:
		mm=gmpy.root(c+k*n,e)
		k+=1
		for r in mm:
		if pow(r,e,n)==c:
			return r
#
# Encoding
#
def encode(msg):
	''' Encode message to hex '''
	return msg.encode('hex')
def decode(msg):
	''' Decode an hex encoded message'''
	return ("0%x"%msg).decode('hex')

def encode_per_char(message=""):
		msg=list()
		for a in message:
			msg.append(string.rfind(ALPHABET,a)+1)
		return msg
def decode_per_char(message=[]):
		msg=""
		for a in message:
			msg+= ALPHABET[a-1]
		return msg
#
# Misc
#
def addprime(prime,ll=[]):
	''' Append a prime to the list ? '''
	for i in range(0,len(ll)):
		(x,y)=ll[i]
		if x==prime:
			ll[i]=(x,y+1)
			return ll
	ll.append((prime,1))
	return ll