# factorize```c: 17830167351685057470426148820703481112309475954806278304600862043185650439097181747043204885329525211579732614665322698426329449125482709124139851522121862053345527979419420678255168453521857375994190985370640433256068675028575470040533677286141917358212661540266638008376296359267047685745805295747215450691069703625474047825597597912415099008745060616375313170031232301933185011013735135370715444443319033139774851324477224585336813629117088332254309481591751292335835747491446904471032096338134760865724230819823010046719914443703839473237372520085899409816981311851296947867647723573368447922606495085341947385255n: 23135514747783882716888676812295359006102435689848260501709475114767217528965364658403027664227615593085036290166289063788272776788638764660757735264077730982726873368488789034079040049824603517615442321955626164064763328102556475952363475005967968681746619179641519183612638784244197749344305359692751832455587854243160406582696594311842565272623730709252650625846680194953309748453515876633303858147298846454105907265186127420148343526253775550105897136275826705375222242565865228645214598819541187583028360400160631947584202826991980657718853446368090891391744347723951620641492388205471242788631833531394634945663```Files:
- [factorize.py](factorize.py)
As you can see is a typical **RSA question**
Look at the source:```pydef 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:```pyp,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)
```pyimport gmpy2from 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 = 23135514747783882716888676812295359006102435689848260501709475114767217528965364658403027664227615593085036290166289063788272776788638764660757735264077730982726873368488789034079040049824603517615442321955626164064763328102556475952363475005967968681746619179641519183612638784244197749344305359692751832455587854243160406582696594311842565272623730709252650625846680194953309748453515876633303858147298846454105907265186127420148343526253775550105897136275826705375222242565865228645214598819541187583028360400160631947584202826991980657718853446368090891391744347723951620641492388205471242788631833531394634945663e = 0x10001c = 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{just_g0tta_f@ct0rize_1t4536}```
That it! Easy RSA challenge!
## Alternative solutionYou also can use this [Integer Factorize website](https://www.alpertron.com.ar/ECM.HTM) to factorize large numbers!
## Flag> flag{just_g0tta_f@ct0rize_1t4536}