HSCTF - High School Math · The Coach Cave

Table of Contents

This challenge was part of a CTF event hosted by HackerSchool.

$logo$

Challenge statement #

The only artifact provided in this challenge was the following python file:

#!/usr/bin/env python3

from Crypto.Util.number import getPrime, bytes_to_long

flag = bytes_to_long(open("flag.txt", "rb").read())

a = getPrime(1024)
b = getPrime(1024)

n = a*b
e = 65537

c = pow(flag, e, n)

print(f"{n = }")
print(f"{a**2 + b**2 + n**2= }")
print(f"{c = }")

# n = 13436543552497379694388600283360717813635824342586727821299891097425087808451129657132646384161598295682244109046681967399152114113039949692442357146097324414403714448303353670168683482849419889475073883021965128721280871508465237809638020307982223244592542117796329109625703795447628394080318467373338188481184094970667886099372277067791758310028719297560663656767841021135681599495175761141006932805280225013110829549034519947236406007628716612049188313632934875069078519054193264853872613184570847857034661356936183017256590466090548910652801538879801014480661747240873360666285731745662148831527068007355413188887
# a**2 + b**2 + n**2 = 180540702638158904555313141999781749074003490908937774272093358209266579892723492583838455210340254147384930625316273582841838217801840890803861355556649018897578690770481254908858674542005577405915622285279899406971259896933489523670420717548639427335001803646983644791045656241401673687187726280876455073539111273773923883651993721358207846391313978350794244107965610913946876423239477612677938072329660651267448386329961458280475278573633820153440808541964695106167741185667955129940403776069295440293733430131735411584242714529642808819687910706106548758202498227083847917068114857875765168196675243257199097750520922525008125630838354307923475925584698238491952278590917901260659431105142243114069887362690687689038563636726039494545276092127293952348826896731339109871895632727377083838126864650984923928053803715088333345176007341201339462938609657841855916777656479086368136149570496132274352713796154428855169222471580102944991273633691501186315783714064203309635192900325313597761340564885530634467783714002020973412451854154980882417205738681469209886776431322230847829601036652620826985668320534712843426539466194377506625250178274870835255571396913574981965993196321085336599004619779060743928193570956088985405537320419
# c = 4310162057906442585564591225725935614592110681401636449166311033403516541185696386758618323817603267436921298898073920430466461400657427528486851687645951458584703781966233462122925386869932442983177035396942716981989385980683508193428811207038681424346099327620840921382090799316092363704925374518170400010075824518901618979810132913400886887431741003736016069099461409316070555522686870318106487018663155309957528733145374170951930363390975465599161111285429601177974353905063294989440175780556563289724596829681492208800996187944182874779465052051746026368620569256527794801333872872427893580775064733755099734518

Solution #

The first lines of the script show a standard RSA scenario where a key is generated and used to encrypt the flag. The comments at the end show us the output of the script. The objects we have to work with are the public key, the ciphertext and an extra expression summing the squares of $a$, $b$ and $n$ (which I will refer to as $x$ from now on). In order to solve an RSA problem like this we need to figure out the private key exponent $d$, and then decrypt the ciphertext:

$$ d=e^{-1}\ mod\ \phi(n),\ where\ \phi(n)=(a-1)(b-1) $$

$$ m=c^d\ mod\ n $$

Therefore, the objective of this challenge is to figure out the value of $(a - 1)(b - 1)$. Since $a$ and $b$ each are composed of 1024 bits, any attempt at factoring $n$ is discarded right away. We can however, manipulate the given expressions in order to isolate what we want like so:

$$ a^2+b^2+n^2=x \leftrightarrow a^2 + b^2 = x - n^2 \leftrightarrow a^2+2ab+b^2 = x - n^2 + 2n \leftrightarrow (a+b)^2 = x - n^2 + 2n \leftrightarrow a+b = \sqrt{x-n^2+2n} $$

$$ (a-1)(b-1)=ab-a-b+1=n-(a+b)+1 $$

Decrypting #

Since all of these values are provided, we can now compute the private exponent and decrypt the flag with the following script:

#!/usr/bin/env python3

from gmpy2 import isqrt
from Crypto.Util.number import long_to_bytes

e = 65537

n = 13436543552497379694388600283360717813635824342586727821299891097425087808451129657132646384161598295682244109046681967399152114113039949692442357146097324414403714448303353670168683482849419889475073883021965128721280871508465237809638020307982223244592542117796329109625703795447628394080318467373338188481184094970667886099372277067791758310028719297560663656767841021135681599495175761141006932805280225013110829549034519947236406007628716612049188313632934875069078519054193264853872613184570847857034661356936183017256590466090548910652801538879801014480661747240873360666285731745662148831527068007355413188887
x = 180540702638158904555313141999781749074003490908937774272093358209266579892723492583838455210340254147384930625316273582841838217801840890803861355556649018897578690770481254908858674542005577405915622285279899406971259896933489523670420717548639427335001803646983644791045656241401673687187726280876455073539111273773923883651993721358207846391313978350794244107965610913946876423239477612677938072329660651267448386329961458280475278573633820153440808541964695106167741185667955129940403776069295440293733430131735411584242714529642808819687910706106548758202498227083847917068114857875765168196675243257199097750520922525008125630838354307923475925584698238491952278590917901260659431105142243114069887362690687689038563636726039494545276092127293952348826896731339109871895632727377083838126864650984923928053803715088333345176007341201339462938609657841855916777656479086368136149570496132274352713796154428855169222471580102944991273633691501186315783714064203309635192900325313597761340564885530634467783714002020973412451854154980882417205738681469209886776431322230847829601036652620826985668320534712843426539466194377506625250178274870835255571396913574981965993196321085336599004619779060743928193570956088985405537320419
c = 4310162057906442585564591225725935614592110681401636449166311033403516541185696386758618323817603267436921298898073920430466461400657427528486851687645951458584703781966233462122925386869932442983177035396942716981989385980683508193428811207038681424346099327620840921382090799316092363704925374518170400010075824518901618979810132913400886887431741003736016069099461409316070555522686870318106487018663155309957528733145374170951930363390975465599161111285429601177974353905063294989440175780556563289724596829681492208800996187944182874779465052051746026368620569256527794801333872872427893580775064733755099734518

a_plus_b = isqrt(x - n**2 + n + n)
phi = n - a_plus_b + 1

d = pow(e, -1, phi)
m = pow(c, d, n)

print(long_to_bytes(m))