RSA Algorithm

So after a long time of scratching my head to learn RSA algorithm, i have finally figured it out!!.

all thanks to this youtube video: NeuralNine Channel

So how how does RSA alogrithm work?
So basically you have:
Public Key
Private Key
where public key is used for encryption ad private key is used for decryption(cause it doesnt matter if some guy takes your public key and encrypts a message)

So lets take an example of Alice and Bob(Generic but sure):

So Alice has a message that she wants to send to Bob,(But Alice doesn't want anyone else to see)
So what she does is take the public key of Bob(cause anyone can access public key of anyone) and encrypts it and sends the Encrypted Message to Bob

and then Bob gets the crypted message and decrypted it using his private key B and then gets the message

but now the question becomes how does this witch craft even work??

So this is how it works

Setup

So you need is-

• p - a random prime number #1
• q - a random prime number #2
• n - product of p and q (p.q)
• O(n) - eulars totient value of n( cant even pronounce this but it is simple)
• e - public key(sort of)
• d - private key(sort of)

So with all that ingredients you get

• public Key -(e,n) - used for encryption
• private Key - (d,n) - used for decrytpion

Note - when we say 'e' is public key is true but when we need to encrypt something we also need n, therefore public key that we usually have is zipped version of (e,n) to base 64. that is same for private key too, but private key is zipped as (d,n,p,q,dp,dq,qinv) which i will explain it later on so dont worry about that)

Prerequistes

• co-prime 2 number a and b are co-prime if gcd(a,b) = 1 which essentially means there is no number that can divide a and b to get a integer value which is not 1.
• mod mod essentially means reminder so A ≡ r mod B means A/B => A = B*m + r your simple division rule interesting stuff (A-r) = B*m so, (A-r) ≡ modB

Step-1 Get the prime numbers

so first thing we need is 2 prime numbers p and q.
now they are generated randomly using some algorithms similiar to random number generator but they are usually very large!!
but for our example we will take:

p = 11
q = 13

Step-2 Find n - product of those 2 prime number

this is very simple just multiply those 2

n = p.q
  = 11.13
  = 143

therefore n = 143

Step-3 find O(n) ( this part is actually simple than it sounds)

Note O(n) is not represented by 'O' its represented by epsilon but i cant find it in my keyboard

Definition-

    O(x) => number of values from [1,x-1] that are co-prime
ex: O(8) => 1, 3, 5, 7
    therefore O(8) = 4 ( 4 prime numbers)

>Note- O(x) = x-1                       if x is prime(think about it)

therefore, O(n) = O(143)
                = O(n)
                = O(p*q)
                = O(p) * O(q)
                = (p-1) * (q-1)                       ,by our rule
                = 10 * 12
                = 120
therefore O(n) = 120

Step-4 Picking public key (e)

Logic: e should be 2<e<O(n) where e and O(n) are co-prime
So we pick e = 7

Note: e could have been any co-prime number below O(n), for O(120) there are possible 32 possibilities but we just picked 7 cause its a cool number!! (you could also pick 11 or even 13 cause logic wise this is also true)

Note: in my mind i though it could be any prime number when i realize 5 even tho is a prime will not work here gcd(120, 5) = 5 they are not co-prime!! ( this really solved my understanding of co-primes)

Note: usually in real cases when p and q are very very large, e is picked as e = 65537 ( reason, i have no idea)

Step- 5 finding private key (d)

Logic=> should satisfy this condition

e.d ≡ 1 mod O(n)

so how can we solve that
Option #1 brute force(easiest but too slow for real cases)
try all the possibities and check the condition
Option #2 Extended Euclidean Algorithm

Extended Euclidean Algorithm

what we have, 
                e.d ≡ 1 mod O(n)
     what we know already, 
                          e and O(n) are co-prime
     therefore,
                  e*x + O(n)*y = 1

where x is considered inverse modulo of e (which i will explain why)

also back to,             e.d ≡ 1 mod O(n)
can be also written as    **(e*d) - 1** is divisible by O(n)

So,                    e*d - 1 = k* O(n)       where k is some number( its quotent btw)
     exchanging LHS and RHS we get,
                      e*d - k* O(n) = 1

                      e*d + (-k)* O(n) = 1
           compare with e*x + O(n)*y = 1

d is inverse modulo of e

So why that matters??

Lets use,      GCD( O(n) , e) = 1
               GCD( 120, 7) = 1
        now it can be re-written as,

                    |
            120 = 7*17 + 1                     (7 is e and 1 is rem)

              1 = 120 - 7*17
              1 = 7*(-17) + 1* 120
compare to,   1 = e* d    + k *O(n)

d = -17 

Note: now technically private key is -17, it must be a positive number so to get the positive number we do inverse of d

d ≡ (-17) mod (120)

because A ≡ r mod B also be written as r ≡ A mod B

-17 ≡ d^-1 mod (120)

-17 ≡ (103) mod (120)                 ,with a bit of calculation

therefore d = 103

Step- 6 Final Result

we get
public key = (e,n)
private key = (d,n)

Note: Now public key (e,n) means we get a public key by taking e and n and zipping it(where we get it in base64 which is like ac32d983a or something like that). so for calculation like encrpyting it we unzip the public key and get the original e and n for encryption calculation

Note: private Key is can be (d,n) but now a days it is also zipped with (d, n, p, q, dp, dq, qinv) where those extra values make the decryption faster , like x4 times faster!!

So back to the example

Alice wants to send message to Bob
assume message = 15 (ya a very secret message)

so how it is encrypted is we take public key of B(a35cd694dcd9422 or something)
and unzip it to get our original e = 7 and n = 143
so we do,

 Cipher = message ^ e mod n          (this is why we need both e and n)
               = 15^7 mod 143
               = 115

Now this cypher text is taken by Bob who decrypts it with his private key (d,n)

 Message = cipher ^ d mod n
              = 115 ^ 103 mod 143
              = 15 !!!!

we finally did it !!!