RSA Notes 1

huangx607087学习RSA的笔记1

I-What is RSA

体制:
1.选择两个大质数$p$,$q$,计算$n=p×q$

2.计算$\phi=(p-1)(q-1)$,也就是$n$的欧拉函数(也就是小于$n$的正整数中与$n$互质数量的个数)

3.取一个数字$e$,使$e,\phi$互质

4.计算$d$,使$ed\equiv 1 \mod \phi$

5.加密函数:$c=E(m)=m^e \mod n $

6.解密函数:$m=D(c)=c^d \mod n $

II-11种RSA题型的总结

0x01 直接给出$p,q,c,e$或者$n=p^k$的题目

直接根据加密体制计算即可,有crypto这个python库的可以直接用inverse(e, (p-1)*(q-1))求出$d$

$n=p^k$时,$\phi=p^k-p^{k-1}$

0x02 只给出了$n,c,e$

这种情况一般$n$是可以暴力分解的,上yafu即可

0x03 只给出了$n,c,e$并且$e=3$的情况

根据$c=E(m)=m^3 \mod n $,也就是$m^3=c+kn,k∈${$0,1,2,3,…$},这个时候可以枚举$k$的值,通过二分$m$确定$m$的值,一般$k$不会太大的

0x04 只给出了$n,c,e$并且$\ln e≈\ln n$(也就是$e$非常大的时候)

使用winnerattack算法,具体代码见下(别看,这个代码不是本fw打的)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
from __future__ import print_function
import libnum
def continued_fractions_expansion(numerator,denominator):#(e,N)
result=[]
divident = numerator % denominator
quotient = numerator // denominator
result.append(quotient)
while divident != 0:
numerator = numerator - quotient * denominator
tmp = denominator
denominator = numerator
numerator = tmp
divident = numerator % denominator
quotient = numerator // denominator
result.append(quotient)
return result
def convergents(expansion):
convergents=[(expansion[0], 1)]
for i in range(1, len(expansion)):
numerator = 1
denominator = expansion[i]
for j in range(i - 1, -1, -1):
numerator += expansion[j] * denominator
if j==0:
break
tmp = denominator
denominator = numerator
numerator = tmp
convergents.append((numerator, denominator)) #(k,d)
return convergents
def newtonSqrt(n):
approx = n // 2
better = (approx + n // approx) // 2
while better != approx:
approx = better
better = (approx + n // approx) // 2
return approx
def wiener_attack(cons, e, N):
for cs in cons:
k,d = cs
if k == 0:
continue
phi_N = (e * d - 1) // k
#x**2 - ((N - phi_N) + 1) * x + N = 0
a = 1
b = -((N - phi_N) + 1)
c = N
delta = b * b - 4 * a * c
if delta <= 0:
continue
x1 = (newtonSqrt(delta) - b)//(2 * a)
x2 = -(newtonSqrt(delta) + b)//(2 * a)
if x1 * x2 == N:
return [x1, x2, k, d]
if __name__ == "__main__":
n = #填写n的值
e = #填写e的值
c = #填写c的值
expansion = continued_fractions_expansion(e, n)
cons = convergents(expansion)
p, q, k, d = wiener_attack(cons, e, n)
m = pow(c, d, n)
print(libnum.n2s(m))

0x05 给出了$n,c,e$并且给出$f(d,\phi)$的一个一次式

直接求出$ef(d,\phi)$的值,然后确定模数

0x06 已知$n,c,e$,$e=3$,并且得知$m-(m \mod 2^k)$的值

这种情况下根本不可能用0x03的方法,因为$k$值也很大

在Sagemath中的Notebook上打开网页,创建一个Sagemath网页文件,把以下代码补完整后运行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n = #你已知的n值
e = 3
m = randrange(n)#不要改
c = pow(m, e, n)#不要改
beta = 1
epsilon = beta^2/7#不要改
nbits = n.nbits()#不要改
kbits=#m被掩盖的字位数
print(nbits,kbits)
mbar = #你得到的不完整的m值
c = #你得到的c值
print ("upper %d bits (of %d bits) is given" % (nbits-kbits, nbits))
PR.<x> = PolynomialRing(Zmod(n))
f = (mbar + x)^e - c
print (m)
x0 = f.small_roots(X=2^kbits, beta=1)[0] # find root < 2^kbits with factor = n1
print( mbar + x0)

0x07 Parity Oracle

直接看0xGame Div 2的相关内容

0x08已知$n,c,e$,$e=3$和$p-(p \mod 2^k)$的值

在Sagemath中的Notebook上打开网页,创建一个Sagemath网页文件,把以下代码补完整后运行

1
2
3
4
5
6
7
8
9
10
11
n = #你得到的n值
p_fake = #你得到的不完整的p值
pbits = p_fake.nbits()
kbits = #p失去的低位
pbar = p_fake & (2^pbits-2^kbits)
print "upper %d bits (of %d bits) is given" % (pbits-kbits, pbits)
PR.<x> = PolynomialRing(Zmod(n))
f = x + pbar
x0 = f.small_roots(X=2^kbits, beta=0.4)[0] # find root < 2^kbits with factor >= n^0.3
p= x0 + pbar
print p

有$p$就可以得到$q$,进而就很简单了

0x09 已知$n,c,e$,$e=3$和$d \mod 2^k$值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def partial_p(p0, kbits, n):
PR.<x> = PolynomialRing(Zmod(n))
nbits = n.nbits()
f = 2^kbits*x + p0
f = f.monic()
roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.3) # find root < 2^(nbits//2-kbits) with factor >= n^0.3
if roots:
x0 = roots[0]
p = gcd(2^kbits*x0 + p0, n)
return ZZ(p)
def find_p(d0, kbits, e, n):
X = var('X')
for k in xrange(1, e+1):
results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits)
for x in results:
p0 = ZZ(x[0])
p = partial_p(p0, kbits, n)
if p:
return p
if __name__ == '__main__':
n = #你得到的n值
e = 3
d = #你得到的d的低位
beta = 0.5
epsilon = beta^2/7
nbits = n.nbits()
print "nbits:%d:"%(nbits)
#kbits = floor(nbits*(beta^2+epsilon))
kbits = nbits - d.nbits()-1
print "kbits:%d"%(kbits)
d0 = d & (2^kbits-1)
print "lower %d bits (of %d bits) is given" % (kbits, nbits)
p = find_p(d0, kbits, e, n)
print "found p: %d" % p
q = n//p
print d
print inverse_mod(e, (p-1)*(q-1))

0x0A 两个模数$n_1,n_2$不互素(模不互素)

这种题目一般给出$2$组$n,e,c$的值,我们可以求一下$\gcd (n_1,n_2)$ 如果不等于$1$的话,我们就得到了$n$的一个因数$p$,一除就得到了$q_1,q_2$,分别求解即可得到明文。

0x0B 模数$n$相同,指数$e$不同(共模攻击)

这种题目一般也是给出$2$组$n,e,c$的值。也就是$5$个数字:$n,e_1,e_2,c_1,c_2$。此时可以不求$d_1,d_2$也可以直接获得明文。

步骤:
显然,多数情况下$\gcd(e_1,e_2)=1$,所以有$e_1s_1+e_2s_2=1$,一般$s_1,s_2$为一正一负的两个整数,用EXGCD可以求得该式子的一组解

我们可以得到算式 :$(c1^{s1}c2^{s2})\mod n = ((m^{e1}\mod n)^{s1}(m^{e2}\mod n)^{s2})\mod n$ .(1)

化简,有:$(c1^{s1}c2^{s2})\mod n = (m^{(e1^{s1}+e2^{s2})})\mod n$ .(2)

又$e_1s_1+e_2s_2=1$ . (3)

所以由**(2)(3)**可知:$c1^{s1}*c2^{s2} \equiv m \mod n $

所以我们可以写出以下的脚本:别膜,这很显然不是我这个fw能够写出来的!,我有过这样的码风?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from libnum import n2s,s2n
from gmpy2 import invert
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def main():
n = #填写n值
c1 = #填写c1值
c2 = #填写c2值
e1 = #填写e1值
e2 = #填写e2值
s = egcd(e1, e2)
s1 = s[1]
s2 = s[2]
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
print n2s(m)

if __name__ == '__main__':
main()

0x0C 给出pem和bin文件的RSA题目

在脚本前加上这些内容。然后pub1和pub2都有两个值(n和e,没有c)

这个脚本的后半部分也可以作为一个更加简洁的共模攻击觉得脚本。我就是个只会利用别人脚本的fw55555555555

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from Crypto.PublicKey import RSA
from Crypto.Util.number import *
import gmpy2
import libnum
c1=libnum.s2n(open('cipher1.txt','rb').read())
c2=libnum.s2n(open('cipher2.txt','rb').read())
pub1=RSA.importKey(open('publickey1.pem').read())
pub2=RSA.importKey(open('publickey2.pem').read())
#注:如果文件是bin类型的话,应该写成这样:
#c=bytes_to_long(open('cipher.bin','rb').read())
n=pub1.n
e1,e2=pub1.e,pub2.e
s = gmpy2.gcdext(pub1.e,pub2.e)
s1,s2=s[1],s[2]
if s1<0:
s1 = -s1
c1 = gmpy2.invert(c1, n)
elif s2<0:
s2 = -s2
c2 = gmpy2.invert(c2, n)
m=pow(c1,s1,n)*pow(c2,s2,n)%n
print(long_to_bytes(m))


RSA Notes 1
http://example.com/2020/10/17/RSA-Notes/
作者
huangx607087
发布于
2020年10月17日
许可协议