(12)
Exercises
1.1 Below are given four examples of ciphertext, one obtained from a Substitution Cipher, one from a Vigenere Cipher, one from an Affine Cipher, and one unspecified.
In each case, the task is to determine the plaintext.
Give a clearly written description of the steps you followed to decrypt each ciphertext. This should include all statistical analysis and computations you performed.
The first two plaintexts were taken from “The Diary of Samuel Marchbanks,” by Robertson Davies, Clarke Irwin, 1947; the fourth was taken from “Lake Wobegon Days,” by Garrison Keillor, Viking Penguin, Inc., 1985.
(a) Substitution Cipher:
EMGLOSUDCGDNCUSWYSFHNSFCYKDPUMLWGYICOXYSIPJCK
QPKUGKMGOLICGINCGACKSNISACYKZSCKXECJCKSHYSXCG
OIDPKZCNKSHICGIWYGKKGKGOLDSILKGOIUSIGLEDSPWZU
GFZCCNDGYYSFUSZCNXEOJNCGYEOWEUPXEZGACGNFGLKNS
ACIGOIYCKXCJUCIUZCFZCCNDGYYSFEUEKUZCSOCFZCCNC
IACZEJNCSHFZEJZEGMXCYHCJUMGKUCY
HINT F decrypts to w.
(b) Vigenere Cipher:
KCCPKBGUFDPHQTYAVINRRTMVGRKDNBVFDETDGILTXRGUD
DKOTFMBPVGEGLTGCKQRACQCWDNAWCRXIZAKFTLEWRPTYC
QKYVXCHKFTPONCQQRHJVAJUWETMCMSPKQDYHJVDAHCTRL
SVSKCGCZQQDZXGSFRLSWCWSJTBHAFSIASPRJAHKJRJUMV
GKMITZHFPDISPZLVLGWTFPLKKEBDPGCEBSHCTJRWXBAFS
PEZQNRWXCVYCGAONWDDKACKAWBBIKFTIOVKCGGHJVLNHI
FFSQESVYCLACNVRWBBIREPBBVFEXOSCDYGZWPFDTKFQIY
CWHJVLNHIQIBTKHJVNPIST
(c) Affine Cipher:
KQEREJEBCPPCJCRKIEACUZBKRVPKRBCIBQCARBJCVFCUP
KRIOFKPACUZQEPBKRXPEIIEABDKPBCPFCDCCAFIEABDKP
BCPFEQPKAZBKRHAIBKAPCCIBURCCDKDCCJCIDFUIXPAFF
ERBICZDFKABICBBENEFCUPJCVKABPCYDCCDPKBCOCPERK
IVKSCPICBRKIJPKABI
(d) unspecified cipher:
BNVSNSIHQCEELSSKKYERIFJKXUMBGYKAMQLJTYAVFBKVT
DVBPVVRJYYLAOKYMPQSCGDLFSRLLPROYGESEBUUALRWXM
MASAZLGLEDFJBZAVVPXWICGJXASCBYEHOSNMULKCEAHTQ
OKMFLEBKFXLRRFDTZXCIWBJSICBGAWDVYDHAVFJXZIBKC
GJIWEAHTTOEWTUHKRQVVRGZBXYIREMMASCSPBNLHJMBLR
FFJELHWEYLWISTFVVYFJCMHYUYRUFSFMGESIGRLWALSWM
NUHSIMYYITCCQPZSICEHBCCMZFEGVJYOCDEMMPGHVAAUM
ELCMOEHVLTIPSUYILVGFLMVWDVYDBTHFRAYISYSGKVSUU
HYHGGCKTMBLRX
(a) How many 2 × 2 matrices are there that are invertible over ?
(b) Let p be prime.
Show that the number of 2 × 2 matrices that are invertible over is (p2 - 1)(p2 - p).
HINT Since p is prime, is a field. Use the fact that a matrix over a field is invertible if and only if its rows are linearly independent vectors (i.e., there does not exist a non-zero linear combination of the rows whose sum is the vector of all 0?s).
(c) For p prime, and m ??2 an integer, find a formula for the number of m × m matrices that are invertible over .
1.2 We describe a special case of a Permutation Cipher. Let m, n be positive integers. Write out the plaintext, by rows, in m × n rectangles. Then form the ciphertext by taking the columns of these rectangles. For example, if m = 4, n = 3, then we would encrypt the plaintext “cryptography” by forming the following rectangle:
cryp
togr
aphy
The ciphertext would be “CTAROPYGHPRY.”
(a) Describe how Bob would decrypt a ciphertext (given values for m and n).
(b) Decrypt the following ciphertext, which was obtained by using this method of
encryption:
MYAMRARUYIQTENCTORAHROYWDSOYEOUARRGDERNOGW
1.3 There are eight different linear recurrences over of degree four having c0= 1. Determine which of these recurrences give rise to a keystream of period 15 (given a non-zero initialization vector).
1.9 The purpose of this exercise is to prove the statement made in Section 1.2.5 that the m × m coefficient matrix is invertible. This is equivalent to saying that the rows of this matrix are linearly independent vectors over .
As before, we suppose that the recurrence has the form
(z1, . . . , zm) comprises the initialization vector. For i ??1, define Note that the coefficient matrix has the vectors v1, . . . , vm
as its rows, so our objective is to prove that these m vectors are linearly independent. Prove the following assertions:
(a) For any i ??1,
(b) Choose h to be the minimum integer such that there exists a non-trivial linear
combination of the vectors v1, . . . , vh which sums to the vector (0, . . . , 0) modulo 2. Then
and not all the ?j?s are zero. Observe that h ??m + 1, since any m + 1 vectors in an mdimensional vector space are dependent.
(c) Prove that the keystream must satisfy the recurrence
for any i ??1.
(d) Observe that if h ??m, then the keystream satisfies a linear recurrence of degree less than m, a contradiction. Hence, h = m + 1, and the matrix must be invertible.
1.5 We describe a stream cipher that is a modification of the Vigenere Cipher. Given a keyword (K1, . . . , Km) of length m, construct a keystream by the rule zi= Ki(1 ??i ??m), zi+ m = zi+ 1 mod26 (i ??m + 1). In other words, each time we use the keyword, we replace each letter by its successor modulo 26. For example, if SUMMER is the keyword, we use SUMMER to encrypt the first six letters, we use TVNNFS for the next six letters, and so on.
Describe how you can use the concept of index of coincidence to first determine the length of the keyword, and then actually find the keyword.
Test your method by cryptanalyzing the following ciphertext:
IYMYSILONRFNCQXQJEDSHBUIBCJUZBOLFQYSCHATPEQGQ
JEJNGNXZWHHGWFSUKULJQACZKKJOAAHGKEMTAFGMKVRDO
PXNEHEKZNKFSKIFRQVHHOVXINPHMRTJPYWQGJWPUUVKFP
OAWPMRKKQZWLQDYAZDRMLPBJKJOBWIWPSEPVVQMBCRYVC
RUZAAOUMBCHDAGDIEMSZFZHALIGKEMJJFPCIWKRMLMPIN
AYOFIREAOLDTHITDVRMSE
The plaintext was taken from “The Codebreakers,” by D. Kahn, Macmillan, 1967.
2.16 Suppose S1is the Shift Cipher (with equiprobable keys, as usual) and S2 is the Shift Cipher where keys are chosen with respect to some probability distribution (which need not be equiprobable). Prove that S1× S2= S1.
2.17 Suppose S1and S2 are Vigenere Ciphers with keyword lengths m1, m2 respectively, where m1> m2.
(a) If m2| m1, then show that S2× S1= S1 .
(b) One might try to generalize the previous result by conjecturing that S2× S1= S3,
where S3is the Vigenere Cipher with keyword length lcm(m1, m2). Prove that this
conjecture is false.
HINT If mod m2, then the number of keys in the product cryptosystem S2× S1 is than the number of keys in S3.
1. Problem: The following ciphertext was enciphered using the Vigenere ci-
pher. How can we decipher it?
Answer: We need to use Friedman’s index of coincidence combined with
Kasiski’s test.
The Kasiski Test
2. Example: Encipher the message: “ ...ON A PLANE. THE PLANE IS DUE...
using the Vigenere cipher with keywords
(a) WATER
(b) MILK
3. Kasiski’s test. If a string of characters appears repeatedly in a polyalpha-
betic ciphertext message, it is possible (though not certain) that the distance
between the occurences is a multiple of the length of the keyword
4. Example. Determine a likely Vigenere keyword length for the following
ciphertext:
Solution: There are repeated letter groups:
The separation (start to start) between the two occurrences of is
108 33 22 letters, and the separation between those of is 18
32 2 letters. Common divisors of these two numbers are 2369, and 18,
and so these are the most likely keyword lengths.
5. Exercise. Use Kasiski’s test to ?nd the more likely keyword lengths in Prob-
lem 1. (Hint: There are repeated strings beginning with , with
and with ).
Solution:
6. Exercise: The ciphertext in Problem 1 contains the following distribution of letters:
letter A B C D E F G H I J K L M
18 31 24 9 9 15 12 12 27 14 17 5 24
letter N O P Q R S T U V W X Y Z
23 28 6 13 29 28 7 5 24 41 20 11 8
Suppose that a pair of letters is selected at random from this text. What is the probability that the two letters selected will be identical?
Solution: ??????
7. Friedman’s Index of Coincidence
The index of coincidence (denoted by I) for a (cipher)text is the probability that two letters selected at random from it are identical. If the text has n0 A’s, n1 B’s, n2 C’s, . . . , n25 Z’s, and
n = n0 + n1+ n2 + … + n25
is the number of letters in the text, then
In the previous exercise, we found I = 0.04713.
8. Example: What is the index of coincidence for a collection of 2600 letters consisting of 100 A’s, 100 B’s, 100 C’s, . . . , 100 Z’s?
Solution: ??????????????
9. Remark. The index of coincidence of a totally random (uniformly distributed) collection of letters is about 0.0385. Vigenere ciphertexts from longer keywords have a more uniform distribution of letters. For keyword lengths closer to 1, the index of coincidence will be larger (closer to 0.0656).
10. Question: Can we quantify the connection between index of coincidence and keyword length?
11. Connection between index of coincidence I and keyword length.
Suppose that the ciphertext has n letters and the Vigenere keyword has k letters. Then
The separation (start to start) between the two occurrences of is
108 33 22 letters, and the separation between those of is 18
32 2 letters. Common divisors of these two numbers are 2369, and 18,
and so these are the most likely keyword lengths.
المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .
|