Rating:
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}'
```
