cs-lecture2-cryptography.pdf
Transcript
Lecture2 -Cryptography 2.1 Terminology and Background Consider the steps involved in sending messages from a sender, S, to a recipient, R. If S entrusts the message to T, who then delivers it to R, T then becomes the transmission medium. If an outsider, O, wants to access the message (to read, chang...
Lecture2 -Cryptography 2.1 Terminology and Background Consider the steps involved in sending messages from a sender, S, to a recipient, R. If S entrusts the message to T, who then delivers it to R, T then becomes the transmission medium. If an outsider, O, wants to access the message (to read, change, or even destroy it), we call O an interceptor or intruder. Any time after S transmits it via T, the message is vulnerable to exploitation, and O might try to access the message in any of the following ways: Block it, by preventing its reaching R, thereby affecting the availability of the message. Intercept it, by reading or listening to the message, there by affecting the confidentiality of the message. Modify it, by seizing the message and changing it in some way, affecting the message's integrity. Fabricate an authentic-looking message, arranging for it to be delivered as if it came from S, thereby also affecting the integrity of the message. Encryption is a technique that can address all these problems. Encryption is the process of encoding a message so that its meaning is not obvious; decryption is the reverse process, transforming an encrypted message back into its normal, original form. Alternatively, the terms encode and decode or encipher and decipher are used instead of encrypt and decrypt A system for encryption and decryption is called a cryptosystem. The original form of a message is known as plaintext, and the encrypted form is called ciphertext. The encryption and decryption rules, called algorithms, often use a device called a key, denoted by K, so that the resulting ciphertext depends on the original plaintext message, the algorithm, and the key value. We write this dependence as C = E(K, P). Sometimes the encryption and decryption keys are the same, so P = D(K, E(K,P)). This form is called symmetric encryption because D and E are mirror-image processes. At other times, encryption and decryption keys come in pairs. Then, a decryption key, KD, inverts the encryption of key KE so that P = D(KD, E(KE,P)). Encryption algorithms of this form are called asymmetric because converting C back to P involves a series of steps and a key that are different from the steps and key of E. Important of using A key 1. Flexibility in using an encryption scheme. We can create different encryptions of one plaintext message just by changing the key. 2. Provides additional security. If the encryption algorithm should fall into the interceptor's hands, future messages can still be kept secret because the interceptor will not know the key value. 11 Lecture2 -Cryptography An encryption scheme that does not require the use of a key is called a keyless cipher. The word cryptography means hidden writing, and it refers to the practice of using encryption to conceal text. A cryptanalyst studies encryption and encrypted messages, hoping to find the hidden meanings. cryptology is the research into and study of encryption and decryption; it includes both cryptography and cryptanalysis. 2.2Substitution Ciphers Substitute a character or symbol for each character of the original message is called a monoalphabetic cipher or simple substitution The Caesar Cipher The Caesar cipher has an important place in history. Julius Caesar is said to have been the first to use this scheme, in which each letter is translated to the letter a fixed number of places after it in the alphabet. Caesar used a shift of 3, Encryption ci = E(pi) = pi + K mod 26 Decryption pi = D(pi) = ci -K mod 26 12 Lecture2 -Cryptography A full translation chart of the Caesar cipher is shown here. 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 Example: encrypt the message TREATY , using ceasor cipher C (T) =19+3 mod 26 = 22 = W C ( R) =17+3 mod 26 =20 = U C (E) =4+3 mod 26 = 7 = H C (A) =0+3 mod 26 = 3 = D C (T) =19+3 mod 26 = 22 = W C (Y) =24+3 mod 26 = 1 = B Would be encoded as TREATY wuhdwb The decryption will be p(w)= 22-3 mod 26= 19 = t p(u)= 20-3 mod 26= 17 = r p(h)= 7-3 mod 26= 4 = e p(d)= 3-3 mod 26= 0 = t p(b)= 1-3 mod 26 = -2 mod 26 = 26-2 =24 = y Advantage: The Caesar cipher is quite simple Disadvantage: repeated pattern is the major weakness of the Caesar cipher Other Substitutions 1. Scrambled alphabet In substitutions, the alphabet is scrambled, and each plaintext letter maps to a unique ciphertext letter. One way to scramble an alphabet is to use a key, a word that controls the permutation. For instance, if the key is word, the sender or receiver first writes the alphabet and then writes the key under the first few letters of the alphabet. 13 Lecture2 -Cryptography ABCDEFGHIJKLMNOPQRSTUVWXYZ Wordabcefghijklmnpqstuvxyz Example: Encrypt the message “gold” using scrambled alphabet table with key= sand Message G O LD Alphabet ABCDEFGHIJKLMNOPQRSTUVWXYZ Reordered alpha SANDBCEFGHIJKLMOPQRTUVWXYZ E M J Cipher text D 2. Substitution with key as a sentence In this type the key would be more than one symbol in form of alphabet, for example the key= smart, then the encryption process would be by repeating the keyword along the message and sum them mod 26. Example: encrypt the message “computer” using substitution cipher with key=”old” Using the alphabet table A 0 B 1 C 2 D 3 E 4 F 5 G 6 H 7 I 8 J 9 K 10 L 11 M 12 N 13 O 14 P 15 Q 16 R 17 S 18 T 19 U 20 V 21 W 22 X 23 Y 24 The message code will be: computer= 2 14 12 15 20 19 4 17 The key code old= 14 11 4 Encryption: C=m +k mod 26 m k M+k mod 26 c 2 14 16 q 14 11 25 z 12 4 16 q 15 14 3 d 20 11 5 f 19 4 23 x 4 14 18 s 17 11 2 c 3. One-Time Pads A one-time pad is sometimes considered the perfect cipher. The Vernam cipher is a type of one-time pad devised by Gilbert Vernam for AT&T. The Vernam cipher is immune from most cryptanalytic attacks. The basic encryption involves an arbitrarily long nonrepeating sequence of numbers that are combined with the plaintext. 14 Z 25 Lecture2 -Cryptography Vernam’s invention used an arbitrarily long punched paper tape that fed into a teletype machine. The tape contained random numbers that were combined with characters typed into the teletype. The sequence of random numbers had no repeats, and each tape was used only once. As long as the key tape does not repeat or is not reused, this type of cipher is immune from cryptanalytic attack because the available ciphertext does not display the pattern of the key. A model of this process is shown in Figure below. Example: use vernam cipher to encrypt the message “VERNAM CIPHER”, with Key = 76 48 16 82 44 03 58 11 60 05 48 88 m k M+k mod 26 c V 21 76 19 t E 4 48 0 a R 17 16 7 h N 13 82 17 r A 0 44 18 s M 12 3 15 p C 2 58 8 i I 8 11 19 t P 15 60 23 x H 7 5 12 m E 4 48 0 a R 17 88 1 b 2.3 Transpositions (Permutations) A transposition is an encryption in which the letters of the message are rearranged. Columnar transposition We arrange the message as array of 2- dimension, The number of columns and rows depends on the length of the message. If the length of the message equal to 30 then the probability of the numbers of rows and columns are 15×2, 2×15, 10×3, 3×10, 5×6, 6×5. Note that if the length of the message is 29, we add a dummy letter in the end of the message. 15 Lecture2 -Cryptography For example if the message is ALIRAQIA UNIVERSITY then the length of the message is 18, 18=3×6 1 A R I N E I 2 L A A I R T 3 I Q U V S Y If the key is (2,3,1) we can arrange the columns as following 2 L A A I R T 3 I Q U V S Y 1 A R I N E I The cipher text comes from the reading on the above table by columns LAAIRT IQUVSY ARINEI ,To decrypt the message we use the same key (2,3,1). 1 A R I N E I 2 L A A I R T 3 I Q U V S Y A secure encryption should not allow an interceptor to use a small piece of the ciphertext to predict the entire pattern of the encryption 16 Lecture2 -Cryptography The goal of substitution is confusion; the encryption method is an attempt to make it difficult for a cryptanalyst or intruder to determine how a message and key were transformed into ciphertext. With transposition, the cryptography aims for diffusion, widely spreading the information from the message or the key across the ciphertext.. An encryption algorithm is called breakable when, given enough time and data, an analyst can determine the algorithm. However, an algorithm that is theoretically breakable may in fact be impractical to try to break. Consider a 25-character message that is expressed in just uppercase letters. A given cipher scheme may have 2625 (approximately 1035) possible decipherments, so the task is to select the right one out of the 2625. If your computer could perform on the order of 1010 operations per second, finding this decipherment would require on the order of 1016 seconds, or roughly 1011 years. Making "Good" Encryption Algorithms ,Shannon's Characteristics of "Good" Ciphers 1. The amount of secrecy needed should determine the amount of labor appropriate for the encryption and decryption. 2. The set of keys and the enciphering algorithm should be free from complexity. 3. The implementation of the process should be as simple as possible. 4. Errors in ciphering should not propagate and cause corruption of further information in the message. 5. The size of the enciphered text should be no larger than the text of the original message. 17
