Homework 19, due Monday, March 14, 2011

[2] 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 RSA cipher y ≡ xe (mod n), with n = 1009961 and e = 97, except now n is not prime, but rather n = pq where p and q are primes. Find the multiplicative inverse d of e mod (p-1)(q-1). To do this you must first find p and q. Then write gcd(e,(p-1)(q-1)), which is 1, as a linear combination d*e + m*(p-1)(q-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 d is the multiplicative inverse of e mod (p-1)(q-1), since d*e ≡ 1 mod (p-1)(q-1); i.e., the number d is our decryption exponent. (If d is negative add (p-1)(q-1) to it to get a positive number for our d.) So now we can decrypt using x ≡ yd (mod n). State what d you found, and then decrypt the original plaintext message.

ciphertext:

935420 314977 408130 523473 155894