NT01_L04 - HackMD

###### tags: `Number Theory` `NT01` # L04 Public-Key Cryptography --- ## Last Week - Groups of Modular Arithmetic - Permutation Group - Permutation Cipher --- ## This week - Problem with Private Keys - Public-Key Cryptography - Python for Basic Diffie-Hellman --- # 1.1 How to secure the key We have seen that we can make out key complicated enough to stop someone hack our information from Brute Force Attack. But one important thing is about, how do we pass the key to the receiver? In most case, our communication of message and key has to be in the same channel, so if someone can intecept message, he/she can intercept the key as well. We need a safer way to communicate our key. ---- #### 1.2 Alice and Bob 1. Alice and Bob then both choose a secret keys; 1.1 let’s call Alice’s secret integer $a$ Bob’s $b$ 2. Eve is attempting to eavesdrop on the communication between Alice and Bob. So these two private keys, a and b, cannot travel through the only communication channel. 3. Alice and Bob begin by choosing two natural numbers: a prime p, and another one, g (with $1 < g < (p − 1)$), **need to be carefully chosen**. Both p and g are transmitted in the clear – that is, Eve can intercept them. 4. Alice then computes $𝐴=𝑔^𝑎 (𝑚𝑜𝑑\ 𝑝)$ , sends this $A$ to Bob through the channel; Bob computes $𝐵=𝑔^𝑏 (𝑚𝑜𝑑\ 𝑝)$ , sends this $B$ to Alice ( Eve can get both). 5. Finally Alice computes $𝐵^𝑎 (𝑚𝑜𝑑\ 𝑝)$ , and Bob computes $𝐴^𝑏 (𝑚𝑜𝑑\ 𝑝)$ . Now, both Alice and Bob now have a shared secret key s! $$s = B^a\ (mod\ p) = g^{ab}\ (mod\ p) = g^{ba}\ (mod\ p) = A^b\ (mod\ p)$$ Why is this? Eve confused... ---- #### 1.3 One-Way Function why can Eve not also compute the secret key s? Because it is difficult to solve Only Given A and B, (without know any of a or b) We call this type of function one-way function: $$f: x \mapsto x^e\ mod\ n$$, or in Alice's case for instance $$f: g \mapsto g^a≅A\ mod\ p$$ It is easy to compute A given g and a; but very difficult to compute a given A and g. ---- ![picture](https://drive.google.com/uc?export=view&id=1qMOfSj-7OHwNDMhsQp-E1TeFfYK_E1pB) ---- #### 2. raise power in $\Bbb{Z}_n$ Let's produce table of "Raise power" for $\Bbb{Z}^{*}_5$ and $\Bbb{Z}_8$ | $\Bbb{Z}^{*}_5$ $^$ | 1 | 2 | 3 | 4 | | --- | --- | --- | --- | --- | | 1 | 1 | 1 | 1 | 1 | | 2 | 2 | 4 | 3 | 1 | | 3 | 3 | 4 | 2 | 1 | | 4 | 4 | 1 | 4 | 1 | | $\Bbb{Z}_8$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | ----------- | --- | --- | --- | --- | --- | --- | --- | | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | | 2 | 2 | 4 | 0 | 0 | 0 | 0 | 0 | | 3 | 3 | 1 | 3 | 1 | 3 | 1 | 3 | | 4 | 4 | 0 | 0 | 0 | 0 | 0 | 0 | | 5 | 5 | 1 | 5 | 1 | 5 | 1 | 5 | | 6 | 6 | 4 | 0 | 0 | 0 | 0 | 0 | | 7 | 7 | 1 | 7 | 1 | 7 | 1 | 7 | ---- #### 2.1 Generator What is the special about 2 and 3 in $\Bbb{Z}^{*}_5$? By raising power on themself, they generate the entire group! We need g to be the generator in $\Bbb{Z}^{*}_p$, So $g^{ab}$ can range from 1 to p-1, it maximise the number of iteration for Brute Force Attack. ***Note(optional)***: Theoritically, the p can be a large composite number, and g can be a primative root in p's multiplicative group. But this is beyond the scope of this tutorial and practically inefficient. So we adapt the way that p as large prime, and g as its generator for multiplicative group. ---- #### 2.2 large Even though we know there are infinitly many primes, But how they are distributed? We don't know the answer yet. So to "Get a Large Prime", we can only apply Trial and Error stretagy 1. Randomly pick a large number 2. Test if it was prime 3. if not, repeat (1) and (2), until success from (2) We will introduce Primality test Next Week