Cryptography and RSA Algorithm

Cryptography and Secure Data Transmission

• Goal: To send data securely through an insecure channel.
• Method: Encryption to protect messages even if the channel is compromised.

Encryption and Decryption Process

1. Plaintext: The original message.
2. Encryption Key: A function used to encrypt the plaintext.
3. Ciphertext: The encrypted message.
   • Plaintext + Encryption Key --> Ciphertext
4. Insecure Channel: The communication channel where interception is possible.
5. Decryption Key: Used by the receiver to convert ciphertext back to plaintext.

Key Exchange Problem

• How do the sender and receiver share the encryption key securely?
• The receiver shares an encryption key with the sender.
• The sender uses this key to encrypt the message.
• The receiver uses their decryption key to decrypt the message.

Example: Sharing a Phone Number

• Two people from the same area know the area code (encryption).
• They only share the last four digits, and the receiver can reconstruct the full number.
• An outsider wouldn't be able to decipher the number without knowing the area code.

Diffie-Hellman Key Exchange Algorithm

• Objective: Two parties cooperate to obtain a shared secret.
• A third party observing the messages should not be able to deduce the secret.

Analogy: Mixing Paints

• Alice and Bob each have a pot of paint.
• Alice and Bob mix their paints, resulting in the same color.
• Eve, an eavesdropper, cannot deduce the final color.

Steps

1. Alice and Bob choose a private color (e.g., Alice: red, Bob: blue).
2. They publicly announce a common, different color (e.g., green).
3. They create a mixture of their private color and the public color.
   • Alice: Red + Green = Orange
   • Bob: Blue + Green = Sea Green
4. They share these mixtures.
   • Eve now has: Green, Orange, Sea Green
5. Alice takes Bob's mixture (Sea Green) and adds her private color (Red).
   • Bob takes Alice's mixture (Orange) and adds his private color (Blue).
   • Both Alice and Bob end up with the same color (Pinkish).

Explanation

• Alice has: Red, Green
• Bob has: Blue, Green
• They exchange mixtures:
  • Alice gets Blue + Green
  • Bob gets Red + Green
• Alice combines Red + (Blue + Green) = Red + Blue + Green
• Bob combines Blue + (Red + Green) = Red + Blue + Green

Why Eve Fails

• Mixing colors is easy, but separating them is hard.
• Eve cannot separate the original colors from the mixtures.
• Eve’s combinations will not result in the same color as Alice and Bob’s.

Mathematical Representation

• Alice and Bob exchange their public keys: $P<em>A$ and $P</em>B$.
• They compute their shared secret using a function $f$:
  • Alice computes $f(S<em>A, P</em>B)$.
  • Bob computes $f(S<em>B, P</em>A)$.
  • Where $S<em>A$ and $S</em>B$ are Alice's and Bob's secret (private) keys.

One-Way Functions

• A function where computation is easy in one direction but hard to reverse.
• Example: Mixing colors (easy), separating them (hard).

Hash Functions

• Similar to one-way functions.
• Easy to compute, hard to reverse.

RSA Algorithm

• Based on one-way functions.
• $f$ is a one-way function (OWF): easy to compute, hard to reverse.
  • Finding red and green from orange is impossible.

Multiplication of Two Prime Numbers

• A one-way function used in RSA.
• Multiplying two large prime numbers is easy, but factoring the product is hard.
• Mathematically proving why it is hard is difficult.

Modular Exponentiation

• a^b
  mod n is easy to compute.
• Reversing it is impossible (finding $b$ given a^b
  mod n and $a$).
• This is the function used in the RSA algorithm.

RSA Algorithm

• Developed by Ron Rivest, Adi Shamir, and Len Adelman.
• Public key encryption is widely used.

Assumptions

1. Based on the Diffie-Hellman key exchange model.
2. The encryption algorithm is known to everyone, including intruders.
3. The decryption key is known only to the receiver.
4. No secure channel exists.

Math Behind RSA

1. Encryption Key: Example: 3, 15 (Public Key)
2. Prime Numbers: Choose two prime numbers, $p$ and $q$.
   • Example: $p = 3$, $q = 5$
3. Calculate n: n = p

• q.
  • Example: n = 3
• 5 = 15

1. Message: Let the message be $m = 2$ (a very small number).
2. Encryption:
   • Formula: c = m^e
     mod n, where $e$ is the encryption exponent.
   • Example: c = 2^3
     mod 15 = 8
     mod 15 = 8.
   • The encrypted message (ciphertext) is 8.
3. Decryption Key: Example: 11, 15 (Private Key)
4. Decryption:
   • Formula: m = c^d
     mod n, where $d$ is the decryption exponent.
   • Example: m = 8^{11}
     mod 15 = 2.

Finding the Keys

1. Euler's Totient Function (phi(n)): Finds the number of coprimes of $n$ with $p$ and $q$.
   • Coprime: No common factors other than 1.
   • For $n = 15$, phi(15) = 8 (1, 2, 4, 7, 8, 11, 13, 14).
   • Easy way to find phi(n): $(p-1)(q-1)$.
     • Example: (3-1)(5-1) = 2

• 4 = 8.

1. Finding e (Encryption Exponent):
   • $e$ should be between 1 and phi(n).
   • $e$ should be coprime with phi(n).
   • Example: Possible values for $e$ are 3, 5, 7.
   • Choose $e = 3$.
2. Public Key: $(e, n) = (3, 15)$.
3. Finding d (Decryption Exponent):
   • $d$ should satisfy the condition: (e * d)
     mod phi(n) = 1.
   • Example: Find $d$ such that (3 * d) mod 8 = 1.
     • If $d = 11$, then (3 * 11)
       mod 8 = 33
       mod 8 = 1.

Summary of RSA

• Receiver (Bob) publicly announces the encryption key $(e, n)$.
• Sender (Alice) encrypts the message using this key and sends the ciphertext.
• Bob decrypts the message using his private key $d$.
• The lock (encryption function) is public, but the key (decryption key) is private.

Limitations of RSA

1. Computationally Expensive: Really hard to compute with really big numbers.
2. Vulnerable to Attack: If not using very big numbers, easily attacked.
3. Small Message Size: Cannot send a lot of big messages at once.
4. Private Key Leak: If the private key is leaked, all previous communications can be compromised.
5. Doesn't Change: Once the receiver puts out the encryption key, it doesn't get changed.