This is the essence of the "DEADBEEF" attack on PGP. PGP used the least significant bits of the modulus as the key ID. If you want to create a key with a particular key ID, you just hack the code so that it checks for primes that end in things which will multiply together to yeild the desired answer; the easy case, of course, is 0x00000001 and 0xDEADBEEF, which is what was done to create the Prime Rib Lovers' key as a proof of concept[*]. There does not appear to be any significant erosion of security, although I'm not sure if anyone's thought too seriously about that specific case either.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.
regards,
Greg.
[*] I note that there are three keys on the us.pgp.net server with 0xDEADBEEF as their key ID (including the one mentioned above), and one of them is even a DSA key! I can only assume this was brute forced through the hash function.
Greg Rose INTERNET: [EMAIL PROTECTED]
Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199
Level 3, 230 Victoria Road, http://people.qualcomm.com/ggr/
Gladesville NSW 2111 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
