pqqp

2 minutes to read

We are given this Python source code that encrypts the flag:

from Crypto.Util.number import *

p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537

m = bytes_to_long(open("flag.txt", "rb").read().strip())  
c = pow(m, e, n)

pqqp = (pow(p, q, n) + pow(q, p, n)) % n

print(f"{n = }")
print(f"{e = }")
print(f"{c = }")
print(f"{pqqp = }")

And we have the output.txt file:

n = 19678109133542698592305708016218863883460540049917712329432013892172528110292745184992950044286234053071380305255840348326164548510255147118470308166391801316954651278311516797693549738950638924838729113122082201649970553380521265027078990142823602788816122841173521655481024888439982252740049512798598085061773695717897738054691150959372485365062487195925100664710335322057804378500514036943988819273662050112952925141139754952427282840502980857190361170607335143494354546987865462698409956206631411308141753183566771545343693446609738596094372008339052131415140340456565555396933183573996686236769224009352680776141  
e = 65537
c = 4072247787644405517693225466780406787448185227848467266590680538951503737695652776519815815044794587161578707809819763441075707137469351267404539758695849074266727221320662086207093016080297854717488042255308770890593983978724257303414642859978484084458380098954259220304333391581145689059564973907676661078965777905977665249069877734867259119271333543347675967002480182290529431802723432351160734165536930587939120516653618367482414081000718254774375447568464759357446892747598177493342245946293460645987948522541784101210339329312458616738544161953857715180345325332187115407714964472659039920532267119264418919947
pqqp = 286274681617083968101800572253589724107707315933733496895870570711787172051691156975540599189839527166581986519156360694553593020374681020209511667035419131460916677948315029070571749042370272329205309015536090768801019566664262350433731622252363771741528214379501493482631649996976367966453784254842455722642

First of all, we need to express $p^q + q^p \mod{n}$ in another way.

By Fermat’s Little Theorem, we know that:

$$ p^q \equiv p \mod{q} \Longrightarrow p^{q - 1} \equiv 1 \mod{q} $$

So,

$$ p^{q - 1} = k \cdot q + 1 \Longrightarrow p^q = p (k \cdot q + 1) \; k \in \mathbb{Z} $$

And similarly, $q^p = q (l \cdot p + 1)$ for $l \in \mathbb{Z}$

Hence,

$$ \begin{align} p^q + q^p & = p \cdot (k \cdot q + 1) + q \cdot (l \cdot p + 1) \newline & = (k + l) \cdot pq + p + q \newline & = (k + l) \cdot n + p + q \end{align} $$

And therefore $p^q + q^p \equiv p + q \pmod{m}$, which is crucial for decrypting RSA.

We need to find $d = e^{-1} \mod{\phi(n)}$, and

$$ \phi(n) = (p - 1) \cdot (q - 1) = pq - (p + q) + 1 = n - (p + q) + 1 $$

Then we’ll decrypt the ciphertext as $m = c^d \mod{n}$.

We can do everything in Python:

$ python3 -q
>>> n = 19678109133542698592305708016218863883460540049917712329432013892172528110292745184992950044286234053071380305255840348326164548510255147118470308166391801316954651278311516797693549738950638924838729113122082201649970553380521265027078990142823602788816122841173521655481024888439982252740049512798598085061773695717897738054691150959372485365062487195925100664710335322057804378500514036943988819273662050112952925141139754952427282840502980857190361170607335143494354546987865462698409956206631411308141753183566771545343693446609738596094372008339052131415140340456565555396933183573996686236769224009352680776141  
>>> e = 65537
>>> c = 4072247787644405517693225466780406787448185227848467266590680538951503737695652776519815815044794587161578707809819763441075707137469351267404539758695849074266727221320662086207093016080297854717488042255308770890593983978724257303414642859978484084458380098954259220304333391581145689059564973907676661078965777905977665249069877734867259119271333543347675967002480182290529431802723432351160734165536930587939120516653618367482414081000718254774375447568464759357446892747598177493342245946293460645987948522541784101210339329312458616738544161953857715180345325332187115407714964472659039920532267119264418919947
>>> pqqp = 286274681617083968101800572253589724107707315933733496895870570711787172051691156975540599189839527166581986519156360694553593020374681020209511667035419131460916677948315029070571749042370272329205309015536090768801019566664262350433731622252363771741528214379501493482631649996976367966453784254842455722642
>>> phi_n = n - pqqp + 1
>>> d = pow(e, -1, phi_n)
>>> m = pow(c, d, n)
>>> bytes.fromhex(hex(m)[2:])
b'ictf{can_you_proof_that_p^q+q^p_is_actually_p+q?}'