Feature Column

 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.

Welcome to the
Feature Column!

These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Read more . . .

Search Feature Column

Feature Column at a glance


Show Archive

Browse subjects



Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement

Connect with us Facebook Twitter Google+ LinkedIn Instagram RSS feeds Blogs YouTube Podcasts Wikipedia