Basic Encryption and Decryption I PDF

CHAPTER 2 Basic Encryption and Decryption (I) Dr. Sayed El-Sayed  Cryptography Cryptography is a branch of mathematics that deals with the transformation of data. Cryptographic algorithms are used in many ways in information security and network security. Cr...

CHAPTER 2 Basic Encryption and Decryption (I) Dr. Sayed El-Sayed  Cryptography Cryptography is a branch of mathematics that deals with the transformation of data. Cryptographic algorithms are used in many ways in information security and network security. Cryptography is an essential component in the secure storage and transmission of data, and in the secure interaction between parties. 2  Cryptographic algorithms Cryptographic algorithms can be divided into three categories → : Keyless: Do not use any keys during cryptographic transformations. Example: Cryptographic Hash Function Single-key: The result of a transformation is a function of the input data and a single key, known as a secret key. Two-key: At various stages of the calculation, two different but related keys are used, referred to as a private key and a public key. In this chapter we will cover single-key (referred to as symmetric encryption, or conventional encryption) 3  Definitions We describe the process of encoding a message so its meaning is not obvious as encryption. Plaintext: The original message Ciphertext: The coded message Encryption: The process of converting from plaintext to ciphertext. Also called Enciphering. Decryption: Restoring the plaintext from the ciphertext. Also called Deciphering 4  Definitions (cont’ed) Cryptography – The area of study of the many schemes used for encryption (hidden writing) Cryptographic system (cryptosystem)/cipher – A scheme for encryption and decryption Cryptanalysis – Techniques used for deciphering a message without any knowledge of the enciphering details – The person practicing cryptanalysis is called a Cryptanalyst Cryptology – The areas of cryptography and cryptanalysis 5  Definitions (cont’ed) Cryptographic Hash Function – The most basic type of cryptographic algorithm is a one-way hash algorithm. – A hash algorithm creates a unique “digital fingerprint” of a set of data and is commonly called hashing. This fingerprint, called a digest (sometimes called a message digest or hash), represents the contents. – The purpose of a hashing algorithm is NOT to create ciphertext that can later be decrypted. Instead, hashing is “one-way”: its contents cannot be used to reveal the original set of data. Hashing is used primarily for comparison purposes. A secure hash that is created from a set of data cannot be reversed. – A hashing algorithm is secure if it has these characteristics: Fixed size, Unique, Original, and Secure. 6  Simplified Model of Symmetric Encryption There are two requirements for secure use of conventional encryption: A strong encryption algorithm Sender and receiver must have obtained copies of the secret key in a secure fashion and must keep the key secure 7 Model of Symmetric Cryptosystem 8  Cryptographic Systems Are characterized along three independent dimensions: The type of operations used for transforming plaintext to ciphertext – Substitution – Transposition – Product (involve multiple stages of substitutions and transpositions) The number of keys used – Symmetric (i.e., single-key, secret-key, conventional encryption) – Asymmetric (i.e. two-key, or public-key encryption) The way in which the plaintext is processed – Block cipher (processes the input one block of elements at a time, producing an output block for each input block. ) – Stream cipher (processes the input elements continuously, producing output one element at a time, as it goes along) 9  Cryptanalysis and Brute-Force Attack The objective of attacking an encryption system is to recover the key rather than recovering the plaintext. There are two general approaches: Cryptanalysis – Attack relies on the nature of the algorithm plus some knowledge of the general characteristics of the plaintext – Attack exploits the characteristics of the algorithm to attempt to deduce a specific plaintext or to deduce the key being used Brute-force attack – Attacker tries every possible key on a piece of ciphertext until an intelligible translation into plaintext is obtained – On average, half of all possible keys must be tried to achieve success 10  Types of Attacks on Encrypted Messages Type of Attack Known to Cryptanalyst Ciphertext Only Encryption algorithm Ciphertext Known Plaintext Encryption algorithm Ciphertext One or more plaintext–ciphertext pairs formed with the secret key Chosen Plaintext Encryption algorithm Ciphertext Plaintext message chosen by cryptanalyst, together with its corresponding ciphertext generated with the secret key Chosen Ciphertext Encryption algorithm Ciphertext Ciphertext chosen by cryptanalyst, together with its corresponding decrypted plaintext generated with the secret key Chosen Text Encryption algorithm Ciphertext Plaintext message chosen by cryptanalyst, together with its corresponding ciphertext generated with the secret key Ciphertext chosen by cryptanalyst, together with its corresponding decrypted plaintext generated with the secret key 11  Encryption Scheme Security Unconditionally secure – No matter how much time an opponent has, it is impossible for him or her to decrypt the ciphertext simply because the required information is not there Computationally secure – The cost of breaking the cipher exceeds the value of the encrypted information – The time required to break the cipher exceeds the useful lifetime of the information 12  Brute-Force Attack Involves trying every possible key until an intelligible translation of the ciphertext into plaintext is obtained On average, half of all possible keys must be tried to achieve success To supplement the brute-force approach, some degree of knowledge about the expected plaintext is needed, and some means of automatically distinguishing plaintext from garble is also needed 13  Strong Encryption The term strong encryption refers to encryption schemes that make it impractically difficult for unauthorized persons or systems to gain access to plaintext that has been encrypted Properties that make an encryption algorithm strong are: – Appropriate choice of cryptographic algorithm – Use of sufficiently long key lengths – Appropriate choice of protocols – A well-engineered implementation – Absence of deliberately introduced hidden flaws 14  Encryption Algorithms Plaintext Ciphertext Original Plaintext Encryption Decryption Encoding: the process of translating entire words or phrases to other words or phrases. Enciphering: the process of translating letters or symbols individually. Encryption: is the group of term that covers both encoding and enciphering. 15  Encryption Algorithms There are 2 types of encryptions: – Symmetric Encryption: uses same key for encryption and decryption process. – To encrypt: C = E(P, K) – To decrypt: P = D (E(P,K), K) Key Original Plaintext Ciphertext Plaintext Encryption Decryption 16  Encryption Algorithms – Asymmetric Encryption: uses different keys for encryption and decryption process. – To encrypt: C = E (P, KE) – To decrypt: P = D (E (P, KE), KD) Encryption Key Decryption Key (KE) (KD) Original Plaintext Ciphertext Plaintext Encryption Decryption 17  Substitution Technique Is one in which the letters of plaintext are replaced by other letters or by numbers or symbols If the plaintext is viewed as a sequence of bits, then substitution involves replacing plaintext bit patterns with ciphertext bit patterns 18  Caesar Cipher Simplest and earliest known use of a substitution cipher Used by Julius Caesar First attested use in military affairs Involves replacing each letter of the alphabet with the letter standing three places further down the alphabet Alphabet is wrapped around so that the letter following Z is A Advantage: easy to remember Disadvantage: easy to predict pattern of encryption plaintext: meet me after the toga party (Lowercase) ciphertext: PHHW PH DIWHU WKH WRJD SDUWB (Uppercase) Tool for Caesar cipher: http://www.ti89.com/cryptotut/caesar3.htm 19  Caesar Cipher Algorithm Can define transformation as: 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 Mathematically give each letter a number 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 Algorithm can be expressed as: c = E(3, p) = (p + 3) mod (26) A shift may be of any amount, so the general Caesar algorithm is: C = E(k , p ) = (p + k ) mod 26 Where k takes on a value in the range 1 to 25; Decryption algorithm is simply: p = D(k , C ) = (C − k ) mod 26 20  The Caesar Cipher – Example1 Plaintext: meet me; Key, k=3 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 Numerical Encrypt as Plaintext Represent- Ciphertext (pi+k) mod 26 ation, pi m 12 (12+3) mod 26 = 15 mod 26 = 15 P e 4 (4+3) mod 26 = 7 mod 26 = 7 H e 4 (4+3) mod 26 = 7 mod 26 = 7 H t 19 (19+3) mod 26 = 22 mod 26 = 22 W m 12 (12+3) mod 26 = 15 mod 26 = 15 P e 4 (4+3) mod 26 = 7 mod 26 = 7 H Ciphertext: PHHW PH 21  The Caesar Cipher – change the key Plaintext: meet me; Key, k=9 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 Numerical Encrypt as Plaintext Represent- Ciphertext (pi+k) mod 26 ation, pi m 12 (12+9) mod 26 = 21 mod 26 = 21 V e 4 (4+9) mod 26 = 13 mod 26 = 13 N e 4 (4+9) mod 26 = 13 mod 26 = 13 N t 19 (19+9) mod 26 = 28 mod 26 = 2 C m 12 (12+9) mod 26 = 21 mod 26 = 21 V e 4 (4+9) mod 26 = 13 mod 26 = 13 N Ciphertext: VNNC VN 22  The Caesar Cipher – Decryption Ciphertext: VNNC VN; Key, k=9 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 Numerical Decrypt as Ciphertext Represent- Plaintext (pi-k) mod 26 ation, pi V 21 (21-9) mod 26 = 12 mod 26 = 12 m N 13 (13-9) mod 26 = 4 mod 26 = 4 e N 13 (13-9) mod 26 = 4 mod 26 = 4 e C 2 (2-9) mod 26 = -7 mod 26 = -7+26=19 t V 21 (21-9) mod 26 = 12 mod 26 =12 m N 13 (13-9) mod 26 = 4 mod 26 = 4 e Plaintext: meet me 23  The Caesar Cipher – More examples Example: (k = 19) 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 T U V W X Y Z A B C D E F G H I J K L M N O P Q R S – Plaintext: security – Ciphertext: LXVNKBMR 24  Brute-Force Cryptanalysis of Caesar Cipher Only have 25 possible ciphers – A maps to B,C,...,Z Could simply try each in turn A brute force search- try every possible key on a piece of ciphertext until an intelligible translation into plaintext is obtained – given ciphertext, just try all shifts of letters – do need to recognize when have plaintext E.g. break ciphertext "GCUA VQ DTGCM" 25  Monoalphabetic Cipher With only 25 possible keys, the Caesar cipher is far from secure. A dramatic increase in the key space can be achieved by allowing an arbitrary substitution, such as permutations of the alphabet. A permutation of a finite set S is an ordered sequence of all the elements of S, with each element appearing exactly once. – For example, if S = {a, b, c}, there are six permutations of S: {a,b,c}, {a,c,b}, {b,a,c}, {b,c,a}, {c,a,b}, and {c,b,a} – In general, there are n! permutations of a set of n elements. If the “cipher” line can be any permutation of the 26 alphabetic characters, then there are 26! possible keys (greater than 4 x 1026) – This approach is referred to as a monoalphabetic substitution cipher because a single cipher alphabet is used per message (i.e., always uses the same letter of the alphabet for the ciphertext letter)  Cryptanalysis Based on Relative Frequencies of Letters The Arabs were the first to make significant advances in cryptanalysis. An Arabic author, Qalqashandi, wrote down a technique for solving ciphers, which is still used today. The line of attack is based on the nature of the plaintext (e.g., non- compressed English text) The technique is to write down all the ciphertext letters and count the frequency of each symbol. Using the average frequency of each letter of the language, the plaintext can be written out. 27 Relative Frequency of Letters in English Text The analyst exploits the regularities of the language. – Assume the ciphertext to be solved is UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ – As a first step, the relative frequency of the letters can be determined and compared to a standard frequency distribution for English. For long messages, this technique alone might be sufficient, but because this is a short message, we cannot expect an exact match. – The relative frequencies of the letters in the ciphertext (in %ages) are as follows: P 13.33 H 5.83 F 3.33 B 1.67 C 0.00 Z 11.67 D 5.00 W 3.33 G 1.67 K 0.00 S 8.33 E 5.00 Q 2.50 Y 1.67 L 0.00 U 8.33 V 4.17 T 2.50 I 0.83 N 0.00 O 7.50 X 4.17 A 1.67 J 0.83 R 0.00 M 6.67 Comparing ciphertext letters’ frequencies with left Figure, what are the equivalents of the ciphertext letters P and Z? 28  Substitution using Key Phrase The Key Phrase (or keyword) is a simple substitution cipher (monoalphabetic cipher) which uses a key phrase to mix the letters to generate the cipher alphabet. – The plaintext is written retaining word divisions and each letter is substituted by the letter in the key phrase. Key Phrase must contain unique letters. Any redundancy must be removed before encrypting. Example: If the key phrase is BOM, the shifted key are as follows: Plaintext: a b c d e f g h i j k l m n o p... Ciphertext: B O M A C D E F G H I J K L N P.. Have the same strength as the previous simple substitution ciphers. 29  Substitution using Key Phrase: Example Example: – Key phrase: SPECTACULAR (key must not contain redundant letters so drop C and A), and therefore key phrase becomes SPECTAULR –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 –S P E C T A U L R B D F G H I J K M N O Q V W X Y Z Do you think it is a problem that there are 5 collisions (i.e., a plaintext letter being substituted for itself) in this substitution? (Answer: It depends.) Perhaps a better key phrase is EZRA CORNELL (why): 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 Ciphertext: E Z R A C O N L B D F G H I J K M P Q S T U V W X Y 30  Substitution using a Key Phrase and a Matrix To strengthen key phrase substitution, apply a matrix in which the letters from the key phrase form the headings of the columns, and the remaining letters of the alphabet fill in order in the rows below. Mixing is achieved by transcribing columns. : Example: Key Phrase is CINCIN C I N A B D ✓ Notice that 5x6 matrix is used (i.e., 5 E F G H J K rows by 6 columns. L M O P Q R S T U V W X ✓ We can use other formats, such as a Y Z 6x5 matrix. PT: 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 CT: C E L S Y I F M T Z N G O U A H P V B J Q W D K R X 31  Multiplicative Ciphers (Monoalphabetic Substitutions) Encryption f(a) = a*k mod n, where k and n are relatively prime [GCD(k,n)=1] so that the letters of the alphabet produced a complete set of residues. If k and n are not relatively prime, several plaintext will encrypt to the same ciphertext letter and not all letter will appear in the ciphertext alphabet e.g. if k = 12 and n =26. – Example: If k = 12 Plaintext ABC DEF GHI JKL MNO PQR STU VWX YZ Ciphertext = AMY KWI UJS EQC OAM YKW IUA SEQ CO eg. BOM → MMO Decryption To decrypt a message encrypted with a Multiplicative Cipher, multiply the ciphertext number by the multiplicative inverse of the key mod 26 [= ci*k-1 mod 26] 32  Table of Multiplication modulo 26 Only 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, and 25 have multiplicative inverses mod26 33  Multiplicative Cipher – Encryption example Plaintext: meet me; Key, k=7 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 Numerical Encrypt as Plaintext Represent- Ciphertext (pi*k) mod 26 ation, pi m 12 (12*7) mod 26 = 84 mod 26 = 6 G e 4 (4*7) mod 26 = 28 mod 26 = 2 C e 4 (4*7) mod 26 = 28 mod 26 = 2 C t 19 (19*7) mod 26 = 133 mod 26 = 3 D m 12 (12*7) mod 26 = 84 mod 26 = 6 G e 4 (4*7) mod 26 = 28 mod 26 = 2 C Ciphertext: GCCD GC 34  Multiplicative Cipher – Decryption example Ciphertext: GCCD GC; Key, k=7, k-1 mod 26 = 15 (see slides back) 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 Numerical Decrypt as Ciphertext Represent- Plaintext (pi*k-1) mod 26 ation, pi G 6 (6*15) mod 26 = 90 mod 26 = 12 m C 2 (2*15) mod 26 = 30 mod 26 = 4 e C 2 (2*15) mod 26 = 30 mod 26 = 4 e D 3 (3*15) mod 26 = 45 mod 26 = 19 t G 6 (6*15) mod 26 = 90 mod 26 = 12 m C 2 (2*15) mod 26 = 30 mod 26 = 4 e Plaintext: meet me 35  Cryptanalysis of the Caesar Cipher Suppose you were trying to break the following ciphertext: WKLV PHVVDJH LV QRW WRR KDUG WR EUHDN It is not so difficult to break the ciphertext above by doing some analysis on it. How? 1) Start on the weak points: blank is translated to itself! 2) In English there are relatively few small words like; am, is, be, he, we, and, are, you, she etc… Therefore, one attack can start off by substituting known short words at appropriates places. 3) Look for repetition and patterns. Example: If WRR is TOO, then WR would be TO (more sense compared to SEE) WKLV PHVVDJH LV QRW WRR KDUG WR EUHDN T--- ------- -- -OT TOO ---- TO ----- (If Q is N, -OT is likely to be NOT) The word LV appears in WKLV. If LV is IS then WKLV would be THIS THIS --SS--- IS NOT TOO ---- TO ----- By now, we should be able to figure out the plaintext is: this message is not too hard to break 36  Polyalphabetic Substitution Ciphers The weakness of monoalphabetic ciphers - frequency distribution reflects the distribution of the underlying alphabet. Solution : flatten the distribution : use polyalphabetic substitution How to flatten the distribution? – combine both high and low distributions. If E1 (T) = a and E2 (T) = b E1 (X) = a and E2 (X) = b T & X – plaintext 37 Flat distribution of ciphertext ‘a’ and ‘b’ 38  Polyalphabetic Substitution Ciphers We can also combine two distributions by using two separate encryption alphabets ✓ the first is for all characters in odd positions of the plaintext ✓ the second is for all the characters in even positions. Consider the two encryption algorithms below: Table for Odd Position  1( ) = (3 *  ) mod 26 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 A D G J M P S V Y B E H K N Q T W Z C F I L O R U X Table for Even Position  2( ) = ((5 *  ) + 13) mod 26 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 N S X C H M R W B G L Q V A F K P U Z E J O T Y D I 39  Polyalphabetic Substitution Ciphers Encrypt TREATY IMPOSSIBLE treat yimpo ssibl e (plaintext) FUMNF DYVTF CZYSH H (ciphertext) What have you noticed? 40 THE END 41