botan.pubkey.algo.rw source code

1 /**
2 * Rabin-Williams
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.rw;
12 
13 import botan.constants;
14 static if (BOTAN_HAS_PUBLIC_KEY_CRYPTO && BOTAN_HAS_RW):
15 
16 public import botan.pubkey.pubkey;
17 import botan.pubkey.algo.if_algo;
18 import botan.pubkey.pk_ops;
19 import botan.math.numbertheory.reducer;
20 import botan.pubkey.blinding;
21 import botan.math.numbertheory.numthry;
22 import botan.pubkey.algo.keypair;
23 import botan.utils.parsing;
24 import botan.utils.types;
25 import memutils.helpers;
26 import std.algorithm;
27 import std.concurrency;
28 import core.thread;
29 
30 struct RWOptions {
31     enum algoName = "RW";
32 
33     /*
34     * Check Private Rabin-Williams Parameters
35     */
36     static bool checkKey(in IFSchemePrivateKey privkey, RandomNumberGenerator rng, bool strong)
37     {
38         if (!privkey.checkKeyImpl(rng, strong))
39             return false;
40         
41         if (!strong)
42             return true;
43         
44         auto p_minus_1 = privkey.getP() - 1;
45         auto q_minus_1 = privkey.getQ() - 1;
46         auto arg1 = (privkey.getE() * privkey.getD());
47         auto arg2 = (lcm(&p_minus_1, &q_minus_1) >> 1);
48         auto mod_res = arg1 % arg2;
49         logTrace(mod_res.toString());
50         import botan.math.bigint.divide;
51         BigInt q, r;
52         logTrace("Calling divide with arg1arg2:");
53         logTrace(arg1.toString());
54         logTrace(arg2.toString());
55         divide(&arg1, &arg2, &q, &r, true);
56         logTrace(r.toString());
57 
58         if (mod_res != 1)
59             return false;
60                
61         return signatureConsistencyCheck(rng, privkey, "EMSA2(SHA-1)");
62     }
63 }
64 /**
65 * Rabin-Williams Public Key
66 */
67 struct RWPublicKey
68 {
69 public:
70     alias Options = RWOptions;
71     __gshared immutable string algoName = Options.algoName;
72 
73     this(in AlgorithmIdentifier alg_id, const ref SecureVector!ubyte key_bits)
74     {
75 		m_owned = true;
76         m_pub = new IFSchemePublicKey(Options(), alg_id, key_bits);
77     }
78 
79     this(BigInt mod, BigInt exponent)
80     {
81 		m_owned = true;
82         m_pub = new IFSchemePublicKey(Options(), mod.move(), exponent.move());
83     }
84 
85     this(PrivateKey pkey) { m_pub = cast(IFSchemePublicKey) pkey; }
86     this(PublicKey pkey) { m_pub = cast(IFSchemePublicKey) pkey; }
87 
88     mixin Embed!(m_pub, m_owned);
89 
90 	bool m_owned;
91     IFSchemePublicKey m_pub;
92 }
93 
94 /**
95 * Rabin-Williams Private Key
96 */
97 struct RWPrivateKey
98 {
99 public:
100     alias Options = RWOptions;
101     __gshared immutable string algoName = Options.algoName;
102 
103     this(in AlgorithmIdentifier alg_id,
104          const ref SecureVector!ubyte key_bits,
105          RandomNumberGenerator rng) 
106     {
107 		m_owned = true;
108         m_priv = new IFSchemePrivateKey(Options(), rng, alg_id, key_bits);
109     }
110 
111     this(RandomNumberGenerator rng,
112          BigInt p, BigInt q,
113          BigInt e, BigInt d = BigInt(0),
114          BigInt n = BigInt(0))
115     {
116 		m_owned = true;
117         m_priv = new IFSchemePrivateKey(Options(), rng, p.move(), q.move(), e.move(), d.move(), n.move());
118     }
119 
120     /*
121     * Create a Rabin-Williams private key
122     */
123     this(RandomNumberGenerator rng, size_t bits, size_t exp = 2)
124     {
125         if (bits < 1024)
126             throw new InvalidArgument(algoName ~ ": Can't make a key that is only " ~
127                                        to!string(bits) ~ " bits long");
128         if (exp < 2 || exp % 2 == 1)
129             throw new InvalidArgument(algoName ~ ": Invalid encryption exponent");
130 
131         BigInt p, q, e, d, n, d1, d2;
132 
133         e = exp;
134         
135         do
136         {
137             p = randomPrime(rng, (bits + 1) / 2, e / 2, 3, 4);
138             q = randomPrime(rng, bits - p.bits(), e / 2, ((p % 8 == 3) ? 7 : 3), 8);
139             n = p * q;
140         } while (n.bits() != bits);
141         auto p_minus_1 = p-1;
142         auto q_minus_1 = q-1;    
143         auto d_0 = lcm(&p_minus_1, &q_minus_1);
144         d_0 >>= 1;
145         d = inverseMod(&e, &d_0);
146 
147 		m_owned = true;
148         m_priv = new IFSchemePrivateKey(Options(), rng, p.move(), q.move(), e.move(), d.move(), n.move());
149 
150         genCheck(rng);
151     }
152 
153     mixin Embed!(m_priv, m_owned);
154 
155     this(PrivateKey pkey) { m_priv = cast(IFSchemePrivateKey) pkey; }
156 	bool m_owned;
157     IFSchemePrivateKey m_priv;
158 }
159 
160 /**
161 * Rabin-Williams Signature Operation
162 */
163 final class RWSignatureOperation : Signature
164 {
165 public:
166     this(in RWPrivateKey pkey) {
167         this(pkey.m_priv);
168     }
169 
170     this(in PrivateKey pkey) {
171         this(cast(IFSchemePrivateKey) pkey);
172     }
173 
174     this(in IFSchemePrivateKey rw) 
175     {
176         assert(rw.algoName == RWPublicKey.algoName);
177         m_priv_key = rw;
178         m_n = &m_priv_key.getN();
179         m_e = &m_priv_key.getE();
180         m_q = &m_priv_key.getQ();
181         m_c = &m_priv_key.getC();
182         m_d1 = &m_priv_key.getD1();
183         m_p = &m_priv_key.getP();
184         m_powermod_d1_p = FixedExponentPowerMod(m_d1, m_p);
185         m_powermod_d2_q = FixedExponentPowerMod(&m_priv_key.getD2(), m_q);
186         m_mod_p = ModularReducer(*m_p);
187     }
188     override size_t messageParts() const { return 1; }
189     override size_t messagePartSize() const { return 0; }
190     override size_t maxInputBits() const { return (m_n.bits() - 1); }
191 
192     override SecureVector!ubyte sign(const(ubyte)* msg, size_t msg_len, RandomNumberGenerator rng)
193     {
194 		import core.memory : GC; GC.disable(); scope(exit) GC.enable();
195 		import core.thread;
196         rng.addEntropy(msg, msg_len);
197 
198         if (!m_blinder.initialized()) { // initialize here because we need rng
199             BigInt k = BigInt(rng, std.algorithm.min(160, m_n.bits() - 1));
200             auto e = powerMod(&k, m_e, m_n);
201             m_blinder = Blinder(e, inverseMod(&k, m_n), *m_n);
202         }
203 
204         BigInt i = BigInt(msg, msg_len);
205         
206         if (i >= *m_n || i % 16 != 12)
207             throw new InvalidArgument("Rabin-Williams: invalid input");
208         
209         if (jacobi(&i, m_n) != 1)
210             i >>= 1;        
211         i = m_blinder.blind(i);
212         const BigInt j1 = (cast(FixedExponentPowerModImpl)*m_powermod_d1_p)(cast(BigInt*)&i);
213 		const BigInt j2 = (cast(FixedExponentPowerModImpl)*m_powermod_d2_q)(cast(BigInt*)&i);		
214 		BigInt j3 = m_mod_p.reduce(subMul(&j1, &j2, m_c));
215         BigInt r = m_blinder.unblind(mulAdd(&j3, m_q, &j2)); 
216         BigInt cmp2 = *m_n - r;
217         BigInt min_val = r.move();
218         if (cmp2 < min_val)
219             min_val = cmp2.move();
220         auto ret = BigInt.encode1363(&min_val, m_n.bytes());
221         return ret;
222     }
223 private:
224     const IFSchemePrivateKey m_priv_key;
225     const BigInt* m_n;
226     const BigInt* m_e;
227     const BigInt* m_q;
228     const BigInt* m_c;
229     const BigInt* m_d1;
230     const BigInt* m_p;
231 
232     FixedExponentPowerMod m_powermod_d1_p, m_powermod_d2_q;
233     ModularReducer m_mod_p;
234     Blinder m_blinder;
235 }
236 
237 /**
238 * Rabin-Williams Verification Operation
239 */
240 final class RWVerificationOperation : Verification
241 {
242 public:
243     this(in PublicKey pkey) {
244         this(cast(IFSchemePublicKey) pkey);
245     }
246 
247     this(in RWPublicKey pkey) {
248         this(pkey.m_pub);
249     }
250 
251     this(in IFSchemePublicKey rw)
252     {
253         assert(rw.algoName == RWPublicKey.algoName);
254         m_n = &rw.getN();
255         m_e = &rw.getE();
256         m_powermod_e_n = FixedExponentPowerMod(m_e, m_n);
257     }
258     override size_t messageParts() const { return 1; }
259     override size_t messagePartSize() const { return 0; }
260     override size_t maxInputBits() const { return (m_n.bits() - 1); }
261     override bool withRecovery() const { return true; }
262 
263     override bool verify(const(ubyte)*, size_t, const(ubyte)*, size_t)
264     {
265         throw new InvalidState("Message recovery required");
266     }
267 
268     override SecureVector!ubyte verifyMr(const(ubyte)* msg, size_t msg_len)
269     {
270         BigInt m = BigInt(msg, msg_len);
271         
272         if ((m > (*m_n >> 1)) || m.isNegative())
273             throw new InvalidArgument("RW signature verification: m > n / 2 || m < 0");
274         m_powermod_e_n = FixedExponentPowerMod(m_e, m_n);
275         BigInt r = (cast()*m_powermod_e_n)(cast(BigInt*)&m);
276         if (r % 16 == 12)
277             return BigInt.encodeLocked(&r);
278         if (r % 8 == 6)
279             return BigInt.encodeLocked(r*2);
280         
281         r = (*m_n) - r;
282         if (r % 16 == 12)
283             return BigInt.encodeLocked(&r);
284         if (r % 8 == 6)
285             return BigInt.encodeLocked(r*2);
286         
287         throw new InvalidArgument("RW signature verification: Invalid signature");
288     }
289 
290 private:
291     const BigInt* m_n;
292     const BigInt* m_e;
293     FixedExponentPowerMod m_powermod_e_n;
294 }
295 
296 
297 static if (BOTAN_TEST):
298 import botan.test;
299 import botan.pubkey.test;
300 import botan.rng.auto_rng;
301 import botan.codec.hex;
302 import core.atomic;
303 import memutils.hashmap;
304 
305 shared size_t total_tests;
306 __gshared immutable string padding = "EMSA2(SHA-1)";
307 
308 size_t testPkKeygen(RandomNumberGenerator rng)
309 {
310     atomicOp!"+="(total_tests, 1);
311     size_t fails;
312     auto rw1024 = RWPrivateKey(rng, 1024);
313     rw1024.checkKey(rng, true);
314     fails += validateSaveAndLoad(rw1024, rng);
315     return fails;
316 }
317 size_t rwSigKat(string e,
318                   string p,
319                   string q,
320                   string msg,
321                   string signature)
322 {
323     atomicOp!"+="(total_tests, 1);
324 	Unique!AutoSeededRNG rng = new AutoSeededRNG;
325     
326     auto privkey = RWPrivateKey(*rng, BigInt(p), BigInt(q), BigInt(e));
327     
328     auto pubkey = RWPublicKey(privkey);
329     
330     PKVerifier verify = PKVerifier(pubkey, padding);
331     PKSigner sign = PKSigner(privkey, padding);
332     
333     return validateSignature(verify, sign, "RW/" ~ padding, msg, *rng, signature);
334 }
335 
336 size_t rwSigVerify(string e,
337                      string n,
338                      string msg,
339                      string signature)
340 {
341     atomicOp!"+="(total_tests, 1);
342 
343     BigInt e_bn = BigInt(e);
344     BigInt n_bn = BigInt(n);
345     
346     auto key = RWPublicKey(n_bn.move(), e_bn.move());
347     
348     PKVerifier verify = PKVerifier(key, padding);
349     
350     if (!verify.verifyMessage(hexDecode(msg), hexDecode(signature)))
351         return 1;
352     return 0;
353 }
354 
355 static if (BOTAN_HAS_TESTS && !SKIP_RW_TEST) unittest
356 {
357 	import core.thread : Thread;
358 	//Thread.sleep(10.seconds);
359     logDebug("Testing rw.d ...");
360     size_t fails = 0;
361     
362 	Unique!AutoSeededRNG rng = new AutoSeededRNG;
363     
364     fails += testPkKeygen(*rng);
365     
366     File rw_sig = File("test_data/pubkey/rw_sig.vec", "r");
367     File rw_verify = File("test_data/pubkey/rw_verify.vec", "r");
368     
369     fails += runTestsBb(rw_sig, "RW Signature", "Signature", true,
370         (ref HashMap!(string, string) m) {
371             return rwSigKat(m["E"], m["P"], m["Q"], m["Msg"], m["Signature"]);
372         });
373     
374     fails += runTestsBb(rw_verify, "RW Verify", "Signature", true,
375         (ref HashMap!(string, string) m) {
376             return rwSigVerify(m["E"], m["N"], m["Msg"], m["Signature"]);
377         });
378 
379     testReport("rw", total_tests, fails);
380 }