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}
