RSA with Larger Prime Numbers#
Extending on from the RSA Algorithm example, we will now use larger prime numbers to demonstrate the RSA algorithm and how the time taken to decrypt the message increases with the size of the prime numbers.
Show code cell source
import numpy as np
import sympy
from sympy import mod_inverse, isprime
import random
from math import gcd
Generate a Prime Number Function#
We will generate 2 function for this, the first is for randomly generating a prime number between a range we will define. The second function is for code reusability, this will print out all our outputs in a nice format.
def generate_prime(start=100000, end=800000):
while True:
num = random.randint(start, end)
if sympy.isprime(num):
return num
def print_rsa_values(p, q, n, e, totient_n, message, ciphertext, decrypted_message):
print(f"Our original value of p and q were: {p} and {q}")
print(f"Our original value of n was: {n}")
print(f"Our original value of e was: {e}")
print(f"Our calculated value of totient_n was: {totient_n}")
print(f"Our original message was: {message}")
print(f"Our encrypted message was: {ciphertext}")
print(f"Our decrypted message was: {decrypted_message}")
print(f"Is the decrypted message the same as the original message? {message == decrypted_message}")
The RSA algorithm on 5 digit prime numbers#
Here the total time for generating the keys and encrypting/decrypting a message is shown. You can see that it takes a bit longer to generate the keys and encrypt/decrypt a message when using 5 digit prime numbers. With it being \(40.1 μs\) for the entire process.
%%time
p = 10427
q = 10663
n = p * q
e = 17
message = 1234
totient_n = euler_phi(p) * euler_phi(q)
while gcd(e, totient_n) != 1:
e += 2 # Increment e until it's coprime with totient_n
d = find_private_key(e, totient_n)
ciphertext = encrypt_message(message, e, n)
decrypted_message = decrypt_message(ciphertext, d, n)
CPU times: user 36 μs, sys: 0 ns, total: 36 μs
Wall time: 40.5 μs
print_rsa_values(p, q, n, e, totient_n, message, ciphertext, decrypted_message)
Our original value of p and q were: 10427 and 10663
Our original value of n was: 111183101
Our original value of e was: 17
Our calculated value of totient_n was: 111162012
Our original message was: 1234
Our encrypted message was: 104710521
Our decrypted message was: 1234
Is the decrypted message the same as the original message? True
The RSA algorithm on 10 digit prime numbers#
Here the total time for generating the keys and encrypting/decrypting a message is shown. You can see that it takes a bit longer to generate the keys and encrypt/decrypt a message when using 10 digit prime numbers. With it now being \(26.5~ms\) for the entire process, a significant increase from the 5 digit prime numbers.
%%time
p = generate_prime(1000000000, 8000000000)
q = generate_prime(1000000000, 8000000000)
n = p * q
e = 17
message = 123456789
totient_n = euler_phi(p) * euler_phi(q)
while gcd(e, totient_n) != 1:
e += 2 # Increment e until it's coprime with totient_n
d = find_private_key(e, totient_n)
ciphertext = encrypt_message(message, e, n)
decrypted_message = decrypt_message(ciphertext, d, n)
CPU times: user 27.2 ms, sys: 0 ns, total: 27.2 ms
Wall time: 26.5 ms
print_rsa_values(p, q, n, e, totient_n, message, ciphertext, decrypted_message)
Our original value of p and q were: 37201553 and 14549159
Our original value of n was: 541251309643927
Our original value of e was: 17
Our calculated value of totient_n was: 541251257893216
Our original message was: 123456789
Our encrypted message was: 514680304925327
Our decrypted message was: 123456789
Is the decrypted message the same as the original message? True
The RSA algorithm on 15 digit prime numbers#
Here the total time for generating the keys and encrypting/decrypting a message is shown. You can see that it takes longer to generate the keys and encrypt/decrypt a message when using 15 digit prime numbers. With it now being \(4.7~s\) for the entire process, which is a significant jump from 10 digit prime numbers and even more so from 5 digit prime numbers.
%%time
p = generate_prime(100000000000000, 900000000000000)
q = generate_prime(100000000000000, 900000000000000)
n = p * q
e = 17
message = 123456789
totient_n = euler_phi(p) * euler_phi(q)
while gcd(e, totient_n) != 1:
e += 2 # Increment e until it's coprime with totient_n
d = find_private_key(e, totient_n)
ciphertext = encrypt_message(message, e, n)
decrypted_message = decrypt_message(ciphertext, d, n)
CPU times: user 4.7 s, sys: 2 ms, total: 4.7 s
Wall time: 4.71 s
print_rsa_values(p, q, n, e, totient_n, message, ciphertext, decrypted_message)
Our original value of p and q were: 817140172394107 and 547754557755289
Our original value of n was: 447592253753814692862971681923
Our original value of e was: 17
Our calculated value of totient_n was: 447592253753813327968241532528
Our original message was: 123456789
Our encrypted message was: 266981944652092286561115982209
Our decrypted message was: 123456789
Is the decrypted message the same as the original message? True
The RSA algorithm on 18 digit prime numbers#
Here the total time for generating the keys and encrypting/decrypting a message is shown. You can see that it takes longer to generate the keys and encrypt/decrypt a message when using 18 digit prime numbers. With it now being \(1~min~48~s\) for the entire process, which is a significant jump from 15 digit prime numbers and even more so from 10 digit prime numbers.
%%time
p = generate_prime(100000000000000000, 900000000000000000)
q = generate_prime(100000000000000000, 900000000000000000)
n = p * q
e = 17
message = 123456789
totient_n = euler_phi(p) * euler_phi(q)
while gcd(e, totient_n) != 1:
e += 2 # Increment e until it's coprime with totient_n
d = find_private_key(e, totient_n)
ciphertext = encrypt_message(message, e, n)
decrypted_message = decrypt_message(ciphertext, d, n)
CPU times: user 1min 48s, sys: 997 μs, total: 1min 48s
Wall time: 1min 48s
print_rsa_values(p, q, n, e, totient_n, message, ciphertext, decrypted_message)
Our original value of p and q were: 415573428518459957 and 543966113095135777
Our original value of n was: 226057862616805912578094787852581589
Our original value of e was: 17
Our calculated value of totient_n was: 226057862616805911618555246238985856
Our original message was: 123456789
Our encrypted message was: 160107104791976571231752716075044555
Our decrypted message was: 123456789
Is the decrypted message the same as the original message? True
The RSA algorithm on 19 digit prime numbers#
The final example shows the RSA algorithm on 19 digit prime numbers. Here the total time for generating the keys and encrypting/decrypting a message is shown. You can see that it takes longer to generate the keys and encrypt/decrypt a message when using 19 digit prime numbers. With it now being \(~10~min~13~s\) for the entire process, which is a significant jump from 18 digit prime numbers and even more so from 15 digit prime numbers.
%%time
p = generate_prime(1000000000000000000, 9000000000000000000)
q = generate_prime(1000000000000000000, 9000000000000000000)
n = p * q
e = 17
message = 123456789
totient_n = euler_phi(p) * euler_phi(q)
while gcd(e, totient_n) != 1:
e += 2 # Increment e until it's coprime with totient_n
d = find_private_key(e, totient_n)
ciphertext = encrypt_message(message, e, n)
decrypted_message = decrypt_message(ciphertext, d, n)
CPU times: user 10min 12s, sys: 92 ms, total: 10min 13s
Wall time: 10min 13s
print_rsa_values(p, q, n, e, totient_n, message, ciphertext, decrypted_message)
Our original value of p and q were: 5187424496365756861 and 6896938881277935473
Our original value of n was: 35777349702678600972672615955165030253
Our original value of e was: 17
Our calculated value of totient_n was: 35777349702678600960588252577521337920
Our original message was: 123456789
Our encrypted message was: 2177553986524605235606780047389748843
Our decrypted message was: 123456789
Is the decrypted message the same as the original message? True
So as you can see, the RSA algorithm is incredibly powerful and secure, however, it can be slow to compute when using large prime numbers. This is why it’s important to use large prime numbers to ensure the security of the algorithm. The RSA algorithm often uses numbers that are hundreds of digits long to ensure that it’s secure.
Although the RSA algorithm is secure, it’s important to note that it can be vulnerable to attacks such as the timing attack and the low exponent attack. This is why it’s important to use large prime numbers and to ensure that the public and private keys are kept secure.