[python]RSA mathematics learning tool

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
rsa1

Choose p and q, and find phi(n) and n
rsa2

Get the public key e
rsa3

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.
rsa4

Generate private key d, use extended Euclidean algorithm
rsa5
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.
rsa6

First row.
rsa7

Next row.
rsa8

Next row, do not stop until r becomes 0.
rsa9

Next row, keep going…
rsa10

Next row, keep it up…
rsa11

Final row, because the next row, the remainder r column will become 0.
rsa12

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.
rsa13

Decrypt the ciphertext since the private key d is generated.
rsa14

Another results, this time the d is a negative number
rsa15
rsa16
rsa17

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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s