How could Alice, Bob, and Christ to exchange keys safely? Use trusted third party, (TTP)
Basics of Kerbose. Insecure against active attacks, such as replay attacks.
Decentralized key exchanges:
- Merkel (1974)
- Diffe-Hellman (1976)
- RSA (1977)
- ID-based enc. (BF 2001)
- Functional enc. (BSW 2011)
E(k, m) is a symmetric cipher with , define puzzle(P) = E(P, “message”), where .
- Alice prepare puzzles, set , and send all of them to Bob.
- Bob choose a random puzzle, solve it, obtain , and send to Alice.
The eavesdropper needs to to solve puzzles to figure out the specified by , so the time complexity is .
Quadratic gap is possible if we treat ciper as a black box oracle.
Fix a large prime , (e.g 600 digits, ). Fix an integer g such that .
Alice choose random a such , Bob choose random b such as .
- Alice -> Bob: .
- Bob -> Alice:
Then, they can get the secret:
mod pis the number space , see Number Theory below.
Best known algorithm to solve DH problem, arithmetic modular function, is roughly , thus
|Cipher size||Modulus size||Elliptic Curve size|
|80bits||1024 bits||160 bits|
|128 b8ts||3072 bits||256 bits|
|256 bits||15360 bits||512 bits|
Alternatively, we can use elliptic curve to decrease the size, see above.
The Diffie-Hellman is insure against man-in-the-middle attack.
Define the (G, E, D):
- G: randomize algorithm to generate key pairs (pk, sk).
- E(pk, m) takes and output .
- D(sk, c) takes and outputs or .
Notion: is a positive number, is a positive prime number, and .
The modular arithmetic: .
For all integers. there exists integers. such that .
Inverse of x in is an element in , aka in . x in has an inverse if and only if .
Proof: . thus in .
Let p be a prime,
To generate large random prime:
- Choose a a random integer
- test if in .
- If so, output p. Otherwise, go to step 1
The chance that p is not prime < .
is a cyclic group, that is , such that . g is called a generator of .
Given , the set of is called the group generated by g, denoted as
<g>. The order of is the size of :
Thm Lagranage: .
for an integer , define . Examples:
- For .
Euler’s theorem: .
Modular e’th roots
When does in exists? Suppose , for all c in , in exists. let in , in .
x in is Quadratic Residue, aka Q.R, if and only if in . p is odd prime.
How to support 2048 bit number arithmetic operations? Karatsuba 1960: use 3 mults to achieve .
DLOG is hard in G if for all efficient algorithm A: is negligible. such as:
- for large p, see Diffle-Hellman
- Elliptic curve group mod p
For a group G, q = |G| be a prime, choose generate g, h of G, for , define in G. Finding collision for is as hard as computing .