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         assert(key.algoName == ElGamalPublicKey.algoName);
150         const BigInt* p = &key.groupP();
151         
152         m_powermod_g_p = FixedBasePowerMod(key.groupG(), *p);
153         m_powermod_y_p = FixedBasePowerMod(key.getY(), *p);
154         m_mod_p = ModularReducer(*p);
155     }
156 
157     override SecureVector!ubyte encrypt(const(ubyte)* msg, size_t msg_len, RandomNumberGenerator rng)
158     {
159         const BigInt* p = &m_mod_p.getModulus();
160         
161         BigInt m = BigInt(msg, msg_len);
162         
163         if (m >= *p)
164             throw new InvalidArgument("ElGamal encryption: Input is too large");
165 
166         BigInt k = BigInt(rng, 2 * dlWorkFactor(p.bits()));
167         
168         BigInt a = (*m_powermod_g_p)(k);
169         BigInt b = m_mod_p.multiply(m, (*m_powermod_y_p)(k));
170         
171         SecureVector!ubyte output = SecureVector!ubyte(2*p.bytes());
172         a.binaryEncode(&output[p.bytes() - a.bytes()]);
173         b.binaryEncode(&output[output.length / 2 + (p.bytes() - b.bytes())]);
174         return output;
175     }
176 
177 private:
178     FixedBasePowerMod m_powermod_g_p, m_powermod_y_p;
179     ModularReducer m_mod_p;
180 }
181 
182 /**
183 * ElGamal decryption operation
184 */
185 final class ElGamalDecryptionOperation : Decryption
186 {
187 public:
188     override size_t maxInputBits() const { return m_mod_p.getModulus().bits() - 1; }
189 
190     this(in PrivateKey pkey, RandomNumberGenerator rng) {
191         this(cast(DLSchemePrivateKey) pkey, rng);
192     }
193 
194     this(in ElGamalPrivateKey key, RandomNumberGenerator rng)
195     {
196         this(key.m_priv, rng);
197     }
198 
199     this(in DLSchemePrivateKey key, RandomNumberGenerator rng)
200     {
201         assert(key.algoName == ElGamalPublicKey.algoName);
202         const BigInt* p = &key.groupP();
203         
204         m_powermod_x_p = FixedExponentPowerMod(key.getX(), *p);
205         m_mod_p = ModularReducer(*p);
206         
207         BigInt k = BigInt(rng, p.bits() - 1);
208         auto d = (*m_powermod_x_p)(k);
209         m_blinder = Blinder(k, d, *p);
210     }
211 
212     override SecureVector!ubyte decrypt(const(ubyte)* msg, size_t msg_len)
213     {
214         const BigInt* p = &m_mod_p.getModulus();
215         
216         const size_t p_bytes = p.bytes();
217         
218         if (msg_len != 2 * p_bytes)
219             throw new InvalidArgument("ElGamal decryption: Invalid message");
220         
221         BigInt a = BigInt(msg, p_bytes);
222         BigInt b = BigInt(msg + p_bytes, p_bytes);
223         
224         if (a >= *p || b >= *p)
225             throw new InvalidArgument("ElGamal decryption: Invalid message");
226         
227         a = m_blinder.blind(a);
228         
229         BigInt r = m_mod_p.multiply(b, inverseMod((*m_powermod_x_p)(a), *p));
230         
231         return BigInt.encodeLocked(m_blinder.unblind(r));
232     }
233 private:
234     FixedExponentPowerMod m_powermod_x_p;
235     ModularReducer m_mod_p;
236     Blinder m_blinder;
237 }
238 
239 static if (BOTAN_TEST):
240 import botan.test;
241 import botan.pubkey.test;
242 import botan.pubkey.pubkey;
243 import botan.codec.hex;
244 import botan.pubkey.algo.dl_group;
245 import botan.rng.auto_rng;
246 import core.atomic;
247 import memutils.hashmap;
248 
249 private shared size_t total_tests;
250 
251 size_t testPkKeygen(RandomNumberGenerator rng)
252 {
253     size_t fails;
254     
255     string[] elg_list = ["modp/ietf/1024", "dsa/jce/1024", "dsa/botan/2048", "dsa/botan/3072"];
256     
257     foreach (elg; elg_list) {
258         atomicOp!"+="(total_tests, 1);
259         auto key = ElGamalPrivateKey(rng, DLGroup(elg));
260         key.checkKey(rng, true);
261         fails += validateSaveAndLoad(key, rng);
262     }
263     
264     return fails;
265 }
266 
267 size_t elgamalKat(string p,
268                    string g,
269                    string x,
270                    string msg,
271                    string padding,
272                    string nonce,
273                    string ciphertext)
274 {
275     atomicOp!"+="(total_tests, 1);
276 	Unique!AutoSeededRNG rng = new AutoSeededRNG;
277     
278     BigInt p_bn = BigInt(p);
279     BigInt g_bn = BigInt(g);
280     BigInt x_bn = BigInt(x);
281     
282     DLGroup group = DLGroup(p_bn, g_bn);
283     auto privkey = ElGamalPrivateKey(*rng, group.move(), x_bn.move());
284     
285     auto pubkey = ElGamalPublicKey(privkey);
286     
287     if (padding == "")
288         padding = "Raw";
289     
290     auto enc = scoped!PKEncryptorEME(pubkey, padding);
291     auto dec = scoped!PKDecryptorEME(privkey, padding);
292     
293     return validateEncryption(enc, dec, "ElGamal/" ~ padding, msg, nonce, ciphertext);
294 }
295 
296 static if (BOTAN_HAS_TESTS && !SKIP_ELGAMAL_TEST) unittest
297 {
298     logDebug("Testing elgamal.d ...");
299     size_t fails = 0;
300     
301 	Unique!AutoSeededRNG rng = new AutoSeededRNG;
302     
303     fails += testPkKeygen(*rng);
304     
305     File elgamal_enc = File("../test_data/pubkey/elgamal.vec", "r");
306     
307     fails += runTestsBb(elgamal_enc, "ElGamal Encryption", "Ciphertext", true,
308         (ref HashMap!(string, string) m) {
309             return elgamalKat(m["P"], m["G"], m["X"], m["Msg"],
310             m.get("Padding", ""), m["Nonce"], m["Ciphertext"]);
311         });
312     
313     testReport("elg", total_tests, fails);
314 }