Basic Classic & Modern Cryptography Chapter 3 PDF

Chapter 3: CLASSICAL CRYPTOGRAPHY (SUBSTTUTION)  Chapter 3: CLASSICAL CRYPTOGRAPHY (SUBSTTUTION) “Security and safety were the reward of dullness” C.S.Lewis  Chapter 3: CLASSICAL ENCRYPTION (SUBSTTUTION)...

Chapter 3: CLASSICAL CRYPTOGRAPHY (SUBSTTUTION)  Chapter 3: CLASSICAL CRYPTOGRAPHY (SUBSTTUTION) “Security and safety were the reward of dullness” C.S.Lewis  Chapter 3: CLASSICAL ENCRYPTION (SUBSTTUTION) Objectives The learning objectives of this chapter are:  Understand the classical substitution cryptography.  Understand the monoalphabetic ciphers.  Understand cryptanalyze the monoalphabetic ciphers.  Understand the polyalphabetic ciphers.  Understand cryptanalyze the polyalphabetic ciphers.  Understand the polygrams ciphers.  Understand cryptanalyze the polygrams ciphers.  Understand the Homophonic ciphers.  Understand cryptanalyze the Homophonic ciphers. 3.1 INTRODUCTION Classical Cryptograph Substitution Transposition Product Cipher Cipher Cipher 3.1 INTRODUCTION Substitution ciphers are historical ciphers that encode unit (or units) called plaintext (letters, symbols…etc.) to replace it (or them) by another unit (or units) to produce ciphertext. Founded by the Roman ruler Julius Caesar (100 B.C. – 44 B.C.). He used it to protect messages of military significant and to secure communication. 3.2 MONOALPHABETIC CIPHERS Classical Cryptograph Substitution Cipher Monoalphabetic 3.2 MONOALPHABETIC CIPHERS Monoalphabetic ciphers are simple algorithms that replace a single unit (letter, symbol, … etc.) by another (letter, symbol, …etc.). o For example, if the encryption of “A” is “F” , then, every time we see “A” in the sentence, we replace it with “F”. 3.2.1 CAESAR CIPHER (SHIFT CIPHER) Classical Cryptograph Substitution Cipher Monoalphabetic Caesar Cipher 3.2.1 CAESAR CIPHER (SHIFT CIPHER) Caesar Cipher (shift cipher). It is the first historical cipher founded by Julius twenty five hundred years ago. o We simply shift every plaintext letter by a fixed number of positions to the right to produce a ciphertext. 3.2.1 CAESAR CIPHER (SHIFT CIPHER) Encoded letters of Caesar cipher associated with their numbers: A B C D E F G H I J K L M 0 1 2 3 4 5 6 7 8 9 10 11 12 N O P Q R S T U V W X Y Z 13 14 15 16 17 18 19 20 21 22 23 24 25  3.2.1 CAESAR CIPHER (SHIFT CIPHER) Example 3.1: Let us encrypt “MEET ME AT TWO PM”, and the shifting is by 3. In this case key k=3 Plaintext 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 0 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 Ciphertext D E F G H I J K L MN O P Q R S T U V W X Y Z A B C Message after encryption is “PHHWPHDWWZRSP” 3.2.1 CAESAR CIPHER (SHIFT CIPHER) Caesar cipher is expressed in the following mathematical relationship: 𝑪 = 𝑬 𝑷𝒊 = 𝑷𝒊 + 𝒌 𝒎𝒐𝒅 𝟐𝟔 𝒇𝒐𝒓 𝒆𝒏𝒄𝒓𝒚𝒑𝒕𝒊𝒐𝒏 𝑷 = 𝑫 𝑪𝒊 = 𝑪𝒊 − 𝒌 𝒎𝒐𝒅 𝟐𝟔 𝒇𝒐𝒓 𝒅𝒆𝒄𝒓𝒚𝒑𝒕𝒊𝒐𝒏 Where C is the ciphertext, P is the plaintext and k is the key.  3.2.1 CAESAR CIPHER (SHIFT CIPHER) Example 3.2: Using the mathematical expression, encrypt “ATTACK STARTS AT NOON” and the shifting is 15. In this case key k=15. Plaintext AB CDE F GH I J K L MN O P Q R S T U VWX Y Z 0 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 Message after encryption is …………………….. 3.2.1 CAESAR CIPHER (SHIFT CIPHER) We can decrypt Caesar cipher by inverse alphabet shift (shift every ciphertext letter by a fixed number of positions to the left to produce a plaintext). Example 3.3: Decrypt the message “PMTTWBPMZM”, and the inverse alphabet shift is 8 (in this case the inverse key k-1 = 8)  3.2.1 CAESAR CIPHER (SHIFT CIPHER) Solution: Plaintext AB CDE F GH I J K L MN O P Q R S T U VWX Y Z 0 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 Ciphertext I J K L MN O P Q R S T U V W X Y Z A B C D E F G H Now, it is easy to decrypt the message above to become, “HELLO THERE” 3.2.2 ROT13 CIPHER Classical Cryptograph Substitution Cipher Monoalphabetic Caesar ROT13 Cipher Cipher 3.2.2 ROT13 CIPHER ROT13 is another simple monoalphabetic substitution cipher that rotates/shifts the alphabet by 13 letters. It is an example of Ceasar cipher developed in ancient Rome.  3.2.2 ROT13 CIPHER Example 3.4: Using ROT13 cipher, encrypt the message “MEET ME AT TWO PM”. Plaintext AB CDE F GH I J K L MN O P Q R S T U VWX Y Z 0 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 Message after encryption is ……………………..  3.2.2 ROT13 CIPHER Example 3.5: Using ROT13 cipher, decrypt the message “URYYBGURER”. Plaintext AB CDE F GH I J K L MN O P Q R S T U VWX Y Z 0 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 Message after decryption is …………………….. 3.2.3 ATBASH CIPHER Classical Cryptograph Substitution Cipher Monoalphabetic Caesar ROT13 Atbash Cipher Cipher Cipher  3.2.3 ATBASH CIPHER Atbash Cipher is originally Hebrew alphabet and modified to English alphabets. The letters of the alphabet are reversed. Plaintext AB CDE F GH I J K L M NO P QR S T UV W X Y Z Ciphertext Z Y XWV U T S R Q P O N M L K J I H G F E D C B A 3.2.3 ATBASH CIPHER Example 3.6 Using Atbash cipher encrypt “MEET ME AT TWO PM”. What do we know about the key k? Plaintext AB C D E F GH I J K L M N O P QR S T UV W X Y Z Ciphertext Z Y X WVUT S RQPO N M L K J I HG F E D C B A Message after encryption is “NVVGNVZGGDLKN”  3.2.3 ATBASH CIPHER We can decrypt Atbash Cipher by inverse alphabet shift. Example 3.7 Using Atbash cipher decrypt “SVOOLGSVIV”. Plaintext A B C D E F GH I J K L MNOPQR S T UV W X Y Z Message after encryption is …………………….. 3.3 CRYPTANALYSIS OF MONO ALPHABETIC CIPHERS Are the monoalphabetic substitution ciphers secure in the presence of up to date CPUs? The answer is NO. Proof: Performing a brute force attack (claiming that we have no idea about the monoalphabetic cipher used).  We have 26 letters  26! ≈ 4 × 1026 possible keys.  So, breaking any monoalphabetic algorithm can be performed in seconds based on today's CPUs speed. 3.3 CRYPTANALYSIS OF MONO ALPHABETIC CIPHERS Letter frequency analysis is another practical attack. The brute force attack treats the cipher as a black box. Letter frequency attack analyze the internal structure of the cipher (we call it analytical attack as well). 3.3 CRYPTANALYSIS OF MONO ALPHABETIC CIPHERS Disadvantages of monoalphabetic ciphers: – Letter maps to the same letter each time. – The ciphertext will gain the English language redundancy characteristics. All the human languages have letter frequency redundancy but they are varies. 3.3 CRYPTANALYSIS OF MONO ALPHABETIC CIPHERS Fig. below shows that letters E, T, A, O,…etc has more redundancy than others.  3.3 CRYPTANALYSIS OF MONO ALPHABETIC CIPHERS Cryptanalysists can break monoalphabetic ciphers by: Structural attack technique 1) Count relative letter frequencies in the ciphertext. 2) Replacing the most frequent one (say X) with letter E. 3) Check how many shifts between E and X (the key). 4) Apply the decryption using the key founded in step (3). 5) If you didn’t get meaningful sentence use the second most frequent letter used and so on. 3.3 CRYPTANALYSIS OF MONO ALPHABETIC CIPHERS Example 3.8 Use frequency analysis to encrypt the given ciphertext: UFIMEPUEOXAEQPKQEFQDPMKFTMFEQHQDMXUZ RADYMXNGFPUDQOFOAZFMOFETMHQNQQZYMPQI UFTBAXUFUOMXDQBDQEQZFMFUHQEARFTQHUQF OAZSUZYAEOAI 3.3 CRYPTANALYSIS OF MONO ALPHABETIC CIPHERS Q is the most used letter. Letter Repetition Percentage Q 16 13.33% Assume that letter Q encoded from letter E. F 14 11.67% M 10 8.33% U 10 8.33% Number of shifts between E and Q is 12 E 9 7.50% A 8 6.67% Thus the key k=12 O 7 5.83% D 6 5.00% Apply decryption process with key =12. Z 6 5.00% P 5 4.17% Results: X 5 4.17% H 4 3.33% It was disclosed yesterday that several T I 4 3 3.33% 2.50% informal but direct contacts have been made Y 3 2.50% B 2 1.67% with political representatives of the vietcong in K 2 1.67% N 2 1.67% moscow R 2 1.67% G 1 0.83% S 1 0.83% 3.3 CRYPTANALYSIS OF MONO ALPHABETIC CIPHERS Can we use brute force attack to decrypt the previous message? – We need to try all 26 key shifts. – Check meaningful sentence for every decrypted message. – If we start from shift by 1 then we need to carry 12 attempts. – This can give you the difference in performance between structural attack and brute force attack. 3.4 POLYALPHABETIC CIPHER Classical Cryptograph Substitution Cipher Monoalphabetic Polyalphabetic Caesar ROT13 Atbash Cipher Cipher Cipher 3.4 POLYALPHABETIC CIPHER Polyalphabetic cipher is a method to improve the drawbacks of monoalphabetic ciphers. In polyalphabetic one letter can be mapped to different cliphertexts, where monoalphabetic maps one letter to the same cliphertexts every time. 3.4.1 SIMPLE SHIFT VIGENERE CIPHER Classical Cryptograph Substitution Cipher Monoalphabetic Polyalphabetic S.H. Vigenere Caesar Cipher ROT13 Cipher Atbash Cipher Cipher 3.4.1 SIMPLE SHIFT VIGENERE CIPHER It shifts the first letter of the plaintext by n numbers. Then, it shifts the second letter of the plaintext by s number. It continues this process until it shift all the plaintext letters by different shifts values producing a ciphertext. The key length is key k used to indicate the shifting value for each letter. 3.4.1 SIMPLE SHIFT VIGENERE CIPHER Example 3.9: Using the keys and plaintext table below, encrypt the message “STAY ALIVE” using simple shift vigenere cipher. Plaintext S T A Y A L I V E Key Length 5 10 2 9 13 5 4 3 0 Ciphertext 3.4.1 SIMPLE SHIFT VIGENERE CIPHER The first letter s is encrypted by shifting by 5  x Then, we encrypt the second letter t by shifting by 10  d We continue this process until we finish the sentence. Plaintext S T A Y A L I V E Key Length 5 10 2 9 13 5 4 3 0 Ciphertext X D C H N Q M Y E 3.4.1 SIMPLE SHIFT VIGENERE CIPHER We can decrypt simple shift Vigenere cipher by using the frequency analysis (as explained earlier in section 3.3) in case if we do not know the key length. Example 3.10: Decrypt the message “XJXLIOP” using the key length “5 9 2 7 1 6 3”. Ciphertext X J X L I O P Key Length 5 9 2 7 1 6 3 Plaintext 3.4.2 FULL VIGENERE CIPHER Classical Cryptograph Substitution Cipher Monoalphabetic Polyalphabetic S.H. Vigenere Full Vigenere Caesar Cipher ROT13 Cipher Atbash Cipher Cipher Cipher 3.4.2 FULL VIGENERE CIPHER Full Vigenere cipher is a polyalphabetic substitution cipher considered as multiple Caesar ciphers adding the usage of a keyword and a table called tableau. Proposed by Blaise de Vigenere from the Henry III of France in the 16th century. Tableau 3.4.2 FULL VIGENERE CIPHER The first row is Caesar Cipher shift of 0, the second row is shift by 1, and the last row is shift by 25. Example 3.11 Encrypt “BE THERE ON TIME” using the keyword is “DECEPTIVE”. Step1. write the keyword “DECEPTIVE” a long the row of the table. Keyword D E C E P T I V E D E C E Plaintext B E T H E R E O N T I M E 3.4.2 FULL VIGENERE CIPHER Step2. find the first letter of the keyword in the first column of Tableau. Step3. find the first letter of the plaintext in the first row of Tableau. Step4. find the intersection between them (this is the ciphertext). Keyword D E C E P T I V E D E C E Plaintext B E T H E R E O N T I M E Ciphertext E I V L T K M J R W M O I Tableau 3.4.2 FULL VIGENERE CIPHER Full Vigenere cipher can be decrypted by using the frequency analysis method in case if we do not know the keyword. Steps to decrypt the full Vigenere cipher using the Vigenere tableau: Step1. write the keyword a long the row of the table. Step2. use the keyword letter to pick a column of the Tableau. Step3. trace down the column to the row containing the ciphertext letter. Step4. the index of that row is the plaintext letter. 3.4.2 FULL VIGENERE CIPHER Example 3.12 Decrypt the message “UVRSVVLQ” using the keyword “CODE”. Keyword C O D E C O D E Ciphertext U V R S V V L Q Plaintext S H O O T H I M Tableau 3.4.3 AUTO-KEY VIGENERE CIPHER Classical Cryptograph Substitution Cipher Monoalphabetic Polyalphabetic S.H. Vigenere Full Vigenere Auto-key Caesar Atbash ROT13 Cipher Vigenere Cipher Cipher Cipher Cipher Cipher 3.4.3 AUTO-KEY VIGENERE CIPHER Auto-keyword Vigenere cipher It was invented by Blasie de Vigenere. It is identical method of full Vigenere cipher but uses different scheme of obtaining the ciphertext. The keyword should be known previously by the two end parties.  The keyword structure is illustrated below: Keyword letters OR Keyword letters + First letters of the message 3.4.3 AUTO-KEY VIGENERE CIPHER Example 3.13: Encrypt the message “WELCOME”, using the keyword “KNOW”, we will obtain the following table: Keyword K N O W W E L Plaintext W E L C O M E Ciphertext G R Z Y K Q P 3.4.3 AUTO-KEY VIGENERE CIPHER Auto-key Vigenere cipher can be decrypted using the frequency analysis method in case if we do not know the keyword. It also can be decrypted using the Vigenere table (in case if we know the keyword) as we did with Full Vigenere Cipher. In case the ciphertext is longer than the keyword:  First, decrypt part of the ciphertext until obtaining some letters from the plaintext.  Then, add the decrypted letters to the plaintext to complete the table. 3.4.3 AUTO-KEY VIGENERE CIPHER Example 3.14: Decrypt the message “WPVXHK” using the keyword “DIE”, note that, you have to use the first plaintext you have decrypted to complete the keyword, looking at the 3.2 Table, the following table is obtained: Keyword D I E T H R Ciphertext W P V X H K Plaintext T H R E A T 3.4.4 RUNNING KEY VIGENERE CIPHER Classical Cryptograph Substitution Cipher Monoalphabetic Polyalphabetic S.H. Auto-key Running Key Caesar ROT13 Atbash Full Vigenere Vigenere Vigenere Vigenere Cipher Cipher Cipher Cipher Cipher Cipher Cipher 3.4.4 RUNNING KEY VIGENERE CIPHER The running key Vigenere cipher has the same internal working as the Vigenere cipher (difference lies in the keyword used). It uses very long keyword chosen previously by the two end parties.  The keyword should not be repeated and is used only one time, making the cryptanalysis more difficult.  E.g., a sentence is chosen only one time from a public book. 3.4.4 RUNNING KEY VIGENERE CIPHER Example 3.15: Encrypt the message “GET READY”, using the keyword “MOHAMMAD PEACE BE UPON HIM” Referring to Vigenere Tableau we get: Keyword M O H A M M A D Plaintext G E T R E A D Y Ciphertext S S A R Q M D B Tableau 3.4.4 RUNNING KEY VIGENERE CIPHER Decryption of the running key Vigenere cipher can be done using:  Frequency analysis (in case if we do not know the keyword).  The Vigenere table (in case if we know the keyword). Example 3.16: Decrypt the message “HHPDQOFHD” using the keyword “How dose the duck know that? Said victor”. 3.4.4 RUNNING KEY VIGENERE CIPHER Keyword H O W D O E S T H Ciphertext H H P D Q O F H D Plaintext A T T A C K N O W Tableau 3.5 CRYPTANALYSIS OF POLYALPHABETIC The security and complexity are increased using polyalphabetic ciphers compared to monoalphabetic cipher. Brute force and letter frequency analysis attacks are applicable to any cipher. It takes more time to attack polyalphabetic cipher than monoalphabetic cipher using the above techniques. 3.6 POLYGRAM CIPHERS Classical Cryptograph Substitution Cipher Monoalphabetic Polyalphabetic Polygram S.H. Auto-key Running Key Caesar ROT13 Atbash Full Vigenere Vigenere Vigenere Vigenerer 3.6 POLYGRAM CIPHERS Polygrams ciphers (or polygraphic ciphers) are a uniform substitution ciphers that encrypt a block of letters. Sequences of two plaintext characters (digrams/digraphs) can be replaced by other digrams/digraphs. 3.6.1 THE PLAYFAIR CIPHER Classical Cryptograph Substitution Cipher Monoalphabetic Polyalphabetic Polygram Running S.H. Full Auto-key Caesar ROT13 Atbash Key Playfair Vigenere Vigenere Vigenere Vigenere 3.6.1 THE PLAYFAIR CIPHER The Playfair cipher is the first digraph substitution cipher, It encrypts pairs of letters (digraph) instead of single letter. Invented in 1854 by Charles Wheatstone and named after his friend Baron Playfair. 3.6.1 THE PLAYFAIR CIPHER The encryption technique: 1) Break the message into two letters (pair) chunks. 2) For each pair separate repeated letters by an X and regroup. 3) If odd number of letters, append extra X to the last pair. 4) Create a 5 x 5 array including a keyword k. 5) Encrypt the message using the created array. 3.6.1 THE PLAYFAIR CIPHER How to create the 5 x 5 array: 1) Remove duplicated letters from the keyword k to be knew. 2) Fill the array with the keyword knew starting from top left to right. 3) For the rest of the entries in the array, add the remaining letters of the alphabet in sequence. Note: to reduce the alphabet to fit the array you can either omit "Q" or replace "J" with "I“. 3.6.1 THE PLAYFAIR CIPHER How to use the array to encrypt the message: 1. Each pair of letters is encrypted based on which of the following is applicable: Case-1: The two letters are not in the same row or column of the array  replace each letter with the letter in its row that is in the column of the other letter. 3.6.1 THE PLAYFAIR CIPHER Case-2: The two letters are in the same row  replace each letter with the letter to its immediate right. If the letter is on most right  cycle back to the beginning of the row. 3.6.1 THE PLAYFAIR CIPHER Case-3: The two letters are in the same column  replace each letter with the letter immediately below it. If the letter is last on the bottom  cycle back to the top of the column. 3.6.1 THE PLAYFAIR CIPHER Example 3.17: Encrypt the message “target”, using the keyword “cipher”. Table creation 3.6.1 THE PLAYFAIR CIPHER Breaking the message “TARGET”: TA RG ET The ciphertext is “QDGOHU” for the word “TARGET” 3.6.1 THE PLAYFAIR CIPHER The decryption technique:  Follow the same process but using the opposite move directions for case-2 and case-3. Example 3.18:  Decrypt the message “ADMA” using the keyword “SAVE”. Decrypted message “WAKE” 3.6.2 JIFFERSON CYLINDER (THE BAZERIES CYLINDER) Invented by Thomas Jefferson in 1795, the wheel cipher, better known as the bazeries cylinder, was one of the first forms of a cryptographic machin. Invented by Thomas Jefferson in 1795, the wheel cipher, better known as the bazeries cylinder, was one of the first forms of a cryptographic maching. 3.6.2 JIFFERSON CYLINDER (THE BAZERIES CYLINDER) The structure of the Bazeries Cylinder is very basic. A randomized alphabet is printed on the outside edge of a circular disk. 3.6.2 JIFFERSON CYLINDER (THE BAZERIES CYLINDER) Every individual disk is marked as a specific number that indicates which order the letters appear. Each disk is then stacked upon a center, usually iron, axle (barr). The order in which these disks is then stacked is up to the discretion of the person who is encrypting the message. These rotatable disks are then free to form whatever message the beholder has as long as the message’s length dose not exceed the number of disk on the cylinders (Bruff, 2010). 3.7 CRYPTANALYSIS OF POLYGRAM CIPHERS Polygram ciphers proved to be much more secure than monoalphabetic and polyalphabetic ciphers. It is an improved scheme over monoalphabetic and significantly easier in usage over polyalphabetic. The digraph substitution ciphers (ex, Playfair cipher) are susceptible to frequency analysis attack, where the trigraph, quadgraph and more pairs of letters ciphers thwart the frequency analysis attack.  3.8 HOMOPHONIC CIPHERS Classical Cryptograph Substitution Cipher Monoalphabetic Polyalphabetic Polygram Homophonic Running S.H. Full Auto-key Caesar ROT13 Atbash Key Playfair Vigenere Vigenere Vigenere Vigenere 3.8 HOMOPHONIC CIPHERS Homophonic ciphers are substitution ciphers in which a single letter of the plaintext can be replaced with, for example, 5 different letters, numbers, symbols or combination of them. A table of homophones is required for both sender and receiver in order to encrypt and decrypt the message. The characters with higher frequency appearance can have several possible replacements. 3.8 HOMOPHONIC CIPHERS The following represents a sample table of homophones. 3.8 HOMOPHONIC CIPHERS Example 3.19 Encrypt the message “SAVE ME” using the homophones table. Solution: we find that “S” has many choices of encryption, for example “R” and “4”, we can choose any one. - Continue the same process for all letters, the ciphertext is: plaintext S A V E M E ciphertext 4 D 8 Z # $ 3.8 HOMOPHONIC CIPHERS We can decrypt the homophonic cipher by reversing the steps of the encryption process. Example 3.20: Decrypt the message below using homophonic cipher. W3as4F?U8XXJF What is the plaintext? 3.9 CRYPTANALYSIS OF HOMOPHONIC CIPHERS Breaking the homophonic cipher is very difficult if the number of the cipher alphabet for each letter is high. We need to know how many letters, symbols and numbers are mapped to each letter which is called hill climbing. By hand, it takes long time to break. Using computers, it may take few minutes or second depends on how many letters, symbols and numbers are mapped to each letter. 3.9 CRYPTANALYSIS OF HOMOPHONIC CIPHERS This is handled creating two nested hill climbing layers. The outer layer determine how many letters, symbols and number are mapped to each letter and inner layer to determine the correct and exact letter, symbol or number that is mapped to that letter particularly.