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.