Cryptography-Problem Set 2

Cryptography 

Problem Set 2 
Problem 4. For this problem you are to implement the ciphertext-only cryptanalytic method for
substitution ciphers described in class and in the paper by Diaconis. You can use C, C++, Python, Java,
or Go. Email the TAs for permission to use a different language.
Our version of the enciphering scheme works as follows. The key is a random permutation " on the
set Σ = fa; : : : ; zg of lowercase English letters. A message is a string M = M1 · · · Mm of arbitrary
bytes. For each i 2 [1::jMj], if Mi 2 Σ then let Ci = "(Mi); otherwise let Ci = Mi. The ciphertext is
C = C1C2 · · · Cm. We use the same algorithm to decipher except that the inverse permutation f = "−1
is then the key.
Compute bigram (two-letter) frequencies of English based on the English translation of War and Peace,
by Leo Tolstoy. You can find a lower-case version of it at
http://web.cs.ucdavis.edu/ rogaway/classes/127/spring16/war-and-peace.txt
Then decipher the following ciphertext using Diaconis’s method:
qkne l knixw tkn onixenw iytxrerjnx,
qkne tkn uxrray, tkn almbxny, qnxn xiemnw le crobjey hnarxn jn,
qkne l qiy ykrqe tkn ckixty iew wlimxijy, tr iww, wlvlwn, iew jniybxn tknj,
qkne l ylttlem knixw tkn iytxrerjnx qknxn kn onctbxnw qltk jbck iuuoibyn le tkn
onctbxn xrrj,
krq yrre beiccrbetihon l hncijn tlxnw iew ylcd,
tloo xlylem iew molwlem rbt l qiewnxnw raa hz jzynoa,
le tkn jzytlcio jrlyt elmkt ilx, iew axrj tljn tr tljn,
orrdnw bu le unxanct ylonecn it tkn ytixy.
About how many iterations (steps) did you need until the ciphertext was decrypted? Submit the plaintext
as well as your program.
Hints
You will compute a table M that maps a bigram (a; b) 2 Σ2 to its frequency M[a; b] 2 [0; 1]. As described
in class, the plausibility of a deciphering key f relative to C is then defined as
Pl(f) =
n−1
Y i
=1
M[f(Ci); (Ci+1)]
Due to the tiny sizes of numbers, you will probably want to work with ln(Pl(f)) instead of Pl(f). Taking
the natural log of both sides yields:
ln(Pl(f)) =
n−1
X i
=1
ln M[f(Ci); f(Ci+1)]
To maximum of Pl(f) corresponds to the maximum of ln(Pl(f)).
Here is an example of a C procedure to generate a pseudorandom number in some range:
int randin t ( int min , int max) f
unsigned long bin s = max − min + 1 ,
rand s = ( unsigned long )RAND MAX + 1 ,
b i n s i z e = rand s / bin s ,
ov e rfl ow = rand s % bin s ;
int r ;
do f
r = rand ( ) ;
g while ( rand s − ov e rfl ow <= ( unsigned long ) r ) ;
return r / b i n s i z e + min ;
g
Most languages provide a library implementation of something like this. In Python, for example, you
would use random.randint().
Finally, here is an example of a C program to generate a biased coin flip (1 with probability about p and
0 otherwise).
int b e r n o u l i ( double p ) f
double r = ( double ) rand ( ) / ( double )RAND MAX;
return ( r <= p ) ;
g
Again, none of these example mean that you need to program in C.