RSA (Rivest-Shamir-Adleman) Algorithm is
an asymmetric or public-key cryptography algorithm which
means it works on two different keys: Public Key and Private
Key. The Public Key is used for encryption and is known to
everyone, while the Private Key is used for decryption and must
be kept secret by the receiver. RSA Algorithm is named after
Ron Rivest, Adi Shamir and Leonard Adleman, who published
the algorithm in 1977.
Example of Asymmetric Cryptography:
If Person A wants to send a message securely to Person B:
Person A encrypts the message using Person B's Public Key.
Person B decrypts the message using their Private Key.
RSA Algorithm
RSA Algorithm is based on factorization of large number and
modular arithmetic for encrypting and decrypting data. It
consists of three main stages:
1. Key Generation: Creating Public and Private Keys
2. Encryption: Sender encrypts the data using Public Key to get
cipher text.
3. Decryption: Decrypting the cipher text using Private Key to
get the original data.
1. Key Generation
Choose two large prime numbers, say p and q. These prime
numbers should be kept secret.
Calculate the product of primes, n = p * q. This product is part of
the public as well as the private key.
Calculate Euler Totient FunctionΦ(n) as Φ(n) = Φ(p * q) = Φ(p) *
Φ(q) = (p - 1) * (q - 1).
Choose encryption exponent e, such that
1 < e < Φ(n), and
gcd(e, Φ(n)) = 1, that is e should be co-prime with Φ(n).
Calculate decryption exponent d, such that
(d * e) ≡ 1 mod Φ(n), that is d is modular multiplicative
inverse of e mod Φ(n). Some common methods to
calculate multiplicative inverse are: Extended Euclidean
Algorithm, Fermat's Little Theorem, etc.
Page 1
o We can have multiple values of d satisfying (d * e) ≡ 1
mod Φ(n) but it does not matter which value we choose
as all of them are valid keys and will result into same
message on decryption.
Finally, the Public Key = (n, e) and the Private Key = (n, d).
2. Encryption
To encrypt a message M, it is first converted to numerical
representation using ASCII and other encoding schemes. Now,
use the public key (n, e) to encrypt the message and get the
cipher text using the formula:
C = Me mod n, where C is the Cipher text and e and n are
parts of public key.
3. Decryption
To decrypt the cipher text C, use the private key (n, d) and get
the original data using the formula:
M = Cd mod n, where M is the message and d and n are parts
of private key.
Page 2
Example:
Let's say we choose p = 61 and q = 53.
n = p * q = 61 * 53 = 3233
(n) = (p-1)(q-1) = 60 * 52 = 3120
Let's choose e = 17 (a common choice).
d = 2753 (computed such that (17 * d) mod 3120 = 1)
So, the public key is (3233, 17), and the private key is
(3233, 2753).
Encryption
To encrypt a message, the sender Uses the public key (n, e)
provided by the recipient. Converts the plaintext message
(m) into a ciphertext (c) using the formula −
c = m^e mod n.
Suppose we want to encrypt the message "HELLO". We
convert it to ASCII: H(72) E(69) L(76) L(76) O(79). ASCII
value for capital A is 65.
We will encrypt each ASCII value separately −
H: C = 72^17 mod 3233 = 2103
E: C = 69^17 mod 3233 = 2464
L: C = 76^17 mod 3233 = 2190
L: C = 76^17 mod 3233 = 2190
O: C = 79^17 mod 3233 = 875
Decryption
Once the ciphertext (c) is received, the recipient uses their
private key (n, d) to decrypt the message. Computes the
plaintext message (m) using the formula −
Page 3
m = c^d mod n.
The recipient receives the ciphertext (2103, 2464, 2190,
2190, 875).
They use their private key to decrypt each value −
M = 2103^2753 mod 3233 = 72 (H)
M = 2464^2753 mod 3233 = 69 (E)
M = 2190^2753 mod 3233 = 76 (L)
M = 2190^2753 mod 3233 = 76 (L)
M = 875^2753 mod 3233 = 79 (O)
So, the decrypted message is "HELLO".
Diffie-Hellman algorithm:
The Diffie-Hellman algorithm is being used to establish a shared secret that
can be used for secret communications while exchanging data over a
public network using the elliptic curve to generate points and get the secret
key using the parameters.
For the sake of simplicity and practical implementation of the algorithm,
we will consider only 4 variables, one prime P and G (a primitive root of
P) and two private values a and b.
P and G are both publicly available numbers. Users (say Alice and Bob)
pick private values a and b and they generate a key and exchange it
publicly. The opposite person receives the key and that generates a
secret key, after which they have the same secret key to encrypt.
Step-by-Step explanation is as follows:
Page 4
Page 5
Page 6