Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4572 + 2433 = 7005
 Foundations of Cryptography • CSCI 662-01 • Spring Semester 2018
Course Page

## CSCI 662—Foundations of Cryptography Chapter 6. Foundations of Public Key Cryptography Lecture Notes

Prof. Alan Kaminsky
Rochester Institute of Technology—Department of Computer Science

### Public Key Cryptosystems

• Public operation, private operation (asymmetric)

• Public key, private key (asymmetric)

• Public key encryption — requirements
• Ciphertext = EncryptpublicKey (Plaintext) and Plaintext = DecryptprivateKey (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

• Digital signature — requirements
• Signature = SignprivateKey (Message) and VerifypublicKey (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

• Establishing authenticity of public keys
• Public Key Infrastructure (PKI)

### Congruences

• 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 Arithmetic

• 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

• Modular arithmetic is used in many public key algorithms

### Modular Exponentiation

• Example: Compute 201197 (mod 397)

• First compute the following powers of 201 by repeatedly squaring (all calculations are (mod 397)):
2011 = 201
2012 = 201 ⋅ 201 = 304
2014 = 304 ⋅ 304 = 312
2018 = 312 ⋅ 312 = 79
20116 = 79 ⋅ 79 = 286
20132 = 286 ⋅ 286 = 14
20164 = 14 ⋅ 14 = 196
201128 = 196 ⋅ 196 = 304

• Then compute the exponentiation by multiplying the proper powers of 201:
201197
= 201(128 + 64 + 4 + 1)
= 201128 ⋅ 20164 ⋅ 2014 ⋅ 2011
= 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 = ax (mod n) is easy (exponentiation)

• Given a and y, computing x such that y = ax (mod n) is hard (discrete logarithm) . . .
• . . . if n is a large prime number

• 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

### Greatest Common Denominator

• 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

### Multiplicative Inverse

• 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

### Least Common Multiple

• 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

### Fermat's Little Theorem

• Theorem: Let a be an integer and p be a prime, then ap ≡ a (mod p).

• Corollary: ap−1 ≡ 1 (mod p).
• Proof:
• ap ≡ a (mod p)
• ap ⋅ a−1 ≡ a ⋅ a−1 (mod p)
• ap−1 ≡ 1 (mod p)

• Corollary: a ⋅ ap−2 ≡ 1 (mod p).
• Proof:
• ap−1 ≡ 1 (mod p)
• 1 ⋅ ap−1 ≡ 1 (mod p)
• a ⋅ a−1 ⋅ ap−1 ≡ 1 (mod p)
• a ⋅ ap−2 ≡ 1 (mod p)

• In other words, the multiplicative inverse of a is ap−2 (mod p).

• This is another way to compute the multiplicative inverse
• But the Extended Euclidean Algorithm is much faster

### Euler Totient Function

• 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 = p1e1 ⋅ p2e2 ⋅ ⋅ ⋅ pnen

• Then Φ(m) = (p1e1 − p1e1−1) ⋅ (p2e2 − p2e2−1) ⋅ ⋅ ⋅ (pnen − pnen−1)

• Example: Φ(4116)
4116 = 22 ⋅ 31 ⋅ 73
Φ(4116) = (22 − 21) ⋅ (31 − 30) ⋅ (73 − 72) = (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

• 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

### Euler's Theorem

• 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

### Security Level

• 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((64b/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(2n)
• 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

• Consequently, public key algorithms require a lot more computation than block ciphers

 Foundations of Cryptography • CSCI 662-01 • Spring Semester 2018
Course Page
 Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4572 + 2433 = 7005