# kleinvieh

## Description

RSA with some additional leak of information is always a good challenge. I wonder how this one gets broken.

## Source

- `chall.py`
```
from Crypto.PublicKey import RSA

flag = int.from_bytes(open('flag.txt','r').read().strip().encode())
key = RSA.generate(1024)

print(f'n = {key.n}')
print(f'c = {pow(flag, key.e, key.n)}')
phi = (key.p - 1) * (key.q - 1)
print(f'strange = {pow(phi, 2, key.n)}')
```

- `out.txt`
```
n = 123478096241280364670962652250405187135677205589718111459493149962577739081187795982860395854714430939628907753414209475535232237859888263943995193440085650470423977781096613357495769010922395819095023507620908240797541546863744965624796522452543464875196533943396427785995290939050936636955447563027745679377
c = 77628487658893896220661847757290784292662262378387512724956478473883885554341297046249919230536341773341256727418777179462763043017367869438255024390966651705078565690271228162236626313519640870358976726577499711921457546321449494612008358074930154972571393221926233201707908214569445622263631145131680881658
strange = 11519395324733889428998199861620021305356608571856051121451410451257032517261285528888324473164306329355782680120640320262135517302025844260832350017955127625053351256653287330703220294568460211384842833586028123185201232184080106340230097212868897257794101622865852490355812546172336607114197297201223620901
```

## Solution

- `phi` is `n - p - q + 1`. So, `phi ** mod n` = `(p+q+1) ** 2 mod n`
- Since `n = p * q`, `(p+q+1) ** 2` should be around 4 times `n`.
- If we add `n` between 0 to 10 times to `strange`, we should get the exact square of `(p+q+1)`
- The we can subtract that from `n` to get `phi` and decrypt the RSA normally

- `solve.py`
```
n = 123478096241280364670962652250405187135677205589718111459493149962577739081187795982860395854714430939628907753414209475535232237859888263943995193440085650470423977781096613357495769010922395819095023507620908240797541546863744965624796522452543464875196533943396427785995290939050936636955447563027745679377
c = 77628487658893896220661847757290784292662262378387512724956478473883885554341297046249919230536341773341256727418777179462763043017367869438255024390966651705078565690271228162236626313519640870358976726577499711921457546321449494612008358074930154972571393221926233201707908214569445622263631145131680881658
strange = 11519395324733889428998199861620021305356608571856051121451410451257032517261285528888324473164306329355782680120640320262135517302025844260832350017955127625053351256653287330703220294568460211384842833586028123185201232184080106340230097212868897257794101622865852490355812546172336607114197297201223620901

from Crypto.Util.number import *
from gmpy2 import *
e = 65537
for i in range(10):
sq = strange + n*i
re = gmpy2.iroot(sq,2)
if re[1]:
phi = n - int(re[0])
break
d = pow(e,-1,phi)
m = pow(c,d,n)
print(long_to_bytes(m))
```

## Flag
`ENO{4_b1t_0f_ph1_4nd_a_bi1_0f_bru13_f0rc3_br3ak5_1t}`