[0] Read the introduction to chapter 13 and Section 13.1 of the book, pp. 494-499.
[1] Find the decryption exponent d for the RSA cipher with n = 51
and e = 3. (Do it by hand.)
[2] Find the decryption exponent d for the RSA cipher with n = 1938379
and e = 19. (Use the web site; note that one of the web forms factors a
number if the number is not too big.)
[3] Decipher the following message encrypted using the RSA cipher with n = 1938379
and e = 19:
ciphertext:
258925 1810536 1785120 1068249 1458419
Discussion:
The original 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 = x^e (mod n), with n = 1938379
and e = 19, 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 = y^d (mod n).