Botan  2.1.0
Crypto and TLS for C++11
elgamal.cpp
Go to the documentation of this file.
1 /*
2 * ElGamal
3 * (C) 1999-2007 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/keypair.h>
11 #include <botan/reducer.h>
12 #include <botan/blinding.h>
13 #include <botan/workfactor.h>
14 
15 namespace Botan {
16 
17 /*
18 * ElGamal_PublicKey Constructor
19 */
21  {
22  m_group = grp;
23  m_y = y1;
24  }
25 
26 /*
27 * ElGamal_PrivateKey Constructor
28 */
30  const DL_Group& grp,
31  const BigInt& x_arg)
32  {
33  m_group = grp;
34  m_x = x_arg;
35 
36  if(m_x == 0)
37  m_x.randomize(rng, dl_exponent_size(group_p().bits()));
38 
39  m_y = power_mod(group_g(), m_x, group_p());
40  }
41 
43  const secure_vector<uint8_t>& key_bits) :
44  DL_Scheme_PrivateKey(alg_id, key_bits, DL_Group::ANSI_X9_42)
45  {
46  m_y = power_mod(group_g(), m_x, group_p());
47  }
48 
49 /*
50 * Check Private ElGamal Parameters
51 */
53  bool strong) const
54  {
55  if(!DL_Scheme_PrivateKey::check_key(rng, strong))
56  return false;
57 
58  if(!strong)
59  return true;
60 
61  return KeyPair::encryption_consistency_check(rng, *this, "EME1(SHA-256)");
62  }
63 
64 namespace {
65 
66 /**
67 * ElGamal encryption operation
68 */
69 class ElGamal_Encryption_Operation : public PK_Ops::Encryption_with_EME
70  {
71  public:
72 
73  size_t max_raw_input_bits() const override { return m_mod_p.get_modulus().bits() - 1; }
74 
75  ElGamal_Encryption_Operation(const ElGamal_PublicKey& key, const std::string& eme);
76 
77  secure_vector<uint8_t> raw_encrypt(const uint8_t msg[], size_t msg_len,
78  RandomNumberGenerator& rng) override;
79 
80  private:
81  Fixed_Base_Power_Mod m_powermod_g_p, m_powermod_y_p;
82  Modular_Reducer m_mod_p;
83  };
84 
85 ElGamal_Encryption_Operation::ElGamal_Encryption_Operation(const ElGamal_PublicKey& key,
86  const std::string& eme) :
87  PK_Ops::Encryption_with_EME(eme)
88  {
89  const BigInt& p = key.group_p();
90 
91  m_powermod_g_p = Fixed_Base_Power_Mod(key.group_g(), p);
92  m_powermod_y_p = Fixed_Base_Power_Mod(key.get_y(), p);
93  m_mod_p = Modular_Reducer(p);
94  }
95 
96 secure_vector<uint8_t>
97 ElGamal_Encryption_Operation::raw_encrypt(const uint8_t msg[], size_t msg_len,
98  RandomNumberGenerator& rng)
99  {
100  const BigInt& p = m_mod_p.get_modulus();
101 
102  BigInt m(msg, msg_len);
103 
104  if(m >= p)
105  throw Invalid_Argument("ElGamal encryption: Input is too large");
106 
107  BigInt k(rng, dl_exponent_size(p.bits()));
108 
109  BigInt a = m_powermod_g_p(k);
110  BigInt b = m_mod_p.multiply(m, m_powermod_y_p(k));
111 
112  secure_vector<uint8_t> output(2*p.bytes());
113  a.binary_encode(&output[p.bytes() - a.bytes()]);
114  b.binary_encode(&output[output.size() / 2 + (p.bytes() - b.bytes())]);
115  return output;
116  }
117 
118 /**
119 * ElGamal decryption operation
120 */
121 class ElGamal_Decryption_Operation : public PK_Ops::Decryption_with_EME
122  {
123  public:
124 
125  size_t max_raw_input_bits() const override
126  { return m_mod_p.get_modulus().bits() - 1; }
127 
128  ElGamal_Decryption_Operation(const ElGamal_PrivateKey& key,
129  const std::string& eme,
130  RandomNumberGenerator& rng);
131 
132  secure_vector<uint8_t> raw_decrypt(const uint8_t msg[], size_t msg_len) override;
133  private:
134  Fixed_Exponent_Power_Mod m_powermod_x_p;
135  Modular_Reducer m_mod_p;
136  Blinder m_blinder;
137  };
138 
139 ElGamal_Decryption_Operation::ElGamal_Decryption_Operation(const ElGamal_PrivateKey& key,
140  const std::string& eme,
141  RandomNumberGenerator& rng) :
142  PK_Ops::Decryption_with_EME(eme),
143  m_powermod_x_p(Fixed_Exponent_Power_Mod(key.get_x(), key.group_p())),
144  m_mod_p(Modular_Reducer(key.group_p())),
145  m_blinder(key.group_p(),
146  rng,
147  [](const BigInt& k) { return k; },
148  [this](const BigInt& k) { return m_powermod_x_p(k); })
149  {
150  }
151 
152 secure_vector<uint8_t>
153 ElGamal_Decryption_Operation::raw_decrypt(const uint8_t msg[], size_t msg_len)
154  {
155  const BigInt& p = m_mod_p.get_modulus();
156 
157  const size_t p_bytes = p.bytes();
158 
159  if(msg_len != 2 * p_bytes)
160  throw Invalid_Argument("ElGamal decryption: Invalid message");
161 
162  BigInt a(msg, p_bytes);
163  BigInt b(msg + p_bytes, p_bytes);
164 
165  if(a >= p || b >= p)
166  throw Invalid_Argument("ElGamal decryption: Invalid message");
167 
168  a = m_blinder.blind(a);
169 
170  BigInt r = m_mod_p.multiply(b, inverse_mod(m_powermod_x_p(a), p));
171 
172  return BigInt::encode_1363(m_blinder.unblind(r), p_bytes);
173  }
174 
175 }
176 
177 std::unique_ptr<PK_Ops::Encryption>
178 ElGamal_PublicKey::create_encryption_op(RandomNumberGenerator& /*rng*/,
179  const std::string& params,
180  const std::string& provider) const
181  {
182  if(provider == "base" || provider.empty())
183  return std::unique_ptr<PK_Ops::Encryption>(new ElGamal_Encryption_Operation(*this, params));
184  throw Provider_Not_Found(algo_name(), provider);
185  }
186 
187 std::unique_ptr<PK_Ops::Decryption>
188 ElGamal_PrivateKey::create_decryption_op(RandomNumberGenerator& rng,
189  const std::string& params,
190  const std::string& provider) const
191  {
192  if(provider == "base" || provider.empty())
193  return std::unique_ptr<PK_Ops::Decryption>(new ElGamal_Decryption_Operation(*this, params, rng));
194  throw Provider_Not_Found(algo_name(), provider);
195  }
196 
197 }
Modular_Reducer m_mod_p
Definition: elgamal.cpp:82
Blinder m_blinder
Definition: elgamal.cpp:136
size_t dl_exponent_size(size_t bits)
Definition: workfactor.cpp:40
bool encryption_consistency_check(RandomNumberGenerator &rng, const Private_Key &private_key, const Public_Key &public_key, const std::string &padding)
Definition: keypair.cpp:18
ElGamal_PrivateKey(const AlgorithmIdentifier &alg_id, const secure_vector< uint8_t > &key_bits)
Definition: elgamal.cpp:42
void randomize(RandomNumberGenerator &rng, size_t bitsize, bool set_high_bit=true)
Definition: big_rand.cpp:17
bool check_key(RandomNumberGenerator &rng, bool) const override
Definition: elgamal.cpp:52
Fixed_Base_Power_Mod m_powermod_y_p
Definition: elgamal.cpp:81
const BigInt & group_p() const
Definition: dl_algo.h:43
std::vector< T, secure_allocator< T >> secure_vector
Definition: secmem.h:121
Definition: alg_id.cpp:13
Fixed_Exponent_Power_Mod m_powermod_x_p
Definition: elgamal.cpp:134
BigInt inverse_mod(const BigInt &n, const BigInt &mod)
Definition: numthry.cpp:276
BigInt power_mod(const BigInt &base, const BigInt &exp, const BigInt &mod)
Definition: numthry.cpp:373
bool check_key(RandomNumberGenerator &rng, bool) const override
Definition: dl_algo.cpp:90
const BigInt & group_g() const
Definition: dl_algo.h:55
Fixed_Base_Power_Mod m_powermod_g_p
Definition: elgamal.cpp:81