﻿ CS233

## Homework 5 (due 2/19) CSC 233

We finished talking about the Vigenere cipher (covering the kappa test, counting coincidences, and Friedman's Index of Coincidence), and saw a similar security failing in master-key systems. We talked about the Playfair cipher and how to perform a known-plaintext attack on it. Next week, we will move on to some early American cryptography and talk in a bit more depth about transposition ciphers.

Mentioned in class:

Submission:

The homework is due by midnight (I will not accept late homeworks). You can submit your homework through d2l into the drop-box for this homework.

Please prepare your homework as a single file containing all answers (e.g. doc, docx, or pdf, not a zip file). For an example, see hwexample.docx . How to take screenshots? Check out screenshots for MAC, Windows, Linux.

1. (Reading) Read Sections 3.1-3.3 on the Vigenere Cipher and how to break it. Section 3.3 contains a detailed discussion of the index of coincidence. (Note that the formula I showed you for the relationship between IC and key-length in class was simplfied (on page 79: ((N/L)-1)/(N-1) is roughly 1/L for large enough N. I worked with 1/L. The spreadsheet implements the formula from the book.)

You can skip Section 3.4 (though it's fun), and move on to 3.5 on autokeys. We will return to 3.6-3.12 later.

Also, read Section 5.4 on the Playfair cipher. (Section 5.5 describes a ciphertext only attack on Playfair, which we did not cover. We performed a known-plaintext attack.) If you want to read ahead, get started on Chapter 4.

2. (Vigenere Cipher, Kasiski test, 7pt) The following text has been encrypted using a Vigenere cipher

DYEMUEHCBZ SRHTNEJWAP RSAPPNTCGT SRXNSMUEHC PCTMUOEAXA HCGTNEXDTF TDTPDYGADY VGREIMCAOQ HPSQTOBWTG EPNAEPHZNC KPNKDOEPPE EJNLCOJLIL IPDUXEHGIE HYISEGHLBJ TEOADYSRGF CRPNINWPRU WTCFCZBMSJ EJHPCYCOEA XAHCG

a) [5pt] Find three repeating sequences of letters  by hand (i.e. don't use any programs), list their distance, and factor the distances. All sequences should have length at least three, and two of them should be longer than three letters.

b) [2pt] Based on your results from a), what are likely key lengths?

Note: you do not have to break this cipher.

3. (Vigenere, 10pt) The following ciphertext was encrypted using a Vigenere cipher with a keyword of length 9.

INMXWLMNXI ACWGGMFLOG HTLDBJSTQE NGIPGJIAGT QTVCXFNICM YBKEEVNRCG CKLYNNONTB KWNPELLWBJ STIECWYMYU ICHPPLITWW BREFMPGLRB UMJXWHMNEA GCETKFGGHP K

Find the keyword and decrypt the text using the vigenece analsyis program we saw in class (available on d2l). Hint: keep in mind that it's possible that the automatic analysis doesn't get all the letters in the keyword right, so keep track of the top choices and offsets for which the top choices seem iffy. The keyword in this case is a recognizable word.

4. (Vigenere Cipher, 10pt) The following text has been encrypted using a Vigenere cipher.

MTCKVRNCIE QZQEDEAJWH ANYNQAZCNY QZGYIMLRDU YXRKVBKAEF FKPEDEOQPX CYRNELMAKD TOAPYMTNKI QKQOUBHWAL CXWLUPYMJU TKLIEBKPWJ CRWWSOAYED RKBSYRNGPJ FGRDUGYYXB CZMYELYRNK AZYYYNNCNM FOADDMHMZO CRQASYTBAS GVFAH

a) [5pt] Determine the key length using the kappa test (counting coincidences for various shifts).  You can assume that the keyword has between 4 and 9 characters. Use the kappa spreadsheet to count coincidences automatically. Write down the results and determine the most likely key length based on the results.

b) [5pt] With the keylength from a) decrypt the text using the vigenere spreadsheet (available on d2l). Was the keylength you got in a) correct?/p>

Warning: the ciphertext contains spaces and line breaks. For the program to work correctly, you need to remove all spaces and linebreaks before analyzing it. 2nd warning:: the keyword is not a word, it's just a meaningless sequence of letters.

5. (Playfair Cipher, 13pt) You have intercepted the following plaintext/ciphertext pair (don't try to make sense of the plaintext ...):

```boldstepforonesoyoungbigshot
NBMCTEPXQFQBTCHTHFWCTNABHIBO```
You suspect a playfair cipher.

a) [13pt] Reconstruct the key matrix used.

b) [2pt] Guess the keyword that was used to construct the key matrix.

Note: Document and explain your approach step by step as we did in class.
Marcus Schaefer
Last updated: February 13th, 2020.