# jemdoc: addcss{rbh.css}, addcss{jacob.css} = cryptography ~~~ {}{raw} DHM, RSA, ~~~ ~~~ {}{raw}

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}} ~ ? ~~~ ~~~ {}{raw}

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 [http://www.technologyreview.com/news/517781/math-advances-raise-the-prospect-of-an-internet-security-crisis/ math hackers] keep learning ~~~