Botan  2.19.1
Crypto and TLS for C++11
elgamal.cpp
Go to the documentation of this file.
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/keypair.h>
12 #include <botan/blinding.h>
13 
14 namespace Botan {
15 
16 /*
17 * ElGamal_PublicKey Constructor
18 */
20  DL_Scheme_PublicKey(group, y)
21  {
22  }
23 
24 /*
25 * ElGamal_PrivateKey Constructor
26 */
28  const DL_Group& group,
29  const BigInt& x)
30  {
31  m_x = x;
32  m_group = group;
33 
34  if(m_x.is_zero())
35  {
36  const size_t exp_bits = m_group.exponent_bits();
37  m_x.randomize(rng, exp_bits);
38  m_y = m_group.power_g_p(m_x, exp_bits);
39  }
40  else
41  {
43  }
44  }
45 
47  const secure_vector<uint8_t>& key_bits) :
48  DL_Scheme_PrivateKey(alg_id, key_bits, DL_Group::ANSI_X9_42)
49  {
51  }
52 
53 /*
54 * Check Private ElGamal Parameters
55 */
57  bool strong) const
58  {
59  if(!DL_Scheme_PrivateKey::check_key(rng, strong))
60  return false;
61 
62  if(!strong)
63  return true;
64 
65  return KeyPair::encryption_consistency_check(rng, *this, "OAEP(SHA-256)");
66  }
67 
68 namespace {
69 
70 /**
71 * ElGamal encryption operation
72 */
73 class ElGamal_Encryption_Operation final : public PK_Ops::Encryption_with_EME
74  {
75  public:
76 
77  size_t ciphertext_length(size_t) const override { return 2*m_group.p_bytes(); }
78 
79  size_t max_raw_input_bits() const override { return m_group.p_bits() - 1; }
80 
81  ElGamal_Encryption_Operation(const ElGamal_PublicKey& key, const std::string& eme);
82 
83  secure_vector<uint8_t> raw_encrypt(const uint8_t msg[], size_t msg_len,
84  RandomNumberGenerator& rng) override;
85 
86  private:
87  const DL_Group m_group;
88  std::shared_ptr<const Montgomery_Exponentation_State> m_monty_y_p;
89  };
90 
91 ElGamal_Encryption_Operation::ElGamal_Encryption_Operation(const ElGamal_PublicKey& key,
92  const std::string& eme) :
93  PK_Ops::Encryption_with_EME(eme),
94  m_group(key.get_group())
95  {
96  const size_t powm_window = 4;
97  m_monty_y_p = monty_precompute(key.get_group().monty_params_p(),
98  key.get_y(),
99  powm_window);
100  }
101 
102 secure_vector<uint8_t>
103 ElGamal_Encryption_Operation::raw_encrypt(const uint8_t msg[], size_t msg_len,
104  RandomNumberGenerator& rng)
105  {
106  BigInt m(msg, msg_len);
107 
108  if(m >= m_group.get_p())
109  throw Invalid_Argument("ElGamal encryption: Input is too large");
110 
111  /*
112  Some ElGamal implementations generate keys where using short exponents
113  is unsafe. Always use full length exponents to avoid this.
114 
115  See https://eprint.iacr.org/2021/923 for details.
116  */
117  const size_t k_bits = m_group.p_bits() - 1;
118  const BigInt k(rng, k_bits, false);
119 
120  const BigInt a = m_group.power_g_p(k, k_bits);
121  const BigInt b = m_group.multiply_mod_p(m, monty_execute(*m_monty_y_p, k, k_bits));
122 
123  return BigInt::encode_fixed_length_int_pair(a, b, m_group.p_bytes());
124  }
125 
126 /**
127 * ElGamal decryption operation
128 */
129 class ElGamal_Decryption_Operation final : public PK_Ops::Decryption_with_EME
130  {
131  public:
132 
133  ElGamal_Decryption_Operation(const ElGamal_PrivateKey& key,
134  const std::string& eme,
135  RandomNumberGenerator& rng);
136 
137  size_t plaintext_length(size_t) const override { return m_group.p_bytes(); }
138 
139  secure_vector<uint8_t> raw_decrypt(const uint8_t msg[], size_t msg_len) override;
140  private:
141  BigInt powermod_x_p(const BigInt& v) const
142  {
143  const size_t powm_window = 4;
144  auto powm_v_p = monty_precompute(m_monty_p, v, powm_window);
145  return monty_execute(*powm_v_p, m_x, m_x_bits);
146  }
147 
148  const DL_Group m_group;
149  const BigInt& m_x;
150  const size_t m_x_bits;
151  std::shared_ptr<const Montgomery_Params> m_monty_p;
152  Blinder m_blinder;
153  };
154 
155 ElGamal_Decryption_Operation::ElGamal_Decryption_Operation(const ElGamal_PrivateKey& key,
156  const std::string& eme,
157  RandomNumberGenerator& rng) :
158  PK_Ops::Decryption_with_EME(eme),
159  m_group(key.get_group()),
160  m_x(key.get_x()),
161  m_x_bits(m_x.bits()),
162  m_monty_p(key.get_group().monty_params_p()),
163  m_blinder(m_group.get_p(),
164  rng,
165  [](const BigInt& k) { return k; },
166  [this](const BigInt& k) { return powermod_x_p(k); })
167  {
168  }
169 
170 secure_vector<uint8_t>
171 ElGamal_Decryption_Operation::raw_decrypt(const uint8_t msg[], size_t msg_len)
172  {
173  const size_t p_bytes = m_group.p_bytes();
174 
175  if(msg_len != 2 * p_bytes)
176  throw Invalid_Argument("ElGamal decryption: Invalid message");
177 
178  BigInt a(msg, p_bytes);
179  const BigInt b(msg + p_bytes, p_bytes);
180 
181  if(a >= m_group.get_p() || b >= m_group.get_p())
182  throw Invalid_Argument("ElGamal decryption: Invalid message");
183 
184  a = m_blinder.blind(a);
185 
186  const BigInt r = m_group.multiply_mod_p(m_group.inverse_mod_p(powermod_x_p(a)), b);
187 
188  return BigInt::encode_1363(m_blinder.unblind(r), p_bytes);
189  }
190 
191 }
192 
193 std::unique_ptr<PK_Ops::Encryption>
194 ElGamal_PublicKey::create_encryption_op(RandomNumberGenerator& /*rng*/,
195  const std::string& params,
196  const std::string& provider) const
197  {
198  if(provider == "base" || provider.empty())
199  return std::unique_ptr<PK_Ops::Encryption>(new ElGamal_Encryption_Operation(*this, params));
200  throw Provider_Not_Found(algo_name(), provider);
201  }
202 
203 std::unique_ptr<PK_Ops::Decryption>
204 ElGamal_PrivateKey::create_decryption_op(RandomNumberGenerator& rng,
205  const std::string& params,
206  const std::string& provider) const
207  {
208  if(provider == "base" || provider.empty())
209  return std::unique_ptr<PK_Ops::Decryption>(new ElGamal_Decryption_Operation(*this, params, rng));
210  throw Provider_Not_Found(algo_name(), provider);
211  }
212 
213 }
Blinder m_blinder
Definition: elgamal.cpp:152
ElGamal_PrivateKey(const AlgorithmIdentifier &alg_id, const secure_vector< uint8_t > &key_bits)
Definition: elgamal.cpp:46
void randomize(RandomNumberGenerator &rng, size_t bitsize, bool set_high_bit=true)
Definition: big_rand.cpp:17
std::shared_ptr< const Montgomery_Exponentation_State > m_monty_y_p
Definition: elgamal.cpp:88
bool check_key(RandomNumberGenerator &rng, bool) const override
Definition: elgamal.cpp:56
int(* final)(unsigned char *, CTX *)
bool encryption_consistency_check(RandomNumberGenerator &rng, const Private_Key &private_key, const Public_Key &public_key, const std::string &padding)
Definition: keypair.cpp:19
size_t p_bits() const
Definition: dl_group.cpp:451
std::vector< T, secure_allocator< T >> secure_vector
Definition: secmem.h:65
std::shared_ptr< const Montgomery_Params > m_monty_p
Definition: elgamal.cpp:151
std::shared_ptr< const Montgomery_Exponentation_State > monty_precompute(std::shared_ptr< const Montgomery_Params > params, const BigInt &g, size_t window_bits, bool const_time)
Definition: monty_exp.cpp:157
size_t exponent_bits() const
Definition: dl_group.cpp:478
Definition: alg_id.cpp:13
const DL_Group m_group
Definition: elgamal.cpp:87
BigInt power_g_p(const BigInt &x) const
Definition: dl_group.cpp:535
const BigInt & m_x
Definition: elgamal.cpp:149
bool check_key(RandomNumberGenerator &rng, bool) const override
Definition: dl_algo.cpp:78
const size_t m_x_bits
Definition: elgamal.cpp:150
bool is_zero() const
Definition: bigint.h:421
BigInt monty_execute(const Montgomery_Exponentation_State &precomputed_state, const BigInt &k, size_t max_k_bits)
Definition: monty_exp.cpp:165