DASCTF-1zRSA

题目分享
发布日期:   2024-08-15

本文参考了wbuildings师傅的周报和糖醋小鸡块师傅的博客

题目

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
from Crypto.Util.number import *
from sympy import *
import os
from secrets import flag

nbit =130
e = 3
l = getPrime(505)
m = bytes_to_long(flag + os.urandom(64))

assert len(flag) == 29

while True:
    p, q = getPrime(nbit), getPrime(nbit)
    PQ = int(str(p<<120)+str(q))
    QP = int(str(q<<120)+str(p))
    if isPrime(PQ) and isPrime(QP):
        break

n = PQ * QP
PP = nextprime((PQ >> 190) * (QP & (2 ** 190 - 1)))
QQ = nextprime((QP >> 190) * (PQ & (2 ** 190 - 1)))
N = PP * QQ
M = pow(m,1,l)
c = pow(m,e,N)

print('n =', n)
print('M =', M)
print('l =', l)
print('c =', c)

'''
n = 18339446336492672809908730785358232636383625709800392830207979464962269419140428722248172110017576390002616004691759163126532392634394976712779777822451878822759056304050545622761060245812934467784888422790178920804822224673755691
M = 36208281423355218604990190624029584747447986456188203264389519699277658026754156377638444926063784368328407938562964768329134840563331354924365667733322
l = 56911058350450672322326236658556745353275014753768458552003425206272938093282425278193278997347671093622024933189270932102361261551908054703317369295189
c = 720286366572443009268610917990845759123049408295363966717060100862857351750759651979922104897091176824666482923148635058966589592286465060161271579501861264957611980854954664798904862706450723639237791023808177615189976108231923
'''
1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import getPrime

p = getPrime(130)
q = getPrime(130)
print(p)
print(p*2**120)
print(p<<120)
PQ=p*2**120*10**39+q
PQ2=int(str(p<<120)+str(q))
if(PQ==PQ2):
    print("yes")
print(len(str(q)))
print(len(str(p)))

首先审题，看看这个题目的逻辑流程。我们先把已知的式子列出来。
PQ = p2^{120}10^x+q \
QP = q2^{120}10^y+p \
n = pq(2^{240}10^{x+y}+1)+p^22^{120}10^{x}+q^22^{120}*10^{y}

步骤一：求p和q

法一：二元copper

我们观察整个式子可以发现，p，q相对于整个式子可以看作是小量。不妨想到二元copper。
对于x和y是取39还是40，可以写一个循环。

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 Crypto.Util.number import long_to_bytes
import itertools
import sys

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []

n = 18339446336492672809908730785358232636383625709800392830207979464962269419140428722248172110017576390002616004691759163126532392634394976712779777822451878822759056304050545622761060245812934467784888422790178920804822224673755691

lenght = [39,40]
for i in lenght:
    for j in lenght:
        print((i, j))
        R.<x,y> = PolynomialRing(Zmod(n^2))
        PQ = x*2^120*10^i + y
        QP = y*2^120*10^j + x
        f = n - PQ*QP
        roots = small_roots(f,(2^130,2^130),m=1,d=4)
        if roots !=[]:
            # print(roots)
            p,q = roots[0]
            print(p,q)
            break

法二：二元copper优化

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
from Crypto.Util.number import *
from sympy import nextprime
import itertools

def small_roots(f, bounds, m=1, d=None):
	if not d:
		d = f.degree()

	R = f.base_ring()
	N = R.cardinality()
	
	f /= f.coefficients().pop(0)
	f = f.change_ring(ZZ)

	G = Sequence([], f.parent())
	for i in range(m+1):
		base = N^(m-i) * f^i
		for shifts in itertools.product(range(d), repeat=f.nvariables()):
			g = base * prod(map(power, f.variables(), shifts))
			G.append(g)

	B, monomials = G.coefficients_monomials()
	monomials = vector(monomials)

	factors = [monomial(*bounds) for monomial in monomials]
	for i, factor in enumerate(factors):
		B.rescale_col(i, factor)

	B = B.dense_matrix().LLL()

	B = B.change_ring(QQ)
	for i, factor in enumerate(factors):
		B.rescale_col(i, 1/factor)

	H = Sequence([], f.parent().change_ring(QQ))
	for h in filter(None, B*monomials):
		H.append(h)
		I = H.ideal()
		if I.dimension() == -1:
			H.pop()
		elif I.dimension() == 0:
			roots = []
			for root in I.variety(ring=ZZ):
				root = tuple(R(root[var]) for var in f.variables())
				roots.append(root)
			return roots

	return []

nbit = 130
PR.<p,q> = PolynomialRing(Zmod(n))
f = n-((2*p+1)*2^120*10^39+(2*q+1))*((2*q+1)*2^120*10^40+(2*p+1))
bounds = (2^(nbit-1),2^(nbit-1))
res = small_roots(f,bounds,m=1,d=2)
p,q = 2*int(res[0][1])+1,2*int(res[0][0])+1
print(p,q)

法三：解方程

n = pq(2^{240}10^{x+y}+1)+p^22^{120}10^{x}+q^22^{120}10^{y}\
=pq*(2^{240}10^{79}+1)+(p^2+10q^2)*2^{120}*10^{39}

1
2
3
4
5
6
7
8
9
10
from Crypto.Util.number import getPrime

p = getPrime(130)
q = getPrime(130)

print(len(str(q)))
print(len(str(p)))

print(((p**2+10*q**2)*2**120*10**39).bit_length())
print(((2**240*10**79+1)).bit_length())
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import sympy
from tqdm import *

n = 18339446336492672809908730785358232636383625709800392830207979464962269419140428722248172110017576390002616004691759163126532392634394976712779777822451878822759056304050545622761060245812934467784888422790178920804822224673755691

for i in trange(2**10):
    pq = n // (2**240 * 10**79 + 1) - i
    pq2 = (n - pq*(2**240 * 10**79 + 1)) // (2**120 * 10**39)
    if (n - pq*(2**240 * 10**79 + 1)) % (2**120 * 10**39) == 0:     # 倍数
        p, q = sympy.symbols('p q')
        flag = sympy.solve([pq - p*q,pq2-(p**2+10*q**2)],[p,q])
        break

p = abs(flag[0][0])
q = abs(flag[0][1])
print(p,q)

步骤二：求flag

法一：e与phi_n不互素，有限域开根

https://blog.csdn.net/m0_74345946/article/details/133936371

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *

c = 720286366572443009268610917990845759123049408295363966717060100862857351750759651979922104897091176824666482923148635058966589592286465060161271579501861264957611980854954664798904862706450723639237791023808177615189976108231923

p = 1213149261930568621267125437333569321667 
q = 855604426214387476576649090490109822073
PQ = int(str(p<<120)+str(q))
QP = int(str(q<<120)+str(p))

PP = next_prime((PQ >> 190) * (QP & (2 ** 190 - 1)))
QQ = next_prime((QP >> 190) * (PQ & (2 ** 190 - 1)))
N = PP * QQ
e = 3      

for mp in GF(PP)(c).nth_root(e, all=True):
    for mq in GF(QQ)(c).nth_root(e, all=True):
        m = long_to_bytes(crt([ZZ(mp), ZZ(mq)], [PP, QQ]))
        if b'DASCTF' in m:
            print(m)
            break

法二：明文低位泄露

题目中还有这样一个条件 M = pow(m,1,l)
m = m_high+M
M+kl = m
已知:
l = getPrime(505)
m = bytes_to_long(flag + os.urandom(64))
assert len(flag) == 29
m的位数是（29+64）8

1
2
3
4
5
6
print((29+64)*8)

M=36208281423355218604990190624029584747447986456188203264389519699277658026754156377638444926063784368328407938562964768329134840563331354924365667733322
print(M.bit_length())

print((29+64)*8-505)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *

M = 36208281423355218604990190624029584747447986456188203264389519699277658026754156377638444926063784368328407938562964768329134840563331354924365667733322
l = 56911058350450672322326236658556745353275014753768458552003425206272938093282425278193278997347671093622024933189270932102361261551908054703317369295189
c = 720286366572443009268610917990845759123049408295363966717060100862857351750759651979922104897091176824666482923148635058966589592286465060161271579501861264957611980854954664798904862706450723639237791023808177615189976108231923
p = 1213149261930568621267125437333569321667 
q = 855604426214387476576649090490109822073

PQ = int(str(p<<120)+str(q))
QP = int(str(q<<120)+str(p))
PP = next_prime((PQ >> 190) * (QP & (2 ** 190 - 1)))
QQ = next_prime((QP >> 190) * (PQ & (2 ** 190 - 1)))
N = PP * QQ

PR.<x> = PolynomialRing(Zmod(N))
f = c - (M+x*l)^3
f = f.monic()
roots = f.small_roots(X=2^239,epsilon = 0.02)
k = roots[0]

m = M+k*l
print(long_to_bytes(int(m)))
文章作者: collapsar
文章链接: https://crypto-collapsar.github.io/2024/08/15/DASCTF-1zRSA/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 collapsar !
题目分享
  目录