I wrote this script to teach myself on how to do RSA key generation (public key e and private key d), and how to encrypt and decrypt message mathematically. This tool will also be used as a refresher if I have forgotten how to calculate the RSA mathematics. This learning tool presents how the Euclidean algorithm is used to find the gcd of two values, and to use extended Euclidean algorithm to find private key d.
Getting started, and introduction to RSA maths
Choose p and q, and find phi(n) and n
Get the public key e
Given plaintext m, public key e, encrypt m
The m has to be between 0 and n-1, so the choice of m cannot be greater than n = p.q.
Generate private key d, use extended Euclidean algorithm
Below is the instruction on how to find d with extended Euclidean algorithm.
First construct a table of 7 columns, t1 and t2 will always be 0 and 1 respectively, see below instruction generated by the learning tool.
First row.
Next row.
Next row, do not stop until r becomes 0.
Next row, keep going…
Next row, keep it up…
Final row, because the next row, the remainder r column will become 0.
The learning tool will draw the table and present in your browser, thanks to the plotly module, this table is to match your own hand written table to see if they are the same, if both the tabulated table and your hand written calculation are the same means you have got it right and you have grasped the algorithm.
Decrypt the ciphertext since the private key d is generated.
Another results, this time the d is a negative number
The python codes:
from math import sqrt
from random import randrange
from plotly.graph_objects import Figure, Table
# phi(n) = (p - 1) * (q - 1) where p and q are distinct prime numbers.
def phi(p, q):
return (p - 1) * (q - 1)
# Based on the excellent explanation on how to do
# extended Euclidean Algorithm: https://www.youtube.com/watch?v=-uFc7-wOplM
def multiplicative_inverse(e, phi):
q_list = list()
r1_list = list()
r2_list = list()
remainder_list = list()
t1_list = list()
t2_list = list()
t_list = list()
# extended Euclidean Algorithm assumptions:
# s1 = 1, s2 = 0
# t1 = 0, t2 = 1
print("To use extended Euclidean Algorithm draw a table with these columns "
"starting from the left: q, r1, r2, r, t1, t2, t, total 7 columns...\r")
t1, t2 = 0, 1
t1_list.append(t1)
t2_list.append(t2)
print(f"These are the assumptions, t1 = {t1} and t2 = {t2}.\r"
f"Purpose of finding t2 is to get the multiplicative inverse of e mod phi(n) = {e} mod phi({phi}).\r")
# re-arrange r1 and r2, r1 has to be greater than r2
if e < phi:
r1 = phi
r2 = e
else:
r1 = e
r2 = phi
r1_list.append(r1)
r2_list.append(r2)
print(f"Rearrange e and phi(n) where r1 must be greater than r2.\r"
f"In this case r1 is {r1} and r2 is {r2}.\r")
print("Calculation stops once r = 0.\r")
print("To calculate t, use this formula: t = t1 - t2 x quotient.\n")
while True:
quotient = r1 // r2
print(f"Write the quotient of r1 / r2 = {quotient} under column q.\r")
remainder = r1 % r2
print(f"Write the remainder of r1 / r2 = {remainder} under column r.\r")
if remainder != 0:
# left shift as long as remainder is not 0
t = t1 - t2 * quotient
print(f"Use the formula t = t1 - t2 x q find t: t1={t1} - t2={t2} x q={quotient} = {t}, "
f"write this under column t.\n")
print("On next row...\r")
r1 = r2
print(f"Shift the value of r2 ({r2}) to r1.\r")
r2 = remainder
print(f"Shift the value of r ({remainder}) to r2.\r")
t1 = t2
print(f"Shift the value of t2 ({t2}) to t1.\r")
t2 = t
print(f"Shift the value of t ({t}) to t2.\r")
t_list.append(t)
r1_list.append(r1)
r2_list.append(r2)
t1_list.append(t1)
t2_list.append(t2)
remainder_list.append(remainder)
q_list.append(quotient)
else:
# found the gcd and y which is also d -
# private key of RSA
print(f"On next row the column r will be 0, hence we have found the gcd and y.\r")
gcd = r2
y = t2
print(f"The gcd({e}, {phi}) = {gcd}, multiplicative inverse of {e} mod {phi} = {y}.\n")
break
print("Check your browser for the extended Euclidean Algorithm calculation table.\n")
fig = Figure(data=[Table(header=dict(values=['q', 'r1', 'r2', 'r', 't1', 't2', 't']),
cells=dict(values=[[ql for ql in q_list],
[r1l for r1l in r1_list], [r2l for r2l in r2_list],
[remainderl for remainderl in remainder_list],
[t1l for t1l in t1_list],
[t2l for t2l in t2_list],
[tl for tl in t_list]]))])
fig.show()
# the variables are named explicitly according to lecture notes.
if y < 0:
print(f"y is negative number: {y}, make it positive by adding {phi} "
f"until y becomes the first positive number.\r")
while y < 0:
y += phi
print(f"The y is now: {y}.\n")
return gcd, y
def is_prime(num):
# Reference:
# https://learnandlearn.com/python-programming/python-how-to/how-to-find-prime-number-in-python-examples-and-explanation
# 1 is not a prime, of course anything less than 1 is not as well.
if num <= 1:
return False
# 2 is a prime.
elif num == 2:
return True
# all even numbers are not prime
elif num % 2 == 0:
return False
else:
r = sqrt(num)
# 1, 2 and even numbers are validated.
# start from 3.
x = 3
# try all numbers
while x <= r:
# if a factor is found then it is not prime
# prime is a number divisible by itself and 1 only.
# if the number is made from another number it is composite.
if num % x == 0:
return False
# skip to another odd number
x += 2
return True
# Euclidean Algorithm to find gcd.
# gcd(a,b) = gcd(b, a mod b)
def gcd(a, b):
# gcd(a, b) = gcd(b, a mod b)
while b != 0:
remainder = a % b
# left shift
a = b
b = remainder
# found gcd, as remainder is 0.
return a
# e which is the public key of RSA,
# must be between 0 and phi(n).
def is_e_valid(e, phi):
if gcd(e, phi) == 1:
print(f"The public key e must be between 1 and {phi}, and gcd(e, phi(n)) = 1.\r")
print(f"Validated that gcd({e}, {phi}) = 1.\n")
return True
else:
return False
# n = p.q, to find modulus n for RSA key generation
def modulus(p, q):
return p * q
# RSA encryption is C = m^e mod n,
# RSA decryption is P = C^d mod n.
# d is a multiplicative inverse of e mod phi(n).
# e.d = 1 mod phi(n).
def rsa_crypto(text, key, mod, is_encrypt=1):
result = text**key % mod
if is_encrypt:
print(f"To encrypt {text} use this formula: C = m^e mod n, "
f"hence C = {text}^{key} mod {mod} = {result}.\r")
else:
print(f"To decrypt {text} use this formula: P = c^d mod n, "
f"hence P = {text}^{key} mod {mod} = {result}.\r")
return result
def rsa_operation(start, stop, m):
print("Randomly choose p, q and e, p and q are to calculate the modulus n, and e is the public key.\r")
print("Publish n and e, but keep p, q and d secret.\r")
print("The public key must be between 1 and phi(n), where phi(n) = (p-1).(q-1) "
"and p and q are distinct prime numbers.\r")
print("d is the private key which is the multiplicative inverse"
" of e mod phi(n), e.d = 1 mod phi(n).\n")
# Initialize p,q and e to 0.
p, q, e = 0, 0, 0
# evaluate if p is a prime number.
# evaluate if p and q are different (distinct prime numbers).
while p == q:
while not is_prime(p):
p = randrange(start, stop)
# evaluate if q is a prime number.
while not is_prime(q):
q = randrange(start, stop)
n = modulus(p, q)
# This is to ensure the message is less than n.
# if the n is smaller than m then choose p and q again.
if n < m:
p = 0
q = 0
euler = phi(p, q)
while not is_e_valid(e, euler):
e = randrange(1, euler)
print(f"Given p = {p} and q = {q} find phi(n) and n.\r")
print(f"Formula to find phi(n) = (p-1).(q-1), where p and q are distinct prime numbers.\r")
print(f"Hence phi(n) = ({p} - 1) x ({q} - 1) = {euler}.\r")
print(f"Find n, where n = p.q, hence n = {p} x {q} = {n}.\n")
print(f"Choose e, which is the public key, e must be between 1 and phi(n) = between 1 and {euler}.\r")
print(f"Public key {e} is chosen, as it is between 1 and {euler}, "
f"and gcd(e, phi(n)) = gcd({e}, {euler}) = 1.\n")
print(f"Given the plaintext is m = {m} and e = {e}.\r")
print(f"What is the ciphertext of {m}?\n")
c = rsa_crypto(m, e, n)
print(f"Ciphertext of {m}: {c}\n")
print(f"To decrypt {c}, you need d, use extended Euclidean Algorithm to find d.\r")
print(f"Use extended Euclidean Algorithm to find this gcd(e, phi(n)) = gcd({e}, phi({n})).\r")
print("Finding d, which is the private key...\n")
_, d = multiplicative_inverse(e, euler)
print(f"d = {d} which is the private key is a multiplicative inverse of {e} (mod {euler}).\n")
plaintext = rsa_crypto(c, d, n, is_encrypt=0)
print(f"Hence m is {plaintext}, decrypted with private key d: {d}...\n")
if __name__ == '__main__':
# original message m.
m = 10
start = 2
stop = 32
rsa_operation(start, stop, m)
Online RSA calculator
I was using this RSA calculator to validate the variables of my script.
cyruslab 