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: by Sang-Yoon Chang, Ph.D. —

2 thoughts on “VIII. RivestShamirAdleman / RSA Cipher

  1. I’d must examine with you here. Which is not one thing I usually do! I get pleasure from reading a post that can make folks think. Additionally, thanks for permitting me to comment!


Leave a Reply

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

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

Facebook photo

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

Connecting to %s