RSA算法原理
2018-07-21 本文已影响0人
苦苦修行
RSA算法的安全基于:大数(两个大质数的乘积)的质因分解目前做不到(以后量子计算机出现了,就可以办到,RSA算法也就不安全了)
知识点准备:
- 啥叫质数(也叫素数):只能被1和本身整除的整数,比如3、5、7等。
- 啥叫因数(也叫约数、因子):A➗B结果为整数,没有余数,则B就是因数。例如:8➗4
- 啥叫质因分解:因数要同时是质数。8➗4中4是因数但不是质数,不符合。21➗3中3是因数也是质数,符合。所有,对21的质因分解得到两个质数:3和7。
- 啥叫互为质数:这两个质数没有共同因数。
需要翻墙观看(OMG,伟大的天朝!):银行密码系统安全吗?质数(素数)到底有啥用?李永乐老师11分钟讲RSA加密算法(2018最新)
RSA算法流程(假设A给B发消息):
- p、q:找到两个质数p、q,比如 p = 3,q = 5
- n:n = p ✖️ q = 15
- φ(n):φ(n) =(p-1)✖️(p-1)= 2 ✖️ 4 = 8
- 公钥e:需满足俩条件:1️⃣、1 < e < φ(n) 2️⃣、e与n互为质数。比如取 e = 7
- 私钥d:需要满足条件:e ✖️ d ➗ φ(n) 余数为1,例如:7 ✖️ 15 ➗ 8 余数为1,取 d = 15
- A方加密:假设发送的信息为数字 m = 2,加密公式为: m^e ➗ n 余数为 c,即 2^7 ➗ 15 余数为 8,即 c = 8
- B方解密:解密公式:c^d ➗ n 余数就是 m(A传过来的数字),即 8^15 ➗ 15 余数为 m = 2
console.log(35184372088832%15)
总结:
- 网络上传输的明文信息有:公钥e、余数c、n
- 基于以上信息,各公司自己设计加密及解密公式