前言

打了香港，日本的比赛，还有蜀道山，感觉这几个题都很好，但是都不会（），写个记录一下，顺便总结

题目

seccon/reiwa_rot13

task

from Crypto.Util.number import *
import codecs
import string
import random
import hashlib
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from flag import flag

p = getStrongPrime(512)
q = getStrongPrime(512)
n = p*q
e = 137

key = ''.join(random.sample(string.ascii_lowercase, 10))
rot13_key = codecs.encode(key, 'rot13')

key = key.encode()
rot13_key = rot13_key.encode()

print("n =", n)
print("e =", e)
print("c1 =", pow(bytes_to_long(key), e, n))
print("c2 =", pow(bytes_to_long(rot13_key), e, n))

key = hashlib.sha256(key).digest()
cipher = AES.new(key, AES.MODE_ECB)
print("encyprted_flag = ", cipher.encrypt(flag))

思路：
当时比赛第一眼看过去，e很小，就在想是不是富兰克林，然后想利用rot13的性质去写，发现没用，然后就想通过c1和c2直接去构造富兰克林攻击，发现一直不对。
正确想法应该是bytes_to_long转换的时候形成的富兰克林，每一位可以看作$$256^i$$，然后相加，害蠢了。

exp

from Crypto.Util.number import *
import hashlib
import itertools
from tqdm import tqdm
from Crypto.Cipher import AES

n = 105270965659728963158005445847489568338624133794432049687688451306125971661031124713900002127418051522303660944175125387034394970179832138699578691141567745433869339567075081508781037210053642143165403433797282755555668756795483577896703080883972479419729546081868838801222887486792028810888791562604036658927
e = 137
c1 = 16725879353360743225730316963034204726319861040005120594887234855326369831320755783193769090051590949825166249781272646922803585636193915974651774390260491016720214140633640783231543045598365485211028668510203305809438787364463227009966174262553328694926283315238194084123468757122106412580182773221207234679
c2 = 54707765286024193032187360617061494734604811486186903189763791054142827180860557148652470696909890077875431762633703093692649645204708548602818564932535214931099060428833400560189627416590019522535730804324469881327808667775412214400027813470331712844449900828912439270590227229668374597433444897899112329233
encyprted_flag =  b"\xdb'\x0bL\x0f\xca\x16\xf5\x17>\xad\xfc\xe2\x10$(DVsDS~\xd3v\xe2\x86T\xb1{xL\xe53s\x90\x14\xfd\xe7\xdb\xddf\x1fx\xa3\xfc3\xcb\xb5~\x01\x9c\x91w\xa6\x03\x80&\xdb\x19xu\xedh\xe4"

def franklinReiter(n,e,r,c1,c2):
    R.<X> = Zmod(n)[]
    f1 = X^e - c1
    f2 = (X + r)^e - c2
    return Integer(n-(gcd(f1,f2)).coefficients()[0])

def gcd(a, b):
    if(b == 0):
        return a.monic()
    else:
        return gcd(b, a % b)

def gen():
    for perm in itertools.product([13,-13],repeat=10):
        l = sum([256**i*per for i,per in enumerate(perm)])
        yield l

for val in tqdm(gen()):
    m = franklinReiter(n,e,val,c1,c2)

    try:
        m = long_to_bytes(m).decode()
        print(m)

        break
    except:
        continue

key = hashlib.sha256(m.encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
print("encyprted_flag = ", cipher.decrypt(encyprted_flag))

seccon/dual_summon

task

from Crypto.Cipher import AES
import secrets
import os
import signal

signal.alarm(300)

flag = os.getenv('flag', "SECCON{sample}")

keys = [secrets.token_bytes(16) for _ in range(2)]
nonce = secrets.token_bytes(16)

def summon(number, plaintext):
    assert len(plaintext) == 16
    aes = AES.new(key=keys[number-1], mode=AES.MODE_GCM, nonce=nonce)
    ct, tag = aes.encrypt_and_digest(plaintext)
    return ct, tag

# When you can exec dual_summon, you will win
def dual_summon(plaintext):
    assert len(plaintext) == 16
    aes1 = AES.new(key=keys[0], mode=AES.MODE_GCM, nonce=nonce)
    aes2 = AES.new(key=keys[1], mode=AES.MODE_GCM, nonce=nonce)
    ct1, tag1 = aes1.encrypt_and_digest(plaintext)
    ct2, tag2 = aes2.encrypt_and_digest(plaintext)
    # When using dual_summon you have to match tags
    assert tag1 == tag2

print("Welcome to summoning circle. Can you dual summon?")
for _ in range(10):
    mode = int(input("[1] summon, [2] dual summon >"))
    if mode == 1:
        number = int(input("summon number (1 or 2) >"))
        name   = bytes.fromhex(input("name of sacrifice (hex) >"))
        ct, tag = summon(number, name)
        print(f"monster name = [---filtered---]")
        print(f"tag(hex) = {tag.hex()}")

    if mode == 2:
        name   = bytes.fromhex(input("name of sacrifice (hex) >"))
        dual_summon(name)
        print("Wow! you could exec dual_summon! you are master of summoner!")
        print(flag)

思路：
首先是在$$x^{128}+x^7+x^2+x+1$$定义在$$GF(2^{128})$$上的多项式，AES-GCM生成的标签是$$T=(P+H_1)H+H_0$$,H又是和notion绑定的，即notion一样生成的一样，所以我发两个一样的，生成的$$T^’,T$$区别就在于P，那么$$T+T^’=(P+P^’)H$$,那么H就出来了，草，为什么我当时没想到！！！
e x p

import pwn
from sage.all import *

pwn.context(encoding='ascii')

if pwn.args.LOCAL:
    io = pwn.process(['python', 'server.py'])
else:
    io = pwn.remote('dual-summon.seccon.games', '2222')

var('x')
F = GF(2**128, 'x', modulus=x**128 + x**7 + x**2 + x + 1)

def reverse(f):
    return F(list(f)[::-1])

def hex2f(h):
    return reverse(F.from_bytes(bytes.fromhex(h)))

def f2hex(f):
    return reverse(f).to_bytes()[-16:].hex()

def summon(idx, name):
    io.sendline('1')
    io.sendline(str(idx))
    io.sendline(f2hex(name))
    io.recvuntil('tag(hex) = ')
    return hex2f(io.recvline().decode())

trash1 = summon(1, F(0))
hh1 = trash1 + summon(1, F(1))
trash2 = summon(2, F(0))
hh2 = trash2 + summon(2, F(1))

ans = (trash1 + trash2) / (hh1 + hh2)

io.sendline('2')
io.sendline(f2hex(ans))
io.interactive()

强网杯青少年2024/easymath

task

from Crypto.Util.number import *
from gmpy2 import next_prime
from secrets import flag
l=2331
key=0
for k in range(2**(l-1),2**l):
    s=bin(k)[2:]
    if(k%2==1 and '1111' not in s and '0000' not in s):
        key+=1
p=next_prime(key)
q=getPrime(2048)
n=p*q
e=65537
m=bytes_to_long(flag)
c=pow(m,e,n)
print(f'n=',n)
print(f'c=',c)

'''
n=739243847275389709472067387827484120222494013590074140985399787562594529286597003777105115865446795908819036678700460141950875653695331369163361757157565377531721748744087900881582744902312177979298217791686598853486325684322963787498115587802274229739619528838187967527241366076438154697056550549800691528794136318856475884632511630403822825738299776018390079577728412776535367041632122565639036104271672497418509514781304810585503673226324238396489752427801699815592314894581630994590796084123504542794857800330419850716997654738103615725794629029775421170515512063019994761051891597378859698320651083189969905297963140966329378723373071590797203169830069428503544761584694131795243115146000564792100471259594488081571644541077283644666700962953460073953965250264401973080467760912924607461783312953419038084626809675807995463244073984979942740289741147504741715039830341488696960977502423702097709564068478477284161645957293908613935974036643029971491102157321238525596348807395784120585247899369773609341654908807803007460425271832839341595078200327677265778582728994058920387721181708105894076110057858324994417035004076234418186156340413169154344814582980205732305163274822509982340820301144418789572738830713925750250925049059
c=229043746793674889024653533006701296308351926745769842802636384094759379740300534278302123222014817911580006421847607123049816103885365851535481716236688330600113899345346872012870482410945158758991441294885546642304012025685141746649427132063040233448959783730507539964445711789203948478927754968414484217451929590364252823034436736148936707526491427134910817676292865910899256335978084133885301776638189969716684447886272526371596438362601308765248327164568010211340540749408337495125393161427493827866434814073414211359223724290251545324578501542643767456072748245099538268121741616645942503700796441269556575769250208333551820150640236503765376932896479238435739865805059908532831741588166990610406781319538995712584992928490839557809170189205452152534029118700150959965267557712569942462430810977059565077290952031751528357957124339169562549386600024298334407498257172578971559253328179357443841427429904013090062097483222125930742322794450873759719977981171221926439985786944884991660612824458339473263174969955453188212116242701330480313264281033623774772556593174438510101491596667187356827935296256470338269472769781778576964130967761897357847487612475534606977433259616857569013270917400687539344772924214733633652812119743
'''

思路：
直接看上去就是让你去分解，或者是直接求p的，其实这是一种算法，用矩阵状态方程，再结合矩阵快速幂，就可以很快的出来结果
e x p

states = [ (0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3) ]
state_idx = { state: idx for idx, state in enumerate(states) }
idx_state = { idx: state for idx, state in enumerate(states) }

size = len(states)
T = [ [0]*size for _ in range(size) ]

for idx_from, (last_bit, count) in enumerate(states):
    for new_bit in [0, 1]:
        if new_bit == last_bit:
            new_count = count + 1
        else:
            new_count = 1
        if new_count >= 4:
            continue  
        idx_to = state_idx[ (new_bit, new_count) ]
        T[idx_to][idx_from] += 1

def mat_mul(a, b):
    result = [ [0]*size for _ in range(size) ]
    for i in range(size):
        for j in range(size):
            for k in range(size):
                result[i][j] += a[i][k] * b[k][j]
    return result

def mat_pow(mat, power):
    result = [ [1 if i == j else 0 for j in range(size)] for i in range(size) ]  # 单位矩阵
    while power > 0:
        if power % 2 == 1:
            result = mat_mul(mat, result)
        mat = mat_mul(mat, mat)
        power //= 2
    return result

initial_state = [0]*size
initial_state[state_idx[(1, 1)]] = 1

l = 2331
T_pow = mat_pow(T, l - 1)

final_state = [0]*size
for i in range(size):
    for j in range(size):
        final_state[i] += T_pow[i][j] * initial_state[j]

key = 0
for idx, num in enumerate(final_state):
    last_bit, _ = idx_state[idx]
    if last_bit == 1:
        key += num

print("key =", key)

蜀道山/Something like coppersmith

task

from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import hashlib
from secret import flag

p = 6302810904265501037924401786295397288170843149817176985522767895582968290551414928308932200691953758726228011793524154509586354502691822110981490737900239
g = 37
x = getRandomRange(1, p)
key = hashlib.md5(str(x).encode()).digest()
aes = AES.new(key=key, mode=AES.MODE_ECB)
print(f"y = {pow(g, x, p)}")
print(f"xl = {x & (2**404 - 1)}")
print(f"enc = {aes.encrypt(pad(flag, 16))}")
"""
y = 1293150376161556844462084321627758417728307246932113125521569554783424543983527961886280946944216834324374477189528743754550041489359187752209421536046860
xl = 17986330879434951085449288256517884655391850545705434564933459034981508996937405053663301303792832616366656593647019909376   
enc = b'\x08[\x94\xc1\xc2\xc3\xb9"C^\xd6P\xf9\x0c\xbb\r\r\xaf&\x94\x8cm\x02s\x87\x8b\x1c\xb3\x92\x81H\xe7\xc6\x190a\xca\x91j\xc0@(\xc5Fw\x95\r\xee'
"""

思路：
发现$$p-1$$可以分解，利用小数直接分解，求出来106bits，x的低位直接crt，然后爆破几位就出来了
e x p

y = 1293150376161556844462084321627758417728307246932113125521569554783424543983527961886280946944216834324374477189528743754550041489359187752209421536046860
xl = 17986330879434951085449288256517884655391850545705434564933459034981508996937405053663301303792832616366656593647019909376   
enc = b'\x08[\x94\xc1\xc2\xc3\xb9"C^\xd6P\xf9\x0c\xbb\r\r\xaf&\x94\x8cm\x02s\x87\x8b\x1c\xb3\x92\x81H\xe7\xc6\x190a\xca\x91j\xc0@(\xc5Fw\x95\r\xee'
p = 6302810904265501037924401786295397288170843149817176985522767895582968290551414928308932200691953758726228011793524154509586354502691822110981490737900239
g = 37

from Crypto.Util.number import *
from Crypto.Cipher import AES
import hashlib

#2 · 385057 · 727646221919<12> · 193893885660581<15> · 193166780451443059<18> · 3881671740574461385603964379125531<34> · 77364837756797328321829387679372821139010103152781295726133301368685957<71>

r2=193166780451443059
r3=3881671740574461385603964379125531
r4=77364837756797328321829387679372821139010103152781295726133301368685957

r=r2*r3*r4

Fp = GF(p)
#xr = discrete_log(Fp(pow(y,r,p)), Fp(pow(g,r,p)), operation="*", ord=(p-1)//r)

xr=57328333290257638351589051968512

x = crt([xl, xr], [2^404, (p-1)//r])

for i in range(2^10):
    temp = x + i*lcm([2^404, (p-1)//r])
    if(temp > p-1):
        break
    key = hashlib.md5(str(temp).encode()).digest()
    aes = AES.new(key=key, mode=AES.MODE_ECB)
    print(aes.decrypt(enc))

蜀道山/签到!?

task

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

flag = b''
m = bytes_to_long(flag)
a = getPrime(1024);b = getPrime(1024);c = getPrime(1024);d = getPrime(128);n = getPrime(1024)

y = 0
for i in range(n+1):
    x = a*i+b
    y += (x//c)*i

if isPrime(y):
    pass
else:
    y = gmpy2.next_prime(y)

tmp = hashlib.md5(str(y).encode()).hexdigest()
cc = pow(d,int(tmp,16),n)

e = 52595
c3 = pow(m,e,y)
c4 = pow(a*m+b,e,y)

print('a =',a)
print('b =',b)
print('c =',c)
print('d =',d)
print('n =',n)
print('cc =',cc)
print('c3 =',c3)
print('c4 =',c4)

# a = 111406501658261575231314234156049408466629183228824951940397996549233343837444378602865612803520661162092930300450227752136992834681100817745708350750328806415942948297139334928206997684336812509277385194519252428443612078118898709910123899406877252165189871184174372173644257644751683554571917518602985248103
# b = 105754676330138681072874983469472331489357433467464632569519728162042635815478944541148477139634812590504509864018789141646023167940434519693396156652820504954321975234632684842726055170039476517204102162821838097200563406354332901840869790790015364563201564244853988381159598703692897790765599565893345380553
# c = 170600113386807592462858319531540617567133570960670217596634485327958954420566724690918464046407772634147753234450737353193173923873879958589824005123545638184186453602233634037809629812111243183450002707175703333920828461245731172668838771751457387207779427008047454548463398397079552688864699792002976130047
# d = 229823065384822950015724955215847476631
# n = 169428502732446427714165121824913735747920403586738853921495983139840483604966163669399379093896888954652663456556496947292418676356981468237136780175047349167561875551277606897449804926885192045760368051311243166090981061101913245493065268528634952461907634111084108803207099139506693313918834075542826388183
# cc = 105324189115602620621800798531371526317853537119154266873657796691360779628410005302892575043351618666760506544724245300953227618282253336044824499240524905915476071538182232622771476344880513465689824790881603214009332398038930113198889292160815386819010434380814610557831376377280232817587639852364108539892
# c3 = 791801877941025556812260671377895956461402542450910806211264471681160334454968210834058573374802678147030803278793623022600774676606263064237697305258809520983007689647782562591531551137322198839457388757360504835352506363286012791482381915207800512880078672338934869429374580298570299136345411005736381918329554791587303420005844148692211002120828912548145333101329366616120459060822278273689238720580513363138874807500470690610311215233669314430430554144017703130663205211791135140813550629558977548476426876112982216083736966681702987597722820852894624586687261277977164491919429492650781084296080288020330875247574855906390404509845311187888602482142661083771230000178356724801659025002251056321173755782500071361114235931347064100961296562902176010402092225439511324625249209554560052627349307173707304259200397468217911136832133364420684914378754649851955359890480612161233059263522713390654506714661592991514955637304
# c4 = 101923921400007092267790478161024103799892954880859052793422615329222813129835333442478632220182544724530301816393072530672763263645022408189547815923383906565611606888926097135400527299006862907781058931838804887994883095683814203452663467235776407572822082944022133476409878374663555627258035317631489173719410785629090255417861686081571376756906799938593870745471956936393066774907988124411318124604178920755698887086399177650502004883860844187365911953472980921213184639411672503691612418437276530896198002610276732906004741692286470538565288852344158830229580771834123582320782258698392853262935944858898937999647004599668060425461150846652642931397311468425476235056756761805933421643525566845928057238991458469113290576159465234243274971982913939709869951907061169493132309863852016682533998299893705859834844325876890511405664336001308600133946440998690503095156964687645597227368993047211862703399858777949126471093

思路：
第一部分就是求y，是一个循环很大，数很大的迭代，赛后知道了这是类欧几里得算法，参考https://www.luogu.com.cn/problem/solution/P5170
直接把代码转成python就行了，第二部分是HGCD很简单，但是52595 和y-1互素，直接inverse就能出来。
exp

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

def f(a,b,c,N):
    if(a == 0):
        return (N+1)*(b//c)
    elif(a >= c or b >= c):
        return (N*(N+1)//2)*(a//c) + (N+1)*(b//c) + f(a%c, b%c, c, N)
    else:
        M = (a*N+b)//c
        return N*M - f(c, c-b-1, a, M-1)

def g(a,b,c,N):
    if(a == 0):
        return (N+1)*(b//c)^2
    elif(a >= c or b >= c):
        return g(a%c, b%c, c, N) + 2*(a//c)*h(a%c, b%c, c, N) + 2*(b//c)*f(a%c, b%c, c, N) +\
            (N*(N+1)*(2*N+1)//6)*(a//c)^2 + N*(N+1)*(a//c)*(b//c) + (N+1)*(b//c)^2
    else:
        M = (a*N+b)//c
        return N*M*(M+1) - f(a, b, c, N) - 2*h(c, c-b-1, a, M-1) - 2*f(c, c-b-1, a, M-1)

def h(a,b,c,N):
    if(a == 0):
        return (N*(N+1)//2)*(b//c)
    elif(a >= c or b >= c):
        return h(a%c, b%c, c, N) + (N*(N+1)*(2*N+1)//6)*(a//c) + (N*(N+1)//2)*(b//c)
    else:
        M = (a*N+b)//c
        return (M*N*(N+1) - g(c, c-b-1, a, M-1) - f(c, c-b-1, a, M-1))//2

def calc(a, b, c, N):
    F, G, H = 0, 0, 0
    if(a == 0):
        F = (N+1)*(b//c)
        G = (N+1)*(b//c)^2
        H = (N*(N+1)//2)*(b//c)
    elif(a >= c or b >= c):
        ff, gg, hh = calc(a%c, b%c, c, N)
        F = (N*(N+1)//2)*(a//c) + (N+1)*(b//c) + ff
        G = gg + 2*(a//c)*hh + 2*(b//c)*ff +\
            (N*(N+1)*(2*N+1)//6)*(a//c)^2 + N*(N+1)*(a//c)*(b//c) + (N+1)*(b//c)^2
        H = hh + (N*(N+1)*(2*N+1)//6)*(a//c) + (N*(N+1)//2)*(b//c)
    else:
        M = (a*N+b)//c
        ff, gg, hh = calc(c, c-b-1, a, M-1)
        F = N*M - ff
        G = N*M*(M+1) - f(a, b, c, N) - 2*hh - 2*ff
        H = (M*N*(N+1) - gg - ff)//2
    return [F, G, H]

a = 111406501658261575231314234156049408466629183228824951940397996549233343837444378602865612803520661162092930300450227752136992834681100817745708350750328806415942948297139334928206997684336812509277385194519252428443612078118898709910123899406877252165189871184174372173644257644751683554571917518602985248103
b = 105754676330138681072874983469472331489357433467464632569519728162042635815478944541148477139634812590504509864018789141646023167940434519693396156652820504954321975234632684842726055170039476517204102162821838097200563406354332901840869790790015364563201564244853988381159598703692897790765599565893345380553
c = 170600113386807592462858319531540617567133570960670217596634485327958954420566724690918464046407772634147753234450737353193173923873879958589824005123545638184186453602233634037809629812111243183450002707175703333920828461245731172668838771751457387207779427008047454548463398397079552688864699792002976130047
d = 229823065384822950015724955215847476631
n = 169428502732446427714165121824913735747920403586738853921495983139840483604966163669399379093896888954652663456556496947292418676356981468237136780175047349167561875551277606897449804926885192045760368051311243166090981061101913245493065268528634952461907634111084108803207099139506693313918834075542826388183
cc = 105324189115602620621800798531371526317853537119154266873657796691360779628410005302892575043351618666760506544724245300953227618282253336044824499240524905915476071538182232622771476344880513465689824790881603214009332398038930113198889292160815386819010434380814610557831376377280232817587639852364108539892
c3 = 791801877941025556812260671377895956461402542450910806211264471681160334454968210834058573374802678147030803278793623022600774676606263064237697305258809520983007689647782562591531551137322198839457388757360504835352506363286012791482381915207800512880078672338934869429374580298570299136345411005736381918329554791587303420005844148692211002120828912548145333101329366616120459060822278273689238720580513363138874807500470690610311215233669314430430554144017703130663205211791135140813550629558977548476426876112982216083736966681702987597722820852894624586687261277977164491919429492650781084296080288020330875247574855906390404509845311187888602482142661083771230000178356724801659025002251056321173755782500071361114235931347064100961296562902176010402092225439511324625249209554560052627349307173707304259200397468217911136832133364420684914378754649851955359890480612161233059263522713390654506714661592991514955637304
c4 = 101923921400007092267790478161024103799892954880859052793422615329222813129835333442478632220182544724530301816393072530672763263645022408189547815923383906565611606888926097135400527299006862907781058931838804887994883095683814203452663467235776407572822082944022133476409878374663555627258035317631489173719410785629090255417861686081571376756906799938593870745471956936393066774907988124411318124604178920755698887086399177650502004883860844187365911953472980921213184639411672503691612418437276530896198002610276732906004741692286470538565288852344158830229580771834123582320782258698392853262935944858898937999647004599668060425461150846652642931397311468425476235056756761805933421643525566845928057238991458469113290576159465234243274971982913939709869951907061169493132309863852016682533998299893705859834844325876890511405664336001308600133946440998690503095156964687645597227368993047211862703399858777949126471093

y = calc(a,b,c,n)[2]
if isPrime(y):
    pass
else:
    y = gmpy2.next_prime(y)

tmp = hashlib.md5(str(y).encode()).hexdigest()
assert cc == pow(d,int(tmp,16),n)

print(long_to_bytes(pow(c3, inverse(52595,y-1), y)))