Tags: rsa
Rating: 1.7
tl;dr
We have a prime `a` and `2` random numbers `r1,r2` less than `a` such that `2r1a+1` and `2r2a+1` are primes. These primes are used to construct the RSA key.
We can control the top `80` bytes of `a` and only the lowest `2` bytes remain unknown. Since `N%(2a)=1`, this allows us to easily brute force `a`. Alternatively, we have an extremely good approxmation of `a` since out of `64` bytes, only `2` are unknown, so we can run coppersmith with `N-1` as the modulus, or even better, factor out the small primes form `N-1` before running coppersmith.
Now that we have recovered `a`, notice that `N=4a^2r1r2+2a(r1+r2)+1` with `r1
