cryptography

DHM, RSA,

Diffie-Hellman-Merkle key exchange

  • exchange mutually-created random secret key over insecure channel

  • over channel: Alice and Bob agree on prime p (say 97) and base g (say 5)

  • Alice

    • in secret: chooses random number a in {2, …, p-1} (say 5)

    • in secret: computes α = ga mod p ( here α = 55 mod 97 = 21 )

    • over channel: sends α ( 21 ) to Bob

  • Bob

    • in secret: chooses random number b in {2, …, p-1} (say 76),

    • in secret: computes β = gb mod p ( here β = 576 mod 97 = 24 )

    • over channel: sends β ( 24 ) to Alice

  • secret key

    • Bob uses αb mod p ( here 2176 mod 97 = 88 )

    • Alice uses βa mod p ( here 245 mod 97 = 88 )

DHM correctness

αb   =   (ga)b   =   ga⋅b   =   gb⋅a   =   (gb)a   =   βa

DHM efficiency

  • use fast modular exponentiation

DHM security

  • to break, eavesdropper needs to solve discrete log (exponent) problem:

given x, find e     ge = x (mod n)

  • so far, no one knows how to do this much faster than trying all possible values for x

  • how long will this take if n = 10200   ?

RSA public-key cryptosystem

Alice publishes her public numbers

  • picks secret primes p,q     11, 13

  • sets public n = p ⋅ q     11 ⋅ 13 = 143

  • computes secret φ(n) = (p-1)(q-1)     (11 - 1) ⋅ (13 - 1) = 120

  • picks random e in {2, …, φ(n)-1} coprime to φ(n)     23 coprime to 120

  • computes secret d = e-1 mod φ(n)     47 = 23-1 mod 120

  • publishes n, e     143, 23

Alice's computation
extended euclid(120,23)
120  23   5   3   2   1   0
      5   4   1   1   2
 47  -9   2  -1   1   0

so gcd(120,23) = 1 = 47*23 + 120*-9, so
23^-1 (mod 120) = 47
Bob sends secret message to Alice

  • wants to send secret m=84 (must be coprime to n)   to Alice

  • computes β = me mod n

  • sends Alice β     24

Bob's computation
23 = 10111_2

84^1  =  1 *   1 * 84 =  84 mod 143
84^2  =  84 *  84      =  49 mod 143
84^5  =  49 *  49 * 84 =  54 mod 143
84^11 =  54 *  54 * 84 = 128 mod 143
84^23 = 128 * 128 * 84 =  24 mod 143
Alice recovers Bob's secret message

  • receives Bob's encrypted message β   = 24

  • computes m = βd mod n   = 2447 mod 143   = 84

Alice's computation
47 = 101111_2

24^1  =   1 *   1 * 24 =  24 mod 143
24^2  =  24 *  24      =   4 mod 143
24^5  =   4 *   4 * 24 =  98 mod 143
24^11 =  98 *  98 * 24 = 123 mod 143
24^23 = 123 * 123 * 24 =  19 mod 143
24^47 =  19 *  19 * 24 =  84 mod 143
RSA correctness

  • mod n: βd = (me)d = me⋅d = m

  • if m is coprime to n, by Euler's theorem

  • mod n: me⋅d   =   mφ(n)⋅k +1 =   (mφ(n))k m1 =   1 ⋅ m = m

  • mod 143: 2447 = (8423)47 = 8423⋅47 = 84120⋅9 +1 = (84120)9 841 = 1 ⋅ 84 = 84

RSA security

  • Eve needs either

    • to factor n (and then find e inverse, which is easy)

    • factor 143 (and find 23 inverse)   or

    • to solve β = ?e mod n

    • solve 24 = ?23 mod 143

  • so far, both problems seem hard … but math hackers keep learning