Homework 19, due Monday, March 14, 2011
[1] Read pp. 99-106.
[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