青少年CTF擂台挑战赛2024Round1

解个方程

题目

一个动态flag

p = 151655885656450332076952504214322757273  
q = 148531443385360803011533167272599291111  
e = 65537
d = ?

解答

import gmpy2  
p = 151655885656450332076952504214322757273  
q = 148531443385360803011533167272599291111  
e = 65537  
n = q*p  
phi = (p-1)*(q-1)  
d = gmpy2.invert(e,phi)  
print(d)

'''
1288909371486973234158599185728560686247715008971192466783006826206253573473

ez_log

题目：

from Crypto.Util.number import *
from random import *
flag=b'key{xxxxxxx}'
m=bytes_to_long(flag)
p=3006156660704242356836102321001016782090189571028526298055526061772989406357037170723984497344618257575827271367883545096587962708266010793826346841303043716776726799898939374985320242033037
g=3
c=pow(g,m,p)
print(f'c=',c)

"""
c=2992612627750886887770858313476352707594644300807594304705044416699839774471838751545708692735859654685857490788683751410989270851331507477475091396007893070015119892479188689286417701654825

解答：

#sage
m = discrete_log(mod(c,p),mod(g,p))
#或者可以省略，直接写
m = discrete_log(c,mod(g,p))
from Crypto.Util.number import *
long_to_bytes(129834262657483951719921277)
"""
b'key{X8fba6}'

输入容器得到flag

ezrsa

题目

from Crypto.Util.number import *
flag = b'qsnctf{xxx-xxxx-xxxx-xxxx-xxxxxxxxx}'
m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
r = getPrime(512)
n = p * q * r
leak = p * q
e = 0x10001
c = pow(m, e, n)
print(f'c = {c}')
print(f'n = {n}')
print(f'leak = {leak}')
'''
# c = 173595148273920891298949441727054328036798235134009407863895058729356993814829340513336567479145746034781201823694596731886346933549577879568197521436900228804336056005940048086898794965549472641334237175801757569154295743915744875800647234151498117718087319013271748204766997008772782882813572814296213516343420236873651060868227487925491016675461540894535563805130406391144077296854410932791530755245514034242725719196949258860635915202993968073392778882692892
# n = 1396260492498511956349135417172451037537784979103780135274615061278987700332528182553755818089525730969834188061440258058608031560916760566772742776224528590152873339613356858551518007022519033843622680128062108378429621960808412913676262141139805667510615660359775475558729686515755127570976326233255349428771437052206564497930971797497510539724340471032433502724390526210100979700467607197448780324427953582222885828678441579349835574787605145514115368144031247
# leak = 152254254502019783796170793516692965417859793325424454902983763285830332059600151137162944897787532369961875766745853731769162511788354655291037150251085942093411304833287510644995339391240164033052417935316876168953838783742499485868268986832640692657031861629721225482114382472324320636566226653243762620647

分析

$$\begin{align} &c\equiv m^{e}\pmod{n} \\ &c\equiv m^{e}\pmod{p*q*r}\\ &c\equiv m^{e}\pmod{r} \end{align}$$

解答

from Crypto.Util.number import long_to_bytes  
import gmpy2  
c = 
n =  
leak =  
e = 0x10001  
  
r = n//leak  
phi = r-1  
d = gmpy2.invert(e, phi)  
m = pow(c, d, r)  
print(long_to_bytes(m))

'''
qsnctf{12ff81e0-7646-4a96-a7eb-6a509ec01c9e}

factor1

题目

import gmpy2
import hashlib
from Crypto.Util.number import *

p = getPrime(512)
q = getPrime(512)
d = getPrime(256)
e = gmpy2.invert(d, (p**2 - 1) * (q**2 - 1))
flag = "qsnctf{" + hashlib.md5(str(p + q).encode()).hexdigest() + "}"
print(e)
print(p * q)
#4602579741478096718172697218991734057017874575484294836043557658035277770732473025335441717904100009903832353915404911860888652406859201203199117870443451616457858224082143505393843596092945634675849883286107358454466242110831071552006337406116884147391687266536283395576632885877802269157970812862013700574069981471342712011889330292259696760297157958521276388120468220050600419562910879539594831789625596079773163447643235584124521162320450208920533174722239029506505492660271016917768383199286913178821124229554263149007237679675898370759082438533535303763664408320263258144488534391712835778283152436277295861859
#78665180675705390001452176028555030916759695827388719494705803822699938653475348982551790040292552032924503104351703419136483078949363470430486531014134503794074329285351511023863461560882297331218446027873891885693166833003633460113924956936552466354566559741886902240131031116897293107970411780310764816053

解答:

这道是参考+复现

$$\begin{align} (p^2-1)(q^2-1)&=(pq)^2-(p^2+q^2)+1\\ ed&\equiv1\mod (p^2-1)(q^2-1)\\ ed-k*(p^2-1)(q^2-1)&=1\\ (p^2-1)(q^2-1)&>2d\\ \left|\frac{e}{(p^2-1)(q^2-1)}-\frac{k}{d}\right|&=\frac{1}{(p^2-1)(q^2-1)*d}<\frac{1}{2d^2} \end{align}$$

用wiener恢复出k,d，$(p^2-1)(q^2-1)$与$p^2q^2$相差$p^2+q^2-1$，相应数量级位2046和1025，故可忽略不计，将其用$p^2q^2$进行连分数渐进

$$\begin{align} p^2+q^2&=(pq)^2-(p^2-1)(q^2-1)+1\\ p+q&=\sqrt{p^2+q^2+2pq}\\ p-q&=\sqrt{p^2+q^2-2pq} \end{align}$$

在sage中有two_squares函数，可以暴力算$p^2+q^2$的形式，但本题数据有点大，没有跑出来。

#sage 
from Crypto.Util.number import *
 
from gmpy2 import iroot
 
import hashlib
 
e = 4602579741478096718172697218991734057017874575484294836043557658035277770732473025335441717904100009903832353915404911860888652406859201203199117870443451616457858224082143505393843596092945634675849883286107358454466242110831071552006337406116884147391687266536283395576632885877802269157970812862013700574069981471342712011889330292259696760297157958521276388120468220050600419562910879539594831789625596079773163447643235584124521162320450208920533174722239029506505492660271016917768383199286913178821124229554263149007237679675898370759082438533535303763664408320263258144488534391712835778283152436277295861859
 
pq = 78665180675705390001452176028555030916759695827388719494705803822699938653475348982551790040292552032924503104351703419136483078949363470430486531014134503794074329285351511023863461560882297331218446027873891885693166833003633460113924956936552466354566559741886902240131031116897293107970411780310764816053
 
pqx = pq ^ 2
 
fra = (e/pqx).continued_fraction()
 
for i in range(1, len(fra)):
 
    k, d = fra.numerator(i), fra.denominator(i)
 
    if (e*d - 1) % k == 0 and d > 2^250:
 
        print(k, d)
 
        break
 
temp = (e*d - 1) // k
 
pq_square = pqx - temp + 1
 
p_q = iroot(pq_square - 2*pq, 2)[0]
 
p__q = iroot(pq_square + 2*pq, 2)[0]
 
q = (p_q + p__q) // 2
 
p = pq // q
 
flag = "qsnctf{" + hashlib.md5(str(p + q).encode()).hexdigest() + "}"
 
print(flag)

'''
qsnctf{8072e8b2982bc729cc74ef58f1abc862}

四重加密

复现‘是在网上下载了一 随波逐流 CTF编码工具
压缩包在WinRAR打开查看
![[https://s2.loli.net/2024/03/21/RQ7tdHChoEWvTzY.png]]
base32解码得到：qsnctf
解压得txt：
zcye{mxmemtxrzt_lzbha_kwmqzec}|key=hello
是unicoed，转ASCII：zcye{mxmemtxrzt_lzbha_kwmqzec}|key=hello
![[https://s2.loli.net/2024/03/21/4yYPsTfRJHSmAjU.png]]
还没有得到flag，再解：
![[https://s2.loli.net/2024/03/21/UKCbT8hqHviW5uV.png]]