欧几里得算法及其扩展,RSA 算法

一、前言

2018年9月24日，阿蒂亚爵士完成黎曼猜想证明的演讲（黎曼猜想证明现场：3分钟核心讲解 提问陷沉默）。证明正确与否自有专业人士来解读，但其中涉及到的一些数学知识很有意思。对整数做因数分解是很困难的事情，所以人们把两个大质数相乘的乘积公开作为加密密钥，即RSA算法的原理。而RSA算法又使用到欧几里得算法的扩展，记一下。

二、欧几里得算法

欧几里得算法，又名辗转相除法，此算法可以求两个整数的公约数。例如 a = 1251 和 b = 390 两个数，计算过程如下：

a       b       mod
1251    390     81
390     81      66
81      66      15
66      15      6
15      6       3
6       3       0
The highest common divissor between 1251 and 390 is : 3

代码实现见 辗转相除法

三、扩展欧几里德算法

扩展欧几里得算法 是这样一个问题：

其中 gcd(a,b) 是a和b的最大公约数，求解x和y，使等式成立。

如对 43x+17y=1 的求解过程如下：

43 = 17 x 2 + 9
17 = 9  x 1 + 8
9  = 8  x 1 + 1

将上述等式倒过来：

9  = 8  x 1 + 1
17 = 9  x 1 + 8
43 = 17 x 2 + 9

为实现 ax + by = 1，取值如下：

a       b       x       y
8       1       0       1
9       8       1       -1
17      9       -1      2

将等式写为与原等式类似的格式：

9  + 8  x (-1) = 1  等式 1
17 + 9  x (-1) = 8  等式 2
43 + 17 x (-2) = 9  等式 3

将等式 2 和等式 3 代入到等式 1 中：

43 + 17 x (-2) + (17 + 9  x (-1)) x (-1) = 1
43 + 17 x (-2) + (17 + (43 + 17 x (-2))  x (-1)) x (-1) = 1
43 x 2 + 17 x (-5) = 1

可以得到最终的结果如下：

43      17      2       -5
Result is : x=2 , y=-5

代码实现见 扩展欧几里得算法

四、RSA算法

RSA算法 是一种非对称加密算法，主要有3个作用：加密、解密和签名。
得到公钥和私钥的过程，在 RSA算法原理（二） 里有详细的阐述。我用go实现的demo如下：

func rsa() (int, int, int) {
	//第一步，随机选择两个不相等的质数p和q。
	p := 3
	q := 11
	//第二步，计算p和q的乘积n。
	n := p * q
	//第三步，计算n的欧拉函数φ(n)。
	phi := (p - 1) * (q - 1)
	//第四步，随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质。
	e := 3
	//第五步，计算e对于φ(n)的模反元素d。
	d, _ := exgcd(e, phi)
	if d < 0 {
		d = phi + d
	}
	//第六步，将n和e封装成公钥，n和d封装成私钥。
	return n, e, d
}

代码实现见 RSA算法示例。

输出结果类似于如下：

public key = 3,private key = 7,length = 33
Origin Message =  24
Encoded Message =  30
Decoded Message =  24

以上是原理实现的demo，这里的公钥和私钥都是很小的质数。如果试着把p和q放大，会发现加密和解密时的复杂度快速提高，甚至int64类型的数字溢出了。应用到实际上，公钥和私钥都是很大的质数，一般是1024位，重要场合则为2048位。

五、参考链接

世界上最早的算法：辗转相除法（求两个自然数最大公约数

扩展欧几里得算法视频

轻松学习RSA加密算法原理

RSA算法原理（一）

RSA算法原理（二）