FLAG Flag and full writeup for Lostkey
by FukElitism - May 18, 2021 at 07:13 AM
#1
Flag: HTB{uns4f3_3ll1pt1c_curv3s_l3d_t0_th3_c0ll4ps3_0f_0u7l4nd1s}

As you can see, from the flag we can already know its about elliptic curves.
Note: u can recover the math formula by using TeX discord bot. ($ to another $ is a math syntax)

Source code formula:
Not the normal $y^2 = x^3 + ax + b\ mod\ p$ equation but another elliptic curve with the following lambda calculation for point doubling. i, j, k, m and n are all arbitrary numbers.

By comparing the equation of lambda form the Weirstrass form and the source code formula used, we get the following:
$a_1 = 0$
$2a_2 = i \Leftrightarrow a_2 = i/2$
$a_3 = k$
$a_4 = j$
$a_6 = ?$

We only need one more parameter. Since its just a constant in the equation and we know all the other terms, we can just solve the following for $a_6$:
a_6 = y^2+a_1xy+a_3y-x^3-a_2x^2-a_4x

And that gives us the following curve parameters:
a1 = 0
a2 = 417826948860567519876089769167830531934/2 = 208913474430283759938044884583915265967
a3 = 3045783791
a4 = 177776968102066079765540960971192211603
x = 14374457579818477622328740718059855487576640954098578940171165283141210916477
y = 97329024367170116249091206808639646539802948165666798870051500045258465236698
p = 101177610013690114367644862496650410682060315507552683976670417670408764432851
a6 = (y**2 + a3*y - x**3 - a2*x**2-a4*x) % p = 308081941914167831441899320643373035841


Get the private key:
Goal here is to calculate n by way of the CRT. First we need to calculate the order of the curve . In this case we will be using sage.

E = EllipticCurve(GF(p), [a1, a2, a3, a4, a6])
P = E(x,y)
Q = E.lift_x(32293793010624418281951109498609822259728115103695057808533313831446479788050)
O = E.order()
O
101177610013690114367644862496650410682371882435919767898009148385876141737891


Get the factors of the order of the curve do get the different $p_i^e$:
fact = factor(O)
fact = list(fact)
factors = []
for f in fact:
    factors.append(f[0]**f[1])
factors
[9,
59,
14771,
27733,
620059697,
2915987653003935133321,
257255080924232005234239344602998871]


In all these factors, the last 2 have too big of an order so we remove them from our set of valid factors and start calculating the ECDLP with the other factors.

factors = factors[:-2]
dl = []
for f in factors:
    Pi = P * (int(O)//f)
    Qi = Q * (int(O)//f)
   
    d_log = discrete_log(Qi, Pi, operation="+")
    print("factor:  ", f, " ECDLP sol: ", d_log)
    dl.append(d_log)
print(dl)

factor:  9  ECDLP sol:  4
factor:  59  ECDLP sol:  27
factor:  14771  ECDLP sol:  12977
factor:  27733  ECDLP sol:  2568
factor:  620059697  ECDLP sol:  261975359
[4, 27, 12977, 2568, 261975359]


Compute the CRT:
l = crt(dl, factors)
print(l)
def list_product(l, n=1):
    for x in l:
        n = n*x
    return n
mod = list_product(factors)
print(mod)

82438979720724695506
134876030111980880301


Now we know that $l\equiv n[134876030111980880301]$. Thus we know that $n = 134876030111980880301*i+l$. So now since we know $n \leq 38685626227668133590597631$ we can just test all possible $i$ and get the value of $n$:
for i in range(38685626227668133590597631/mod):
    if (P*(l+mod*i))[0] == Q[0]:
        print(i)
        break

i = 6283

n = (l+mod*i)%p
n = 847508536173296595626689


Getting the flag:
from Crypto.Util.number import *
from hashlib import sha1
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

iv = ...
key = ...

flag = bytearray.fromhex('df572f57ac514eeee9075bc0ff4d946a80cb16a6e8cd3e1bb686fabe543698dd8f62184060aecff758b29d92ed0e5a315579b47f6963260d5d52b7ba00ac47fd')

def encrypt(key):
    key = sha1(str(key).encode('ascii')).digest()[0:16]
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ct = cipher.decrypt(pad(flag,16))
    return(ct,iv.hex())


Donate if you like Hidden Content
You must register or login to view this content.

Possibly Related Threads…
Thread Author Replies Views Last Post
FLAG HTB RAuth Challenge - writeup, password and flag JaneHopkirk 0 260 November 17, 2021 at 10:22 PM
Last Post: JaneHopkirk
TUTORIAL Line - HTB Hardware Challenge - simplified writeup and flag vorsprung1 0 497 October 31, 2021 at 05:36 PM
Last Post: vorsprung1
BUYING Endgame Ascension complete writeup AND / OR Odyssey complete writeup peteristderlustig 3 970 October 03, 2021 at 05:21 PM
Last Post: Decosta

 Users browsing this thread: 1 Guest(s)