Question 1. (a) ASCII characters. Original message is HALF OF A POINT IS YOURS, including space characters. (b) Morse code. V is 'in' is '-' (long syllable). Message is NEW YORK. (c) Anagram. MINOTAUR or MAIN TOUR. (d) Binary system transformed into decimal one, get the alphabet characters according to their alphabet order, A=l. NORTH TOWER. (e) Order of prime numbers, get alphabet characters according to this order. YETTI FOUND. (f) Caesar cipher, shift - 8 to the right. ATTACK AFTER DINNER. (g) Atbash cipher. KING IN AVIGNON. (h) Scytale cipher, 4 letters around the circle. FOLLOW THE MAN IN BLACK. Question 2. (a) (i) Using ea^(x) — a*x + b(mod2Q): where x is each letter of word CODING, we get numbers 12,14,23,0,3,4. That gives us cryptotext MOXADE. (ii) Using dafi(x) = (x — b) * a~1(mod26), where x is each letter of cryptotext MVUZRO, we obtain numbers 2,17,24,19,14,15. That gives us encrypted word CRYPTO. (b) (i) Encrypting "CODING", corresponding numbers are 2,14,3,8,13,6, operations mod 26. "2" "25" "8" M * 14 = 3 ; M * 13 0 3 4 6 7 We see that we get numbers 25,3,4,9,0,7 so encrypted word is ZDEJAH. (ii) Corresponding numbers for JTUYVC are 9,19,20,24,21,2. For decoding we need to find M-1 in mod 26. "9 25 23" 9 2 24 7 2 10 3 ;M * 19 8 ;M * 21 4 20 21 16 20 15 2 17 Wc get numbers 9,19,20,7,4,17 so decrypted word is CIPHER. Question 3. (a) Pigpen cipher Number of possible keys is 26!, Assuming all keys are equally likely H(k) = log2(26]) = 88.381953, for englisli text D = 3.2, and Unicity distance U = —jy^- = 27.6194, that means given at least 28 characters of cryptotext, it should be possible to find unique plaintext and key. (b) Vigenere cipher Number of possible keys is 26" where n is length of key. U = = l°92j226 ^ = 10.2822 (11 characters needed) (c) Transposition cipher with period 7 columns: 1 2 3 4 5 6 7, Transposed columns example: 2 3 4 6 7 1 5 Number of possible permutations is 7! U=HM = ^£7!) = 3 g435 ^ characters needed) (d) one-time pad For any alphabetic substitution cipher with a truly random key of length greater or equal to the length of the message, plaintext cannot be found from ciphertext alone. So unicity distance is oo. Number of possible keys = oo. Question 4. (a) K is distributed uniformly: Pr[K = k0] = Pr[K = fa] = Pr[K = k2] = Pr[K = k3] = 1/4 4i(0)] + dm (0)] = _7 24 dfci(l)] + dM(l)] = i 4 Pc(0) : Pr[C = 0] = Pr[K = k()]Pr[P = dM(0)] + Pr[K = fa]Pr[P = Pr[K = k2]Pr[P = dk2 (0)] + Pr K = k3]Pr[P = Pr[K = k0]Pr[P = 3] + Pr[K = fa]Pr[P = 1] + Pr[K = k2]Pr[P = 2] + Pr[K = k3]Pr[P = 3] = Pc(l) : Pr[C = 1] = Pr[K = k0]Pr[P = dk0{l)] + Pr K = ki]Pr[P = Pr[K = k2]Pr[P = dM(l)] + Pr[K = k3]Pr[P = Pr[K = h]Pr[P = 2] + Pr[K = fa]Pr[P = 0] + Pr[K = k2]Pr[P = 3] + Pr[K = k3]Pr[P = 0] = PC (2) : Pr[C = 2] = Pr[K = k0]Pr[P = 1] + Pr[K = fa]Pr[P = 3] + Pr[K = k2]Pr[P = 0] + Pr[K = k3]Pr[P = 2] = PC(3) : Pr[C = 3] = Pr[K = kQ]Pr[P = 0] + Pr[K = fa]Pr[P = 2] + Pr[K = k2]Pr[P = 1] + Pr[K = k3]Pr[P = 1] = 21 (b) A cryptosystem has perfect secrecy if Pr[P — w\C — c] — Pr[P = w] or equivalent Pr[C = c\P = w] = Pr[C = c] for all w € P and c € C. The specified cryptosystem has not perfect secrecy. F.e. Pr[C = 0] ^ Pr[C = 0\P = 0] because + 0) m\ek eo ei ?2 es 0 3 1 2 0 1 2 0 3 1 2 1 3 0 2 3 0 2 1 3 We can change the encryption function e3 so that the cryptosystem becomes perfectly secure. Now, for Vc e {0,1, 2, 3} hold: Pr[C = c] = | and Pr[C = c|P = 0] = Pr[C = c\P = 1] = Pr[C = c\P = 2} = Pr[C = c\P = 3] = \ Question 5. Let Wi = Xifl Xiti ... Xi>n,C{ = yifi yi,i ... yi,n- Then we can calculate u>;_i = fcj the following way: = ki = Xi-ifl ... Xj_i)n = Cj - w, = y^o - xh0 yiti - xi}j ... yi)H - xi>n mod 26 From this we can calculate u>2 using u>3 and C3: W2 = k3 = C3 - 103 = (j/3,0 - X3,o) (l/3,l - ^3,l) ••■ (j/3,n ~ ^3,n) mod 26 Then we can calculate wi using u>2 and C2: «!1 = &2 = C2 - U>2 = C2 - (C3 - IU3) = = (1/2,0 - 1/3,0 + 2:3,0) (2/2,1 - 2/3,1 + 2:3,1) ... (j/2,n ~ l/3,n + 2?3,n) mod 26 And finally we calculate &i using toi and c\: ki = ci—wi = c\ - (02 - 102) = ci - (c2 - (c3 - tu3)) = - (t/1,0 - 2/2,0 + 1/3,0 - Z3)o) (l/l,l - 1/2,1 + 2/3,1 - 2:3,1) ••• {y\,n ~ 2/2,« + 2/3,n - ^3,n) mod 26 4.6 For 26-letter alphabet, determine how many affine ciphers are there that leave Solution: First of all wc have to define the fixed character. From definition of affine cipher for key (a, b) is letter encoded e^a,b) (w) = a ■ w 4- b mod 26. Therefore the fixed character is w = a ■ w + b mod 26, which is equivalent to —b = (a — l)w mod 26. So wc have to discus how many solutions have this equivalence. From definiton we know, that gcd(a, 26) = 1, therefore a e {1,3,5,7,9,11,15,17,19,21,23,25}, therefore (a - 1) e {0, 2, 4,6, 8,10,14,16,18,20, 22, 24} (a - 1 is even). First of all wc look at a = 1, which is special case: a = 1 : b = 0 mod 26, therefore for 6 = 0 are all characters fixed position and otherwise there are no fixed characters. For all other a: We know, that a — 1 is even and 26 is even too. • b is odd: This equivalence have no solutions (therefore there are no fixed characters), • 6 is even: We can divide both sides of equivalence and modulo too by 2 and we obtain | = mod 13. From set of all possible numbers of a — 1 we can see that gc.d(a — 1,13) = 1, therefore this second equivalence have exactly one solution therefore the original equivalence has exactly two solutions. We look at all possible values of a and b. □ (a) no characters fixed; Solution: No fixed characters are for a = 1 and 6^0 and for other possible a and b even. Therefore it is 2.") -11.1:!= ICS affine ciphers. □ (b) exactly one character fixed: Solution: As we can see above all possible options have no fixed or at least 2 fixed characters, therefore there are 0 affine ciphers with one fixed character. □ (c) at least two characters fixed. Solution: At least two fixed characters are when a ^ 1 and 6 is even and for a. — 1 and 6 = 0, therefore there are 11 • 13 + 1 = 144 affine cipher with at least two fixed characters. □ Question 7. First, determine key length. We do it by overlaying the message with its right rotation and counting letters that are the same, for each rotation 2..20. The results are: offset matches 2 58 3 59 4 36 5 80 6 53 7 17 8 42 9 49 10 83 11 44 12 46 13 52 14 45 15 88 16 50 17 48 18 44 19 43 20 74 Clearly the best results are for 15, 10 and 5. As such, it is a good start to assume a key of length 5. Next, we use frequency analysis on every 5th letter with offset 0..4 to determine the key. We sort the corresponding letters by frequency, creating a frequency list for each position. Next, we take each frequency list, and for each right shift with offsets 0..25 compute the difference from the English frequency list, which is "ETAOINSRHDLUCMFYWGPBVKXQJZ". We quantify the difference by summing up squares of index differences for each letter. Then we take the lowest difference for each position, giving us: offset best shift best difference 0 16 478 1 6 252 2 23 400 3 12 280 4 8 218 The shift wc got is the one needed to "fix" that position. To get the appropriate key, we subtract it from 26, giving us: 10,20,3,14,18, or as letters, KUDOS. Deciphered text with this key: WHILEMDSTCRYPTANALYSTSHADGIVENUPALLHOPEOFEVERBREAKINGTHEVIGENE RECIPHERBABBAGEWASINSPIREDTOATTEMPTADECIPHERMENTBYANEXCHANGEDF LETTERSWITHJDHNHALLBRQCKTHWAITESADENTISTFROMBRISTOLWITHARATHER INNDCENTVIEWOFCIPHERSINEIGHTEENFIFTYFOURTHWAITESCLAIMEDTDHAVEI NVENTEDANEWCIPHERWHICHINFACTWASEQUIVALENTTOTHEVIGENERECIPHERHE WROTETOTHEJ0URNALOFTHESOCIETYOFARTSWITHTHEINTENTION0FPATENTING HISIDEAAP PARENTLYUNAWARETHATHEWAS SEVERALCENTURIEST0 0LATEBABBAG ETO0WROTETOTHESOCIETYPDINTINGOUTTHATTHECYPHERISAVERYOLDONEANDT DBEF0UNDINM0STBQ0KSTHWAITESWASUNAP0L0GETICANDCHALLENGEDBABBAGE T0BREAKHISCIPHERWHETHER0RN0TITWASBREAKABLEWASIRRELEVANTT0WHETH ER0RNOTITWASNEWBUTBABBAGESCURIQSITYWASSUFFICIENTLYAROUSEDFORHI MTQEMBARKONASEARCHFORAWEAKNESSINTHEVIGENERECIPHERCRACKINGADIFF ICULTCIPHERISAKIMTOCLIMBINGASHEERCLIFFFACETHECRYPTANALYSTISSEE KINGANYN0DK0RCRANNYTHATC0ULDPRDVIDETHESLIGHTESTF00THDLDINAM0N0 ALPHABETICCIPHERTHECRYPTANALYSTWILLLATCH0NTOTHEFREQUENCYOFTHEL ETTERSBECAUSETHECOMMONESTLETTERSSUCHASETANDAWILLSTANDOUTNDMATT ERHOWTHEYHAVEBEENDISGUISEDINTHEPOLYALPHABETICVIGENERECIPHERTHE FREQUENCIESAREHUCHMDREBALANCEDBECAUSETHEKEYWORDISUSEDTOSWITCHB ETWEENCIPHERALPHABETSHENCEATFIRSTSIGHTTHEROCKFACESEEMSPERFECTL YSMO0THSIMQNSINGHTHECODEB0OK 4.8 (a) I finished my second book. It was on the sixth day of Christmas, The manuscript was hidden on the bottom of the seventh drawer of my table. Fortunately, my friend called and said he can come over in three days. At first, I conld not believe it. But my four-leg friend Hop greeted John in the door. Solution: Each sentence contains number n,. Encryption of this cipher text is the n;-th letter in the sentence {e. g. in first sentence is number two so the first letter is f). The code is four a. m.. □ (b) Solution: This symbols are symbol from the beginning of ASCII table and the position of symbol in ASCII table is position of letter in alphabet. The plaintext is TREASURE IN THE CAVE. □