Somkracht was a 200 point cryptography challenge on WhyCTF 2025.

Problem Description

Is this how RSA works? I read something about p and q somewhere.

Solution

from Crypto.Util.number import *

p = getPrime(1024)
q = getPrime(1024)
N = p*q

e = 65537

msg = bytes_to_long(b"flag{dummy_flag}")

ct1 = pow(msg, e, N)
ct2 = pow(msg, p+q, N)

print(f"{N = }")
print(f"{ct1 = }")
print(f"{ct2 = }")

"""
N = 13172635138210286640933237746072073728198869440440273861514688422430115450596963502627269613634657978751692320585777768877613321668778514462972611542147278205792418292362109100597755668571861738781190210255903465162483813897653948305531342676537057130369323555420200545974179860718822410192595079238246216026529376260568656408216009127973127738250617629330070723654601189310430802429585919291621479622419163092371272056180409609142738265178224163465585013019636286435078812898907472859171136422659050412212315590509027225331104292443193693974638004592849794819591007103879538185323581422819852185166422985403024630123
ct1 = 8499526321488266762028127474977263983474334713646962923180757984708039537289636737028409522654349845032612940144246996001396064450188534247830979105036627472087587636695469693411422088223080856169980341928057477564688506588678465277896123712776169270866525885072607021419929184184301722442524104467963680432737243478200661224741027413690099507128782156810842444314483076587935222998920241102484844741597333281611874849648935849985954902264102662618041817365284648356127737145896858259709819593359264714426125676691235985164360773645489923563993927995838346085066937602961724919392025887999986486672200850129835569774
ct2 = 2263178005282615069738169250508811825030372342139636879043114251227029802177975391784856426659871916802959302578620910469427367218786299839311310420522660987052055310279591316813828952756984548230575321772825193775083404279028090110850848262192595930920326368607665856808251531130234210906413358662814500632504899088517752958423466186872534450108628371006268110210630017230741670440780982809417986017372337888735465439382827207990030719121834402226087906249993820193417658352914727984318783025375497623944699995700474418221251293446038111913247755996471673024017921092527032486774115935601292346440934530921157935322

We’re given two RSA ciphertexts:

\[c_1 = m^e \pmod{N}\] \[c_2 = m^{p + q} \pmod{N}\]

By Euler’s theorem, we have for \(m, N\) coprime (as is the case here), \(m^{\varphi(N)} \equiv 1 \pmod{N}\). Then since \(N = pq\), \(\varphi(N) = N - (p + q) + 1\), so \(N + 1 \equiv p + q \pmod{\varphi(N)}\), meaning \(m^{p + q} \equiv m^{N + 1} \pmod{N}\).

To recover \(m\), we verify that \(\gcd(e, N + 1) = 1\). By Bézout’s identity, there exist integers \(x, y\) such that \(ex + (N + 1)y = 1\), and computing these is simple with the extended Euclidean algorithm. Then

\[c_1^x c_2^y = (m^e)^x (m^{N + 1})^y\] \[= m^{ex + (N + 1)y}\] \[\equiv m \pmod{N}\]

This can be done concisely in Sage:

import binascii
_, x, y =  xgcd(e, N + 1)
m = (pow(ct1, x) * pow(ct2, y)) % N
print(binascii.unhexlify(hex(m)[2:]))

which gives us flag{31470335203860e47f0c3b1dd50e1da9}

Flag

flag{31470335203860e47f0c3b1dd50e1da9}