First of all, this is a challenge from HTB: LostKey under Crypto category and weighed as “Medium”. But man, this is a total brain rot to me.
Second, since I don’t know what the f am I doing, I just ended up reading walkthrough, even just reading, I can’t still comprehend what’s happening.
Lastly, the solution below is a complete copypasta from here. FULL CREDITS TO THEM.
The challenge
The challenge contains 2 files
#!/usr/bin/env python3
from Crypto.Util.number import *
from hashlib import sha1
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from secret import flag, n
class coord:
def __init__(self, x, y):
self.x = x
self.y = y
def __str__(self):
return f"coord({self.x}, {self.y})"
class EC:
def __init__(self, p):
self.p = p
self.zero = coord(0,0)
def add(self, P,Q):
if P == self.zero:
return Q
if Q == self.zero:
return P
if P.x == Q.x and P.y == -Q.y:
return self.zero
if P != Q:
Lambda = (Q.y - P.y) * inverse(Q.x - P.x, self.p)
else:
Lambda = (3*(P.x*Q.x) + 417826948860567519876089769167830531934*P.x + 177776968102066079765540960971192211603) * inverse(P.y+Q.y+3045783791, self.p)
Lambda %= self.p
R = coord(0,0)
R.x = (Lambda**2-P.x-Q.x-208913474430283759938044884583915265967) % self.p
R.y = (Lambda*(P.x-R.x) - P.y - 3045783791) % self.p
return R
def mul(self, P, n):
Q = P
R = self.zero
while n > 0:
if n % 2 == 1:
R = self.add(R,Q)
n >>= 1
Q = self.add(Q,Q)
return R
def encrypt(key):
iv = __import__('os').urandom(16)
key = sha1(str(key).encode('ascii')).digest()[0:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
ct = cipher.encrypt(pad(flag,16))
return(ct.hex(),iv.hex())
assert(n < 38685626227668133590597631)
e = EC(101177610013690114367644862496650410682060315507552683976670417670408764432851)
G = coord(14374457579818477622328740718059855487576640954098578940171165283141210916477, 97329024367170116249091206808639646539802948165666798870051500045258465236698)
print ("G =",G)
print ("Gn =", e.mul(G,n).x)
enc = encrypt(n)
print ("Ciphertext: {}\nIV: {}".format(enc[0],enc[1]))
encrypt.py The class in EC defines an elliptic curve. The encryption process is to use a point on the curve G to n * G calculate Gn and use it as the AES key to encrypt the plaintext, so the value n required to decrypt the ciphertext is obtained .n
output.txt The text file gives the values of G, Gn (x coordinates), Ciphertext and IV
G = coord(14374457579818477622328740718059855487576640954098578940171165283141210916477, 97329024367170116249091206808639646539802948165666798870051500045258465236698)
Gn = 32293793010624418281951109498609822259728115103695057808533313831446479788050
Ciphertext: df572f57ac514eeee9075bc0ff4d946a80cb16a6e8cd3e1bb686fabe543698dd8f62184060aecff758b29d92ed0e5a315579b47f6963260d5d52b7ba00ac47fd
IV: baf9137b5bb8fa896ca84ce1a98b34e5The Solution
Firstly, according to the general form of the elliptic curve and the calculation formula of point addition, the parameters of the curve are obtained.
The SageMath code is as follows
p = 101177610013690114367644862496650410682060315507552683976670417670408764432851
a1 = 0
a2 = 417826948860567519876089769167830531934 // 2
a3 = 3045783791
a4 = 177776968102066079765540960971192211603
Gx = 14374457579818477622328740718059855487576640954098578940171165283141210916477
Gy = 97329024367170116249091206808639646539802948165666798870051500045258465236698
a6 = Gy^2 + a1 * Gx * Gy + a3 * Gy - (Gx^3 + a2 * Gx^2 + a4 * Gx)
a6 = a6 % p
EC = EllipticCurve(Zmod(p), [a1, a2, a3, a4, a6])
G = EC(Gx, Gy)
print("G =", G)We can then Gn get the y coordinate given the x coordinate Gn.
Gnx = 32293793010624418281951109498609822259728115103695057808533313831446479788050
Gn = EC.lift_x(Gnx)
print("Gn =", Gn.xy())We can also see that the order of the curve is not a prime number, so we can use the Pohlig–Hellman algorithm to calculate Gn the G discrete logarithm of the sum, that is, n
ecOrder = EC.order()
print("EC order =", ecOrder)
F = factor(ecOrder)
print("F =", F)The prime factorization of the curve order gives 7 prime factors. Only the first 5 values are small enough to directly calculate the discrete logarithm. Then you need to use n the upper limit given in the question to enumerate the possible values one by one to find it n.
#we only need the first 5 factor
primes = [9, 59, 14771, 27733, 620059697]
dlogs = []
product = 1
for fac in primes:
t = ecOrder // fac
dlog = discrete_log(t*Gn, t*G, operation="+")
dlogs.append(dlog)
print("factor: ", fac, ", Discrete Log: ", dlog)
product = product * fac
L = crt(dlogs, primes)
print("L =", L)
print("check L =", L * G == Gn)
print("product =", product)
n = L
while (n <= 38685626227668133590597631):
if (n * G == Gn):
print("Found n =", n)
break
else:
n = n + product
print("n =", n)After obtaining it n, apply the AES decryption method to get the plain text of the Flag.
from Crypto.Cipher import AES
from hashlib import sha1
iv = bytes.fromhex("baf9137b5bb8fa896ca84ce1a98b34e5")
cipherText = bytes.fromhex("df572f57ac514eeee9075bc0ff4d946a80cb16a6e8cd3e1bb686fabe543698dd8f62184060aecff758b29d92ed0e5a315579b47f6963260d5d52b7ba00ac47fd")
key = sha1(str('PUT_n_HERE').encode('ascii')).digest()[0:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
plainText = cipher.decrypt(cipherText)
print ("plainText=", plainText)
