Algoritmo RSA

For this week, the homework was to implement the RSA Algorithm, for doing this I have to create private and public keys and create sockets for the server and client. I follow the next steps:

• I choose p and q, these numbers have to be primes and random
• Then I get n by multiplying p*q
• After this I calculate phi, using this formula (p-1)(q-1)
• Next I implement the Extended Euclidean Algorithm to get d (for private key)
• Then I choose e and check that this number is greater than 1 but less than phi
• Then create the public.txt and private.txt
• Create the server.py and client.py following this steps:

Well, with this assignment it was difficult to me to understand the Extended Euclidean Algorithm and I lost a lot of time with that and I could only get the parameters for the public and private keys, and because of that I couldn't do the sockets.

I thank my classmate Obed Guevara for helping to understand the part of the sockets, and during this week I would get this RSA algorithm complete.

Well, here is the code for getting the parameters.

	#!/usr/bin/python
	import random
	def getParameters():
	p = getPrime()
	q = getPrime()
	n = p*q
	fi = (p-1)*(q-1)
	return p,q,n,fi
	def getPrime():
	while(True):
	x = random.randint(3,1000)
	if ((x % 2) != 0):
	break
	return x
	def gcd(a,b):
	while(b != 0):
	r = a % b
	a = b
	b =r
	return a
	def getD(a,b):
	x=0
	y=0
	d=0
	if(b==0):
	x2=1
	y2=0
	if(b > 0):
	x1 =0
	x2 =1
	y1 = 1
	y2 = 0
	q =0
	r =0
	while(b>0):
	q = (a/b);
	r = a - q*b;
	x = x2-q*x1;
	y = y2 - q*y1;
	a = b;
	b = r;
	x2 = x1;
	x1 = x;
	y2 = y1;
	y1 = y;
	return x2
	def getE(fi):
	x = random.randint(1,fi)
	a =x
	b=fi
	while(b!=0):
	r= a%b
	a = b
	b = r
	if(a!=1):
	getE(fi)
	return x
	def main():
	p,q,n,fi = getParameters()
	e = getE(fi)
	d = getD(n,fi)
	print "p=",p
	print "q=",q
	print "n=",n
	print "fi=", fi
	print "e=",e
	print "d=",d
	main()

view raw rsa.py hosted with ❤ by GitHub

Sources

• Extended Euclidean Algorithm - Wolfram &  trans4mind
• Wikipedia
• rsa