Botan 3.3.0
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/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
16namespace Botan {
17
18ElGamal_PublicKey::ElGamal_PublicKey(const DL_Group& group, const BigInt& y) {
19 m_public_key = std::make_shared<DL_PublicKey>(group, y);
20}
21
22ElGamal_PublicKey::ElGamal_PublicKey(const AlgorithmIdentifier& alg_id, std::span<const uint8_t> key_bits) {
23 m_public_key = std::make_shared<DL_PublicKey>(alg_id, key_bits, DL_Group_Format::ANSI_X9_42);
24}
25
27 return m_public_key->estimated_strength();
28}
29
31 return m_public_key->p_bits();
32}
33
37
38std::vector<uint8_t> ElGamal_PublicKey::public_key_bits() const {
39 return m_public_key->DER_encode();
40}
41
42const BigInt& ElGamal_PublicKey::get_int_field(std::string_view field) const {
43 return m_public_key->get_int_field(algo_name(), field);
44}
45
46std::unique_ptr<Private_Key> ElGamal_PublicKey::generate_another(RandomNumberGenerator& rng) const {
47 return std::make_unique<ElGamal_PrivateKey>(rng, m_public_key->group());
48}
49
51 return m_public_key->check_key(rng, strong);
52}
53
55 m_private_key = std::make_shared<DL_PrivateKey>(group, rng);
56 m_public_key = m_private_key->public_key();
57}
58
60 m_private_key = std::make_shared<DL_PrivateKey>(group, x);
61 m_public_key = m_private_key->public_key();
62}
63
64ElGamal_PrivateKey::ElGamal_PrivateKey(const AlgorithmIdentifier& alg_id, std::span<const uint8_t> key_bits) {
65 m_private_key = std::make_shared<DL_PrivateKey>(alg_id, key_bits, DL_Group_Format::ANSI_X9_42);
66 m_public_key = m_private_key->public_key();
67}
68
69std::unique_ptr<Public_Key> ElGamal_PrivateKey::public_key() const {
70 return std::unique_ptr<Public_Key>(new ElGamal_PublicKey(m_public_key));
71}
72
73const BigInt& ElGamal_PrivateKey::get_int_field(std::string_view field) const {
74 return m_private_key->get_int_field(algo_name(), field);
75}
76
78 return m_private_key->DER_encode();
79}
80
82 return m_private_key->raw_private_key_bits();
83}
84
86 if(!m_private_key->check_key(rng, strong)) {
87 return false;
88 }
89
90 return KeyPair::encryption_consistency_check(rng, *this, "OAEP(SHA-256)");
91}
92
93namespace {
94
95/**
96* ElGamal encryption operation
97*/
98class 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 PK_Ops::Encryption_with_EME(eme), m_key(key) {
102 const size_t powm_window = 4;
103 m_monty_y_p = monty_precompute(m_key->group().monty_params_p(), m_key->public_key(), powm_window);
104 }
105
106 size_t ciphertext_length(size_t /*ptext_len*/) const override { return 2 * m_key->group().p_bytes(); }
107
108 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
117secure_vector<uint8_t> ElGamal_Encryption_Operation::raw_encrypt(const uint8_t msg[],
118 size_t msg_len,
119 RandomNumberGenerator& rng) {
120 BigInt m(msg, msg_len);
121
122 const auto& group = m_key->group();
123
124 if(m >= group.get_p()) {
125 throw Invalid_Argument("ElGamal encryption: Input is too large");
126 }
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 const size_t k_bits = group.p_bits() - 1;
137 const BigInt k(rng, k_bits, false);
138
139 const BigInt a = group.power_g_p(k, k_bits);
140 const BigInt b = group.multiply_mod_p(m, monty_execute(*m_monty_y_p, k, k_bits));
141
142 return BigInt::encode_fixed_length_int_pair(a, b, group.p_bytes());
143}
144
145/**
146* ElGamal decryption operation
147*/
148class 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 PK_Ops::Decryption_with_EME(eme),
154 m_key(key),
155 m_blinder(
156 m_key->group().get_p(),
157 rng,
158 [](const BigInt& k) { return k; },
159 [this](const BigInt& k) { return powermod_x_p(k); }) {}
160
161 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 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
172secure_vector<uint8_t> ElGamal_Decryption_Operation::raw_decrypt(const uint8_t msg[], size_t msg_len) {
173 const auto& group = m_key->group();
174
175 const size_t p_bytes = group.p_bytes();
176
177 if(msg_len != 2 * p_bytes) {
178 throw Invalid_Argument("ElGamal decryption: Invalid message");
179 }
180
181 BigInt a(msg, p_bytes);
182 const BigInt b(msg + p_bytes, p_bytes);
183
184 if(a >= group.get_p() || b >= group.get_p()) {
185 throw Invalid_Argument("ElGamal decryption: Invalid message");
186 }
187
188 a = m_blinder.blind(a);
189
190 const BigInt r = group.multiply_mod_p(group.inverse_mod_p(powermod_x_p(a)), b);
191
192 return BigInt::encode_1363(m_blinder.unblind(r), p_bytes);
193}
194
195} // namespace
196
197std::unique_ptr<PK_Ops::Encryption> ElGamal_PublicKey::create_encryption_op(RandomNumberGenerator& /*rng*/,
198 std::string_view params,
199 std::string_view provider) const {
200 if(provider == "base" || provider.empty()) {
201 return std::make_unique<ElGamal_Encryption_Operation>(this->m_public_key, params);
202 }
203 throw Provider_Not_Found(algo_name(), provider);
204}
205
207 std::string_view params,
208 std::string_view provider) const {
209 if(provider == "base" || provider.empty()) {
210 return std::make_unique<ElGamal_Decryption_Operation>(this->m_private_key, params, rng);
211 }
212 throw Provider_Not_Found(algo_name(), provider);
213}
214
215} // namespace Botan
virtual OID object_identifier() const
Definition pk_keys.cpp:22
BigInt blind(const BigInt &x) const
Definition blinding.cpp:33
BigInt unblind(const BigInt &x) const
Definition blinding.cpp:53
std::unique_ptr< PK_Ops::Decryption > create_decryption_op(RandomNumberGenerator &rng, std::string_view params, std::string_view provider) const override
Definition elgamal.cpp:206
secure_vector< uint8_t > private_key_bits() const override
Definition elgamal.cpp:77
const BigInt & get_int_field(std::string_view field) const override
Definition elgamal.cpp:73
std::unique_ptr< Public_Key > public_key() const override
Definition elgamal.cpp:69
secure_vector< uint8_t > raw_private_key_bits() const override
Definition elgamal.cpp:81
bool check_key(RandomNumberGenerator &rng, bool) const override
Definition elgamal.cpp:85
std::unique_ptr< PK_Ops::Encryption > create_encryption_op(RandomNumberGenerator &rng, std::string_view params, std::string_view provider) const override
Definition elgamal.cpp:197
const BigInt & get_int_field(std::string_view field) const override
Definition elgamal.cpp:42
std::vector< uint8_t > public_key_bits() const override
Definition elgamal.cpp:38
friend class ElGamal_PrivateKey
Definition elgamal.h:61
size_t estimated_strength() const override
Definition elgamal.cpp:26
bool check_key(RandomNumberGenerator &rng, bool strong) const override
Definition elgamal.cpp:50
AlgorithmIdentifier algorithm_identifier() const override
Definition elgamal.cpp:34
size_t key_length() const override
Definition elgamal.cpp:30
std::unique_ptr< Private_Key > generate_another(RandomNumberGenerator &rng) const final
Definition elgamal.cpp:46
std::string algo_name() const override
Definition elgamal.h:50
int(* final)(unsigned char *, CTX *)
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::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:61
BigInt monty_execute(const Montgomery_Exponentation_State &precomputed_state, const BigInt &k, size_t max_k_bits)
std::shared_ptr< const Montgomery_Exponentation_State > monty_precompute(const std::shared_ptr< const Montgomery_Params > &params, const BigInt &g, size_t window_bits, bool const_time)