RSA算法详解
测试产品的时候，对签名跟认证很是熟悉。但是对RSA的原理，以及秘钥的关系还是有原理性方面的欠缺。
本文梳理下RSA的加解密流程，以及秘钥的对应关系
关于RSA的认证跟加密的应用，采用如下的方式
认证：私钥签名，公钥认证
加密：公钥加密，私钥解密
RSA算法流程
RSA算法的的原理简单来说就是将一个很大的质数M，很难分解为两个质数a,b,并且a*b=M
详解请参照：
http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html
-
生成秘钥
- 选择两个不相等的质数p,q
- 计算p,q的乘积n
- 计算n的欧拉函数φ(n)=(p-1)*(q-1),计算出来的值就是不大于n且与n互质的整数个数
- 选择一个与φ(n)互质的整数e，且1<e<φ(n)
- 计算e对于φ(n)的模反元素d，计算公式d*e≡1(mod(n))。
- 公钥(n,e),私钥(n,d)。
- 销毁p，q
-
加解密
- 加密
- 发送方向接收方发送明文信息m，发送方使用公钥(n,e)依照如下公式加密：
m^e=c(mod n)
m必须是整数，且小于n。根据上面的公式可以算出密文C
- 发送方向接收方发送明文信息m，发送方使用公钥(n,e)依照如下公式加密：
- 解密
- 接收方获取密文c，使用自己的私钥(n,d)依照如下公式解密
c^d=m(mod n)
c,d,n已知，可以算出明文m
- 接收方获取密文c，使用自己的私钥(n,d)依照如下公式解密
- 加密
从上面的秘钥生成流程中，我们可以发现
如果p,q都销毁了，很难通过公钥(n,e)获取私钥(n,d).反之亦然。以为公式中的φ(n)=(p-1)(q-1),通过n很难得到p，q是本算法的基础
但是通常我们使用的tool生成的私钥中，包含了公钥信息。所以可以通过私钥获取公钥
示例
1. 随机选择两个不相等的质数47和59
2. 二者的乘积为43×57=2773，2773转化为二进制为1010,1101,0101，长度为12位，所以密钥的长度为12位
3. 根据欧拉函数公式φ(n)=n(1-1/p)(1-1/q)计算，φ(2773)= 2773×(1-1/47)(1-1/59)=(47-1)(59-1)=2668
4. 随机选择一个整数e=63，2668>63>1，并且63与2668互质
5. 计算63对于2668的模反元素d，根据公式ed≡1(mod φ(n))，有63d-1=2668k，由欧几里得扩展公式计算d=847
6. 公钥(n,e)=(2773,63)，私钥(n,d)=(2773,847)
- 加密
根据上面计算出的公钥(n,e)=(2773,63)，假如m=244，根据公式m^e=c(mod n)，可计算出密文c=465 - 解密
根据上面计算出的私钥(n,d)=(2773,847)，已知c=465，根据公式c^d=m(mod n)，可计算出明文m=244
版权声明：本文为richard-xiong原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。