Crypto++  8.6
Free C++ class library of cryptographic schemes
elgamal.h
Go to the documentation of this file.
1 // elgamal.h - originally written and placed in the public domain by Wei Dai
2 
3 /// \file elgamal.h
4 /// \brief Classes and functions for ElGamal key agreement and encryption schemes
5 
6 #ifndef CRYPTOPP_ELGAMAL_H
7 #define CRYPTOPP_ELGAMAL_H
8 
9 #include "cryptlib.h"
10 #include "modexppc.h"
11 #include "integer.h"
12 #include "gfpcrypt.h"
13 #include "pubkey.h"
14 #include "misc.h"
15 #include "oids.h"
16 #include "dsa.h"
17 #include "asn.h"
18 
19 NAMESPACE_BEGIN(CryptoPP)
20 
21 /// \brief ElGamal key agreement and encryption schemes base class
22 /// \since Crypto++ 1.0
23 class CRYPTOPP_NO_VTABLE ElGamalBase :
27 {
28 public:
29  virtual ~ElGamalBase() {}
30 
31  void Derive(const DL_GroupParameters<Integer> &groupParams, byte *derivedKey, size_t derivedLength, const Integer &agreedElement, const Integer &ephemeralPublicKey, const NameValuePairs &derivationParams) const
32  {
33  CRYPTOPP_UNUSED(groupParams); CRYPTOPP_UNUSED(ephemeralPublicKey);
34  CRYPTOPP_UNUSED(derivationParams);
35  agreedElement.Encode(derivedKey, derivedLength);
36  }
37 
38  size_t GetSymmetricKeyLength(size_t plainTextLength) const
39  {
40  CRYPTOPP_UNUSED(plainTextLength);
41  return GetGroupParameters().GetModulus().ByteCount();
42  }
43 
44  size_t GetSymmetricCiphertextLength(size_t plainTextLength) const
45  {
46  unsigned int len = GetGroupParameters().GetModulus().ByteCount();
47  if (plainTextLength <= GetMaxSymmetricPlaintextLength(len))
48  return len;
49  else
50  return 0;
51  }
52 
53  size_t GetMaxSymmetricPlaintextLength(size_t cipherTextLength) const
54  {
55  unsigned int len = GetGroupParameters().GetModulus().ByteCount();
56  CRYPTOPP_ASSERT(len >= 3);
57 
58  if (cipherTextLength == len)
59  return STDMIN(255U, len-3);
60  else
61  return 0;
62  }
63 
64  void SymmetricEncrypt(RandomNumberGenerator &rng, const byte *key, const byte *plainText, size_t plainTextLength, byte *cipherText, const NameValuePairs &parameters) const
65  {
66  CRYPTOPP_UNUSED(parameters);
67  const Integer &p = GetGroupParameters().GetModulus();
68  unsigned int modulusLen = p.ByteCount();
69 
70  SecByteBlock block(modulusLen-1);
71  rng.GenerateBlock(block, modulusLen-2-plainTextLength);
72  memcpy(block+modulusLen-2-plainTextLength, plainText, plainTextLength);
73  block[modulusLen-2] = (byte)plainTextLength;
74 
75  a_times_b_mod_c(Integer(key, modulusLen), Integer(block, modulusLen-1), p).Encode(cipherText, modulusLen);
76  }
77 
78  DecodingResult SymmetricDecrypt(const byte *key, const byte *cipherText, size_t cipherTextLength, byte *plainText, const NameValuePairs &parameters) const
79  {
80  CRYPTOPP_UNUSED(parameters);
81  const Integer &p = GetGroupParameters().GetModulus();
82  unsigned int modulusLen = p.ByteCount();
83 
84  if (cipherTextLength != modulusLen)
85  return DecodingResult();
86 
87  Integer m = a_times_b_mod_c(Integer(cipherText, modulusLen), Integer(key, modulusLen).InverseMod(p), p);
88 
89  m.Encode(plainText, 1);
90  unsigned int plainTextLength = plainText[0];
91  if (plainTextLength > GetMaxSymmetricPlaintextLength(modulusLen))
92  return DecodingResult();
93  m >>= 8;
94  m.Encode(plainText, plainTextLength);
95  return DecodingResult(plainTextLength);
96  }
97 
98  virtual const DL_GroupParameters_GFP & GetGroupParameters() const =0;
99 };
100 
101 /// \brief ElGamal key agreement and encryption schemes default implementation
102 /// \tparam BASE Base class implementation
103 /// \tparam SCHEME_OPTIONS Scheme options
104 /// \tparam KEY ElGamal key classes
105 /// \since Crypto++ 1.0
106 template <class BASE, class SCHEME_OPTIONS, class KEY>
108  public DL_ObjectImplBase<BASE, SCHEME_OPTIONS, KEY>,
109  public ElGamalBase
110 {
111 public:
112  virtual ~ElGamalObjectImpl() {}
113 
114  size_t FixedMaxPlaintextLength() const {return this->MaxPlaintextLength(FixedCiphertextLength());}
115  size_t FixedCiphertextLength() const {return this->CiphertextLength(0);}
116 
117  const DL_GroupParameters_GFP & GetGroupParameters() const {return this->GetKey().GetGroupParameters();}
118 
119  DecodingResult FixedLengthDecrypt(RandomNumberGenerator &rng, const byte *cipherText, byte *plainText) const
120  {return Decrypt(rng, cipherText, FixedCiphertextLength(), plainText);}
121 
122 protected:
123  const DL_KeyAgreementAlgorithm<Integer> & GetKeyAgreementAlgorithm() const {return *this;}
124  const DL_KeyDerivationAlgorithm<Integer> & GetKeyDerivationAlgorithm() const {return *this;}
125  const DL_SymmetricEncryptionAlgorithm & GetSymmetricEncryptionAlgorithm() const {return *this;}
126 };
127 
128 /// \brief ElGamal Public Key adapter
129 /// \tparam BASE PublicKey derived class
130 /// \details DL_PublicKey_ElGamal provides an override for GetAlgorithmID()
131 /// to utilize 1.3.14.7.2.1.1. Prior to DL_PublicKey_ElGamal, the ElGamal
132 /// keys [mistakenly] used the OID from DSA due to DL_GroupParmaters_GFP().
133 /// If you need to <tt>Load</tt> an ElGamal key with the wrong OID then
134 /// see <A HREF="https://www.cryptopp.com/wiki/ElGamal">ElGamal</A> on
135 /// the Crypto++ wiki.
136 /// \sa <A HREF="https://github.com/weidai11/cryptopp/issues/876">Issue 876</A>,
137 /// <A HREF="https://github.com/weidai11/cryptopp/issues/567">Issue 567</A>
138 /// \since Crypto++ 8.3
139 template <class BASE>
140 struct DL_PublicKey_ElGamal : public BASE
141 {
142  virtual ~DL_PublicKey_ElGamal() {}
143 
144  /// \brief Retrieves the OID of the algorithm
145  /// \return OID of the algorithm
146  /// \details DL_PrivateKey_ElGamal provides an override for GetAlgorithmID()
147  /// to utilize 1.3.14.7.2.1.1. Prior to DL_PrivateKey_ElGamal, the ElGamal
148  /// keys [mistakenly] used the OID from DSA due to DL_GroupParmaters_GFP().
149  /// If you need to <tt>Load</tt> an ElGamal key with the wrong OID then
150  /// see <A HREF="https://www.cryptopp.com/wiki/ElGamal">ElGamal</A> on
151  /// the Crypto++ wiki.
152  /// \sa <A HREF="https://github.com/weidai11/cryptopp/issues/876">Issue 876</A>,
153  /// <A HREF="https://github.com/weidai11/cryptopp/issues/567">Issue 567</A>
154  virtual OID GetAlgorithmID() const {
155  return ASN1::elGamal();
156  }
157 };
158 
159 /// \brief ElGamal Private Key adapter
160 /// \tparam BASE PrivateKey derived class
161 /// \details DL_PrivateKey_ElGamal provides an override for GetAlgorithmID()
162 /// to utilize 1.3.14.7.2.1.1. Prior to DL_PrivateKey_ElGamal, the ElGamal
163 /// keys [mistakenly] used the OID from DSA due to DL_GroupParmaters_GFP().
164 /// If you need to <tt>Load</tt> an ElGamal key with the wrong OID then
165 /// see <A HREF="https://www.cryptopp.com/wiki/ElGamal">ElGamal</A> on
166 /// the Crypto++ wiki.
167 /// \sa <A HREF="https://github.com/weidai11/cryptopp/issues/876">Issue 876</A>,
168 /// <A HREF="https://github.com/weidai11/cryptopp/issues/567">Issue 567</A>
169 /// \since Crypto++ 8.3
170 template <class BASE>
171 struct DL_PrivateKey_ElGamal : public BASE
172 {
173  virtual ~DL_PrivateKey_ElGamal() {}
174 
175  /// \brief Retrieves the OID of the algorithm
176  /// \return OID of the algorithm
177  /// \details DL_PrivateKey_ElGamal provides an override for GetAlgorithmID()
178  /// to utilize 1.3.14.7.2.1.1. Prior to DL_PrivateKey_ElGamal, the ElGamal
179  /// keys [mistakenly] used the OID from DSA due to DL_GroupParmaters_GFP().
180  /// If you need to <tt>Load</tt> an ElGamal key with the wrong OID then
181  /// see <A HREF="https://www.cryptopp.com/wiki/ElGamal">ElGamal</A> on
182  /// the Crypto++ wiki.
183  /// \sa <A HREF="https://github.com/weidai11/cryptopp/issues/876">Issue 876</A>,
184  /// <A HREF="https://github.com/weidai11/cryptopp/issues/567">Issue 567</A>
185  virtual OID GetAlgorithmID() const {
186  return ASN1::elGamal();
187  }
188 
189  /// \brief Check the key for errors
190  /// \param rng RandomNumberGenerator for objects which use randomized testing
191  /// \param level level of thoroughness
192  /// \return true if the tests succeed, false otherwise
193  /// \details There are four levels of thoroughness:
194  /// <ul>
195  /// <li>0 - using this object won't cause a crash or exception
196  /// <li>1 - this object will probably function, and encrypt, sign, other
197  /// operations correctly
198  /// <li>2 - ensure this object will function correctly, and perform
199  /// reasonable security checks
200  /// <li>3 - perform reasonable security checks, and do checks that may
201  /// take a long time
202  /// </ul>
203  /// \details Level 0 does not require a RandomNumberGenerator. A NullRNG() can
204  /// be used for level 0. Level 1 may not check for weak keys and such.
205  /// Levels 2 and 3 are recommended.
206  bool Validate(RandomNumberGenerator &rng, unsigned int level) const
207  {
208  // Validate() formerly used DL_PrivateKey_GFP implementation through
209  // inheritance. However, it would reject keys from other libraries
210  // like BouncyCastle. The failure was x < q. According to ElGamal's
211  // paper and the HAC, the private key is selected in over [1,p-1],
212  // Later Tsiounis and Yung showed the lower limit as [1,q-1] in
213  // "On the Security of EIGamal Based Encryption". As such, Crypto++
214  // will generate a key in the range [1,q-1], but accept a key
215  // in [1,p-1]. Thanks to JPM for finding the reference. Also see
216  // https://github.com/weidai11/cryptopp/commit/a5a684d92986.
217 
218  CRYPTOPP_ASSERT(this->GetAbstractGroupParameters().Validate(rng, level));
219  bool pass = this->GetAbstractGroupParameters().Validate(rng, level);
220 
221  const Integer &p = this->GetGroupParameters().GetModulus();
222  const Integer &q = this->GetAbstractGroupParameters().GetSubgroupOrder();
223  const Integer &x = this->GetPrivateExponent();
224 
225  // Changed to x < p-1 based on ElGamal's paper and the HAC.
226  CRYPTOPP_ASSERT(x.IsPositive());
227  CRYPTOPP_ASSERT(x < p-1);
228  pass = pass && x.IsPositive() && x < p-1;
229 
230  if (level >= 1)
231  {
232  // Minimum security level due to Tsiounis and Yung.
234  pass = pass && Integer::Gcd(x, q) == Integer::One();
235  }
236  return pass;
237  }
238 };
239 
240 /// \brief ElGamal key agreement and encryption schemes keys
241 /// \details ElGamalKeys provide the algorithm implementation ElGamal key
242 /// agreement and encryption schemes.
243 /// \details The ElGamalKeys class used <tt>DL_PrivateKey_GFP_OldFormat</tt>
244 /// and <tt>DL_PublicKey_GFP_OldFormat</tt> for the <tt>PrivateKey</tt> and
245 /// <tt>PublicKey</tt> from about Crypto++ 1.0 through Crypto++ 5.6.5. At
246 /// Crypto++ 6.0 the serialization format was cutover to standard PKCS8 and
247 /// X509 encodings.
248 /// \details The ElGamalKeys class [mistakenly] used the OID for DSA from
249 /// about Crypto++ 1.0 through Crypto++ 8.2. At Crypto++ 8.3 the OID was
250 /// fixed and now uses ElGamal encryption, which is 1.3.14.7.2.1.1.
251 /// If you need to <tt>Load</tt> an ElGamal key with the wrong OID then
252 /// see <A HREF="https://www.cryptopp.com/wiki/ElGamal">ElGamal</A> on
253 /// the Crypto++ wiki.
254 /// \details At Crypto++ 8.6 ElGamalKeys were changed to use DL_CryptoKeys_ElGamal
255 /// due to Issue 1069 and CVE-2021-40530. DL_CryptoKeys_ElGamal group parameters
256 /// use the subgroup order, and not an estimated work factor.
257 /// \sa <A HREF="https://github.com/weidai11/cryptopp/issues/876">Issue 876</A>,
258 /// <A HREF="https://github.com/weidai11/cryptopp/issues/567">Issue 567</A>,
259 /// <A HREF="https://github.com/weidai11/cryptopp/issues/1059">Issue 1059</A>
260 /// \since Crypto++ 1.0
262 {
263  /// \brief Implements DL_GroupParameters interface
265  /// \brief Implements DL_PrivateKey interface
267  /// \brief Implements DL_PublicKey interface
269 };
270 
271 /// \brief ElGamal encryption scheme with non-standard padding
272 /// \details ElGamal provide the algorithm implementation ElGamal key
273 /// agreement and encryption schemes.
274 /// \details The ElGamal class [mistakenly] used the OID for DSA from about
275 /// Crypto++ 1.0 through Crypto++ 8.2. At Crypto++ 8.3 the OID was fixed
276 /// and now uses ElGamal encryption, which is 1.3.14.7.2.1.1.
277 /// If you need to <tt>Load</tt> an ElGamal key with the wrong OID then
278 /// see <A HREF="https://www.cryptopp.com/wiki/ElGamal">ElGamal</A> on
279 /// the Crypto++ wiki.
280 /// \sa <A HREF="https://github.com/weidai11/cryptopp/issues/876">Issue 876</A>,
281 /// <A HREF="https://github.com/weidai11/cryptopp/issues/567">Issue 567</A>
282 /// \since Crypto++ 1.0
283 struct ElGamal
284 {
286  typedef SchemeOptions::PrivateKey PrivateKey;
287  typedef SchemeOptions::PublicKey PublicKey;
288 
289  /// \brief The algorithm name
290  /// \return the algorithm name
291  /// \details StaticAlgorithmName returns the algorithm's name as a static
292  /// member function.
293  CRYPTOPP_STATIC_CONSTEXPR const char* StaticAlgorithmName() {return "ElgamalEnc/Crypto++Padding";}
294 
295  /// \brief Implements DL_GroupParameters interface
296  typedef SchemeOptions::GroupParameters GroupParameters;
297  /// \brief Implements PK_Encryptor interface
299  /// \brief Implements PK_Encryptor interface
301 };
302 
305 
306 NAMESPACE_END
307 
308 #endif
ElGamal
ElGamal encryption scheme with non-standard padding.
Definition: elgamal.h:283
PrivateKey
Interface for private keys.
Definition: cryptlib.h:2540
EnumToType
Converts an enumeration to a type suitable for use as a template parameter.
Definition: cryptlib.h:135
ElGamal::Decryptor
PK_FinalTemplate< ElGamalObjectImpl< DL_DecryptorBase< Integer >, SchemeOptions, SchemeOptions::PrivateKey > > Decryptor
Implements PK_Encryptor interface.
Definition: elgamal.h:300
DL_CryptoSchemeOptions
Discrete Log (DL) crypto scheme options.
Definition: pubkey.h:1944
byte
unsigned char byte
8-bit unsigned datatype
Definition: config_int.h:56
ElGamalObjectImpl
ElGamal key agreement and encryption schemes default implementation.
Definition: elgamal.h:107
DL_PublicKey_ElGamal
ElGamal Public Key adapter.
Definition: elgamal.h:140
ElGamal::GroupParameters
SchemeOptions::GroupParameters GroupParameters
Implements DL_GroupParameters interface.
Definition: elgamal.h:296
DL_PrivateKey_ElGamal::GetAlgorithmID
virtual OID GetAlgorithmID() const
Retrieves the OID of the algorithm.
Definition: elgamal.h:185
SecByteBlock
SecBlock<byte> typedef.
Definition: secblock.h:1226
ElGamalKeys
ElGamal key agreement and encryption schemes keys.
Definition: elgamal.h:261
CRYPTOPP_ASSERT
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition: trap.h:68
ElGamalBase
ElGamal key agreement and encryption schemes base class.
Definition: elgamal.h:23
DL_KeyAgreementAlgorithm< Integer >
pubkey.h
This file contains helper classes/functions for implementing public key algorithms.
DL_ObjectImplBase
Discrete Log (DL) base object implementation.
Definition: pubkey.h:1956
gfpcrypt.h
Classes and functions for schemes based on Discrete Logs (DL) over GF(p)
ElGamalKeys::PrivateKey
DL_PrivateKey_ElGamal< DL_CryptoKeys_ElGamal::PrivateKey > PrivateKey
Implements DL_PrivateKey interface.
Definition: elgamal.h:266
ElGamal::StaticAlgorithmName
static const char * StaticAlgorithmName()
The algorithm name.
Definition: elgamal.h:293
DL_GroupParameters_GFP
GF(p) group parameters.
Definition: gfpcrypt.h:224
OID
Object Identifier.
Definition: asn.h:264
RandomNumberGenerator
Interface for random number generators.
Definition: cryptlib.h:1434
DL_SymmetricEncryptionAlgorithm
Interface for symmetric encryption algorithms used in DL cryptosystems.
Definition: pubkey.h:1504
Integer::ByteCount
unsigned int ByteCount() const
Determines the number of bytes required to represent the Integer.
misc.h
Utility functions for the Crypto++ library.
STDMIN
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Definition: misc.h:655
DL_KeyDerivationAlgorithm
Interface for key derivation algorithms used in DL cryptosystems.
Definition: pubkey.h:1492
dsa.h
Classes for the DSA signature algorithm.
PublicKey
Interface for public keys.
Definition: cryptlib.h:2535
DecodingResult
Returns a decoding results.
Definition: cryptlib.h:277
DL_PublicKey_ElGamal::GetAlgorithmID
virtual OID GetAlgorithmID() const
Retrieves the OID of the algorithm.
Definition: elgamal.h:154
asn.h
Classes and functions for working with ANS.1 objects.
oids.h
ASN.1 object identifiers for algorithms and schemes.
ElGamalKeys::PublicKey
DL_PublicKey_ElGamal< DL_CryptoKeys_ElGamal::PublicKey > PublicKey
Implements DL_PublicKey interface.
Definition: elgamal.h:268
RandomNumberGenerator::GenerateBlock
virtual void GenerateBlock(byte *output, size_t size)
Generate random array of bytes.
DL_PrivateKey_ElGamal
ElGamal Private Key adapter.
Definition: elgamal.h:171
DL_KeyAgreementAlgorithm_DH
Diffie-Hellman key agreement algorithm.
Definition: pubkey.h:2141
ElGamal::Encryptor
PK_FinalTemplate< ElGamalObjectImpl< DL_EncryptorBase< Integer >, SchemeOptions, SchemeOptions::PublicKey > > Encryptor
Implements PK_Encryptor interface.
Definition: elgamal.h:298
Integer::Encode
void Encode(byte *output, size_t outputLen, Signedness sign=UNSIGNED) const
Encode in big-endian format.
ElGamalKeys::GroupParameters
DL_CryptoKeys_ElGamal::GroupParameters GroupParameters
Implements DL_GroupParameters interface.
Definition: elgamal.h:264
CryptoPP
Crypto++ library namespace.
DL_PrivateKey_ElGamal::Validate
bool Validate(RandomNumberGenerator &rng, unsigned int level) const
Check the key for errors.
Definition: elgamal.h:206
DL_GroupParameters< Integer >
DL_GroupParameters_ElGamal
ElGamal encryption for safe interop.
Definition: gfpcrypt.h:291
PK_FinalTemplate
Template implementing constructors for public key algorithm classes.
Definition: pubkey.h:2197
Integer::One
static const Integer & One()
Integer representing 1.
NameValuePairs
Interface for retrieving values given their names.
Definition: cryptlib.h:321
cryptlib.h
Abstract base classes that provide a uniform interface to this library.
Integer::Gcd
static Integer Gcd(const Integer &a, const Integer &n)
Calculate greatest common divisor.
integer.h
Multiple precision integer with arithmetic operations.
Integer
Multiple precision integer with arithmetic operations.
Definition: integer.h:49