[12358] in cryptography@c2.net mail archive
Re: deadbeef attack was choose low order RSA bits (Re: Key Pair Agreement?)
daemon@ATHENA.MIT.EDU (Adam Back)
Thu Jan 23 15:05:37 2003
X-Original-To: cryptography@wasabisystems.com
X-Original-To: cryptography@wasabisystems.com
Date: Thu, 23 Jan 2003 18:01:52 +0000
From: Adam Back <adam@cypherspace.org>
To: Peter Gutmann <pgut001@cs.auckland.ac.nz>
Cc: Radia.Perlman@sun.com, cryptography@wasabisystems.com
In-Reply-To: <200301220218.h0M2IYf18632@medusa01.cs.auckland.ac.nz>; from pgut001@cs.auckland.ac.nz on Wed, Jan 22, 2003 at 03:18:34PM +1300
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@wasabisystems.com
