Discrete Structures - I

01:198:205
Fall 2025, Rutgers

Instructor: Surya Teja Gavva

Modular Arithmetic

⊚ Remainders: a ≡ b (mod m) means m divides (a − b) — same

remainder on division by m.
⊚ Operations
a + b ≡ a′ + b ′ (mod m)
a − b ≡ a′ − b ′ (mod m)
ab ≡ a′ b ′ (mod m)
ak ≡ (a′ )k (mod m)

⊚ Division: valid only if gcd(a, m) = 1 (then a has an inverse mod m).

⊚ Finding Inverses: Use the Euclidean Algorithm and Bézout’s Identity:

sa + tm = 1 ⇒ a−1 ≡ s (mod m).

In short: Modular arithmetic behaves like normal

arithmetic—except division only works when the divisor is coprime
to the modulus.
1
Fermat’s Little Theorem

Statement
If p is prime and p ∤ a, then:

ap−1 ≡ 1 (mod p).

Simple Checks

24 ≡ 1 (mod 5) (p = 5).
36 ≡ 1 (mod 7) (p = 7).
510 ≡ 1 (mod 11) (p = 11).

Idea: Multiplying all nonzero residues mod p by a just permutes

them.
2
Using Fermat’s Little Theorem for Fast Remainders

Example 1: 523 mod 7

Since 7 is prime, ϕ(7) = 6 and 56 ≡ 1 (mod 7). Reduce the

exponent: 23 mod 6 = 5.

523 ≡ 55 = 3125 ≡ 3 (mod 7).

Example 2: 350 mod 11

ϕ(11) = 10, so 310 ≡ 1 (mod 11). Reduce the exponent:

50 mod 10 = 0.

350 = (310 )5 ≡ 15 ≡ 1 (mod 11).

Idea: Replace large exponents by their remainder mod ϕ(p) for

3
quick computation.
Euler’s Theorem (General Case)

Statement
If gcd(a, n) = 1, then:

aϕ(n) ≡ 1 (mod n)

where ϕ(n) is the number of integers 1 ≤ k ≤ n with gcd

(k, n) = 1

Why it Generalizes Fermat

For prime p, ϕ(p) = p − 1, so Euler’s Theorem ⇒ Fermat’s

Theorem.

4
Computing Euler’s ϕ(n)

⊚ ϕ(p) = p − 1 if p is prime.
⊚ ϕ(p k ) = p k − p k−1 = p k (1 − p1 ).
⊚ If gcd(m, n) = 1, then ϕ(mn) = ϕ(m)ϕ(n).

Examples

ϕ(60) = ϕ(22 )ϕ(3)ϕ(5) = 2 · 2 · 4 = 16.

ϕ(84) = ϕ(22 )ϕ(3)ϕ(7) = 2 · 2 · 6 = 24.
ϕ(100) = 100(1 − 12 )(1 − 15 ) = 40.

5
More Examples

Prime Powers

ϕ(25 ) = 25 − 24 = 16.
ϕ(53 ) = 125 − 25 = 100.

Composite Numbers

ϕ(45) = ϕ(9)ϕ(5) = 6 · 4 = 24.

ϕ(72) = ϕ(8)ϕ(9) = 4 · 6 = 24.

6
Using Euler’s Totient Theorem for Fast Remainders

Example 1: 7222 mod 40

Since gcd(7, 40) = 1, we can use Euler’s theorem: ϕ(40) = 16 ⇒ 716 ≡ 1

(mod 40). Reduce the exponent: 222 mod 16 = 14.

7222 ≡ 714 = (72 )7 ≡ 497 ≡ 97 (mod 40).

Now, 92 ≡ 1 (mod 40) ⇒ 97 ≡ 9.

7222 ≡ 9 (mod 40) .

Example 2: 13202 mod 100

Here gcd(13, 100) = 1, and ϕ(100) = 40. So 1340 ≡ 1 (mod 100). Reduce
exponent: 202 mod 40 = 2.

13202 ≡ 132 ≡ 169 ≡ 69 (mod 100) .

7
Euler’s Theorem (Proof Sketch)

Let R = {r1 , r2 , . . . , rϕ(n) } be the numbers < n coprime to n. Since

gcd(a, n) = 1, the set

aR = {ar1 , ar2 , . . . , arϕ(n) }

is just a permutation of R modulo n.

Multiply all terms:

r1 r2 · · · rϕ(n) ≡ aϕ(n) r1 r2 · · · rϕ(n) (mod n).

Cancel the invertible product:

aϕ(n) ≡ 1 (mod n).

(When n = p prime, this gives Fermat’s Little Theorem.)

8
Fermat Primality Test

Algorithm

For integer n > 2:

1. Pick random a such that gcd(a, n) = 1.
2. Compute an−1 mod n.
3. If an−1 ̸≡ 1 (mod n), n is composite.
4. If an−1 ≡ 1 (mod n), n may be prime.

Reasoning (Fermat’s Little Theorem)

For a prime p: ap−1 ≡ 1 (mod p) for all a coprime to p. ⇒

So if the congruence fails, n definitely not prime.

9
Examples & Caveats

Quick Checks

a = 2, n = 7: 26 = 64 ≡ 1 (mod 7) → passes → 7 is prime.

a = 2, n = 9: 28 = 256 ≡ 4 (mod 9) → fails → 9 is compos-
ite.

Caution: Pseudoprimes Exist!

Some composites still satisfy an−1 ≡ 1 (mod n) for many a.

These are called Carmichael numbers.

Example

561 = 3 · 11 · 17 is composite, yet a560 ≡ 1 (mod 561) for all

a coprime to 561.
10
Modular Arithmetic

The ”remainder” world.

⊚ Euclidean Algorithm to find inverses:

ax ≡ 1 mod n ⇐⇒ ax − ny = 1
⊚ Fermat’s Little Theorem: ap−1 ≡ 1 mod p, a ̸= 0 mod p
⊚ Euler’s Theorem: aϕ(n) ≡ 1 mod n, (a, n) = 1

Modulo p Modulo n
Every a ̸= 0 mod p invertible Coprime a invertible- (a, n) = 1
ap−1 ≡ 1 mod p, a ̸= 0 mod p aϕ(n) ≡ 1 mod n, (a, n) = 1
mod p world is nicer– can do arithmetic similar to all numbers. For arbitrary n, we
need to restrict to (a, n) = 1 which is not good. But mod n problems can be reduced
to modp k problems by Chinese Remainder Theorem.

11
The Chinese Remainder Theorem

Motivating Problem

Find an integer x that satisfies:

x ≡2 (mod 3), x ≡3 (mod 5), x ≡2 (mod 7).

⊚ The moduli 3, 5, 7 are small and pairwise coprime.

⊚ Brute-force works for small numbers, but what if the moduli
are large?
⊚ We need a systematic method — that’s what the Chinese
Remainder Theorem (CRT) provides.

Goal: Combine several modular equations into a single one

modulo their product.
12
Chinese Remainder Theorem (CRT)

Theorem (Existence and Uniqueness)

Let m1 , m2 , . . . , mk be pairwise coprime integers. The system

x ≡ ai (mod mi ), (i = 1, 2, . . . , k)

has a unique solution modulo M = m1 m2 · · · mk .

Simple Case

x ≡ 2 (mod 3), x ≡ 3 (mod 5) Check multiples of 3 that

give remainder 2: 2, 5, 8, 11, 14, . . . 8 ≡ 3 (mod 5) ⇒ works!
x ≡ 8 (mod 15) .

CRT guarantees: Such a solution always exists and is unique

modulo M. 13
CRT Intuition: Parallel Clocks

Think: Two clocks ticking at different rates.

⊚ One resets every 3 hours, another every 5 hours.

⊚ Both realign every 3 × 5 = 15 hours.

CRT = finding the “time” when both clocks show the desired
readings.

Quick Check

x ≡ 1 (mod 3), x ≡ 2 (mod 5)

⇒ try x = 1, 4, 7, 10, 13, 16, . . .
7 ≡ 2 (mod 5) ⇒ works! Solution: x ≡ 7 (mod 15).

14
Constructive CRT: Building the Solution

Two Coprime Moduli m1 and m2

M M
M = m1 m2 , M1 = , M2 = .
m1 m2
Find inverses:

y1 ≡ M1−1 (mod m1 ), y2 ≡ M2−1 (mod m2 ).

Then the unique solution modulo M is

x ≡ a1 M1 y1 + a2 M2 y2 (mod M).

This formula generalizes to any number of congruences.

15
Worked Example: Two Moduli System

Solve
x ≡ 2 (mod 3), x ≡ 3 (mod 5).

M = 15, M1 = 5, M2 = 3.
Find inverses: 5−1 ≡ 2 (mod 3), 3−1 ≡ 2 (mod 5).
Substitute:

x ≡ 2(5)(2) + 3(3)(2) = 20 + 18 = 38 ≡ 8 mod 15 .

Solution: x ≡ 8 (mod 15).

16
Worked Example: Three Moduli System

Solve
x ≡ 1 (mod 3), x ≡ 2 (mod 5), x ≡ 3 (mod 7).

M = 105, M1 = 35, M2 = 21, M3 = 15.

Compute inverses:

35−1 ≡ 2 (mod 3), 21−1 ≡ 1 (mod 5), 15−1 ≡ 1 (mod 7).

Substitute:

x ≡ 1(35)(2)+2(21)(1)+3(15)(1) = 70+42+45 = 157 ≡ 52 mod 105 .

Solution: x ≡ 52 (mod 105).

17
Representing Large Integers

Idea
For pairwise coprime moduli m1 , m2 , . . . , mn , any integer a
with 0 ≤ a < M = m1 m2 · · · mn can be uniquely represented
by its remainders:

a ←→ (a mod m1 , a mod m2 , . . . , a mod mn ).

Why: Each modulus gives a “local view.” Together, these small

remainders fully encode a (via CRT).

18
Example: Breaking a Large Number

Moduli: (99, 98, 97, 95) — all pairwise coprime.

Compute Remainders for a = 123,684

(a mod 99, a mod 98, a mod 97, a mod 95) = (33, 8, 9, 89).

Similarly for b = 413,456

(32, 92, 42, 16).

Observation: Each number ⇒ a small tuple!

19
Arithmetic in Remainder Form

Addition mod each component:

(33, 8, 9, 89) + (32, 92, 42, 16) = (65, 100, 51, 105).

Reduce each component:

(65, 2, 51, 10).

Result: 123,684 + 413,456 represented as (65, 2, 51, 10).

Key Benefit

CRT lets us do arithmetic on small moduli instead of huge

integers — perfect for computers!

20
Application: Modular Hashing

Hash functions map large data sets to smaller table indices.

Simple Hash Function

h(k) = k mod m

Example

⊚ h(064212848) = 64212848 mod 111 = 14

⊚ h(037149212) = 37149212 mod 111 = 65

Note: Collisions occur when different keys produce the same index.

21
Application: Random Number Generation

Computers are deterministic — they simulate randomness using

modular arithmetic.

Linear Congruential Generator (LCG)

Xn+1 = (aXn + c) mod m

Example

a = 5, c = 3, m = 16, X0 = 7.

Sequence: 7, 6, 1, 8, 11, 10, . . .

22
Cryptographically Secure: Blum–Micali

Blum–Micali Generator
Based on the difficulty of discrete logarithms.

1, x < p−1
i 2
xi+1 = g xi mod p, output
0, otherwise

Idea
Each step produces one random bit. Security comes from the
hardness of reversing g xi mod p.

23
Application: Error Detection

Adding small redundancy allows detection (and sometimes

correction) of errors.

Parity Bit (mod 2)

For bits x1 x2 . . . xn , append xn+1 such that:

xn+1 ≡ x1 + x2 + · · · + xn (mod 2)

If this congruence fails on receipt → error detected.

24
Example: Error Detection
Example: Encoding and Detecting

⊚ Sender:
◦ Original data: 1011
◦ Sum = 1 + 0 + 1 + 1 = 3 ≡ 1 (mod 2).
◦ To make the total sum ≡ 0 (mod 2), the parity bit must
be 1.
◦ Transmits codeword: 10111 (Total sum is 4 ≡ 0
(mod 2). Check passes.)
⊚ Receiver:
◦ Received codeword: 10101 (a 1-bit error occurred)
◦ Receiver computes the check: 1 + 0 + 1 + 0 + 1 = 3 ≡ 1
(mod 2).
◦ This does not equal 0. =⇒ Parity check fails. Error
detected!

Parity can only detect an odd number of bit flips (1, 3, 5, ...). If two bits flip (10111
→ 10001), the sum is 2 ≡ 0 (mod 2).The check passes, and the error is not detected. 25
Application: The ISBN-10 Check Digit System

ISBN-10 Verification Rule

A 10-digit number is a valid ISBN if its weighted sum is congruent to zero modulo
11:
10
!
X
i · xi ≡ 0 (mod 11)
i=1

⊚ If the 10th digit needs to be the value ’10’ to satisfy the rule, the
character ’X’ is used.

Verifying a Valid ISBN: 0-306-40615-2

Let’s check the digits x1 , . . . , x10 = (0, 3, 0, 6, 4, 0, 6, 1, 5, 2). Sum = 0 + 6 + 0 +

24 + 20 + 0 + 42 + 8 + 45 + 20= 165
Since 165 = 15 × 11 ≡ 0 mod 11, the answer is yes. The ISBN is valid.

26
Cryptography: The Basic Question

The Goal
Allow Alice to send a message to Bob so that Eve cannot
understand it, even if she intercepts it.

27
Warm-up: The Caesar Cipher

Map letters to mod 26 (A=0, B=1, ..., Z=25). Key: shift k.

⊚ Encryption: E (p) = (p + k) mod 26

⊚ Decryption: D(c) = (c − k) mod 26

Plaintext Z E B R A

28
Warm-up: The Caesar Cipher

Map letters to mod 26 (A=0, B=1, ..., Z=25). Key: shift k.

⊚ Encryption: E (p) = (p + k) mod 26

⊚ Decryption: D(c) = (c − k) mod 26

Plaintext Z E B R A

Numeric (p) 25 4 1 17 0

28
Warm-up: The Caesar Cipher

Map letters to mod 26 (A=0, B=1, ..., Z=25). Key: shift k.

⊚ Encryption: E (p) = (p + k) mod 26

⊚ Decryption: D(c) = (c − k) mod 26

Plaintext Z E B R A

Numeric (p) 25 4 1 17 0

Shift (p + 3) 28 7 4 20 3

28
Warm-up: The Caesar Cipher

Map letters to mod 26 (A=0, B=1, ..., Z=25). Key: shift k.

⊚ Encryption: E (p) = (p + k) mod 26

⊚ Decryption: D(c) = (c − k) mod 26

Plaintext Z E B R A

Numeric (p) 25 4 1 17 0

Shift (p + 3) 28 7 4 20 3

Result (mod 26) 2 7 4 20 3

28
Warm-up: The Caesar Cipher

Map letters to mod 26 (A=0, B=1, ..., Z=25). Key: shift k.

⊚ Encryption: E (p) = (p + k) mod 26

⊚ Decryption: D(c) = (c − k) mod 26

Plaintext Z E B R A

Numeric (p) 25 4 1 17 0

Shift (p + 3) 28 7 4 20 3

Result (mod 26) 2 7 4 20 3

Ciphertext C H E U D

28
Shift Cipher Example (k = 11)

Encryption: : E11 (p) = (p + 11) mod 26

Decryption: D11 (c) = (c − 11) mod 26.

Encrypting ”STOP GLOBAL WARMING”

Plaintext: STOP GLOBAL WARMING
Numeric (p): 18 19 14 15 6 11 14 1 0 11 22 0 17 12 8 13 6
Shift (p + 11): 3 4 25 0 17 22 25 12 11 22 7 11 2 23 19 24 17
Ciphertext: DEZA RWZMLW HLCXTYR

[Link]

29
Shift Cipher Example: Decryption (k = 7)

Decrypt the message using Dk (c) = (c − 7) mod 26.

Ciphertext: THAOLTHAJPZ PZ ILYBBAFSLC
Numeric (c): 19 7 0 14 11 19 7 0 9 15 25 15 25 8 11 24 1 1 0 5 18 11 2
Plain (c − 7): 12 0 19 7 4 12 0 19 2 8 18 8 18 1 4 17 20 20 19 24 11 4 17 21
Plaintext: MATHEMATICS IS BEAUTIFUL

30
Classical Ciphers Break: Frequency Analysis

Idea
Monoalphabetic ciphers preserve letter frequencies (E most
common in English).

Attack Sketch
Most frequent ciphertext letter → guess it maps to ’E’ and
recover the shift.
If most common is ’K’(10) and ’E’(4): 10 ≡ 4+k (mod 26) ⇒
k = 6.

31
Frequency Analysis: Example

Task: Break a Shift Cipher

We intercept the following ciphertext: ROHKXGZOUT UL GRR

UVVXKYYKJ VKOVNK

1. Count Frequencies: We scan the ciphertext. The most frequent letters are ’K’ and ’V’ (both
appear 4 times).

2. Hypothesize: We have two strong guesses. Let’s test the first one: assume ’K’ (10) is the
encrypted form of ’E’ (4).

3. Solve for key k:

′ ′ ′ ′
Ek ( E ) = K ⇒ (4 + k) mod 26 = 10

k =6

4. Test Key: Decrypt using D6 (c) = (c − 6) mod 26.

5. Result:

◦ D6 (′ R ′ ) = (17 − 6) mod 26 = 11 →′ L′
◦ D6 (′ O ′ ) = (14 − 6) mod 26 = 8 →′ I ′
◦ D6 (′ H ′ ) = (7 − 6) mod 26 = 1 →′ B ′

The full message decrypts to: LIBERATION OF ALL OPPRESSED PEOPLE 32

The Symmetric-Key Model

General Encryption/Decryption

A symmetric cipher uses a single shared secret key, k, for both

encryption and decryption.
⊚ Encryption function: Ek (m) = c
⊚ (Encrypts plaintext m into ciphertext c using key k)
⊚ Decryption function: Dk (c) = m
⊚ (Decrypts ciphertext c back into plaintext m using key k)

For any key k and any message m:

Dk (Ek (m)) = m

The key k must be kept secret from Eve.

33
The Key Exchange Problem

The Symmetric-Key Issue

Alice and Bob must share a single secret key k for both
encryption Ek (m) and decryption Dk (m).

But how do they securely share k in the first place, with Eve
listening?

34
The Public-Key Vision

A New Idea: Asymmetric Keys

What if we split the key in two?

⊚ Public Key (for locking): Give this to the world.
Anyone can use it to encrypt a message for you.
⊚ Private Key (for unlocking): Keep this secret. Only
you can use it to decrypt messages sent to you.
This solves the key exchange problem!

35
RSA: The Ingredients

Three Core Tools

⊚ The ”Hard” Problem: Multiplication is easy
(p · q = n), but Factoring n back into p, q is extremely
hard.
⊚ The ”Hiding” Function: Modular exponentiation
(C = M e mod n) effectively scrambles the message M.
⊚ The ”Trapdoor”: C d = M mod n. ed ≡ 1 mod ϕ(n)
Euler’s Theorem (aϕ(n) ≡ 1 (mod n)). Knowing ϕ(n)
is the secret trapdoor to reverse the exponentiation.

36
RSA: The Trapdoor Math

The Goal
We need to find an encryption exponent e and decryption ex-
ponent d such that:

(M e )d ≡ M (mod n)

This works if we choose e and d such that:

ed ≡ 1 (mod ϕ(n))

Why? Because ed = 1 + kϕ(n) for some k.

M ed = M 1+kϕ(n) = M · (M ϕ(n) )k ≡ M · (1)k ≡ M (mod n)

Punchline: To find d, you need ϕ(n). To find ϕ(n) = (p −1)(q −1),

you must be able to factor n. 37
RSA: Key Generation

Steps

1. (Private) Pick two large primes p, q.

2. (Private) Compute ϕ(n) = (p − 1)(q − 1).
3. (Public) Compute modulus n = pq.
4. (Public) Pick public exponent e (with
gcd(e, ϕ(n)) = 1).
5. (Private) Compute private exponent d ≡ e −1
(mod ϕ(n)).
Publish: (n, e) Keep Secret: (p, q, d)

38
RSA: The Algorithm

Encryption (Public Key) Decryption (Private Key)

Alice wants to send M to Bob receives C . He uses his

Bob. She looks up Bob’s private key d.
public key (n, e).
M ≡ Cd (mod n)
e
C ≡M (mod n)
He recovers the message M.
She sends C .

39
RSA Example 1: Encrypting & Decrypting “HI”

Key Setup

⊚ p = 17, q = 23 ⇒ n = 391, ϕ(n) = 352.

⊚ Choose e = 3 (coprime with 352).
⊚ Compute d ≡ 3−1 (mod 352) ⇒ d = 235.
⊚ Public key (n, e) = (391, 3), Private key d = 235.

Encryption

“HI” ⇒ numeric (7, 8). Combine M = 78.

C = 783 mod 391 = 150.

Decryption

M = 150235 mod 391 = 78 ⇒ (7, 8) ⇒ HI.

40
RSA Example 2: Encrypting & Decrypting “YES”

Key Setup

⊚ p = 47, q = 59 ⇒ n = 2773, ϕ(n) = 2668.

⊚ Choose e = 17, compute d ≡ 17−1 (mod 2668) ⇒ d = 157.
⊚ Public key (2773, 17), Private key d = 157.

Encryption

“YES” ⇒ numeric (24, 04, 18) split into blocks. M1 = 2404, M2 = 18.

C1 = 240417 mod 2773 = 1575, C2 = 1817 mod 2773 = 1545.

Ciphertext: 1575 1545

Decryption

M1 = 1575157 mod 2773 = 2404, M2 = 1545157 mod 2773 = 18.

Recover: 24, 4, 18 ⇒ YES.

41
RSA Example: Encrypting & Decrypting “STOP”

Key Setup

⊚ p = 43, q = 59 ⇒ n = 2537, ϕ(n) = 2436.

⊚ Choose e = 13, compute d ≡ 13−1 (mod 2436) ⇒ d = 937.
⊚ Public key (2537, 13), Private key d = 937.

Encryption

“STOP” ⇒ numeric (18, 19, 14, 15) → group into blocks.

M1 = 1819, M2 = 1415.
Encrypt using C ≡ M 13 (mod 2537): C1 = 181913 mod 2537 =
2081, C2 = 141513 mod 2537 = 2182. → Ciphertext: 2081 2182

Decryption

Decrypt with d = 937: M1 = 2081937 mod 2537 = 1819, M2 =

2182937 mod 2537 = 1415.
Split: 18 19 14 15 ⇒ STOP.
42
Beyond Secrecy: Digital Signatures

Goal
Prove authorship/integrity of a message.

RSA Signature Flow

1. Alice computes S = M d (mod n) (sign with private

key).
2. Bob verifies by M ′ = S e (mod n) (check with public
key).
3. Accept if M ′ = M (in practice, on a hash of M with
padding).

43
Warning: ”Textbook” RSA is Unsafe

Why We Can’t Use Basic RSA Directly

The simple RSA algorithm we learned is ”deterministic” — the same plaintext

M always encrypts to the same ciphertext C .

This Leads to Major Attacks

⊚ Guessing Attack: If Eve thinks the message is ”YES” or ”NO”, she can
encrypt both with the public key and see which one matches the
ciphertext.
⊚ Malleability: An attacker can mathematically alter the ciphertext C to
produce a C ′ that decrypts to a different, but related, message M ′ .
Solution: Never encrypt raw data. We must add a random ”padding” scheme
to the message before encrypting.

44
Hash Functions

Definition

A hash function h(m) maps data of any size to a short, fixed-size ”digest” (e.g.,
SHA-256).
⊚ One-Way: Given the digest, you can’t find the original message.
⊚ Changing one bit of the input completely changes the output.
⊚ Collision-Resistant: It’s infeasible to find two different messages that
produce the same hash.

Practical Uses

⊚ Password Storage: Store h(password + salt) instead of the password.

⊚ File Integrity: Check if a downloaded file’s hash matches the original.
⊚ Digital Signatures: We sign the hash of a message, not the full message.

45
Hybrid Encryption (Best of Both Worlds)

The Problem

⊚ RSA (Asymmetric): Very secure for key exchange, but very slow.
⊚ AES (Symmetric): Very fast, but needs a shared secret key.

The Hybrid Solution

Use RSA only to exchange a key for AES.

1. Alice generates a new, random AES key K .
2. She encrypts her large file using K (fast).
3. She encrypts K using Bob’s RSA public key (slow, but K is tiny).
4. She sends: (Encrypted File) + (Encrypted K ).
Result: The speed of AES combined with the key-exchange security of RSA.

46
Application: Digital Signatures

Goal: Prove Authorship Integrity

How can Bob know a message really came from Alice and wasn’t altered?
Idea: Flip RSA! Sign with private key, verify with public key.

The Workflow (using Hashes)

1. Alice (Signs):
◦ Computes h(M), the hash of her message.
◦ ”Signs” the hash with her private key: S ≡ (h(M))d
(mod n).
2. Bob (Verifies):
◦ Receives (M, S). He computes h(M) himself.
◦ Verifies the signature with Alice’s public key: h′ ≡ S e
(mod n).
◦ If h(M) = h′ , the signature is valid!
47
Case Study: HTTPS / TLS (Web Security)

Goal: Securely browse a website.

HTTPS combines all our tools: Signatures (for identity) and Hybrid Encryption
(for secrecy).

The Handshake (Simplified)

1. Server Identity (Signature):

◦ Server sends its Certificate.
◦ Browser checks the digital signature on the certificate (using the
CA’s public key). This proves the server is who it says it is.

2. Secrecy (Hybrid Encryption):

◦ Browser generates a random AES session key, K .
◦ Browser encrypts K with the server’s RSA public key (from the
cert).
◦ Server decrypts K with its RSA private key.
Result: Both sides now have K . All web traffic is now encrypted with fast AES.

48
SSH (Secure Login)

Goal: Log in to a remote server without a password.

This is purely an authentication task. It uses digital signatures.

The Challenge-Response Workflow

1. Your public key is already stored on the server (in

/.ssh/authorized keys).
2. Server: ”If you are who you say you are, sign this random message:
81xTqR”
3. You: Your computer signs the challenge with your private key and sends
the signature back.
4. Server: The server verifies the signature using your public key.
5. Server: ”Signature is valid. Welcome.”
This proves you possess the private key without ever sending it over the network.

49
Summary: RSA in the Real World

Core Idea
RSA’s strength is asymmetric keys, based on the hardness of
factoring.

Key Takeaways

⊚ Never use ”textbook” RSA. Always use padding

(OAEP).
⊚ For Secrecy (HTTPS, PGP): Use Hybrid Encryption.
⊚ RSA encrypts a fast symmetric key (e.g., AES).
⊚ For Authentication (SSH, Software Updates): Use
Digital Signatures.
⊚ RSA signs a hash of the message.
50