Re: RSA examples required

[Derek Atkins <warlord@MIT.EDU>]

Here is the response I sent to Peter Simons:

Well, your example that you sent isn't even correct!  Your example
said:

        p = 5    q = 7

        xy = 4*6+1 = 25         x=5
                                y=5

Well, you just chose some bad primes.  Here is a better example:

     p = 5   q = 11  N = pq = 55
     m = (p-1)(q-1) = 4*10 = 40

Now, we need to choose our public and private decryptors, E and d,
such that Ed = 1 mod (m):
     E = 3   d = 27

So, the Public Key (N, E) is (55, 3) and the Private (Secret)
Key (p, q, m, d) is (5, 11, 40, 27).  Now, to encrypt a message,
S, you take C = S^E mod N, and to decrypt you get S = C^d mod N.

So, say the message you want to send is, oh, "8" (for lack of a
better example off the top of my head).  So, you try to encrypt this
message, and you get:
     C = 8^3 mod 55 = 512 mod 55 = 17

You then send this message to the recipient, who then calculates
the message back:
     S = 17^27 mod 55 = 1667711322168688287513535727415473 mod 55 = 8

And you get the original message back.

-derek