RSA system works as follows : We use two large primes p and q, n = pq, and compute the "encrypt key" e by gcd(e,(p-1)(q-1)) = 1. At the same time, the "decrypt key" d can be found; d is an inverse of e mod (p-1)(q-1).

Note :
a* a º 1 ( mod m )
a* is an inverse of a modulo m.

Let John be a person who want to send a secret message to Mary. Mary generates e,d,n as explained above and publishs two keys to the public: e, n. The d is kept as the secret decrypt key by Mary herself. John uses e, n to encrypt his message, let it be M, (the message is considered to be a block of number not larger than n),

C = M^e mod n

John sends the encrypted message C to Mary. Upon receiving C, Mary decrypts the message using her secret key d, by

M = C^d mod n

Proof

if d e º 1 (mod (p-1)(q-1) ), there is k such that d e º 1 + k(p-1)(q-1)
C ^d = ( M ^e ) ^d = M ^{d e} = M ^{1 + k(p-1)(q-1)}

by Fermat’s little theorem
M ^p-1 (mod p ) = 1;  M ^q-1 (mod q ) = 1

C ^d º M . (M ^p-1 ) ^k(q-1) º M (mod p);  C ^d º M . (M ^q-1 ) ^k(p-1) º M (mod q )

gcd(p,q ) = 1, follows by Chinese Remainder Theorem
C ^d º M (mod pq)     QED.

Fermat's Little Theorem
Let n be prime then a ^n-1 mod n =1   ;  1 <= a <= n -1

Chinese Remainder Theorem

Sun-Tsu : There are certain things whose number is unknown. When divided by 3, the remainder is 2; when divided by 5, the remainder is 3; and when divided by 7, the remainder is 2. What will be the number of things?

Let m₁, m₂, . . . m_n be pairwise relatively prime positive integers. The system
x º a₁ (mod m₁)
x º a₂ (mod m₂)
. . .
x º a_n (mod m_n)

has a unique solution modulo m = m₁m₂ . . . m_n. That is, there is a solution x with 0 <= x < m, and all other solutions are congruent modulo m to this solution.

Example : Sun-Tsu
x º 2 (mod 3)
x º 3 (mod 5)
x º 2 (mod 7)

Let m = 3 . 5 . 7 = 105, M₁ = m/3 = 35, M₂ = m/5 = 21, and M₃ = m/7 = 15. We see that 2 is an inverse of M₁ = 35 modulo 3, since 35 º 2 (mod 3); 1 is an inverse of M₂ = 21 modulo 5, since 21 º 1 (mod 5); and 1 is an inverse of M₃ = 15 (mod 7),
x º a₁ M₁ y₁ + a₂ M₂ y₂ + a₃ M₃ y₃ = 2 . 35 . 2 + 3 . 21 . 1 + 2 . 15 . 1 ( mod 105)
= 233 º 23 (mod 105)

23 is the smallest positive integer that is a simultaneous solution. Ans.

Exponentiation

Function expoiter(a, n)
    i = n; r =1; x =a;
    while i > 0 do
        if i is odd then r = rx
        x = x^2
        i = i div 2
    return r

Function expomod( a, n, z )     // a ⁿ mod z
    i = n; r = 1; x = a mod z
    while i > 0 do
        if i is odd then r = rx mod z
        x = x ^ 2 mod z
        i = i div 2
    return r