RSA Encryption Learning

How RSA Works

Step 3 of 9

Understand the detailed workings of RSA encryption and decryption processes.

RSA Algorithm Overview

RSA encryption involves several key steps, from key generation to encryption and decryption. Let's explore how the algorithm works in detail.

Key Insight: RSA's security is based on the mathematical difficulty of factoring large numbers into their prime components. This asymmetry makes it practical for one-way functions used in public key cryptography.

RSA Encryption Process Flow

Key Generation

Generate public and private key pairs

Encryption

Encrypt message with public key

Decryption

Decrypt message with private key

1
Choose two distinct prime numbers

Select two large prime numbers, p and q (typically 1024 bits or larger)

2
Compute n = p × q

Calculate the modulus n which is used in both public and private keys

3
Calculate φ(n) = (p-1)(q-1)

Compute Euler's totient function for n

4
Choose public exponent e

Select e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1

5
Determine private exponent d

Calculate d such that (d × e) mod φ(n) = 1

Key Mathematical Formulas

Key Generation

Choose two prime numbers p and q

n = p × q

φ(n) = (p - 1)(q - 1)

Choose e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1

d ≡ e-1 mod φ(n)

Public key: (n, e), Private key: (n, d)

Encryption

For a message m where 0 ≤ m < n

c = me mod n

Where c is the ciphertext

Decryption

For a ciphertext c

m = cd mod n

Where m is the original message

Why RSA Works

RSA works because of Euler's theorem which states that for any coprime integers a and n:

aφ(n) ≡ 1 (mod n)

Since ed ≡ 1 (mod φ(n)), we can write ed = kφ(n) + 1 for some integer k. This means:

cd ≡ (me)d ≡ med ≡ mkφ(n)+1 ≡ m · (mφ(n))k ≡ m · 1k ≡ m (mod n)

This mathematical property ensures that encryption followed by decryption yields the original message.

Encryption and Decryption Process

Original Message

M

Apply Public Key

Me mod n

Ciphertext

C

Apply Private Key

Cd mod n

Decrypted Message

M

Encryption/Decryption Simulator

Key Generation
143
120
103
Encryption/Decryption
48
9

Test Your Understanding

1. Which of the following is NOT part of the RSA key generation process?

2. In RSA, which mathematical operation is used for encryption?

3. What is the relationship between the public exponent e and private exponent d in RSA?

Back