Euclid to RSA - Asymmetric Encryption

At the foundation of RSA are discoveries of popular mathematicians whose formulas shall be discussed with practical simplicity in this article.

Before we begin, although not in many, precise details, the concepts I cover in this post should be enough to understand RSA ultimately to a decent depth.

What is the GCD or the Greatest Common Divisor?

The GCD for two numbers will be the greatest number that can divide them both without any remainder.For e.g, GCD for 3 and 6 is 3 and that for 3 and 5 is 1.

Euclidean Algorithm to find the Greatest Common Divisor

References:

Here's a quote from the wiki article.

The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number.

Here's the function that implements the above description.

def gcd(a, b):
    if a == b:
        return a
    elif b > a:
        return gcd(b, a)
    else:
        return gcd(b, a-b)         

Let's take two numbers and try to break down the flow of this function:

• Take 24, 40
• This function needs the greater number to be the first argument which is clear from the clause:

if b > a:
  return gcd(b, a)         

• So we initially call gcd(24, 40). now a = 24 ; b = 40 .
• It satisfies the 2nd condition b > a, so now it calls gcd(40, 24)
• Now a = 40 ; b = 24 . This satisfies the 3rd condition a > b.
• So now a = 24, b = 40 - 24 and therefore the call is gcd(24, 16).
• now, a = 24, b = 16, 3rd condition satisfied, call is gcd(16, 8)
• now, a = 16, b = 8, 3rd condition satisfied, call is gcd(8, 8)
• now, a=8, b=8, this satisfies the 1st condition, therefore 'a' is returned.

And if you tried checking 8 is indeed the biggest number that can divide both 24 and 40 without a reminder.

Let's take another relatively smaller pair of numbers of run it by the algorithm:

• a=16; b=21; call=gcd(16, 21)
• Now let's not manually track the flow like in the last exercise, so, let's just look at the successive input values for a and b through a print statement before the if: print(a, b)

(16, 21)
(21, 16)
(16, 5)
(5, 11)
(11, 5)
(5, 6)
(6, 5)
(5, 1)
(1, 4)
(4, 1)
(1, 3)
(3, 1)
(1, 2)
(2, 1)
(1, 1)
1        

GCD for 16 and 21 is 1. So what does it make both of the numbers? Co-primes.

Pretty soon a slightly more optimized way of finding the GCD was discovered.

Here's a quote from the wiki article:

The version of the Euclidean algorithm described above (and by Euclid) can take many subtraction steps to find the GCD when one of the given numbers is much bigger than the other. A more efficient version of the algorithm shortcuts these steps, instead replacing the larger of the two numbers by its remainder when divided by the smaller of the two (with this version, the algorithm stops when reaching a zero remainder). With this improvement, the algorithm never requires more steps than five times the number of digits (base 10) of the smaller integer. This was proven by Gabriel Lamé in 1844

Here's a function that implements the optimized version to obtained the GCD:

def gcd(a, b):
    if a==0:
        return b
    return gcd(b%a, a)         

Let's try and break this function down and try draw some inferences about it:

1st iteration:

• 2nd number is divided by the 1st number and a reminder is obtained; this is reminder-1.
• Therefore, 1st number 'a' becomes divisor-1.
• So, the call for the next iteration is gcd(reminder-1, divisor-1)

2nd iteration:

• This time, a=reminder-1; b=divisor-1
• The call for the next iteration requires two things "b%a" and "a".
• So reminder-2=divisor-1 % reminder-1.
• And, divisor-2=reminder-1

Nth iteration:

• reminder-n = divisor n-1 % reminder n-1
• divisor-n = reminder n-1

To explain further:

In the current iteration, you get a 'reminder' by dividing the 2nd input by the 1st input and therefore, the 'divisor' is the 1st input.

Before initiating the next iteration i.e., 'pre' next iteration, its 1st input will be the reminder and its 2nd input will be the divisor that we just obtained.

In the next iteration, again we calculate b%a where we'll be dividing the 'divisor' by the 'reminder' to get the 'new reminder' and the 'current' reminder becomes the 'new' divisor, all for the subsequent iterations.

In conclusion:

From the 2nd iteration in this function, we continuously divide the 'divisor' by the 'reminder' until the 'new' reminder is zero at which point the 'new' divisor will be the gcd.

Euler's Totient function

References:

fi(n) for any integer n is the number of numbers between 1 and n-1 that that do not share factors with n or are co-primes with n. In other words, the GCD between any number (from 1 to n-1) and n should be 1 to be counted by Totient Function.

The article referenced above is enough to understand the various optimized implementation methods through code. Ultimately, Euler's totient function should adhere to the following description:

input: any positive integer 'n'

output: number of numbers from 1 to n-1 which are coprimes with 'n'        

Here's the mathematical expression for it:

Essentially, it means fi(n) = (p1 - 1)(p2 - 1)...(pn - 1) where p1 to pn are prime factors of n. So, instead of iteratively counting the number of co primes from 1 to n-1, this formula can be implemented to reduce complexities.

RSA (Rivest Shamir Adleman) Algorithm

References:

If you've watched the video under 'References' then, it might not even be necessary for you to read ahead as you're almost sorted with understanding RSA.

Nonetheless, if you're still reading, then please know I am going to be setting to e according to the rules followed in the video rather than in the article although it also works to use the conditions used in the article.

So, here's a sample implementation.

1. Pick random two prime numbers p and q.

p = 3
q = 5        

2. Find n from p and q.

n = p*q
n = 15        

3. Calculate phi(n)

We've already discussed different methods of implementing Euler's Totient Function and some useful articles have been linked earlier.

fi(n) = (p -1) * (q -1)
fi(15) = 8         

4. Choose 'e'

• 1 < e < fi(n) therefore: 1 < e < 8
• not sharing factors or co-primes with n and fi(n) so 15 and 8.

Maybe 7? It doesn't share factors with either n or fi(n) and is less than 8. try using the program shared earlier to compute the gcd's and confirm.

so e is 7 and the encryption key (e, n) is (7, 15)

5. Choose 'd'

Based on the reference, the rule for setting d can be interpreted in two very similar ways.

1. d*e (mod fi(n)) = 1 i.e., reminder of ( d*e % fi(n) )
2. d*e - k*fi(n) = 1        

Except, the 2nd expression just means that fi(n) can be subtracted 'k' times from d*e if the resulting reminder is '1'.

So,

d*7 - k*8 = 1

d =15; k = 13 satisfy the equation.
        

Therefore, the decryption key (d, n) can be (15, 15).

Let's try implementing it!

So, as done in the above video, let's try to encrypt 'b' and decrypt to get it back.

Encryption, keys -> (7, 15)

• take b = 8
• 3^7 ( mod 15) = 2

Decryption, keys -> (15, 15)

• decrypted_value = 2^15 (mod 15) = 8
• 8 -> 'b'

So, here's a simple Go program I've written to encrypt and decrypt other values. Run it in any Golang environment available online.

package main
?
import (
??? "fmt"
??? "math"
)

func encrypt(x float64) float64 {
??????? var raised_x float64 = math.Pow(x, 7)
??????? var encrypted float64 = math.Mod(raised_x, 15)
??????? return encrypted
}

func decrypt(y float64) float64 {
??????? var raised_y float64 = math.Pow(y, 15)
??????? var decrypted float64 = math.Mod(raised_y, 15)
??????? return decrypted
}

func main() {
??????? var inp_no float64
??????? inp_no = 12
??????? fmt.Printf("Input:? %v? will be encrypted with keys (7, 15)\n", inp_no)
??????? var encr float64 = encrypt(inp_no)
??????? fmt.Printf("Here's the encrypted value: %v\n", encr)
??????? fmt.Printf("The encrypted value, %v? will be decrypted with keys (15, 15)\n", encr)
??????? var decr float64 = decrypt(encr)
??????? fmt.Printf("Here's the decrypted value: %v\n", decr)
}        

We've seen how the public and private keys are calculated but let's put a finger on the most important aspect.

How does RSA provide security?

References:

In Public Key Infrastructure, the two popular and basic terms are Public and Private Keys. Private Key can be considered protected since it's not exposed.

But the Public Key is! So, does that make the user vulnerable? We shall see..

Basically, we can assume, the information revealed of the Public Key are its numbners 'e' and 'n'. Check the sample RSA implementation earlier if required.

If 'n' were as small as 21, one could instantly make out the prime factors and there by cracking the key-pairs. But in reality, the value for 'n' is monstrous. For e.g., for a number like 8723467823524, any two large prime factors could have been picked.

And it's supposed to be of impractical and huge computational expense to compute and crack the two prime numbers used to calculate the public key and private key.

TLDR; you may know the 'n' and 'e' but good luck finding the 'p' and 'q' soon enough to threaten one's security.

Thanks, if you've read so far. I'll be back on more posts to explore more concepts and implementations.