绿色健康小清新

耐得住寂寞,守得住繁华

非对称加密算法

RSA数学原理

获取两个不相等的质数pq

质数又称素数,在自然数中,除了1和自身外,不能被其他自然数整除。比如10以内的质数有:1,2,3,5,7。

把p和q相乘,得到n

比如:n=61*53=3233,用二进制表示为:110010100001。

我们常说的RSA算法中的多少位,就是n用二进制表示后的位数,在我们例子就是12位。目前商用中一般都是2048位。

计算出小于n的自然数中,有多少数与n互质(欧拉函数)

如果两个数的最大公约数为1,那么我们说这两个数互质,记:GCD(a,b)=1。其中GCD表示两个数的最大公约数。

使用欧拉函数来判断是否互质:

  • 情况1:如果n=1,那么与n互质的自然数只有1

    φ(n)=1φ(n)=1

  • 情况2:如果n是质数,那么与n互质的自然数有n-1个,

    φ(n)=n1φ(n)=n-1

    例:φ(7)=6例:φ(7)=6

  • 情况3:如果n可以因式分解为两个互质数的乘积,则:

    φ(n)=φ(p)×φ(q)=(p1)×(q1)φ(56)=φ(7)φ(8)=67=42φ(n)=φ(p)\times φ(q)=(p-1)\times (q-1) \\ 例:φ(56)=φ(7)*φ(8) = 6 * 7 = 42

  • 情况4:如果n可以写成某个数的质数次幂(其中k为质数),则:

    φ(n)=φ(pk)=pkpk1=pk(11p)φ(49)=φ(72)=7271=42φ(n)=φ(p^k)=p^k-p^{k-1}=p^k(1-\frac 1p) \\ 例:φ(49)=φ(7^2)=7^2 - 7^1 = 42

  • 情况5:根据以上规律,总结出一个通用的公式:

n=p1k1×p2k2prkr\qquad n=p_1^{k^1} \times p_2^{k^2} \ldots p_r^{k^r} \quad 注:任意一个整数,都可以写成两个质数的乘积
\qquad \Downarrow
φ(n)=φ(p1k1)×φ(p2k2)φ(prkr)\qquad φ(n)=φ(p_1^{k^1}) \times φ(p_2^{k^2})\ldots φ(p_r^{k^r})
\qquad \Downarrow
φ(n)=p1k1(11p1)×p2k2(11p2)prkr(11pr)\qquad φ(n)= p_1^{k^1}(1- \frac 1p_1) \times p_2^{k^2}(1- \frac 1p_2) \ldots p_r^{k^r}(1- \frac 1p_r)
\qquad \Downarrow
φ(n)=p1k1×p2k2prkr×(11p1)×(11p2)(11pn)\qquad φ(n)=p_1^{k^1} \times p_2^{k^2}\ldots p_r^{k^r}\times (1- \frac 1p_1)\times(1- \frac 1p_2)\ldots(1- \frac 1p_n)
\qquad \Downarrow
φ(n)=n×(11p1)×(11p2)(11pn)\qquad φ(n)=n\times(1- \frac 1p_1)\times(1- \frac 1p_2)\ldots(1- \frac 1p_n)

  • 总结:通过欧拉函数最后的通式,我们发现最后的结果只和n和p有关,和p的幂无关,这点很重要,在我们用程序实现时,能够大大的简化我们的逻辑代码。

回到算法中,我们需要计算与n互质的个数,也就是求φ(n),根据欧拉函数,计算过程如下:

φ(n)=φ(3233)=φ(61)×φ(53)=60×52=3120φ(n)=φ(3233)=φ(61)×φ(53)=60×52=3120

在1和φ(n)之间,选取一个随机质数e

即在1~3120中选取e=17。

求e和φ(n)的模反元素d(裴蜀定理、扩展欧几里得算法)

模反元素也称为模倒数,可以写成 a1b (mod n)a^{−1}≡b \ (mod \ n)ab1 (mod n)ab≡1 \ (mod \ n)。(ab和1关于n同模)

如果两个正整数a和n互质,那么一定可以找到整数b,使得a*b与n相除,余数为1,记作:(a×b)%n=1(a×b)1n=1(a \times b) \% n = 1 \Rightarrow \frac {(a \times b) - 1} n = 1

例:求3和11的模反元素

(3×b)111=1=>b=4\frac {(3 \times b) - 1} {11} =1 => b = 4

  • 通过上面的运算,我们可以算出一些简单数的模反元素,对于较大的数来说,我们需要引入新的计算工具:裴蜀定理,通过它,我们可以通过一个二元一次方程来得出模反元素。在求模反元素时,给予二个整数a、b,必存在整数x、y使得ax + by = gcd(a,b),而我们真正要获取的是x的值。
  • 定义:如果a与b互质,即GCD(a, b) = 1,二元一次方程ax+by=1ax + by = 1有一对正整数解,其中x即为a、b的模反元素。同理,上面的例子我们可以化简成这样:3x + 11y = 1
  • 疑惑:对于二元一次方程,好像不可解(也可以说有无穷多个解),我们之前都是解方程组。即然定理已经解决,两个互素(质)数组成的二元一次方程有一对整数解,那肯定是能解,解法我们需要引入另一个数学工具:扩展欧几里得算法

扩展欧几里得算法这个算法其实就是上面我们求最大公约数时,用到的辗转相除法+它的逆运算,我们看个例子就明白是什么意思了

例1:求47x+30y=147x + 30y = 1的解

解:使用辗转相除法,我们可以得到:

47 = 30 \times 1 + 17 \ \\ 30 = 17 \times 1 + 13 \ \\ 17 = 13 \times 1 + 4 \ \ \ \\ 13 = 4 \times 3 + 1 \ \ \ \ \ \\ 4 = 1 \times 4 + 0 \ \ \ \ \ \

我们可以得到GCD(47, 30) = 1,对到处第二行,我们移项处理:

1=134×34=1713×113=3017×117=4730×11 = 13 - 4 \times 3 \\ 4 = 17 - 13 \times 1 \\ 13 = 30 - 17 \times 1 \\ 17 = 47 - 30 \times 1 \\

我们把第二行代入第一行中:

1=13(1713×1)4×31=4×133×171=4×(3017)133×s171=(7)×47+11×30x=7(d)y=111 = 13 - \overbrace{(17 - 13 \times 1)}^4 \times 3 \\ \Downarrow \\ 1 = 4 \times 13 - 3 \times 17 \\ \Downarrow \\ 1 = 4 \times \overbrace{(30 - 17)}^{13} - 3 \times s17 \\ \Downarrow \\ \ldots \\ 1 = (-7) \times 47 + 11 \times 30 \\ 解得:x=-7(即为我们要求的模反元素d) \quad y = 11

回到算法中,我们根据e=17和φ(n)=3120,得到一个二元一次方程:17x+3120y=117x + 3120y = 1,再根据扩展欧几里得算法,我们可以得到方程的解:x=2753d=2753x = 2753 \quad 即:d = 2753

把n和e封装成公钥,n和d封装成私钥

  • 公钥:(3233,17)(3233, 17)
  • 私钥:(3233,2753)(3233, 2753)

实例

私钥和公钥获取:

  1. 取p=47, q=71;

  2. 则n = p * q = 3337, Φ(n)=(p-1)(q-1)=3220;

  3. 随机选择加密密钥e,e与Φ(n)互素,取e=79;

  4. 79 * d=1(mod n) =》 d = 1019101^9

  5. 公钥为(3337,79),私钥为(3379,1019)

假设要加密的明文是m=6882326879666683:

  • 首先,根据n的大小将m进行分组,这里我们把明文m分成六个组,即:m1=688, m2=232, m3=687, m4=966, m5=668, m6=003;
  • 接着分别对各个分组进行加密运算,第一个分组加密为c1=68879688^{79}(mod 3337) = 1570,类似的,对其余各个分组分别进行加密运算,得到如下密文:c=1570 2756 2091 2276 2423 158;
  • 解密时用私钥1019分别对明文进行解密运算,即:m1=157010191570^{1019}(mod 3337) = 688,对其余的密文用同样的计算方法就可以把密文恢复出来,即得到密文。

RSA参数的选择

p和q的选择:

  • p和q要足够大

  • p和q应为强素数。如p满足以下三个条件,即为强素数:

    (1)P-1有大素数因子r

    (2)P+1有大素数因子s

    (3)R-1有大素数因子t

  • p和q的差不能太小

  • p-1和q-1的最大公因数应很小

公钥e的选择:e不能太小;最好选择e为modΦ(n)的阶数,意思就是要使i的值尽量大才能使得ei≡ (mod Φ(n))成立。i等于(p-1)(q-1)/2是最好的。一般建议取e=2162^{16}+1=65537

代码

(1)质数判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
import Gcd from './Gcd'
/**
* 质数类
*/
class Prime {
private static pNumArr: Array<number> = []
/**
* 判断一个数是否为质数
* @param num 转入值
*/
public static isPrimeNum(num: number): boolean {
// 1和2都是质数
if (num < 3) {
return true
}
// i取开方,效率要比/2高出许多
for (let i = 2; i <= Math.sqrt(num); i++) {
if (num % i === 0) {
return false
}
}
return true
}
/**
* 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。
*/
public static coprime(n1: number, n2: number): boolean {
// 保证n1比n2要大
if (n2 > n1) {
let tmp = n1
n1 = n2
n2 = tmp
}
// 两个数中, 有一个是1, 则两数互质
if (n1 === 1 || n2 === 1) {
return true
}
// 如果两数相邻, 则两数互质
if (n1 - n2 === 1) {
return true
}
// 如果大数为奇数, 则n1-n2 = 2, 则两数互质
if (n1 % 2 === 1 && n1 - n2 === 2) {
return true
}
// 如果较大的数为质数, 则两数互质
if (this.isPrimeNum(n1)) {
return true
}
// 有一个是质数, 别一个不为此数的倍数, 则两数互质
if ((this.isPrimeNum(n1) || this.isPrimeNum(n2)) && n1 % n2 !== 0) {
return true
}
// 如果两个数都为质数, 则两个数互质
if (this.isPrimeNum(n1) && this.isPrimeNum(n2)) {
return true
}
// 如果两个数的最大公约数为1, 则两个数互质
if (Gcd.gcd(n1, n2) === 1) {
return true
}
return false
}
/**
* 获取该数下所有的质数
* @param num 转入的数
*/
public static getAllPrimeNum(num: number) {
let arr = []
for (let i = 1; i <= num; i++) {
if (this.isPrimeNum(i)) {
arr.push(i)
}
}
return arr
}

/**
* 把一个正整数分解为两个质数的乘积
* @param num
*/
public static break(num: number) {
this.getBreakArr(num)
return this.pNumArr
}

/**
* 把一个正整数分解为两个质数的乘积(中间步骤)
* @param num
*/
private static getBreakArr(num: number) {
// 获取该数/2的所有质数
let arr = this.getAllPrimeNum(Math.floor(num / 2))
// 能被这个数整除的最大质数
let maxNum = 1
for (let i = 0; i < arr.length; i++) {
if (num % arr[i] === 0) {
maxNum = arr[i]
}
}
// 除数
let divNum = num / maxNum
if (maxNum !== 1) {
this.pNumArr.push(maxNum)
return this.break(divNum)
} else {
this.pNumArr.push(divNum)
return maxNum
}
}
}

export default Prime

(2)欧拉函数计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import Prime from './Prime'
import Util from './Util'
/**
* 欧拉函数
*/
class Euler {
/**
* 根据欧拉函数取与此数互质的个数
* @param num 参数
*/
public static getEulerNum(num: number) {
Prime.break(num)
let arr = Util.uniqueArr(Prime.break(num))
let result = num
for (let i = 0; i < arr.length; i++) {
result *= 1 - 1 / arr[i]
}
return Math.floor(result)
}
}

export default Euler

(3)最大公约数计算-欧几里得算法-辗转相除法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/**
* 最大公约数
*/
class Gcd {
/**
* 计算2个数的最大公约数
* @param n1 数1
* @param n2 数2
*/
public static gcd(n1: number, n2: number): number {
let s = Math.floor(n1 / n2)
let y = n1 % n2
// console.log(n1 + ' = ' + n2 + '*' + s + ' + ' + y)
if (y === 0) {
return n2
} else {
return this.gcd(n2, y)
}
}
/**
* 扩展欧几里德算法 - 求方程的解 (详细注释版)
* 我们要求:47x + 30y = 1的解,下面为辗转相除法的步骤:
* 47 = 30*1 + 17
* 30 = 17*1 + 13
* 17 = 13*1 + 4
* 13 = 4*3 + 1
*
*
* @param num1 数1
* @param num2 数2
*/
public static gcdEx(n1: number, n2: number): Array<number> {
// 两数相除的商
let q = Math.floor(n1 / n2)
// 两数相除的余数
let r = n1 % n2
// 当到 13 = 4*3 + 1 即4 % 1 = 0时 返回
// 返回值为:1 | -4 即:x=1 y=-4
if (n2 % r === 0) {
// 转化为:1 = 13 + 4*(-3)
// 所以返回:x=1 y=q*(-1)=-3
return [1, q * -1]
} else {
let ret = this.gcdEx(n2, r)
// x和y为上一步返回的值
let x = ret[0]
let y = ret[1]
// x1和y1为当前步骤的值
let x1 = 1
let y1 = -q
// console.log('----', x, y, x1, y1)
// x2和y2为当前步骤计算得到的值
// 1 = 13 + 4*(-3)
// 4 = 17 + 13*(-1)
// 代入得:1 = 13 + (17 + 13*(-1)) * (-3)
// 计算得:1 = 17*(-3) + 13*4 ==> x=-3 | y=4
let x2 = y * x1
let y2 = y * y1 + x
ret = [x2, y2]
return ret
}
}
}
export default Gcd

(4)裴蜀定理的求解-扩展欧几里得算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/**
* 最大公约数
*/
class Gcd {
/**
* 计算2个数的最大公约数
* @param n1 数1
* @param n2 数2
*/
public static gcd(n1: number, n2: number): number {
let s = Math.floor(n1 / n2)
let y = n1 % n2
// console.log(n1 + ' = ' + n2 + '*' + s + ' + ' + y)
if (y === 0) {
return n2
} else {
return this.gcd(n2, y)
}
}
/**
* 扩展欧几里德算法 - 求方程的解 (详细注释版)
* 我们要求:47x + 30y = 1的解,下面为辗转相除法的步骤:
* 47 = 30*1 + 17
* 30 = 17*1 + 13
* 17 = 13*1 + 4
* 13 = 4*3 + 1
*
*
* @param num1 数1
* @param num2 数2
*/
public static gcdEx(n1: number, n2: number): Array<number> {
// 两数相除的商
let q = Math.floor(n1 / n2)
// 两数相除的余数
let r = n1 % n2
// 当到 13 = 4*3 + 1 即4 % 1 = 0时 返回
// 返回值为:1 | -4 即:x=1 y=-4
if (n2 % r === 0) {
// 转化为:1 = 13 + 4*(-3)
// 所以返回:x=1 y=q*(-1)=-3
return [1, q * -1]
} else {
let ret = this.gcdEx(n2, r)
// x和y为上一步返回的值
let x = ret[0]
let y = ret[1]
// x1和y1为当前步骤的值
let x1 = 1
let y1 = -q
// console.log('----', x, y, x1, y1)
// x2和y2为当前步骤计算得到的值
// 1 = 13 + 4*(-3)
// 4 = 17 + 13*(-1)
// 代入得:1 = 13 + (17 + 13*(-1)) * (-3)
// 计算得:1 = 17*(-3) + 13*4 ==> x=-3 | y=4
let x2 = y * x1
let y2 = y * y1 + x
ret = [x2, y2]
return ret
}
}
}
export default Gcd

ECC算法

椭圆曲线

ECC是椭圆曲线加密算法,Wolfram MathWorld(线上数学百科全书,http://mathworld.wolfram.com) 给出了非常精准的定义:一条椭圆曲线就是一组被 y2=x3+ax+by^2 = x^3 + ax + b定义的且满足 4a3+27b204a^3 + 27b^2 ≠ 0 的点集。4a3+27b204a^3 + 27b^2 ≠ 0 这个限定条件是为了保证曲线不包含奇点(在数学中是指曲线上任意一点都存在切线)。椭圆曲线示例图:

不同的椭圆曲线对应不同的形状(b=1,a从2到-3)

左(带锐点):y2=x3y^2 = x^3
右(曲线自交):y2=x33x+2y^2 = x^3 -3x + 2
都不是有效的椭圆曲线

椭圆曲线的二元运算

(1)加法

(2)乘法

以2A为例:

3A:

因此,在ECC算法中,Q(公钥)=kP很好算,但是根据Q和P求出k(私钥)很难。

关于阿贝尔群(abelian group)

阿贝尔群的概念是抽象代数的基本概念之一,是一种代数结构,由一个集合以及一个二元运算所组成。如果一个集合或者运算是群的话,就必须满足以下条件(+ 表示二元运算):

  1. 封闭性(closure),如果a和b被包含于群,那么a+b也一定是群的元素;
  2. 结合律(associativity);
  3. 存在一个单位元(identity element)0,0与任意元素运算不改变其值的元素,即 a+0 = 0+a = a;
  4. 每个元素都存在一个逆元(inverse);
  5. 交换律(commutativity),即 a+b = b+a;

椭圆曲线中的阿贝尔群

我们可以在椭圆曲线上定义一个群:

  1. 群中的元素就是椭圆曲线上的点;
  2. 单位元就是无穷处的点0;
  3. 相反数P,是关于X轴对称的另一边的点;
  4. 二元运算规则定义如下:取一条直线上的三点(这条直线和椭圆曲线相交的三点),P, Q, R(皆非零),他们的总和等于0,P+Q+R=0。

如果P, Q, R在一条直线上的话,他们满足:

P+(Q+R)=Q+(P+R)=R+(P+Q)==0P+(Q+R)=Q+(P+R)=R+(P+Q)=⋯=0。

当P,Q点为同一点时,P=Q,满足:

这样,我们可以直观的证明:+运算符是符合交换律和结合律的,这是一个阿贝尔群。

因为阿贝尔群满足交换律和结合律,所以点P和点-R的二元运算结果必会在曲线上,即P+P+P的结果必会在曲线上的另一点Q,

以此类推,可以得出得出:

Q=kP(kP,kP)Q=kP(k个相同的点P进行二元运算(数乘),记做kP)

椭圆曲线加密算法原理

描述一条Fp上的椭圆曲线,常用到六个参量:T=(p,a,b,n,x,y)。(p 、a 、b) 用来确定一条椭圆曲线,p为素数域内点的个数,a和b是其内的两个大数;

x,y为G基点的坐标,也是两个大数;n为点G基点的阶;

以上六个量就可以描述一条椭圆曲线,有时候我们还会用到h(椭圆曲线上所有点的个数p与n相除的整数部分)。

现在我们描述一个利用椭圆曲线进行加密通信的过程:

  1. 选定一条椭圆曲线 Ep(a,b) 并取椭圆曲线上一点,作为基点P(比如(0,1));

  2. 选择一个大数k作为私钥,并生成公钥 Q=kP;

  3. 将 Ep(a,b) 和点Q、P传给用户;

  4. 用户接到信息后 ,选择一个随机数r,将消息M生成密文C,C是一个点对,C=(rP,M+rQ),并发送;

  5. 私钥解密(M + rQ - k(rP) ,解密结果就是点M),公式如下:

    M+rQk(rP)=M+r(kP)k(rP)=MM + rQ - k(rP) = M + r(kP) - k(rP) = M

  6. 对点M进行解码就可以得到明文

    假设在加密过程中,有一个第三者H,H只能知道椭圆曲线 Ep(a,b)、公钥Q、基点P、密文点C,而通过公钥Q、基点P求私钥k或者通过密文点C、基点P求随机数r都是非常困难的,因此得以保证数据传输的安全。

DH算法

离散对数

DH 算法是非对称加密算法, 因此它可以用于密钥交换,该算法的核心数学思想是离散对数

对数运算:i=logabi = log_{a}b

离散对数是在对数运算的基础上加了「模运算」,也就说取余数,对应编程语言的操作符是「%」,也可以用 mod 表示。离散对数的概念如下图:

上图的,底数 a 和模数 p 是离散对数的公共参数,也就说是公开的,b 是真数,i 是对数。知道了对数,就可以用上面的公式计算出真数。但反过来,知道真数却很难推算出对数。

特别是当模数 p 是一个很大的质数,即使知道底数 a 和真数 b ,在现有的计算机的计算水平是几乎无法算出离散对数的,这就是 DH 算法的数学基础。

DH算法

现假设小红和小明约定使用 DH 算法来交换密钥,那么基于离散对数,小红和小明需要先确定模数和底数作为算法的参数,这两个参数是公开的,用 P 和 G 来代称。

然后小红和小明各自生成一个随机整数作为私钥,双方的私钥要各自严格保管,不能泄漏,小红的私钥用 a 代称,小明的私钥用 b 代称。

现在小红和小明双方都有了 P 和 G 以及各自的私钥,于是就可以计算出公钥:

  • 小红的公钥记作 A,A=Ga (mod P)A = G ^ a \ ( mod \ P )
  • 小明的公钥记作 B,B=Gb (mod P)B = G ^ b \ ( mod \ P )

A 和 B 也是公开的,因为根据离散对数的原理,从真数(A 和 B)反向计算对数 a 和 b 是非常困难的,至少在现有计算机的计算能力是无法破解的,如果量子计算机出来了,那就有可能被破解,当然如果量子计算机真的出来了,那么密钥协商算法就要做大的升级了。

双方交换各自 DH 公钥后,小红手上共有 5 个数:P、G、a、A、B,小明手上也同样共有 5 个数:P、G、b、B、A。

然后小红执行运算:$ B ^ a ( mod P )$,其结果为 K,因为离散对数的幂运算有交换律,所以小明执行运算: Ab(modP)A ^ b ( mod P ),得到的结果也是 K。

这个 K 就是小红和小明之间用的对称加密密钥,可以作为会话密钥使用。

可以看到,整个密钥协商过程中,小红和小明公开了 4 个信息:P、G、A、B,其中 P、G 是算法的参数,A 和 B 是公钥,而 a、b 是双方各自保管的私钥,黑客无法获取这 2 个私钥,因此黑客只能从公开的 P、G、A、B 入手,计算出离散对数(私钥)。

前面也多次强调, 根据离散对数的原理,如果 P 是一个大数,在现有的计算机的计算能力是很难破解出 私钥 a、b 的,破解不出私钥,也就无法计算出会话密钥,因此 DH 密钥交换是安全的

DHE 算法

根据私钥生成的方式,DH 算法分为两种实现:

  • static DH 算法,这个是已经被废弃了;
  • DHE 算法,现在常用的;

static DH 算法里有一方的私钥是静态的,也就说每次密钥协商的时候有一方的私钥都是一样的,一般是服务器方固定,即 a 不变,客户端的私钥则是随机生成的。

于是,DH 交换密钥时就只有客户端的公钥是变化,而服务端公钥是不变的,那么随着时间延长,黑客就会截获海量的密钥协商过程的数据,因为密钥协商的过程有些数据是公开的,黑客就可以依据这些数据暴力破解出服务器的私钥,然后就可以计算出会话密钥了,于是之前截获的加密数据会被破解,所以 static DH 算法不具备前向安全性。

既然固定一方的私钥有被破解的风险,那么干脆就让双方的私钥在每次密钥交换通信时,都是随机生成的、临时的,这个方式也就是 DHE 算法,E 全称是 ephemeral(临时性的)。

所以,即使有个牛逼的黑客破解了某一次通信过程的私钥,其他通信过程的私钥仍然是安全的,因为每个通信过程的私钥都是没有任何关系的,都是独立的,这样就保证了「前向安全」

ECDHE 算法

DHE 算法由于计算性能不佳,因为需要做大量的乘法,为了提升 DHE 算法的性能,所以就出现了现在广泛用于密钥交换算法 —— ECDHE 算法。

ECDHE 算法是在 DHE 算法的基础上利用了 ECC 椭圆曲线特性,可以用更少的计算量计算出公钥,以及最终的会话密钥。

小红和小明使用 ECDHE 密钥交换算法的过程:

  • 双方事先确定好使用哪种椭圆曲线,和曲线上的基点 G,这两个参数都是公开的;
  • 双方各自随机生成一个随机数作为私钥d,并与基点 G相乘得到公钥Q(Q = dG),此时小红的公私钥为 Q1 和 d1,小明的公私钥为 Q2 和 d2;
  • 双方交换各自的公钥,最后小红计算点(x1,y1) = d1Q2,小明计算点(x2,y2) = d2Q1,由于椭圆曲线上是可以满足乘法交换和结合律,所以 d1Q2 = d1d2G = d2d1G = d2Q1 ,因此双方的 x 坐标是一样的,所以它是共享密钥,也就是会话密钥(其实在TLS中最终的会话密钥,就是用「客户端随机数 + 服务端随机数 + x(ECDHE 算法算出的共享密钥) 」三个材料生成的)。

这个过程中,双方的私钥都是随机、临时生成的,都是不公开的,即使根据公开的信息(椭圆曲线、公钥、基点 G)也是很难计算出椭圆曲线上的离散对数(私钥)。

-------------本文结束感谢您的阅读-------------
六经蕴籍胸中久,一剑十年磨在手

欢迎关注我的其它发布渠道