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