Mathematics of RSA Encryption Algorithm

What is RSA?

The Rivest-Shamir-Adleman (RSA) is an asymmetric encryption algorithm. Asymmetric Encryption is when a box(data) can be locked by one key and unlocked by other. locking key cannot unlock the box and vice-versa. The locking key is the public key and the unlocking key is the private key, Public key is called so, because it is publicly distributed, so anyone/everyone would send the user an encrypted msg, and the user can unlock it in private with the private key. By keeping private to the user-self, no hacker can get a method of unlocking it.

How Asymmetric Encryption is achieved?

We need a mathematical function such that

f: public key function , g: private key function
f-1(f(msg)) != msg
g(g-1(msg)) != msg
g(f(msg)) == msg

Signing Document via Asymmetric Encryption:

Digital Signature is the by-product of Asymmetric Encryption, In most asymmetric encryption algorithms (including RSA), public and private are just names, one can simply interchange them for locking and unlocking. Here is how to sign a document:

How to sign:

• Step 1: Calculate hash of the document using an unbreakable and popular hashing algorithm (for eg. SHA-256)
• Step 2: Make digest by performing the decryption function with the private key on that hash.
• Step 3: Send the document, digest, and hashing algorithm to the world.

How to Verify:

• Step 1: Calculate the hash of the document using the provided hashing algorithm, let's call it the "calculated hash".
• Step 2: Get the hash by performing the encryption function with the user's public key on that digest, let's call it the "given hash".
• Step 3: If "calculated hash" matches with the "given hash" then the document is authentic else not.

Mathematics of RSA:

for g and f should be such that g must relatively harder to perform so that it could not be cracked by brute force.

First, let's get this straight. Every string data can be represented as numbers or chunks of numbers, which can happen via ASCII or change it to binary then to decimal. So mathematical operation can be used on any and every data.

Consider m as the message. say m is 10, now we have to find 2 functions, one that will change it some else and the other that can change back!

Multiplication/Division:

let f(key, m) = key * m so now we have to distribute f and key but same key can be used to change it back!

Addition/Subtraction:

let f(key, m) = key + m so now we have to distribute f and key but same key can be used to change it back!

Trigonometry:

let f(..., m) = sin(... m) Here the problem is the decimal nature of output, can have different result at different machines!

Modulus: For those who are new to modulus function, it is the reminder of integer division.

x mod y => ky - x where ky > x for example: 7/5 = 1 and 2 = 7 mod 5

Here is the catch, for

2 = m mod 5 m can be 2, 7, 12... 5*(x) + 2 So a hacker with 2 (encrypted msg) and 5 cannot decode the m, but so can't we.

Let us try one more trick

3mmod 5 = x
for if m is 0, 1, 2, 3, 4 ... x is 1, 3, 4, 2, 1 ... respectively, m is uniformly distributed in 1 to 4. So a hacker with x (encrypted msg), 5 and 3 cannot decode the m, but still so can't we. Another major point to be noted is, if 3 < 5 exists, then x == 3 for some m and x < 5 exists always.

Now Let us merge both tricks.

memod n = x, m < n --> eq 1
m: message, e, n: some constants, x: encrypted message Let there be another equation

xdmod n = m --> eq 2
x: encrypted message, d, n: some constants, m: message
Let us substitute x in eq 2 with eq 1

(mdmod n)emod n = m
me * dmod n = m
m: message, e, d, n: some constants, x: encrypted message in other words: e -> public_key and d -> private_key All we need is do is define those constants and we are good to go!

Now Lets take a dive into history,

Introducing the Totient function aka Euler's phi function

phi(n) = m, m is the count of integers b/w [1, n], which are coprime(relatively prime) to n
for example, phi(8) = 2 as, gcd(6, n) == 1 holds true only for 1 and 5.

• Interestingly enough, phi(prime) is always prime - 1, as all the numbers before prime gave their gcd as 1, given the definition of prime is exactly that.
• Another Observation is phi(p1 * p2) = phi(p1) * phi(p2)

Let's cook with the ingredients we have.

• phi(n) = Set of all the co-primes
• 3emod 5 = x,
  for if e is 0, 1, 2, 3, 4 ... x is 1, 3, 4, 2, 1 ... respectively, e is uniformly distributed in 1 to 4.
• Let there be ak, such that ak= 1 mod n
• Since, is k one of the uniformly distributed power, it must be within phi(n), therefore phi(n) = kc, there c is some constant.
• Now if raise both side with power for c
• It becomes: akc= aphi(n)= 1 mod n This is Fermat–Euler Theorem

Merge both the discoveries:

a * aphi(n)mod n = aedmod n
a * aphi(n) * c= aedmod n
(phi(n) * c) + 1 = e * d
if n is product of big prime number then phi(n) easy to calculate and n itself hard to find (prime factorization would take a lot of time) d = (c * phi(n) + 1) / e
where c is calculated such that d becomes an integer (n, e) : public key, (n, d): private key

Bibliography / Resources:

RSA Brief: youtube.com/watch?v=wXB-V_Keiu8

Khan Academy: khanacademy.org/computing/computer-science/..

Proof of Fermat–Euler Theorem: youtube.com/watch?v=5pswKNgVZSg

RSA SIgning: cs.cornell.edu/courses/cs5430/2015sp/notes/..