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的后门程序轻易破解各种加密数据。

RSA原理

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

密钥生成过程

步骤	概述	公式	说明
1	随机p，q	p,q	选择一对不相等且足够大的质数
2	求n	n = p*q	计算质数p，q的乘积
3	求φ(n)	φ(n) = (p-1)(q-1)	计算n的欧拉函数
4	求e	1 < e < φ(n)	选一个和φ(n)互质的整数e
5	求d	ed = 1 (mod φ(n))	计算出e对于φ(n)的模反元素d
6	公钥	e,n	PK(e, n)
7	私钥	d,n	SK(d, n)

第一步：随机p，q

p，q为不相等且足够大的质数。

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

代码实现：

function isPrime(num) {
  for (let i = 2; i < num; i++) {
    if (num % i === 0) {
      return false;
    }
  }
  return true;
}
function getPrime(min, max) {
  const rst = [];
  for (let i = Math.max(2, min); i <= max; i++) {
    if (isPrime(i)) {
      rst.push(i);
    }
  }
  return rst;
} 
// 第一步，随机选择两个不相等的质数p和q
let primeList = getPrime(1, 100);
const pIndex = Math.floor(Math.random() * 1000) % primeList.length;
const p = primeList[pIndex];
primeList.splice(pIndex, 1);
const qIndex = Math.floor(Math.random() * 1000) % primeList.length;
const q = primeList[qIndex];

第二步：求n

n 的长度就是密钥长度。

n = p * q = 11 * 3 = 33;

33写成二进制是100001，一共有6位，所以这个密钥就是6位。实际应用中，RSA密钥一般是1024位，重要场合则为2048位。

代码实现：

// 第二步 计算n 代表密钥的长度
const n = p * q;

第三步：求n的欧拉函数φ(n)

互质关系 如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。比如，15和32没有公因子，所以它们是互质关系。
公因子 是一个数学概念，指的是能同时整除几个整数的整数，可以用辗转相除法算出。

问题：任意两个合数存在互质关系吗？

例如15，44这说明，不是质数也可以构成互质关系。

互质关系结论

1. 任意两个质数构成互质关系，比如13和61。

2. 一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如3和10。

3. 如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如97和57。

4. 1和任意一个自然数是都是互质关系，比如1和99。

5. p是大于1的整数，则p和p-1构成互质关系，比如57和56。

6. p是大于1的奇数，则p和p-2构成互质关系，比如17和15。

欧拉函数

任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？（比如φ(8)，表示在1到8之中，有多少个数与8构成互质关系？）

计算这个值的方法就叫做欧拉函数，以φ(n)表示。在1到8之中，与8形成互质关系的是1、3、5、7，所以 φ(n) = 4。

φ(n) 的计算方法并不复杂，但是为了得到最后那个公式，需要一步步讨论。

条件	公式	解释
如果n=1	φ(1) = 1	因为1与任何数（包括自身）都构成互质关系。
如果n是质数	φ(n)=n-1	因为质数与小于它的每一个数，都构成互质关系。比如5与1、2、3、4都构成互质关系。
如果n是质数的某一个次方, n = p^k (p为质数，k为大于等于1的整数)	φ(p^k) = p^k - p^k-1 = p^k * (1 - 1/p)	譬如 φ(8) = φ(2^3) =2^3 - 2^2 = 8 -4 = 4。这是因为只有当一个数不包含质数p，才可能与n互质。而包含质数p的数一共有p^(k-1)个，即1×p、2×p、3×p、...、p^(k-1)×p，把它们去除，剩下的就是与n互质的数。当 k=1 时为第二种情况。
如果n可以分解成两个互质的整数之积	φ(n) = φ(q * p) = φ(q)φ(p)	即积的欧拉函数等于各个因子的欧拉函数之积。比如，φ(56)=φ(8×7)=φ(8)×φ(7)=4×6=24。
因为任意一个大于1的正整数，都可以写成一系列质数的积。	n = p1^k1 * p2^k2... φ(n) = φ(p1^k1) * φ(p2^k2)... φ(n) = p1^k1 * p2^k2 * (1 - 1/p1)(1 - 1/p2) φ(n) = n(1 - 1/p1)(1 - 1/p2)...	φ(33) = φ(3 * 11) = 33 * (1-1/3) * (1-1/7) = 332/310/11

根据欧拉函数，求n的欧拉函数

φ(n)

= φ(pq)

= φ(p) φ(q)

= (p-1)(q-1)

代码实现：

// 第三步 计算n的欧拉函数φ(n)
const oN = (p - 1) * (q - 1);

第四步：求e

随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质。

那么是不是找出一个小于φ(n)且与φ(n)的最大公因子为1的数，这个数就是e？

欧几里德算法

求解最大公约数 Greatest Common Divisor(GCD)就叫欧几里得算法（又称辗转相除法），公式表示：gcd(a,b) = gcd(b,a mod b)

它的具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。

例如：68和3的最大公约数求解

68 % 3 = 2;
3 % 2 = 1;
2 % 1 = 0;
// 所以68和3的最大公约数是1
// 68和4的最大公约数求解
68 % 4 = 0;
// 68和4的最大公约数是4

代码实现：

function gcd(a, b) {
  // return b === 0 ? a : gcd(b, a%b)
  let big = a;
  let small = b;
  if (a < b) {
    big = b;
    small = a;
  }
  return big % small === 0 ? small : gcd(big % small, small);
}

现在只要满足 gcd(x, φ(n))===1 则x就是我们要找的e，因为满足 1< e < φ(n) 条件下和φ(n)互质的数不止一个，下面罗列所有的互质数然后随机选出一个就是e。

代码实现：

const primeList = [];
for (let i = 1; i < oN; i++) {
  if (gcd(i, oN) === 1) {
    primeList.push(i);
  }
}
const index = Math.floor(Math.random() * (primeList.length - 1)) + 1;
const e = primeList[index];

第五步：求d

求e对与φ(n)的模反元素d，根据欧拉定理得出以下公式：
ed ≡ 1 (mod φ(n))

欧拉定理

欧拉函数是根据欧拉定理计算的。

如果两个正整数a和m互质，则m的欧拉函数 φ(m) 可以让下面的等式成立：

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

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

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

3^φ(5) = 1 (mod 5);
3^4 mod 5 = (3^4)%5 = 1;

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

假设正整数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的模反元素。

换算以上公式：

ed ≡ 1 (mod φ(n))
ed - 1 = k\*φ(n)
**ed + φ(n)k = 1**
ax+by=1
因为e和φ(n)已知，实则求解而二元一次方程d和k。

假设已知 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。

算法实现：

#include <bits/stdc++.h>
using namespace std;
int ext_euc(int a, int b, int &x, int &y)
{
    if (b == 0)
    {                
      x = 1, y = 0;
      return a;        
    }    
    int x1, y1, d;    
    int d = ext_euc(b, a % b, x1, y1);
    x = y1;
    y = x1 - a/b * y1;
    return d;
}
int main()
{
    int a, b, x, y;
    cin >> a >> b;
    ext_euc(a, b, x, y);
    cout << x << ' ' << y << endl;
    return 0;
}

模拟执行：

假设 p=3, q=5, e=5，φ(n)=(3-1)*(5-1)=8
ext_euc(8,5,x,y) {d = ext_euc(5,1,x,y)}
ext_euc(5,1,x,y){d = ext_euc(1,0,x,y)}
ext_euc(1,0,x,y){x=1,y=0,return 1;}
ext_euc(5,1,x,y){d=1,x=0,y=1-5/1*0=1,return 1;}
ext_euc(8,5,x,y){d=1,x=1,y=0-8/5*1=-1,return 1;}
得出x = 1, y = -1;

js代码实现：

const xyObj = { x: null, y: null };
function exGCD(a, b, xyObj) {
  // 特解 ax + 0 * y = gcd(a, b); 当x=1,b=0时，a = gcd(a, 0);
  if (b === 0) {
    xyObj.x = 1;
    xyObj.y = 0;
    return a;
  }
  const ans = exGCD(b, a % b, xyObj);
  const { x, y } = xyObj;
  xyObj.y = x - Math.floor(a / b) * y;
  xyObj.x = y;
  return ans;
}
// e*x + oN*y = 1
exGCD(e, oN, xyObj);
while (xyObj.x < 0) {
  xyObj.x += oN;
}
const d = xyObj.x;

第六步：公钥和私钥

公钥：PK(n, e)

私钥：SK(n, d)

加密

加密要用公钥 (n,e)，所谓加密就是算出以下公式的c，等价于m的e次方除以n余数为c，m为被加密对象，m必须是整数，且m必须小于n。

$m^e ≡ c (mod n)$

假设A的公钥是(23, 3)，B的m假设是65，那么算出以下等式：

$65^3≡ c(mod 23)$

公钥(n,e) 只能加密小于n的整数m，那么如果要加密大于n的整数，该怎么办？

解密

解密要用私钥(n,d)，所谓解密就是算出以下公式的m，等价于c的d次方除以n的余数为m。

$c^d =m(mod n)$

私钥证明

根据加密公式

$m^e ≡ c (mod n)$

$c ≡ m^e - kn$

将 c 代入需要证明的那个密钥规则：

$c^d =m(mod n)$

$(m^e - kn)d ≡ m (mod n)$

等同于求证：

$m^em^d ≡ m (mod n)$

由于

ed ≡ 1 (mod φ(n))

ed = hφ(n) + 1

将ed代入：

$m^(hφ(n)+1) ≡ m (mod n)$

若m与n互质，根据欧拉定理: $m^φ(n) ≡ 1(mod n)$

得到：

$(m^φ(n))^h * m ≡ m (mod n)$

m与n不是互质关系

参见：RSA加密算法【维基百科】

RSA算法的可靠性

那么，有无可能在已知公钥PK(n, e)的情况下，推导出d？

（1）ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。

（2）φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。

（3）n=pq。只有将n因数分解，才能算出p和q。

结论：如果n可以被因数分解，d就可以算出，也就意味着私钥被破解。

但至今为止还没有人找到一个多项式时间的算法来分解一个大的整数的因子，同时也还没有人能够证明这种算法不存在，目前，除了暴力破解，还没有发现别的有效方法。

对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。

假如有人找到一种快速因数分解的算法，那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到现在为止，世界上还没有任何可靠的攻击RSA算法的方式。

根据已经披露的文献，目前被破解的最长RSA密钥是768个二进制位。只要密钥长度足够长，用RSA加密的信息实际上是不能被解破的。

一般认为认为，1024位的RSA密钥基本安全，2048位的密钥极其安全。

参考来源

https://zh.wikipedia.org/zh-cn/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95

https://zh.wikipedia.org/wiki/%E6%A8%A1%E5%8F%8D%E5%85%83%E7%B4%A0

https://zh.wikipedia.org/wiki/扩展欧几里得算法

https://zh.wikipedia.org/wiki/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95

https://www.bilibili.com/video/BV1rD4y1C7qg/?zw

https://juejin.cn/post/7044863141062115341

https://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html

https://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html

https://www.aqniu.com/news-views/942.html

- END -

关于奇舞团

奇舞团是 360 集团最大的大前端团队，代表集团参与 W3C 和 ECMA 会员（TC39）工作。奇舞团非常重视人才培养，有工程师、讲师、翻译官、业务接口人、团队 Leader 等多种发展方向供员工选择，并辅以提供相应的技术力、专业力、通用力、领导力等培训课程。奇舞团以开放和求贤的心态欢迎各种优秀人才关注和加入奇舞团。

继续滑动看下一个