# Arranged Write-up

> From: Cyber Apocalypse 2024, Hacker Royale
> Tags: Crypto
> Problem statement:
> <Too lengthy and not very helpful, so I am not posting it here. I did not even read it when solving the challenge.>
> Files attached: `main.sage`, `output.txt`
>
> Solved by: Jackylkk2003

## Files attached:
`main.sage`:

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes
from hashlib import sha256

from secret import FLAG, p, b, priv_a, priv_b

F = GF(p)
E = EllipticCurve(F, [726, b])
G = E(926644437000604217447316655857202297402572559368538978912888106419470011487878351667380679323664062362524967242819810112524880301882054682462685841995367, 4856802955780604241403155772782614224057462426619061437325274365157616489963087648882578621484232159439344263863246191729458550632500259702851115715803253)

A = G * priv_a
B = G * priv_b

print(A)
print(B)

C = priv_a * B

assert C == priv_b * A

# now use it as shared secret
secret = C[0]

hash = sha256()
hash.update(long_to_bytes(secret))

key = hash.digest()[16:32]
iv = b'u\x8fo\x9aK\xc5\x17\xa7>[\x18\xa3\xc5\x11\x9en'
cipher = AES.new(key, AES.MODE_CBC, iv)

encrypted = cipher.encrypt(pad(FLAG, 16))
print(encrypted)

`output.txt`

(6174416269259286934151093673164493189253884617479643341333149124572806980379124586263533252636111274525178176274923169261099721987218035121599399265706997 : 2456156841357590320251214761807569562271603953403894230401577941817844043774935363309919542532110972731996540328492565967313383895865130190496346350907696 : 1)
(4226762176873291628054959228555764767094892520498623417484902164747532571129516149589498324130156426781285021938363575037142149243496535991590582169062734 : 425803237362195796450773819823046131597391930883675502922975433050925120921590881749610863732987162129269250945941632435026800264517318677407220354869865 : 1)
b'V\x1b\xc6&\x04Z\xb0c\xec\x1a\tn\xd9\xa6(\xc1\xe1\xc5I\xf5\x1c\xd3\xa7\xdd\xa0\x84j\x9bob\x9d"\xd8\xf7\x98?^\x9dA{\xde\x08\x8f\x84i\xbf\x1f\xab'

## Code Analysis

F = GF(p)
E = EllipticCurve(F, [726, b])
G = E(926644437000604217447316655857202297402572559368538978912888106419470011487878351667380679323664062362524967242819810112524880301882054682462685841995367, 4856802955780604241403155772782614224057462426619061437325274365157616489963087648882578621484232159439344263863246191729458550632500259702851115715803253)

This code defines an Elliptic Curve here using the parameters $(GF(p), [726, b])$. In other words, the curve $E$ is: $$y^2 \equiv x^3 + 726x + b\ (mod\ p)$$

And $G$ is a point on $E$.

A = G * priv_a
B = G * priv_b

print(A)
print(B)

C = priv_a * B

assert C == priv_b * A

# now use it as shared secret
secret = C[0]

This code is a standard [Diffie-Hellman Key Exchange scheme](https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange). We know about `G`, `A`, `B`, and we want to know `((G * priv_a) * priv_b)` (equivalent to `A * priv_b`) or `((G * priv_b) * priv_a)` (equivalent to `B * priv_a`). This is a (supposingly) hard problem, that is, no one should be able to effiently find `C`, `priv_a` or `priv_b` by knowing only `G`, `A`, `B`, `E`, at least when this key exchange and cryptography is secure.

From what is printed in the code, we know what $A$ and $B$ is. They are provided in the `output.txt` file.

To avoid long long long numbers in this writeup, we will use the notation $G = (G_x, G_y)$. Similar notations are defined for points $A$, $B$.

## Straightforward approach

A simple approach is to apply Sage discrete_log function directly to do the discrete log problem (ECDLP). However, there is a crucial problem: we do NOT have the whole curve yet. In this problem, $b$ and $p$ are unknown secrets.

## Solving for the unknowns

What information can help us find out what $b$ and $p$ are? The only information about the curve is:

* The equation stated [above](#Code-Analysis), but obviously this is not helpful.

Looks like that is all, but actually there are some more.

* $G$, $A$, $B$ are points on $E$.
* $A, B$ can be obtained from $G$ by multiplying some integer constants.

The first fact here is actually useful. Recall what we learnt in functions and graphs: `A point is on the graph if and only if it satisfies the equation of the graph.` In other words, we can put the points into the equation of $E$ and obtain some more equations.

When we put $G$ into the equation, we have $$G_y^2 \equiv G_x^3 + 726 G_x + b\ (mod\ p)$$

We can express it in another form by making $b$ as the subject. $$b \equiv G_y^2 - G_x^3 - 726 G_x\ (mod\ p)$$

Similarly, we have $$b \equiv A_y^2 - A_x^3 - 726 A_x\ (mod\ p)$$ $$b \equiv B_y^2 - B_x^3 - 726 B_x\ (mod\ p)$$

We can calculate this using the following python/sage script.

Gx = 926644437000604217447316655857202297402572559368538978912888106419470011487878351667380679323664062362524967242819810112524880301882054682462685841995367
Gy = 4856802955780604241403155772782614224057462426619061437325274365157616489963087648882578621484232159439344263863246191729458550632500259702851115715803253
Ax = 6174416269259286934151093673164493189253884617479643341333149124572806980379124586263533252636111274525178176274923169261099721987218035121599399265706997
Ay = 2456156841357590320251214761807569562271603953403894230401577941817844043774935363309919542532110972731996540328492565967313383895865130190496346350907696
Bx = 4226762176873291628054959228555764767094892520498623417484902164747532571129516149589498324130156426781285021938363575037142149243496535991590582169062734
By = 425803237362195796450773819823046131597391930883675502922975433050925120921590881749610863732987162129269250945941632435026800264517318677407220354869865

print(f'b = {Gy ** 2 - Gx ** 3 - 726 * Gx} (mod p)')
print(f'b = {Ay ** 2 - Ax ** 3 - 726 * Ax} (mod p)')
print(f'b = {By ** 2 - Bx ** 3 - 726 * Bx} (mod p)')

We get the results:

b = -795681697752979021841640608005122212254481408059333389436461092784825702781732075202998355532776161687242583770626554226646700702822681028522622317139580412047249073777431186248756242053726846178683519895410827411480170487123529965570801762127312372615864877956046265119226609132011067488796059500296475165757221621606814766422659840111721465733339628985553330872697245012596263817584801121878502774373869888031674062739837325462968000518671538655034251350296 (mod p)
b = -235389841633113518256718847719878733250125469551464659906955192105157068458892240496251208387305226684383977028692545364635616542911806071089784509634298138989466830088876060296948154657939206289908022191050803100386883123914692738193940269023567868365152264359631600117242932969716150281155438233466191095095609214364837462241270538753838231525244229345683421423856137208707912136351137768367596194932966862290676506665434291342481388359433898092926158324340379 (mod p)
b = -75513297865381877165237329749121305404649863496562673628611547255472034783877319748412808667393686469886193277063058638505262905686384583987011362358457319536381368909650855340838565913232589885267322076370772598544068431036767525014189151469943189648194802751895203116369697087745722271774063256103313038301802715001727593484105594170399633466906647630238948981759128945460239877679475297123445626351905950631998326963214683279579832911791864195598564038489563 (mod p)

Again, for conciseness, we will name these 3 numbers as $r_1, r_2, r_3$. Note that all $r_i$ are equal after modulo $p$. (Otherwise $b\ mod\ p$ would have multiple values, which is obviously impossible.)

To further simplify this, we can make use of the fact that $b = pq + r$ for some integers $q, r$ is equivalent to $b \equiv r\ (mod\ p)$.

Combining these results, we have $$b = pq_1 + r_1 = pq_2 + r_2 = pq_3 + r_3$$ for some integers $q_1, q_2, q_3$.

Applying more simple algebra, we have 3 more equations. $$p (q_1 - q_2) = r_2 - r_1$$ $$p (q_1 - q_3) = r_3 - r_1$$ $$p(q_2 - q_3) = r_3 - r_2$$

While these 3 equations seem to be useless, the main thing here is that the differences are multiples of $p$.

In other words, $p$ is a factor of all $r_2-r_1, r_3-r_1, r_3-r_2$, that is, $p$ is a factor of $\gcd(r_2-r_1, r_3-r_1, r_3-r_2)$.

A script for computing this is:

r1 = Gy ** 2 - Gx ** 3 - 726 * Gx
r2 = Ay ** 2 - Ax ** 3 - 726 * Ax
r3 = By ** 2 - Bx ** 3 - 726 * Bx

print(f'b = {r1} (mod p)')
print(f'b = {r2} (mod p)')
print(f'b = {r3} (mod p)')

print(f'p is a factor of {gcd([r2 - r1, r3 - r1, r3 - r2])}')

The output is `p is a factor of 6811640204116707417092117962115673978365477767365408659433165386030330695774965849821512765233994033921595018695941912899856987893397852151975650548637533`.

Additionally, we can check whether $p$ is a prime. If $p$ is a prime, then $p$ is directly the number above. Otherwise, we may have to factorize it.

Luckily, the number above is a prime, so we know get $p$.

Now that we know $p$, we can recalculate $b$.

b = -795681697752979021841640608005122212254481408059333389436461092784825702781732075202998355532776161687242583770626554226646700702822681028522622317139580412047249073777431186248756242053726846178683519895410827411480170487123529965570801762127312372615864877956046265119226609132011067488796059500296475165757221621606814766422659840111721465733339628985553330872697245012596263817584801121878502774373869888031674062739837325462968000518671538655034251350296 (mod p)

Computing the modulo, we have $b \equiv 42\ (mod\ p)$. The mod $p$ does not really matter here.

## Final Step

We can finally apply our solution in the [straightforward approach](#Straightforward-approach) and use the discrete_log function in Sagemath to help us calculate $priv\_a$ or $priv\_b$.

Here is the solve script:

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes
from hashlib import sha256

Gx = 926644437000604217447316655857202297402572559368538978912888106419470011487878351667380679323664062362524967242819810112524880301882054682462685841995367
Gy = 4856802955780604241403155772782614224057462426619061437325274365157616489963087648882578621484232159439344263863246191729458550632500259702851115715803253
Ax = 6174416269259286934151093673164493189253884617479643341333149124572806980379124586263533252636111274525178176274923169261099721987218035121599399265706997
Ay = 2456156841357590320251214761807569562271603953403894230401577941817844043774935363309919542532110972731996540328492565967313383895865130190496346350907696
Bx = 4226762176873291628054959228555764767094892520498623417484902164747532571129516149589498324130156426781285021938363575037142149243496535991590582169062734
By = 425803237362195796450773819823046131597391930883675502922975433050925120921590881749610863732987162129269250945941632435026800264517318677407220354869865

r1 = Gy ** 2 - Gx ** 3 - 726 * Gx
r2 = Ay ** 2 - Ax ** 3 - 726 * Ax
r3 = By ** 2 - Bx ** 3 - 726 * Bx

print(f'b = {r1} (mod p)')
print(f'b = {r2} (mod p)')
print(f'b = {r3} (mod p)')

p = gcd([r2 - r1, r3 - r1, r3 - r2])
print(f'p is a factor of {p}')

if is_prime(p):
    print(f'p = {p}')
else:
	print('p is not prime. Please factorize before proceeding.')
	exit()

b = r1 % p
print(f'b = {b} (mod p)')

F = GF(p)
E = EllipticCurve(F, [726, b])
G = E(Gx, Gy)
A = E(Ax, Ay)
B = E(Bx, By)
priv_a = discrete_log(A, G, operation='+')

print(priv_a)

C = priv_a * B
secret = C[0]

print(C)

hash = sha256()
hash.update(long_to_bytes(lift(secret)))

key = hash.digest()[16:32]
iv = b'u\x8fo\x9aK\xc5\x17\xa7>[\x18\xa3\xc5\x11\x9en'
cipher = AES.new(key, AES.MODE_CBC, iv)
encrypted = b'V\x1b\xc6&\x04Z\xb0c\xec\x1a\tn\xd9\xa6(\xc1\xe1\xc5I\xf5\x1c\xd3\xa7\xdd\xa0\x84j\x9bob\x9d"\xd8\xf7\x98?^\x9dA{\xde\x08\x8f\x84i\xbf\x1f\xab'
decrypted = cipher.decrypt(encrypted)
print(decrypted)

And here is the output: `b'HTB{0rD3r_mUsT_b3_prEs3RveD_!!@!}\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f'`

## Alternative solution

Credit: This solution idea comes from https://7rocky.github.io/en/ctf/other/htb-cyber-apocalypse/arranged/

After we have obtained the parameters $b, p$. We can investigate the order of $G$.

F = GF(p)
E = EllipticCurve(F, [726, b])
G = E(Gx, Gy)
A = E(Ax, Ay)
B = E(Bx, By)

g_order = G.order()
print(g_order) # Output: 11

We can notice that $G$ has a very very very small order. We can simply loop through all the possible values of $n$.

priv_a = 0
priv_b = 0
for i in range(g_order):
    if i * G == A:
        print(f'priv_a = {i}')
        priv_a = i
    if i * G == B:
        print(f'priv_b = {i}')
        priv_b = i

And the whole solve script is:

# A detailed writeup is available at https://hackmd.io/@Jackylkk2003/Hyv5pCLlA

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Util.number import long_to_bytes
from hashlib import sha256

Gx = 926644437000604217447316655857202297402572559368538978912888106419470011487878351667380679323664062362524967242819810112524880301882054682462685841995367
Gy = 4856802955780604241403155772782614224057462426619061437325274365157616489963087648882578621484232159439344263863246191729458550632500259702851115715803253
Ax = 6174416269259286934151093673164493189253884617479643341333149124572806980379124586263533252636111274525178176274923169261099721987218035121599399265706997
Ay = 2456156841357590320251214761807569562271603953403894230401577941817844043774935363309919542532110972731996540328492565967313383895865130190496346350907696
Bx = 4226762176873291628054959228555764767094892520498623417484902164747532571129516149589498324130156426781285021938363575037142149243496535991590582169062734
By = 425803237362195796450773819823046131597391930883675502922975433050925120921590881749610863732987162129269250945941632435026800264517318677407220354869865

r1 = Gy ** 2 - Gx ** 3 - 726 * Gx
r2 = Ay ** 2 - Ax ** 3 - 726 * Ax
r3 = By ** 2 - Bx ** 3 - 726 * Bx

print(f'b = {r1} (mod p)')
print(f'b = {r2} (mod p)')
print(f'b = {r3} (mod p)')

p = gcd([r2 - r1, r3 - r1, r3 - r2])
print(f'p is a factor of {p}')

if is_prime(p):
    print(f'p = {p}')
else:
    print('p is not prime. Please factorize before proceeding.')
    exit()

b = r1 % p
print(f'b = {b} (mod p)')

F = GF(p)
E = EllipticCurve(F, [726, b])
G = E(Gx, Gy)
A = E(Ax, Ay)
B = E(Bx, By)

g_order = G.order()
print(g_order) # Output: 11

priv_a = 0
priv_b = 0
for i in range(g_order):
    if i * G == A:
        print(f'priv_a = {i}')
        priv_a = i
    if i * G == B:
        print(f'priv_b = {i}')
        priv_b = i

C = priv_a * B
secret = C[0]

print(C)

hash = sha256()
hash.update(long_to_bytes(lift(secret)))

key = hash.digest()[16:32]
iv = b'u\x8fo\x9aK\xc5\x17\xa7>[\x18\xa3\xc5\x11\x9en'
cipher = AES.new(key, AES.MODE_CBC, iv)
encrypted = b'V\x1b\xc6&\x04Z\xb0c\xec\x1a\tn\xd9\xa6(\xc1\xe1\xc5I\xf5\x1c\xd3\xa7\xdd\xa0\x84j\x9bob\x9d"\xd8\xf7\x98?^\x9dA{\xde\x08\x8f\x84i\xbf\x1f\xab'
decrypted = cipher.decrypt(encrypted)
print(decrypted)

We have the same output as above: `b'HTB{0rD3r_mUsT_b3_prEs3RveD_!!@!}\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f'`