Long challenge name, but short story. We are given an article at this link, outlining the difficulties in generating RSA keys such that there are no two public keys using the same prime. Because if that’s the case, one can very efficiently recover the factorisation by doing Euclid’s Algorithm, which runs in polynomial time (and thus much faster compared to factorising), to obtain one of the two primes used in the modulus....
I hate recursion depths. Sage on Windows sucks at configuring anything related to this. The challenge gives a peculiar way of generating primes 1 2 3 4 5 6 7 def get_complex_prime(): D = 427 while True: s = random.randint(2 ** 1020, 2 ** 1021 - 1) tmp = D * s ** 2 + 1 if tmp % 4 == 0 and isPrime((tmp // 4)): return tmp // 4 And given the name of the challenge, we are pretty sure that this leads to a vulnerability....
The primes are generated using the primorial and the sieve. This is known to be ROCA, the vulnerability CVE-2017-15361. More details can be found at this link. This article is also a great start for understanding a bit of Coppersmith-Howgrave method for finding roots of polynomial. Again, an unintended solution is the fact that we can use FactorDB for a quick hack at the factorisation. Python Implementation: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 from Crypto....
From the code, we can observe that the way that the primes are generated is a bit weird - the primes are very close to each other. This is a very classic problem which happens in real life - some RSA modulus is cracked because of the distance of the primes being too small. The code opens up a vector for an attack - the Fermat’s factorization method when the prime difference is small....
The primes used for the modulus N is of the form 2 ^ x - 1. Such primes are called Mersenne’s primes, named after French mathematician Marin Mersenne. A quick hack for factorisation is to lookup FactorDB, as I assume the primes are studied extensively. The result from FactorDB shows two primes $2^{2203}-1$ and $2^{2281}-1$ Another solution involves a bit of math. Suppose the two primes used are $2 ^ a - 1$ and $2 ^ b - 1$, and $a \leq b$....