NT01_L02 - HackMD

###### tags: `Number Theory` `NT01` # L02 Euclidean Algorithm and Affine Cipher --- ## Last Week - Introduction on modular arithmetic - Fundamental Cipher: Caeser Cipher - Brute Force Attack (Python for loop) --- ## This week - Modular arithmetic with multiplication - Great Common Divisor and Eulidean Algorithm - Python While loop and "Try - Exception" structure --- ### 1. Increase difficulty for hackers Last week, We learnt that for Cryptography like Caeser Cipher, it is every easy for a hacker to try all possible keys . So our stretagy at the first stage is to make his/her trial not so easy. We have used one pair of arithmetic, (+ & -) for one key in our modular, What if we introduce another pair of arithmetic, ($\times$ and $\div$) ---- ### 1.1 Modular Multiplication Let's start with some example on MOD 26 - $2 \times 14 = 2\ MOD\ 26$ - $2 \times 1 = 2\ MOD\ 26$ we can see that, 2 multiply two distinct values in Modular 26 generate same output. This is not good for encryption Image that, your choose 2 as a key, If you get encrypted letter C, How do you know that the original message is B or O? In modular 26, the addtion is a one-to-one function, but not multiplication. ---- 1.2 Zero Divisor Numbers like 2 have a formal name in MOD 26: **Zero Devisor** **Definition**: An non-zero element a in MOD n is called non-zero devisor, if there exits another non-zero element b in MOD n that $a \times b = 0\ MOD\ n$ Example: - $2 \times 13 = 0\ MOD\ 26$ - $4 \times 13 = 0\ MOD\ 26$ - $6 \times 13 = 0\ MOD\ 26$ - $\dots$ {2, 4, 6, 13 ,$\dots$} are all zero divisors But, is there an one-off criteria to identify all Zero Divisor, rather than try every multiplication for every number? Yes! ---- 1.3 Greatest Common Divisor The Idea of Greatest Common Divisor can be demonstrated in example below Example: - Divisor of 10: $\{ 1, 2, 5, 10 \}$ - Divisor of 15: $\{ 1, 3, 5, 15 \}$ - $gcd (10, 15) = 5$ **Criteria for identifing zero divisors:** **Theorem 1.1:** *if gcd(a, n) = d > 1 for some a in MOD n, then a is a Zero Divisor in MOD n.* Now, we only need a way to evaluate for given any gcd(a, n) --- 2. Euclidean Algorithm Euclidean Algorithm was based on the following Theorem **Theorem 1.2:** *let a, b, q, r be any positive integers such that $a=qb + r$. Then gcd(a,b) = gcd(b, r)* Example: let a = 26, b = 4, then q = 6, r = 2, so we have $26 = 4 \times 6 + 2$ $gcd(b, r) = gcd(4, 2) = 2 = gcd(26,4)$ ---- 2.1 Euclidean Algorithm Continued Euclidean Algorithm then can be described as the following processes **Euclidean Alogrithm:** *$a = q_1b + r_1,\ r_1 \in (0, b)$* *$b = q_2r_1 + r_2,\ r_2 \in (0, r_1)$* *$r_1 = q_3r_2 + r_3,\ r_3 \in (0, r_2)$* $\dots$ *$r_{s-1} = q_{s+1}r_s$* Then $r_s = gcd(a,b)$ We will use Python to achieve this simple and elegent algorithm!