算法描述    
   隨機(jī)選擇兩個(gè)大的素?cái)?shù) p、q ，且p ≠ q，計(jì)算n = pq、r = (p-1)(q-1)，依歐拉定理，r即為與n互質(zhì)的素?cái)?shù)個(gè)數(shù)；選擇一個(gè)小于r的整數(shù)e（即加密指數(shù)），求得e關(guān)于模r的逆元d（即解密指數(shù)），則{n，e}為公鑰、{n，d}為私鑰；根據(jù)模的逆元性質(zhì)有ed ≡ 1 (mod r)；設(shè)m為明文，則加密運(yùn)算為m^e ≡ c (mod n)， c即為密文；則解密過程 c^d ≡ m (mod n)。
   證明會(huì)用到費(fèi)馬小定理，即 若y為素?cái)?shù)且x不為y的倍數(shù)， 則 x^(y-1) ≡ 1 (mod y)（費(fèi)馬小定理的證明需先證明歐拉定理，此處略）。符號(hào)≡表示同余，^表示冪，|表示整除，*表示相乘。

算法證明
 第一種證明途徑   
   因 ed ≡ 1 (mod (p-1)(q-1))，令 ed = k(p-1)(q-1) + 1，其中 k 是整數(shù)
   則 c^d = (m^e)^d = m^(ed) = m^(k(p-1)(q-1)+1)
   1.若m不是p的倍數(shù)，也不是q的倍數(shù)
      則 m^(p-1) ≡ 1 (mod p) (費(fèi)馬小定理)
         => m^(k(p-1)(q-1)) ≡ 1 (mod p)
      m^(q-1) ≡ 1 (mod q) (費(fèi)馬小定理)
         => m^(k(p-1)(q-1)) ≡ 1 (mod q)
      故 p、q 均能整除 m^(k(p-1)(q-1)) - 1
         => pq | m^(k(p-1)(q-1)) - 1
      即 m^(k(p-1)(q-1)) ≡ 1 (mod pq)   
         => m^(k(p-1)(q-1)+1) ≡ m (mod n)   

   2.若m是p的倍數(shù)，但不是q的倍數(shù)
      則 m^(q-1) ≡ 1 (mod q) (費(fèi)馬小定理)
         => m^(k(p-1)(q-1)) ≡ 1 (mod q)
         => m^(k(p-1)(q-1)+1) ≡ m (mod q)
      因 p | m
         => m^(k(p-1)(q-1)+1) ≡ 0 (mod p)
         => m^(k(p-1)(q-1)+1) ≡ m (mod p)
      故 m^(k(p-1)(q-1)+1) ≡ m (mod pq) 
      即 m^(k(p-1)(q-1)+1) ≡ m (mod n)

   3.若m是q的倍數(shù)，但不是p的倍數(shù)，證明同上

   4.若m同為p和q的倍數(shù)時(shí)
      則 pq | m
         => m^(k(p-1)(q-1)+1) ≡ 0 (mod pq)
         => m^(k(p-1)(q-1)+1) ≡ m (mod pq)
      即 m^(k(p-1)(q-1)+1) ≡ m (mod n)

 第二種證明途徑
   先證明m^ed ≡ m (mod p)恒成立
   1.若p為m的因子，則p | m^ed - m顯然成立，即m^ed ≡ m (mod p)
   2.若p不為m的因子，令ed = k(p-1)(q-1) + 1，則 m^(ed-1) - 1 = m^(k(p-1)(q-1)) - 1
       m^(p-1) ≡ 1 (mod p) (費(fèi)馬小定理)
        => m^(k(p-1)) ≡ 1 (mod p)
        => m^(k(p-1)(q-1)) ≡ 1 (mod p)
        => m^(ed-1) ≡ 1 (mod p)
        => m^ed ≡ m (mod p)
   同理可證m^ed ≡ m (mod q)
   故m^ed ≡ m (mod pq)，即m^ed ≡ m (mod n)
   又因 c^d = m^e^d = m^(ed)
   故 c^d ≡ m (mod n)，證畢
   
總結(jié)
 第二種比第一種簡(jiǎn)單直觀，以上證明途徑對(duì)RSA私鑰簽名與驗(yàn)簽同樣適合。