4003-482-01/4005-705-01 Cryptography
Chapter 6. Introduction to Public Key Cryptography
Lecture Notes

Public Key Cryptosystems

• Public operation, private operation (asymmetric)

• Public key, private key (asymmetric)

• Public key encryption -- requirements
  • Ciphertext = Encrypt_publicKey (Plaintext) and Plaintext = Decrypt_privateKey (Ciphertext)
  • Encrypt operation is hard to invert, even if public key is known
  • Finding private key is hard, even if public key is known

• Digital signature -- requirements
  • Signature = Sign_privateKey (Message) and Message = Verify_publicKey (Signature)
  • Verify operation is hard to invert, 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)

Finite Groups

• Group consists of a set of elements and an operation, symbolized as #

• Requirements:
  • Closed: For any elements A and B, C = A # B is also an element
  • Associativity: For any elements A, B, and C, A # (B # C) = (A # B) # C
  • Identity: There is an element I such that A # I = A for any element A
  • Inverses: For any element A, there is an element A' such that A # A' = I

• Example: The set of integers Z = {. . . , −2, −1, 0, 1, 2, . . .} and the addition operation (+) form a group
  • It is an infinite group because the set of elements is infinite

• Example: Given a prime number p, the set {1, 2, . . . , p−1} and the "multiplication modulo p" operation (* (mod p)) form a group called Z_p^*, the "multiplicative group mod p"
  • It is a finite group because the set of elements is finite

Modular Exponentiation

• a^x = a * a * . . . * a (mod p)
  • x copies of a multiplied together

• Example: Compute 201¹⁹⁷ (mod 397)

• First compute the following powers of 201 by repeatedly squaring (all calculations are (mod 397)):
  201¹ = 201
  201² = 201 * 201 = 304
  201⁴ = 304 * 304 = 312
  201⁸ = 312 * 312 = 79
  201¹⁶ = 79 * 79 = 286
  201³² = 286 * 286 = 14
  201⁶⁴ = 14 * 14 = 196
  201¹²⁸ = 196 * 196 = 304

• Then compute the exponentiation by multiplying the proper powers of 201:
  201¹⁹⁷
  = 201^{(128 + 64 + 4 + 1)}
  = 201¹²⁸ * 201⁶⁴ * 201⁴ * 201¹
  = 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 p) is easy (exponentiation)

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

• Finite group 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 in Z_p^*

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 m), or a⁻¹ (mod m)
  • For the multiplicative inverse to exist, gcd (a, m) must be 1
  • Algorithm:
    (x, y, t2, t1) ← (m, 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, m) and t1 = a⁻¹ (mod m)
    If y ≠ 1: Return "no inverse"
    If t1 < 0: t1 ← t1 + m
    Return t1

• Example: Compute 46⁻¹ (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⁻¹ = 164 (mod 397); that is, 46 * 164 = 1 (mod 397)

Fermat's Little Theorem

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

• Corollary: a^p−1 = 1 (mod p).

• Corollary: 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 in Z_p^*
  • 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 = 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² * 3¹ * 7³
  Φ(4116) = (2² − 2¹) * (3¹ − 3⁰) * (7³ − 7²) = 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: http://www.rsa.com/rsalabs/node.asp?id=2094

• 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(2ⁿ)
  • 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

Cryptography • 4003-482-01/4005-705-01 • Spring Quarter 2013

Course Page

Alan Kaminsky • Department of Computer Science • Rochester Institute of Technology • 4486 + 2220 = 6706

Home Page

Copyright © 2012 Alan Kaminsky. All rights reserved. Last updated 23-Jan-2012. Please send comments to ark­@­cs.rit.edu.