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". Thus "711013" corresponds to "A c" and "113037" corresponds to "at.". Each 6 digit number x was then encrypted to give a number y using the cipher y = x^e (mod p), with p = 1000003 and e = 9347. One way to decipher the ciphertext would be to take each possible string of 3 characters, turn it into a 6 digit number, and then encrypt the number to make a lookup table with every possibility. Then we could find each encrypted number in our lookup table, and look up what the original number was. For example, "at." turns into the number 113037, which encrypts to 720454. We could just find 720454 in our lookup table and see that it came from 113037 which gives "at.". The problem is that our original table above has 90 entries and we're using a blocksize of 3 characters to make up our 6 digit numbers, so there are 90*90*90=729000 possible numbers for each block. Thus our lookup table would have 729000 entries. It would take a while to work out the lookup table to begin with since it would be so big, and it would be awkward to find things in it. It might be doable with a fast computer, but if we used a blocksize of 6 characters rather than 3, the lookup table would need to have 90

So the only reasonable way to decipher the secret message is to break the code mathematically. To do this, find the multiplicative inverse e mod p-1; i.e. write gcd(e,p-1), which is 1, as a linear combination n*e + m*(p-1) = 1. This is easy to do using Euclid's algorithm, but you don't have to do it by hand; you can use the web form here to do the arithmetic 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 = y^d (mod p).

Problem [1]: Find the decryption exponent d if e = 9347 and p = 1000003.

Problem [2]: Decrypt the ciphertext below to determine the original plaintext message.

ciphertext:

260546 436187 849652 408378 894855

260546 436187 849652 408378 835699