/src/Botan-3.4.0/src/lib/pubkey/elgamal/elgamal.cpp

Source
/*
* ElGamal
* (C) 1999-2007,2018,2019,2023 Jack Lloyd
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include <botan/elgamal.h>

#include <botan/internal/blinding.h>
#include <botan/internal/dl_scheme.h>
#include <botan/internal/keypair.h>
#include <botan/internal/monty_exp.h>
#include <botan/internal/pk_ops_impl.h>

namespace Botan {

ElGamal_PublicKey::ElGamal_PublicKey(const DL_Group& group, const BigInt& y) {
   m_public_key = std::make_shared<DL_PublicKey>(group, y);
}

ElGamal_PublicKey::ElGamal_PublicKey(const AlgorithmIdentifier& alg_id, std::span<const uint8_t> key_bits) {
   m_public_key = std::make_shared<DL_PublicKey>(alg_id, key_bits, DL_Group_Format::ANSI_X9_42);
}

size_t ElGamal_PublicKey::estimated_strength() const {
   return m_public_key->estimated_strength();
}

size_t ElGamal_PublicKey::key_length() const {
   return m_public_key->p_bits();
}

AlgorithmIdentifier ElGamal_PublicKey::algorithm_identifier() const {
   return AlgorithmIdentifier(object_identifier(), m_public_key->group().DER_encode(DL_Group_Format::ANSI_X9_42));
}

std::vector<uint8_t> ElGamal_PublicKey::public_key_bits() const {
   return m_public_key->DER_encode();
}

const BigInt& ElGamal_PublicKey::get_int_field(std::string_view field) const {
   return m_public_key->get_int_field(algo_name(), field);
}

std::unique_ptr<Private_Key> ElGamal_PublicKey::generate_another(RandomNumberGenerator& rng) const {
   return std::make_unique<ElGamal_PrivateKey>(rng, m_public_key->group());
}

bool ElGamal_PublicKey::check_key(RandomNumberGenerator& rng, bool strong) const {
   return m_public_key->check_key(rng, strong);
}

ElGamal_PrivateKey::ElGamal_PrivateKey(RandomNumberGenerator& rng, const DL_Group& group) {
   m_private_key = std::make_shared<DL_PrivateKey>(group, rng);
   m_public_key = m_private_key->public_key();
}

ElGamal_PrivateKey::ElGamal_PrivateKey(const DL_Group& group, const BigInt& x) {
   m_private_key = std::make_shared<DL_PrivateKey>(group, x);
   m_public_key = m_private_key->public_key();
}

ElGamal_PrivateKey::ElGamal_PrivateKey(const AlgorithmIdentifier& alg_id, std::span<const uint8_t> key_bits) {
   m_private_key = std::make_shared<DL_PrivateKey>(alg_id, key_bits, DL_Group_Format::ANSI_X9_42);
   m_public_key = m_private_key->public_key();
}

std::unique_ptr<Public_Key> ElGamal_PrivateKey::public_key() const {
   return std::unique_ptr<Public_Key>(new ElGamal_PublicKey(m_public_key));
}

const BigInt& ElGamal_PrivateKey::get_int_field(std::string_view field) const {
   return m_private_key->get_int_field(algo_name(), field);
}

secure_vector<uint8_t> ElGamal_PrivateKey::private_key_bits() const {
   return m_private_key->DER_encode();
}

secure_vector<uint8_t> ElGamal_PrivateKey::raw_private_key_bits() const {
   return m_private_key->raw_private_key_bits();
}

bool ElGamal_PrivateKey::check_key(RandomNumberGenerator& rng, bool strong) const {
   if(!m_private_key->check_key(rng, strong)) {
      return false;
   }

   return KeyPair::encryption_consistency_check(rng, *this, "OAEP(SHA-256)");
}

namespace {

/**
* ElGamal encryption operation
*/
class ElGamal_Encryption_Operation final : public PK_Ops::Encryption_with_EME {
   public:
      ElGamal_Encryption_Operation(const std::shared_ptr<const DL_PublicKey>& key, std::string_view eme) :
            PK_Ops::Encryption_with_EME(eme), m_key(key) {
         const size_t powm_window = 4;
         m_monty_y_p = monty_precompute(m_key->group().monty_params_p(), m_key->public_key(), powm_window);
      }

      size_t ciphertext_length(size_t /*ptext_len*/) const override { return 2 * m_key->group().p_bytes(); }

      size_t max_ptext_input_bits() const override { return m_key->group().p_bits() - 1; }

      secure_vector<uint8_t> raw_encrypt(const uint8_t msg[], size_t msg_len, RandomNumberGenerator& rng) override;

   private:
      std::shared_ptr<const DL_PublicKey> m_key;
      std::shared_ptr<const Montgomery_Exponentation_State> m_monty_y_p;
};

secure_vector<uint8_t> ElGamal_Encryption_Operation::raw_encrypt(const uint8_t msg[],
                                                                 size_t msg_len,
                                                                 RandomNumberGenerator& rng) {
   BigInt m(msg, msg_len);

   const auto& group = m_key->group();

   if(m >= group.get_p()) {
      throw Invalid_Argument("ElGamal encryption: Input is too large");
   }

   /*
   Some weird PGP implementations generate keys using bad parameters
   which result in easily breakable encryption if short exponents are
   used during encryption. To avoid this problem, always use full size
   exponents.

   See https://eprint.iacr.org/2021/923
   */
   const size_t k_bits = group.p_bits() - 1;
   const BigInt k(rng, k_bits, false);

   const BigInt a = group.power_g_p(k, k_bits);
   const BigInt b = group.multiply_mod_p(m, monty_execute(*m_monty_y_p, k, k_bits));

   return BigInt::encode_fixed_length_int_pair(a, b, group.p_bytes());
}

/**
* ElGamal decryption operation
*/
class ElGamal_Decryption_Operation final : public PK_Ops::Decryption_with_EME {
   public:
      ElGamal_Decryption_Operation(const std::shared_ptr<const DL_PrivateKey>& key,
                                   std::string_view eme,
                                   RandomNumberGenerator& rng) :
            PK_Ops::Decryption_with_EME(eme),
            m_key(key),
            m_blinder(
               m_key->group().get_p(),
               rng,
               [](const BigInt& k) { return k; },
               [this](const BigInt& k) { return powermod_x_p(k); }) {}

      size_t plaintext_length(size_t /*ctext_len*/) const override { return m_key->group().p_bytes(); }

      secure_vector<uint8_t> raw_decrypt(const uint8_t msg[], size_t msg_len) override;

   private:
      BigInt powermod_x_p(const BigInt& v) const { return m_key->group().power_b_p(v, m_key->private_key()); }

      std::shared_ptr<const DL_PrivateKey> m_key;
      Blinder m_blinder;
};

secure_vector<uint8_t> ElGamal_Decryption_Operation::raw_decrypt(const uint8_t msg[], size_t msg_len) {
   const auto& group = m_key->group();

   const size_t p_bytes = group.p_bytes();

   if(msg_len != 2 * p_bytes) {
      throw Invalid_Argument("ElGamal decryption: Invalid message");
   }

   BigInt a(msg, p_bytes);
   const BigInt b(msg + p_bytes, p_bytes);

   if(a >= group.get_p() || b >= group.get_p()) {
      throw Invalid_Argument("ElGamal decryption: Invalid message");
   }

   a = m_blinder.blind(a);

   const BigInt r = group.multiply_mod_p(group.inverse_mod_p(powermod_x_p(a)), b);

   return BigInt::encode_1363(m_blinder.unblind(r), p_bytes);
}

}  // namespace

std::unique_ptr<PK_Ops::Encryption> ElGamal_PublicKey::create_encryption_op(RandomNumberGenerator& /*rng*/,
                                                                            std::string_view params,
                                                                            std::string_view provider) const {
   if(provider == "base" || provider.empty()) {
      return std::make_unique<ElGamal_Encryption_Operation>(this->m_public_key, params);
   }
   throw Provider_Not_Found(algo_name(), provider);
}

std::unique_ptr<PK_Ops::Decryption> ElGamal_PrivateKey::create_decryption_op(RandomNumberGenerator& rng,
                                                                             std::string_view params,
                                                                             std::string_view provider) const {
   if(provider == "base" || provider.empty()) {
      return std::make_unique<ElGamal_Decryption_Operation>(this->m_private_key, params, rng);
   }
   throw Provider_Not_Found(algo_name(), provider);
}

}  // namespace Botan

Coverage Report

Created: 2025-10-10 06:23

Line	Count	Source
1		/*
2		* ElGamal
3		* (C) 1999-2007,2018,2019,2023 Jack Lloyd
4		*
5		* Botan is released under the Simplified BSD License (see license.txt)
6		*/
7
8		#include <botan/elgamal.h>
9
10		#include <botan/internal/blinding.h>
11		#include <botan/internal/dl_scheme.h>
12		#include <botan/internal/keypair.h>
13		#include <botan/internal/monty_exp.h>
14		#include <botan/internal/pk_ops_impl.h>
15
16		namespace Botan {
17
18	0	ElGamal_PublicKey::ElGamal_PublicKey(const DL_Group& group, const BigInt& y) {
19	0	m_public_key = std::make_shared<DL_PublicKey>(group, y);
20	0	} Unexecuted instantiation: Botan::ElGamal_PublicKey::ElGamal_PublicKey(Botan::DL_Group const&, Botan::BigInt const&) Unexecuted instantiation: Botan::ElGamal_PublicKey::ElGamal_PublicKey(Botan::DL_Group const&, Botan::BigInt const&)
21
22	0	ElGamal_PublicKey::ElGamal_PublicKey(const AlgorithmIdentifier& alg_id, std::span<const uint8_t> key_bits) {
23	0	m_public_key = std::make_shared<DL_PublicKey>(alg_id, key_bits, DL_Group_Format::ANSI_X9_42);
24	0	} Unexecuted instantiation: Botan::ElGamal_PublicKey::ElGamal_PublicKey(Botan::AlgorithmIdentifier const&, std::__1::span<unsigned char const, 18446744073709551615ul>) Unexecuted instantiation: Botan::ElGamal_PublicKey::ElGamal_PublicKey(Botan::AlgorithmIdentifier const&, std::__1::span<unsigned char const, 18446744073709551615ul>)
25
26	0	size_t ElGamal_PublicKey::estimated_strength() const {
27	0	return m_public_key->estimated_strength();
28	0	}
29
30	0	size_t ElGamal_PublicKey::key_length() const {
31	0	return m_public_key->p_bits();
32	0	}
33
34	0	AlgorithmIdentifier ElGamal_PublicKey::algorithm_identifier() const {
35	0	return AlgorithmIdentifier(object_identifier(), m_public_key->group().DER_encode(DL_Group_Format::ANSI_X9_42));
36	0	}
37
38	0	std::vector<uint8_t> ElGamal_PublicKey::public_key_bits() const {
39	0	return m_public_key->DER_encode();
40	0	}
41
42	0	const BigInt& ElGamal_PublicKey::get_int_field(std::string_view field) const {
43	0	return m_public_key->get_int_field(algo_name(), field);
44	0	}
45
46	0	std::unique_ptr<Private_Key> ElGamal_PublicKey::generate_another(RandomNumberGenerator& rng) const {
47	0	return std::make_unique<ElGamal_PrivateKey>(rng, m_public_key->group());
48	0	}
49
50	0	bool ElGamal_PublicKey::check_key(RandomNumberGenerator& rng, bool strong) const {
51	0	return m_public_key->check_key(rng, strong);
52	0	}
53
54	0	ElGamal_PrivateKey::ElGamal_PrivateKey(RandomNumberGenerator& rng, const DL_Group& group) {
55	0	m_private_key = std::make_shared<DL_PrivateKey>(group, rng);
56	0	m_public_key = m_private_key->public_key();
57	0	} Unexecuted instantiation: Botan::ElGamal_PrivateKey::ElGamal_PrivateKey(Botan::RandomNumberGenerator&, Botan::DL_Group const&) Unexecuted instantiation: Botan::ElGamal_PrivateKey::ElGamal_PrivateKey(Botan::RandomNumberGenerator&, Botan::DL_Group const&)
58
59	0	ElGamal_PrivateKey::ElGamal_PrivateKey(const DL_Group& group, const BigInt& x) {
60	0	m_private_key = std::make_shared<DL_PrivateKey>(group, x);
61	0	m_public_key = m_private_key->public_key();
62	0	} Unexecuted instantiation: Botan::ElGamal_PrivateKey::ElGamal_PrivateKey(Botan::DL_Group const&, Botan::BigInt const&) Unexecuted instantiation: Botan::ElGamal_PrivateKey::ElGamal_PrivateKey(Botan::DL_Group const&, Botan::BigInt const&)
63
64	0	ElGamal_PrivateKey::ElGamal_PrivateKey(const AlgorithmIdentifier& alg_id, std::span<const uint8_t> key_bits) {
65	0	m_private_key = std::make_shared<DL_PrivateKey>(alg_id, key_bits, DL_Group_Format::ANSI_X9_42);
66	0	m_public_key = m_private_key->public_key();
67	0	} Unexecuted instantiation: Botan::ElGamal_PrivateKey::ElGamal_PrivateKey(Botan::AlgorithmIdentifier const&, std::__1::span<unsigned char const, 18446744073709551615ul>) Unexecuted instantiation: Botan::ElGamal_PrivateKey::ElGamal_PrivateKey(Botan::AlgorithmIdentifier const&, std::__1::span<unsigned char const, 18446744073709551615ul>)
68
69	0	std::unique_ptr<Public_Key> ElGamal_PrivateKey::public_key() const {
70	0	return std::unique_ptr<Public_Key>(new ElGamal_PublicKey(m_public_key));
71	0	}
72
73	0	const BigInt& ElGamal_PrivateKey::get_int_field(std::string_view field) const {
74	0	return m_private_key->get_int_field(algo_name(), field);
75	0	}
76
77	0	secure_vector<uint8_t> ElGamal_PrivateKey::private_key_bits() const {
78	0	return m_private_key->DER_encode();
79	0	}
80
81	0	secure_vector<uint8_t> ElGamal_PrivateKey::raw_private_key_bits() const {
82	0	return m_private_key->raw_private_key_bits();
83	0	}
84
85	0	bool ElGamal_PrivateKey::check_key(RandomNumberGenerator& rng, bool strong) const {
86	0	if(!m_private_key->check_key(rng, strong)) {
87	0	return false;
88	0	}
89
90	0	return KeyPair::encryption_consistency_check(rng, *this, "OAEP(SHA-256)");
91	0	}
92
93		namespace {
94
95		/**
96		* ElGamal encryption operation
97		*/
98		class ElGamal_Encryption_Operation final : public PK_Ops::Encryption_with_EME {
99		public:
100		ElGamal_Encryption_Operation(const std::shared_ptr<const DL_PublicKey>& key, std::string_view eme) :
101	0	PK_Ops::Encryption_with_EME(eme), m_key(key) {
102	0	const size_t powm_window = 4;
103	0	m_monty_y_p = monty_precompute(m_key->group().monty_params_p(), m_key->public_key(), powm_window);
104	0	}
105
106	0	size_t ciphertext_length(size_t /ptext_len/) const override { return 2 * m_key->group().p_bytes(); }
107
108	0	size_t max_ptext_input_bits() const override { return m_key->group().p_bits() - 1; }
109
110		secure_vector<uint8_t> raw_encrypt(const uint8_t msg[], size_t msg_len, RandomNumberGenerator& rng) override;
111
112		private:
113		std::shared_ptr<const DL_PublicKey> m_key;
114		std::shared_ptr<const Montgomery_Exponentation_State> m_monty_y_p;
115		};
116
117		secure_vector<uint8_t> ElGamal_Encryption_Operation::raw_encrypt(const uint8_t msg[],
118		size_t msg_len,
119	0	RandomNumberGenerator& rng) {
120	0	BigInt m(msg, msg_len);
121
122	0	const auto& group = m_key->group();
123
124	0	if(m >= group.get_p()) {
125	0	throw Invalid_Argument("ElGamal encryption: Input is too large");
126	0	}
127
128		/*
129		Some weird PGP implementations generate keys using bad parameters
130		which result in easily breakable encryption if short exponents are
131		used during encryption. To avoid this problem, always use full size
132		exponents.
133
134		See https://eprint.iacr.org/2021/923
135		*/
136	0	const size_t k_bits = group.p_bits() - 1;
137	0	const BigInt k(rng, k_bits, false);
138
139	0	const BigInt a = group.power_g_p(k, k_bits);
140	0	const BigInt b = group.multiply_mod_p(m, monty_execute(*m_monty_y_p, k, k_bits));
141
142	0	return BigInt::encode_fixed_length_int_pair(a, b, group.p_bytes());
143	0	}
144
145		/**
146		* ElGamal decryption operation
147		*/
148		class ElGamal_Decryption_Operation final : public PK_Ops::Decryption_with_EME {
149		public:
150		ElGamal_Decryption_Operation(const std::shared_ptr<const DL_PrivateKey>& key,
151		std::string_view eme,
152		RandomNumberGenerator& rng) :
153	0	PK_Ops::Decryption_with_EME(eme),
154	0	m_key(key),
155	0	m_blinder(
156	0	m_key->group().get_p(),
157	0	rng,
158	0	[](const BigInt& k) { return k; },
159	0	[this](const BigInt& k) { return powermod_x_p(k); }) {}
160
161	0	size_t plaintext_length(size_t /ctext_len/) const override { return m_key->group().p_bytes(); }
162
163		secure_vector<uint8_t> raw_decrypt(const uint8_t msg[], size_t msg_len) override;
164
165		private:
166	0	BigInt powermod_x_p(const BigInt& v) const { return m_key->group().power_b_p(v, m_key->private_key()); }
167
168		std::shared_ptr<const DL_PrivateKey> m_key;
169		Blinder m_blinder;
170		};
171
172	0	secure_vector<uint8_t> ElGamal_Decryption_Operation::raw_decrypt(const uint8_t msg[], size_t msg_len) {
173	0	const auto& group = m_key->group();
174
175	0	const size_t p_bytes = group.p_bytes();
176
177	0	if(msg_len != 2 * p_bytes) {
178	0	throw Invalid_Argument("ElGamal decryption: Invalid message");
179	0	}
180
181	0	BigInt a(msg, p_bytes);
182	0	const BigInt b(msg + p_bytes, p_bytes);
183
184	0	if(a >= group.get_p() \|\| b >= group.get_p()) {
185	0	throw Invalid_Argument("ElGamal decryption: Invalid message");
186	0	}
187
188	0	a = m_blinder.blind(a);
189
190	0	const BigInt r = group.multiply_mod_p(group.inverse_mod_p(powermod_x_p(a)), b);
191
192	0	return BigInt::encode_1363(m_blinder.unblind(r), p_bytes);
193	0	}
194
195		} // namespace
196
197		std::unique_ptr<PK_Ops::Encryption> ElGamal_PublicKey::create_encryption_op(RandomNumberGenerator& /rng/,
198		std::string_view params,
199	0	std::string_view provider) const {
200	0	if(provider == "base" \|\| provider.empty()) {
201	0	return std::make_unique<ElGamal_Encryption_Operation>(this->m_public_key, params);
202	0	}
203	0	throw Provider_Not_Found(algo_name(), provider);
204	0	}
205
206		std::unique_ptr<PK_Ops::Decryption> ElGamal_PrivateKey::create_decryption_op(RandomNumberGenerator& rng,
207		std::string_view params,
208	0	std::string_view provider) const {
209	0	if(provider == "base" \|\| provider.empty()) {
210	0	return std::make_unique<ElGamal_Decryption_Operation>(this->m_private_key, params, rng);
211	0	}
212	0	throw Provider_Not_Found(algo_name(), provider);
213	0	}
214
215		} // namespace Botan