RSA算法

Diffie-Hellman（迪菲-赫尔曼）秘钥交换

首先先了解下最基础的秘钥交换算法，Diffie-Hellman算法，它是一种建立秘钥的方法，而不是加密方法，所以秘钥必须和其他一种加密算法结合使用。这种秘钥交换技术的目的在于使两个用户安全的交换一个秘钥一遍后面的报文加密。

Diffie-Hellman密钥交换算法的有效性依赖于计算离散对数的难度。

以如下定义离散对数：首先定义一个素数p的原根，为其各次幂产生从1 到p-1的所有整数根，也就是说，如果g是素数p的一个原根，那么数值 g mod p, g2 mod p, ..., gp-1 mod p，p为指数

那么再了解一下什么是原根

原根

原根，是一个数学符号。设m是正整数，a是整数，若a模m的阶等于φ(m)，则称a为模m的一个原根。

φ(m)为欧拉函数（在数论，对正整数n，欧拉函数是小于等于n的正整数中与n互质的数的数目.）

欧拉定理：设

（a,m）=1，则a^φ(m)=1modm

特别地，当m=p(p为素数)时，φ(p)=p-1,此时a^p-1=1(modp)

下面我们继续来看DH

下面是DH算法的原理：

有两个全局公开的参数，一个素数p和一个整数g，g是p的一个原根。

服务端的私钥和公钥分别是a和A，客户端的私钥和公钥分别是b和B；

服务端根据a、p、g，可以计算出公钥A；

服务端将g, p, A明文传送给客户端，客户端可以计算自己的公钥B，以及共享密钥K；

客户端将B明文发送给服务端，服务端也可以计算出共享密钥K。

也可以来说是一个颜色混淆的结果，比如，几种颜色混合顺序不同，但最终获得的颜色都是一样的。

因此相当于双方已经交换了一个相同的秘密密钥。

自从有了DH，打开了新世界的大门，出现了非对称加密算法。

　　（1）乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。

　　（2）甲方获取乙方的公钥，然后用它对信息加密。

　　（3）乙方得到加密后的信息，用私钥解密。

1977年，三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法。从那时直到现在，RSA算法一直是最广为使用的"非对称加密算法"。毫不夸张地说，只要有计算机网络的地方，就有RSA算法。

RSA基础

互质关系

如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。比如，15和32没有公因子，所以它们是互质关系。这说明，不是质数也可以构成互质关系。

　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=1，则 φ(1) = 1 。因为1与任何数（包括自身）都构成互质关系。

第二种情况

如果n是质数，则 φ(n)=n-1 。因为质数与小于它的每一个数，都构成互质关系。比如5与1、2、3、4都构成互质关系。

第三种情况

如果n是质数的某一个次方，即 n = p^k (p为质数，k为大于等于1的整数)，则

比如 φ(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 = p1 × p2

则

　　φ(n) = φ(p1p2) = φ(p1)φ(p2)

RSA的算法步骤

1、随机选两个不相等的质数p和q

2、计算p和q的乘积n

3、计算n的欧拉函数 φ(n)

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

5、计算e对于φ(n)的模反元素d

6、n和e为公钥，n和d为私钥

再看下图

步骤	说明	描述	备注
1	找出质数	P 、Q	-
2	计算公共模数	N = P * Q	-
3	欧拉函数	φ(N) = (P-1)(Q-1)	-
4	计算公钥E	1 < E < φ(N)	E的取值必须是整数 E 和 φ(N) 必须是互质数
5	计算私钥D	E * D % φ(N) = 1	-
6	加密	C ＝ M E mod N	C：密文 M：明文
7	解密	M ＝C D mod N	C：密文 M：明文

对外，我们只暴露公钥。

举个例子

1.找出两个质数

P = 3 ，Q = 11

2.计算公共模数

N = PQ = 3 *11 = 33

3.欧拉函数求质数最大范围

φ(N) = (P-1)(Q-1) = 2 * 10 = 20 //求质数取数范围

这里用的费马小定理

假设正整数a与质数p互质，因为质数p的φ(p)等于p-1，则欧拉定理可以写成

φ(N) = 20

4.计算公钥E

// E 质素范围内取公钥E 1 < E < φ(N) 1 <E < 20

E 的取值范围 {3, 7, 9, 11, 13, 17, 19} E的取值必须是整数, E 和 φ(N) 必须是互质数为了测试，我们取最小的值 E =3

5.计算私钥D

E * D % φ(N) = 1 3 * D % 20 = 1

D为7

这里其实是取模反，

ED ≡ 1 (mod φ(N))

这个式子等价于

　ED - 1 = kφ(N)

于是，找到模反元素d，实质上就是对下面这个二元一次方程求解

　Ex + φ(N)y = 1

这里就可以用拓展欧几里得算法

6.公钥加密

公式：C ＝ M^E mod N

M = 2 //被加密的数字 E = 3 //公钥 N = 33 //公共取模数

C = 222%33 = 8 //加密后的值

7.私钥解密

M ＝CD mod N

C = 8 //密文 D = 7 //秘钥 N = 33 //公共取模数

8 * 8 * 8 * 8 * 8 * 8 * 8=2097152 8 * 8 * 8 * 8 * 8 * 8 * 8 % 33 = 2

rsa的各种情况

那么，有无可能在已知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密钥才可能被暴力破解。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。

　　只要密钥长度足够长，用RSA加密的信息实际上是不能被解破的。"

举例来说，你可以对3233进行因数分解（61×53），但是你没法对下面这个整数进行因数分解。

　1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413

它等于这样两个质数的乘积：

　33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489 　　　　× 　36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917

RSA共模攻击

拓展欧几里得算法

ax+by = d = gcd(a, b)

形式是这样，看上去就是一个两元一次方程

d = ax0 + by0 辗转相除法其中一步的a，b d = bx1 + (a % b)y1 辗转相除法上一步的a = b，b = a % b

生成秘钥的过程中使用了相同的模数n，此时用不同的秘钥e加密同一信息m

1
2
3

c1 = m^e1 % n
c2 = m^e2 % n

若两个秘钥e互素根据扩展的欧几里得算法则存在s1，s2有

1 2	e1 * s1 + e2 * s2 = gcd(e1, e2) = 1

结合以上所有信息，可以得到一个结论

 (c1^s1 * c2^s2) %n
=  (m^e1 % n)^s1 * (m^e2 %n)^s2 % n
=  m^(e1 * s1 + e2 * s2) % n
=  m % n
=  m

也就是在完全不知道私钥的情况下，得到了明文m

1	m = (c1^s1 * c2^s2) % n

python中的gmpy2的库的了解

1.初始化大整数

import gmpy2
gmpy2.mpz(909090)

result:mpz(909090)

2.求大整数a,b的最大公因数

import gmpy2
gmpy2.gcd(6,18)

result:mpz(6)

3.求大整数x模m的逆元y

import gmpy2
#4*6 ≡ 1 mod 23
gmpy2.invert(4,23)

result:mpz(6)

4.检验大整数是否为偶数

import gmpy2
gmpy2.is_even(6)

result:True

-----------
import gmpy2
gmpy2.is_even(7)

result:False

5.检验大整数是否为奇数

import gmpy2
gmpy2.is_odd(6)

result:False

-----------
import gmpy2
gmpy2.is_odd(7)

result:True

6.检验大整数是否为素数

import gmpy2
gmpy2.is_prime(5)

result:True

7.求大整数x开n次根

import gmpy2
gmpy2.iroot(81,2)

result:(mpz(9),True)

8.求大整数x的y次幂模m取余

import gmpy2
#2^4 mod 5 
gmpy2.powmod(2,4,15)

result:mpz(1)

gmpy2.iroot(x,n) # x开n次根

ctf常见题型

RSA中已知dq，dp的计算m步骤

dp=dmod(p-1),dq=dmod(q-1)

(1).计算q模p的逆元I; (2).计算m1=(c^dp)modp; (3).计算m2=(c^dq)modq; (4).m=(((m1-m2)I)modp)q+m2;

举个例子

p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229 q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469 dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929 dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041 c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

import gmpy2
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
I = gmpy2.invert(q,p)
m1 = pow(c,dp,p)
m2 = pow(c,dq,q)
m = (((m1-m2)*I)%p)*q+m2
print(m)                               #10进制明文
print(hex(m)[2:])                      #16进制明文
print(bytes.fromhex(hex(m)[2:]))       #16进制转文本

已知 p ，q，e 求 d

import gmpy2
p = 38456719616722997
q = 44106885765559411
e = 65537
 
s = (p-1)*(q-1)
d = gmpy2.invert(e,s)
print ("dec: " + str(d))
print ("hex: " +  hex(d))