ElGamal
| Documentation |
#include <cryptopp/elgamal.h>
|
ElGamal is a public-key cryptosystem which is based on the Discrete Log problem and similar to Diffie-Hellman. Its one of the oldest cryptosystems available. Also see A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms by Taher ElGamal.
The Crypto++ implementation of ElGamal encryption uses non-standard padding. It may not interop well with other libraries. Crypto++ does not provide ElGamal signatures. However, the library does provide the modified ElGamal signature scheme as proposed by Nyberg and Rueppel and standardized in IEEE P1363.
ElGamal's paper and the Handbook of Applied Cryptography says the private key [math]\displaystyle{ x }[/math] is selected randomly from [math]\displaystyle{ 1,...,p-1 }[/math]. Crypto++ selects [math]\displaystyle{ x }[/math] randomly from [math]\displaystyle{ 1,...,q-1 }[/math] due to Tsiounis and Yung's On the Security of EIGamal Based Encryption. Crypto++ will load and validate a key from [math]\displaystyle{ 1,...,p-1 }[/math].
In January 2018 for the Crypto++ 6.0 release, the ASN.1 format of the public and private keys changed. The old format was a legacy format used in the 1990s. The new format is a standard encoding format based on X509PublicKey and PKCS8PrivateKey. Also see Issue 567, Remove DL_PrivateKey_GFP_OldFormat and Commit a5a684d92986.
Issue 876 revealed Crypto++ 8.2 and below used OID 1.2.840.10040.4.1 (idDSA) for ElGamal encryption keys. If you need to Load a key with OID 1.3.14.7.2.1.1 (elGamal), then use Crypto++ 8.3 or above. Also see the section OID Load Bug below for a workaround.
Issue 1059 revealed Crypto++ 8.5 and below were vulnerable to message recovery due to bad interactions with other implementations. The vulnerability happened because Crypto++ would use an estimate of work factor when selecting parameters. At Crypto++ 8.6 parameter selection was changed to use subgroup order. Also see Commit bee8e8ca6658.
Saving and Loading Keys
You can save and load keys to and from disk as follows. While a PrivateKey and Decryptor are shown, the same applies to a PubicKey and Encryptor. See Keys and Formats for a detailed discussion.
ElGamalKeys::PrivateKey privateKey1;
privateKey1.GenerateRandomWithKeySize(prng, 2048);
privateKey1.Save(FileSink("elgamal.der", true /*binary*/).Ref());
ElGamalKeys::PrivateKey privateKey2;
privateKey2.Load(FileSource("elgamal.der", true /*pump*/).Ref());
privateKey2.Validate(prng, 3);
ElGamal::Decryptor decryptor(privateKey2);
// ...
Or, you can do it on a Decryptor rather than a PrivateKey because the decryptor provides access to the private key:
ElGamalKeys::PrivateKey privateKey1;
privateKey1.GenerateRandomWithKeySize(prng, 2048);
ElGamal::Decryptor decryptor1(privateKey1);
decryptor1.AccessKey().Save(FileSink("elgamal.der", true /*binary*/).Ref());
The keys are ASN.1 encoded, so you can dump them with something like Peter Gutmann's dumpasn1:
$ ./cryptopp-elgamal-keys.exe
Generating private key. This may take some time...
$ dumpasn1 elgamal.der
0 556: SEQUENCE {
4 257: INTEGER
: 00 C0 8F 5A 29 88 82 8C 88 7D 00 AE 08 F0 37 AC
: FA F3 6B FC 4D B2 EF 5D 65 92 FD 39 98 04 C7 6D
: 6D 74 F5 FA 84 8F 56 0C DD B4 96 B2 51 81 E3 A1
: 75 F6 BE 82 46 67 92 F2 B3 EC 41 00 70 5C 45 BF
: 40 A0 2C EC 15 49 AD 92 F1 3E 4D 06 E2 89 C6 5F
: 0A 5A 88 32 3D BD 66 59 12 A1 CB 15 B1 72 FE F3
: 2D 19 DD 07 DF A8 D6 4C B8 D0 AB 22 7C F2 79 4B
: 6D 23 CE 40 EC FB DF B8 68 A4 8E 52 A9 9B 22 F1
: [ Another 129 bytes skipped ]
265 1: INTEGER 3
268 257: INTEGER
: 00 BA 4D ED 20 E8 36 AC 01 F6 5C 9C DA 62 11 BB
: E9 71 D0 AB B7 E2 D3 61 37 E2 7B 5C B3 77 2C C9
: FC DE 43 70 AE AA 5A 3C 80 0A 2E B0 FA C9 18 E5
: 1C 72 86 46 96 E9 9A 44 08 FF 43 62 95 BE D7 37
: F8 99 16 59 7D FA 3A 73 DD 0D C8 CA 19 B8 6D CA
: 8D 8E 89 52 50 4E 3A 84 B3 17 BD 71 1A 1D 38 9E
: 4A C4 04 F3 A2 1A F7 1F 34 F0 5A B9 CD B4 E2 7F
: 8C 40 18 22 58 85 14 40 E0 BF 01 2D 52 B7 69 7B
: [ Another 129 bytes skipped ]
529 29: INTEGER
: 01 61 40 24 1F 48 00 4C 35 86 0B 9D 02 8C B8 90
: B1 56 CF BD A4 75 FE E2 8E 0B B3 66 08
: }
0 warnings, 0 errors.
Public Key Encryption
The following is a sample program that encrypts a secret under a ElGamal public key and then recovers the secret using an ElGamal private key.
////////////////////////////////////////////////
// Generate keys
AutoSeededRandomPool rng;
cout << "Generating private key. This may take some time..." << endl;
ElGamal::Decryptor decryptor;
decryptor.AccessKey().GenerateRandomWithKeySize(rng, 2048);
const ElGamalKeys::PrivateKey& privateKey = decryptor.AccessKey();
ElGamal::Encryptor encryptor(decryptor);
const PublicKey& publicKey = encryptor.AccessKey();
////////////////////////////////////////////////
// Secret to protect
static const int SECRET_SIZE = 16;
SecByteBlock plaintext( SECRET_SIZE );
memset( plaintext, 'A', SECRET_SIZE );
////////////////////////////////////////////////
// Encrypt
// Now that there is a concrete object, we can validate
assert( 0 != encryptor.FixedMaxPlaintextLength() );
assert( plaintext.size() <= encryptor.FixedMaxPlaintextLength() );
// Create cipher text space
size_t ecl = encryptor.CiphertextLength( plaintext.size() );
assert( 0 != ecl );
SecByteBlock ciphertext( ecl );
encryptor.Encrypt( rng, plaintext, plaintext.size(), ciphertext );
////////////////////////////////////////////////
// Decrypt
// Now that there is a concrete object, we can check sizes
assert( 0 != decryptor.FixedCiphertextLength() );
assert( ciphertext.size() <= decryptor.FixedCiphertextLength() );
// Create recovered text space
size_t dpl = decryptor.MaxPlaintextLength( ciphertext.size() );
assert( 0 != dpl );
SecByteBlock recovered( dpl );
DecodingResult result = decryptor.Decrypt( rng,
ciphertext, ciphertext.size(), recovered );
// More sanity checks
assert( result.isValidCoding );
assert( result.messageLength <= decryptor.MaxPlaintextLength( ciphertext.size() ) );
// At this point, we can set the size of the recovered
// data. Until decryption occurs (successfully), we
// only know its maximum size
recovered.resize( result.messageLength );
// SecByteBlock is overloaded for proper results below
assert( plaintext == recovered );
// If the assert fires, we won't get this far.
if(plaintext == recovered)
cout << "Recovered plain text" << endl;
else
cout << "Failed to recover plain text" << endl;
Symmetric Encryption
Crypto++ ElGamal objects offer SymmetricEncrypt and SymmetricDecrypt. The functions will encrypt and decrypt arbitrary length text under a symmertic key, and then encrypt the symmetric key under the ElGamal public key.
You can find the source code for SymmetricEncrypt and SymmetricDecrypt in elgamal.h.
ElGamal Signatures
There is no implementation of ElGamal signatures as proposed by Taher ElGamal. Rather, the Crypto++ library provides the modified ElGamal signature scheme as proposed by Nyberg and Rueppel and standardized in IEEE P1363. From the Readme.txt under the Crypto++ 3.0 changes:
Renamed ElGamalSignature to NR and changed it to track IEEE P1363
If you need the original ElGamal signature scheme, then you should download it from an archive.
OID Load Bug
Crypto++ 8.2 and below used the OID for the DSA algorithm for ElGamal keys. Crypto++ 8.3 and above are OK. The problem affected loading and saving ElGamal keys. Also see Issue 876, ElGamal encryption key Load and BERDecodeErr.
If you are using Crypto++ 8.2 or below then you can load an ElGamal public key with either OID using the code below. The code requires Commits b80693d5322a, 29e3818fd222, 3d96234038b5 and a2c06c35b84f.
#include "cryptlib.h"
#include "elgamal.h"
#include "filters.h"
#include "files.h"
#include "osrng.h"
#include "base64.h"
#include "oids.h"
#include "asn.h"
#include <iostream>
#include <string>
void LoadElGamalPublicKey(CryptoPP::BufferedTransformation& bt,
CryptoPP::ElGamal::PublicKey& key)
{
using namespace CryptoPP;
Integer v1, v2, v3, v4;
bool parametersPresent;
BERSequenceDecoder subjectPublicKeyInfo(bt);
BERSequenceDecoder algorithm(subjectPublicKeyInfo);
OID oid; // Check for old and new OID here.
oid.BERDecode(algorithm);
if (oid != ASN1::id_dsa() && oid != ASN1::elGamal())
throw BERDecodeErr();
parametersPresent = !algorithm.EndReached();
if (parametersPresent)
{
BERSequenceDecoder params(algorithm);
v1.BERDecode(params);
v2.BERDecode(params);
parametersPresent = !params.EndReached();
if (parametersPresent)
v3.BERDecode(params);
else
v3=v2, v2=(v1-1)/2;
params.MessageEnd();
}
algorithm.MessageEnd();
BERSequenceDecoder subjectPublicKey(subjectPublicKeyInfo, BIT_STRING);
subjectPublicKey.CheckByte(0); // unused bits
parametersPresent = !subjectPublicKey.EndReached();
if (parametersPresent)
v4.BERDecode(subjectPublicKey);
subjectPublicKey.MessageEnd();
subjectPublicKeyInfo.MessageEnd();
key.AccessGroupParameters().Initialize(v1, v2, v3);
key.SetPublicElement(v4);
}
int main(void)
{
using namespace CryptoPP;
AutoSeededRandomPool prng;
const std::string encodedPublicKey =
"MHYwTwYGKw4HAgEBMEUCIQDebUvQDd9UPMmD27BJ"
"ovZSIgWfexL0SWkfJQPMLsJvMwIgDy/kEthwO6Q+"
"L8XHnzumnEKs+txH8QkQD+M/8u82ql0DIwACIAY6"
"rfW+BTcRZ9QAJovgoB8DgNLJ8ocqOeF4nEBB0DHH";
StringSource decodedPublicKey(encodedPublicKey, true, new Base64Decoder);
ElGamal::Encryptor encryptor;
ElGamal::PublicKey& publicKey = encryptor.AccessKey();
LoadElGamalPublicKey(decodedPublicKey, publicKey);
if (publicKey.Validate(prng, 3))
std::cout << "Public key is valid" << std::endl;
else
std::cout << "Public key is not valid" << std::endl;
// Key has been loaded with either OID. The in-memory key uses
// the ElGamal OID. Now save the key with the ElGamal OID.
publicKey.Save(FileSink("converted-key.der").Ref());
return 0;
}
Downloads
cryptopp-elgamal.zip - Demonstrates ElGamal public key encryption.
cryptopp-elgamal-keys.zip - Demonstrates loading and saving ElGamal private keys.