Rating:
We discovered that Primes generated by the getPrimes method in the challenge Always generates primes that are symmetric around one of the modular square root of N modulo 2^1024.
We know that N = pq --> N = (a+b)(a-b) <=> N = a^2 - b^2 from fermat's factorization method Thus, b^2 = a^2 - N.
The choosen root shall always satisfy the condition root^2 > N.
Thus, we can have a = root, and b as the deviation from a to give p and q Thus, b = sqrt(a^2 - N) given (a^2 - N) is a perfect square and we get p, q as a+b, a-b
def cracker(N, root):
bsquare = root**2 - N
if bsquare < 0:
return 0, 0
b = gmpy2.sqrt(root**2 - N)
if int(b)**2 != int(bsquare):
return 0, 0
p = int(root + b)
q = int(root - b)
return p, q
ans = getRoot(N)
p, q = cracker(N, ans)
This worked for every N=pq I generated. but It failed on the N specified. The reason was that the condition root*2 > N was not met for any modulo square roots. The information of LSB was preserved in the roots but the information of MSB was lacking. So to fix this, I tried using bytes from the normal square root of N (which contains lots of MSBs) and bytes of one of the modulo square roots of N (which contains lots of LSBs), combining to give a 'pseudoRoot'. But using this root apparently worked!
def getPartialRoot(N, root, nr_bytes = 32):
Nroot = int(gmpy2.sqrt(N)).to_bytes(128, 'big')
root = root.to_bytes(128, 'big')
newRoot = eval('0x' + Nroot[:nr_bytes].hex() + root[nr_bytes:].hex())
return newRoot
def solver(N, nr_bytes=32):
ans = getRoot(N)
if ans == 0:
# No proper roots were found, lets use a random root
possiblePartials = [int(i) for i in prime_mod_sqrt(gmpy2.mpz(N%2**2048), 2, 1024)]
for root in possiblePartials:
root = getPartialRoot(N, root, nr_bytes)
print("Using Partial Root: ", root)
p, q = cracker(N, root)
if p * q == N:
print("Root FOund!!!!", hex(p), hex(q))
return p, q
else:
p, q = cracker(N, ans)
if p * q == N:
print("Root FOund!!!!", hex(p), hex(q))
return p, q
N = 0xf7e6ddd1f49d9f875904d1280c675e0e03f4a02e2bec6ca62a2819d521441b727d313ec1b5f855e3f2a69516a3fea4e953435cbf7ac64062dd97157b6342912b7667b190fad36d54e378fede2a7a6d4cc801f1bc93159e405dd6d496bf6a11f04fdc04b842a84238cc3f677af67fa307b2b064a06d60f5a3d440c4cfffa4189e843602ba6f440a70668e071a9f18badffb11ed5cdfa6b49413cf4fa88b114f018eb0bba118f19dea2c08f4393b153bcbaf03ec86e2bab8f06e3c45acb6cd8d497062f5fdf19f73084a3a793fa20757178a546de902541dde7ff6f81de61a9e692145a793896a8726da7955dab9fc0668d3cfc55cd7a2d1d8b631f88cf5259ba1
c = 0xf177639388156bd71b533d3934016cc76342efae0739cb317eb9235cdb97ae50b1aa097f16686d0e171dccc4ec2c3747f9fbaba4794ee057964734835400194fc2ffa68a5c6250d49abb68a9e540b3d8dc515682f1cd61f46352efc8cc4a1fe1d975c66b1d53f6b5ff25fbac9fa09ef7a3d7e93e2a53f9c1bc1db30eed92a30586388cfef4d68516a8fdebe5ebf9c7b483718437fcf8693acd3118544249b6e62d30afa7def37aecf4da999c1e2b686ca9caca1b84503b8794273381b51d06d0dfb9c19125ce30e67a8cf72321ca8c50a481e4b96bbbc5b8932e8d5a32fa040c3e29ced4c8bf3541e846f832a7f9406d263a592c0a9bce88be6aed043a9867a7
p, q = solver(N)
We got the output:
p = 0xfbeb1a7886ef44622066fa094ac36e67bae3ae428725ae40b33b4360f16d70ab1ab25e6ece7bdc51014e2e1a816cc3b16572d8d8aace175126f92981b765af06c6a719d16cdb83f4f9b1df22a37e6b5ddf4443a736d33190bd7f72b400829118b5bc520817f4210dbcefb930c1f5cce6c9fc9e3a903118b0a838cec76a090eaf
q = 0xfbeb1a7886ef44622066fa094ac36e67bae3ae428725ae40b33b4360f15502329379f55582e4fed5b5db1092155a566973adb60112301d087e794845d3fc0cce57e015acce21d2e86a8ee8cea59239dddf4443a736d33190bd7f72b400829118b5bc520817f4210dbcefb930c1f5cce6c9fc9e3a903118b0a838cec76a090eaf
And thus we decrypted the message as
Here is the message: CTF-BR{w3_n33d_more_resources_for_th3_0mni_pr0j3ct}\n
