# HKCERT CTF 2022 Writeup: Rogue Secret Assistant
> Rogue Secret Assistant (250 points, 7 solves)
> Mystiz does not seem to give up using RSA to store his secrets. This time you are even allowed to send arbitrary public exponent, e. Can you unveil the secret flag?

<details>
<summary>Source code:</summary>

from Crypto.Util.number import getPrime as get_prime
import os

def build_message(secret, e):
    m = f'The secret token is {secret.hex()} and it is encrypted with e = {e}.'.encode()
    return int.from_bytes(m, 'big')

def main():
    # Do not submit hkcert22{***REDACTED***}. The actual flag is in the netcat service!
    flag = os.environ.get('FLAG', 'hkcert22{***REDACTED***}')

    p, q = [get_prime(1024) for _ in 'pq']
    n = p * q

    secret = os.urandom(64)

    for _ in range(3):
        e = int(input())
        if e == 1: raise Exception('send me better values!')
        m = build_message(secret, e)
        c = pow(m, e, n)
        print(f'c = {hex(c)}')

    guess = input()
    if secret != bytes.fromhex(guess): raise Exception('incorrect secret!')

    print(flag)

if __name__ == '__main__':
    try:
        main()
    except:
        print('better luck next time!')

</details>

## Challenge Overview
From reading the source code, it seems the challenge server is using RSA to encrypt messages of the form - `The secret token is {secret.hex()} and it is encrypted with e = {e}.`, where `secret` is $64$ random bytes, and $e \neq 1$ is an integer from our input.

We are able to send up to $3$ different values of $e$ (and receive the $3$ corresponding ciphertexts), but we are *not* given the value of $n$.

## Observation
Notice that the challenge server will use any value of $e$ that we pass to it, as long as $e \neq 1$, which means it accepts non-positive values of $e$ as well. Note that $e = 0$ isn't really helpful to us, as the ciphertext will always be $1$. However, negative values of $e$ might be helpful to us ($e = -1$ in particular!).

## Eww Equations D:
It might be helpful for us to define the (currently unknown) variable $x$ as follows:
Let `x = bytes_to_long(b'The secret token is {secret.hex()} and it is encrypted with e = ')`.
We shall also define $E(e)$ as the value of the ciphertext when we send $e$ to the challenge server.

Then, we should be able to see that:

$E(1) = 256^2 * x + bytes\_to\_long('1.') \mod n$
$E(2) = (256^2 * x + bytes\_to\_long('2.'))^2 \mod n$
$E(3) = (256^2 * x + bytes\_to\_long('3.'))^3 \mod n$
...
$E(-1) = (256^3 * x + bytes\_to\_long('-1.'))^{-1} \mod n$
$E(-2) = (256^3 * x + bytes\_to\_long('-2.'))^{-2} \mod n$
$E(-3) = (256^3 * x + bytes\_to\_long('-1.'))^{-3} \mod n$

Let us focus on $E(-1)$ for now. It follows that:

$E(-1) = (256^3 * x + bytes\_to\_long('-1.'))^{-1} \mod n$
$E(-1) = (k1 * x + k2)^{-1} \mod n$
$E(-1) * (k1 * x + k2) = 1 \mod n$
$E(-1) * (k1 * x + k2) - 1 = 0 \mod n$

Where $k1, k2$ are known constants, and $E(-1)$ could be given to us if we send $e = -1$ to the challenge server.

Let us assume we do send $e = -1$ to the server (and hence $E(-1)$ will be known to us). Then,

$E(-1) * k1 * x + E(-1) * k2 - 1 = 0 \mod n$
$k3 * x = k4 \mod n$

Where $k3, k4$ are known constants as well.
Here, we end up with a linear equation in terms of $x \mod n$, which means once we recover the value of $n$, we could easily recover $x$ and hence `secret.hex()` as well :D

## Recovering n
Seeing as we can't send over $e = 1$, and since $e = 0$ is useless to us, it's natural for us to consider the next smallest values of $e$: $e = 2$ and $e = -2$.

By expanding the equations for $E(2), E(-2)$ from above (once again assuming $E(2), E(-2)$ are known values to us), we get $2$ quadratic equations, which we shall denote as:

$E(2): ax^2 + bx + c = 0 \mod n$
$E(-2): dx^2 + ex + f = 0 \mod n$

By themselves, these $2$ equations aren't really useful to us, but when combined with the linear equation from above, we should be able to get $2$ values that are $0 \mod n$.

Given $E(-1): k3 * x = k4 \mod n$.
$E(2): ax^2 + bx + c = 0 \mod n$
$\implies (k3)^2 * (ax^2 + bx + c) = (k3)^2 * 0 \mod n$
$\implies a * (k3 * x)^2 + b * (k3 * x) * k3 + (k3^2) * c = 0 \mod n$
$\implies a * (k4)^2 + b * k3 * k4 + c * (k3)^2 = 0 \mod n$

Similarly, we have

$E(-2): dx^2 + ex + f = 0 \mod n$
$\implies d * (k4)^2 + e * k3 * k4 + f * (k3)^2 = 0 \mod n$

Where $a, b, c, d, e, f, k3, k4$ are all known constants. Once we have these two values, we could just take their gcd, and hope that we end up with a small multiple of `n`. (And it seems like we do!).

## Recovering the Secret
Now, once we have $n$, all we have to do is to print out $k4 * k3^{-1} \mod n$ in bytes form.

## Implementation
<details>
<summary>Ugly "Code" Below</summary>

# 2, -1, -2
c1 = 0x8126974f99173b730f8905d4dd5afa9ade3173e0881e08d808e3025358c036804ec01890bcabae376a423594e60e8987b4d2da064b34fd038ba98c3fe3edd97daaf1a2b95627bededda9786ce73c8e3f9fa3a250a3fd752b9785e419cde8c513de748e1807945c1a06f305e2e06974b6f26a5bedb9bd2f91cb7957492f16e065b77afd3987294407ccb4d216fb102cc4e0de49e7625a61a73873e3c3f443585db6425c9a2f4912d7bd7102d36ba8504bcc3b0e89bcf3e7cbe68cd8ee88dd42aafdbf9a8407f7c390c927da620b2750c1d87f44a5e4f290e58bf505ff8902a2b8622380df7e9a4a2887f3fd433eedf08d218a91441ff9cfd2daf1e5cbfa360dcb
c2 = 0x477fbafeb162453b4c145500a04733cefe10d86fd732d5ff69e6f5583476d1f88249fde6f854a836037f08525903bebe25be5d962645d93b5ec4c1b9b6964fe394959568f38c344cbdf33637e04cf0b2ef1c11af2041b798f015e572996218ee1a595cb987f036ead6d9c118a0e6d25b2465137cd15e261d952c31e6cd8f72c222bf8c42eb922237a0ce151069490a148b9062f0056e248b046f9e0ad2a21ef5d105ef9aa128842100c053b95f36a8aa2c523d02afff2e186932afd1311c45ddd74e16a5473031df4657b7a45f0ae57a1633374fdff073870732ebb0c7eb12f5d1b9ccd10ea60e0234295ffa594a0a2668d3ca09ccad975c1314b9e14fdae738
c3 = 0x62ef6375bcc67a29d6205aacf686fc6ce5a56bdd313ef900a37bb08116cd03f6c453cf3f4c461f30b8d354f0501c44220c538f3b81cd51a67723f5c0ec43ffc3a76c54366df48ee4ca0abbfca2dbaeedb04263be1ec46334345b7c72ca1814e9dabc80c904f80cd2bf6e8d1020d407b39b63e4c0ccb8f4db1d75c7c8b82212bf6457abe20f8178add110ec3ade7218a3789738ba8bff3b5393fe5494c2bedd04746d87d0e1fe1fd66edb62c8b53db0f725669cb0d2da82045d299a245e5237682c98eed0f9bf272d18c64b91f23ec83fc8d62f51cde3b2f2dd845978688cc6a5fb3f029278fb6f247a72fd28d0e927225432cca9338ca9f1cb16d2551dfd48dd

R.<x> = ZZ[]
f1 = (256^2 * x + 256 * ord('2') + ord('.'))^2 - c1
f2 = (256^3 * x + 256^2 * ord('-') + 256 * ord('1') + ord('.')) * c2 - 1
f3 = (256^3 * x + 256^2 * ord('-') + 256 * ord('2') + ord('.'))^2 * c3 - 1
print("f1 is: {}".format(f1))
print("f2 is: {}".format(f2))
print("f3 is: {}".format(f3))

f1 is: 4294967296*x^2 + 1683750912*x - 16303771300735113688863174706362805482473631526015411269611317375665975262592864397615884315016590265473739837393081418531525004107142523953426387617059319558064461068374627819380928911444147278439019484472456407085890964682183546943819566285816172859427842925696517102539287512068316973484833313977754242678764250647471019174603799338267418417339214438176079542013987358630808631220349469959987984845033281577431572459074280729758714188512381635827742464257921910809664474784397654297405623659603145191514684449093099826416216234523724291961247135535344109256161492383039531753840360535758193750208588358604761861511
f2 is: 151429572618670544930292164008030247887933350943061279075842172829809435841273693917565754961893407348736587098762457568910610026024863252985622727035913549935908142066162839615557503079357784766202539013172847729174502220254319176966941793414897859070109085208300586760608370970985148412590913167827332102779101891504031995676946898546656120810410479471658862561506754301995702892969129358446445443600395723451329503114526777966926771104979947544812877258061296913231238164192364962295565747402579107516507783463574284464168893115405131326692380032990778314098060899661314526560163600466225317460056219503045005469921837056*x + 26732115716960593439668155018342928020487492371891380599243195157752925409403962612902740962993462293078102909104571235562458206425791844427588503771396608351509481873439260942804384973357006592745168317598352125166262088462675788975641797719886132370622919723527188945696438454894806379381098356144779191143625608866596615428708219462312275145375777551889823069396029072032194925256705290806557055399759293681564158360321825955654781296809325244602426690099997739844685219721208169012093545778971467526120917043799316527865746762086542338226919702739066960850201126762384882358223327227641593514360374561808313319106233359
f3 is: 3515453788959018607131599211093180191169936156135020804540162721770994686266264742497787455942960772352810372430239139418883395467441662966447932922699160208900736403752846427504421003852124705350994525122754468052526480985619210475206408666941517358103221218305452411503981499779592139442265016966579594753463199329783485454412389183759257436572357121253058807253350135374220340208909296018625248285958476369031531952016883192430182159884952737843386346047958990158477047782667203165184198335904541027787024944370995233715803774072187638761052141561551754504169199781352673964335591053684685662694403564916867010128953646602256384*x^2 + 1241285156901811183415788935289957828297478093700721625368667556804793601858775986942911329237168758755059758136952603200434729497327365003833522568621103855051622224197173538385577185523016739488800030899017400827368456218129466816712048703859579372776933400523582417666054018375415731775194161325029360765640303929572280797656064837105592812582788268686465928922292767414312115217116145120990675945826445152387005158637480669254023662970756759774568519813810455589740708746032195698066708947206238480795648470685336502603085570511043230489554234448969746122562411785074955736571220551838661867807899922080344308677150764085280768*x + 109572542639012040606061538741143203641503095605562675887546860234703638724184968320767500943401449909647981273230223485564555346676133454172157153740178838405961789873731294774942830619063013785978647241647212942213929795938374528563896419142965760125714609522081414441008906262855429452158354200221655237363593234689816542420093528667160997412043542773967288184948200557443511446153540608270176305429809464282844308665657760738958819297398344180656660209859398004452047590066492514700289298102875750303517690841018063404239742605218668974644631075676593871225765245717505405641463752181749163208707991260428104120350645187336883

a, b, c = f1.coefficients(sparse=False)[::-1]
d, e, f = f3.coefficients(sparse=False)[::-1]
k3, k4 = f2.coefficients(sparse=False)[::-1]; k3 *= -1

F1 = a * k4^2 + b * k3 * k4 + c * k3^2
F2 = d * k4^2 + e * k3 * k4 + f * k3^2
multiple_of_n = gcd(F1, F2)
print(multiple_of_n)

106405824425311617034850273051867764358903765537521590978650924092843202611283771614730352189091527651545905057832856766770936600418749260033635428693735909071748599653165873562653815162802761735376181330182626844385224176269304563213713473706493642649217751900382667758537930483578643647585712995644920666371300487168500049467496853441177566201998760180317596690921734116234442513159605528613460216374191497952039670071773568669054454379987471919533566877065264853352602119423217352998321165980404415769796943612218835597185900639750008486108615853323943403904844497749493244778744375601217205057730553051686939761103018655744

# from factor-db
n = 24774536589465946200036041683486607940612306245025617764017294182638452065010501913430716886439250701001357533464407726836143201314552980482959055503303163934440491640280437088258055775147574426461053390564077264718996401938913521173809066812157082056910207471899378057228850779025499626897674285724042138636880667686578829183126067146933070896658757743499613527888835900517749253930432146557946739805441232852647004200092882073729870463718537222485422826620113303268468500912007259437423470891174957102583009659363617095441068671585528293184148113551536436170536209305164694036064756941333693698451517394670969750989
long_to_bytes(int((k4 * pow(k3, -1, n)) % n))

b'The secret token is 2e5379e3caa2dd0bc6ed48be1ccfb53eb7d16bb52df9a0c71c85f5cda33a259b8643200fe698dad3a619a6ba56d871aaa867eb4c37f3b5e9795abd141229f019 and it is encrypted with e = '

</details>