Same problem as the previous similar name challenge. But there is a twist this time. There is a check of (3*d)**4 > N, which effectively renders Weiner’s attack useless. We can use Boneh-Durfee Attack. Awesome script at this link. The Github repo contains some useful scripts. Boneh-Durfee Attack limit: $$ d < N ^ {0.292} $$ From the retrieved d, we can easily recover the plaintext. Seems like there is another solution by aloof, which I am too lazy to type so here’s the screenshot of the math involved.

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: from Crypto.PublicKey import RSA 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$.

We need to recover the plaintext from the incorrectly generated RSA parameters, in this case, e = 16 and the modulo n is a prime. As the public exponent and the totient of n is not coprime, this implies The first, and intended solution is to take advantage of the fact that e = 2 ^ 4, hence we only need to calculate the square root of the plaintext in the finite field four times.