Implementing RSA in Python from Scratch (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, 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.
Don't forget to read the firsrt article of the series Implementing RSA in Python from Scratch. You could be missing some detailed information for this – Part 2 Article – to make sense.
TheLastTechie
In the last article 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 Fibonacci number calculator with modulo needs to be implemented.
Fibonacci number calculation
Let f be a function that calculates next Fibonacci number, given last 2.
f(a, b) = (b, a + b)
First, to calculate 4th Fibonacci number you'd do f(f(1, 1)). Then to calculate 10th you'd do f(f(f(f(f(f(f(f(1, 1)))))))), or simplified, (f^8)(1, 1). Finally, to calculate n-th Fibonacci number you'd do (f^(n - 2))(1, 1).
Since f is a linear function, it can be represent 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 last article.
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 that, instead of using random module, here is used secrets. 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 encrypting 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
If you want to continue reading, we also have a Part 3 and Part 4 to this series of articles for those who are interested in Implementing RSA in Python from Scratch.
TheLastTechie
TheLastTechie
Do you like what you're reading from the CoderOasis Technology Blog? We recommend reading our Hacktivism: Social Justice by Data Leaks and Defacements as your next choice.
ExiledTech
The CoderOasis Community
Did you know we have a Community Forums and Discord Server? which we invite everyone to join us? Want to discuss this article with other members of our community? Want to join a laid back place to chill and discuss topics like programming, cybersecurity, web development, and Linux? Consider joining us today!
