Foundations of Security Week5 Lecture

Lecture Outline#

Review of RSA cryptographic algorithm
Public key and Private key generation in RSA
RSA encryption and decryption process
Introduction to Chosen Ciphertext Attack (CCA) on RSA
Understanding how attackers exploit decryption systems

Learning Outcomes#

By the end of this lecture, students should be able to:

Explain the RSA key generation process
Identify the steps for generating public and private keys
Apply the Extended Euclidean Algorithm to compute the private key
Perform RSA encryption and decryption
Explain the concept of chosen ciphertext attacks on RSA

Key Generation#

1. Select Primes	2. Compute $n$	3. Calculate $\phi(n)$	4. Choose $e$	5. Compute $d$
Choose two large prime numbers $p$ and $q$ . These must be kept secret.	Calculate the modulus $n$ by multiplying p and q. This is part of both keys.	Compute Euler’s totient function using the formula $(p-1) \times (q-1)$ .	Select public exponent $e$ where $1 < e < \phi(n)$ and $\gcd(e, \phi(n)) = 1$ .	Calculate private exponent $d$ as the modular multiplicative inverse of $e$ .
$p, q = primes$	$n = p \times q$	$\phi(n) = (p-1)(q-1)$	$1 < e < \phi(n)$ $\gcd(e, \phi(n)) = 1$	$(d × e) \equiv 1 \bmod \phi(n)$

Public Key	Private Key
$(n,~ e)$ Share freely with anyone	$(n,~ d)$ Keep secret at all times

Public Key Generation#

Public Keys of Alice#

🤵🏼‍♀️

Alice

Sender

💬 Wants to send a message

Alice needs to encrypt her message
so only Bob can read it.

🔑 Needs a key pair

She must generate public and
private keys for encryption.

📤 Shares public key

Her public key can be shared with
anyone, including Bob.

↔️

Secure Channel

End-to-end encryption

🤵🏻

Bob

Receiver

📩 Wants to receive message

Bob needs to decrypt Alice's message
securely.

🔑 Needs a key pair

He must also generate public and
private keys.

🔒 Keeps private key secret

His private key must never be shared
with anyone.

Public Keys of Alice & Bob#

Both parties generate their public keys simultaneously

👩

Alice

1 Select Prime Numbers

P_A = 61,
Q_A = 53

2 Calculate modulus n

n_A = P_A × Q_A
= 61 × 53 = 3233

3 Choose Public Exponent e

e_A must satisfy:
✓ 1 < e_A < φ(n_A)
✓ gcd(e_A, φ(n_A)) = 1
e_A = 17

Calculate Euler's Totient Function

φ(n_A) = (P_A - 1) × (Q_A - 1)
= (61 - 1) × (53 - 1) = 60 × 52 = 3120

🔑 Alice's Public Key

            (nA = 3233, eA = 17)
          

⇄

👨

Bob

1 Select Prime Numbers

P_B = 3,
Q_B = 11

2 Calculate modulus n

n_B = P_B × Q_B
= 3 × 11 = 33

3 Choose Public Exponent e

e_B must satisfy:
✓ 1 < e_B < φ(n_B)
✓ gcd(e_B, φ(n_B)) = 1
e_B = 7

Calculate Euler's Totient Function

φ(n_B) = (P_B - 1) × (Q_B - 1)
= (3 - 1) × (11 - 1) = 2 × 10 = 20

🔑 Bob's Public Key

            (nB = 33, eB = 7)
          

Public Keys of Alice#

Mathematical constraints for selecting the public exponent e

Range Constraint

e must be:

1 < e < φ(n)

✓ Greater than 1

✓ Less than φ(n) (Euler's totient)

Why: Ensures e is in the valid multiplicative group

Co-prime Condition

e must be co-prime with φ(n):

gcd(e, φ(n)) = 1

✓ No common factors with φ(n)

✓ Ensures multiplicative inverse exists

Why: Required for the decryption key to exist

Modular Inverse

e × d ≡ 1 (mod φ(n))

Must have a multiplicative inverse d

✓ d is the private key

✓ Found using Extended Euclidean Algorithm

Why: Enables encryption/decryption symmetry

Alice's φ(n)

φ(3233) = 3120

Bob's φ(n)

φ(33) = 20

💡

Formula: φ(n) = (p-1) × (q-1)

Private Key of Alice#

👩

Alice

Private Key Calculation

Public Values

n_A = 3233
e_A = 17

Prime Factors

P_A = 61
Q_A = 53

Calculate Euler's Totient Function

φ(n_A) = (P_A - 1) × (Q_A - 1)
= (61 - 1) × (53 - 1) = 60 × 52 = 3120

Private Key

d_A = 2753

Step-by-Step Calculation

Set Up the Congruence Equation

Find d_A such that:
e_A × d_A ≡ 1 (mod φ(n_A))
17 × d_A ≡ 1 (mod 3120)

Apply Extended Euclidean Algorithm

3120 = 17(183) + 9
17 = 9(1) + 8
9 = 8(1) + 1
8 = 1(8) + 0

Working backwards to find the inverse...

1 = 9 + 8(-1)
1 = 9 + [17 + 9(-1) ] (-1)
1 = 9 + 17 (-1) + 9(1)
1 = 17 (-1) + 9(2)
1 = 17 (-1) + [3120 + 17(-183)](2)

1 = 17 (-1) + [3120(2) + 17(-366)]
1 = 17 (-1) + 3120(2) + 17(-366)
1 = 17 (-367) + 3120(2)

3120 + (-367) = 2753

Solution: Private Key

d_A = 2753

Verification: 17 (2753) = 46801 mod 3120 = 3120(15) + 1 mod 3120 ✓

🔒

Alice's Private Key: dₐ = 2753 (Keep Secret!)

🔑 Used for decrypting messages

Private Key of Bob#

👨

Bob

Private Key Calculation

Public Values

n_B = 33
e_B = 7

Prime Factors

P_B = 3
Q_B = 11

Calculate Euler's Totient Function

φ(n_B) = (P_B - 1) × (Q_B - 1)
= (3 - 1) × (11 - 1) = 2 × 10 = 20

Private Key

d_B = 3

Step-by-Step Calculation

Set Up the Congruence Equation

Find d_B such that:
e_B × d_B ≡ 1 (mod φ(n_B))
7 × d_B ≡ 1 (mod 20)

Apply Extended Euclidean Algorithm

20 = 7(2) + 6
7 = 6(1) + 1
6 = 1(6) + 0

Working backwards to find the inverse...

1 = 7 + 6(-1)
1 = 7 + [20 + 7(-2) ] (-1)
1 = 7 + [20(-1) + 7(2)]
1 = 7(3) + 20(-1)

Solution: Private Key

d_B = 3

Verification: 7 (3) = 21 mod 20 = 1 mod 20 ✓

🔒

Bob's Private Key: d_B = 3 (Keep Secret!)

🔑 Used for decrypting messages

Key Pairs Summary#

👩

Alice

🔓 Public Key SHARE

Modulus n 3233

Exponent e 17

🔒 Private Key SECRET

Exponent d 2753

Prime Factors (Secret)

👨

Bob

🔓 Public Key SHARE

Modulus n 33

Exponent e 7

🔒 Private Key SECRET

Exponent d 3

Prime Factors (Secret)

RSA Encryption & Decryption#

With their key pairs generated, Alice and Bob can now securely exchange encrypted messages. The foundation of RSA encryption is established.

👩

👨

✈️

Alice Encrypts

Using Bob's public key

↔️

Secure Transfer

Encrypted message sent

🔒

Bob Decrypts

Using his private key

Encryption & Decryption#

Encryption and Decryption Process#

🔒

Encryption

The sender uses the recipient's public key (n, e) to encrypt
the plaintext message M into ciphertext C.

Formula:

C = M^e mod n

Ciphertext (encrypted message)

Plaintext message (as number)

Public exponent

Modulus (part of public key)

🔓

Decryption

The recipient uses their private key (n, d) to decrypt the
ciphertext C back into the original plaintext message M.

Formula:

M = C^d mod n

Recovered plaintext message

Ciphertext (encrypted message)

Private exponent (secret)

Modulus (same as public key)

Security Guarantee

Only the holder of the private key d can decrypt the message. Even if an attacker knows the public key (n, e) and intercepts the ciphertext C, they cannot compute d without factoring n into p and q — a computationally infeasible task for large keys.

Encryption and Decryption Process#

👤Alice's Keys

Public Key:

n_A = 3233, e_A = 17

Private Key:

d_A = 2753

👤Bob's Keys

Public Key:

n_B = 33, e_B = 7

Private Key:

d_B = 3

✉️Message to Send

M = 2

🔒Step 1: Encryption (Alice)

Alice uses Bob's public key to encrypt the message:

C = M^e_B mod n_B
C = 2⁷ mod 33
= 128 mod 33
= 29 mod 33

Ciphertext
C = 29

🔓Step 2: Decryption (Bob)

Bob uses his private key to decrypt:

M = C^d_B mod n_B
M = 29³ mod 33
= 24389 mod 33
= 2 mod 33

Recovered Message
M = 2

Quiz#

👤Alice's Keys

Public Key:

n_A = 3233, e_A = 17

Private Key:

d_A = 2753

👤Bob's Keys

Public Key:

n_B = 33, e_B = 7

Private Key:

d_B = 3

✉️Message to Send

M = 5

🔒Step 1: Encryption (Alice)

Alice uses Bob's public key to encrypt the message:

C = M^e_B mod n_B
C = 5⁷ mod 33
= 78125 mod 33
= 14 mod 33

Ciphertext
C = 14

🔓Step 2: Decryption (Bob)

Bob uses his private key to decrypt:

M = C^d_B mod n_B
M = 14³ mod 33
= 2744 mod 33
= 5 mod 33

Recovered Message
M = 5

Chosen Ciphertext Attacks (CCA) on RSA Algorithm#

The Chosen Ciphertext Attack (CCA) on the RSA algorithm is a type of cryptographic attack where the attacker uses the decryption capabilities of a system/users to decrypt messages by choosing a series of ciphertexts and using the results to deduce the plaintext or the encryption key.

Chosen Ciphertext Attack on RSA#

Normal RSA Communication Flow

👩

Alice

Sender

Has Bob's Public Key:

(e_B, n_B)

Message M

→

Encryption
C = M^e_B mod n_B

→

Ciphertext C

☁️ Public Channel (Encrypted)

👨

Bob

Receiver

Has Private Key:

(d_B, n_B)

Encryption

Alice uses Bob's public key to encrypt
message M:

C = 2⁷ mod 33 = 29

Transmission

Ciphertext C travels through the public channel.
Even if intercepted, it's unreadable without the
private key.

Decryption

Bob uses his private key to decrypt:

M = 29³ mod 33 = 2

Public Keys of Alice#

👩

Alice

Sender

Key Generation

P_A = 61, Q_A = 53
n_A = 3233
φ(n_A) = 3120
e_A = 17
d_A = 2753

Has Access To

🔑 Own keys

🌍 Bob's public key

Message to Send

M = 2

👤

Attacker

Adversary

Capabilities

👁️ Intercepts all traffic

📝 Modifies messages

🔑 Knows public keys

Attack Parameters

Chooses: r = 2

(coprime to n_B = 33)

Goal

Recover M without d_B

👨

Bob

Receiver

Key Generation

P_B = 3, Q_B = 11
n_B = 33
φ(n_B) = 20
e_B = 7
d_B = 3

Has Access To

🔑 Own private key

🔓 Alice's public key

Receives

C' = 16

(not the original C)

Attack Setup

Alice wants to send message M=2 to Bob. The attacker intercepts the communication and substitutes ciphertext C with manipulated C’

Chosen Ciphertext Attack on RSA#

Attacker

Intercepts C
Alice's Public
(n_A, e_A)
Bob's Public
(n_B, e_B)

🔒 Step 2: Attacker computes fake message C'

Chooses random: r = 2 (coprime with n_B(33) so it has an inverse)
Compute: C' = (C × r^e_B mod n_B)
= 29 × 2⁷ mod 33
= 16 mod 33
Sends C' to Bob to decrypt:

C' = 16

🔒 Step 4: Attacker computes inverse to retrieve original message

Attacker knows: ResM' = 4 = C'^d_Bmod n_B
= (C×r^e_B)^d_Bmod n_B
Deduce: M' = (M^e_B×r^e_B)^d_Bmod n_B
= (M^e_B×d_Bmod n_B)×(r^e_B×d_Bmod n_B) = M¹×r¹

Compute inverse of r to get M: M¹ × r¹ (r^-1)

Inverse: 2 (r^-1) ≡ 1 mod n_B
= r^-1 = 17

Retrieve M: Res × 17 mod n_B
        = 4 × 17 mod 33
        = 68 mod 33
        = 2

Alice Encrypts

Alice encrypts M=2 using Bob's public key (eB=7, nB=33):

C = M^e_B mod n_B
C = 2⁷ mod 33 = 29

Attacker Intercepts

Attacker captures C=29 and chooses r=2 (coprime to 33):

C' = (C × r^e_B) mod n_B
C' = (29 × 2⁷) mod 33
C' = (29 × 128) mod 33 = 16

Attacker Sends C'

Attacker forwards C' = 16 to Bob instead of the original C = 29

Bob Decrypts C'

Bob decrypts using his private key (dB=3, nB=33):

Res = C'^d_B mod n_B
Res = 16³ mod 33 = 4

Bob Sends Result

Bob sends Res=4 back (thinking it's related to the original message):

Res = 4

Attacker Recovers M

Attacker computes r^-1 mod 33 = 17 using Extended Euclidean Algorithm:

M = Res × r^-1 mod n_B
M = 4 × 17 mod 33
M = 2 ✓

Original Message

M = 2

→

Attacker Recovered

M = 2

✓

Attack Successful!

Assignment#

Assignment: Complete this exercise and submit during seminar class

Alice’s Public key: $\textcolor{red}{𝑛_𝐴 = 3233}$ and $\textcolor{red}{𝑒_𝐴=17}$ Alice’s Private key: $\textcolor{blue}{𝑑_𝐴} = 2753$	Bob’s Public key: $\textcolor{red}{𝑛_B = 33}$ and $\textcolor{red}{𝑒_B = 7}$ Bob’s Private key: $\textcolor{blue}{𝑑_B} = 3$

Task:
If Alice wants to send the message $\textcolor{blue}{𝑀 = 5}$ to Bob, perform the chosen ciphertext attack and retrieve the original message if the attacker chooses random number $\textcolor{blue}{r = 2}$ . Show the following:
Modified Ciphertext (C′): _____________
Bob’s Response: _____________
Attacker’s Recover Process: _____________

Show how you computed your answers.
Only handwritten solutions.
No copy-paste will be accepted.

Security Strength & Key Sizes#

📏 NIST Recommendations for RSA Key Sizes

2048-bit RSA

Security: ~112 bits | Status: Acceptable until 2030

Current Standard

3072-bit RSA

Security: ~128 bits | Status: For beyond 2030

Recommended

4096-bit RSA

Security: Higher | Use: Long-term protection, root CAs

Maximum Security

🛡️ Security Foundation

RSA's security relies on the computational difficulty of factoring
large numbers

Easy: Multiply two 1024-bit primes

Hard: Factor the 2048-bit product

Time: Billions of years with classical computers

⚛ Quantum Computing Threat

RSA is vulnerable to Shor's algorithm, which can factor large numbers
efficiently on a quantum computer. Current estimates:

⚠️ Key Security Principles

✓

Keep private keys absolutely secret

✓

Use minimum 2048-bit keys

✓

Rotate keys periodically

✓

Use secure padding schemes (OAEP)

Applications#

🌐

HTTPS/SSL/TLS

RSA is used in X.509 certificates to secure web
browsing. When you see the padlock icon, RSA
is likely protecting your connection.

Usage: 90%+ of websites

ᝰ.

Digital Signatures

RSA provides authentication and
non-repudiation. Signers cannot deny their
signatures, and recipients can verify authenticity.

Usage: Code signing, document signing

✉️

Email Encryption

Protocols like S/MIME and PGP use RSA to
encrypt emails, ensuring only intended
recipients can read them.

Usage: Secure corporate email

🔄

Secure File Transfer

SFTP, FTPS, and VPNs use RSA for key
exchange and authentication, protecting data
in transit.

Usage: Enterprise file sharing

</>

Software Signing

Developers digitally sign software to prove
authenticity and integrity. Users can verify
software hasn't been tampered with.

Usage: OS updates, app stores

💡

Hybrid Approach

RSA is computationally intensive.
In practice, RSA encrypts symmetric keys
(like AES), which then encrypt large data
efficiently.

Benefit: Best of both worlds

INFO

This week dose have seminar class, which theme is phishing, but teacher didn’t provide seminar material, so no separate seminar article this week.

音乐

音乐

Lecture Outline#

Learning Outcomes#

Key Generation#

Public Key Generation#

Public Keys of Alice#

Public Keys of Alice & Bob#

Public Keys of Alice#

Private Key of Alice#

Private Key of Bob#

Key Pairs Summary#

RSA Encryption & Decryption#

Encryption & Decryption#

Encryption and Decryption Process#

Encryption and Decryption Process#

Quiz#

Chosen Ciphertext Attacks (CCA) on RSA Algorithm#

Chosen Ciphertext Attack on RSA#

Public Keys of Alice#

Chosen Ciphertext Attack on RSA#

Assignment#

Security Strength & Key Sizes#

Applications#

支持与分享

评论区

音乐

目录