(1) Person A selects two prime numbers. We will use p = 23 and q = 41 for this example, but
keep in mind that the real numbers person A should use should be much larger.
(2) Person A multiplies p and q together to get pq = (23)(41) = 943. 943 is the \public key",
which he tells to person B (and to the rest of the world, if he wishes).
(3) Person A also chooses another number e which must be relatively prime to (p 􀀀 1)(q 􀀀 1).
In this case, (p 􀀀 1)(q 􀀀 1) = (22)(40) = 880, so we could choose the number e = 7. This
5
number e is also part of the public key, so B also is told the value of e. [see footnote4 for a
remark on why we're using the number (p 􀀀 1)(q 􀀀 1).]
(4) Now B knows enough to encode a message to A. Suppose, for this example, that the message
is the number M = 35.
(5) B calculates the value of C = Me(mod N) = 357(mod 943).
(6) 357 = 64339296875 and 64339296875(mod 943) = 545. The number 545 is the encoding
that B sends to A.
(7) Now A wants to decode 545. To do so, he needs to nd a number d such that ed =
1(mod (p 􀀀 1)(q 􀀀 1)), or in this case, such that 7d = 1(mod 880). A solution is d = 503,
since 7 503 = 3521 = 4(880) + 1 = 1(mod 880).
(8) To nd the decoding, A must calculate Cd(mod N) = 545503(mod 943). This looks like
it will be a horrible calculation, and at rst it seems like it is, but notice that 503 =
256+128+64+32+16+4+2+1 (this is just the binary expansion of 503). So this means
that
545503 = 545256+128+64+32+16+4+2+1 = 545256545128 5451:
The line above just uses basic rules about how exponents work. Now since we only care about the
result (mod 943), we can calculate all the parts of the product (mod 943). By repeated squaring of
545, we can get all the exponents that are powers of 2. For example, 5452(mod 943) = 545 545 =
297025(mod 943) = 923. Then square again: 5454(mod 943) = (5452)2(mod 943) = 923 923 =
851929(mod 943) = 400, and so on. We obtain the following table:
5451(mod 943) = 545
5452(mod 943) = 923
5454(mod 943) = 400
5458(mod 943) = 633
54516(mod 943) = 857
54532(mod 943) = 795
54564(mod 943) = 215
545128(mod 943) = 18
545256(mod 943) = 324
So the result we want is:
545503(mod 943) = 324X18X215X795X857X400X923X545(mod 943) = 35