Crypto++  8.4
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 /// \sa <A HREF="https://github.com/weidai11/cryptopp/issues/876">Issue 876</A>,
255 /// <A HREF="https://github.com/weidai11/cryptopp/issues/567">Issue 567</A>
256 /// \since Crypto++ 1.0
258 {
259  /// \brief Implements DL_GroupParameters interface
261  /// \brief Implements DL_PrivateKey interface
263  /// \brief Implements DL_PublicKey interface
265 };
266 
267 /// \brief ElGamal encryption scheme with non-standard padding
268 /// \details ElGamal provide the algorithm implementation ElGamal key
269 /// agreement and encryption schemes.
270 /// \details The ElGamal class [mistakenly] used the OID for DSA from about
271 /// Crypto++ 1.0 through Crypto++ 8.2. At Crypto++ 8.3 the OID was fixed
272 /// and now uses ElGamal encryption, which is 1.3.14.7.2.1.1.
273 /// If you need to <tt>Load</tt> an ElGamal key with the wrong OID then
274 /// see <A HREF="https://www.cryptopp.com/wiki/ElGamal">ElGamal</A> on
275 /// the Crypto++ wiki.
276 /// \sa <A HREF="https://github.com/weidai11/cryptopp/issues/876">Issue 876</A>,
277 /// <A HREF="https://github.com/weidai11/cryptopp/issues/567">Issue 567</A>
278 /// \since Crypto++ 1.0
279 struct ElGamal
280 {
282  typedef SchemeOptions::PrivateKey PrivateKey;
283  typedef SchemeOptions::PublicKey PublicKey;
284 
285  /// \brief The algorithm name
286  /// \return the algorithm name
287  /// \details StaticAlgorithmName returns the algorithm's name as a static
288  /// member function.
289  CRYPTOPP_STATIC_CONSTEXPR const char* StaticAlgorithmName() {return "ElgamalEnc/Crypto++Padding";}
290 
291  /// \brief Implements DL_GroupParameters interface
292  typedef SchemeOptions::GroupParameters GroupParameters;
293  /// \brief Implements PK_Encryptor interface
295  /// \brief Implements PK_Encryptor interface
297 };
298 
301 
302 NAMESPACE_END
303 
304 #endif
Classes and functions for working with ANS.1 objects.
GF(p) group parameters that default to safe primes.
Definition: gfpcrypt.h:275
GF(p) group parameters.
Definition: gfpcrypt.h:225
Interface for Discrete Log (DL) group parameters.
Definition: pubkey.h:782
Diffie-Hellman key agreement algorithm.
Definition: pubkey.h:2132
Interface for DL key agreement algorithms.
Definition: pubkey.h:1474
Interface for key derivation algorithms used in DL cryptosystems.
Definition: pubkey.h:1488
Discrete Log (DL) base object implementation.
Definition: pubkey.h:1947
Interface for symmetric encryption algorithms used in DL cryptosystems.
Definition: pubkey.h:1499
ElGamal key agreement and encryption schemes base class.
Definition: elgamal.h:27
ElGamal key agreement and encryption schemes default implementation.
Definition: elgamal.h:110
Multiple precision integer with arithmetic operations.
Definition: integer.h:50
static const Integer & One()
Integer representing 1.
unsigned int ByteCount() const
Determines the number of bytes required to represent the Integer.
static Integer Gcd(const Integer &a, const Integer &n)
Calculate greatest common divisor.
void Encode(byte *output, size_t outputLen, Signedness sign=UNSIGNED) const
Encode in big-endian format.
Interface for retrieving values given their names.
Definition: cryptlib.h:322
Object Identifier.
Definition: asn.h:265
Template implementing constructors for public key algorithm classes.
Definition: pubkey.h:2188
Interface for private keys.
Definition: cryptlib.h:2524
Interface for public keys.
Definition: cryptlib.h:2519
Interface for random number generators.
Definition: cryptlib.h:1418
virtual void GenerateBlock(byte *output, size_t size)
Generate random array of bytes.
SecBlock<byte> typedef.
Definition: secblock.h:1115
unsigned char byte
8-bit unsigned datatype
Definition: config_int.h:56
Abstract base classes that provide a uniform interface to this library.
Classes for the DSA signature algorithm.
Classes and functions for schemes based on Discrete Logs (DL) over GF(p)
Multiple precision integer with arithmetic operations.
Utility functions for the Crypto++ library.
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
Definition: misc.h:635
Crypto++ library namespace.
ASN.1 object identifiers for algorthms and schemes.
This file contains helper classes/functions for implementing public key algorithms.
Discrete Log (DL) crypto scheme options.
Definition: pubkey.h:1935
ElGamal Private Key adapter.
Definition: elgamal.h:172
virtual OID GetAlgorithmID() const
Retrieves the OID of the algorithm.
Definition: elgamal.h:185
bool Validate(RandomNumberGenerator &rng, unsigned int level) const
Check the key for errors.
Definition: elgamal.h:206
ElGamal Public Key adapter.
Definition: elgamal.h:141
virtual OID GetAlgorithmID() const
Retrieves the OID of the algorithm.
Definition: elgamal.h:154
Returns a decoding results.
Definition: cryptlib.h:278
ElGamal encryption scheme with non-standard padding.
Definition: elgamal.h:280
PK_FinalTemplate< ElGamalObjectImpl< DL_EncryptorBase< Integer >, SchemeOptions, SchemeOptions::PublicKey > > Encryptor
Implements PK_Encryptor interface.
Definition: elgamal.h:294
PK_FinalTemplate< ElGamalObjectImpl< DL_DecryptorBase< Integer >, SchemeOptions, SchemeOptions::PrivateKey > > Decryptor
Implements PK_Encryptor interface.
Definition: elgamal.h:296
static const char * StaticAlgorithmName()
The algorithm name.
Definition: elgamal.h:289
SchemeOptions::GroupParameters GroupParameters
Implements DL_GroupParameters interface.
Definition: elgamal.h:292
ElGamal key agreement and encryption schemes keys.
Definition: elgamal.h:258
DL_PrivateKey_ElGamal< DL_CryptoKeys_GFP::PrivateKey > PrivateKey
Implements DL_PrivateKey interface.
Definition: elgamal.h:262
DL_CryptoKeys_GFP::GroupParameters GroupParameters
Implements DL_GroupParameters interface.
Definition: elgamal.h:260
DL_PublicKey_ElGamal< DL_CryptoKeys_GFP::PublicKey > PublicKey
Implements DL_PublicKey interface.
Definition: elgamal.h:264
Converts an enumeration to a type suitable for use as a template parameter.
Definition: cryptlib.h:136
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Definition: trap.h:68