RSA Asymmetrical
Algorithm
RSA, named after Ron Rivest, Adi Shamir, and Leonard
Adleman, is one of the most widely used encryption methods.
It is essential for securing online communication and ensuring
data integrity.
What Is RSA?
• RSA (Rivest-Shamir-Adleman) is a form of asymmetric encryption developed in
1977. Unlike symmetric encryption, RSA uses two distinct keys:
• Public Key: Shared openly and used for encrypting messages.
• Private Key: Kept secret by the owner and used for decrypting messages.
• This approach ensures enhanced security because even if the public key is
intercepted, the encrypted message cannot be decrypted without the private key.
• For example:
• Alice wants to send a private message to Bob. She encrypts the message using
Bob's public key.
• Only Bob, who holds the corresponding private key, can decrypt the message and
read it.
Three Main Steps of RSA
1. Key Generation:
• This process involves creating a public-private key pair.
• The public key is shared openly, while the private key remains confidential.
2. Encryption:
• A sender encrypts the message using the recipient's public key.
• The encrypted message can only be decrypted by the corresponding private
key.
3. Decryption:
• The recipient uses their private key to decrypt the ciphertext, restoring the
original message.
• RSA ensures that encrypted data can only be decoded by its intended recipient.
Step By Step Guide For Key
Generation:
Choose Two Large Prime Numbers:
• Select primes p and q (e.g., p = 61, q = 53).
( Larger primes = larger n = harder to factor )
Calculate n:
• n = p × q.
• n = 61 × 53 = 3233. (Think of n as a box that holds our encryption system, it is
used to generate both public and private keys)
Compute Totient ϕ(n):
• ϕ(n) = (p-1) × (q-1)
• ϕ(3233) = (61-1) × (53-1) = 3120.
Choose Public Exponent e:
• e is a number used for encryption. It must satisfy two rules:
• 1<e<ϕ(n).
• e and ϕ(n) are relatively prime (their greatest common divisor is 1).
• Here, we choose e=17. Why? Because it fits both rules.
Calculate Private Exponent d:
• d is the "secret key" that allows decryption. It satisfies:
(e×d) mod ϕ(n) =1
17×d=1(mod3120)
To find d, we use the Extended Euclidean Algorithm. The purpose of
this algorithm is to find the modular inverse of e with respect to ϕ(n).
gcd(a,b)=ax+by
• Where:
• a = e = 17
• b = ϕ(n) = 3120
• We want to find x (which will give us d) such that:
17x+3120y =gcd(17,3120) =1
Step 1: Apply the Euclidean Algorithm
•Start by dividing b (3120) by a (17) and find the remainder:
3120 ÷ 17=183 (quotient), 9 (remainder)
So, we have:
3120 = 17 x 183 + 9
Next, apply the algorithm to 17 and 9:
17 ÷ 9=1 (quotient), 8 (remainder)
So, we have:
17=9×1+8
Next, apply the algorithm to 9 and 8:
9 ÷ 8=1 (quotient), 1 (remainder)
So, we have:
9=8×1+1
•Finally, we reach a remainder of 1, so we stop here. The greatest
common divisor (gcd) of 17 and 3120 is 1, and we can now work
backward to find x and y.
Step 2: Work Backwards to Find x And y
Start from last equation:
1=9-1x8
Substitute 8 from previous step: ( 17 - 1 x 9)
1 = 9 – 1 x (17 – 1 x 9)
1 =9 – 17 + 1 x 9
1 = 2 x 9 – 17
Now substitute 9 from the equation before that:
1 = 2 x ( 3120 – 17 x 183) – 17
1 = 2x 3120 – 2 x 17 x 183 – 17
1 = 2 x 3120 – 366 x 17 – 17
1 = 2 x 3120 – 366 – 1 x 17
1= 2 x 3120 – 367 x 17
Step 3: Identify x and y
• From the equation:
1= 2 x 3120 – 367 x 17
• We can see that: x = -367, y = 2
• Since x = -367, we now know that d = -367.
• However, we need d to be a positive number, so we add ϕ(n) =
3120 to -367 to get the positive equivalent:
d = −367+3120 = 2753
d = 2753
• Keys:
• Public Key: (e, n) = (17, 3233).
• Private Key: (d, n) = (2753, 3233).
Step By Step Process for Calculating mod:
•Combine Powers to Compute 65^17 mod 3233 Using 65^ 17 = 65^16 . 65^1 mod
3233
65^17 mod 3233 = (2685⋅65) mod 3233
Compute 2685⋅65:
2685⋅65 = 174525 mod 3233 = 2790
Uses Of RSA:
RSA is widely used in:
• Sending secure emails.
• Online transactions (like credit card payments).
• Protecting data in apps and websites.
• Ensures secure communication between parties.
• Confirms the sender's identity and message integrity.
RSA in Everyday Use:
• SSL/TLS Protocols:
• These protocols are like protective layers for websites.
• When you visit a secure website (the ones with HTTPS), SSL/TLS ensures
that any data you send, like passwords or credit card details, is encrypted.
RSA is one of the tools used to set up this secure connection.
• Email Encryption:
• When you want to send a private email, tools like PGP (Pretty Good
Privacy) use RSA to make sure only the intended person can read your
message.
• Importance of RSA:
• RSA plays a vital role in protecting our online activities. Without it, secure
websites and private emails wouldn't be possible, leaving our sensitive
information exposed.
