EC Fun

Co-authors: @APJifengc @JOHNKRAM

Attachment:

from Crypto.Cipher import AES
import random

flag = '******'.encode()
p = 1361137685787644823054950239221481267310111

have = lambda s,t:((1132105824051503958365821105743937899761226*s[0]**3 + 229031861736140864689129133477543367548885*s[0]**2*t[0] + 229031861736140864689129133477543367548885*s[0]*t[0]**2 + 1132105824051503958365821105743937899761226*t[0]**3 + 820243406944125048991336110221143271981334*s[0]**2 + 649313030456686003640437242797882952355121*s[0]*s[1] + 527983998322961064385871655992141377230770*s[1]**2 + 1081788557687039548127228258000675990657554*s[0]*t[0] + 711824655330958819414512996423598314954990*s[1]*t[0] + 820243406944125048991336110221143271981334*t[0]**2 + 711824655330958819414512996423598314954990*s[0]*t[1] + 305169689141722694283206927237198512848571*s[1]*t[1] + 649313030456686003640437242797882952355121*t[0]*t[1] + 527983998322961064385871655992141377230770*t[1]**2)*pow(229031861736140864689129133477543367548885*s[0]**2 + 903073962315363093676691972266394532212341*s[0]*t[0] + 229031861736140864689129133477543367548885*t[0]**2,-1,p)%p, (54187766978142688518903451220347809940963*s[0]**4 + 229031861736140864689129133477543367548885*s[0]**3*s[1] + 1252762151831359446017143336780785647428185*s[0]**3*t[0] + 674042100579222228987562838788851164663456*s[0]*s[1]*t[0]**2 + 108375533956285377037806902440695619881926*s[0]*t[0]**3 + 458063723472281729378258266955086735097770*s[1]*t[0]**3 + 1306949918809502134536046788001133457369148*t[0]**4 + 903073962315363093676691972266394532212341*s[0]**3*t[1] + 687095585208422594067387400432630102646655*s[0]**2*t[0]*t[1] + 1132105824051503958365821105743937899761226*t[0]**3*t[1] + 409448300551393558178072250995397507413084*s[0]**3 + 1207230666903911661795540475036106991723031*s[0]**2*s[1] + 62511624874272815774075753625715362599869*s[0]*s[1]**2 + 833153687464683758669078583229339890079341*s[1]**3 + 132792784133464148520733486235288745070859*s[0]**2*t[0] + 307814037767466322518819528370748551174160*s[0]*s[1]*t[0] + 1298626060913372007280874485595765904710242*s[1]**2*t[0] + 1228344901654180674534216752986192522239252*s[0]*t[0]**2 + 1207230666903911661795540475036106991723031*s[1]*t[0]**2 + 951689385236251264876877988226083759897027*t[0]**3 + 153907018883733161259409764185374275587080*s[0]**2*t[1] + 1236114436039099191506798731970050542110373*s[0]*s[1]*t[1] + 222814309181238370102664728754942864382199*s[1]**2*t[1] + 1053323648020178500536130710850732716135951*s[0]*t[0]*t[1] + 125023249748545631548151507251430725199738*s[1]*t[0]*t[1] + 153907018883733161259409764185374275587080*t[0]**2*t[1] + 62511624874272815774075753625715362599869*s[0]*t[1]**2 + 1138323376606406452952285510466538402927912*s[1]*t[1]**2 + 1298626060913372007280874485595765904710242*t[0]*t[1]**2 + 527983998322961064385871655992141377230770*t[1]**3)*pow(229031861736140864689129133477543367548885*s[0]**3 + 674042100579222228987562838788851164663456*s[0]**2*t[0] + 687095585208422594067387400432630102646655*s[0]*t[0]**2 + 1132105824051503958365821105743937899761226*t[0]**3,-1,p)%p)
fun = lambda t:((1355411426698193074927107560516481409632646*t[0]**4 + 1178449528330025005130887555984327255695700*t[0]**3 + 431210186226622274082401960566604243166160*t[0]**2*t[1] + 59195913557099283872495176385768072148921*t[0]*t[1]**2 + 251369299603578168918462619253512221092756*t[0]**2 + 879678478093874414429176172962662062922270*t[0]*t[1] + 281103361207015191365820977148971655332738*t[1]**2 + 362519131628697943100337725424101898137457*t[0] + 443705393890279523315779887935020111939334*t[1] + 578364425578037679604436300506704082028031)*pow(956880610267536390357724782030411500415237*t[0]**2 + 1145532592674333686013749258938179145727031*t[0]*t[1] + 650970886115272769591227531417856597580595*t[1]**2 + 233572674711604604519014902334948133513444*t[0] + 535453460641822632058096218419954325337796*t[1] + 725112018286073523450664990921518386913035,-1,p)%p, (1229680448238589741915782165367654357920185*t[0]**6 + 508331960611786860744946345382725399597519*t[0]**5 + 1343958908519289578671422203106481694277716*t[0]**4*t[1] + 177167026616744824850256300247635539724057*t[0]**3*t[1]**2 + 647526478257364195975697407176118287861906*t[0]**4 + 874634578828271234182240863130269063092359*t[0]**3*t[1] + 753721599708341578448324615735431250261044*t[0]**2*t[1]**2 + 59195913557099283872495176385768072148921*t[0]*t[1]**3 + 135184449413711070637582564227488684273926*t[1]**4 + 1184268232038119513987721523209048245879902*t[0]**3 + 588376066139055328517853740807864391561055*t[0]**2*t[1] + 975956920560485006036771022835309336072696*t[0]*t[1]**2 + 1352108846430422970045668681682022723360513*t[1]**3 + 1280832417616997174969599325837067484280181*t[0]**2 + 954546681684014316952546155309712995684234*t[0]*t[1] + 865928094420333438629116336228132264435796*t[1]**2 + 1082085886860697193173121066542089802274658*t[0] + 755869998556204076975668261501936206771336*t[1] + 657902451019006293214253561308197638483112)*pow(956880610267536390357724782030411500415237*t[0]**3 + 1037730046117678117493148768796528084935491*t[0]**2*t[1] + 591774972558173485718732355032088525431674*t[0]*t[1]**2 + 1225953236373933752417367674993992583036185*t[1]**3 + 350359012067406906778522353502422200270166*t[0]**2 + 245222696137823073119338416038381708703277*t[0]*t[1] + 1197892972677768820041026587455773400480227*t[1]**2 + 814198369070575747297044733543073893428994*t[0] + 447093761510564524382892260162823859185717*t[1] + 558976911634572335364921619094958402137856,-1,p)%p)

def have_fun(a, b):
    res = g1
    while b:
        if b&1:
            res = have(res,a)
        a = fun(a)
        b >>= 1
    return res

g1 = (1151954709424958906091046463160132564937644,709388597947225692614956015386635942863012)
g2 = (981333628607549915704008747402562350211701,1251610635487471222383956310361676241534200)

key = random.randrange(2,1<<54)
y = have_fun(g2, key)

print('y =',y)
# y = (1233646914495991358880000369082822614720033, 169216170896679696320800078452784590711491)

cipher = AES.new(str(key).encode()[:16], AES.MODE_ECB)
enc = cipher.encrypt(flag)
print('enc =', enc)
# enc = b"t\xf1x\xc2'}q\xe7i.\x0cmj\x0fkNkVJ-\xd5\xbf\xf9H_\xd1\x04hO\xcd\xe1\x95P\xad\xea\xe1\xec\x1c\xben?RCr\x932\x90t"

The code seemed like computing y = g1 + g2 * key, so we are solving ECDLP problem. First, we need to recover the curve parameters:

res = [have_fun(g2, i) for i in range(100)] + [g1, g2]

# x^3 + Ax^2 + Bx + Cy^2 + Dy + Exy + F = 0
M = []
Y = []
for x, y in res:
    M.append([x**2, x, y**2, y, x * y, 1])
    Y.append(-(x**3))

M = Matrix(Zmod(p), M)
Y = vector(Y)
X = M.solve_right(Y)

It is not in Weierstrass form. Transform:

R = Zmod(p)["x, y"]
(
    x,
    y,
) = R._first_ngens(2)

A, B, C, D, E, F = X
f = x**3 + A * x**2 + B * x + C * y**2 + D * y + E * x * y + F

print(X, f, C)

# map to another curve:
# x^3 + Gx^2 + Hx + y^2 + Iy + Jxy + K = 0
# x = -X * C
# y = -Y * C


def mapping(point):
    return (-point[0] * pow(C, -1, p) % p, -point[1] * pow(C, -1, p) % p)


# progress:
# original:
# x^3 + Ax^2 + Bx + Cy^2 + Dy + Exy + F = 0
# - C^3X^3 + AC^2X^2 - BCX + C^3Y^2 - DCY + EC^2XY + F = 0
# - X^3 + A/C*X^2 - B/C^2*X + Y^2 - D/C^2*Y + E/C*XY + F/C^3 = 0
f1 = (
    -1 * x**3
    + A * pow(C, -1, p) * x**2
    - B * pow(C, -2, p) * x
    + y**2
    - D * pow(C, -2, p) * y
    + E * pow(C, -1, p) * x * y
    + F * pow(C, -3, p)
)

C1 = EllipticCurve(f1)

Now, we can solve the ECDLP problem in the curve:

G1 = C1(mapping(g1))
G2 = C1(mapping(g2))

Y1 = C1(mapping(y1))

key = discrete_log((Y1 - G1), G2, operation="+")

print(key)

enc = b"t\xf1x\xc2'}q\xe7i.\x0cmj\x0fkNkVJ-\xd5\xbf\xf9H_\xd1\x04hO\xcd\xe1\x95P\xad\xea\xe1\xec\x1c\xben?RCr\x932\x90t"
cipher = AES.new(str(key).encode()[:16], AES.MODE_ECB)
flag = cipher.decrypt(enc)
print(flag)

However, the discrete_log step takes ~2 hours to finish (thansk @Jifengc). @JOHNKRAM suggests that the order has small coefficients:

order = G2.order()
factors = G2.order().factor()
print(factors)
# 59 * 139 * 11032831 * 46795057 * 160737905349093178761667

Following Pohlig-Hellman, we can factor in a small subgroup without the largest prime factor, and it gives us the unknown key because it is small enough:

key = discrete_log((Y1 - G1) * factors[-1][0], G2 * factors[-1][0], operation="+")

Alternatively, full Pohlig-Hellman without the largest factor:

moduli = []
residues = []

for p, e in factors[:-1]:
    m = p**e
    x = discrete_log_lambda(
        (Y1 - G1) * (order // m), G2 * (order // m), bounds=(0, m), operation="+"
    )
    residues.append(x)
    moduli.append(m)

key = crt(residues, moduli)

Full attack script:

from Crypto.Cipher import AES
import random
from sage.all import *
import math
import tqdm

flag = "******".encode()
p = 1361137685787644823054950239221481267310111

have = lambda s, t: (
    (
        1132105824051503958365821105743937899761226 * s[0] ** 3
        + 229031861736140864689129133477543367548885 * s[0] ** 2 * t[0]
        + 229031861736140864689129133477543367548885 * s[0] * t[0] ** 2
        + 1132105824051503958365821105743937899761226 * t[0] ** 3
        + 820243406944125048991336110221143271981334 * s[0] ** 2
        + 649313030456686003640437242797882952355121 * s[0] * s[1]
        + 527983998322961064385871655992141377230770 * s[1] ** 2
        + 1081788557687039548127228258000675990657554 * s[0] * t[0]
        + 711824655330958819414512996423598314954990 * s[1] * t[0]
        + 820243406944125048991336110221143271981334 * t[0] ** 2
        + 711824655330958819414512996423598314954990 * s[0] * t[1]
        + 305169689141722694283206927237198512848571 * s[1] * t[1]
        + 649313030456686003640437242797882952355121 * t[0] * t[1]
        + 527983998322961064385871655992141377230770 * t[1] ** 2
    )
    * pow(
        229031861736140864689129133477543367548885 * s[0] ** 2
        + 903073962315363093676691972266394532212341 * s[0] * t[0]
        + 229031861736140864689129133477543367548885 * t[0] ** 2,
        -1,
        p,
    )
    % p,
    (
        54187766978142688518903451220347809940963 * s[0] ** 4
        + 229031861736140864689129133477543367548885 * s[0] ** 3 * s[1]
        + 1252762151831359446017143336780785647428185 * s[0] ** 3 * t[0]
        + 674042100579222228987562838788851164663456 * s[0] * s[1] * t[0] ** 2
        + 108375533956285377037806902440695619881926 * s[0] * t[0] ** 3
        + 458063723472281729378258266955086735097770 * s[1] * t[0] ** 3
        + 1306949918809502134536046788001133457369148 * t[0] ** 4
        + 903073962315363093676691972266394532212341 * s[0] ** 3 * t[1]
        + 687095585208422594067387400432630102646655 * s[0] ** 2 * t[0] * t[1]
        + 1132105824051503958365821105743937899761226 * t[0] ** 3 * t[1]
        + 409448300551393558178072250995397507413084 * s[0] ** 3
        + 1207230666903911661795540475036106991723031 * s[0] ** 2 * s[1]
        + 62511624874272815774075753625715362599869 * s[0] * s[1] ** 2
        + 833153687464683758669078583229339890079341 * s[1] ** 3
        + 132792784133464148520733486235288745070859 * s[0] ** 2 * t[0]
        + 307814037767466322518819528370748551174160 * s[0] * s[1] * t[0]
        + 1298626060913372007280874485595765904710242 * s[1] ** 2 * t[0]
        + 1228344901654180674534216752986192522239252 * s[0] * t[0] ** 2
        + 1207230666903911661795540475036106991723031 * s[1] * t[0] ** 2
        + 951689385236251264876877988226083759897027 * t[0] ** 3
        + 153907018883733161259409764185374275587080 * s[0] ** 2 * t[1]
        + 1236114436039099191506798731970050542110373 * s[0] * s[1] * t[1]
        + 222814309181238370102664728754942864382199 * s[1] ** 2 * t[1]
        + 1053323648020178500536130710850732716135951 * s[0] * t[0] * t[1]
        + 125023249748545631548151507251430725199738 * s[1] * t[0] * t[1]
        + 153907018883733161259409764185374275587080 * t[0] ** 2 * t[1]
        + 62511624874272815774075753625715362599869 * s[0] * t[1] ** 2
        + 1138323376606406452952285510466538402927912 * s[1] * t[1] ** 2
        + 1298626060913372007280874485595765904710242 * t[0] * t[1] ** 2
        + 527983998322961064385871655992141377230770 * t[1] ** 3
    )
    * pow(
        229031861736140864689129133477543367548885 * s[0] ** 3
        + 674042100579222228987562838788851164663456 * s[0] ** 2 * t[0]
        + 687095585208422594067387400432630102646655 * s[0] * t[0] ** 2
        + 1132105824051503958365821105743937899761226 * t[0] ** 3,
        -1,
        p,
    )
    % p,
)
fun = lambda t: (
    (
        1355411426698193074927107560516481409632646 * t[0] ** 4
        + 1178449528330025005130887555984327255695700 * t[0] ** 3
        + 431210186226622274082401960566604243166160 * t[0] ** 2 * t[1]
        + 59195913557099283872495176385768072148921 * t[0] * t[1] ** 2
        + 251369299603578168918462619253512221092756 * t[0] ** 2
        + 879678478093874414429176172962662062922270 * t[0] * t[1]
        + 281103361207015191365820977148971655332738 * t[1] ** 2
        + 362519131628697943100337725424101898137457 * t[0]
        + 443705393890279523315779887935020111939334 * t[1]
        + 578364425578037679604436300506704082028031
    )
    * pow(
        956880610267536390357724782030411500415237 * t[0] ** 2
        + 1145532592674333686013749258938179145727031 * t[0] * t[1]
        + 650970886115272769591227531417856597580595 * t[1] ** 2
        + 233572674711604604519014902334948133513444 * t[0]
        + 535453460641822632058096218419954325337796 * t[1]
        + 725112018286073523450664990921518386913035,
        -1,
        p,
    )
    % p,
    (
        1229680448238589741915782165367654357920185 * t[0] ** 6
        + 508331960611786860744946345382725399597519 * t[0] ** 5
        + 1343958908519289578671422203106481694277716 * t[0] ** 4 * t[1]
        + 177167026616744824850256300247635539724057 * t[0] ** 3 * t[1] ** 2
        + 647526478257364195975697407176118287861906 * t[0] ** 4
        + 874634578828271234182240863130269063092359 * t[0] ** 3 * t[1]
        + 753721599708341578448324615735431250261044 * t[0] ** 2 * t[1] ** 2
        + 59195913557099283872495176385768072148921 * t[0] * t[1] ** 3
        + 135184449413711070637582564227488684273926 * t[1] ** 4
        + 1184268232038119513987721523209048245879902 * t[0] ** 3
        + 588376066139055328517853740807864391561055 * t[0] ** 2 * t[1]
        + 975956920560485006036771022835309336072696 * t[0] * t[1] ** 2
        + 1352108846430422970045668681682022723360513 * t[1] ** 3
        + 1280832417616997174969599325837067484280181 * t[0] ** 2
        + 954546681684014316952546155309712995684234 * t[0] * t[1]
        + 865928094420333438629116336228132264435796 * t[1] ** 2
        + 1082085886860697193173121066542089802274658 * t[0]
        + 755869998556204076975668261501936206771336 * t[1]
        + 657902451019006293214253561308197638483112
    )
    * pow(
        956880610267536390357724782030411500415237 * t[0] ** 3
        + 1037730046117678117493148768796528084935491 * t[0] ** 2 * t[1]
        + 591774972558173485718732355032088525431674 * t[0] * t[1] ** 2
        + 1225953236373933752417367674993992583036185 * t[1] ** 3
        + 350359012067406906778522353502422200270166 * t[0] ** 2
        + 245222696137823073119338416038381708703277 * t[0] * t[1]
        + 1197892972677768820041026587455773400480227 * t[1] ** 2
        + 814198369070575747297044733543073893428994 * t[0]
        + 447093761510564524382892260162823859185717 * t[1]
        + 558976911634572335364921619094958402137856,
        -1,
        p,
    )
    % p,
)


# g1 * pow(a, b)
def have_fun(a, b):
    res = g1
    while b:
        if b & 1:
            res = have(res, a)  # multiply
        a = fun(a)  # double
        b >>= 1
    return res


g1 = (
    1151954709424958906091046463160132564937644,
    709388597947225692614956015386635942863012,
)
g2 = (
    981333628607549915704008747402562350211701,
    1251610635487471222383956310361676241534200,
)

y1 = (
    1233646914495991358880000369082822614720033,
    169216170896679696320800078452784590711491,
)


res = [have_fun(g2, i) for i in range(100)] + [g1, g2]

# x^3 + Ax^2 + Bx + Cy^2 + Dy + Exy + F = 0
M = []
Y = []
for x, y in res:
    M.append([x**2, x, y**2, y, x * y, 1])
    Y.append(-(x**3))

M = Matrix(Zmod(p), M)
Y = vector(Y)
X = M.solve_right(Y)

R = Zmod(p)["x, y"]
(
    x,
    y,
) = R._first_ngens(2)

A, B, C, D, E, F = X
f = x**3 + A * x**2 + B * x + C * y**2 + D * y + E * x * y + F

print(X, f, C)

# map to another curve:
# x^3 + Gx^2 + Hx + y^2 + Iy + Jxy + K = 0
# x = -X * C
# y = -Y * C


def mapping(point):
    return (-point[0] * pow(C, -1, p) % p, -point[1] * pow(C, -1, p) % p)


# progress:
# original:
# x^3 + Ax^2 + Bx + Cy^2 + Dy + Exy + F = 0
# - C^3X^3 + AC^2X^2 - BCX + C^3Y^2 - DCY + EC^2XY + F = 0
# - X^3 + A/C*X^2 - B/C^2*X + Y^2 - D/C^2*Y + E/C*XY + F/C^3 = 0
f1 = (
    -1 * x**3
    + A * pow(C, -1, p) * x**2
    - B * pow(C, -2, p) * x
    + y**2
    - D * pow(C, -2, p) * y
    + E * pow(C, -1, p) * x * y
    + F * pow(C, -3, p)
)

C1 = EllipticCurve(f1)
G1 = C1(mapping(g1))
G2 = C1(mapping(g2))

Y1 = C1(mapping(y1))

order = G2.order()
factors = G2.order().factor()
print(factors)

moduli = []
residues = []

for p, e in factors[:-1]:
    assert e == 1
    x = discrete_log_lambda(
        (Y1 - G1) * (order // p), G2 * (order // p), bounds=(0, p), operation="+"
    )
    residues.append(x)
    moduli.append(p)

key = crt(residues, moduli)

# key = discrete_log((Y1 - G1), G2, operation="+")
assert key == discrete_log(
    (Y1 - G1) * factors[-1][0], G2 * factors[-1][0], operation="+"
)

print(key)

enc = b"t\xf1x\xc2'}q\xe7i.\x0cmj\x0fkNkVJ-\xd5\xbf\xf9H_\xd1\x04hO\xcd\xe1\x95P\xad\xea\xe1\xec\x1c\xben?RCr\x932\x90t"
cipher = AES.new(str(key).encode()[:16], AES.MODE_ECB)
flag = cipher.decrypt(enc)
print(flag)