2024强网杯

发表于 分类于 阅读次数： Waline： 本文字数： 2.8k 阅读时长 ≈ 10 分钟

记录2024强网杯Crypto部分题解

结束前1小时做出高分题，win!

easyRSA

task.py

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
#encoding:utf-8
from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime
import random, gmpy2

class RSAEncryptor:
	def __init__(self):
		self.g = self.a = self.b = 0
		self.e = 65537
		self.factorGen()
		self.product()

	def factorGen(self):
		while True:
			self.g = getPrime(500)
			while not gmpy2.is_prime(2*self.g*self.a+1):
				self.a = random.randint(2**523, 2**524)
			while not gmpy2.is_prime(2*self.g*self.b+1):
				self.b = random.randint(2**523, 2**524)
			self.h = 2*self.g*self.a*self.b+self.a+self.b
			if gmpy2.is_prime(self.h):
				self.N = 2*self.h*self.g+1
				print(len(bin(self.N)))
				return

	def encrypt(self, msg):
		return gmpy2.powmod(msg, self.e, self.N)


	def product(self):
		with open('/flag', 'rb') as f:
			self.flag = f.read()
		self.enc = self.encrypt(self.flag)
		self.show()
		print(f'enc={self.enc}')

	def show(self):
		print(f"N={self.N}")
		print(f"e={self.e}")
		print(f"g={self.g}")


RSAEncryptor()

根据p,q的产生方式

定位到Common Prime RSA。Common Prime RSA 笔记 | 独奏の小屋找到该题符合的条件：g < a + b，即1.3.3中的攻击脚本

先获取数据，N是2048bit，g是500bit。更改参数，把nbits改成2048,gamma改为0.244

exp

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
from sage.groups.generic import bsgs
from Crypto.Util.number import *

N=20435271199198608366445070163055743926530547854315033141279645965767638473864664330754962276436466649275050979103893712139245544544872935554374114399052839215948338405516499474115214273699914266370050930769132408706474824505336493869342787492685168436693712862639462238101469809198476436457638629311139852354706756281766432512479057195404236230484898324707597749019917227269367587815080448139295679716499335061655279345030131435571625512494222844856455878041228974934679176701090200039100574296646644271325056802850586021423090540681108392177561696676096831318357211402247645340390966411768743795331989322314544746799
e=65537
g=1782714261471199600627912602675948124521242155026857581417496643395108146067670647314507299724027644449584417991370237640807949819393846820875335817261
enc=20350664281726403319264794434818308682046627973818456992245939179105629755654804516474027208643477028915373806837243260505684415739400790158679693158292815111799557125205151404100645653607777497253093260710715998875446908652240009553176151050618425031785922700834263127349910566138042780128833737173370642149352579347648172805592085834236458809040063106208561153446872735282875495007579182595935084451653408565873131518763369654422924777264084722832367604444283493236654780236432466093893715601405666605776325094892405077833019846528616538992220553807641215435015982473851848348382653049398621386187791517991659737573
nbits = 2048
gamma = 0.244
cbits = ceil(nbits * (0.5 - 2 * gamma))

M = (N - 1) // (2 * g)
u = M // (2 * g)
v = M - 2 * g * u
GF = Zmod(N)
x = GF.random_element()
y = x ^ (2 * g)
# c的范围大概与N^(0.5-2*gamma)很接近
c = bsgs(y, y ^ u, ((2**(cbits-1)), (2**(cbits+1))))
ab = u - c
apb = v + 2 * g * c
P.<x> = ZZ[]
f = x ^ 2 - apb * x + ab
a = f.roots()
if a:
    a, b = a[0][0], a[1][0]
    p = 2 * g * a + 1
    q = 2 * g * b + 1
    assert p * q == N

d = inverse(e,(p-1)*(q-1))
m = pow(enc,d,N)
print(long_to_bytes(m))
# flag{927ab370-fd1e-422d-8658-60b16447c86e}

apbq

task.py

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
65
66
67
68
69
70
71
72
73
74
75
76
from Crypto.Util.number import *
from secrets import flag
from math import ceil
import sys

class RSA():
    def __init__(self, privatekey, publickey):
        self.p, self.q, self.d = privatekey
        self.n, self.e = publickey

    def encrypt(self, plaintext):
        if isinstance(plaintext, bytes):
            plaintext = bytes_to_long(plaintext)
        ciphertext = pow(plaintext, self.e, self.n)
        return ciphertext

    def decrypt(self, ciphertext):
        if isinstance(ciphertext, bytes):
            ciphertext = bytes_to_long(ciphertext)
        plaintext = pow(ciphertext, self.d, self.n)
        return plaintext

def get_keypair(nbits, e = 65537):
    p = getPrime(nbits//2)
    q = getPrime(nbits//2)
    n = p * q
    d = inverse(e, n - p - q + 1)
    return (p, q, d), (n, e)

if __name__ == '__main__':
    pt = './output.txt'
    fout = open(pt, 'w')
    sys.stdout = fout

    block_size = ceil(len(flag)/3)
    flag = [flag[i:i+block_size] for i in range(0, len(flag), block_size)]
    e = 65537

    print(f'[+] Welcome to my apbq game')
    # stage 1
    print(f'┃ stage 1: p + q')
    prikey1, pubkey1 = get_keypair(1024)
    RSA1 = RSA(prikey1, pubkey1)
    enc1 = RSA1.encrypt(flag[0])
    print(f'┃ hints = {prikey1[0] + prikey1[1]}')
    print(f'┃ public key = {pubkey1}')
    print(f'┃ enc1 = {enc1}')
    print(f'----------------------')

    # stage 2
    print(f'┃ stage 2: ai*p + bi*q')
    prikey2, pubkey2 = get_keypair(1024)
    RSA2 = RSA(prikey2, pubkey2)
    enc2 = RSA2.encrypt(flag[1])
    kbits = 180
    a = [getRandomNBitInteger(kbits) for i in range(100)]
    b = [getRandomNBitInteger(kbits) for i in range(100)]
    c = [a[i]*prikey2[0] + b[i]*prikey2[1] for i in range(100)]
    print(f'┃ hints = {c}')
    print(f'┃ public key = {pubkey2}')
    print(f'┃ enc2 = {enc2}')
    print(f'----------------------')

    # stage 3
    print(f'┃ stage 3: a*p + q, p + bq')
    prikey3, pubkey3 = get_keypair(1024)
    RSA3 = RSA(prikey3, pubkey3)
    enc3 = RSA2.encrypt(flag[2])
    kbits = 512
    a = getRandomNBitInteger(kbits)
    b = getRandomNBitInteger(kbits)
    c1 = a*prikey3[0] + prikey3[1]
    c2 = prikey3[0] + b*prikey3[1] 
    print(f'┃ hints = {c1, c2}')
    print(f'┃ public key = {pubkey3}')
    print(f'┃ enc3 = {enc3}')

output.txt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[+] Welcome to my apbq game
┃ stage 1: p + q
┃ hints = 18978581186415161964839647137704633944599150543420658500585655372831779670338724440572792208984183863860898382564328183868786589851370156024615630835636170
┃ public key = (89839084450618055007900277736741312641844770591346432583302975236097465068572445589385798822593889266430563039645335037061240101688433078717811590377686465973797658355984717210228739793741484666628342039127345855467748247485016133560729063901396973783754780048949709195334690395217112330585431653872523325589, 65537)
┃ enc1 = 23664702267463524872340419776983638860234156620934868573173546937679196743146691156369928738109129704387312263842088573122121751421709842579634121187349747424486233111885687289480494785285701709040663052248336541918235910988178207506008430080621354232140617853327942136965075461701008744432418773880574136247
----------------------
┃ stage 2: ai*p + bi*q
┃ hints = []
┃ public key = (73566307488763122580179867626252642940955298748752818919017828624963832700766915409125057515624347299603944790342215380220728964393071261454143348878369192979087090394858108255421841966688982884778999786076287493231499536762158941790933738200959195185310223268630105090119593363464568858268074382723204344819, 65537)
┃ enc2 = 30332590230153809507216298771130058954523332140754441956121305005101434036857592445870499808003492282406658682811671092885592290410570348283122359319554197485624784590315564056341976355615543224373344781813890901916269854242660708815123152440620383035798542275833361820196294814385622613621016771854846491244
----------------------
┃ stage 3: a*p + q, p + bq
┃ hints = (68510878638370415044742935889020774276546916983689799210290582093686515377232591362560941306242501220803210859757512468762736941602749345887425082831572206675493389611203432014126644550502117937044804472954180498370676609819898980996282130652627551615825721459553747074503843556784456297882411861526590080037, 117882651978564762717266768251008799169262849451887398128580060795377656792158234083843539818050019451797822782621312362313232759168181582387488893534974006037142066091872636582259199644094998729866484138566711846974126209431468102938252566414322631620261045488855395390985797791782549179665864885691057222752)
┃ public key = (94789409892878223843496496113047481402435455468813255092840207010463661854593919772268992045955100688692872116996741724352837555794276141314552518390800907711192442516993891316013640874154318671978150702691578926912235318405120588096104222702992868492960182477857526176600665556671704106974346372234964363581, 65537)
┃ enc3 = 17737974772490835017139672507261082238806983528533357501033270577311227414618940490226102450232473366793815933753927943027643033829459416623683596533955075569578787574561297243060958714055785089716571943663350360324047532058597960949979894090400134473940587235634842078030727691627400903239810993936770281755

stage1

给出$h = p+q$，联立$n = p\times q$就能分解了

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

hints = 18978581186415161964839647137704633944599150543420658500585655372831779670338724440572792208984183863860898382564328183868786589851370156024615630835636170
n1,e1 = (89839084450618055007900277736741312641844770591346432583302975236097465068572445589385798822593889266430563039645335037061240101688433078717811590377686465973797658355984717210228739793741484666628342039127345855467748247485016133560729063901396973783754780048949709195334690395217112330585431653872523325589, 65537)
enc1 = 23664702267463524872340419776983638860234156620934868573173546937679196743146691156369928738109129704387312263842088573122121751421709842579634121187349747424486233111885687289480494785285701709040663052248336541918235910988178207506008430080621354232140617853327942136965075461701008744432418773880574136247

p_add_q = hints
p_sub_q = gmpy2.iroot(p_add_q^2 - 4*n1,2)[0]

p1 = (p_add_q + p_sub_q) // 2
q1 = (p_add_q - p_sub_q) // 2
d1 = inverse(e1,(p1-1)*(q1-1))
m1 = pow(enc1,d1,n1)
flag1 = long_to_bytes(m1)
print(flag1)
# flag{yOu_can_

stage2

第二部分类似于DownUnderCTF2023的ap+bq-ii。今年华为杯也有这题。找到这个exp：my-ctf-challenges/downunderctf-2023/apbq-rsa-ii/solve/solv.sage at main · josephsurin/my-ctf-challenges

拿原有的exp打了一下发现没打出来，试过爆破一些高位，但无果，后面索性多用些数据，没想到4个数据就分解了。

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

# n, c, hints
hints = []
n, e = (73566307488763122580179867626252642940955298748752818919017828624963832700766915409125057515624347299603944790342215380220728964393071261454143348878369192979087090394858108255421841966688982884778999786076287493231499536762158941790933738200959195185310223268630105090119593363464568858268074382723204344819, 65537)
enc2 = 30332590230153809507216298771130058954523332140754441956121305005101434036857592445870499808003492282406658682811671092885592290410570348283122359319554197485624784590315564056341976355615543224373344781813890901916269854242660708815123152440620383035798542275833361820196294814385622613621016771854846491244

V = hints[:4]
k = 2^800
M = Matrix.column([k * v for v in V]).augment(Matrix.identity(len(V)))
B = [b[1:] for b in M.LLL()]
M = (k * Matrix(B[:len(V)-2])).T.augment(Matrix.identity(len(V)))
B = [b[-len(V):] for b in M.LLL() if set(b[:len(V)-2]) == {0}]

for s, t in itertools.product(range(4), repeat=2):
    T = s*B[0] + t*B[1]
    a1, a2, a3, a4 = T
    kq = gcd(a1 * hints[1] - a2 * hints[0], n)
    if 1 < kq < n:
        print('find!', kq, s, t)
        break
for i in range(2**16, 1, -1):
    if kq % i == 0:
        kq //= i
q = int(kq)
p = int(n // kq)
d = pow(0x10001, -1, (p - 1) * (q - 1))
m = pow(enc2, d, n)
flag = long_to_bytes(m).decode()
print(flag)
enc3 = 17737974772490835017139672507261082238806983528533357501033270577311227414618940490226102450232473366793815933753927943027643033829459416623683596533955075569578787574561297243060958714055785089716571943663350360324047532058597960949979894090400134473940587235634842078030727691627400903239810993936770281755
flag = long_to_bytes(pow(enc3,d,n)).decode()
print(flag)
# flag{yOu_can_s0lve_the_@pbq_prob1em!!}

stage3——unsolved

比赛的时候第三部分参数和第二部分一样，直接拿第二部分的私钥解密enc3即可。

赛后找到ctf/angstromctf-2024/blahaj/solve.sage at master · defund/ctf

原题代码

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
p = random_prime(2**1024)
q = random_prime(2**1024)
a = randint(0, 2**1024)
b = randint(0, 2**1024)

def read_flag(file='flag.txt'):
    with open(file, 'rb') as fin:
        flag = fin.read()
    return flag

def pad_flag(flag, bits=1024):
    pad = os.urandom(bits//8 - len(flag))
    return int.from_bytes(flag + pad, "big")

def generate_keys(p, q):
    n = p * q
    e = 0x10001
    return n, e

def encrypt_message(m, e, n):
    return pow(m, e, n)

flag = read_flag()
m = pad_flag(flag)

n, e = generate_keys(p, q)
assert m < n

c = encrypt_message(m, e, n)

print(c)
print(n)
print(p + b * q)
print(a * p + q)

exp

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
x = 68510878638370415044742935889020774276546916983689799210290582093686515377232591362560941306242501220803210859757512468762736941602749345887425082831572206675493389611203432014126644550502117937044804472954180498370676609819898980996282130652627551615825721459553747074503843556784456297882411861526590080037
y = 117882651978564762717266768251008799169262849451887398128580060795377656792158234083843539818050019451797822782621312362313232759168181582387488893534974006037142066091872636582259199644094998729866484138566711846974126209431468102938252566414322631620261045488855395390985797791782549179665864885691057222752
n = 94789409892878223843496496113047481402435455468813255092840207010463661854593919772268992045955100688692872116996741724352837555794276141314552518390800907711192442516993891316013640874154318671978150702691578926912235318405120588096104222702992868492960182477857526176600665556671704106974346372234964363581
c = 17737974772490835017139672507261082238806983528533357501033270577311227414618940490226102450232473366793815933753927943027643033829459416623683596533955075569578787574561297243060958714055785089716571943663350360324047532058597960949979894090400134473940587235634842078030727691627400903239810993936770281755
e = 65537

R = Integers(n)
P.<a, b, p, q> = PolynomialRing(Integers(n))
f1 = a*p + q
f2 = p + b*q
f3 = p*q
I = Ideal([f1 - x, f2 - y, f3 - n])
B = I.groebner_basis()

g = B[-1]

z = ZZ(g.coefficient({q: 1}))
assert g.constant_coefficient() == R(-y)

_, (z1, _), (z2, _) = list(g)
z1 = ZZ(z1)
z2 = ZZ(z2)

S = 2^1024
for p_upper_bits in range(16):
	p_upper = p_upper_bits << 1020
	for q_upper_bits in range(16):
		q_upper = q_upper_bits << 1020
		M = matrix(ZZ, [[S, -1, 0, 0], [S*z1, 0, -1, 0], [S*(z2 + p_upper + q_upper*z1), 0, 0, S], [S*n, 0, 0, 0]])
		B = M.LLL()
		for b in B:
			if b[-1] == S:
				if b[1] < 0:
					b *= -1

				p_guess = b[1] + p_upper
				q_guess = b[2] + q_upper
				if p_guess * q_guess == n:
					d = pow(e, -1, (p_guess - 1)*(q_guess - 1))
					print(int(pow(c, d, n)).to_bytes(1024//8, 'big'))
					exit()

没打出来

21_steps

问GPT如何用python在21步内计算128bit值的汉明重量，得到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def hamming_weight(x):
    # 1. 分离每一位和其邻位，并相加（每2位一组）
    x = x - ((x >> 1) & 0x55555555555555555555555555555555)
    
    # 2. 将每4位一组中的前2位和后2位相加
    x = (x & 0x33333333333333333333333333333333) + ((x >> 2) & 0x33333333333333333333333333333333)
    
    # 3. 将每8位一组中的前4位和后4位相加
    x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F
    
    # 4. 将每16位一组中的前8位和后8位相加
    x = (x * 0x01010101010101010101010101010101) & 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
    
    # 5. 将所有累加的结果移到最低位，并提取结果
    return (x >> 120) & 0x7F  # 最高7位足以表示128的汉明权重

# 示例
binary_number = 0b110101011011011011011111000110110111011111010111011110110111101101111111110111011111011111010101011101010110101010
print(hamming_weight(binary_number))

然后一步一步改成符合正则的式子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
B=A>>1;
B=B&113427455640312821154458202477256070485;
A=A-B;
# 实现x = x - ((x >> 1) & 0x55555555555555555555555555555555)
B=A>>2;
B=B&68056473384187692692674921486353642291;
A=A&68056473384187692692674921486353642291;
A=A+B;
# 实现x = (x & 0x33333333333333333333333333333333) + ((x >> 2) & 0x33333333333333333333333333333333)
B=A>>4;
A=A+B;
A=A&20016609818878733144904388672456953615;
# 实现x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F
B=A*1334440654591915542993625911497130241;
A=B&340282366920938463463374607431768211455;
# 实现x = (x * 0x01010101010101010101010101010101) & 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
B=A>>120;
A=B&127;

一步一步检查是否正确

test.py

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
def hamming_weight(x):
    # 1. 分离每一位和其邻位，并相加（每2位一组）
    x = x - ((x >> 1) & 0x55555555555555555555555555555555)
    print(f"x1={x}")
    # 2. 将每4位一组中的前2位和后2位相加
    x = (x & 0x33333333333333333333333333333333) + ((x >> 2) & 0x33333333333333333333333333333333)
    print(f"x2={x}")
    # 3. 将每8位一组中的前4位和后4位相加
    x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F0F
    print(f"x3={x}")
    # 4. 将每16位一组中的前8位和后8位相加
    x = (x * 0x01010101010101010101010101010101) & 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
    print(f"x4={x}")
    # 5. 将所有累加的结果移到最低位，并提取结果
    return (x >> 120) & 0x7F  # 最高7位足以表示128的汉明权重

import random

binary_number = random.getrandbits(128)
print(hamming_weight(binary_number))

A=0b110101011011011011011111000110110111011111010111011110110111101101111111110111011111011111010101011101010110101010
B=A>>1
B=B&113427455640312821154458202477256070485
A=A-B
print(f"A1={A}")
B=A>>2
B=B&68056473384187692692674921486353642291
A=A&68056473384187692692674921486353642291
A=A+B
print(f"A2={A}")
B=A>>4
A=A+B
A=A&20016609818878733144904388672456953615
print(f"A3={A}")
B=A*1334440654591915542993625911497130241
A=B&340282366920938463463374607431768211455
print(f"A4={A}")
B=A>>120;A=B&127
print(A)

最后传

1
B=A>>1;B=B&113427455640312821154458202477256070485;A=A-B;B=A>>2;B=B&68056473384187692692674921486353642291;A=A&68056473384187692692674921486353642291;A=A+B;B=A>>4;A=A+B;A=A&20016609818878733144904388672456953615;B=A*1334440654591915542993625911497130241;A=B&340282366920938463463374607431768211455;B=A>>120;A=B&127;

traditional_game

step1

同时开两个靶机sh1和sh2，大概率使得seed一样，这样在sh1中一直输入1，如果错误的话，sh2就输入0，反之输入1

step2

尝试：

d_的生成原理是，先把d的高659位整除blind，最后加上(d % blind)，那么我记准确的高659位为$d_h$，实际上我们得到的是$d_h’$，其中dh' = d_ >> unknown_bit。并且
$$
d_h = d_h’ + x
$$
这个x的值和blind同数量级

$$
d = ((d_h’+ x)\times 2^{365} + y)\times blind + d_l
$$
取dh = d_ >> 365

$$
d = d_h\times 2^{365} + d_x\times blind + d_l
$$

$$
e[((d_h’ + x)\times 2^{365} + y)\times blind + d_l] = 1 + k[(n+1)-(p+q)]
$$

于是有
$$
(ed_h’\times 2^{365}\times blind) + (ex\times2^{365} + y)\times blind + ed_l = 1 + k[(n+1)-(p+q)]
$$
k可以用这个式子计算得到，$k = \frac{ed_h\times 2^{365}}{n} + 1$

在模$ed_h\times 2^{365}\times blind$下建立多项式
$$
f = 1 + k[(n+1) - z] - ed_l - (ex\times 2^{365} + y)\times blind \mod (ed_h’\times 2^{365}\times blind)
$$
无果

正解：根据论文：Small Public Exponent Brings More: Improved Partial Key Exposure Attacks against RSA

根据论文一步一步实现攻击即可

第一步是计算$k$，我用$k = \frac{e\times d_h}{n} + 1$计算，经检验是准确的。

第二步拿dh，前面就拿了

第三步是恢复p的高位。根据论文中，先令$S = N + 1 - \frac{(e\times d_h)}{k}$，$D = \sqrt{S^2 - 4n}$，计算$p_h = \frac{S + D}{2}$，这样得到的高位大概有105位正确

第四步是求$p \mod blind$，根据式子$ed_l \equiv 1 + k(n+1 - p- q) \mod blind$，这里可以计算出$p + q \equiv k^{-1}(1 + k(n + 1) - ed_l) \mod blind$，记s = p+q，然后解一元二次方程:$x^2 - sx + n \mod blind$，得到$p \mod blind$的值

第五步是求$p \mod e$，和上面的思路一样

第六步分解n

我们现在有
$$
p_1 \equiv p \mod e
$$

$$
p_2 \equiv p \mod blind
$$

用中国剩余定理求$p_l \equiv p \mod e\times blind$

然后看作$p = t\times (e\times blind) + p_l$，这个t可以用$t_0 = \frac{p_h - p_l)}{e\times blind}$来近似，那么就有$p = (t_0 + x)\times (e\times blind) + p_l$，这个x的差值差不多是240-245bit左右

用coppersmith求小根

exp.sage

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
from Crypto.Util.number import *
from tqdm import *
import gmpy2
from pwn import *

sh1 = remote("",)
sh2 = remote("",)

sh1.recvuntil(b"[+] Welcome to the game!")
sh2.recvuntil(b"[+] Welcome to the game!")
sh1.recvuntil(b"[+] rsa public key:")
sh2.recvuntil(b"[+] rsa public key:")
public_key = eval(sh2.recvline().strip().decode())
for i in range(100):
    sh1.recvuntil(b"[-] b:")
    sh1.sendline(b"1")
    sh2.recvuntil(b"[-] b:")
    if b"wrong!" in sh1.recvline().strip():
        sh2.sendline(b"0")
        print(sh2.recvline().strip())
    else:
        sh2.sendline(b"1")
        print(sh2.recvline().strip())

blind_bit = 40
unknown_bit = 365
n,e = public_key
print(f"n = {n}")
print(f"e = {e}")
sh2.recvuntil(b"privkey is:")
d_,blind = eval(sh2.recvline().strip().decode()[:-1])
print(f"d_ = {d_}")
print(f"blind = {blind}")
sh2.recvuntil(b"encrypt token is:")
c = eval(sh2.recvline().strip().decode())
print(f"c = {c}")

dh = d_ >> (unknown_bit + blind_bit) << (unknown_bit + blind_bit)
dl = d_ % blind

# step1 calculate k
k = (e*dh) // n + 1
# step2 dh
# step3 recover the MSBs of p
S = n + 1 - ((e*dh - 1) // k)
D = gmpy2.iroot(abs(S**2 - 4*n),2)[0]
ph = int((S + D) // 2) >> (512 - 105) << (512 - 105)

# step4 calculate p+q % blind
s = inverse(k,blind) * (1 + k * (n+1) - e*dl) % blind
R.<x> = PolynomialRing(Zmod(blind))
f = x^2 - s*x + n
res = f.roots()
may_p_mod_blind = [int(res[0][0]),int(res[1][0])]

# step5 calculate p+q % e
k_inv = inverse(k,e)
s = (n + 1 + k_inv) % e

# step6 factor n
R.<x> = PolynomialRing(Zmod(e))
f = x^2 - s*x + n
res = f.roots()
may_p_mod_e = [int(res[0][0]),int(res[1][0])]
moduls = int(blind) * int(e)

for p_mod_e in may_p_mod_e:
    for p_mod_blind in may_p_mod_blind:
        pl = crt([p_mod_blind,p_mod_e],[blind,e])
        th = (ph - pl) // moduls
        PR.<x> = PolynomialRing(Zmod(n))
        f = (th + x) * moduls + pl
        for i in trange(240, 246):
            roots = f.monic().small_roots(X=2^i,beta=0.49,epsilon=0.02)
            if roots != []:
                p = int(f(roots[0]))
                if n % p == 0:
                    print(p)
                    q = n // p
                    d = inverse(e,(p-1)*(q-1))
                    m = pow(c,d,n)
                    msg = long_to_bytes(m)
                    print(msg.hex())
                    sh2.sendlineafter(b"[-] guess token:",msg.hex())
                    print(sh2.recvline())
                    break

-------------已经到底啦！-------------