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 _______________________________________________ Gnupg-users mailing list Gnupg-users@gnupg.org http://lists.gnupg.org/mailman/listinfo/gnupg-users