CSci 4509 Cryptographic Protocols -- Problem set 1.

Problem 1: Affine ciphers (6 points)

Part 1 Inhabitants of northern hemisphere of Mars speak a language that has 20 letters, and martians who live in the southern hemisphere speak a language with 17 letters. Northern martians claim that their Affine Ciphers are harder to break using a brute force attack than those of southern martians because they have more letters.

How many different keys do Affine ciphers have in each martian language? Show all your computations. Which of the two languages is more secure against a brute force attack?

Part 2 All 20 letters of the Northern martian language occur in the language with the same frequency and all possible combinations of letters are equally probable. What's the best way to break an affine cipher for Northern martian language? How does its security compare to that of an affine cipher for English?

Problem 2: frequencies of letters (5 points)

This problem is a collaborative effort. The textbook gives approximate frequencies of English letters. In practice frequencies may vary. Your task is to find three texts of about 1000-2000 characters each, use the program LetterFrequency.java to compute frequencies of letters in the text. Texts must all be in English, but can be of different kinds. Attach the texts and the frequencies analysis to this Wiki page. Summarize your observations: how much can letter frequencies in an individual text differ from the averages? You may use texts submitted by others, in addition to your own.

Extra credit: do you believe that letter frequencies differ significantly depending on the type of text? For instance, is it possible to distinguish texts of the time of Shakespeare from modern texts based on letter frequencies alone? You have to describe your methods and your findings.

Problem 3: cryptanalysis of affine cipher (10 points)

Write a program that will help you decrypt texts encrypted using a substitution cipher. Your program should compute the letter frequencies in a text and possibly make suggestions using the frequencies of English letters given in the textbook.

The following is an encryption of an English text using affine cipher: 

ETWCAIEMDAYWRRWRYLQYALJANGLWNABQZMWLLWRYDGXANMWMLANQRLXADERUERBQZXEJ
WRYRQLXWRYLQBQQRCAQNLIWCAMXAXEBPAAPABWRLQLXADQQUXANMWMLANIEMNAEBWRYD
KLWLXEBRQPWCLKNAMQNCQRJANMELWQRMWRWLERBIXELWMLXAKMAQZEDQQULXQKYXLETW
CAIWLXQKLPWCLKNAMQNCQRJANMELWQR
Use your program to help you decrypt the text. Find out the key (a and b) that it has been encrypted with. Describe the procedure that you followed: what hypotheses did you try? Keep in mind that this is an affine cipher, so a must be relatively prime with 26.

Optional, no extra credit Who is the author of the above text?

Problem 4: invalid keys for an Affine cipher (3 points)

In a language with 33 letters in the alphabet, which letters will have the same encryption as letter number 5 (assuming that the first letter has the number 0) if the cipher uses the key a = 9, b = 1? Show your computations.

Problem 5: Vigenere cipher (4 points)

Alex and Beth decided to use Vigenere cipher for secret communications and came up with this key:
alexandbethdecidedtousevigenerecipherforsecretcommunicationsandcameupwiththiskey
(this is 80 characters).

They start their secret communication by Alex sending the encryption of this message to Beth:

whatareyoudoingthisweekend
(this is 26 characters). Eve intercepts the encrypted message. What are Eve's chances to decrypt the message at this point? Assume that Eve has no way of guessing the key or any part of it.

Beth replies to Alex with the encryption of the following:

whatistheretodo
Beth could use the part of the key that was not used by Alex's message (i.e. start at letter number 27 in the key) or she could start at the beginning of the key (presumably, she can communicate her choice to Alex somehow so that Alex knows what portion of the key to use to decrypt the message). How does each choice affect Eve's ability to decrypt the message?

Problem 6: cryptanalysis of Vigenere cipher (10 points)

The following text is encrypted using Vigenere cipher with the key of length <= 20. Your task is to decrypt the text and to find the key. Describe the procedure that you used, all the hypotheses that you checked, and submit all your computations. 
LBIEWBWKKSECTAJGVIGKIELYTLOVXRTANQIBSLKOUJVFOVWVSXWHREWZXAKGCIQSGUNXJ
RPQGMYIGLHILEFUIGOCCOAMPAGIDLUWLKFTNHYXFARPINZPIGKJWHWBRQVZLIEISUKGGF
UKXVRPWYLLEDAZVHERCXIOEGETZDXSJZULNVRNISCBKMIUFUSKHVTEDKNUYWHXIFXHHZR
FPIOGLTLODRUILLFRFWWRNWXHIHFZKHUDZZPHBEGLBOPGALRBEJRRQVTITFFRVWGGXUXY
WVGTRRUMMCILLRRNWKCCOQWFCMTFCLCXTOGYFFODBEGLPWCOSGUSBRDCHLKLTARWJFSEC
DLNAGOAVZTRFBUFSIKIOJUFRVTKTXSRZQYVRPMFWELDEKIKJRNLLARLEYVVVWYIOFYVVV
WPFUEIWSHYHEELFJVWZTKTHIWVLDXRVXRMCRNXRLHSS
You might want to write a program that will perform some of the computations (in particular, you definitely don't want to compute index of coincidence by hand!). Submit your program together with the results.

Note: the grammar of the text might not be obvious in some places without punctuation marks, but the text is easily recognizable as English.

Optional, no extra credit. How is the keyword related to the text?

Problem 7 (extra credit)

Stinson, exercise 1.22 p.41.

Problem 8: autokey cipher (7 points)

Stinson, exercise 1.28 p.43. You might want to write a program for this one.

Problem 9 (7 points)

Stinson, exercise 1.30 p.43. There is a typo in the book. Please see the correction here. Corrected 2/9/05 and again 3/1/05.
CSci 4509 homepage