Rating:
# Baby RSA (crypto, 60p, 87 solved)
## Description
In the task we get [some code](https://raw.githubusercontent.com/TFNS/writeups/master/2020-07-03-ASIS-quals/baby_rsa/baby_rsa.py) and [outputs](https://raw.githubusercontent.com/TFNS/writeups/master/2020-07-03-ASIS-quals/baby_rsa/output.txt).
The code is just standard RSA encryption, however the key is selected in such a way that private exponent `d` is divisible by some `1 << r` for `r = random.randint(12, 19)`.
Apart from public key we also get to know two special values `t_p` and `t_q`
```python
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)
```
## Solution
Let's look at `t_p`.
It is `(s*p+1)^((d-1)/(2^r)) mod n`
We could rephrase this as just `(s*p+1)^k mod p*q`
Now if we were to do `mod p` here we would have:
```
(s*p+1)^k mod p
((s*p+1) mod p * (s*p+1) mod p * (s*p+1) mod p ... *(s*p+1) mod p) mod p
```
We know that `(s*p+1) mod p = (s*p mod p + 1 mod p) mod p = 1 mod p`, therefore `(s*p+1)^k mod p = 1`
This implies that `(s*p+1)^k - 1 mod p = 0` and this implies that `(s*p+1)^k - 1` has to be a multiple of `p`.
If this is the case, then `gcd((s*p+1)^k - 1, n) = p` and thus `gcd(t_p-1,n) = p`
We can then recover the flag by:
```python
from crypto_commons.generic import long_to_bytes
from crypto_commons.rsa.rsa_commons import modinv, gcd
def main():
n = 10594734342063566757448883321293669290587889620265586736339477212834603215495912433611144868846006156969270740855007264519632640641698642134252272607634933572167074297087706060885814882562940246513589425206930711731882822983635474686630558630207534121750609979878270286275038737837128131581881266426871686835017263726047271960106044197708707310947840827099436585066447299264829120559315794262731576114771746189786467883424574016648249716997628251427198814515283524719060137118861718653529700994985114658591731819116128152893001811343820147174516271545881541496467750752863683867477159692651266291345654483269128390649
t_p = 4519048305944870673996667250268978888991017018344606790335970757895844518537213438462551754870798014432500599516098452334333141083371363892434537397146761661356351987492551545141544282333284496356154689853566589087098714992334239545021777497521910627396112225599188792518283722610007089616240235553136331948312118820778466109157166814076918897321333302212037091468294236737664634236652872694643742513694231865411343972158511561161110552791654692064067926570244885476257516034078495033460959374008589773105321047878659565315394819180209475120634087455397672140885519817817257776910144945634993354823069305663576529148
enc = 5548605244436176056181226780712792626658031554693210613227037883659685322461405771085980865371756818537836556724405699867834352918413810459894692455739712787293493925926704951363016528075548052788176859617001319579989667391737106534619373230550539705242471496840327096240228287029720859133747702679648464160040864448646353875953946451194177148020357408296263967558099653116183721335233575474288724063742809047676165474538954797346185329962114447585306058828989433687341976816521575673147671067412234404782485540629504019524293885245673723057009189296634321892220944915880530683285446919795527111871615036653620565630
e = 65537
p = gcd(t_p - 1, n)
q = n // p
d = modinv(e, (p - 1) * (q - 1))
print(long_to_bytes(pow(enc, d, n)))
main()
```
And we get `ASIS{baby___RSA___f0r_W4rM_uP}`
It does seem like an unexpected solution though.
The task setup seems to hint at brute-forcing `r`, raising `t_p` and `t_q` to `2^r` powers to get `(s*p+1)^(d-1)` and `(t*q+4)^(d-1)` and working from here...
