非对称加密算法RSA全过程

曹悦芬 2016-11-29

展开全文

昨天跟大家简单介绍了什么是非对称密码体制，今天就来讲一下非对称加密算法RSA全过程：

首先，我们来了解一下公钥加密：

非对称加密算法RSA
密文=（明文）emod n
明文=（密文）dmod n
私钥={d，n}
公钥={e，n}

RSA算法过程（1）
密钥产生
① 选择p和q。其中p和q都是素数，且p和q不相等；
② 计算n=pq；
③ 计算H(n)=(p-1)(q-1)；
④ 选择整数e，使之满足gcd(H(n)，e)=1，1< e< H(n)；
⑤ 计算d，使之满足(d*e) mod H(n)=1；
⑥ 等到公钥PU={e,n}，私钥PR={d,n}。
RSA算法过程（2）
加密
明文M
解密
密文C

RSA示例
首先产生公钥和私钥
① 选择了两个素数，例如选择p=11，q=12
② 现在计算n=pq，这意味着n=11*12=142
③ 现在必须计算H(n)=(p-1)(q-1)=10*12=120
④ 选择对于H(n)=120的一个互质数为e，这里选择e=7
⑤ 必须决定d，以便使(d*e) mod H(n) =1，因此(d*7)mod 120=1，并且d必须小于120
可以得到d=102（102乘以7等于721.721除以120等于6，余数为1）
⑥ 私钥是{102，142}
⑦ 公钥是{7，142}
如果希望发送的消息为9（明文），可以使用加密公式：密文=97 mod 142=48
收到加密之后，要使用解密算法：明文=48102 mod 142=9
加解密的过程如图所示：