**I just completed the following worksheet for class, but can someone check my work?**

*Suppose you want to receive private messages. To set up a public key system, you pick 2 primes p and q and set n=pq. Then you choose a positive integer e relatively prime with phi (n)=(p-1)(q-1). Suppose you choose p=101 and q=29, so n=2929 and phi(n)=2800.*

Next you choose e=2291 which is relatively prime to phi(n)=2800. The pair (e,n)=(2291, 2929) is your enciphering key.

You now make public (only) your enciphering key. Of course, p and q need to be much larger in real life, so that n will be hard to factor.

Now suppose I have your enciphering key and decide to send you an encrypted message.

Given the value of n, the block size should be m=2 (2 letters per numerical block).

I use the key to encipher a message as follows.

First I translate to a numerical message.

i f t h i s i s m y m e s s a g e

0805 1907 0818 0818 1224 1204 1818 0006 1426

Here we have used the translation table:

A b c d e f g and so on
. to z and then

00 01 02 03 04 05 06 25 26

We added the symbol - since all messages need to have length divisible by m (2 in this case) so we can add a - to make an odd length even.

To encode the first block of message above, I raise 805 to the power e=2291 and take the result mod n=2929 obtaining 1372.

The first couple of blocks of the encrypted example message are 1372 937 2313

Ok, now I am sending you the following message using your enciphering key:

230 1989 362 653 516 1069 2373 571 724 1420

**I figured out the above message, but now I am supposed to send back a message of my own using enciphering key: (e,n)=(7, 3131) using block length m=2.**

Heres what I came up with. Can anyone decode it to let me know I did it correctly:

2891 1202 2045 2069 1188 0072 2337 2863 0919 2891 2691 0102 0880 1581 2691 1931 0571