算法描述    
   随机选择两个大的素数 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私钥签名与验签同样适合。