2024 数信杯 南区决赛

分区第11名,还行.

Crypto

2024

task

import random
from Crypto.Util.number import *


p = getPrime(1024)
q = getPrime(1024)
n = p*q
e = 0x10001

flag = open("flag1.txt", "r").readline().strip()
m = bytes_to_long(flag.encode())
c = pow(m, e, n)

entropy = 1
for _ in range(10):
    entropy *= random.randint(1, 2024)
hint = 2024 * (p+entropy) + 4202 * (q-entropy)

with open("flag1.enc", "w") as f:
    f.write(f"n: {n}\n")
    f.write(f"e: {e}\n")
    f.write(f"c: {c}\n")
    f.write(f"hint: {hint}\n")

flag1.enc

n: 13111253489758945122188556204390868224402311366143537090988165178965154068863113668446449296161794818953904845201813996968339175738080442391942643611047671328902660055336047685713304129172682406229372976535096463219284722397386622225405198953493021223679602593847091241061873677679220911618002298935622233065778867002182025189925827061716645121096144074791457524062807482711962935614075745533387992708507241041977555043122850321627021193880102281432259303601748832191559700505221501964668864114901027968209331940369201883937024497451608116803469734003989442454337530585803565044371000913648068275830986927382800781681
e: 65537
c: 3141593659746664351498073454326525921278004049392262860564812386804301385926352130830533412578874279777640307188723459000463428867163614026289296879770488846381739604850222680140990612960870712767337498300491425339595560063413241351308224105572360319196544100393979267058845081698258960852205426031225313109530203279690862845089207809897122319874567095069304622924480675948095945621254263622260935871100325009810290118800765403881701575348143626360445449744566574435383154061556825346058028982396103440611104578717448812402689794592513919949144741640447134546309350853929866403202944053915102252929311750864951026513
hint: 782993969528210557059565742408728402230323848332570220271460417891552472950551278394818109223963432351812998468748813440403357929589500208607237429933882666987268547344569219725506578724635426286158583723948311951028435419747266085620508643289259244020884007774614053960633170911201106122613673596744042970439226

与今年国赛初赛的OvO类似的一道题，直接拿hint联立n解出来的解与p和q的高位相同，随后Copper Smith即可。

exp

import gmpy2

n = 
e = 65537
c = 
hint = 

x, y = var("x y")
eq1 = 2024 * x + 4202 * y - hint
eq2 = x * y - n
solutions = solve([eq1, eq2], x, y)
solutions
"""
Copper Smith
"""
from Crypto.Util.number import *

p = 
q = 
c = 

n = p * q
e = 65537
phin = (p - 1) * (q - 1)

d = gmpy2.invert(e, phin)
plain = gmpy2.powmod(c, d, n)
print(long_to_bytes(plain))

0_curve

task

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import *
import os
from Curve import curve

FLAG = b"flag{???????????????????????????}"


def point_add(P, Q):
    x = (P[0] * Q[0] + D * P[1] * Q[1]) % p
    y = (P[0] * Q[1] + P[1] * Q[0]) % p
    return (x, y)


def multiplication(P, n):
    Q = (1, 0)
    while n > 0:
        if n % 2 == 1:
            Q = point_add(Q, P)
        P = point_add(P, P)
        n = n // 2
    return Q


def en_key(G, key):
    public_key = multiplication(G, key)
    return public_key


def AES_encrypt(FLAG):
    key = os.urandom(16)
    iv = os.urandom(16)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ciphertext = cipher.encrypt(pad(FLAG, 16))
    data = {"key": key, "iv": iv, "ciphertext": ciphertext}
    return data


data = AES_encrypt(FLAG)
Curve_content = curve()
p = Curve_content["p"]
D = Curve_content["D"]
G = (Curve_content["G.x"], Curve_content["G.y"])

key = bytes_to_long(data["key"])
enkey = en_key(G, key)

print("AES_data =", data)
print("curve_info =", Curve_content)
print("enkey =", enkey)

# AES_data = {'iv': b'\xed<uA\xc1\x9dD\xd3\xa0;\x06:\xcd\xaa%z', 'ciphertext': b'\xed\xa6\xe0&\xd7s\x886\xbd\x97d\x87%u\x98FH\x9c\xf8\x7f1qP\x99\xa9\xfa\x7fT\xa8\x01\xb1[\xea%\xe3\xb0Es\xb9\xa5\xb2<\xef7^;T8'}
# Curve_content = {'p': 235909871596517317710210566266868237119478957045712729679136620029221608388713487, 'D': 529, 'G.x': 64796846415747341206108535946553163276506223834166820859514203889024089732433179, 'G.y': 152458940800420288184044468735699849002307819746134208432822226465077924539270150}
# enkey = (42425275806865339226957893185555988883401253500639099807980506147020786708805718, 135653735714340428212752505142570676131020606806644503114962216834699043807823317)

对SEETF 2022的The True ECC熟悉的人立马就能看出这个形式是圆锥曲线上的点加和点乘。具体到本题使用的是双曲线。

双曲线的形式其实是Pell Equation，而我们知道Pell Equation的解满足：

\(x_{i}+\sqrt{D}y_{i}=(x_{1}+\sqrt{D}y_{1})^{i}\)

所以直接把enkey和G的坐标代入上式即可转化为\(\mathbb{F}_{p}\)上的DLP问题求解。

exp

#! /usr/bin/sage
p = 235909871596517317710210566266868237119478957045712729679136620029221608388713487
F = GF(p)
gx = 64796846415747341206108535946553163276506223834166820859514203889024089732433179
gy = 152458940800420288184044468735699849002307819746134208432822226465077924539270150
ax, ay = (
    42425275806865339226957893185555988883401253500639099807980506147020786708805718,
    135653735714340428212752505142570676131020606806644503114962216834699043807823317,
)
g = F(ax + 23 * ay).log(F(gx + 23 * gy))
# g = 102409594203061095085224006143259123584
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from Crypto.Util.number import long_to_bytes


def AES_decrypt(ciphertext, iv, key_long):
    key = long_to_bytes(key_long, 16)

    cipher = AES.new(key, AES.MODE_CBC, iv)

    plaintext = unpad(cipher.decrypt(ciphertext), 16)

    return plaintext


ciphertext = b"\xed\xa6\xe0&\xd7s\x886\xbd\x97d\x87%u\x98FH\x9c\xf8\x7f1qP\x99\xa9\xfa\x7fT\xa8\x01\xb1[\xea%\xe3\xb0Es\xb9\xa5\xb2<\xef7^;T8"
iv = b"\xed<uA\xc1\x9dD\xd3\xa0;\x06:\xcd\xaa%z"
key_long = 102409594203061095085224006143259123584

flag = AES_decrypt(ciphertext, iv, key_long)
print("Decrypted FLAG:", flag)

ps:最初一直想找个映到高斯整环的同态，结果因为\(x^{2}-529\)在\(GF(p^2)\)上可约所以一直没能搞定，最后回到pell equation的初等性质上反而很轻松地解决了XD

*32RSA

task

from Crypto.Util.number import *
from secret import flag

def gen():
    e = getPrime(12)
    p = getPrime(512)
    while (p-1) % e != 0:
        e = getPrime(12)
        p = getPrime(512)
    return p, e * getPrime(300)

p1, e1 = gen()
p2, e2 = gen()
p3, e3 = gen()
p4, e4 = gen()

params = [(p1, e1), (p2, e2),(p3, e3),(p4, e4)]
params=sorted(params, key = lambda x : x[0])

m = bytes_to_long(flag)
c = pow(m, e1, p1)
c = pow(c, e2, p2)
c = pow(c, e3, p3)
c = pow(c, e4, p4)

p = [p1, p2, p3, p4]
e = [e1, e2, e3, e4]

print(f"p = {p}")
print(f"e = {e}")
print(f"c = {c}")

'''
p = [9971877305101532548667657113915432686374600625802767915440064066247538969690929504779569308758806158316830036732847609558927989368198515992358962884845999, 9686779713749996013370168873387336643810360139391110278373359707982679675197866831353082822950439414021110597331749608836927764104519058819809287999191277, 11738824822038281341750095913199075446517552586485188261315252543625912278840584386174541563838459902823978442587021089252281373649445095529570370997140353, 8385622786171806844076175753935694055996440456538617120122854340325548660120153189193604171523482203780916677672818268556891995843000386665967836853148101]
e = [3949210634899972905354615323966329995013354120760848313001868527895893105358656676275468825581, 3352586350227882729695194848291019666469497650929882112900986499971706693129836865558906119017, 2538382896284047546927213869533310553533512722671755934207012576147843086855632406951937438613, 5811018619884267813495708620058955656757034290452722071543724890613376672936415477627562597173]
c = 6584399172697878406122485312269951595848044260489518691299790064128553815820157618343563425157360368851091584911872688623840890520680003501265955854989154
'''

没做出来,搓的脚本解不出flag但是我还看不出哪里有问题,先挖个坑

Misc

ez_sign

爆破得到压缩包密码为123456，解压得到3个文件.

part1图片内直接有flag的第一段，part2追踪TCP stream，在stream 6内找到第二段flag，part3逐字节与0xff异或后恢复压缩包，解压得到第三段flag。