[note]about RSA

#
#    I use the ssh client to connect my iPhone today,
#    the ssh configuration file "known_hosts" confuses me .
#    I search RSA at wikipedia.org. I write this for
#    reference later.
#                Feb,9,2009    17:00 UTC+8
#                nikky
#

The RSA algorithm

computing step
1 select 2 prime p,q
2 compute n=p*q
3 compute Euler's totient phi(n)
4 randomly choose e such that 1 < e < phi(n) and gcd(phi(n),e) = 1
5 compute d*e = 1 mod phi(n)

e is the public key
d is the private key

Encryption
    m = c^e (mod n)                eq.1

Decryption
    c = m^d (mod n)                eq.2


Proof
    For decryption, substititing eq.1 into eq.1, we obtain
    c' = c^(e*d) (mod n)            eq.3

    According to Euler's totient theorem, that
    e*d = 1 (mod n)
    e*d = 1 + k * phi(n)             eq.4

    Substituting eq.4 in to eq.3, yield
    c' = c^(1 + k * phi(n)) (mod n)
    c' = c * (c^k)^phi(n) (mod n)        eq.5

    According to Euler's totient therem, that

    (c^k)^phi(n) = 1 (mod n)              eq.6

    Substituting eq.6 to eq.5, we get
    c' = c                    Done