[I thought I posted the post Anonymous is replying to to cypherpunks &
cryptography. He however seems to have followed up to coderpunks.]
Here [1] is a suggestion from Anonymous which sounds technically good,
an improvement over my approach to finding additional keys capable of
signing the message, it shows that quite plausibly one could generate
another key which could have signed the message in question.
Hope Carl Johnson can get a technical expert with enough smarts to
understand the below, and express this if it is necessary.
Adam
[1] Forwarded message from coderpunks:
======================================================================
Date: Sat, 19 Sep 1998 21:48:07 +0200
From: Anonymous
This post discusses the possibility of generating a RSA public key n, and e given a signature s on a message m creating using an unknown (unpublished) n and e. A message and signature whose validity has some bearing on a current IRS investigation is given as a target for an attack if such an attack is feasible. [...] So next we would like to solve:
s ^ e mod n = m
or in other words find e, k and n st:
s ^ e - m = k * n
In addition it has to be that n is the right length based on the "s" padding. This limits it to an 8 bit range, in this case 1024-1031 bits. There are two approaches here. First, the one you are doing: try different e values and factor s^e - m until you find one which looks like it could be a plausible k * n. The problem is that n is supposed to be the product of two large primes, and if it is, you won't be able to factor it. So you might be able to create a public key which looks reasonable, but you can't create a private key which does, one which is a multiple of two large primes. If you make n be a product of a bunch of small primes, so that you can make signatures with it, then a third party can detect this and know it is bogus. Also, this approach won't match the keyid of the original signature. Another approach is to generate an n such that the discrete logarithm is solvable mod n. Then you can solve for e in s^e = m mod n, with the base of the discrete log being s. Doing this you can match the keyid and size of n without too much difficulty. Unfortunately e will not be small; it will be about the same size as n. There are one or two keys on the public keyring which have large e's, apparently generated by hacked versions of pgp. Some people feel safer with random e than a small e. So this could perhaps be accepted. (OTOH given two keys that both sign the same message, one with a small e and one with a large one, it is obvious that the first is the legit one and the second is the cloned one.) If you know the factorization of the size of the exponentiation group mod n, and all the factors are small enough, you can solve the discrete log problem mod n. You solve the discrete log separately for each factor and then combine the results. With an RSA modulus, the group order is LCM(p-1,q-1), or equivalently (p-1)(q-1)/GCD(p-1,q-1). If you were able to solve discrete logs mod p-1 and q-1 then you could solve discrete logs mod n. Unfortunately with a 1024 bit RSA modulus it is not going to be feasible to solve 512 bit discrete logs using a reasonable amount of effort. However by using more factors in the RSA modulus it should become practical. The number of factors needed will depend on how much resources you have to work on the discrete log. Once you have your n and e you can sign other messages with the key. The n looks OK from outside because the fact that it has more than two factors is not detectable, as long as its factors are not too small. Actually there may be a way of distinguishing n's with two factors from n's with more, check into this. Also check into whether n's of this form can be factored via a p-1 factoring attack. It may be that making the discrete log easy also makes the modulus factorable.