As we celebrated the Pi-Day yesterday, we hope you did enjoy a copious piece of your favorite pie. Today we would like to challenge you with an puzzle that you might enjoy!
Let's get startet with the challenge!
As so many of us, Alice and Bob also shared a pie yesterday. While enjoying this delicious pie, they wondered what shape their next pie should have. The obvious choice would be one of the cousin shapes of a circle. Therefore they looked at conic sections:
As it is getting late, Bob has to go. But they have not decided on which shape to use next. Fortunately, they also learned that they could use conics to exchange secret messages! Can you guess which shape are they going to eat next?
Here are the details:
Curve details: X2 - D * Y2 = 1 defined over the finite field Fp where:
p = 65058822587253916768083374249215630934917653029680133220444494211758557321921
D = 3141592
Generator
G:Point(x=58812305942798333300558189583390676334049806192380385399780663328904901530328
y=13015070926644505848080678854883269375023523658465198736280037005218460675921)
Public keys
Alice's public key: Point(x=1772868614035089622587328363862787386270978372297334698356741181946717430365
y=50363499595447778843503186760858925579193639138718578554151885777243837204919)
Bob's public key: Point(x=35395268437937032965093933470191862772891875655827096404006826016182618223902
y=2791282314116473888571201731177111096246008612047684817487077188227349832759)
Encrypted Message
Encrypted_message = {'nonce': '480a554d8a67f993cb24d5a31b0caa8f', 'ctxt': 'cdf215f9c48159c4cfdd019747e0087649897383e85016793700a3b5971e6e037b7a323a1da45d2230d66a03714315489d8b0b64', 'tag': 'c292dd3b71aa884034ba271505362ab9'}
from Crypto.Cipher import AES
from Crypto.Util.number import *
from Crypto.Random import random
from hashlib import sha256
from collections import namedtuple
Point = namedtuple("Point", "x y")
def point_addition(P, Q):
Rx = (P.x*Q.x + D*P.y*Q.y) % p
Ry = (P.x*Q.y + P.y*Q.x) % p
return Point(Rx, Ry)
def scalar_multiplication(P, n):
Q = Point(1, 0)
while n > 0:
if n % 2 == 1:
Q = point_addition(Q, P)
P = point_addition(P, P)
n = n//2
return Q
def gen_keypair():
private = random.randint(1, p-1)
public = scalar_multiplication(G, private)
return (public, private)
def gen_shared_secret(P, d):
return scalar_multiplication(P, d).x
def encrypt_flag(shared_secret: int, flag: bytes):
key = sha256(long_to_bytes(sab)).digest()
# Encrypt flag
print(key)
nonce = os.urandom(16)
cipher = AES.new(key, AES.MODE_SIV, nonce)
ctxt, tag = cipher.encrypt_and_digest(flag)
# Prepare data to send
data = {}
data['nonce'] = nonce.hex()
data['ctxt'] = ctxt.hex()
data['tag'] = tag.hex()
return data
def decrypt_flag(shared_secret, ctxt, nonce, tag):
key = sha256(long_to_bytes(sab)).digest()
ctxt = bytes.fromhex(ctxt)
nonce = bytes.fromhex(nonce)
tag = bytes.fromhex(tag)
cipher = AES.new(key, AES.MODE_SIV, nonce)
try:
ptxt = cipher.decrypt_and_verify(ctxt, tag)
return ptxt
except:
print("Wrong data!")
p = 65058822587253916768083374249215630934917653029680133220444494211758557321921
D = 3141592
G = Point(58812305942798333300558189583390676334049806192380385399780663328904901530328,
13015070926644505848080678854883269375023523658465198736280037005218460675921)
pa = Point(x=1772868614035089622587328363862787386270978372297334698356741181946717430365, y=50363499595447778843503186760858925579193639138718578554151885777243837204919)
pb = Point(x=35395268437937032965093933470191862772891875655827096404006826016182618223902, y=2791282314116473888571201731177111096246008612047684817487077188227349832759)
encrypted_message = {'nonce': '480a554d8a67f993cb24d5a31b0caa8f', 'ctxt': 'cdf215f9c48159c4cfdd019747e0087649897383e85016793700a3b5971e6e037b7a323a1da45d2230d66a03714315489d8b0b64', 'tag': 'c292dd3b71aa884034ba271505362ab9'}
Got it?
If you are stuck - Alfred Menezes will give you a little hint!
"flag format: sec-consult{??????????????}"
We wish you good luck!
You are interested if you found the right solution? Come back- we will publish the result on Thursday, March 18, 2021!
This challenge was inspired by Cryptohack, an incredible platform for learning modern cryptography!
Alice and Bob used a method similar to Elliptic Curve Diffie-Hellman, the only difference is that the curve is not an elliptic curve. However, a group structure is well defined, therefore a key exchange is possible!
To learn more about this: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.66.8688&rep=rep1&type=pdf
The paper above shows how to "transfer" the discrete log in our curve to the discrete log in a subgroup of Fp2. Additionally we have chosen p such that the subgroup has a smooth order.
The code is provided here:
sa = dlog_solve(pa, G)
print(f'sa {sa}')
sab = gen_shared_secret(pb, sa)
print(f'sab {sab}')
flag = decrypt_flag(sab, encrypted_message['ctxt'], encrypted_message['nonce'], encrypted_message['tag'])
print(f'flag bytes: {flag}')
print(f'flag string {flag.decode()}')
Output:
Please note: out of respect for an ongoing challenge on a similar topic we will not provide the code for the discrete logarithm computation, however the paper above will provide all the details needed.
We hope you enjoyed our little challenge!
In search for more challenges? Checkout Cryptohack!