异想天开

What's the true meaning of light, Could you tell me why

RSA算法过程

日期:2014-10-31 20:09:24
  
最后更新日期:2014-11-13 14:10:45
【技术】
如果已经了解了RSA算法的专家,请忽略。
背景知识:
《数论中的欧拉定理-RSA算法数学基础》一文

算法过程: 1.选定两个大质数p和q。计算N=pq。 2.随意选择一个数e,(N,e)即为私钥。 3.解下列同余方程,计算d
ed mod (p-1)(q-1) = 1
(N,d)即为发布出去的公钥。

加密过程: 假设加密数n(总有方法将你要加密的内容分割为一个个数),则用私钥(N,e)加密方法 n^e mod N = c ,c即为你加密后得到的。
解密过程: 已知你的公钥(N,d),解密c^d mod N 可以证明该值为n。
注意:一般n是要小于p,q的
证明: c^d mod N = n ^ed mod N
由ed mod (p-1)(q-1) = 1
得到: ed = k(p-1)(q-1)+1
那么: n^ed mod N = n^[k(p-1)(q-1)+1] mod N
若n与N互质(即没有公共因子),而N=pq,p,q都为质数,由欧拉定理:
n^[(p-1)(q-1)] mod N = 1,那么 n^[k(p-1)(q-1)+1] mod N = n 。

若n与N不互质(即有公共因子),而N为p和q的乘积,故a只能为p或q的倍数。假设n=ap,n为q的倍数时,同理可证。
那么:(ap)^[k(p-1)(q-1)+1]
由于n=ap,那么a是与n互质的一个数,则a^[k(p-1)(q-1)+1] mod N =a
那么p^[k(p-1)(q-1)+1] mod N呢?
考虑p,q互质,有:p^[k(p-1)(q-1)] mod q = 1 ,则 p^[k(p-1)(q-1)] = mq+1,p^[k(p-1)(q-1)+1] = p(mq+1)
合起来:
(ap)^[k(p-1)(q-1)+1] mod N = ap(mq+1) mod N = ap = n。得证。
该算法可以用于:
1.用于加密和解密:公钥加密,私钥解密。
2.验证签名:私钥加密,公钥解密。