NT01_L01.5 - HackMD

--- ###### tags: `Number Theory` `NT01` # L01.5 Introduction to Group and Caesar Cipher --- ## Last week - Introduction: Module, Home coding, Friday - Natural Number and (Modular) arithmetic - Intro to Python (numpy array) --- ## This week - Introduction to Group - Caesar Cipher and Brute Force Attack - For loop in Python --- ### 1.1 Modular and Group We use "modular n" or "MOD n" so far, actually this type of structure have a more advanced name in Math: **Group**! **Defintion:** A non-empty set G and a binary operation * form a structure called group (G, *), with following properties: 1. For all $a, b, c \in G$, $(a*b)*c = a*(b*c)$ 2. Exit $e \in G$, that for any $g \in G$, $g*e = e*g = g$ 3. for any $g \in G$, exit $h \in G$, that $g * h = e$ ---- 1.2 Example $(\Bbb{Z}_5, +)$ From now on, we will denote our "Modular n" $\Bbb{Z}_n$, and attach different operation to specify different groups **$(\Bbb{Z}_5, +)$ or $(\{0,1,2,3,4\}, +)$** Check: 1. For all $a, b, c \in G$, $(a*b)*c = a*(b*c)$ >yes, e.g. (1+2)+3 = 1 = 1+(2+3) 2. Exit $e \in G$, that for any $g \in G$, $g*e = e*g = g$ >yes, 0 is that e, identity element 3. for any $g \in G$, exit $h \in G$, that $g * h = e$ >yes, 1+4 = 0, 2+3 = 0, 3+2=0, 4+1=0 ---- ### 1.3 Some Simple term of Group **Defintion a.:** The *number of elements* of group G is called the **order** of G and denoted by |G|. **Defintion b.:** The elements of group G that generate entire group is called the Generators. Here, "generate" means apply the operation on itself. ---- 1.4 Example $(\Bbb{Z}_5, +),\ with\{0,1,2,3,4\}$ **a**. $|(\Bbb{Z}_5, +)|=5$ **b.** for $(\Bbb{Z}_5, +)$, 1 is a trivial generetor, as: $$\{1=1, 2=1+1, 3=1+1+1,4=1+1+1+1,0=1+1+1+1+1\}$$ **Quiz:** Can you find other generators? --- #### 2. Caeser Cipher and Brute-force Attack We learnt a authentification application of Modular Arithmetic last week. This week we will learn its application in encryption and decryption. ![](https://drive.google.com/uc?export=view&id=1dFHNfVr9V4Zv-Jf1u6vr8q5KIXdWnAp0) This is Caeser Cipher (49 B.C.) ---- 2.1 Procedure of Caeser Cipher 1. Mapping alphabets to 0-25, e.g. Hello = 2. Choose a Key, e.g. K = 5 3. Add Key to each alphabet of the message, so Hello => Mjqqt 4. Send "Mjqqt" to the receiver with the key; 5. Receiver use Key to map back the original message. This is very easy to create, also, very easy to hack. ---- 2.2 Brute-force Attack The easiest way to hack encryption like Caeser Cipher with today's computer, is just try every posible value of Key. Lucky for any hacker, Key for Caeser Cipher are just numbers from $\{1,2,3,\dots,25\}$. So one can just try all keys and print the message from each trial, the true messsage can be very easy to identify. We will show you how to do this in Python Today!