RSA加密算法详细解说 - Math - 数论 | Yume Shoka = GNI+Eliauk = 身体健康事事如意

RSA 加密算法是一种非对称加密算法，加密由公钥，私钥，明文，密文四部分组成.

取模运算

a mod n ≡ b 表示 a 与 b 对模 n 同余 (a,b 分别除以 n)

举个栗子: 3 mod 2 ≡ 1 <--> 1mod2=1 且 3mod2=1

欧拉函数

任意给定正整数 n，计算在小于等于 n 的正整数之中，有多少个与 n 构成互质关系？计算这个值的方法就叫做欧拉函数，以 φ(n) 表示.

例如，在 1 到 8 之中，与 8 形成互质关系的是 1、3、5、7，所以 φ(n)=4

在 RSA 算法中，欧拉函数对以下定理成立

1. 如果 n 可以分解成两个互质的整数之积，即 n=p×q，则有：φ(n)=φ(pq)=φ( p )φ( q );
2. 当 p 为质数，φ(p)=p-1

所以有 φ(n)=(p-1)(q-1)

欧拉定理与模反元素

欧拉函数的用处，在于欧拉定理
“欧拉定理” 指的是:
如果两个正整数 a 和 n 互质，则 n 的欧拉函数 φ(n) 可以让下面的等式成立：
a^φ(n)≡1(modn)
也就是说，a 的 φ(n) 次方被 n 除的余数为 1

模反元素的推导过程如下:

根据欧拉定理，有：
a^φ(n) = a × a^(φ(n)−1)≡1(modn)

令 b=a^(φ(n)−1)，得：

ab≡1(modn)

b 就是 a 的模反元素
所以，如果两个正整数 a 和 n 互质，那么一定可以找到整数 b 使得 ab-1 被 n 整除，或者说 ab 被 n 除的余数是 1

所以求私钥 d 的公式：d*e≡1mod [(p-1)(q-1)]

如何求 d

例如我们定义 e 为 17,p=473398607161，q=4511491
为了求出 d 我们写出如下脚本

	# 17x + 2135733082216268400y = 1
	def ext_euclid ( a , b ):
	if (b == 0):
	return 1, 0, a
	else:
	x , y , q = ext_euclid( b , a % b )
	x , y = y, ( x - (a // b) * y )
	return x, y, q
	print(ext_euclid(17, 2135733082216268400))

由于 de≡1mod [(p-1)(q-1) 可等价为 de mod (p-1)(q-1)=1
代入 e、p、q
所以我们可以把上式看作: 17x+(473398607161-1)(4511491-1) y=1

代入 φ(n) = (p-1)(q-1),φ(n) 与 e 互质，k 为正整数
可化为：d= (k*φ(n)+1)/e

	公钥 n --> 两素数p、q之积
	e --> 1<e<(p-1)·(q-1)且e与乘积互质
	私钥 d --> d·e ≡ 1 mod[(p-1)·(q-1)]
	n --> 同公钥n
	加密 -----> C ≡ M^e mod(n) M为明文
	解密 -----> M ≡ C^d mod(n) C为密文

由 p,q,dp,dq,c 求明文的算法

	import gmpy2
	I = gmpy2.invert(q,p)
	mp = pow(c,dp,p)
	mq = pow(c,dq,q) #求幂取模运算

	m = (((mp-mq)I)%p)q+mq #求明文公式

	print(hex(m)) #转为十六进制

pow (a,b,c) 表示 a^b % c 即 a^b mod c

数学运算规律

a^b %p = ((a%p)^b)%p
若 a≡b (% p), 则对任意的 c, 都有 (a+c)≡(b+c)(% p)
若 a≡b (% p), 则对任意的 c, 都有 (ac)≡(bc)(%p)
若 a≡b (% p), 对任意的 c, 都有 c≡d (% p), 那么 (a+c)≡(b+d)(% p),(ac)≡(bd)(%p)

运算推论：参考 https://blog.csdn.net/mikecoke/article/details/105967809?utm_medium=distribute.pc_relevant.none-task-blog-baidujs_title-2&spm=1001.2101.3001.4242

RSA