VIII. RivestShamirAdleman / RSA Cipher

Prime Factorization

Consider prime numbers “p” and “q ” such that, there exist a number “n”, multiple of “p”and “q” (p x q = n).

Now, let’s consider very large prime numbers (e.g. 300 digits long ) “p” and “q” such that, there exist a very large number (e.g. 4000 digits long) “n”,multiple of “p”and “q” (p x q = n).

Here is the thing, you can easily compute the multiple of very large prime numbers “p” and “q” then find “n”. However, can you find “p” and “q” from very large number “n” ? This problem is the main idea of RSA Cipher.

Basically, in RSA, derive a public key “e” and private key “d” from “p” and “q”. Then, use “e”, “d” and “n” for encryption and decryption.

RSA Algorithm

RSA was invented by R. Rivest, A. Shamir, and L. Adleman, who first publicly described the algorithm, in 1977. However, as mentioned previous article,  Clifford Cocks, an English mathematician working for GCHQ, had developed an equivalent system in 1973, but this was not declassified until 1997.

In RSA, keys are typically 1024 to 4096 bit long, where security is based on the difficulty of finding “p” and “q” of very large “n”.

RSA Encryption and Decryption

Encryption(message-m): Alice obtains Bob’s public key {e, n} then computes c = [m^(e) mod(n)], where 0 <= m < n.

Decryption(ciphertext-c): Bob uses Alice’s private key {d, n} then computes m = [c^(d) mod(n)] that can be also written as m = [ [c^(e) mod(n)]^(d) mod(n) ], which is also equals to, m = [ m^(e*d) mod(n) ].

RSA Public Key(“e”) and Private Key(“d”)

At first, each user select two large prime numbers “p” and “q” then computes “n” such that, n = p x q. Here, to continue, we need to know about Euler Totient (phi) Function that counts the number of positive integers less than n that are co-prime (only common factor is 1) to n. That is in this case ϕ(n) = (p-1) x (q-1).

Now, we can select random “e”, from the interval 1 < e < ϕ(n) and where gcd(e*ϕ(n)) = 1 [gcd: greatest common divisor]. After selecting “e”, we can get “d” by solving equation(Extended Euclidean algorithm) e*d ≡ 1 mod(ϕ(n)), where 0 <= d <= n.

For instance: For p = 11 & q = 13, n =11*13 = 143 and ϕ(n) =(p-1) x (q-1) = 10*12 = 120. Select e = 11, then from d*11 = 1 mod 120, d = 11. Hence, for m = 7, c = 7^(11) mod(143) = 106 and m = 106^(11) mod(143) = 7.

O.S. Tapsin

Resources: https://d3c33hcgiwev3.cloudfront.net/_dc21492af5d308efbaa6702af3ab29c8_slides_rsa.pdf?Expires=1568678400&Signature=GJxJpRbg7dkjqAxd-afpk-G4OFm3b6m~bIxvWm~NXrm7pwgVEZDMrsxPYfl2RE0KPOvEbkcP7~bmFMOl8cuLBPIRF5ZGPSdaftqVMeNJGeGoJwXSWWwvKNFa86FDkLmmKu9ZWPv2M1TJRZsYBNXTwCxmJiFoT8KKhtera5EY4pc_&Key-Pair-Id=APKAJLTNE6QMUY6HBC5A by Sang-Yoon Chang, Ph.D. — https://people.csail.mit.edu/rivest/Rsapaper.pdf — http://www.math.uchicago.edu/~may/VIGRE/VIGRE2007/REUPapers/FINALAPP/Calderbank.pdf — https://www.whitman.edu/mathematics/higher_math_online/section03.08.html —