Re: OT: help generating gpg key with prescribed key ID

[Georgi Guninski <guninski () guninski com>]

On Wed, Sep 21, 2011 at 01:08:59PM -0400, Valdis.Kletnieks () vt edu 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/