RSA Algorithm is a widely used asymmetric encryption algorithm used for secure data transmission.
Thank you for reading this post, don't forget to subscribe!- It is named after its inventors: Ron Rivest, Adi Shamir, and Leonard Adleman.
Key Concepts:
1.) Asymmetric Encryption:
RSA uses two keys:
- A public key to encrypt messages.
- A private key to decrypt messages.
The two keys are mathematically related, but knowing the public key does not easily reveal the private key.
2.) Based on Prime Factorization:
- RSA’s security depends on the mathematical difficulty of factoring a large number (product of two primes).
- For large primes, factoring n=p×q becomes computationally infeasible.
How RSA Works:
1.) Key Generation:
- Step 1: Choose two large prime numbers,
pandq.- These primes must be distinct and randomly selected.
- Step 2: Calculate the modulus:
n=p×q- This number n is used in both public and private keys.
- Step 3: Compute Euler’s Totient Function:
ϕ(n)=(p−1)×(q−1)- This represents the number of integers less than n that are coprime to n.
- Step 4: Choose a public exponent e: e must satisfy:
1<e<ϕ(n)gcd(e, ϕ(n)) = 1
- Step 5: Compute the private exponent d:
d×e ≡ 1 mod ϕ(n)- This means that d is the modular inverse of
e mod ϕ(n).
- This means that d is the modular inverse of
Final Keys:
- Public Key: (e,n)
- Private Key: (d,n)
2.) Encryption:
Given a plaintext m, where 0 ≤ m < n: To encrypt a message ‘m’.
- Calculate ciphertext (c):
c = me mod n
- Encrypt the message using the recipient’s public key.
3.) Decryption:
To recover the plaintext from the ciphertext c:
m = cd mod n
- Decrypt using your private key.