In the paper titled Remote Timing Attacks are Practical, the authors mention the following:
Initially our guess g of q lies between 25122512 (i.e. 2log2(N/2)2log2(N/2)) and 25112511 (i.e. 2log2(N/2)−12log2(N/2)−1). We then time the decryption of all possible combinations of the top few bits (typically 2-3). When plotted, the decryption times will show two peaks: one for q and one for p. We pick the values that bound the first peak, which in OpenSSL will always be q.
I don't understand the following:
- Does the initial guess of
g start from an arbitrary range? - What's the rationale behind trying out top 2-3 bits?
- What will the remaining bits be in this case?
