Intro to Computer Security Homework 2: Cryptanalysis

Solve both of the following problems. You will probably want to write some short programs to help;

submit them along with your answers. This might be a good opportunity to try Python, but you may

use any common language or numerical package.

1. Here is some ciphertext that was produced with a Vigenère cipher:

GERGHDEVNIYMXQXUXGFPAXVVVOCBWGNUMDDXRVYBXOYRLWCGQIPNISRMQZNEWRYXVHEWCR

LRIISHCRPXFTIFMEWGOGRMRLTOAJIQTUJTPWNKZSHKSEXXSCCVNECMXRMFTSCJRGBGJHGS

GGBEUPLHNGRZNXMAZGFDRSPHCGIFEGHMSGASZXKVTGRSELSCAIBYRRKCVFTIWTQEAWNVXA

LNKVFTJEGXUHDTEEBFIHYWCXTHHGRVGWCGKEGBFBHCGHKZHNQYPARGSYXNVFBUGHRGKWPJ

MGRUOIYMAMVUGGXLTLHWCRGBTOIGSATERCMREXGISGEGBFBBMHRKEQGWTGHXFPNLLBEHTP

WRVKGIFIQBJQXNPVGVGDDQNMYSBYXVVJQDKTHMVFHAMRGTSPLHREVQIPMPTCSCEMAXVFXL

KZHUSGLGERGHDEVNIYMXQLRTMWAWFNLVRDLQNMYSBYXVVRZIFIBKPOCBGBFGIICVFVZSCA

ICKRQIGGRVIMERSTKRDWGGNEXCGGXUFJOGCHRLZUCCHNKFICBGBFGIIYXVHEOAFEEWESHQ

EFLLAERMBGJAPIMAZJIRFEYZFFXRLZLYOGBXBUISPIMAIIORRMPXSMPLCNWMSGQEERZHXQ

XUXFFTRMPTCZNNSFLZPACXBUISPIWHVYOHWWGXDPJRMGBJWCDINLZPACXBWFGDZCNGPYCM

AAIIORRMPTCATYRFVIMERSYHXMGCPNMVRICGUGFZDECUTJFPGWRWRBJKFRKFTACKNEZGHS

IFMYSTJIPMICCGGSKFBIGIEYFICBEGBFBLYWVGMCATIQBEORYWRBEHWCYABKSSQXNMVGLF

MPAHITQXVHESSULRMYSGPIDNZFXLKFNJDTAXRWTFXKMATCGIMTEHMWSCXUXZFSCGERGHXM

RXXPGIMPNPVBUMVPXDSCRMFNEQDLWGBKIIGSATCHWCISYRFVSIQMYOIRLVLZGPTMBERHXM

RBYKVTPMTAKCULSGUVWCEJBKTSSRSVGTFXKMATKSDLIFXCTPQKVOVBXLXUXWWURLNFVBSK

Assume that encrypting with the key letter A results in no change, B results in an increment by

one place in the alphabet, C results in an increment by two places, etc.

What is the key? (Please show your work.)

2. Here is a table of the relative frequency of letters in English text:

A: 8.167% B: 1.492% C: 2.782% D: 4.253% E: 12.702% F: 2.228% G: 2.015%

H: 6.094% I: 6.996% J: 0.153% K: 0.772% L: 4.025% M: 2.406% N: 6.749%

O: 7.507% P: 1.929% Q: 0.095% R: 5.987% S: 6.327% T: 9.056% U: 2.758%

V: 0.978% W: 2.360% X: 0.150% Y: 1.974% Z: 0.074%

Here is some plaintext:

ethicslawanduniversitypoliciestodefendasystemyouneedtobeabletothinklik

eanattackerandthatincludesunderstandingtechniquesthatcanbeusedtocompro

misesecurityhoweverusingthosetechniquesintherealworldmayviolatethelawo

rtheuniversitysrulesanditmaybeunethicalundersomecircumstancesevenprobi

ngforweaknessesmayresultinseverepenaltiesuptoandincludingexpulsioncivi

lfinesandjailtimeourpolicyineecsisthatyoumustrespecttheprivacyandprope

rtyrightsofothersatalltimesorelseyouwillfailthecourseactinglawfullyand

ethicallyisyourresponsibilitycarefullyreadthecomputerfraudandabuseactc

faaafederalstatutethatbroadlycriminalizescomputerintrusionthisisoneofs

everallawsthatgovernhackingunderstandwhatthelawprohibitsyoudontwanttoe

nduplikethisguyifindoubtwecanreferyoutoanattorneypleasereviewitsspolic

iesonresponsibleuseoftechnologyresourcesandcaenspolicydocumentsforguid

elinesconcerningproperuseofinformationtechnologyatumaswellastheenginee

ringhonorcodeasmembersoftheuniversitycommunityyouarerequiredtoabidebyt

The population variance of a finite population X of size N and mean µ is given by

Var(X) = 1

N

N

Â

i=1

(xi µ)

2.

(a) What is the population variance of the relative letter frequencies in English text?

(b) What is the population variance of the relative letter frequencies in the given plaintext?

(c) For each of the following keys — yz, xyz, wxyz, vwxyz, uvwxyz — encrypt the plaintext

with a Vigenère cipher and the given key, then calculate and report the population

variance of the relative letter frequencies in the resulting ciphertext. Describe and briefly

explain the trend in this sequence of variances.

(d) Viewing a Vigenère key of length k as a collection of k independent Caesar ciphers,

calculate the mean of the frequency variances of the ciphertext for each one. (E.g., for

key yz, calculate the frequency variance of the even numbered ciphertext characters

and the frequency variance of the odd numbered ciphertext characters. Then take their

mean.) Report the result for each key in part (c). Is the mean variance like those

observed in part (b)? Part (c)? Briefly explain.

(e) Consider the ciphertext that was produced with key uvwxyz. In part (d), you calculated

the mean of six variances for this key. Revisit that ciphertext, and calculate the mean of

the frequency variances that arise if you had assumed that the key had length 2, 3, 4, and

5. Does this suggest a variant to the Kasiski attack? (Don’t say no!) Briefly explain. ⇤

2

Submission Template

# Problem 1:

key=XXXXXXXXXX

show_your_work_here …

# Problem 2:

part_a_var_english=0.0000000

part_b_var_plaintext=0.0000000

part_c_var_ciphertexts=[0.0000000, 0.0000000, 0.0000000, 0.0000000, 0.0000000]

part_c_explain=”briefly_describe_and_explain_trend …”

part_d_means=[0.0000000, 0.0000000, 0.0000000, 0.0000000, 0.0000000]

part_d_explain=”briefly_compare_and_explain_results …”

part_e_means=[0.0000000, 0.0000000, 0.0000000, 0.0000000]

part_e_explain=”briefly_explain_attack_variant …”

show_your_work_here …

3