Extract numbers from a key

[Hubert Kario]

On Sunday 14 August 2011 13:26:26 Peter Lebbing wrote:
> 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.

>From what I learned, RSA cracking is basically an exaustive search. 
If your "prime" is composite, it is at most half as long as a real prime would 
be.

So, instead of a ~1024 bit prime you have a ~512 bit prime, which are tryvial 
to crack.

Mind that I learned RSA 5 years ago during 2 hours of a 20 hours course on 
cryptography, so it may be even easier to crack encryption using composite 
numbers.

Regards,
-- 
Hubert Kario
QBS - Quality Business Software
02-656 Warszawa, ul. Ksawerów 30/85
tel. +48 (22) 646-61-51, 646-74-24
www.qbs.com.pl