Re: [Full-disclosure] OT: help generating gpg key with prescribed key ID

[Georgi Guninski <guninski@xxxxxxxxxxxx>]

On Wed, Sep 21, 2011 at 01:08:59PM -0400, Valdis.Kletnieks@xxxxxx wrote:
> On Wed, 21 Sep 2011 16:21:24 +0300, Georgi Guninski said:
> > for a fishing expedition i need to generate a gpg key with prescribed key 
> > ID.
> > 
> > is there a relatively easy way to do this?
> 
> It's intentionally difficult.  It *is* possible to generate a key to match a 
> given key ID,
> or even match a given key fingerprint - however, the resulting key will have 
> odd values
> for key length (for instance, it may be a 25-bit DSA key or 1,343,342 bit RSA 
> or other
> wild stuff).  
> 
> http://www.pgp.net/pgpnet/pgp-faq/pgp-faq-keys.html#key-public-key-forgery
> 
> The tricky part will be getting the person to accept that the key is from who 
> it
> purports to be - this will probably involve some social engineering, 
> especially if
> the target already *has* a trusted key from the person you're trying to forge.


thanks Valdis, very useful references!

just in case this question show up in searches:

in gpg 1.4.10 it is easy to generate RSA keys with prescribed key ID of 
arbitrary length >= 320.
if the packet version is set to 3, the key ID is just the RSA n \mod 2^64.

the algorithm is:
set the lowest 64 bits to the desired ID.
generate random high bits until you fully factor $n$ using trial division or EC.
number theory is on your side.
a disadvantage is that the key will be weak, but almost sure this can be fixed 
with more advanced theory.


-- 
joro

_______________________________________________
Full-Disclosure - We believe in it.
Charter: http://lists.grok.org.uk/full-disclosure-charter.html
Hosted and sponsored by Secunia - http://secunia.com/