RSA, except we are given a huge public exponent e that has the same number of bits as the modulus N. We can attack this using Wiener’s Attack. The condition for Wiener’s attack is $$ d \le \frac{1}{3} \sqrt[^4]{N}. $$ We can refer to the way that the attack works in the Cryptohack Book. Sage Implementation: from Crypto.Util.number import long_to_bytes def wiener(e, n): # Convert e/n into a continued fraction cf = continued_fraction(e/n) convergents = cf.

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$.