RSA Notes 1

huangx607087学习RSA的笔记1

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-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))

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