Extract numbers from a key

[Peter Lebbing]

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.

As far as I can see, there would be a few messages that would be corrupted when
encrypted to this key, because it turns out the message is not co-prime with a
factor of the key. If this is a possibility in practice, I don't know. It would
depend on the padding of the session key and which numbers that can lead to for
the RSA operation. But I don't really know if it becomes easier to extract the
private part from the public key, as long as the attacker does not know a
composite was used.

If it is known that a certain piece of software often accidentally produces
composites, you could account for this in your cracking software and indeed gain
an advantage, I think.

I'm even thinking it might be *harder* to factorize the public key because the
attacker expects a number with two prime factors and dismisses the possibility
of one of the "factors" being composite ;D. This is somewhat tongue-in-cheeck,
but it might have a grain of truth to it.

By the way, on a related subject: I suppose the padding scheme is chosen in such
a way that the message is never a multiple of one of the primes of the key?
Because I suppose in that case the message would be corrupted, as it is not
co-prime with n?

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