FINALS_Cryptography and Modular Arithmetic.pptx

Mathematics in the modern world for cryptography and modular arithmetic

1. CRYPTOGRAPHY Originated from two greek word such as KRYPTO which means hidden and GRAPHENE means writing. Method of making and breaking of secret codes. It uses two processes such as encryption and decryption.

2. Encryption Is the process of transforming plain text into code form using a certain algorithm. Ex: PDWK LV IXQ Decryption Is the process of returning/converting back the coded message into plain text. Ex: Math is fun Key -refer to the strings of information that is used to reveal the encrypted message into readable form. Ex: Original: Maps to: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

3. DIFFERENT TYPES OF CRYPTOGRAPHY 1. Secret (Symmetric) Key Cryptography Uses single key for both encryption and decryption. 2. Public key (Asymmetric) Cryptography Uses two keys, one for encryption and other for decryption. 3. Hash Functions Also called message digests and one-way encryption Use no key 4. Trust Models Secure use of cryptography requires trust.

4. SIMPLE METHODS OF CRYPTOGRAPHY Shift Cipher ( Ceasar Cipher) Is the simple type of substitution cipher Uses shift in forming the key of cryptography Cipher text is obtained from taking an equivalent of a single letter of the alphabet to another letter by doing a uniform number of shifts either left or right. Each letter of the English alphabet should be matched exactly to one letter of the cipher alphabet.

5. ILLUSTRATIONS: Using a shift of 3 to the right (the commonly used number of shifts) Take note: 1 st line of letters are the English Alphabet while the letters on the 2 nd row are the equivalent cipher character/alphabet. Encrypt Message: Ex: CRYPTOGRAPHY FUBSWRJUDSKB Encrypt the message: Ex: GOD IS GOOD A B C D E F G H I J K L M N O P Q R S T U V W X Y Z D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

6. BLOCK CIPHER MODES OF OPERATION Block Cipher Is an encryption algorithm which takes fixed size of input say b bits and produces a ciphertext of b bits again. Electronic Code Book (ECB)- Is the easiest block cipher mode of functioning. Cipher Block Chaining (CBC)- Is an advancement made on ECB since ECB compromises some security requirements. Cipher Feedback Mode (CFB)- This mode the cipher is given as feedback to the next block of encryption. Output Feedback Mode- follows nearly same process as the Cipher Feedback mode except that it sends the encrypted output as feedback instead of the actual cipher which is XOR input. Counter Mode- or CTR is a simple counter based block cipher implementation.

7. USING A MODULO OPERATIONS To encrypt the message: Express the letters of the alphabet into an integer from 0 to 25, that matches its order, for example A=O, B=1, C=2 …., then label them as C Calculate Y=(C+K) mod 26, for every letter of the message. Convert the number Y into a letter following the order of the letter of the alphabet. Illustration: Encrypt the message “MMW is fun to learn” Let K=5 Step 1. M=12, W=22, I=8, S=18, F=5, U=20, N=13, T=19, O=14, L=11, E=4, A=O, R=17, N=13 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

8. Step 2. TOTAL Y= (17 17 27 13 23 10 25 18 24 19 16 9 5 22 18) mod26. Y= 17 17 1 13 23 10 25 18 24 19 16 9 5 22 18 Step 3. RRB NX KZS YT QJFWS ENCRYPTED MESSAGE M M W I S F U N T O L E A R N 12 12 22 8 18 5 20 13 19 14 11 4 17 13 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 17 17 27 13 23 10 25 18 24 19 16 9 5 22 18

9. To Decrypt the Message: 1. Express the letters of the alphabet into an integer from 0 to 25, that matches its order, for example A=0, B=1, C=3……, then label them as Y 2. Calculate C=(Y-K) mod 26, for every letter of the decrypted message 3. Convert the number C into a letter following the order of the letter of the alphabet. Illustration: Decrypt the cipher text RRB NX KZS YT QJFWS Let K=5 Step 1 R=17, B=1, N=13, X=23, K=10, Z=25, S=18, Y=24, T=19, Q=16, J=9, F=5, W=22 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

10. Step 2 Total C= ( 12 12 -4 18 5 20 13 19 14 11 4 0 17 13) mod 26 C= 12 12 22 8 18 5 20 13 19 14 11 4 0 17 13 Step 3 MMW IS FUN TO LEARN DECRYPTED MESSAGE R R B N X K Z S Y T Q J F W S 17 17 1 13 23 10 25 18 24 19 16 9 5 22 18 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 12 12 -4 8 18 5 20 13 19 14 11 4 17 13

11. 3. Encrypt the word “FATIMA” using the MODULO Operator, given K=20 Step 1 F=5, A=0, T=19, I=8, M=12 Step 2 Y= (25 20 39 28 32 20) mod 26 Y= 25 20 13 2 6 20 Step 3 ZUNCGU ENCRYPTED MESSAGE A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 F A T I M A 5 19 8 12 20 20 20 20 20 20 25 20 39 28 32 20

12. MODULAR ARITHMETIC It is the arithmetic of congruences , sometimes known informally as "clock arithmetic." In modular arithmetic, numbers "wrap around" upon reaching a given fixed quantity, which is known as the modulus (which would be 12 in the case of hours on a clock, or 60 in the case of minutes or seconds on a clock).

13. MODULAR ARITHMETIC Also known Clock Arithmetic It is an operator (mod), which seeks for a remainder when two numbers are divided. It is denoted by the symbol K mod M=r (which read as K modulo M equals r)

14. How to calculate the Arithmetic Modulo? Let K and M are any positive integers Divide k by the value of M to obtain the quotient (q) and the remainder (r) Such that k= Mq + r, 0 < r < M Examples: 1. Find 15 mod 6 = ; 15 mod 6 = 3 Solution: 15 6=2 remainder 3, hence 15 mod 6=3 Checking: k= Mq+3, where k=15, M=6, q=2, and r=3 15=6*2 +3 15=12+3 15=15 2. 41 mod 30 = 11 3. 45 mod 30 = 15

15. 2. Solve 8 mod 10 8 mod 10 = 8 8/10=0 remainder 8, hence, 8 mod 10=8 Checking: k= Mq +3, where k=8, M=10, q=0, and r=8 8=10*0 +8 8=8 B. Let k be any negative integer and M is positive integer. Divide /k/ by the value of M to obtained the r’, (r’= 0) Therefore, r=M-r’ Example: Evaluate -6 mod 4 = /-6/ 4 =1 remainder 2, r’-=2 r=4–2=2 ,hence -6 mod 4=2

16. a+ K mod M 1. . 6+ 5 mod 4 11 mod 4 = 3 2. ) 10 - 5 mod 4 5 mod 4 = 1 3) 6 * 3 mod 7 = 4