NCTF Crypto

发表于 2022-01-19 更新于 2024-03-18 分类于 Crypto ， WriteUp

NCTF Crypto 题目复现

\[ k = (p*2^{1024})//(q+r)--> p*2^{1024}=k*(q+r)+m--> 2^{1024}/k=(q+r)/p+m/(k*p) \]

其中k*p>>m，故 \[ 2^{1024}/k 略大于 (q+r)/p \] 对 2**1024/k 进行连分数逼近，可以覆盖到(q+r)/p这个数（类似维纳攻击），再对p,q,r求解运算求出d，解出明文

import gmpy2
from Crypto.Util.number import*
def transform(x,y):       #使用辗转相处将分数 x/y 转为连分数的形式
	res=[]
	while y:
		res.append(x//y)
		x,y=y,x%y
	return res

def continued_fraction(sub_res):
	numerator,denominator=1,0
	for i in sub_res[::-1]:      #从sublist的后面往前循环
		denominator,numerator=numerator,i*numerator+denominator
	return denominator,numerator   #得到渐进分数的分母和分子，并返回

    
#求解每个渐进分数
def sub_fraction(x,y):
	res=transform(x,y)
	res=list(map(continued_fraction,(res[0:i] for i in range(1,len(res)))))  #将连分数的结果逐一截取以求渐进分数
	return res


def wienerAttack(t,k):
	for (p,sumqr) in sub_fraction(t,k):  #用一个for循环来注意试探e/n的连续函数的渐进分数，直到找到一个满足条件的渐进分数
		if sumqr==0:                     #可能会出现连分数的第一个为0的情况，排除
			continue
		if isPrime(p):
			if n%p==0:
				print(p)
				print(sumqr)
		return p, sumqr
	
t = 2**1024
k = 94541588860584895585135152950569493777168309607384495730944110393788712443252059813470464503558980161423182930915955597122997950103392684040352673659694990925903156093591505153081718027169554019948988048641061593654540898258994671824807628660558123733006209479395447337793897155523508261277918178756662618785
n=780382574657056148524126341547161694121139907409040429176771134165303790043856598163799273195157260505524054034596118923390755532760928964966379457317135940979046201401066257918457068510403020146410174895470232276387032511651496790519359024937958635283547294676457588680828221680705802054780628993173199987362419589945445821005688218540209709368995166794607635504501281131700210990592718388166388793182269128127850804650083811982799377308916540691843310867205397
p,sumqr=wienerAttack(t,k)

得到p，与q+r，sage解方程得到p,q,r的值~~（我是懒鬼）~~

然后ezRsa

from Crypto.Util.number import*
p=9591034708161364221769733163551836281062083244512519384396165987809544507968391606587728397659016542948096617311787604058178460710869231247971978002127911
q=7783303527956388882925926241649086816516401013818809868989894869944824560842420253258139068646778092017713916219975429637932259781411715380715911885101359
r=10453894999046673647308947017087829722773272707345254431452943862698229414154549643006087444848992128177899286390321602677342098868495750510174086311850253
n=780382574657056148524126341547161694121139907409040429176771134165303790043856598163799273195157260505524054034596118923390755532760928964966379457317135940979046201401066257918457068510403020146410174895470232276387032511651496790519359024937958635283547294676457588680828221680705802054780628993173199987362419589945445821005688218540209709368995166794607635504501281131700210990592718388166388793182269128127850804650083811982799377308916540691843310867205397
phi=(p-1)*(q-1)*(r-1)
e=65537
d=inverse(e,phi)
c=601133470721804838247833449664753362221136965650852411177773274117379671405966812018926891137093789704412080113310175506684194683631033003847585245560967863306852502110832136044837625931830243428075035781445021691969145959052459661597331192880689893369292311652372449853270889898705765869674961705116875378568712306021536838123003111819172078652012105725060809972222290408551883774305223612755026614701916201374200602892717051698568751566665976546137674450533774
m=pow(c,d,n)
print(long_to_bytes(m))

得到b'nctf{238fa78a-5e61-4dc6-8faf-7e2e30e02286}'

rsa

将一个16位长度的字节型数据分成四份，每份转换为long之后为32bits

而一个32bits的数字有很大概率可以分解为i(20bits)*j(16bits) 或者更低（

那么我们可以在给出的120s时间内建表然后通过验证，再以极短的时间爆破出c \[ m^e=i^e*j^e \]

\[ c≡i^e*j^e\ \ \ (mod\ n)\ \ \ \ \ \ \ \ -1 \]

\[ inv(c)*j^e≡inv(i^e)\ \ \ (mod\ n)\ \ \ \ \ \ \ \ -2 \]

建表{ pow(i,-e,n) : i }

破解验证码发送

穷举j，使满足2式，然后就能得到对应的m了

由于本fw的脚本太过lj，于是贴上官方wp给的jio本

from Crypto.Util.number import *
from pwn import *
from tqdm import tqdm
def proof_of_work():
	rev = r.recvuntil(b"sha256(XXXX+")
	suffix = r.recv(16).decode()
	rev = r.recvuntil(b" == ")
	tar = r.recv(64).decode()
	def f(x):
		hashresult = hashlib.sha256(x.encode()+suffix.encode()).hexdigest()
		return hashresult == tar
	prefix = util.iters.mbruteforce(f, string.digits + string.ascii_letters, 4, 'upto')
	r.recvuntil(b'Give me XXXX: ')
	r.sendline(prefix.encode())
e = 65537

while True:
	r = remote("43.129.69.35",10002)
	r.recvuntil(b'n = ')
	n = int(r.recvline().strip())
	S = {pow(i,-e,n):i for i in tqdm(range(1,2**20))}
	
	proof_of_work()
	secret = ''
	for i in range(4):
		c = int(r.recvline().split(b'=')[1].strip())
		l = inverse(c,n)
		for j in range(1,2**16):
			s = l*pow(j,e,n)%n
			if s in S:
				secret += hex(S[s]*j)[2:].zfill(8)
				break
	print(len(secret),secret)
	if len(secret)!=32:
		r.close()
		continue
	r.recvuntil(b"Give me the secret:")
	r.sendline(secret.encode())
	r.interactive()

NCTF Crypto 题目复现

signin

rsa