Rating:
# Klepto (crypto, 932p, 12 solved)
In the task we get some [code](https://raw.githubusercontent.com/TFNS/writeups/master/2020-04-25-IJCTF/klepto/klepto.py) and [results](https://raw.githubusercontent.com/TFNS/writeups/master/2020-04-25-IJCTF/klepto/enc).
Result is just RSA public key and ciphertext.
The goal is to analyse the key generation logic and break the public key.
## Solution
The generation code might look complex, but most of it is just primarity-check, so we can skip that entirely.
The only useful part is:
```python
IV = 5326453656607417485924926839199132413931736025515611536784196637666048763966950827721156230379191350953055349475955277628710716247141676818146987326676993279104387449130750616051134331541820233198166403132059774303658296195227464112071213601114885150668492425205790070658813071773332779327555516353982732641; seed = 0; temp = [0, 0]; key = 0
while(key != 2):
if key == 0:
seed = getrandbits(1024) | (2 ** 1023 + 1)
seed_ = seed ^ IV
n = seed_ << 1024 | getrandbits(1024)
seed = n//seed | 1
while(1):
seed += 2;
## primarity checks
temp[key] = seed
return(temp[0], temp[1])
```
Let's look closely at:
```python
seed_ = seed ^ IV
n = seed_ << 1024 | getrandbits(1024)
seed = n//seed | 1
```
Let's rewrite this:
```
s2 = seed ^ IV
n = s2 * 2**1024 + r
almost_p = n//seed
p = almost_p + small_value
```
Now:
```
almost_p = n//seed
almost_p = (s2 * 2**1024 + r)//seed
almost_p = ((seed ^ IV) * 2**1024 + r)//seed
almost_p = ((seed ^ IV) * 2**1024)//seed + r//seed
almost_p = ((seed ^ IV) * 2**1024)//seed + very_small
p = 2**1024 * (seed ^ IV)//seed + very_small + small_value
p ~= 2**1024 * (seed ^ IV)//seed
```
The same logic follows for `q`, but in this case `seed` is our `p`:
```
p ~= 2**1024 * (seed ^ IV)//seed
q ~= 2**1024 * (p ^ IV)//p
p*q ~= p * (2**1024 * (p ^ IV)//p)
p*q ~= 2**1024 * (p ^ IV)
p*q^IV ~= 2**1024 * p
p ~= ((p*q)^IV)/2**1024
```
There were all those small parts we skipped here, so actual `p` might be a bit smaller/larger, but we easily iterate over those values:
```python
iv = 5326453656607417485924926839199132413931736025515611536784196637666048763966950827721156230379191350953055349475955277628710716247141676818146987326676993279104387449130750616051134331541820233198166403132059774303658296195227464112071213601114885150668492425205790070658813071773332779327555516353982732641
n = 31492593980972292127624243962770751972791586997559415119664067126352874455354554396825959492520866585425367347800693358768073355393830644370233119742738920691048174984688259647179867604016694194959178874017481204930806636137689428300906890690499460758884820784037362414109026624345965004388036791265355660637942956892135275111144499770662995342441666665963192321379766221844532877240853120099814348371659810248827790798567539193378235283620829716728221866131016495050641120781696656274043778657558111564011476899021178414456560902915167861941065608670797745473745460370154604158882840935421329890924498705681322154941
p_approx = (n >> 1024) ^ iv
print(hex(p_approx))
r = 5000
potential_p = p_approx - r
for i in range(2 * r):
if n % potential_p == 0:
print(hex(potential_p))
break
potential_p += 1
p = potential_p
q = n / p
assert gmpy2.is_prime(p)
assert gmpy2.is_prime(q)
```
This way we recover `p` and `q` and can do:
```python
d = modinv(65537, (p - 1) * (q - 1))
print(rsa_printable(31105943135542175872131854877903463541878591074483146885600982339634188894256348597314413875362761608401326213641601058666720123544299104566877513595233611507482373096711246358592143276357334231127437090663716106190589907211171164566820101003469295773837109380815526746746678580390779170877213166506863176846508933485178812858166031517243792487958635017917996626849408595921536238471169975280762677305759764602707285224588771643832335444552739959904673158661424651074772864245589406308229908379716500604590198490474257870603210120239125184805345188782082520055749851184516545898673495570079185198108523819932428027921,d, n))
```
And get: `IJCTF{kl3pt0_n0th1n6_uP_mY_s133v3_numb3r5}`
