botan.pubkey.algo.elgamal source code

1 /**
2 * ElGamal
3 * 
4 * Copyright:
5 * (C) 1999-2007 Jack Lloyd
6 * (C) 2014-2015 Etienne Cimon
7 *
8 * License:
9 * Botan is released under the Simplified BSD License (see LICENSE.md)
10 */
11 module botan.pubkey.algo.elgamal;
12 
13 import botan.constants;
14 static if (BOTAN_HAS_PUBLIC_KEY_CRYPTO && BOTAN_HAS_ELGAMAL):
15 
16 public import botan.pubkey.pubkey;
17 import botan.pubkey.algo.dl_algo;
18 import botan.math.numbertheory.numthry;
19 import botan.math.numbertheory.reducer;
20 import botan.pubkey.blinding;
21 import botan.pubkey.pk_ops;
22 import botan.pubkey.workfactor;
23 import botan.math.numbertheory.numthry;
24 import botan.pubkey.algo.keypair;
25 import botan.rng.rng;
26 import botan.utils.types;
27 import memutils.helpers : Embed;
28 
29 struct ElGamalOptions {
30     enum algoName = "ElGamal";
31     enum format = DLGroup.ANSI_X9_42;
32 
33     /*
34     * Check Private ElGamal Parameters
35     */
36     static bool checkKey(in DLSchemePrivateKey privkey, RandomNumberGenerator rng, bool strong)
37     {
38         if (!privkey.checkKeyImpl(rng, strong))
39             return false;
40         
41         if (!strong)
42             return true;
43         
44         return encryptionConsistencyCheck(rng, privkey, "EME1(SHA-1)");
45     }
46 
47 }
48 
49 /**
50 * ElGamal Public Key
51 */
52 struct ElGamalPublicKey
53 {
54 public:
55     alias Options = ElGamalOptions;
56     __gshared immutable string algoName = Options.algoName;
57 
58     this(in AlgorithmIdentifier alg_id, const ref SecureVector!ubyte key_bits)
59     {
60 		m_owned = true;
61         m_pub = new DLSchemePublicKey(Options(), alg_id, key_bits);
62     }
63     /*
64     * ElGamalPublicKey Constructor
65     */
66     this(DLGroup grp, BigInt y1)
67     {
68 		m_owned = true;
69         m_pub = new DLSchemePublicKey(Options(), grp.move, y1.move);
70     }
71 
72     this(PublicKey pkey) { m_pub = cast(DLSchemePublicKey) pkey; }
73     this(PrivateKey pkey) { m_pub = cast(DLSchemePublicKey) pkey; }
74 
75     mixin Embed!(m_pub, m_owned);
76 
77 	bool m_owned;
78     DLSchemePublicKey m_pub;
79 }
80 
81 /**
82 * ElGamal Private Key
83 */
84 struct ElGamalPrivateKey
85 {
86 public:
87     alias Options = ElGamalOptions;
88     __gshared immutable string algoName = Options.algoName;
89 
90     /*
91     * ElGamalPrivateKey Constructor
92     */
93     this(RandomNumberGenerator rng, DLGroup grp, BigInt x_arg = BigInt(0))
94     {    
95         bool x_arg_0;
96         if (x_arg == 0) {
97             x_arg_0 = true;
98             x_arg.randomize(rng, 2 * dlWorkFactor(grp.getP().bits()));
99         }
100         BigInt y1 = powerMod(&grp.getG(), &x_arg, &grp.getP());
101         
102 		m_owned = true;
103         m_priv = new DLSchemePrivateKey(Options(), grp.move, y1.move, x_arg.move);
104 
105         if (x_arg_0)
106             m_priv.genCheck(rng);
107         else
108             m_priv.loadCheck(rng);
109 
110     }
111 
112     this(in AlgorithmIdentifier alg_id,
113          const ref SecureVector!ubyte key_bits,
114          RandomNumberGenerator rng) 
115     {
116 		m_owned = true;
117         m_priv = new DLSchemePrivateKey(Options(), alg_id, key_bits);
118 
119         m_priv.setY(powerMod(&m_priv.groupG(), &m_priv.m_x, &m_priv.groupP()));
120         m_priv.loadCheck(rng);
121     }
122 
123     this(PrivateKey pkey) { m_priv = cast(DLSchemePrivateKey) pkey; }
124 
125     mixin Embed!(m_priv, m_owned);
126 
127 	bool m_owned;
128     DLSchemePrivateKey m_priv;
129 }
130 
131 /**
132 * ElGamal encryption operation
133 */
134 final class ElGamalEncryptionOperation : Encryption
135 {
136 public:
137     override size_t maxInputBits() const { return m_mod_p.getModulus().bits() - 1; }
138 
139     this(in PublicKey pkey) {
140         this(cast(DLSchemePublicKey) pkey);
141     }
142 
143     this(in ElGamalPublicKey pkey) {
144         this(pkey.m_pub);
145     }
146 
147     this(in DLSchemePublicKey key)
148     {
149         m_key = key;
150         assert(key.algoName == ElGamalPublicKey.algoName);
151         const BigInt* p = &m_key.groupP();
152         
153         m_powermod_g_p = FixedBasePowerMod(&m_key.groupG(), p);
154         m_powermod_y_p = FixedBasePowerMod(&m_key.getY(), p);
155         m_mod_p = ModularReducer(*p);
156     }
157 
158     override SecureVector!ubyte encrypt(const(ubyte)* msg, size_t msg_len, RandomNumberGenerator rng)
159     {
160         const BigInt* p = &m_mod_p.getModulus();
161         
162         BigInt m = BigInt(msg, msg_len);
163         
164         if (m >= *p)
165             throw new InvalidArgument("ElGamal encryption: Input is too large");
166 
167         BigInt k = BigInt(rng, 2 * dlWorkFactor(p.bits()));
168         BigInt g_p = (cast()*m_powermod_g_p)(&k);
169         BigInt y_p_0 = (cast()*m_powermod_y_p)(&k);
170         BigInt y_p = m_mod_p.multiply(&m, &y_p_0);
171         
172         SecureVector!ubyte output = SecureVector!ubyte(2*p.bytes());
173         g_p.binaryEncode(&output[p.bytes() - g_p.bytes()]);
174         y_p.binaryEncode(&output[output.length / 2 + (p.bytes() - y_p.bytes())]);
175         return output;
176     }
177 
178 private:
179     const DLSchemePublicKey m_key;
180     FixedBasePowerMod m_powermod_g_p, m_powermod_y_p;
181     ModularReducer m_mod_p;
182 }
183 
184 /**
185 * ElGamal decryption operation
186 */
187 final class ElGamalDecryptionOperation : Decryption
188 {
189 public:
190     override size_t maxInputBits() const { return m_mod_p.getModulus().bits() - 1; }
191 
192     this(in PrivateKey pkey, RandomNumberGenerator rng) {
193         this(cast(DLSchemePrivateKey) pkey, rng);
194     }
195 
196     this(in ElGamalPrivateKey key, RandomNumberGenerator rng)
197     {
198         this(key.m_priv, rng);
199     }
200 
201     this(in DLSchemePrivateKey key, RandomNumberGenerator rng)
202     {
203         assert(key.algoName == ElGamalPublicKey.algoName);
204         const BigInt* p = &key.groupP();
205         
206         m_powermod_x_p = FixedExponentPowerMod(&key.getX(), p);
207         m_mod_p = ModularReducer(*p);
208         
209         BigInt k = BigInt(rng, p.bits() - 1);
210         auto d = (cast()*m_powermod_x_p)(&k);
211         m_blinder = Blinder(k, d, *p);
212     }
213 
214     override SecureVector!ubyte decrypt(const(ubyte)* msg, size_t msg_len)
215     {
216         const BigInt* p = &m_mod_p.getModulus();
217         
218         const size_t p_bytes = p.bytes();
219         
220         if (msg_len != 2 * p_bytes)
221             throw new InvalidArgument("ElGamal decryption: Invalid message");
222         
223         BigInt a = BigInt(msg, p_bytes);
224         BigInt b = BigInt(msg + p_bytes, p_bytes);
225         
226         if (a >= *p || b >= *p)
227             throw new InvalidArgument("ElGamal decryption: Invalid message");
228         
229         a = m_blinder.blind(a);
230         auto r_0 = (cast()*m_powermod_x_p)(&a);
231         auto inv_res = inverseMod(&r_0, p);
232         BigInt r = m_mod_p.multiply(&b, &inv_res);
233         
234         return BigInt.encodeLocked(m_blinder.unblind(r));
235     }
236 private:
237     FixedExponentPowerMod m_powermod_x_p;
238     ModularReducer m_mod_p;
239     Blinder m_blinder;
240 }
241 
242 static if (BOTAN_TEST):
243 import botan.test;
244 import botan.pubkey.test;
245 import botan.pubkey.pubkey;
246 import botan.codec.hex;
247 import botan.pubkey.algo.dl_group;
248 import botan.rng.auto_rng;
249 import core.atomic;
250 import memutils.hashmap;
251 
252 private shared size_t total_tests;
253 
254 size_t testPkKeygen(RandomNumberGenerator rng)
255 {
256     size_t fails;
257     
258     string[] elg_list = ["modp/ietf/1024", "dsa/jce/1024", "dsa/botan/2048", "dsa/botan/3072"];
259     
260     foreach (elg; elg_list) {
261         atomicOp!"+="(total_tests, 1);
262         auto key = ElGamalPrivateKey(rng, DLGroup(elg));
263         key.checkKey(rng, true);
264         fails += validateSaveAndLoad(key, rng);
265     }
266     
267     return fails;
268 }
269 
270 size_t elgamalKat(string p,
271                    string g,
272                    string x,
273                    string msg,
274                    string padding,
275                    string nonce,
276                    string ciphertext)
277 {
278     atomicOp!"+="(total_tests, 1);
279 	Unique!AutoSeededRNG rng = new AutoSeededRNG;
280     
281     BigInt p_bn = BigInt(p);
282     BigInt g_bn = BigInt(g);
283     BigInt x_bn = BigInt(x);
284     
285     DLGroup group = DLGroup(p_bn, g_bn);
286     auto privkey = ElGamalPrivateKey(*rng, group.move(), x_bn.move());
287     
288     auto pubkey = ElGamalPublicKey(privkey);
289     
290     if (padding == "")
291         padding = "Raw";
292     
293     auto enc = scoped!PKEncryptorEME(pubkey, padding);
294     auto dec = scoped!PKDecryptorEME(privkey, padding);
295     
296     return validateEncryption(enc, dec, "ElGamal/" ~ padding, msg, nonce, ciphertext);
297 }
298 
299 static if (BOTAN_HAS_TESTS && !SKIP_ELGAMAL_TEST) unittest
300 {
301     logDebug("Testing elgamal.d ...");
302     size_t fails = 0;
303     
304 	Unique!AutoSeededRNG rng = new AutoSeededRNG;
305     
306     fails += testPkKeygen(*rng);
307     
308     File elgamal_enc = File("test_data/pubkey/elgamal.vec", "r");
309     
310     fails += runTestsBb(elgamal_enc, "ElGamal Encryption", "Ciphertext", true,
311         (ref HashMap!(string, string) m) {
312             return elgamalKat(m["P"], m["G"], m["X"], m["Msg"],
313             m.get("Padding", ""), m["Nonce"], m["Ciphertext"]);
314         });
315     
316     testReport("elg", total_tests, fails);
317 }