Extract numbers from a key

[Peter Lebbing]

On 04/08/11 17:14, Peter Lebbing wrote:
> On 03/08/11 12:43, Sébastien wrote:
>> I know that gpg is an hybrid system. I want to know these numbers to check 
>> with a mathematica-like program that numbers supposed to be primes are 
>> actually real prime numbers.
> 
> And suppose GnuPG accidentally picked a composite. What would be the security
> implications of that? I am supposing that the adversary does *not* know your key
> isn't actually based on 2 primes.

I still think this is an interesting academic question. Does anybody have some
insight to offer on this?

The conditions as I envision them are:

- An OpenPGP implementation uses heuristic methods to determine if the numbers
used in key generation are prime. I.e., there is an (extremely small) chance of
accidentally picking a composite number.
- The adversary doesn't know whether the implementation has a higher than normal
chance of accidentally picking composites.
- The adversary is trying to solve the RSA problem for a key where key
generation accidentally used a composite where a prime was intended.

Will the adversary likely have a better chance of solving the RSA problem
because key generation went "wrong"?

The reason for this scenario, is that I suppose that GnuPG uses heuristics as
mentioned above, and that there are no known weaknesses in these heuristics.
That is, either they have no weaknesses, or nobody has found them yet. So you
can't use knowledge of the weaknesses in your attack.

Again, this is purely academic. I won't push for GnuPG to adopt deterministic
PRIME algorithms or something :). I just wonder.

Greets,

Peter.

-- 
I use the GNU Privacy Guard (GnuPG) in combination with Enigmail.
You can send me encrypted mail if you want some privacy.
My key is available at http://wwwhome.cs.utwente.nl/~lebbing/pubkey.txt