[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).