deadbeef attack was choose low order RSA bits (Re: Key Pair Agreement?)

[Adam Back]

On Wed, Jan 22, 2003 at 03:18:34PM +1300, Peter Gutmann wrote:
> >One cheap way the low order 64 bits can be set is to set the low order bits
> >of p to the target bitset and the low order bits of q to ...00001 (63 0s and
> >one 1 in binary), and then to increase the stride of candidate values in the
> >prime sieve to be eg 2^64.
> 
> That way's trivially detectable by inspection of the private key
> [...].  More challenging though are ways of embedding a fixed
> pattern that isn't (easily) detectable, 

An alternate method which doesn't leave such an obvious pattern in the
private key would be to find a factorization of x the target string
other than using ...0001 and x, to use p' and q' being equal length
factors of x = p'.q'.  Or if there aren't any then equal length
factorizations of r||x where r is some number of random bits.

Adam

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com