Coverage Report

Created: 2023-01-25 06:35

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