# 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:
```pythonIV = 5326453656607417485924926839199132413931736025515611536784196637666048763966950827721156230379191350953055349475955277628710716247141676818146987326676993279104387449130750616051134331541820233198166403132059774303658296195227464112071213601114885150668492425205790070658813071773332779327555516353982732641; seed = 0; temp = [0, 0]; key = 0while(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] = seedreturn(temp[0], temp[1])```
Let's look closely at:
```pythonseed_ = seed ^ IVn = seed_ << 1024 | getrandbits(1024)seed = n//seed | 1```
Let's rewrite this:
```s2 = seed ^ IVn = s2 * 2**1024 + ralmost_p = n//seedp = almost_p + small_value```
Now:
```almost_p = n//seedalmost_p = (s2 * 2**1024 + r)//seedalmost_p = ((seed ^ IV) * 2**1024 + r)//seedalmost_p = ((seed ^ IV) * 2**1024)//seed + r//seedalmost_p = ((seed ^ IV) * 2**1024)//seed + very_smallp = 2**1024 * (seed ^ IV)//seed + very_small + small_valuep ~= 2**1024 * (seed ^ IV)//seed```
The same logic follows for `q`, but in this case `seed` is our `p`:
```p ~= 2**1024 * (seed ^ IV)//seedq ~= 2**1024 * (p ^ IV)//pp*q ~= p * (2**1024 * (p ^ IV)//p)p*q ~= 2**1024 * (p ^ IV)p*q^IV ~= 2**1024 * pp ~= ((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:
```pythoniv = 5326453656607417485924926839199132413931736025515611536784196637666048763966950827721156230379191350953055349475955277628710716247141676818146987326676993279104387449130750616051134331541820233198166403132059774303658296195227464112071213601114885150668492425205790070658813071773332779327555516353982732641n = 31492593980972292127624243962770751972791586997559415119664067126352874455354554396825959492520866585425367347800693358768073355393830644370233119742738920691048174984688259647179867604016694194959178874017481204930806636137689428300906890690499460758884820784037362414109026624345965004388036791265355660637942956892135275111144499770662995342441666665963192321379766221844532877240853120099814348371659810248827790798567539193378235283620829716728221866131016495050641120781696656274043778657558111564011476899021178414456560902915167861941065608670797745473745460370154604158882840935421329890924498705681322154941p_approx = (n >> 1024) ^ ivprint(hex(p_approx))r = 5000potential_p = p_approx - rfor i in range(2 * r):    if n % potential_p == 0:        print(hex(potential_p))        break    potential_p += 1p = potential_pq = n / passert gmpy2.is_prime(p)assert gmpy2.is_prime(q)```
This way we recover `p` and `q` and can do:
```pythond = modinv(65537, (p - 1) * (q - 1)) print(rsa_printable(31105943135542175872131854877903463541878591074483146885600982339634188894256348597314413875362761608401326213641601058666720123544299104566877513595233611507482373096711246358592143276357334231127437090663716106190589907211171164566820101003469295773837109380815526746746678580390779170877213166506863176846508933485178812858166031517243792487958635017917996626849408595921536238471169975280762677305759764602707285224588771643832335444552739959904673158661424651074772864245589406308229908379716500604590198490474257870603210120239125184805345188782082520055749851184516545898673495570079185198108523819932428027921,d, n))```
And get: `IJCTF{kl3pt0_n0th1n6_uP_mY_s133v3_numb3r5}`