N1CTF | flagbot

from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes, bytes_to_long
from Crypto.Util.Padding import pad, unpad
import base64
from secret import flag

RECEIVER_NUM = 7

def generate_safecurve():
    while True:
        p = random_prime(2 ^ 256-1, False, 2 ^ 255)
        a = randint(-p, p)
        b = randint(-p, p)

        if 4*a^3 + 27*b^2 == 0:
            continue

        E = EllipticCurve(GF(p), [a, b])

        fac = list(factor(E.order()))

        # Prevent rho method
        if fac[-1][0] < 1 << 80:
            continue

        # Prevent transfer
        for k in range(1, 20):
            if (p ^ k - 1) % fac[-1][0] == 0:
                break
        else:
            return E

class Sender:
    def __init__(self, curves, receivers):
        self.secret = randint(1 << 254, 1 << 255)
        self.curves = curves
        self.receivers = receivers
        self.shared_secrets = [None for _ in range(len(receivers))]

    def setup_connections(self):
        for idx, receiver in enumerate(self.receivers):
            curve = self.curves[idx]
            print(f"curves[{idx}] : {curve}")
            g = self.curves[idx].gens()[0]
            print(f"g[{idx}] = {g.xy()}")
            receiver.set_curve(curve, g)
            public = self.secret * g
            print(f"S_pub[{idx}] = {public.xy()}")
            yours = receiver.key_exchange(public)
            print(f"R_pub[{idx}] = {yours.xy()}")
            self.shared_secrets[idx] = yours * self.secret

    def send_secret(self):
        msg = b'Hi, here is your flag: ' + flag
        for idx, receiver in enumerate(self.receivers):
            px = self.shared_secrets[idx].xy()[0]
            _hash = sha256(long_to_bytes(px)).digest()
            key = _hash[:16]
            iv = _hash[16:]
            encrypted_msg = base64.b64encode(AES.new(key, AES.MODE_CBC, iv).encrypt(pad(msg, 16)))
            print(f"encrypted_msg[{idx}] = {encrypted_msg}")
            receiver.receive(encrypted_msg)


class Receiver:
    def __init__(self):
        self.secret = randint(1 << 254, 1 << 255)
        self.curve = None
        self.g = None
        self.shared_secret = None

    def set_curve(self, curve, g):
        self.curve = curve
        self.g = g

    def key_exchange(self, yours):
        self.shared_secret = yours * self.secret
        return self.g * self.secret

    def receive(self, encrypted_msg):
        px = self.shared_secret.xy()[0]
        _hash = sha256(long_to_bytes(px)).digest()
        key = _hash[:16]
        iv = _hash[16:]
        msg = AES.new(key, AES.MODE_CBC, iv).decrypt(base64.b64decode(encrypted_msg))
        msg = unpad(msg, 16)
        assert msg.startswith(b'Hi, here is your flag: ')


receivers = [Receiver() for _ in range(RECEIVER_NUM)]
curves = [generate_safecurve() for _ in range(RECEIVER_NUM)]

A = Sender(curves, receivers)
A.setup_connections()
A.send_secret()

EllipticCurve

楕円曲線DHをやっているように見える。7人に対してそれぞれ適当な曲線と生成元を選んでおいて、曲線のパラメータと生成元 、を送り、向こうからが送られてくるのでのx座標を鍵にする、というやつ

ここで問題になるのが、全ての相手に対して同じを使ってしまっているということ。楕円曲線の位数の小さい素因数でPohlig-Hellman Attackをやることによってが求まる。これでは足りないようだけど楕円曲線が7つもあるので解けるという寸法。

curves = [None for _ in range(7)]
g = [None for _ in range(7)]
S_pub = [None for _ in range(7)]

curves[0] = [25080904022674360699928001742955972930647134245095368243176041782631007842721, 51653146499008013562938728057440216556983928277479897024444219497340655463785,66116745352204681519469100961724220561156687225236967561841501424810928307807]
g[0] = (63081569813401008552324671243982371480394903382778267836374074361871201577834, 23474141625196059564605908362235632708979984522174825228263753550289099376123)
S_pub[0] = (24019555976552900590169231571461552054483009204136674938458250215680500736104, 28011367537644480596653140995440810446354950450235617877156869800605294049216)
curves[1] =[2043815101359890065237307309939296857003577532583569338661660469466065827348,  102067006665666390630291837887546295447695223287490132072379307910043009809365 , 113695419170059566479346310029048094168019545028712145271916973344605708411231]
g[1] = (20423141275809893159167255142239866844060625870997452377601981868107180347177, 19992442879371504373024138247445104476473382515298680276871238677864732873443)
S_pub[1] = (20441117040475832878884881554942470687198039971240520739479757559219246872653, 45246074815149735681764719655664095933149602519570537420221414480297443431660)
curves[2] = [65648683508174640005634659396734789146850512565992025130433731687468428014179, 26272780223380324248552131058359547612836533364530177350421100387341037019139 , 83896367993822828206543253354724494500260288857736562669184182628538083809367]
g[2] = (66637030276058391005466451194860659717163350367470416781614482222291041550445, 42130578561329742617661868751583766503456310634248769620710117199609280153951)
S_pub[2] = (925254032087886664320524398426659165460688490381753543166449423088972289752, 34161936287534442440574848409277776704051339550136374930448045799102091304385)
curves[3] = [45714287149662768031120362703352163808283687329364642685969786161037988402322, 13490438512144550503686574382307330330369767336370722471096599302102081052907 , 84408463109891431539543683776163072259768663955147054397339555539484223860849]
g[3] = (6570681797979574798980058367762289163101761416726999337302555519117884193133, 84131903756864767816718674235096921776761058318540805902656635647097220746176)
S_pub[3] = (13984502094770046374464253413876930620949304198826997187733768160077642199799, 76189432959768786280656878273218310462258843058909625672800249356146578715552)
curves[4] = [62223277804445341254787981117021600074420157388064163010607145435104547417397, 34707768442186125131806569005593351434199621336955141175747334384779700268005 , 89828857550588499041754475095787311033679358237685956741247265953298714723687]
g[4] = (34259562830800168427768937337523005601956109650950692560887503779629450207546, 59537565415508947262456971121016634323997129438307627449854610945426322682741)
S_pub[4] = (18674993449005014174961788230324741554553064950594321248138769231475404529578, 59930549653627690834693291622117932519282699095911346563631008466579071303426)
curves[5] = [6337991232311655881887193909687709244219846533018968166917954811344714846066, 78122417324315819522754419456195999300938035298934025516545906232290029817169 , 82544632586959503132766613901425519954811832603382905418700501867183631299857]
g[5] = (61666697446814016414589934733724006272024805116115169616762303794869830135004, 59765716632865814863135920288941972023872535929772755998052459642763576842072)
S_pub[5] = (14257092299382249876113216794843385700363061125668985733880785860525545219476, 18042157168209341016333130324332590121081457687400293942816847797124074413866)
curves[6] = [7403894190458165962231103292957170939506045762430202131193681466982830965756, 28082358492257355502989846048067008405688147223381838582915838704597222383734 , 73686745743965275836733554459385219570128908432394569325825918375480977933431]
g[6] = (46903230973099695924304295095696738305010395820826985689804239955539011384634, 69482437544400948021814998583755682054581126133090152647261459868866067367682)
S_pub[6] = (29313916694388937464203037295444584421266117814196799108742785455912142615392, 20695090655307032585729557746989704351847975924796772990704232701677433061651)

R_pub = (21964916650662314987863240651434170404291932859105698307245034338578258435153, 35342442175625429390144720170949410218699162882078535647858248442359306505200)
encrypted_msg = b'AphuswakJ9tm3U4RgxglCND0791F19eDYXjolhKnePtSNScGR+0KDtZ30SEY5QTZvYak0pW2nACbUDIKAUsW7g=='

def pohlig_hellman(P, Q, order, limit=10**10):
    factors = [f[0]**f[1] for f in order.factor(limit=limit) if f[0] <= limit]
    print("[-]",factors)
    bs = []
    mods = []
    M = 1
    for f in factors:
        k = order//f
        Pi = k * P
        Qi = k * Q
        b = discrete_log(Qi, Pi, operation="+")
        bs.append(b)
        mods.append(f)
        M *= f

    return CRT(bs, mods), M


xs = []
ms = []

for i in range(7):
    curves[i] = EllipticCurve(GF(curves[i][2]), curves[i][:2])
    g[i] = curves[i](g[i])
    S_pub[i] = curves[i](S_pub[i])

    x, mod = pohlig_hellman(g[i], S_pub[i], curves[i].order())
    print((i+1, x, mod))
    xs.append(x)
    ms.append(mod)

x = CRT(xs, ms)
print(x)
R = curves[0](R_pub)
K = x * R

from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.number import long_to_bytes, bytes_to_long
import base64

h = sha256(long_to_bytes(K.xy()[0])).digest()
key = h[:16]
iv = h[16:]
msg = AES.new(key, AES.MODE_CBC, iv).decrypt(base64.b64decode(encrypted_msg))
print(msg)