# 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
~~~