Public Key Algorithms - RSA

Seguridad de la Información y Criptografía
Homework 4

The homework for this week was:
"Implement RSA authentication in Python for a client-server system with sockets."

I will describe what the code should do:

1. The server open a socket, and wait for a client.
2. The client start a session with the server.
3. The server send a random "x" to the client.
4. The client calculate a f(x) where the function can be anyone.
5. Get from a user file the (d, n) previously created.
6. Calculate r = (y^d)mod(n), and send it to the server.
7. Send to the server the name of the current user and the r.
8. The server receive the the data, and open a file with a list of all the users.
9. The server find the correct public key (e, n) from the current user.
10. The server calculate y = (r^e)mod(n) and get the same "y" that the client calculate.
11. Verify if the "y" received is equal to f(x) in the server. (This is for authenticate the user)
12. If the previous sentence was true, send to the client a verification message. (I send "OK" and the client print "Welcome")
13. If not, close the connection. (My code send form the server "NO" and when the client receive this print "Something was wrong")

Generator of public and private keys

	#!/usr/bin/python
	import socket
	import random
	import math
	import sys
	# verify if "x" is a prime number
	def is_prime(x):
	div = 2
	r = int(math.sqrt(x))
	while (div <= r):
	if (x%div == 0):
	return False
	div = div+1
	return x
	# found the prime numbers between "x" and "y"
	# return a list of the found primes
	def search_primes():
	x = 100
	y = 999
	primes = []
	while (x < y):
	prime = is_prime(x)
	if (prime != False):
	primes.append(prime)
	x = x+1
	return primes
	# return the gcd of "a" and "b"
	def gcd(a, b):
	if (a < b):
	a,b = b,a
	while (b != 0):
	r = a%b
	a = b
	b = r
	return a
	# used to get a "s" where (n*s)mod(phi(n)) = 1
	def euclides(a, b):
	if (b == 0):
	return a,1,0
	else:
	x,d,y = euclides(b,a%b)
	return x,y,d-(a/b)*y
	# return the keys
	def keys():
	# create a list of primes
	primes = search_primes()
	total = len(primes) - 1
	# choose a different prime number for p and q
	p = q = 1
	while (p == q):
	p = primes[random.randint(0,total)]
	q = primes[random.randint(0,total)]
	n = p*q
	phi = (p-1)*(q-1)
	# get a number prime n
	# check if gcd(n,phi) = 1
	# if not, try with other n
	check = 0
	while(check != 1):
	e = primes[random.randint(0,total)]
	check = gcd(e, phi)
	x,d,y = euclides(e, phi)
	d = d%phi
	return e,d,n
	def main():
	if (len(sys.argv) > 1):
	quantity = int(sys.argv[1])
	file_server = open('users', 'w')
	for i in range(quantity):
	# get the keys
	e,d,n = keys()
	# create a file for the private key in one user
	user = 'user'+str(i)
	file_user = open(user,'w')
	# save the public keys in the file "users"
	public = ' %d %d' %(e,n)
	file_server.write(user+public+'\n')
	#save the private in the file for this user
	private = ' %d %d' %(d,n)
	file_user.write(user+private)
	file_user.close()
	file_server.close()
	else:
	print 'Forgot arguments'
	main()

view raw create_key.py hosted with ❤ by GitHub

Server

	#!/usr/bin/python
	import socket
	import random
	# the same function is in client.py
	def funcx(x):
	y = int(x**2 + x)
	return y
	def main():
	s = socket.socket()
	s.bind(('localhost', 9090))
	s.listen(1)
	print 'Socket opened'
	sc, addr = s.accept()
	print 'Sesion started'
	# choose a random "x" and send it to the client
	x = random.randint(10,100)
	sc.send(str(x))
	print 'Sended to the client x =', x
	# receive the "user" and the "r"
	data = sc.recv(1024)
	data = data.split()
	user = data[0]
	r = int(data[1])
	print 'User name: ', user
	print 'And received r =', r
	# get the public key of the current user
	f = open('users', 'r')
	get_user = ''
	while (get_user != user):
	line = f.readline()
	sep = line.split()
	get_user = str(sep[0])
	e = int(sep[1])
	n = int(sep[2])
	f.close()
	print 'Public key: (%d, %d)' %(e,n)
	# use the public key to decrypt
	y = r**e%n
	# verify if the "y" received is the same that f(x)
	if (y == funcx(x)):
	print 'User accepted'
	sc.send('OK')
	else:
	print 'Something was wrong'
	sc.send('NO')
	sc.close()
	s.close()
	print 'Sesion closed'
	main()

view raw server.py hosted with ❤ by GitHub

Client

	#!/usr/bin/python
	import socket
	import sys
	# the same function is in server.py
	def funcx(x):
	y = int(x**2 + x)
	return y
	def main():
	if (len(sys.argv) > 1):
	user = sys.argv[1]
	try:
	s = socket.socket()
	s.connect(('localhost', 9090))
	print 'Connected with the server'
	except:
	print 'No server available'
	sys.exit()
	# get the "d" and "n" from the user file
	f = open(user, 'r')
	line = f.readline()
	sep = line.split()
	d = int(sep[1])
	n = int(sep[2])
	f.close()
	print 'Current user: ', user
	print 'Private key: (%d, %d)' %(d,n)
	x = s.recv(1024)
	print 'The server send me x =', x
	y = funcx(int(x))
	print 'After the function f(x) =', y
	r = y**d%n
	print 'My f(x) encrypted, r =', r
	s.send(user+' '+str(r))
	status = s.recv(1024)
	if (status == 'OK'):
	print 'Welcome'
	else:
	print 'Something was wrong'
	s.close()
	print 'Sesion closed'
	else:
	print 'Forgot arguments'
	main()

view raw client.py hosted with ❤ by GitHub

Execution

First of all the folder with the three python files.

I send an argument to the "create keys" program for create 5 users. Create one file per each user with the private key, and all the public keys for all the users are in the file "users".

When we want to run the programs, we need to open two terminals, one for the server and one for the client.

The client receive an argument that indicate the user to use in this running.

The numbers indicate what part of the list was mentioned in the first part in this post. Some numbers aren't in the same sequence that the list and others are omitted becasue the program do it internal and don't have a debug print.

Server:

[1] Socket opened
Sesion started
[3] Sended to the client x = 43
User name:  user3
And received r = 209263
[9] Public key: (349, 225391)
User accepted
Sesion closed

Client:

[2] Connected with the server
Current user:  user3
[5] Private key: (68117, 225391)
The server send me x = 43
[4] After the function f(x) = 1892
[6] My f(x) encrypted, r = 209263
[12] Welcome
Sesion closed

This is the file of user that the server use to find if the current user is allowed or not.

And the keys for the user that I used in the example. Check that the "n" is the same in the use3 in the previous image.

For the function of euclides(), I saw the pseudo-code of the reference [1], and for the gcd() I saw the pseudo-code from the book "Matematica Discreta - Richard Johnsonbaugh".

References:
[1] - Fundamentos matemáticos del método RSA