TJCTF | curvature

ecdh invalidcurveattack crt 位数を調整するテク

#ECDH #InvalidCurveAttack #CRT

楕円曲線の位数がある程度小さい数を含むように素因数分解できる場合に、楕円曲線のgenerator * (order / factor)をやると、位数がfactorな部分群のgeneratorが求まる（位数を調整するテク）。あとは #CRT で復元

#!/usr/bin/env python
import socketserver, threading

PORT = 12345
FLAG = int(b"y0u're_th3_3llipt1c_curv3_mas7tr".hex(), 16)

A = 0x7D5A0975FC2C3057EEF67530417AFFE7FB8055C126DC5C6CE94A4B44F330B5D9
B = 0x26DC5C6CE94A4B44F330B5D9BBD77CBF958416295CF7E1CE6BCCDC18FF8C07B6
P = 0xA9FB57DBA1EEA9BC3E660A909D838D726E3BF623D52620282013481D1F6E5377
# Curve is y^2 = x^3 + Ax + B, all modulo P

# From Wikibooks, because I'm lazy
def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
    gcd = b
    return gcd, x, y

def inv(a):
    gcd, x, y = egcd(a % P, P)
    if gcd != 1:
        return -1
    else:
        return x % P

def add(a, b):
    if a == 0:
        return b
    if b == 0:
        return a
    i = inv(b[0] - a[0])
    if i == -1:
        return 0
    l = ((b[1] - a[1]) * i) % P
    x = (l*l - a[0] - b[0]) % P
    y = (l*(a[0] - x) - a[1]) % P
    return (x,y)

def double(a):
    if a == 0:
        return a
    i = inv(2*a[1])
    if i == -1:
        return 0
    l = ((3*a[0]*a[0] + A) * i) % P
    x = (l*l - 2*a[0]) % P
    y = (l*(a[0] - x) - a[1]) % P
    return (x,y)

def multiply(point, exponent):
    # No timing attack for you :P
    r0 = 0
    r1 = point
    for i in bin(exponent)[2:]:
        if i == '0':
            r1 = add(r0, r1)
            r0 = double(r0)
        else:
            r0 = add(r0, r1)
            r1 = double(r1)
    return r0

class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
    allow_reuse_address = True

class Handler(socketserver.BaseRequestHandler):
    def handle(self):
        self.request.send(b"Send me points to exponentiate!\n")
        self.request.send(b"Format: \"x y\"\n")

        while True:
            point = self.request.recv(4096)
            x, y = [int(i) for i in point.strip().split()]
            mpoint = multiply((x, y), FLAG)
            self.request.send(b"Your point:\n")
            if mpoint == 0:
                self.request.send(b"[point at infinity]\n")
            else:
                self.request.send("({}, {})\n".format(mpoint[0], mpoint[1]).encode())

server = ThreadedServer(('0.0.0.0', PORT), Handler)
server_thread = threading.Thread(target=server.serve_forever)
server_thread.daemon = True
server_thread.start()
server_thread.join()

from sage.all import *
from timeout_decorator import timeout


A = 0x7D5A0975FC2C3057EEF67530417AFFE7FB8055C126DC5C6CE94A4B44F330B5D9
B = 0x26DC5C6CE94A4B44F330B5D9BBD77CBF958416295CF7E1CE6BCCDC18FF8C07B6
P = 0xA9FB57DBA1EEA9BC3E660A909D838D726E3BF623D52620282013481D1F6E5377
F = GF(P)
size = EllipticCurve(F, [A, B]).order()


@timeout(10, timeout_exception=Exception, use_signals=False)
def factorize(n):
    return prime_factors(n)

cur = 1
b = 2
while cur < size:
    EC = EllipticCurve(F, [A, b])
    order = EC.order()

    try:
        factors = factorize(order)
    except Exception:
        b += 1
        continue

    suborder = 1
    for f in factors:
        if f < 10**10:
            suborder = f
        else:
            break
    g = EC.gen(0) * int(order // suborder)
    print({
        "generator": g.xy(),
        "order": suborder,
        "b": b,
    }, ",")

    cur *= suborder
    b += 1

from sage.all import *
from timeout_decorator import timeout
from ptrlib import *

generators = [
    {'generator': (75018829908334641135287907832364588376392648394852697956512464620901439399091, 59310606686882497582859801487472084112791104513525809772271515095232323519002), 'order': 17, 'b': 2} ,
    {'generator': (14108366122805723625020075750179082265774395778849335024217582787861312312270, 48131724537792101564129626030579998631347236213771248503484807671517428824779), 'order': 11871421, 'b': 3} ,
    {'generator': (10219791296939476446978405667751432187697243109108209712110403172731476918598, 29956495008696010243175913739747719779132987433052330275148912122314390288669), 'order': 137, 'b': 5} ,
    {'generator': (42777940522922357350677116116779112965460458338266309438879684299889046092060, 55153724152154375167247217363093302126821206645660100074296996339252760370913), 'order': 32633, 'b': 7} ,
    {'generator': (10831563407297415859788486867917312379445005544125515905759465100401482164790, 83673279217201573271136390602924299332268405981527089175622432592003182193), 'order': 2192629, 'b': 9} ,
    {'generator': (21866291018291769753200219006065902052302271116278780675505468066315056034667, 26320854338400571929354338120932758767766121454452318420674426177401484895077), 'order': 1146083, 'b': 11} ,
    {'generator': (70477946629836528396820075171089472321695231503572908556028599471720495852914, 45359043459356443396911931469603778921737175440775125150426057614649863769381), 'order': 557693197, 'b': 12} ,
    {'generator': (3067625162943157588017556490906306538160163692852525289213976752118141691559, 70135860004395620803901190886933054437366829947624865529920703668208548865169), 'order': 4787, 'b': 13} ,
    {'generator': (20453887951492396382116635373156816246787390607186046864442208295254950706353, 41374043013134953199326755315280127177100264339162100449295591769938446808604), 'order': 120528059, 'b': 14} ,
    {'generator': (63860357017578264591074151267679315831331582854780010735294147152111534385449, 7787790211631466170916931897483087919405908652838124300647908802622489289322), 'order': 167, 'b': 15} ,
    {'generator': (28266681978198457092812065766219275154917100817596733107392104751238123037180, 25375345042438509641710766829984998144411914831489524239691171315736258149744), 'order': 433981, 'b': 17} ,
    {'generator': (30194731389043602783690419048124763865168292379437069881181109836251172351228, 40665116364724631324900157788568397943144157820689726966949666425146455719977), 'order': 370871, 'b': 18} ,
    {'generator': (24936471025919082430845657538468506580791307884831801991879227749137995844519, 63816116169864815848466423976585822530331789272863018928197180972927927939612), 'order': 259177, 'b': 21} ,
    {'generator': (41876169769492810135683621405650315114043483742421946397396849624969605627524, 62374885101651406800250293984653592947701957841184358843280066067652148661439), 'order': 9804344863, 'b': 22} ,
    {'generator': (45845934232875157717087534318790345406363949403587257916077210108373946981911, 10876312240831805735749936927491976773415927845336159631890752995764740480225), 'order': 11, 'b': 23} ,
]

A = 0x7D5A0975FC2C3057EEF67530417AFFE7FB8055C126DC5C6CE94A4B44F330B5D9
B = 0x26DC5C6CE94A4B44F330B5D9BBD77CBF958416295CF7E1CE6BCCDC18FF8C07B6
P = 0xA9FB57DBA1EEA9BC3E660A909D838D726E3BF623D52620282013481D1F6E5377
F = GF(P)

sock = Socket("localhost", 12345)
sock.recvuntil('"x y"\n')

pairs = []

for i, g in enumerate(generators):
    print("[+] {}/{}".format(i+1, len(generators)))
    E = EllipticCurve(F, [A, g['b']])
    P = E(g['generator'])

    sock.sendline("{} {}".format(*g['generator']))
    sock.recvuntil("point:\n")
    x,y = [int(xy) for xy in sock.recvline()[1:-1].split(b", ")]

    Q = E((x,y))
    z = P.discrete_log(Q)

    pairs.append((z,g['order']))

print(bytes.fromhex(hex(crt(pairs)[0])[2:]))