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

算法證明
 第一種證明途徑   
   因 ed ≡ 1 (mod (p-1)(q-1))，令 ed = k(p-1)(q-1) + 1，其中 k 是整數
   則 c^d = (m^e)^d = m^(ed) = m^(k(p-1)(q-1)+1)
   1.若m不是p的倍數，也不是q的倍數
      則 m^(p-1) ≡ 1 (mod p) (費馬小定理)
         => m^(k(p-1)(q-1)) ≡ 1 (mod p)
      m^(q-1) ≡ 1 (mod q) (費馬小定理)
         => 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的倍數，但不是q的倍數
      則 m^(q-1) ≡ 1 (mod q) (費馬小定理)
         => 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的倍數，但不是p的倍數，證明同上

   4.若m同為p和q的倍數時
      則 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) (費馬小定理)
        => 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)，證畢
   
總結
 第二種比第一種簡單直觀，以上證明途徑對RSA私鑰簽名與驗簽同樣適合。