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

[Peter Gutmann]

Adam Back <adam at cypherspace.org> writes:
>On Mon, Jan 20, 2003 at 09:08:31PM -0500, Radia Perlman wrote:
>>[...] I was going to suggest something similar to what David Wagner
>>suggested, but with Scott telling Alice the modulus size and the
>>*high* order 64 bits (with the top bit constrained to be 1). I can
>>see how Alice can easily generate two primes whose product will have
>>that *high* order part, but it seems hard to generate an RSA modulus
>>with a specific *low* order 64 bits.
>
>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 (which
admittedly isn't a problem in this case because you're not trying to hide its
presence).  More challenging though are ways of embedding a fixed pattern that
isn't (easily) detectable, a la various ways of leaking information in the
public key such as SETUP attacks.

Peter.

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