Read the latest issue of Notices  Read the latest issue of Bulletin  Shop in the AMS Bookstore  My Account | Cart  
 
American Mathematical Society   
From Euclid to public-key codes 3

 From Euclid and Euler to Public-Key Codes

How does a public-key code work?

The RSA system works as follows. You pick two large primes p and q and publish their product N, your ``modulus'', along with a number k chosen to be relatively prime to (p-1)(q-1).

Need to review? relatively prime

The combination (N, k) is your public key. If correspondent X wants to send you a message, X first converts it to numerical form in some standard way and breaks that numerical message into blocks of length less than the length of N. So the message now looks like

a, b, ... ,

where each of a, b, etc., is a number less than N. Now X encrypts the message by raising each number to the power k (mod N):

a --> a^k (mod N)

b --> b^k (mod N)

...

and sends you the message A, B, ... .

Need to review? congruence mod N

Meanwhile, you have calculated your secret key (N, s), where N is your public modulus and s is the multiplicative inverse of k (mod (p - 1)(q-1)). More about this calculation below. This choice of s guarantees that for any number z

(z^k)^s = z (mod N)

so that raising each of the transmitted numbers to the power s will undo the encryption:

A --> A^s (mod N) = a

B --> B^s (mod N) = b

...

(since the numbers a, b, etc., are smaller than N, the congruence specifies them exactly). Then the original message can be easily reconstructed.

Note that the secret key cannot be constructed from the public key without the knowledge of the factorization N=pq. Otherwise there is no way to access the number (p - 1)(q - 1) used in the calculation. If N is large enough, for a stranger to discover your factorization it could take, even with today's best methods, practically speaking, forever.

On to the next codes page.

Back to the previous codes page.

Back to the first codes page.