RSA加密算法原理及JS实现

1976年以前，加密世界主要采用对称加密算法（Symmetric-key algorithm）。

对称加密存在让人头疼的问题：甲乙双方通信，甲方必须把加密规则告诉乙方，否则无法解密。

保存和传递密钥无法确保安全？

1976年，两位美国计算机学家Whitfield Diffie 和 Martin Hellman，"DH密钥协议算法"。

如上所示，Alice和Bob同时拥有了共享密钥K，私钥a,b也未在互联网上传播，且公开的A\B\g\p在短时间内无法破解出a,b,K。因此DH算法便可以在不安全的网络上协商出密钥，基于此构建安全的加密通道。

这个算法启发了其他科学家。人们认识到，加密和解密可以使用不同的规则，只要这两种规则之间存在某种对应关系即可，这样就避免了直接传递密钥。这种新的加密模式被称为 **"非对称加密算法"**。

如果公钥加密的信息只有私钥解得开，那么只要私钥不泄漏，通信就是安全的。

1977年，三位数学家 Rivest、Shamir 和 Adleman 设计了一种算法，当时他们三人都在麻省理工学院工作。RSA 就是他们三人姓氏开头字母拼在一起组成的，可以实现非对称加密。从那时直到现在，RSA算法一直是最广为使用的"非对称加密算法"。毫不夸张地说，只要有计算机网络的地方，就有RSA算法。

在RSA算法中，加密密钥（即公开密钥）PK是公开信息，而解密密钥（即秘密密钥）SK是需要保密的。加密算法E和解密算法D也都是公开的。

据NSA前通讯员斯诺登所提供的机密文件显示，NSA跟RSA达成了一份价值1000万美元的合同，前者通过在后者的加密软件中植入一个缺陷公式，为自己留了一道“后门”。据悉，RSA存有缺陷公式的软件叫做Bsafe，而该缺陷公式的名字为Dual Elliptic Curve，它由NSA开发而出。

BSafe是很多企业级用户采购安全软件，此举将让NSA通过随机数生成算法Bsafe的后门程序轻易破解各种加密数据。

根据数论，寻求两个大素数比较简单，而将它们的乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。

密钥生成过程

第一步：随机p，q

质数（素数）：一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数（规定1既不是质数也不是合数）。

代码实现：

也就是a的φ(m)次方被m除的余数为1。或者说，a的φ(m)次方减去1，可以被m整除。

比如，3和7互质，而7的欧拉函数φ(7)等于6，所以3的6次方（729）减去1，可以被7整除（728/7=104）。

譬如求3和5互质，根据欧拉定理：

欧拉定理有一个特殊情况。

假设正整数a与质数p互质，因为质数p的φ(p)等于p-1，则欧拉定理可以写成:

这就是著名的费马小定理。它是欧拉定理的特例。

欧拉定理是RSA算法的核心。理解了这个定理，就可以理解RSA。

模反元素

模反元素也称为模倒数，或者模逆元。

一整数a对同余n之模逆元是指满足以下公式的整数 b：

公式为定理，如何推倒请看定理的推导过程。

也可以写成以下的式子（定理）：

或者：

解释：如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。

这时，b就叫做a的"模反元素"。

例如：3和11互质，那么3的模反元素就是4，因为 (3 × 4)-1 可以被11整除。显然，模反元素不止一个， 4加减11的整数倍都是3的模反元素 {...,-18,-7,4,15,26,...}，即如果b是a的模反元素，则 b+kn 都是a的模反元素。

可以用上述的欧拉定律来证明模范元素必然存在：

可以看到，a的 φ(n)-1 次方，就是a的模反元素。

换算以上公式：

假设已知 e=17, φ(n)=3120，以上公式转换为：

17x + 3120y = 1

那如何求解此二元一次方程的解？

扩展欧几里德算法

利用扩展欧几里得算法计算乘法逆元。

扩展欧几里得算法（英语：Extended Euclidean algorithm）是欧几里得算法（又叫辗转相除法）的扩展。已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足贝祖等式：

ax+by=gcd(a,b)

如果a是负数，可以把问题转化成为 ∣a∣(−x)+by=gcd(∣a∣,b)

|a|为a的绝对值，然后令:

x'=(-x)

欧几里德算法停止的状态是：

a=gcd(a,b), b=0; x=1

由于欧几里德算法：

gcd(a, b) = gcd(b, amodb)

得出：

gcd(a，b) = ax+by

gcd(b, amodb) = bx1 + (amodb)y1

所以：

ax+by = bx1 + (amodb)y1

又因：

amodb=a−⌊a/b⌋b

例如：

11%3 = 11 - Math.floor(11 / 3)*3 = 11-9 = 2

所以：

ax+bx = bx1 + (a- ⌊a/b⌋b)y1

ax+bx = by1 + b(x1- ⌊a/b⌋y1)

推导出：x = y1

y=x1−⌊a/b⌋y1

采用递归先求解第一层x1、y1，再不断迭代到上一层，不断递归直到一组得到特解x=1,y=0停止。即：当b = 0时，ax+by = a故而x=1, y=0。

算法实现：