CS/ECE/Math 435 Fall 2022 Homework #2
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CS/ECE/Math 435
Fall 2022
Homework #2
Please turn in PDF on Gradescope by 11:59 PM Friday, October 7, 2022 Rules for Homework: See Homework 1.
1. For this problem, we imagine a game between the cryptographer CG and the crypt- analyst CA. CG picks key i with probability pi , i = 1, . . . , m, and uses it to encode a message. (These probabilities are known to both parties.) In attempting to read the message, CA has no recourse but to try keys in some order, stopping when the “correct”one is found.
a) Write down a formula for the expected number of trials, when CA tries keys in the order 1, . . . , m. (For simplicity assume that if only one key remains, it is tested just as were the others.)
b) Show that CA minimizes the expected number of trials by using a“greedy” strategy. That is, the most likely key is tried irst, then the second most likely, and so on.
c) Prove that CG’s best strategy (that is, the one that maximizes the expected number of trials by CA, who is searching optimally) is to choose keys with a uniform distribution.
2. This problem deals with Hill ciphers and linear algebra mod N = 10. The numerical encoding for letters is A = 0, B = 1, and so on.
a) Find a 2 
2 matrix A, invertible over ZN , for which A ( )D(A) = ( )C(B) .
How many such matrices are there? Could I choose any plaintext and any cipher- text and do the same task?
b) Use reversible row operations to transform the matrix
|
\ 4(2)
E =
|
4 5 8 0 |
5 8 6 2 |
6(0)
4(5)) |
into upper-triangular form, and thereby ind its determinant. Record both the row operations you did and the intermediate results. (Hint: you should discover that E is invertible.)
c) Continue the work of b) and ind E’s inverse matrix D . Check that you got it right by starting with the plaintext CHAD, encrypting it with E, and then decrypting it with D to recover the plaintext.
3. The following ciphertext was generated by taking English plaintext and applying an unknown a
ne transformation to the letters. (Assume A = 0, B = 1, . . ..)
ZYPML YTXYH YBYNM DEYVT MPDMC TINCA CTYEC IVHYN YQTLO QINTL
IVCEO CCOMV MPOVP MLEIT OMVTX YKCKI NEIVV YLMPC YVHOV GIQME
EKVOQ ITOMV SICZA DLOBI TYEYC CYVGY L
a) Make a frequency table for the letters A–Z, indicating how often each letter ap- pears. Compute the index of coincidence from your frequency table, and verify that it is consistent with the idea that only one transformation was used.
b) Use correlation analysis to identify the most“likely”a, b that were used for the encryption function e(x) = ax +b mod 26. (There are 312 pairs, so you will need computer skills.)
c) For the encrypting pair you found, ind the corresponding decrypting pair and use that transformation to recover the plaintext.
2022-11-03