On Dec 16, 9:35 pm, Atif <[email protected]> wrote: > Hey Alan, wanted to see if you had any luck tracking down the issue. So, there appears to be two issues here.
First is cyclic subgroup attacks due to Schnorr (also known as confinement attacks). That means we don't necessarily have to choose p = 2q + 1, but there is a limit on what we chose. For example, we can chose p = 3q + 1 or p = 4q + 1. p = 2q + 1 just happens to be the hardest case for the known attacks by generating the largest subgroup. Also see the Pohlig-Hellman algorithm which attacks the subgroup's structure. In the past, I did some experimenting with the general form of p = qr + 1. I know Crypto++ will take the generalized parameters, and the parameters will validate. See "Details Lost in Generation and Initialization" at http://www.cryptopp.com/wiki/Diffie-Hellman. Second is the choice of a "non-safe" or "non-strong" primes. We know that some algorithms, such a Pollard's Rho, runs in time proportional q - 1 (in, for example, p = 2q + 1). So I'm skeptical about PGP's choice or selection of parameters. Finally, a quick search of Google and Google Scholar did not turn up ElGamal key requirements with non-safe primes. This is not surprising, since we generally choose safe parameters. In the end, I would probably file a bug report with PGP and have the maintainers go on record with their rationale behind the choice of parameters. It could be they have read a paper that states its not necessary to use safe and strong primes, or its OK to have q - 1 non- prime. Ask them to provide a reference. Jeff > On Thursday, May 17, 2012 11:25:00 AM UTC-4, Alan Rushforth wrote: > > > Hello, > > > I have generated a key pair using GnuPG and am trying to use Crypto++ to > > decrypt an Elgamal encrypted PGP message with the private key. I have > > extracted the p,g and x values from the private key and can use these to > > encrypt and decrypt arbitrary strings. However when ever I try to decrypt > > my encrypted PGP session key it fails. I get a DL_BadElement element > > exception. My problem is exactly the same as the one mentioned in the > > following post from 2003 but it doesn't look like he ever got an answer. > > >https://groups.google.com/d/topic/cryptopp-users/_NJoj8Dqtws/discussion > > > I am using Crypto++ 5.6.1. I have run crypttest and all the tests pass. I > > have also put the key and the message throughhttp://www.pgpdump.net/ > > (it was only a test key) and have compared all the values to ensure I am > > extracting them correctly. The bit that fails seems to be the jacobi test > > on the first half of my cipher text and the modulus. It complains that it > > is not a quadratic residue. As I understand it this means that it isnt a > > very good key. It seems unlikely (but not impossible) that GnuPG would > > select a poor key but even if this is the case why does it stop me > > decrypting it? > > > I have tried validating the keys and they pass up to level 1 but fail on 2 > > and 3 as it says my q value (p/2) is not prime. Again it would seem odd for > > GnuPG to have selected a bad key. Is there another way that I can verify > > the key? > > > Any help on this would be greatly appreciated as I have been banging my > > head against it for days now. > > > And just to prempt the inevitable; i do have to use Elgamal :) > > > Thanks, > > Alan. -- You received this message because you are subscribed to the "Crypto++ Users" Google Group. To unsubscribe, send an email to [email protected]. More information about Crypto++ and this group is available at http://www.cryptopp.com.
