Implementing RSA in Python from Scratch

2024-03-01 22:17:08

Please be aware that it’s important for me to emphasise that the code and strategies introduced listed below are supposed solely for instructional functions and will by no means be employed in real-world functions with out cautious consideration and knowledgeable steerage.

On the identical time, understanding the ideas of RSA cryptography and exploring varied implementations is effective for instructional functions and understanding the right way to code encryption strategies, constructing safe encryption techniques for sensible use requires adherence to business requirements, greatest practices, and thorough safety assessments. An insufficient implementation or improper utilization of cryptographic strategies can result in extreme vulnerabilities, jeopardizing the confidentiality and integrity of delicate knowledge.

I am certain many programmers, notably internet builders have heard of the RSA cryptography system. RSA is an uneven cryptography system, which means that one key’s used for encryption and the opposite for decryption. I’ve seen a number of articles explaining the overall ideas of uneven cryptography, however I’ve not seen any that give easy-to-understand explanations of the mathematical background behind these algorithms, so I made a decision to write down this text.

Clarification of the Math behind RSA

For begin, as I’ve talked about within the paragraph above, to transmit an RSA-encrypted message, you want 2 keys. One that may solely encrypt and one that may decrypt. Let encryption key be denoted as e, the decryption key shall be denoted as d and the message shall be denoted as m. The important thing precept behind RSA is that within the following notion:

(m^e)^d ≡ m (mod n)

The problem of discovering d, figuring out e and n might be very laborious if these numbers are chosen correctly (as shall be demonstrated beneath).

However first, we have to introduce some new ideas in quantity idea.

a ≡ b (mod n) means that there’s an integer x such that a + nx = b. A extra intuitive clarification is that the reminder of a / n equals the reminder of b / n.
gcd(a, b) is the best quantity that divides each a and b.
lcm(a, b) is the smallest quantity that may be a a number of of each a and b.
λ(n) is a quantity such that x^λ(n) ≡ 1 (mod n) for any x such that gcd(x, n) = 1. From this you’ll be able to conclude that x^a ≡ x^b (mod n) if a ≡ b (mod λ(n))

Producing keys

Let’s make n = pq the place p and q are 2 prime numbers. Since λ(p) = p - 1 and λ(q) = q - 1 (lookup Fermat’s little theorem proof for why), λ(n) = (p - 1) * (q - 1).

Now we’ve to resolve ed ≡ 1 (mod λ(n)). e might be some prime quantity (normally 65537) and d might be calculated utilizing prolonged Euclidian’s algorithm (shall be written and defined within the code part) from the equation ed + xλ(n) = gcd(e, λ(n)) (d and x are coefficients to be calculated).

pair (e, n) is used for encryption ((m^e) % n) and pair (d, n) is used for decryption ((m^d) % n)

After computing the keys, p and q might be thrown away. Discover that with out p and q, discovering λ(n) would imply factorizing n, which isn’t a straightforward drawback to resolve for values of n as much as 2^2048, that are repeatedly used.

Implementing RSA in Python

First to record procedures and their steps:

keys era:

discover 2 random prime numbers, p and q
compute n = p * q and λ(n) = (p - 1) * (q - 1)
make e equal some prime quantity, e.g. e = 35537
compute d from equation ed + λ(n)x = gcd(e, λ(n)) = 1 utilizing Prolonged Euclidian Algorithm (from this level on we’ll name it eucalg)

Encryption:

divide the message into sections (of 256 bits if n is 2048-bit)
every part (denoted as m) is encrypted as (m^e) % n

Decryption:

divide the message into sections, identical as above
every part (denoted as m) is decrypted as (m^d) % n

Implementation of Prolonged Euclidian Algorithm

This algorithm depends on the truth that if x divides each a and b, there shall be a pair of coefficients (okay, l) such that:
a * okay + b * l = x
The algorithm finds these coefficients (and x) by repeatedly substracting the lesser argument from the larger one, till the lesser one turns into 0. As a substitute of repeatedly substracting, you’ll be able to calculate what number of occasions b might be substracted from a (okay = a // b) after which substratct b*okay. This optimization makes the algorithm run in O(log max(a, b)) which is so much faster.
Under is an implementation of the algorithm in Python:

def eucalg(a, b):
	# make a the larger one and b the lesser one
	swapped = False
	if a < b:
		a, b = b, a
		swapped = True
	# ca and cb retailer present a and b in type of
	# coefficients with preliminary a and b
	# a' = ca[0] * a + ca[1] * b
	# b' = cb[0] * a + cb[1] * b
	ca = (1, 0)
	cb = (0, 1)
	whereas b != 0:
		# okay denotes what number of occasions quantity b
		# might be substracted from a
		okay = a // b
		# a  <- b
		# b  <- a - b * okay
		# ca <- cb
		# cb <- (ca[0] - okay * cb[0], ca[1] - okay * cb[1])
		a, b, ca, cb = b, a-b*okay, cb, (ca[0]-k*cb[0], ca[1]-k*cb[1])
	if swapped:
		return (ca[1], ca[0])
	else:
		return ca

Discover that the perform above can produce destructive numbers for coefficients, so in case that occurs, all that we have to do is ready d to λ(n) - d.

Implementing quick exponentiation with modulo

Some would possibly counsel to simply use (b ** e) % n, however this strategy is just not superb time and reminiscence -wise as a result of b ** e might be very massive regardless of solely the final 2000 bits or so being wanted. The answer is to reinplement exponentiation with calculating modulo after each division.

Exponentiation implementation beneath has logarithmic time complexity. As a substitute of itterating from 1 to e and multiplying r (end result) by b, it itterates from essentially the most important little bit of e to the least important little bit of e, and at every bit it does r = r*r + bit. This works as a result of if r equals b^x and also you’re appending a bit to the top of x, new x shall be x * 2 + bit.

def modpow(b, e, n):
	# discover size of e in bits
	tst = 1
	siz = 0
	whereas e >= tst:
		tst <<= 1
		siz += 1
	siz -= 1
	# calculate the end result
	r = 1
	for i in vary(siz, -1, -1):
		r = (r * r) % n
		if (e >> i) & 1: r = (r * b) % n
	return r

Key era, encryption and decryption

Keys era, encryption and decryption have all been defined within the math part and the code beneath is solely implementation of that.

def keysgen(p, q):
	n = p * q
	lambda_n = (p - 1) * (q - 1)
	e = 35537
	d = eucalg(e, lambda_n)[0]
	if d < 0: d += lambda_n
        # each non-public and public key will need to have n saved with them
	return {'priv': (d, n), 'pub': (e, n)}

def numencrypt(m, pub):
	return modpow(m, pub[0], pub[1])

def numdecrypt(m, priv):
	return modpow(m, priv[0], priv[1])

Testing the code we’ve till now

I saved the code right into a file named rsa.py and run the next in Python shell:

>>> import rsa
>>> keys = rsa.keysgen(31337, 31357)
>>> keys
{'priv': (720926705, 982634309), 'pub': (35537, 982634309)}
>>> priv = keys['priv']
>>> pub = keys['pub']
>>> msg = 80087
>>> enc = rsa.numencrypt(msg, priv)
>>> enc
34604568
>>> dec = rsa.numdecrypt(enc, pub)
>>> dec
80087
>>>

Conclusion

Ultimately of writing this text I spotted that implementation of a usable Python RSA program is extra difficult than I initially speculated. Due to that, I made a decision to separate the subject up in a number of articles. With the code introduced on this article you will have all core components of RSA written. However you continue to want a random prime generator and plaintext encryption (numencrypt and numdecrypt are appropriate just for numbers m smaller in measurement than n). All these shall be included within the subsequent article that shall be printed shortly.

If you wish to proceed studying, we even have a Half 2 and even a Half 3 to this text for many who are desirous about Implementing RSA in Python from Scratch.