## Baby RSA

> All babies love [RSA](https://asisctf.com/tasks/baby_rsa_704000e3703726346fa621a91a9f8097a9307929.txz). How about you? ?

#### Challenge

```python
#!/usr/bin/python

from Crypto.Util.number import *
import random
from flag import flag

nbit = 512
while True:
p = getPrime(nbit)
q = getPrime(nbit)
e, n = 65537, p*q
phi = (p-1)*(q-1)
d = inverse(e, phi)
r = random.randint(12, 19)
if (d-1) % (1 << r) == 0:
break

s, t = random.randint(1, min(p, q)), random.randint(1, min(p, q))
t_p = pow(s*p + 1, (d-1)/(1 << r), n)
t_q = pow(t*q + 4, (d-1)/(1 << r), n)

print 'n =', n
print 't_p =', t_p
print 't_q =', t_q
print 'enc =', pow(bytes_to_long(flag), e, n)
```

#### Solution

To solve this challenge, we use that for the RSA cryptosystem the public and private keys obey

$$
e\cdot d - 1 \equiv 0 \mod \phi(n), \qquad \Rightarrow \qquad e\cdot d - 1 = k \cdot \phi(n), \quad k \in \mathbf{Z}
$$

and Euler's theorem, which states that

$$
\gcd(a,n) = 1 \qquad \Leftrightarrow \qquad a^{\phi(n)} \equiv 1\mod n
$$

We have the data $t_p, t_q, e, n$ which is suffient to solve for $p$. Using that

$$
t_p = (sp + 1)^{\frac{d-1}{2^r}}
$$

We can take `eth` power to find

$$
\begin{align}
t_p^e &= (sp + 1)^{\frac{ed-e}{2^r}} \mod n \\
&= (sp + 1)^{\frac{k\phi(n) + 1 -e}{2^r}} \mod n \\
&= (sp + 1)^{\frac{k\phi(n)}{2^r}} (sp + 1)^{\frac{e - 1}{2^r}} \mod n
\end{align}
$$

From Euler's theorem we have

$$
(sp + 1)^{\frac{k\phi(n)}{2^r}} \equiv 1^{\frac{k}{2^r}} \equiv 1 \mod n
$$

The value of `r` is of small size `r = random.randint(12, 19)` and we know that $e - 1 = 2^{16}$ and so we know that we have

$$
t_p^e = (sp + 1)^{m} \mod n, \qquad m \in \{16, 8, 4, 2, 1, \frac12, \frac14 \}
$$

We can expand out $t_p^e$ and write down

$$
\begin{align}
t_p^e - 1 = s p \cdot (s^{m-1} p^{m-1} + \ldots + m) \mod n \\
\end{align}
$$

We can solve the challenge by then looking at

$$
\gcd(t_p^e - 1, n) = p
$$

**Note**: we can only treat $p$ as a true factor in the above line as $n = p\cdot q$, so by nature of the CRT, this expression simplifies.

#### Implementation

```python
import math
from Crypto.Util.number import *

n = 10594734342063566757448883321293669290587889620265586736339477212834603215495912433611144868846006156969270740855007264519632640641698642134252272607634933572167074297087706060885814882562940246513589425206930711731882822983635474686630558630207534121750609979878270286275038737837128131581881266426871686835017263726047271960106044197708707310947840827099436585066447299264829120559315794262731576114771746189786467883424574016648249716997628251427198814515283524719060137118861718653529700994985114658591731819116128152893001811343820147174516271545881541496467750752863683867477159692651266291345654483269128390649
e = 65537
t_p = 4519048305944870673996667250268978888991017018344606790335970757895844518537213438462551754870798014432500599516098452334333141083371363892434537397146761661356351987492551545141544282333284496356154689853566589087098714992334239545021777497521910627396112225599188792518283722610007089616240235553136331948312118820778466109157166814076918897321333302212037091468294236737664634236652872694643742513694231865411343972158511561161110552791654692064067926570244885476257516034078495033460959374008589773105321047878659565315394819180209475120634087455397672140885519817817257776910144945634993354823069305663576529148
t_q = 4223555135826151977468024279774194480800715262404098289320039500346723919877497179817129350823600662852132753483649104908356177392498638581546631861434234853762982271617144142856310134474982641587194459504721444158968027785611189945247212188754878851655525470022211101581388965272172510931958506487803857506055606348311364630088719304677522811373637015860200879231944374131649311811899458517619132770984593620802230131001429508873143491237281184088018483168411150471501405713386021109286000921074215502701541654045498583231623256365217713761284163181132635382837375055449383413664576886036963978338681516186909796419
enc = 5548605244436176056181226780712792626658031554693210613227037883659685322461405771085980865371756818537836556724405699867834352918413810459894692455739712787293493925926704951363016528075548052788176859617001319579989667391737106534619373230550539705242471496840327096240228287029720859133747702679648464160040864448646353875953946451194177148020357408296263967558099653116183721335233575474288724063742809047676165474538954797346185329962114447585306058828989433687341976816521575673147671067412234404782485540629504019524293885245673723057009189296634321892220944915880530683285446919795527111871615036653620565630

p = math.gcd(n, pow(t_p, e, n) - 1)
q = n // p
phi = (p-1)*(q-1)
d = inverse(e, phi)
flag = pow(enc,d,n)
print(long_to_bytes(flag))
# b'ASIS{baby___RSA___f0r_W4rM_uP}'
```

#### Flag

`b'ASIS{baby___RSA___f0r_W4rM_uP}'`

Original writeup (https://jack4818.github.io/ASIS-Quals-2020/#baby-rsa).