RSA part 1

RSA Algorithm in Cryptography (Easy Explanation)

The RSA Algorithm is a type of public-key cryptography. This means it uses two different keys:

• A Public Key – anyone can know and use this.

• A Private Key – only the receiver should have this, and it must be kept secret.

The Public Key is used to lock (encrypt) the message, and the Private Key is used to unlock (decrypt) it.

The name RSA comes from the names of the three people who created it: Ron Rivest, Adi Shamir, and Leonard Adleman, in 1977.

Simple Example:

If Person A wants to send a secret message to Person B:

• Person A uses Person B’s Public Key to encrypt the message.

• Person B uses their Private Key to decrypt and read the message.

Here’s how the keys are made:

• Step 1: Pick two large prime numbers (these are special numbers that only divide by 1 and themselves), call them p and q. Keep these secret.

• Step 2: Multiply them:
  n = p × q
  This number n is used in both the public and private keys.

• Step 3: Find the Euler’s function:
  Φ(n) = (p - 1) × (q - 1)
  This helps in key calculations.

• Step 4: Pick a number e, which is:

  • Greater than 1 and smaller than Φ(n)

  • And has no common factors with Φ(n) (they are co-prime)

• Step 5: Find another number d so that:

  • (d × e) % Φ(n) = 1
    This means d can undo what e does.

Now you have:

• Public Key = (n, e) → Anyone can use this to encrypt data.

• Private Key = (n, d) → Only you can use this to decrypt it.

2. Encryption (Hiding the Message)

• First, change the message (M) into numbers using something like ASCII (a way to turn letters into numbers).

• Then, use the Public Key (n, e) to lock the message using this formula:

  C = Mᵉ mod n

• C is the cipher text (the hidden or coded message).

---

3. Decryption (Unlocking the Message)

• To read the original message from the cipher text C, use the Private Key (n, d) with this formula:

  M = Cᵈ mod n

• This gives you back the original message M.

  
  

Idea Behind RSA Algorithm (Simple Explanation)

The main idea behind RSA is that it’s very hard to break a big number into its prime factors.

In RSA:

• The Public Key is (n, e) – everyone knows this.

• The Private Key is (n, d) – only the receiver knows this.

You might wonder:
Can someone find out d using n and e?

Well, here’s the catch:

• To find d, you need to know Φ(n).

• And to find Φ(n), you need the secret prime numbers p and q, because:
  Φ(n) = (p - 1) × (q - 1)

Even though n = p × q is public, RSA makes p and q very large, so it’s extremely hard (almost impossible with normal computers) to figure them out. This is what makes RSA safe.

---

Why RSA is Strong

• If someone could figure out p and q, they could break RSA by finding d and reading the message.

• But because the numbers are so big (RSA keys are usually 1024 or 2048 bits long), finding p and q takes a very, very long time, even for powerful computers.

So, the strength of RSA depends on keeping p and q secret and very large.