Tags: factoring rsa 

Rating: 5.0

# factorize
```
c: 17830167351685057470426148820703481112309475954806278304600862043185650439097181747043204885329525211579732614665322698426329449125482709124139851522121862053345527979419420678255168453521857375994190985370640433256068675028575470040533677286141917358212661540266638008376296359267047685745805295747215450691069703625474047825597597912415099008745060616375313170031232301933185011013735135370715444443319033139774851324477224585336813629117088332254309481591751292335835747491446904471032096338134760865724230819823010046719914443703839473237372520085899409816981311851296947867647723573368447922606495085341947385255
n: 23135514747783882716888676812295359006102435689848260501709475114767217528965364658403027664227615593085036290166289063788272776788638764660757735264077730982726873368488789034079040049824603517615442321955626164064763328102556475952363475005967968681746619179641519183612638784244197749344305359692751832455587854243160406582696594311842565272623730709252650625846680194953309748453515876633303858147298846454105907265186127420148343526253775550105897136275826705375222242565865228645214598819541187583028360400160631947584202826991980657718853446368090891391744347723951620641492388205471242788631833531394634945663
```
Files:

- [factorize.py](factorize.py)

As you can see is a typical **RSA question**

Look at the source:
```py
def genPrimes(size):
base = random.getrandbits(size // 2) << size // 2
base = base | (1 << 1023) | (1 << 1022) | 1
while True:
temp = base | random.getrandbits(size // 2)
if isPrime(temp):
p = temp
break
while True:
temp = base | random.getrandbits(size // 2)
if isPrime(temp):
q = temp
break
return (p, q)
```

After I look though the code, realise the top 512 bits of `p` and `q` are guarantee the same!

By running this code to confirm the vuln:
```py
p,q = genPrimes(1024)
assert bin(p)[2:514] == bin(q)[2:514]
```

If top 512 bits are the same, means `p`,`q` are quite close so `p*q` can be factorize very fast

I using [Fermat's factorization method](https://en.wikipedia.org/wiki/Fermat%27s_factorization_method) to factorize the `n`

[Full python script](solve.py)

```py
import gmpy2
from Crypto.Util.number import *

def fermat_factor(n):
assert n % 2 != 0

a = gmpy2.isqrt(n)
b2 = gmpy2.square(a) - n

for i in range(100000000):
a += 1
b2 = gmpy2.square(a) - n

if gmpy2.is_square(b2):
p = a + gmpy2.isqrt(b2)
q = a - gmpy2.isqrt(b2)

return True,(int(p), int(q))
return False,()

n = 23135514747783882716888676812295359006102435689848260501709475114767217528965364658403027664227615593085036290166289063788272776788638764660757735264077730982726873368488789034079040049824603517615442321955626164064763328102556475952363475005967968681746619179641519183612638784244197749344305359692751832455587854243160406582696594311842565272623730709252650625846680194953309748453515876633303858147298846454105907265186127420148343526253775550105897136275826705375222242565865228645214598819541187583028360400160631947584202826991980657718853446368090891391744347723951620641492388205471242788631833531394634945663
e = 0x10001
c = 17830167351685057470426148820703481112309475954806278304600862043185650439097181747043204885329525211579732614665322698426329449125482709124139851522121862053345527979419420678255168453521857375994190985370640433256068675028575470040533677286141917358212661540266638008376296359267047685745805295747215450691069703625474047825597597912415099008745060616375313170031232301933185011013735135370715444443319033139774851324477224585336813629117088332254309481591751292335835747491446904471032096338134760865724230819823010046719914443703839473237372520085899409816981311851296947867647723573368447922606495085341947385255

can_factor ,(p, q) = fermat_factor(n)
if can_factor:
phi = (p-1)*(q-1)
d = inverse(e,phi)
m = pow(c,d,n)
print(long_to_bytes(m))

# flag{[email protected]_1t4536}
```

That it! Easy RSA challenge!

## Alternative solution
You also can use this [Integer Factorize website](https://www.alpertron.com.ar/ECM.HTM) to factorize large numbers!

## Flag
> flag{[email protected]_1t4536}

Original writeup (https://github.com/Hong5489/0x41414141-CTF/tree/main/factorize).