Weaken
Crypto: Weaken
Challenge Description
I sure hope you paid attention in the slides!
Flag format: RISC{plaintext_here}
Attachments
chal.py
from Crypto.Util.number import getPrime, bytes_to_long
p = getPrime(64)
q = getPrime(64)
n = p * q
e = 65537
with open("flag.txt", 'r') as f:
flag = f.read()
m = bytes_to_long(flag.encode())
c = pow(m, e, n)
with open("output.txt", "w") as f:
f.write(f"n = {n}\n")
f.write(f"e = {e}\n")
f.write(f"c = {c}\n")
output.txt
n = 295772392439388299654489126814990313873
e = 65537
c = 84399961258690568509996087862032043548
Approach
Since $p$ and $q$ are only 64-bit primes, $n$ is around 128 bits and should likely appear in FactorDB (or be factorable in a reasonable amount of time). Looking up $n$ on FactorDB directly yields its prime factors:
$$ p = 16576445552230103159\\ q = 17842932099493230647 $$We can sanity check this if we so please:
$$ \begin{align*} p \cdot q &= 16576445552230103159 \cdot 17842932099493230647 \\ &= 295772392439388299654489126814990313873 \\ &= n \end{align*} $$With $p$ and $q$, we can compute Euler’s totient ($\varphi$) and thus the private exponent d:
$$ \begin{align*} \varphi(n) &= (p − 1)(q − 1) \\ &= 295772392439388299620069749163266980068 \end{align*} $$ $$ \begin{align*} d &\equiv e^{-1}\mod \varphi(n)\\ d &= 194413585020735907518399753642296946265 \end{align*} $$And decrypt:
$$ m \equiv c^d \mod n $$Finally, convert the integer $m$ to bytes to recover the plaintext flag.
Python implementation
from Crypto.Util.number import long_to_bytes
n = 295772392439388299654489126814990313873
e = 65537
c = 84399961258690568509996087862032043548
p = 16576445552230103159
q = 17842932099493230647
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)
flag = long_to_bytes(m).decode()
print("plaintext =", flag)
$ python3 solve.py
plaintext = n33d_m0r3_b1t5
Thus, our flag is:
RISC{n33d_m0r3_b1t5}