Homework 18, due Friday, March 11, 2011
[1] A plaintext message was converted into a string of 2-digit numbers using the following table:
10: space 11: a 12: b 13: c 14: d 15: e 16: f 17: g 18: h 19: i
20: j 21: k 22: l 23: m 24: n 25: o 26: p 27: q 28: r 29: s
30: t 31: u 32: v 33: w 34: x 35: y 36: z 37: . 38: , 39: ;
40: : 41: ? 42: ! 43: ( 44: ) 45: $ 46: # 47: - 48: [ 49: ]
50: 0 51: 1 52: 2 53: 3 54: 4 55: 5 56: 6 57: 7 58: 8 59: 9
60: + 61: = 62: % 63: ^ 64: & 65: * 66: { 67: } 68: \ 69: '
70: ` 71: A 72: B 73: C 74: D 75: E 76: F 77: G 78: H 79: I
80: J 81: K 82: L 83: M 84: N 85: O 86: P 87: Q 88: R 89: S
90: T 91: U 92: V 93: W 94: X 95: Y 96: Z 97: < 98: > 99: carriage return (end of line)
For example "A cat." would turn into "71 10 13 11 30 37".
The string was then broken into groups of 6 digits, so for example
"A cat." would become "711013 113037". Each 6 digit number x was then encrypted
to give a number y using the cipher y ≡ xe (mod p), with p = 1000003
and e = 9347. Find the multiplicative inverse d of e mod p-1. To do this write gcd(e,p-1), which is 1,
as a linear combination n*e + m*(p-1) = 1, using Euclid's algorithm,
as done in class; you can use the web form
here to do the work for you. The number n is the
multiplicative inverse of e mod p-1, since n*e ≡ 1 mod p-1; i.e.,
the number n is our d. (If n is negative add p-1 to n to get a positive number for our d.)
So now we can decrypt using x ≡ yd (mod p). State what d you found, and
then decrypt enough of the the ciphertext to determine the source of the original plaintext message.
(If you decipher the first 16 characters in the original message, you'll have enough to
identify the source using google, if you don't already recognize it!)
ciphertext:
707286 316831 295380 154312 713263 622073 78346
414628 532836 777441 591445 226983 335824 374407
671602 435698 365458 375131 6458 70863 737649