A plaintext message was converted into a string of 2-digit numbers using the following table (it has 99-10+1 = 90 entries):
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 906 = 531,441,000,000
entries, and if we used blocks of 9 characters we would need a lookup table with
909 = 387,420,489,000,000,000 entries. That's too big even for a computer.
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