Botan 3.14.1
Crypto and TLS for C&
elgamal.cpp
Go to the documentation of this file.
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/buffer_stuffer.h>
12#include <botan/internal/ct_utils.h>
13#include <botan/internal/dl_scheme.h>
14#include <botan/internal/keypair.h>
15#include <botan/internal/monty_exp.h>
16#include <botan/internal/pk_ops_impl.h>
17#include <botan/internal/pk_options_impl.h>
18
19namespace Botan {
20
22 m_public_key = std::make_shared<DL_PublicKey>(group, y);
23}
24
25ElGamal_PublicKey::ElGamal_PublicKey(const AlgorithmIdentifier& alg_id, std::span<const uint8_t> key_bits) {
26 m_public_key = std::make_shared<DL_PublicKey>(alg_id, key_bits, DL_Group_Format::ANSI_X9_42);
27}
28
30 return m_public_key->estimated_strength();
31}
32
34 return m_public_key->p_bits();
35}
36
40
41std::vector<uint8_t> ElGamal_PublicKey::raw_public_key_bits() const {
42 return m_public_key->public_key_as_bytes();
43}
44
45std::vector<uint8_t> ElGamal_PublicKey::public_key_bits() const {
46 return m_public_key->DER_encode();
47}
48
49const BigInt& ElGamal_PublicKey::get_int_field(std::string_view field) const {
50 return m_public_key->get_int_field(algo_name(), field);
51}
52
53std::unique_ptr<Private_Key> ElGamal_PublicKey::generate_another(RandomNumberGenerator& rng) const {
54 return std::make_unique<ElGamal_PrivateKey>(rng, m_public_key->group());
55}
56
58 return m_public_key->check_key(rng, strong);
59}
60
62 m_private_key = std::make_shared<DL_PrivateKey>(group, rng);
63 m_public_key = m_private_key->public_key();
64}
65
67 m_private_key = std::make_shared<DL_PrivateKey>(group, x);
68 m_public_key = m_private_key->public_key();
69}
70
71ElGamal_PrivateKey::ElGamal_PrivateKey(const AlgorithmIdentifier& alg_id, std::span<const uint8_t> key_bits) {
72 m_private_key = std::make_shared<DL_PrivateKey>(alg_id, key_bits, DL_Group_Format::ANSI_X9_42);
73 m_public_key = m_private_key->public_key();
74}
75
76std::unique_ptr<Public_Key> ElGamal_PrivateKey::public_key() const {
77 return std::unique_ptr<Public_Key>(new ElGamal_PublicKey(m_public_key));
78}
79
80const BigInt& ElGamal_PrivateKey::get_int_field(std::string_view field) const {
81 return m_private_key->get_int_field(algo_name(), field);
82}
83
85 return m_private_key->DER_encode();
86}
87
89 return m_private_key->raw_private_key_bits();
90}
91
93 if(!m_private_key->check_key(rng, strong)) {
94 return false;
95 }
96
97 if(!strong) {
98 return true;
99 }
100
101#if defined(BOTAN_HAS_OAEP) && defined(BOTAN_HAS_SHA_256)
102 const std::string padding = "OAEP(SHA-256)";
103#else
104 const std::string padding = "Raw";
105#endif
106
107 return KeyPair::encryption_consistency_check(rng, *this, padding);
108}
109
110namespace {
111
112/**
113* ElGamal encryption operation
114*/
115class ElGamal_Encryption_Operation final : public PK_Ops::Encryption_with_Padding {
116 public:
117 ElGamal_Encryption_Operation(const std::shared_ptr<const DL_PublicKey>& key,
118 const PK_Encryption_Options_Reader& options) :
119 PK_Ops::Encryption_with_Padding(options), m_key(key) {
120 const size_t powm_window = 4;
121 m_monty_y_p = monty_precompute(m_key->group()._monty_params_p(), m_key->public_key(), powm_window);
122 }
123
124 size_t ciphertext_length(size_t /*ptext_len*/) const override { return 2 * m_key->group().p_bytes(); }
125
126 size_t max_ptext_input_bits() const override { return m_key->group().p_bits() - 1; }
127
128 std::vector<uint8_t> raw_encrypt(std::span<const uint8_t> ptext, RandomNumberGenerator& rng) override;
129
130 private:
131 std::shared_ptr<const DL_PublicKey> m_key;
132 std::shared_ptr<const Montgomery_Exponentiation_State> m_monty_y_p;
133};
134
135std::vector<uint8_t> ElGamal_Encryption_Operation::raw_encrypt(std::span<const uint8_t> ptext,
137 const BigInt m(ptext);
138
139 const auto& group = m_key->group();
140
141 if(m == 0 || m >= group.get_p()) {
142 throw Invalid_Argument("ElGamal encryption: Message out of valid plaintext range");
143 }
144
145 /*
146 Some weird PGP implementations generate keys using bad parameters
147 which result in easily breakable encryption if short exponents are
148 used during encryption. To avoid this problem, always use full size
149 exponents.
150
151 See https://eprint.iacr.org/2021/923
152 */
153 const size_t k_bits = group.p_bits() - 1;
154 const BigInt k(rng, k_bits, false);
155
156 const auto scope = CT::scoped_poison(m, k);
157
158 const BigInt a = group.power_g_p(k, k_bits);
159 const BigInt b = group.multiply_mod_p(m, monty_execute(*m_monty_y_p, k, k_bits).value());
160 CT::unpoison_all(a, b);
161
162 const size_t p_bytes = group.p_bytes();
163 std::vector<uint8_t> ctext(2 * p_bytes);
164 BufferStuffer stuffer(ctext);
165 a.serialize_to(stuffer.next(p_bytes));
166 b.serialize_to(stuffer.next(p_bytes));
167 return ctext;
168}
169
170/**
171* ElGamal decryption operation
172*/
173class ElGamal_Decryption_Operation final : public PK_Ops::Decryption_with_Padding {
174 public:
175 ElGamal_Decryption_Operation(const std::shared_ptr<const DL_PrivateKey>& key,
176 const PK_Encryption_Options_Reader& options,
177 RandomNumberGenerator& rng) :
178 PK_Ops::Decryption_with_Padding(options),
179 m_key(key),
180 m_blinder(
181 m_key->group()._reducer_mod_p(),
182 rng,
183 [](const BigInt& k) { return k; },
184 [this](const BigInt& k) { return powermod_x_p(k); }) {}
185
186 size_t plaintext_length(size_t /*ctext_len*/) const override { return m_key->group().p_bytes(); }
187
188 size_t ciphertext_length(size_t /*ptext_len*/) const override { return 2 * m_key->group().p_bytes(); }
189
190 secure_vector<uint8_t> raw_decrypt(std::span<const uint8_t> ctext) override;
191
192 private:
193 BigInt powermod_x_p(const BigInt& v) const {
194 return m_key->group().power_b_p(v, m_key->private_key(), m_key->max_private_key_bits());
195 }
196
197 std::shared_ptr<const DL_PrivateKey> m_key;
198 Blinder m_blinder;
199};
200
201secure_vector<uint8_t> ElGamal_Decryption_Operation::raw_decrypt(std::span<const uint8_t> ctext) {
202 const auto& group = m_key->group();
203
204 const size_t p_bytes = group.p_bytes();
205
206 if(ctext.size() != 2 * p_bytes) {
207 throw Invalid_Argument("ElGamal decryption: Invalid message");
208 }
209
210 BigInt a(ctext.first(p_bytes));
211 const BigInt b(ctext.last(p_bytes));
212
213 if(!group.verify_public_element(a)) {
214 throw Invalid_Argument("ElGamal decryption: Invalid message");
215 }
216
217 if(b == 0 || b >= group.get_p()) {
218 throw Invalid_Argument("ElGamal decryption: Invalid message");
219 }
220
221 const auto scope = CT::scoped_poison(m_key->private_key(), m_blinder);
222
223 a = m_blinder.blind(a);
224
225 const BigInt r = group.multiply_mod_p(group.inverse_mod_p(powermod_x_p(a)), b);
226
227 // Any further secret handling of the output is up to the caller
228 const BigInt ptext = m_blinder.unblind(r);
229 CT::unpoison(ptext);
230
231 return ptext.serialize<secure_vector<uint8_t>>(p_bytes);
232}
233
234} // namespace
235
236std::unique_ptr<PK_Ops::Encryption> ElGamal_PublicKey::_create_encryption_op(
237 RandomNumberGenerator& rng, const PK_Encryption_Options_Reader& options) const {
238 BOTAN_UNUSED(rng);
240
241 return std::make_unique<ElGamal_Encryption_Operation>(this->m_public_key, options);
242}
243
244std::unique_ptr<PK_Ops::Decryption> ElGamal_PrivateKey::_create_decryption_op(
245 RandomNumberGenerator& rng, const PK_Encryption_Options_Reader& options) const {
247
248 return std::make_unique<ElGamal_Decryption_Operation>(this->m_private_key, options, rng);
249}
250
251} // namespace Botan
#define BOTAN_UNUSED
Definition assert.h:151
virtual OID object_identifier() const
Definition pk_keys.cpp:24
BigInt blind(const BigInt &x) const
Definition blinding.cpp:34
BigInt unblind(const BigInt &x) const
Definition blinding.cpp:50
std::unique_ptr< PK_Ops::Decryption > _create_decryption_op(RandomNumberGenerator &rng, const PK_Encryption_Options_Reader &options) const override
Definition elgamal.cpp:244
secure_vector< uint8_t > private_key_bits() const override
Definition elgamal.cpp:84
const BigInt & get_int_field(std::string_view field) const override
Definition elgamal.cpp:80
bool check_key(RandomNumberGenerator &rng, bool strong) const override
Definition elgamal.cpp:92
std::unique_ptr< Public_Key > public_key() const override
Definition elgamal.cpp:76
secure_vector< uint8_t > raw_private_key_bits() const override
Definition elgamal.cpp:88
const BigInt & get_int_field(std::string_view field) const override
Definition elgamal.cpp:49
std::unique_ptr< PK_Ops::Encryption > _create_encryption_op(RandomNumberGenerator &rng, const PK_Encryption_Options_Reader &options) const override
Definition elgamal.cpp:236
std::vector< uint8_t > public_key_bits() const override
Definition elgamal.cpp:45
friend class ElGamal_PrivateKey
Definition elgamal.h:61
size_t estimated_strength() const override
Definition elgamal.cpp:29
bool check_key(RandomNumberGenerator &rng, bool strong) const override
Definition elgamal.cpp:57
AlgorithmIdentifier algorithm_identifier() const override
Definition elgamal.cpp:37
std::vector< uint8_t > raw_public_key_bits() const override
Definition elgamal.cpp:41
size_t key_length() const override
Definition elgamal.cpp:33
std::unique_ptr< Private_Key > generate_another(RandomNumberGenerator &rng) const final
Definition elgamal.cpp:53
std::string algo_name() const override
Definition elgamal.h:51
ElGamal_PublicKey(const AlgorithmIdentifier &alg_id, std::span< const uint8_t > key_bits)
Definition elgamal.cpp:25
bool encryption_consistency_check(RandomNumberGenerator &rng, const Private_Key &private_key, const Public_Key &public_key, std::string_view padding)
Definition keypair.cpp:18
std::shared_ptr< const Montgomery_Exponentiation_State > monty_precompute(const Montgomery_Int &g, size_t window_bits)
void require_software_provider(const OptionsT &options, std::string_view algo_name)
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:128
Montgomery_Int monty_execute(const Montgomery_Exponentiation_State &precomputed_state, const BigInt &k, size_t max_k_bits)