We’re given the 3 python scripts. Here’s the one of the script called curvy_decryptor.py where the main flow of this challenge is located.

#!/usr/bin/env python3
import os
import sys
import string
from Crypto.Util import number
from Crypto.Util.number import bytes_to_long, long_to_bytes
from Crypto.Cipher import AES
from binascii import hexlify

from ec import *
from utils import *
from secret import flag1, flag2

#P-256 parameters
p = 0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff
a = -3
b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
curve = EllipticCurve(p,a,b, order = n)
G = ECPoint(curve, 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296, 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5)

d_a = bytes_to_long(os.urandom(32))
P_a = G * d_a

printable = [ord(char.encode()) for char in string.printable]

def encrypt(msg : bytes, pubkey : ECPoint):
    x = bytes_to_long(msg)
    y = modular_sqrt(x**3 + a*x + b, p)
    m = ECPoint(curve, x, y)
    d_b = number.getRandomRange(0,n)
    return (G * d_b, m + (pubkey * d_b))

def decrypt(B : ECPoint, c : ECPoint, d_a : int):
    if B.inf or c.inf: return b''
    return long_to_bytes((c - (B * d_a)).x)

def loop():
    print('I will decrypt anythin as long as it does not talk about flags.')
    balance = 1024
    while True:
        print('B:', end = '')
        sys.stdout.flush()
        B_input = sys.stdin.buffer.readline().strip().decode()
        print('c:', end = '')
        sys.stdout.flush()
        c_input = sys.stdin.buffer.readline().strip().decode()
        B = ECPoint(curve, *[int(_) for _ in B_input.split(',')])
        c = ECPoint(curve, *[int(_) for _ in c_input.split(',')])
        msg = decrypt(B, c, d_a)
        if b'ENO' in msg:
            balance = -1
        else:
            balance -= 1 + len([c for c in msg if c in printable])
        if balance >= 0:
            print(hexlify(msg))
            print('balance left: %d' % balance)
        else:
            print('You cannot afford any more decryptions.')
            return

if __name__ == '__main__':
    print('My public key is:')
    print(P_a)
    print('Good luck decrypting this cipher.')
    B,c = encrypt(flag1, P_a)
    print(B)
    print(c)
    key = long_to_bytes((d_a >> (8*16)) ^ (d_a & 0xffffffffffffffffffffffffffffffff))
    enc = AES.new(key, AES.MODE_ECB)
    cipher = enc.encrypt(flag2)
    print(hexlify(cipher).decode())
    try:
        loop()
    except Exception as err:
        print(repr(err))

This script implements the Elgamal encryption based on Elliptic Curve. It uses private key d_a to decrypt any encrypted message and public key P_a where P_a = G * d_a to encrypt any message.

TL;DR

• P-256 curve is used
• The encryption will encrypt message m into B and c where B = G * d_b and c = m + (P_a * d_b)
• The decryption will take two inputs B and c from user, then recover m by computing c - (B * d_a)
• We can prove this scheme is true since c - (B * d_a) = m + (P_a * d_b) - (G * d_b * d_a) = m + (G * d_a * d_b) - (G * d_b * d_a) = m
• We can’t decrypt the encrypted flag1 directly since the program will check whether there’s “ENO” string or not in the decrypted message

Since we have a full control over B and c, we can trick the decryption process by trying to decrypt the message m + G so that the string “ENO” doesn’t appear in the decryption result. As we have the decrypted result (which is the x-coordinate of point m + G), then we can calculate the original m locally by subtracting it with G.

My public key is:
Point(35328020660011696586564709258679785381786343512657089812378287082952917934716, 50416609790690128272655082973486394880002358124206268101298526556963890817882)
Good luck decrypting this cipher.
Point(104154835773696245508276030859477464297007825271904213255158699262376517719952, 53449655463778645126537272461287855887128030500959951790357090736353714142083)
Point(52168834033775429783455814818719333757981140192623818913235122708297420734798, 104323109031322302473535719172928547306740421293266175085426829976948991264626)
4d5cc7368d8ec8481b44309ee0e0bcc7
I will decrypt anythin as long as it does not talk about flags.
B:

Let’s take the P_a, B, and c values to our solver script.

from fastecdsa.curve import P256
from fastecdsa.point import Point

G = P256.G

P = Point(35328020660011696586564709258679785381786343512657089812378287082952917934716, 50416609790690128272655082973486394880002358124206268101298526556963890817882)
B = Point(104154835773696245508276030859477464297007825271904213255158699262376517719952, 53449655463778645126537272461287855887128030500959951790357090736353714142083)
c = Point(52168834033775429783455814818719333757981140192623818913235122708297420734798, 104323109031322302473535719172928547306740421293266175085426829976948991264626)

new_c = c + G

print(f"{int(B.x)}, {int(B.y)}")
print(f"{int(new_c.x)}, {int(new_c.y)}")

$ python3 solve.py 
104154835773696245508276030859477464297007825271904213255158699262376517719952, 53449655463778645126537272461287855887128030500959951790357090736353714142083
97394679619587788933333201089550117417489418909990818455148320248855936249801, 82185379848596875687249291483240443665288425087915452032458758698163910630490
My public key is:
Point(35328020660011696586564709258679785381786343512657089812378287082952917934716, 50416609790690128272655082973486394880002358124206268101298526556963890817882)
Good luck decrypting this cipher.
Point(104154835773696245508276030859477464297007825271904213255158699262376517719952, 53449655463778645126537272461287855887128030500959951790357090736353714142083)
Point(52168834033775429783455814818719333757981140192623818913235122708297420734798, 104323109031322302473535719172928547306740421293266175085426829976948991264626)
4d5cc7368d8ec8481b44309ee0e0bcc7
I will decrypt anythin as long as it does not talk about flags.
B:104154835773696245508276030859477464297007825271904213255158699262376517719952, 53449655463778645126537272461287855887128030500959951790357090736353714142083
c:97394679619587788933333201089550117417489418909990818455148320248855936249801, 82185379848596875687249291483240443665288425087915452032458758698163910630490
b'cc5ceac68ba0e89194b84049ccab1d1a5a6b0825801ec3f2a2b9e8fc871548aa'
balance left: 1016
B:

from fastecdsa.curve import P256
from fastecdsa.point import Point
from utils import *
from Crypto.Util.number import *

x = 0xcc5ceac68ba0e89194b84049ccab1d1a5a6b0825801ec3f2a2b9e8fc871548aa
y = modular_sqrt(x**3 + P256.a*x + P256.b, P256.p)

m = Point(x, y)
m -= P256.G

print(m.x)
print(long_to_bytes(m.x))

$ python3 solve.py 
478331744150452007169656202614580135667533560163676060093785159488648061
b'ENO{ElGam4l_1s_mult1pl1cativ3}'

Original writeup (https://hackmd.io/@vidner/nullcon-sksd#Curvy-Decryptor-cry).