Cryptography 101: RSA Algorithm
How the key pairs are mathematically derived with application of RSA algorithm
This article is originally appeared on https://luniverse.io/cryptography-101-rsa-algorithm/
The term encryption refers to a process of taking a message and “scrambling” its contents so that only the intended person can decrypt the ciphertext (encrypted message). In cryptography, there are two types of encryption:
- Symmetric encryption This is the simplest type of encryption that involves a single key that both encrypts AND decrypts ciphertext. e.g. Blowfish, AES, RC4, DES, RC5, RC6, etc. The most widely used symmetric algorithm is AES-128, AES-192, and AES-256.
- Asymmetric encryption (Public-Key Cryptography) This is a method which the key to encrypt the plaintext (original message) is distinguished from the key to decrypt the ciphertext. A public key is used to encrypt the plaintext, while a private key is used to decrypt the ciphertext. e.g. RSA, DSA, Elliptic Curve DSA, PKCS, etc.
Up until the 1970s, cryptography had been based on symmetric keys- that is, the sender encrypts their message using a specific key and the receiver decrypts the message using an identical key.
For Alice and Bob to communicate securely with symmetric encryption method, they must share identical keys. However, establishing a shared key is often impossible if Alice when Bob cannot physically meet or requires extra communications overhead.
In 1977, three mathematicians named Rivest, Shamir, and Adleman, developed the RSA encryption method which became one of the most powerful and secure algorithm today. Main characteristics of RSA is that it doesn’t require key to be exchanged between parties; the basic idea behind RSA is that it uses large prime numbers to generate a pair of keys- 1 public key and 1 private key.
In this article, we will look at how the key pairs are mathematically derived with application of RSA algorithm.
0. Assumption
The security strength of RSA algorithm is based on an assumption that factoring a large number into product of prime numbers* is very difficult and time-consuming. For example, if we have two prime numbers 89 and 71, we can easily compute that the product of the two numbers is 6,319. However, it would not be easy if you are given 6,319 and were asked to factor this number into product of prime numbers. (Of course, computers are able to solve our example above within milliseconds)
*Definition 1) We say that a positive integer x > 1 is a prime number if the complete set of divisors of x is 1 and itself. (e.g. 2, 3, 5, 7, ….)
1. Select a random set of prime numbers p and q such that p ≠ q
In this example, we will use $p = 11,\ q = 17$ for convenience.
(Note that in real life, one should use a very large prime number to ensure security of the encrypted message)
2. Calculate n = p x q
$n = 11 * 17 = 187$
3. Calculate Φ(n) = (p-1)(q-1)
Definition 2) Φ(n), also known as Euler’s totient function, is the number of positive integers less than n that are relatively prime to n. Definition 3) Two integers a and b are said to be relatively prime (coprime) if gcd(a,b) = 1.
So we have: $Φ(n) = Φ(187) = (11–1)(17–1) = 160$
4. Select integer e such that gcd(Φ(n), e) = 1, where 1 < e < Φ(n)
We want e such that gcd(160, e) = 1.
Let’s choose e = 7 and see if gcd(160, 7)= 1:
$160 = 2⁵ * 5$
Since 7 is prime and 7 does not divide 160, we know 7 and 160 are relatively prime.
5. Solve for d such that d*e modΦ(n) ≡ 1
We want a number d such that 7*d mod 160 = 1; i.e., we want to find the modular inverse of e with respect to Φ(n). To do so, we use the extended Euclidean algorithm to solve our equation.
160x + 7y = 1
⇔ 160 = 7(22) + 6
⇔ 7 = 6(1) + 1
Now we perform backward substitution to express 1 as a linear combination of 7 and 160:
1 = 7–6(1)
⇔ 7 — (160–7(22))
⇔ 7(23) — 160(1)
⇔ 7(23) + 160(-1)
⇒ x = -1,\ y = 23.
⇒ 160(-1) + 7(23) = 1.
Therefore, we have d ≡ 23 mod 160.
Since 23 ≡ 23 mod 160, we will choose d = 23 for convenience.
- For detailed explanation on modular arithmetic and Euclidean algorithm, check out following links:
- Modular Arithmetic
- Euclidean Algorithm
6. Find public key and private key
So far, we have all the values needed to generate the public key and private key.
p = 11, q = 17
n = 187
Φ(n) = 160
e = 7
d = 23
∴ Public key = KU = {e, n} = {7, 187}
Private Key = KR = {d, n} = {23, 187}
Now that we have generated the key pairs using the RSA algorithm, we will try encrypting and decrypting using our key pairs.
Want to read more? Click here.
If you’re interested in introducing blockchain on your service,
feel free to reach out at any time here support@lambda256.io.
Or you can schedule quick online meeting on here.
