CHAPTER 4: Classical (secret-key) cryptosystems • In this chapter we deal with some of the very old or quite old cryptosystems that were primarily used in the pre-computer era. Cryptology, Cryptosystems - secret-key cryptography Cryptology (= cryptography + cryptoanalysis) has more than two thousand years of history. Approaches and paradoxes of cryptography Sound approaches to cryptography • Shannon’s approach based on information theory • Current approach based on complexity theory • Very recent approach based on the laws and limitations of quantum physics Cryptosystems - ciphers The cryptography deals the problem of sending a message (plaintext, cleartext), through a insecure channel, that may be tapped by an adversary (eavesdropper, cryptanalyst), to a legal receiver. Components of cryptosystems: Plaintext-space: P – a set of plaintexts over an alphabet Cryptotext-space: C – a set of cryptotexts (ciphertexts) over alphabet Key-space: K – a set of keys 100 – 42 B.C., CAESAR cryptosystem, Shift cipher CAESAR can be used to encrypt words in any alphabet. In order to encrypt words in English alphabet we use: 100 – 42 B.C., CAESAR cryptosystem, Shift cipher Example e[2](EXAMPLE) = GZCOSNG, e[3](EXAMPLE) = HADPTOH, e[1](HAL) = IBM, e[3](COLD) = FROG POLYBIOUS cryptosystem for encrypion of words in the English alphabet without J. Key-space: Polybious checkerboards 5×5 with 25 English letters and with rows + columns labeled by symbols. Encryption algorithm: Each symbol is substituted by the pair of symbols denoting the row and the column of the checkboard in which the symbol is placed. Example: Decryption algorithm: ??? Kerckhoff’s Principle The philosophy of modern cryptoanalysis is embodied in the following principle formulated in 1883 by Jean Guillaume Hubert Victor Francois Alexandre Auguste Kerckhoffs von Nieuwenhof (1835 - 1903). Requirements for good cryptosystems (Sir Francis R. Bacon (1561 - 1626)) 1. Given e[k] and a plaintext w, it should be easy to compute c = e[k](w). Cryptoanalysis The aim of cryptoanalysis is to get as much information about the plaintext or the key as possible. Main types of cryptoanalytics attack 1.Cryptotexts-only attack. The cryptanalysts get cryptotexts c[1] = e[k](w[1]),…, c[n] = e[k](w[n]) and try to infer the key k or as many of the plaintexts w[1],…, w[n] as possible. Cryptoanalysis 4. Known-encryption-algorithm attack The encryption algorithm e[k] is given and the cryptanalysts try to get the decryption algorithm d[k]. WHAT CAN a BAD EVE DO? Let us assume that Alice sends an encrypted message to Bob. What can a bad enemy, called usually Eve (eavesdropper), do? · Eve can read (and try to decrypt) the message. · Eve can try to get the key that was used and then decrypt all messages encrypted with the same key. · Eve can change the message sent by Alice into another message, in such a way that Bob will have the feeling, after he gets the changed message, that it was a message from Alice. · Eve can pretend to be Alice and communicate with Bob, in such a way that Bob thinks he is communicating with Alice. An eavesdropper can therefore be passive - Eve or active - Mallot. Basic goals of broadly understood cryptography Confidentiality: Eve should not be able to decrypt the message Alice sends to Bob. Data integrity: Bob wants to be sure that Alice's message has not been altered by Eve. Authentication: Bob wants to be sure that only Alice could have sent the message he has received. Non-repudiation: Alice should not be able to claim that she did not send messages that she has sent. HILL cryptosystem The cryptosystem presented in this slide was probably never used. In spite of that this cryptosystem played an important role in the history of modern cryptography. We describe Hill cryptosystem or a fixed n and the English alphabet. Key-space: matrices M of degree n with elements from the set {0, 1,…, 25} such that M^-1 mod 26 exist. Plaintext + cryptotext space: English words of length n. Encoding: For a word w let c[w] be the column vector of length n of the codes of symbols of w. (A -> 0, B -> 1, C -> 2, …) Encryption: c[c] = Mc[w] mod 26 Decryption: c[w] = M^-1c[c] mod 26 HILL cryptosystem Example Plaintext: w = LONDON Cryptotext: MZVQRB Theorem Proof: Exercise Secret-key (symmetric) cryptosystems A cryptosystem is called secret-key cryptosystem if some secret piece of information – the key – has to be agreed first between any two parties that have, or want, to communicate through the cryptosystem. Example: CAESAR, HILL. Another name is symmetric cryptography. Secret-key cryptosystems Example: AFFINE cryptosystem is given by two integers 1 -L- a, b -L- 25, gcd(a, 26) = 1. Encryption: e[a,b](x) = (ax + b) mod 26 Example a = 3, b = 5, e[3,5](x) = (3x + 5) mod 26, e[3,5](3) = 14, e[3,5](15) = 24 - e[3,5](D) = 0, e[3,5](P) = Y Decryption: d[a,b](y) = a^-1(y - b) mod 26 Cryptanalysis’s The basic cryptanalytic attack against monoalphabetic substitution cryptosystems begins with a frequency count: the number of each letter in the cryptotext is counted. The distributions of letters in the cryptotext is then compared with some official distribution of letters in the plaintext laguage. The letter with the highest frequency in the cryptotext is likely to be substitute for the letter with highest frequency in the plaintext language …. The likehood grows with the length of cryptotext. Frequency counts in English: and for other languages: The 20 most common digrams are (in decreasing order) TH, HE, IN, ER, AN, RE, ED, ON, ES, ST, EN, AT, TO, NT, HA, ND, OU, EA, NG, AS. The six most common trigrams: THE, ING, AND, HER, ERE, ENT. Cryptanalysis’s Cryptoanalysis of a cryptotext encrypted using the AFINE cryptosystem with an encryption algorithm e[a,b](x) = ax + b mod 26 where 0 -L- a, b -L- 25, gcd(a, 26) = 1. (Number of keys: 12 × 26 = 312.) Example: Assume that an English plaintext is divided into blocks of 5 letter and encrypted by an AFINE cryptosystem (ignoring space and interpunctions) as follows: How to find the plaintext? Cryptanalysis’s Frequency analysis of plainext and frequency table for English: First guess: E = X, T = U Equations 4a + b = 23 (mod 26) 19a + b = 20 (mod 26) Solutions: a = 5, b = 3 Translation table provides from the above cryptotext the plaintext that starts with KGWTG CKTMO OTMIT DMZEG, what does not make a sense. Cryptanalysis’s Second guess: E = X, A = H Equations 4a + b = 23 (mod 26) b = 7 (mod 26) Solutions: a = 4 or a = 17 and therefore a=17 This gives the translation table and the following plaintext from the above cryptotext Example of monoalphabetic cryptosystem Symbols of the English alphabet will be replaced by squares with or without points and with or without surrounding lines using the following rule: For example the plaintext: WE TALK ABOUT FINNISH SAUNA MANY TIMES LATER results in the cryptotext: Garbage in between method: the message (plaintext or cryptotext) is supplemented by ''garbage letters''. Richelieu cryptosystem used sheets of card board with holes. Polyalphabetic Substitution Cryptosystems Playfair cryptosystem Invented around 1854 by Ch. Wheatstone. Key - a Playfair square is defined by a word w of length at most 25. In w repeated letters are then removed, remaining letters of alphabets (except j) are then added and resulting word is divided to form an array. Polyalphabetic Substitution Cryptosystems VIGENERE and AUTOCLAVE cryptosystems Several polyalphabetic cryptosystems are the following modification of the CAESAR cryptosystem. A 26 ×26 table is first designed with the first row containing a permutation of all symbols of alphabet and all columns represent CAESAR shifts starting with the\break symbol of the first row. Secondly, for a plaintext w and a key k - a word of the same length as w. Encryption: the i-th letter of the plaintext - w[i] is replaced by the letter in the w[i]-row and k[i]-column of the table. Polyalphabetic Substitution Cryptosystems VIGENERE and AUTOCLAVE cryptosystems Example: Keyword: H A M B U R G Plaintext: I N J E D E M M E N S C H E N G E S I C H T E S T E H T S E I N E G Vigenere-key: H A M B U R G H A M B U R G H A M B U R G H A M B U R G H A M B U R Autoclave-key: H A M B U R G I N J E D E M M E N S C H E N G E S I C H T E S T E H Vigerere-cryp.: P N V F X V S T E Z T W Y K U G Q T C T N A E E V Y Y Z Z E U O Y X Autoclave-cryp.: P N V F X V S U R W W F L Q Z K R K K J L G K W L M J A L I A G I N CRYPTOANALYSIS of cryptotexts produced by VINEGAR cryptosystem • Task 1 -- to find the length of the key Kasiski method (1852) - invented also by Charles Babbage (1853). Basic observation If a subword of a plaintext is repeated at a distance that is a multiple of the length of the key, then the corresponding subwords of the cryptotext are the same. CRYPTOANALYSIS of cryptotexts produced by VINEGAR cryptosystem Friedman method Let n[i] be the number of occurrences of the i-th letter in the cryptotext. Let l be the length of the keyword. Let n be the length of the cryptotext. Then it holds Once the length of the keyword is found it is easy to determine the key using the statistical method of analyzing monoalphabetic cryptosystems. Derivation of the Friedman method • Let n[i] be the number of occurrences of i-th alphabet symbol in a text of length n. The probability that if one selects a pair of symbols from the text, then they are the same is and it is called the index of coincides. Derivation of the Friedman method Assume that a cryptotext is organized into l columns headed by the letters of the keyword First observation Each column is obtained using the CAESAR cryptosystem. Probability that two randomly chosen letters are the same in - the same column is 0.065. - different columns is 0.038. The number of pairs of letters in the same column: The number of pairs of letters in different columns: The expect number A of pairs of equals letters is Since one gets the formula for l from the previous slide. ONE-TIME PAD cryptosystem – Vernam’s cipher Binary case: plaintext w key k are binary words of the same length cryptotext c Encryption: c = w AA k Decryption: w = c AA k Perfect secret cryptosystems By Shanon, a cryptosystem is perfect if the knowledge of the cryptotext provides no information whatsoever about its plaintext (with the exception of its length). It follows from Shannon's results that perfect secrecy is possible if the key-space is as large as the plaintext-space. In addition, a key has to be as long as plaintext and the same key should not be used twice. Transposition Cryptosystems The basic idea is very simple: permutate the plaintext to get the cryptotext. Less clear it is how to specify and perform efficiently permutations. One idea: choose n, write plaintext into rows, with n symbols in each row and then read it by columns to get cryptotext. Example Cryptotexts obtained by transpositions, called anagrams, were popular among scientists of 17th century. They were used also to encrypt scientific findings. Newton wrote to Leibnitz a^7c^2d^2e^14f^2i^7l^3m^1n^8o^4q^3r^2s^4t^8v^12x^1 what stands for: ”data aequatione quodcumque fluentes quantitates involvente, fluxiones invenire et vice versa” Example a^2cdef^3g^2i^2jkmn^8o^5prs^2t^2u^3z Solution: KEYWORD CAESAR cryptosystem1 Choose an integer 0 < k < 25 and a string, called keyword, with at most 25 different letters. The keyword is then written bellow the English alphabet letters, beginning with the k-symbol, and the remaining letters are written in the alphabetic order after the keyword. KEYWORD CAESAR cryptosystem Exercise Decrypt the following cryptotext encrypted using the KEYWORD CAESAR and determine the keyword and k KEYWORD CAESAR cryptosystem Step 1. Make the frequency counts: UNICITY DISTANCE of CRYPTOSYSTEMS Redundancy of natural languages is of the key importance for cryptanalysis. Would all letters of a 26-symbol alphabet have the same probability, a character would carry lg 26 = 4.7 bits of Information. The estimated average amount of information carried per letter in a meaningful English text is 1.5 bits. The unicity distance of a cryptosystem is the minimum number of cryptotext (number of letters) required to a computationally unlimited adversary to recover the unique encryption key. Empirical evidence indicates that if any simple cryptosystem is applied to a meaningful English message, then about 25 cryptotext characters is enough for an experienced cryptanalyst to recover the plaintext. ANAGRAMS - EXAMPLES German: IRI BRÄTER, GENF Briefträgerin FRANK PEKL, REGEN … PEER ASSSTIL, MELK … INGO DILMR, PEINE … EMIL REST, GERA … KARL SORDORT, PEINE … STREAM CRYPTOSYSTEMS Two basic types of cryptosystems are: • Block cryptosystems (Hill cryptosystem,…) – they are used to encrypt simultaneously blocks of plaintext. • Stream cryptosystems (CAESAR, ONE-TIME PAD,…) – they encrypt plaintext letter by letter, or block by block, using an encryption that may vary during the encryption process. Stream cryptosystems are more appropriate in some applications (telecommunication), usually are simpler to implement (also in hardware), usually are faster and usually have no error propagation (what is of importance when transmission errors are highly probable). Two basic types of stream cryptosystems: secret key cryptosystems (ONE-TIME PAD) and public-key cryptosystems (Blum-Goldwasser) Block versus stream cryptosystems In block cryptosystems the same key is used to encrypt arbitrarily long plaintext – block by block - (after dividing each long plaintext w into a sequence of subplaintexts (blocks) w[1]w[2]w[3] ). In stream cryptosystems each block is encryptyd using a different key CRYPTOSYSTEMS WITH STREAMS OF KEYS EXAMPLES A keystream is called synchronous if it is independent of the plaintext. KEYWORD VIGENERE cryptosystem can be seen as an example of a synchronous keystream cryptosystem. Another type of the binary keystream cryptosystem is specified by an initial sequence of keys k[1], k[2], k[3] … k[m ]and a initial sequence of binary constants b[1], b[2], b[3] … b[m-1 ]and the remaining keys are computed using the rule A keystrem is called periodic with period p if k[i+p] = k[i] for all i. PERFECT SECRECY - BASIC CONCEPTS Let P, K and C be sets of plaintexts, keys andcryptotexts. Let p[K](k) be the probability that the key k is chosen from K and let a priory probability that plaintext w is chosen is p[p](w). If for a key , then for the probability P[C](y) that c is the cryptotext that is transmitted it holds For the conditional probability p[c](c|w) that c is the cryptotext if w is the plaintext it holds Using Bayes' conditional probability formula p(y)p(x|y) = p(x)p(y|x) we get for probability p[P](w|c) that w is the plaintext if c is the cryptotext the expression PERFECT SECRECY - BASIC RESULTS Definition A cryptosystem has perfect secrecy if (That is, the a posteriori probability that the plaintext is w,given that the cryptotext is c is obtained, is the same as a priori probability that the plaintext is w.) Example CAESAR cryptosystem has perfect secrecy if any of the26 keys is used with the same probability to encode any symbol of the plaintext. Proof Exercise. An analysis of perfect secrecy: The condition p[P](w|c) = p[P](w) is for all wÎP and cÎC equivalent to the condition p[C](c|w) = p[C](c). Let us now assume that p[C](c) > 0 for all cÎC. Fix wÎP. For each cÎC we have p[C](c|w) = p[C](c) > 0. Hence, for each c€C there must exists at least one key k such that e[k](w) = c. Consequently, |K| >= |C| >= |P|. In a special case |K| = |C| = |P|. the following nice characterization of the perfect secrecy can be obtained: Theorem A cryptosystem in which |P| = |K| = |C| provides perfect secrecy if and only if every key is used with the same probability and for every wÎP and every c€C there is a unique key k such that e[k](w) = c. Proof Exercise. PRODUCT CRYPTOSYSTEMS A cryptosystem S = (P, K, C, e, d) with the sets of plaintexts P, keys K and cryptotexts C and encryption (decryption) algorithms e (d) is called endomorphic if P = C. If S[1] = (P, K[1], P, e^(1), d ^(1)) and S[2] = (P, K[2], P, e ^(2), d ^(2)) are endomorphic cryptosystems, then the product cryptosystem is S[1] Ä S[2] = (P, K[1] Ä K[2], P, e, d), where encryption is performed by the procedure e[( k1, k2 )](w) = e[k2](e[k1](w)) and decryption by the procedure d[( k1, k2 )](c) = d[k1](d[k2](c)). EXERCISES • For the following pairs plaintext-cryptotext determine which cryptosystem was used: - COMPUTER - HOWEWVER THE EST UNDERESTIMATES ZANINESS YOUR JUDICIOUS WISDOM - SAUNA AND LIFE – RMEMHCZZTCEZTZKKDA A spy group received info about the arrival of a new member. Thesecret police succeeded in learning the message and knew that it wasencrypted using the HILL cryptosystem with a matrix of degree 2. It also learned that the code ``10 3 11 21 19 5'' stands for the name ofthe spy and ``24 19 16 19 5 21'', for the city, TANGER, the spy should come from. What is the name of the spy? • Decrypt the following cryptotexts. (Not all plaintexts are in English.) - WFLEUKZFEKZFEJFWTFDGLKZEX - DANVHEYD SEHHGKIIAJ VQN GNULPKCNWLDEA - DHAJAHDGAJDI AIAJ AIAJDJEH DHAJAHDGAJDI AIDJ AIBIAJDJ\DHAJAHDGAJDI AIAJ DIDGCIBIDH DHAJAHDGAJDI AIAJ DICIDJDH - KLJPMYHUKV LZAL ALEAV LZ TBF MHJPS • Find the largest possible word in Czech language such that its nontrivial encoding by CAESAR is again a meaningful Czech word. • Find the longest possible meaningful word in a European language such that some of its non-trivial encoding by CAESAR is again ameaningful word in a European language (For example: e[3](COLD) = FROG). EXERCISES IV • Decrypt the following cryptotext obtained by encryption with an AFFINE cryptosystem: KQEREJEBCPPCJCRKIEACUZBKRVPKRBCIBQCARBJCVFCUPKRIOFKPACUZQEPBKRXPEIIEABDKPBCPFCDCCAFIEABDKPBCPFEQPKAZBKRHAIBKAPCCIBURCCDKDCCJCIDFUIXPAFFERBICZDFKABICBBENEFCUPJCVKABPCYDCCDPKBCOCPERKIVKSCPICBRKIJPKAI • Suppose we are told that the plaintext “FRIDAY'' yields the cryptotext “PQCFKU'' with a HALL cryptosystem. Determine the encryption matrix. • Suppose we are told that the plaintext “BREATHTAKING”' yieldsthe cryptotext “RUPOTENTOSUP'' with a HILL cryptosystem. Determine the encryption matrix. • Decrypt the following cryptotext, obtained using the AUTOKLAVE cryptotext (using exhaustive search ?) MALVVMAFBHBUQPTSOXALTGVWWRG • Design interesting cryptograms in (at least) one of the languages: Czech, French, Spanish, Chines? • Show that each permutation cryptosystem is a special case of the HILL cryptosystem. • How many 2 × 2 matrices are there that are invertible over Z[p], where p is a prime. • Invent your own interesting and quite secure cryptosystem.