What is RSA algorithm and how does it work?
The Rivest-Shamir-Adleman (RSA) encryption algorithm is an asymmetric cryptography algorithm that is one of the oldest and still commonly used today. RSA algorithm uses two mathematically linked key pairs to encrypt and decrypt data. One is known as the private key and the other is the public key. The public key can be shared publicly with anyone, but the private key must be only with the creator.
Either public or private key can be used to encrypt data, but the opposite must be used for decryption. And this is one of the reasons that this algorithm is widely used today.
The history of RSA algorithms goes back to 1977 which was invented by three computer scientists and cryptography specialists Ron Rivest, Adi Shamir, and Leonard Adleman at MIT.
How does is RSA algorithm work?
Now let’s see how the RSA algorithm actually works step by step.
1. Generating keys
- Select two large prime numbers (should be extremely large so that it can’t be figured out easily). When two large prime numbers are multiplied together, the result can only be broken down by only those two prime numbers and by the result and by one. The selected two prime numbers are x and y respectively.
- Multiply those prime numbers; n = x * y.
- Calculate the totient function on; ϕ(n)=(x−1) (y−1).
- Select an integer e, such that e is co-prime to ϕ(n) and 1 < e < ϕ(n). The pair of numbers (n,e) makes up the public key.
- Calculate d such that e.d = 1 mod ϕ(n).
d can be found using the extended euclidean algorithm. The pair (n,d) makes up the private key.
2. Encryption
Given a plaintext P, represented as a number, the ciphertext C is calculated as:
C = P^e mod n.3. Decryption
Using the private key (n,d), the plaintext can be found using:
P = C^d mod n.Implementation
Below code is the implementation of the RSA algorithm using Python codded by the programmer ANIRUDH GOTTIPARTHY at the University of Pennsylvania
