4 ms·
Cool. Would this approach work if 'partialp' is not coming from the starting or ending bits of the targeted prime number?
by vizzah 13y ago
Cool.
Would this approach work if 'partialp' is not coming from the starting or ending bits of the targeted prime number?
- pbsd 13y agoYes. But it makes for a worse didactic example, since Sage does not support it out of the box. Imagine you know the middle 288 bits of p. Then you have to find small roots of the equation x1*2**400 + partialp + x0, which now has 2 variables x0, x1 < 2^112. This requires building a different lattice than in the single variable case, but the complexity of the attack is not very different. Also note that it doesn't have to be p or q. Bits of d, d mod (p-1), and d mod (q-1), and possibly other intermediate values of RSA computations are also usable for this.