Nanxer's blog

外观

H&NCTF2025

约 1420 字大约 5 分钟

crypto

2025-06-08

哈吉coke

原先的两个生成式子转化一下,解一个二元一次方程组,得到逆向式，代入跑一下即可(那个库没装好，用image凑合下)

import matplotlib.pyplot as plt
import numpy as np
from PIL import Image
from Crypto.Util.number import *

def arnold_decode(image, shuffle_times, a, b):
    h, w = image.shape[0], image.shape[1]
    N = h
    arnold_decode_image = np.zeros(shape=image.shape)

    for time in range(shuffle_times):
        for ori_x in range(h):
            for ori_y in range(w):
                y = (ori_y - a*ori_x) % N
                x = (ori_x - b*y) % N

                arnold_decode_image[x, y, :] = image[ori_x, ori_y, :]

        image = np.copy(arnold_decode_image)

    decoded_image_pil = Image.fromarray(np.uint8(arnold_decode_image))
    decoded_image_pil.save('decoded_coke.png', compress_level=0)
    return arnold_decode_image

# 读取编码后的图像并进行解码
encoded_img_pil = Image.open('en_flag.png')
encoded_img = np.array(encoded_img_pil)
decoded_img = arnold_decode(encoded_img, 6, 9, 1)

lcgp

用groebner_basis()求出m，解线性方程组得到a和b，恢复seed，后边是一个p-1光滑的离散对数问题

from Crypto.Util.number import *

cc=[]
n=604805773885048132038788501528078428693141138274580426531445179173412328238102786863592612653315029009606622583856638282837864213048342883583286440071990592001905867027978355755042060684149344414810835371740304319571184567860694439564098306766474576403800046937218588251809179787769286393579687694925268985445059

"""
R.<a, b> = PolynomialRing(ZZ)

f1 = cc[0]*a+b - cc[1]
f2 = cc[1]*a+b - cc[2]
f3 = cc[2]*a+b - cc[3]
f4 = cc[3]*a+b - cc[4]

F = [f1, f2, f3, f4]
I = Ideal(F).groebner_basis()

m = I[-1]
print(m)
"""
m = 17685238729089629081000199791073775580173848219782600577303616658328942786376878589055722139055973814631247947507009292556525580971952751595622172013382374577299734041726162411213993858497140178230251563824957482883763872967881950049985507310408962206729214890421322185752340466578359217999838551622613116097987673746844913920603425686103175874552686869764028906518131374266999714020645422015426801070343771422250037085635856203202935123956520415086942807824199018302630540169113637093488756273183240186533936637562954227188102214396705205042491881526862572569275650908415160529650027016717502470758797514488134766043

# A = Matrix(ZZ, [[cc[i], 1] for i in range(2)])
# B = vector(ZZ, [cc[i + 1] for i in range(2)])

# a,b = A.solve_right(B) % n
# print(f'a = {a}\nb = {b}')

a = 114639391295096853251612556825424912332678858383511980037292109727674744136577
b = 93832859253688755553822283464268412913296578295483854293903270701758530321487

# cc[0] = (a * seed + b) % m
# seed = (cc[0]-b)*inverse(a, m) % m
# print(seed)

c = 98136663393066487319477131255488756533037186459124433869847045986870213783395243380337142782779765255670853582334927187474123853371504168896312528278296763527266828907487342102002206806408616944398694810398049626860321901229014612541564249969665358849039818103044159048535403863928440335143886672949700153798350

p=n
G=GF(p)
m = discrete_log(G(c),G(2024))
print(long_to_bytes(m))
# b'H&NCTF{7ecf4c8c-e6a5-45c7-b7de-2fecc31d8511}'

为什么出题人的rsa总是ez

part1去年强网杯的apdq第三部分，part2可参考去年强网杯的Easyrsa，p-1和q-1有公共大因子

part1

from Crypto.Util.number import *

c=
n=
e = 0x10001

"""
h1=6992022576367328281523272055384380182550712894467837916200781058620282657859189270338635886912232754034211897894637971546032107000253692739473463119025570291091085702056938901846349325941043398928197991115231668917435951127329817379935880511925882734157491821315858319170121031835598580384038723788681860763814776365440362143661999054338470989558459179388468943933975861549233231199667742564080001256192881732567616103760815633265325456143601649393547666835326272408622540044065067528568675569233240785553062685974593620235466519632833169291153478793523397788719000334929715524989845012633742964209311952378479134661
h2=16731800146050995761642066586565348732313856101572403535951688869814016691871958158137790504490910445304384109605408840493227057830017039824412834989258703833576252634055087138315434304691218949240382395879124201923060510497916818961571111218224960267593032380037212325935576750663442553781924370849537501656957488833521657563900462052017695599020610911371304659875887924695896434699048696392210066253577839887826292569913713802634067508141124685789817330268562127695548527522031774601654778934513355315628270319037043809972087930951609429846675450469414212384044849089372435124609387061864545559812994515828333828939
x = h2
y = h1
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

def run():
    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:
                        print("p=",p_guess)
                        print("q=",q_guess)
                        return
run()
"""

p= 177188903285208307296042325337718015070655966550016849028622684895094994530212031016077478657820294659863380087882438642551865895876610089785688582159581077163878172279272664130902330048802699551787625218282191061369731999218514018283838127417774124079449425744547307723663295068039399770055798019129196328737
q= 77421764304371516785830207119218195629740062757289214574806372572009324268810656196398704095896732565388883789325878708426448197358847849305068830018367523348775355938562535952043518151103113628048467358783207610070925380543689515588622304430181304811333093745360491647924456778377701448561214951376869138477

print(long_to_bytes(pow(c,inverse(e, (p-1)*(q-1)), n)))
# b'flag{e_is_xevaf-cityf-fisof-ketaf-metaf-disef-nuvaf-cysuf-dosuf-getuf-cysuf-dasix,bubbleBabble}\xea\xc7P|OQ\x0f\xbc\xdcL;@-\x04\x9de\xd4\x14\xa7vNN\xa1\xce$T\xfd\x12\xc4\x9b\xfe\xeew'
# e = 81733668723981020451323

part2

from Crypto.Util.number import *
import sympy
from gmpy2 import iroot

P.<a,b,g,h,N> = PolynomialRing(ZZ)
h = 2*g*a*b+a+b
N = 2*h*g+1
print(N.factor())
# (2*b*g + 1) * (2*a*g + 1)

n=10244621233521168199001177069337072125430662416754674144307553476569744623474797179990380824494968546110022341144527766891662229403969035901337876527595841503498459533492730326942662450786522178313517616168650624224723066308178042783540825899502172432884573844850572330970359712379107318586435848029783774998269247992706770665069866338710349292941829996807892349030660021792813986069535854445874069535737849684959397062724387110903918355074327499675776518032266136930264621047345474782910332154803497103199598761422179303240476950271702406633802957400888398042773978322395227920699611001956973796492459398737390290487
g=2296316201623391483093360819129167852633963112610999269673854449302228853625418585609211427788830598219647604923279054340009043347798635222302374950707
c=7522161394702437062976246147354737122573350166270857493289161875402286558096915490526439656281083416286224205494418845652940140144292045338308479237214749282932144020368779474518032067934302376430305635297260147830918089492765917640581392606559936829974748692299762475615766076425088306609448483657623795178727831373194757182797030376302086360751637238867384469269953187938304369668436238848537646544257504724753333177938997524154486602644412199535102323238852958634746165559537630341890450666170836721803871120344373143081664567068672230842855208267929484000179260292518351155693154372172449820053764896414799137097

"""
b=2*g
D=int(iroot(n,4)[0]/b)*3
u,v=divmod((n-1)//b,b)
a=pow(3,b,n)
l=[pow(a,r*D,n) for r in range(D+1)]

for s in range(D+1):
    if pow(a,u-s,n) in l:
        r=l.index(pow(a,u-s,n))
        c=r*D+s
        x,y=sympy.symbols('x,y')
        r=sympy.solve([x+y-c*b-v,x*y-u+c])[0]
        x,y=r[x],r[y]
        p,q=int(x*b+1),int(y*b+1)
        break

print(f'p={p}')
print(f'q={q}')
"""
p=89689471847596377741222144429998037990667180177357564376140367776414308387012923411995322262858328353318533567758158657166891766790825298883408932478365300323143798943782413227199460096726803837011408747331311614322911225425264615177532865042145570988661750629687056545931523546752474174278821175282246381821
q=114223230692329221233593176873809300402703143063931397822580003361438712054166147412606967205124955861521969519047697209787311806459638088623102779532442176190528211946769436968799761724667716082655997119572158947882963880778970164432326393480858337150525471346874196183962785321409039116916910681846888186947
# bubblebabble编码: xevaf-cityf-fisof-ketaf-metaf-disef-nuvaf-cysuf-dosuf-getuf-cysuf-dasix
e = 81733668723981020451323
print(long_to_bytes(pow(c,inverse(e,(p-1)*(q-1)),p*q)))
# b'flag{I wish you success in your cryptography career}'

数据处理

离散对数+爆破

part1:

# part1:
n = 2 ^ 512
m = 5084057673176634704877325918195984684237263100965172410645544705367004138917087081637515846739933954602106965103289595670550636402101057955537123475521383
c = 2989443482952171039348896269189568991072039347099986172010150242445491605115276953489889364577445582220903996856271544149424805812495293211539024953331399

f= discrete_log((mod(c,n)), (mod(m,n)))
print(f)
assert pow(m,f,n) == c
# 3282248010524512146638712359816289396373430161050484501341123570760619381019795910712610762203934445754701

part2:

from Crypto.Util.number import *
from itertools import permutations
from tqdm import trange

# part2:
flag = '3282248010524512146638712359816289396373430161050484501341123570760619381019795910712610762203934445754701'
dict = [''.join(p) for p in permutations('0123689', int(7))]
dict_new = ['7'+k[:3]+'4'+k[3:]+'5' for k in dict]
lowercase = '0123456789' 
uppercase = [k for k in dict_new]

for i in trange(len(uppercase)):
    k = uppercase[i].strip()
    table = ''.maketrans(k,lowercase)
    f = flag.translate(table)
    m = long_to_bytes(int(f)) 
    if b'H&NCTF{' in m:
        print(m)
        break

# b'H&NCTF{cut_cut_rrioajtfijrwegeriogjiireigji}'

ez-factor

A*p+r在coppersmith中mod n的情况下会只剩一个r，得到r后GCD得到p，从而得到答案

from Crypto.Util.number import *

N= 155296910351777777627285876776027672037304214686081903889658107735147953235249881743173605221986234177656859035013052546413190754332500394269777193023877978003355429490308124928931570682439681040003000706677272854316717486111569389104048561440718904998206734429111757045421158512642953817797000794436498517023
hint= 128897771799394706729823046048701824275008016021807110909858536932196768365642942957519868584739269771824527061163774807292614556912712491005558619713483097387272219068456556103195796986984219731534200739471016634325466080225824620962675943991114643524066815621081841013085256358885072412548162291376467189508
c=32491252910483344435013657252642812908631157928805388324401451221153787566144288668394161348411375877874802225033713208225889209706188963141818204000519335320453645771183991984871397145401449116355563131852618397832704991151874545202796217273448326885185155844071725702118012339804747838515195046843936285308
"""
P.<r> = PolynomialRing(Zmod(N))
f = r - hint
res = f.small_roots(X=2^249, beta=0.49, epsilon=0.013)
print(f'r = {res[0]}')
"""
r = 310384729555967603261671853388867753979360895944109353196595111340924855459
p = GCD(N,hint-r)
q = N//p
assert N == p*q
e=0x10001
d = inverse(e,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,N)))
# b'H&NCTF{ac354aae-cb6b-4bd1-a9cd-090812b8f93e}'

ez-factor-pro

比上一个的r多了4位，以至于直接copper出不来，那就爆破四位吧，也不多，到15的时候可以跑出来，part2要先bytes.fromhex()把c转化为bytes再操作

part1:

from Crypto.Util.number import *
from tqdm import trange

N = 133196604547992363575584257705624404667968600447626367604523982016247386106677898877957513177151872429736948168642977575860754686097638795690422242542292618145151312000412007125887631130667228632902437183933840195380816196093162319293698836053406176957297330716990340998802156803899579713165154526610395279999
hint = 88154421894117450591552142051149160480833170266148800195422578353703847455418496231944089437130332162458102290491849331143073163240148813116171275432632366729218612063176137204570648617681911344674042091585091104687596255488609263266272373788618920171331355912434290259151350333219719321509782517693267379786

"""
P.<r> = PolynomialRing(Zmod(N))
for rh in trange(8,16):
    print(f'Checking rh = {rh}')
    f = rh*2^248 + r - hint
    res = f.small_roots(X=2^248, beta=0.49, epsilon=0.013)
    if res:
        print(f'rr = {rh*2^248 + res[0]}')
        break
"""
rr = 7166351305785506670352015492214713707534657162937963088592442157834795391917
p = GCD(hint -rr, N)
q = N//p
assert p*q == N
print(f'r = {rr}\np = {p}\nq = {q}')
# r = 7166351305785506670352015492214713707534657162937963088592442157834795391917
# p = 10028729313926419703025256508152026623108338149091078764973884312717908184535793132629646141453659427095349436587466628835078575518082248569520191060305909
# q = 13281503606147647246708380767428957306516210204292257132138079387068505557520151605985669600345608943780007813758130736816723511421069886664561045223935011

part2:

from gmssl.sm4 import CryptSM4, SM4_DECRYPT
from hashlib import sha256
from Crypto.Util.number import long_to_bytes
from Crypto.Util.Padding import *

r = 7166351305785506670352015492214713707534657162937963088592442157834795391917
p = 10028729313926419703025256508152026623108338149091078764973884312717908184535793132629646141453659427095349436587466628835078575518082248569520191060305909
q = 13281503606147647246708380767428957306516210204292257132138079387068505557520151605985669600345608943780007813758130736816723511421069886664561045223935011
c = '476922b694c764725338cca99d99c7471ec448d6bf60de797eb7cc6e71253221035eb577075f9658ac7f1a40747778ac261787baad21ee567256872fa9400c37'

leak=p*q*r
r_bytes = long_to_bytes(leak)
iv = r_bytes[:16] if len(r_bytes) >= 16 else r_bytes + b'\0'*(16-len(r_bytes))
key = sha256(str(p + q + r).encode()).digest()[:16] 
print("iv:", iv)
print("key:", key)

sm4 = CryptSM4()
sm4.set_key(key, SM4_DECRYPT)

decrypted_padded_flag = sm4.crypt_cbc(iv, bytes.fromhex(c))
decrypted_flag = unpad(decrypted_padded_flag, 16)
print("解密后的flag:", decrypted_flag)
# b'H&NCTF{ac354aae-cb6b-4bd1-a9cd-090812b8f93e}'

three vertical lines

参考niteCTF-2024/crypto/R Stands Alone/solution/solve.py at main · Cryptonite-MIT/niteCTF-2024 · GitHub

形如a∗pc+b∗qd=ra*p^c+b*q^d = r的均可如此进行，在mod r 的基础上得到p/q的值，然后进行规约

(q0)∗(1p/q0hint)=(qp)\begin{pmatrix}q & 0 \end{pmatrix}*\begin{pmatrix}1 & p/q \\ 0 & hint\end{pmatrix}=\begin{pmatrix}q & p \end{pmatrix}

(1p/q0hint)\begin{pmatrix}1 & p/q \\0 & hint\end{pmatrix}的det为hint，n∗det(L)1/n=2∗hint\sqrt n *det(L)^{1/n}=\sqrt {2 * hint}远大于 (qp)\begin{pmatrix}q & p\end{pmatrix}的长度，符合Hermite定理

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

hint = 72063558451087451183203801132459543552092564094711815404066471440396765744526854383117910805713050240067432476705168314622044706081669935956972031037827580519320550326077291392722314265758802332280697884744792689996718961355845963752788234205565249205191648439412084543163083032775054018324646541875754706761793307667356964825613429368358849530455220484128264690354330356861777561511117
c = 2864901454060087890623075705953001126417241189889895476561381971868301515757296100356013797346138819690091860054965586977737630238293536281745826901578223
e = 65537

# hint = 3*p**5 + 4*q**5
# 3*(p/q)**5 + 4 = 0 mod hint
PF = Zmod(hint)
PR = PolynomialRing(PF, 'x')
x = PR.gen()
f = 3*x**5 + 4
root = f.roots()[0][0]

M = matrix(ZZ,[
              [1,root],
              [0,hint]])

p,q = M.LLL()[0]
p,q = int(abs(p)),int(abs(q))
print(long_to_bytes(pow(c,inverse(e,(p-1)*(q-1)),p*q)))
# b'H&NCTF{You_learned_the_code_well}'