RSA算法详解

一、欧拉函数(phi)

函数内容
通式:

upload successful

其中p1, p2……pn为x的所有质因数,x是不为0的整数。

φ(1)=1(和1互质的数(小于等于1)就是1本身)。
注意:每种质因数只一个。 比如12=223那么φ(12)=φ(43)=φ(2^23^1)=(2^2-2^1)*(3^1-3^0)=4
若n是质数p的k次幂,

upload successful

,因为除了p的倍数外,其他数都跟n互质。

设n为正整数,以 φ(n)表示不超过n且与n互素的正整数的个数,称为n的欧拉函数值
φ:N→N,n→φ(n)称为欧拉函数。
欧拉函数是积性函数——若m,n互质,

upload successful

如:φ(15)=φ(3)·φ(5)=2·4=8
特殊性质:当n为奇质数时,

upload successful

, 证明与上述类似。
若n为质数则

upload successful

函数表
0~100欧拉函数表(“x?”代表十位数,“x”代表个位数)

upload successful
φ(100)=40

二、费马小定理

版本一:
若a为一个整数,p为一个素数
那么a的p次方再减去a一定为p的倍数(同余)
记为

upload successful

版本二:
把a提出来

upload successful

当a不是p的倍数时,可以写成(p必须为一个素数)

upload successful

三、费马欧拉定理

1736年欧拉证明费马小定理是对的,给出更一般的定理:
若满足a为一个整数,n为一个与a互素的整数,即a⊥n,那么

upload successful

所以有了费马欧拉定理(在数论中命名)

upload successful

⦁ 模反函数
如果两个正整数e和n互质,那么一定可以找到整数d,使得 e * d - 1 被n整除,或者说e * d被n除的余数是1。这时,d就叫做e的“模反元素”。欧拉定理可以用来证明模反元素必然存在。两个整数a,b,它们除以整数M所得的余数相等:a ≡ b(mod m),比如说5除3余数为2,11除3余数也为2,于是可写成11 ≡ 5(mod 3)。

五、欧几里得算法(辗转相除法-求最大公约数)
欧几里得算法是求最大公约数的算法, 也就是辗转相除法。记 gcd(a,b) 为a和b的最大公约数,欧几里得算法的基本原理是gcd(a,b)==gcd(b,a%b),(b!=0) 和 gcd(a,0)==a 。
基本原理证明:
第一步:令c=gcd(a,b),则设a=mc,b=nc
第二步:可知r =a-kb=mc-knc=(m-kn)c 【r=a%b】
第三步:根据第二步结果可知c也是r的因数
第四步:可以断定m-kn与n互素【否则,可设m-kn=xd,n=yd,(d>1),则m=kn+xd=kyd+xd=(ky+x)d,则a=mc=(ky+x)dc,b=nc=ycd,故a与b最大公约数≥cd,而非c,与前面结论矛盾】
从而可知gcd(b,r)=c,继而gcd(a,b)=gcd(b,r),得证
扩展欧几里得算法
扩展欧几里得算法基于欧几里得算法,能够求出使得 ax+by=gcd(a,b) 的一组x,y。
对照下图更容易理解

upload successful

同样按照欧几里得算法的递归过程一样,到边界的时候b=0,这时候整数解非常好找,就是x=1,y=0。
六、RSA
①找两素数p和q,取n=pq (N)
②r=φ(n)=φ(p)*φ(q)=(p-1)
(q-1)
③e∈Z,e<r 且 e⊥r (必须)
。。。。。。公钥(N,e)
④d(模逆元),满足ed-1=r的倍数
d*e%r=1
求d令ed ≡ 1 (mod r)
。。。。。。私钥(N,d)
加密:
Bob用公钥加密给Alice传数
Bob 传 m 给 Alice,要求m<N

upload successful

Alice得到密文c
解密:Alice用私钥破解密文得到明文

upload successful

?即是明文m

解释:

upload successful

差个正负号,但是都是N的倍数,都成立
两边同时做d次方

upload successful

最后一步根据费马欧拉定理得来
所以得到解密式子:

upload successful

对明文m进行加密:c = pow(m, e, N),可以得到密文c。
对密文c进行解密:m = pow(c, d, N),可以得到明文m。
pow(x, y, z):效果等效pow(x, y)1% z, 先计算x的y次方,如果存在另一个参数z,需要再对结果进行取模。即pow(x,y,z)=x^y(mod z)
⦁ 实例-共模攻击
所谓共模攻击,是指多个用户共用一个模数n,各自有自己的e和d,在几个用户之间共用n会使攻击者能够不用分解n而恢复明文。
例如假设m为信息明文,两个加密密钥为e1和e2,公共模数为n,则:
c1 = pow(m, e1, n) – c1 = m^e1%n
c2 = pow(m, e2, n) – c2 = m^e2%n
分别拿对应的私钥来加密,可以得到相同的明文m
m = pow(c1, d1, n) – m = c1^d1%n
m = pow(c2, d2, n) – m = c2^d2%n
假设攻击者已知n,e1,e2,c1,c2,即可得到明文p,因为e1和e2互质,所以使用欧几里得算法可以找到能够满足以下条件的x,y:
pow(x,e1)+pow(y,e2)=1 – x^e1+y^e2=1(式中,x、y皆为整数,但是一正一负)
因为:c1 = m^e1%n ;c2 = m^e2%n
所以:(c1^xc2^y)%n = ((m^e1%n)^x(m^e2%n)^y)%n
根据模运算性质,可以化简为:(c1^xc2^y)%n = ((m^e1)^x(m^e2)^y)%n
即:(c1^xc2^y)%n = (m^(e1x+e2y))%n
又前面提到:e1x+e2y = 1
所以
(c1^xc2^y)%n = (m^(1))%n
(c1^x
c2^y)%n = m%n

c1^x*c2^y ≡ m (mod n)
假设x为负数,需再使用欧几里得算法来计算pow(c1,-1),则可以得到
pow(pow(c1,-1),-x) * pow(c2,y) = m mod(n) – {[c1^(-1)]^(-x)}
(c2^y) = m mod n
m = c1^x*c2^y mod N
在数论模运算中,要求一个数的负数次幂,与常规方法并不一样。
比如此处要求c1的x次幂,就要先计算c1的模反元素c1r,然后求c1r的-x次幂
如果m<n,则m可以被计算出来。

例题:
某次ctf比赛中的题
共模攻击的脚本+测试代码
题中给了n,e1,e2,c1,c2
运行脚本解出10进制的m,转换成hex,再转换成字符串即可得到flag。
总的脚本如下:

-- coding:utf-8 --

from gmpy2 import invert
def gongmogongji(n, c1, c2, e1, e2):
def egcd(a, b):
if b == 0:
return a, 0
else:
x, y = egcd(b, a % b)
return y, x - (a // b) * y
s = egcd(e1, e2)
s1 = s[0]
s2 = s[1]

1
2
3
4
5
6
7
8
9
# 求模反元素
if s1 < 0:
s1 = - s1
c1 = invert(c1, n)
elif s2 < 0:
s2 = - s2
c2 = invert(c2, n)
m = pow(c1, s1, n) * pow(c2, s2, n) % n
return m

n= 103109065902334620226101162008793963504256027939117020091876799039690801944735604259018655534860183205031069083254290258577291605287053538752280231959857465853228851714786887294961873006234153079187216285516823832102424110934062954272346111907571393964363630079343598511602013316604641904852018969178919051627
e1= 13
e2= 15
c1= 13981765388145083997703333682243956434148306954774120760845671024723583618341148528952063316653588928138430524040717841543528568326674293677228449651281422762216853098529425814740156575513620513245005576508982103360592761380293006244528169193632346512170599896471850340765607466109228426538780591853882736654
c2= 79459949016924442856959059325390894723232586275925931898929445938338123216278271333902062872565058205136627757713051954083968874644581902371182266588247653857616029881453100387797111559677392017415298580136496204898016797180386402171968931958365160589774450964944023720256848731202333789801071962338635072065

result = gongmogongji(n, c1, c2, e1, e2)
print result
m1=hex(50937517501984079318479184180525081694999782691988219077509947184814275476037417455150384)
print m1
import binascii
m2=binascii.unhexlify(b’666c61672d3534643364623563316566636437616661353739633337626362353630616530’)
print m2
最后得到flag:
flag-54d3db5c1efcd7afa579c37bcb560ae0
参考文献
https://blog.csdn.net/qq_23077403/article/details/86099229
https://blog.csdn.net/qq_23077403/article/details/86099229