Solve the following cryptographic problem.


You have found one small piece of matching plaintext and ciphertext for a Hill cipher using a 2x2 matrix key with mod 17 entries. In particular, the plaintext (12, 5) maps to the ciphertext (14, 10). (Note that these entries typically appear as column vectors when the encryption is applied.) Using this given information and nothing else, how many possible keys could there be? List two of these possible keys.
 Let the encryption matrix be
.  Then we have the following equations:

12a + 5b = 14 mod 17
12c + 5d = 10 mod 17

Solve these equations for a and c respectively:

12a = (14 – 5b) mod 17
a = (12-1 mod 17)(14 – 5b) mod 17

12c = (10 – 5d) mod 17
c = (12-1 mod 17)(10 – 5d) mod 17

Now, notice that plugging in each of the 17 possible values of b yields a solution for a and plugging in each of the 17 possible values of d yields a solution for c. Thus, the total possible number of keys seems to be 17*17 = 289. But, some of these keys give a determinant equivalent to 0 mod 17, which is not permissible. To see this, using the equations above and solving for the determinant ad-bc eventually yields the expression: 8+2b+4c. We can set this to 0, and quickly show that there are 17 combinations of values for b and c that have this equal to 0. (Once b and c are set, so are a and d.) Thus, we must subtract 17 from our original answer to yield a final answer of 272 possible total keys. To find two of these, simply plug in two sets of values for a and b above and one set of values for c and d. For example:

a = 4+b (mod 17), two solutions to this are a=5,b=1 and a=6,b=2.
The other equation simplifies to d = 2+c (mod 17). One solution to this is d=3, c=1. So two possible keys are

 and 


(Note: I skipped several algebra steps including finding inverse to shorten this explanation. If you want to see these steps, please come to my office. This question was slightly more difficult than I intended. So, I will only take off 1 pt. of credit if an answer of 289 was given to the first question.)

0 comments:

Feel free to contact the admin for any suggestions and help.