| Home Page |

| Course Page |

Chapter 6. Foundations of Public Key Cryptography

Lecture Notes

Rochester Institute of Technology—Department of Computer Science

- Public operation, private operation (asymmetric)
- Public key, private key (asymmetric)
- Public key encryption — requirements
- Ciphertext = Encrypt
_{publicKey}(Plaintext) and Plaintext = Decrypt_{privateKey}(Ciphertext) - Decrypting ciphertext is hard without the private key, even if public key is known
- Finding private key is hard, even if public key is known

- Ciphertext = Encrypt
- Digital signature — requirements
- Signature = Sign
_{privateKey}(Message) and Verify_{publicKey}(Message, Signature) - Determining signature of a message is hard without the private key, even if public key is known
- Finding private key is hard, even if public key is known

- Signature = Sign
- Establishing authenticity of public keys
- Public Key Infrastructure (PKI)

- We say: "a is congruent to b modulo n"
- We write: "a ≡ b (mod n)"
- We mean: "n is a factor of (a − b)" or "n divides (a − b)" or "(a − b) is a multiple of n"
- Example: 29 ≡ 5 (mod 12)
- Because (29 − 5) = 24, and 12 is a factor of 24, because 24 = 2⋅12

- Congruence classes
- The "congruence class of a modulo n" is the set of all integers b such that b ≡ a (mod n)
- Example: The congruence class of 5 (mod 12) is {. . . , −31, −19, −7, 5, 17, 29, 41, . . .}
- Every integer is a member of exactly one congruence class (mod n)
- We usually represent a congruence class by the smallest nonnegative member of the set, which is in the range 0 through n−1

- Modular addition: a + b ≡ c (mod n)
- To find c, compute (a + b), divide that by n, let c = the remainder
- This works by the definition of division:
- (a + b) = q⋅n + c, 0 ≤ c ≤ n−1 (q = quotient, c = remainder)
- (a + b) − c = q⋅n
- That is, n is a factor of ((a + b) − c)
- Therefore, a + b ≡ c (mod n)
- Example: 42 + 17 ≡ 11 (mod 12), because 42 + 17 = 59 = 4⋅12 + 11

- Modular subtraction: a − b ≡ c (mod n)
- To find c, compute (a − b), divide that by n, let c = the remainder
- Example: 5 − 8 ≡ 9 (mod 12), because 5 − 8 = −3 = −1⋅12 + 9

- Modular multiplication: a ⋅ b ≡ c (mod n)
- To find c, compute (a ⋅ b), divide that by n, let c = the remainder
- Example: 8⋅9 ≡ 0 (mod 12), because 8⋅9 = 72 = 6⋅12 + 0

- Repeated modular arithmetic operations
- When doing a series of modular additions, subtractions, or multiplications . . .
- You can do all the operations first, then find the congruence once at the end . . .
- Or you can find the congruence after each individual operation
- Either way, you get the same answer
- Example: 9 + 18 + 23 + 15 (mod 12)
- 9 + 18 + 23 + 15 = 65 ≡ 5 (mod 12)
- 9 + 18 = 27 ≡ 3 (mod 12); 3 + 23 = 26 ≡ 2 (mod 12); 2 + 15 = 17 ≡ 5 (mod 12)

- Example: 9 ⋅ 18 ⋅ 23 ⋅ 15 (mod 12)
- 9 ⋅ 18 ⋅ 23 ⋅ 15 = 55890 ≡ 6 (mod 12)
- 9 ⋅ 18 = 162 ≡ 6 (mod 12); 6 ⋅ 23 = 138 ≡ 6 (mod 12); 6 ⋅ 15 = 90 ≡ 6 (mod 12)

- Multiplicative inverse
- The "multiplicative inverse of a modulo n" is written "a
^{−1}(mod n)" - It is the integer such that a ⋅ a
^{−1}≡ 1 (mod n), if such an integer exists - Example: 17
^{−1}is 5 (mod 12), because 17⋅5 ≡ 1 (mod 12), because 17⋅5 = 85 = 7⋅12 + 1 - Later we will see an algorithm for finding the multiplicative inverse

- The "multiplicative inverse of a modulo n" is written "a
- Modular arithmetic is used in many public key algorithms

- Example: Compute 201
^{197}(mod 397) - First compute the following powers of 201 by repeatedly squaring (all calculations are (mod 397)):

201^{1}= 201

201^{2}= 201 ⋅ 201 = 304

201^{4}= 304 ⋅ 304 = 312

201^{8}= 312 ⋅ 312 = 79

201^{16}= 79 ⋅ 79 = 286

201^{32}= 286 ⋅ 286 = 14

201^{64}= 14 ⋅ 14 = 196

201^{128}= 196 ⋅ 196 = 304 - Then compute the exponentiation by multiplying the proper powers of 201:

201^{197}

= 201^{(128 + 64 + 4 + 1)}

= 201^{128}⋅ 201^{64}⋅ 201^{4}⋅ 201^{1}

= 304 ⋅ 196 ⋅ 312 ⋅ 201

= 34 ⋅ 312 ⋅ 201

= 286 ⋅ 201

= 318 - The proper powers of 201 come from the binary version of the exponent: 197 = binary 11000101 = 128 + 64 + 4 + 1
- Given a and x, computing y = a
^{x}(mod n) is easy (exponentiation) - Given a and y, computing x such that y = a
^{x}(mod n) is hard (discrete logarithm) . . .- . . . if n is a
*large*prime number

- . . . if n is a
- Modular exponentiation is used in several public key algorithms, including RSA, Diffie-Hellman key exchange, and various digital signature algorithms
- The security of several public key algorithms, including Diffie-Hellman and digital signatures, relies on the hardness of the discrete logarithm problem

- gcd (a, b) = The largest number that divides (is a factor of) both a and b
- Euclidean Algorithm
- Fact: gcd (a, b) = gcd (b, a mod b)
- Repeatedly replace (a, b) with (b, a mod b) until we get to (x, 0); then gcd (a, b) = x

- Example: gcd (100, 56)

(100, 56) → (56, 44) → (44, 12) → (12, 8) → (8, 4) → (4, 0)

Then gcd (100, 56) = 4 - If gcd (a, b) = 1 (they have no common factors other than 1), then a and b are
**relatively prime**

- Extended Euclidean Algorithm for computing the multiplicative inverse of a (mod n), or a
^{−1}(mod n)- For the multiplicative inverse to exist, gcd (a, n) must be 1
- Algorithm:

(x, y, t2, t1) ← (n, a, 0, 1)

Loop:

r ← x mod y

If r = 0: Exit loop

q ← (x − r)/y

t ← t2 − t1⋅q

(x, y, t2, t1) ← (y, r, t1, t)

// At this point, y = gcd (a, n) and t1 = a^{−1}(mod n)

If y ≠ 1: Return "no inverse"

If t1 < 0: t1 ← t1 + n

Return t1

- Example: Compute 46
^{−1}(mod 397)x y t2 t1 r q t 397 46 0 1 29 8 −8 46 29 1 −8 17 1 9 29 17 −8 9 12 1 −17 17 12 9 −17 5 1 26 12 5 −17 26 2 2 −69 5 2 26 −69 1 2 164 2 1 −69 164 0 46

^{−1}≡ 164 (mod 397); that is, 46⋅164 ≡ 1 (mod 397); because 46⋅164 = 7544 = 19⋅397 + 1

- Common multiple of a and b = An integer that is a multiple of a and a multiple of b
- Least common multiple of a and b = lcm (a, b) = The smallest (nonnegative) common multiple
- Fact: lcm (a, b) = a⋅b / gcd (a, b)
- You can prove this using the prime factorizations of a and b
- So a = lcm (a, b) ⋅ gcd (a, b) / b
- And b = lcm (a, b) ⋅ gcd (a, b) / a

- Fact: Any common multiple of a and b is a multiple of lcm (a, b)
- If x is a common multiple of a and b, then x = i⋅a and x = j⋅b for some integers i and j
- So x = i ⋅ a = i ⋅ lcm (a, b) ⋅ gcd (a, b) / b, which is a multiple of lcm (a, b)
- And x = j ⋅ b = j ⋅ lcm (a, b) ⋅ gcd (a, b) / a, which is a multiple of lcm (a, b)

- Fact: If a divides x and b divides x, then lcm (a, b) divides x
- "a divides x" means "x is a multiple of a"
- "b divides x" means "x is a multiple of b"
- That is, x is a common multiple of a and b
- Thus, x is a multiple of lcm (a, b) by the previous fact
- Restating: lcm (a, b) divides x

- Fact: If y ≡ x (mod a) and y ≡ x (mod b), then y ≡ x (mod lcm (a, b))
- Restating: a divides (y − x) and b divides (y − x)
- Thus, lcm (a, b) divides (y − x) by the previous fact
- Restating: y ≡ x (mod lcm (a, b))

- These facts are used in the proof of why RSA works

- Theorem: Let a be an integer and p be a prime, then a
^{p}≡ a (mod p). - Corollary: a
^{p−1}≡ 1 (mod p).- Proof:
- a
^{p}≡ a (mod p) - a
^{p}⋅ a^{−1}≡ a ⋅ a^{−1}(mod p) - a
^{p−1}≡ 1 (mod p)

- Corollary: a ⋅ a
^{p−2}≡ 1 (mod p).- Proof:
- a
^{p−1}≡ 1 (mod p) - 1 ⋅ a
^{p−1}≡ 1 (mod p) - a ⋅ a
^{−1}⋅ a^{p−1}≡ 1 (mod p) - a ⋅ a
^{p−2}≡ 1 (mod p)

- In other words, the multiplicative inverse of a is a
^{p−2}(mod p). - This is another way to compute the multiplicative inverse
- But the Extended Euclidean Algorithm is much faster

- Given an integer m, the Euler totient Φ(m) is the number of integers less than m that are relatively prime to m
- Calculating Φ(m): First factor m as a product of prime powers:

m = p1^{e1}⋅ p2^{e2}⋅ ⋅ ⋅ pn^{en} - Then Φ(m) = (p1
^{e1}− p1^{e1−1}) ⋅ (p2^{e2}− p2^{e2−1}) ⋅ ⋅ ⋅ (pn^{en}− pn^{en−1}) - Example: Φ(4116)

4116 = 2^{2}⋅ 3^{1}⋅ 7^{3}

Φ(4116) = (2^{2}− 2^{1}) ⋅ (3^{1}− 3^{0}) ⋅ (7^{3}− 7^{2}) = (4 − 2) ⋅ (3 − 1) ⋅ (343 − 49) = 2 ⋅ 2 ⋅ 294 = 1176 - Fact: If p is prime, then Φ(p) = p−1
- Fact: If n = pq is the product of two primes p and q, then Φ(n) = (p−1)(q−1)
- Example: Φ(8505307)

8505307 = 2689 ⋅ 3163 (both prime)

Φ(8505307) = 2688 ⋅ 3162 = 8499456 - Given n = pq where p and q are known primes, finding Φ(n) is easy
- Given just n, the product of two unknown primes, finding Φ(n) is hard (integer factorization) . . .
- . . . if p and q are
*large*prime numbers, and not too close together

- . . . if p and q are
- The RSA Factoring Challenge: https://en.wikipedia.org/wiki/RSA_Factoring_Challenge
- The security of RSA relies on the hardness of computing Φ(n), that is, the hardness of the integer factorization problem

- A generalization of Fermat's Little Theorem
- Theorem: Let a and m be integers with gcd(a,m) = 1, then a
^{Φ(m)}≡ 1 (mod m). - The Euler totient function and Euler's Theorem are used in RSA

- There are many special-purpose algorithms for solving the discrete logarithm problem
- There are many special-purpose algorithms for solving the integer factorization problem
- Best
*general*-purpose algorithm: General Number Field Sieve (GNFS)- Solves the discrete logarithm problem — breaks DH key exchange
- Solves the integer factorization problem — breaks RSA
- Smallest asymptotic running time for large integers

- GNFS asymptotic running time for a
*b*-bit integer is O(exp((64*b*/9)^{1/3}(log*b*)^{2/3}))- A "subexponential"-time algorithm
- Asymptotically larger than any polynomial running time
- Asymptotically smaller than any exponential running time

- Generic attacks on block ciphers versus public key algorithms
- Block ciphers: Exponential time, O(2
^{n}) - Public key algorithms: Subexponential time
- Therefore, public key integer sizes (
*b*bits) must be much larger than block cipher key sizes (*n*bits) - Recommended bit sizes for equivalent security levels:
*n**b*80 1024 128 3072 192 7680 256 15360

- Block ciphers: Exponential time, O(2
- Consequently, public key algorithms require a
*lot*more computation than block ciphers

| Course Page |

| Home Page |