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