Homework 17, due Wednesday, March 9, 2011

[1] Using the encryption method discussed in class I encrypted a plaintext message, but this time I used e = 17 as the encryption exponent, so now the encryption works by taking the number x of a letter (as specified below) and finding the number y of the encrypted letter, using the formula y ≡ xe mod 29. Here is how we assigned numbers to the letters in class:
```a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z
2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
```

Here is the encrypted message I got using e = 17 as the encryption exponent:

qfs nx rcl snqrlm fw fdm hnxefqrlqr

Find the decryption exponent d and decrypt enough of the message to identify the source of the original plaintext message. You can use the web forms here to do the arithmetic for you.

Recall: To decrypt this message you must find the decryption exponent d. To find d you must solve the equation d*e ≡ 1 (mod 28); i.e., d is the multiplicative inverse of e mod 28. Since e = 17, this is: 17d ≡ 1 (mod 28). Another way to say this is that d times 17 leaves a remainder of 1 when divided by 28. So you can find d by guess and check: try 1*17, 2*17, 3*17 etc until you find which multiple of 17 has a remainder of 1 mod 28. An even faster way to get d is to use the web form to execute Euclid's algorithm to write 1=gcd(17,28) as a linear combination of 17 and 28. The answer will be: 17d + m28 = 1, which just means that 17d ≡ 1 (mod 28). (If d > 0, you have d. If d < 0, keep adding 28 to d until you get a positive number.)

When you have d, you can then decrypt using the decryption formula
x ≡ yd mod 29.