欧几里得算法及其扩展,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 的求解过程如下:

a       b       x       y
8       1       0       1
9       8       1       -1
17      9       -1      2
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算法原理(二)

Published: September 26 2018

blog comments powered by Disqus