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
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):
b --> B = bk (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
so that raising each of the transmitted numbers to the power s will undo the encryption:
B --> Bs (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 = p · q. 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 could take, with today's best methods, practically speaking forever.
Back to the previous codes page.
Back to the first codes page.