RSA Notes

huangx607087学习RSA的笔记

O-About

一个密码学废物的学习笔记,很菜,别看

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-9种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$非常大的时候)

由于$ed \equiv 1 \mod n$ 所以这时$d$可能会很小,直接枚举爆破$d$即可

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 模不互素

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