Implementing RSA From Scratch in Python (Part 2)

Please note that it is essential for me to emphasize that the code and techniques presented here are intended solely for educational purposes and should never be employed in real-world applications without careful consideration and expert guidance.

At the same time, understanding the principles of RSA cryptography and exploring various implementations is valuable for educational purposes, and understanding how to code encryption methods and building secure encryption systems for practical use requires adherence to industry standards, best practices, and thorough security assessments. An inadequate implementation or improper usage of cryptographic techniques can lead to severe vulnerabilities, jeopardizing the confidentiality and integrity of sensitive data.

In our first article, Implementing RSA from Scratch in Python, the RSA key generation and integer encryption were explained and implemented. This is good for demonstrating how the algorithm works, but it is not really usable if you want to exchange encrypted messages with someone. To be usable, it needs big random prime generation and text encryption, so those will be explained in this part.

Random Prime Numbers

To make sure nobody can factorize your n and find the decryption key, it is recommended to use 2048-bit values for n. This means that the prime numbers should be around 1024 bits long. The method is to randomly generate numbers until a prime is found. Since the numbers generated are very big, heuristic tests such as Selfridge's conjure are preferable over classical methods which are a lot slower.

The PWS conjure states:

If a number p gives reminders 3 and 7 (mod 10) (equivalent of saying that p is odd and ±2 (mod 5)), then it is prime if the following conditions hold:

• 2^(p - 1) ≡ 1 (mod p)
• (p + 1)-th Fibonacci number ≡ 0 (mod p)

Fast exponentiation with modulo was already implemented in the last article, so only the Fibonacci number calculator with modulo needs to be implemented.

Fibonacci Number Calculation

 Let f be a function that calculates the next Fibonacci number, given the last 2.

• f(a, b) = (b, a + b)
• To calculate the 4th Fibonacci number, you'd do f(f(1, 1)).
• To calculate the 10th, you'd do f(f(f(f(f(f(f(f(1, 1)))))))), or simplified, (f^8)(1, 1).
• To calculate the n-th Fibonacci number you'd do (f^(n - 2))(1, 1).
• Since f is a linear function, it can be represented by a matrix.

[ 0 1 ]
[ 1 1 ]

(Matrix multiplication won't be explained in this article, so in case you don't know it, it is recommended that you look it up before continuing.)

Using matrices, you can calculate the n-th Fibonacci number like this:

[ 1 ] [ 0 1 ]^n  = [ (n - 1)-th Fibonacci number ]
[ 1 ] [ 1 1 ]    = [       n-th Fibonacci number ]

Matrix multiplication is associative ((M1 * M2) * M3 = M1 * (M2 * M3)) so you can apply the same optimization as in modpow from the last article.

# matrix multiplication
def sqmatrixmul(m1, m2, w, mod):
	mr = [[0 for j in range(w)] for i in range(w)]
	for i in range(w):
		for j in range(w):
			for k in range(w):
				mr[i][j] =(mr[i][j]+m1[i][k]*m2[k][j])%mod
	return mr

# fibonacci calculator
def fib(x, mod):
	if x < 3: return 1
	x -= 2
	# find length of e in bits
	tst = 1
	siz = 0
	while x >= tst:
		tst <<= 1
		siz += 1
	siz -= 1
	# calculate the matrix
	fm = [
		# function matrix
		[0, 1],
		[1, 1]
	]
	rm = [
		# result matrix
		# (identity)
		[1, 0],
		[0, 1]
	]
	for i in range(siz, -1, -1):
		rm = sqmatrixmul(rm, rm, 2, mod)
		if (x >> i) & 1:
			rm = sqmatrixmul(rm, fm, 2, mod)

	# second row of resulting vector is result
	return (rm[1][0] + rm[1][1]) % mod

The prime number generation can then be implemented like this: 

def genprime(siz):
	while True:
		num = (1 << (siz - 1)) + secrets.randbits(siz - 1) - 10;
		# num must be 3 or 7 (mod 10)
		num -= num % 10
		num += 3 # 3 (mod 10)
		# heuristic test
		if modpow(2, num - 1, num) ==1 and fib(num + 1, num) ==0:
			return num
		num += 5 # 7 (mod 10)
		# heuristic test
		if modpow(2, num - 1, num) ==1 and fib(num + 1, num) ==0:
			return num

Please note: Instead of using the random module, here, secrets are used. Random is good for generating statistically random numbers, but it can be predicted and is therefore less preferable in cryptography.

Plaintext Encryption and Decryption

Since everything is calculated modulo n, representing the whole byte array as a single number and encrypting it would result in data loss, so you should instead split the data up into subsequences and encrypt those separately. The longer the subsequences are, the smaller are chances of the message being guessed by randomly generating sequences until their ciphertexts match. Since n is 2048-bit, the biggest the sequence can be is 256 bytes (256 * 8 = 2048).

The message length will not necessarily be divisible by 256, so the last block will have to be padded by trailing 0x00s. Because of this, it is also good to store plaintext length together with ciphertext or inside the plaintext itself in case binary files are exchanged.

def encrypt_bytes(data, key):
	data = bytearray(data)
	cdata = bytearray()
	for i in range(0, len(data), 256):
		# read 256 bytes and store as long
		# to m
		m = 0
		for j in range(256):
			if i + j < len(data):
				m = (m << 8) + data[i + j]
			else:
				m <<= 8
		# encrypt m
		c = modpow(m, key[0], key[1])
		# store c into cdata
		for j in range(255, -1, -1):
			cdata.append((c >> (j * 8)) & 255)
	return bytes(cdata)

# both functions are essencially the same,
# the only difference is in which key you use
decrypt_bytes = encrypt_bytes

What's Next

If you want to continue reading, we continue this series with Parts 3 and 4. These two articles cover major subjects with our implementation of RSA in Python to cover other issues that could arise in the future.