botan.pubkey.algo.nr source code

1 /**
2 * Nyberg-Rueppel
3 * 
4 * Copyright:
5 * (C) 1999-2010 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.nr;
12 
13 import botan.constants;
14 static if (BOTAN_HAS_PUBLIC_KEY_CRYPTO && BOTAN_HAS_NYBERG_RUEPPEL):
15 
16 public import botan.pubkey.pubkey;
17 import botan.pubkey.algo.dl_algo;
18 import botan.pubkey.pk_ops;
19 import botan.math.numbertheory.numthry;
20 import botan.math.numbertheory.reducer;
21 import botan.math.numbertheory.numthry;
22 import botan.pubkey.algo.keypair;
23 import botan.rng.rng;
24 import std.concurrency;
25 import core.thread;
26 import memutils.helpers : Embed;
27 import std.algorithm : max;
28 
29 struct NROptions {
30     enum algoName = "NR";
31     enum format = DLGroup.ANSI_X9_42;
32     enum msgParts = 2;
33 
34     /*
35     * Check Private Nyberg-Rueppel Parameters
36     */
37     static bool checkKey(in DLSchemePrivateKey privkey, RandomNumberGenerator rng, bool strong)
38     {
39         if (!privkey.checkKeyImpl(rng, strong) || privkey.m_x >= privkey.groupQ())
40             return false;
41         
42         if (!strong)
43             return true;
44         
45         return signatureConsistencyCheck(rng, privkey, "EMSA1(SHA-1)");
46     }
47 
48 }
49 
50 /**
51 * Nyberg-Rueppel Public Key
52 */
53 struct NRPublicKey
54 {
55 public:
56     alias Options = NROptions;
57     __gshared immutable string algoName = Options.algoName;
58 
59     this(in AlgorithmIdentifier alg_id, const ref SecureVector!ubyte key_bits) 
60     {
61 		m_owned = true;
62         m_pub = new DLSchemePublicKey(Options(), alg_id, key_bits);
63     }
64 
65     /*
66     * NRPublicKey Constructor
67     */
68     this(DLGroup grp, BigInt y1)
69     {
70 		m_owned = true;
71         m_pub = new DLSchemePublicKey(Options(), grp.move, y1.move);
72     }
73 
74     this(PublicKey pkey) { m_pub = cast(DLSchemePublicKey) pkey; }
75     this(PrivateKey pkey) { m_pub = cast(DLSchemePublicKey) pkey; }
76 
77     mixin Embed!(m_pub, m_owned);
78 
79 	bool m_owned;
80     DLSchemePublicKey m_pub;
81 }
82 
83 /**
84 * Nyberg-Rueppel Private Key
85 */
86 struct NRPrivateKey
87 {
88 public:
89     alias Options = NROptions;
90     __gshared immutable string algoName = Options.algoName;
91 
92     /*
93     * Create a NR private key
94     */
95     this(RandomNumberGenerator rng, DLGroup grp, BigInt x_arg = BigInt(0))
96     {
97         bool x_arg_0;
98         if (x_arg == 0) {
99             x_arg_0 = true;
100             auto bi = BigInt(2);
101             x_arg = BigInt.randomInteger(rng, bi, grp.getQ() - 1);
102         }
103         BigInt y1 = powerMod(&grp.getG(), &x_arg, &grp.getP());
104 
105 		m_owned = true;
106         m_priv = new DLSchemePrivateKey(Options(), grp.move, y1.move, x_arg.move);
107 
108         if (x_arg_0)
109             m_priv.genCheck(rng);
110         else
111             m_priv.loadCheck(rng);
112     }
113 
114     this(in AlgorithmIdentifier alg_id, const ref SecureVector!ubyte key_bits, 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         
121         m_priv.loadCheck(rng);
122     }
123 
124     mixin Embed!(m_priv, m_owned);
125 
126 	bool m_owned;
127     DLSchemePrivateKey m_priv;
128 
129 }
130 
131 /**
132 * Nyberg-Rueppel signature operation
133 */
134 final class NRSignatureOperation : Signature
135 {
136 public:
137     override size_t messageParts() const { return 2; }
138     override size_t messagePartSize() const { return m_q.bytes(); }
139     override size_t maxInputBits() const { return (m_q.bits() - 1); }
140 
141     this(in PrivateKey pkey) {
142         this(cast(DLSchemePrivateKey) pkey);
143     }
144 
145     this(in NRPrivateKey pkey) {
146         this(pkey.m_priv);
147     }
148 
149     this(in DLSchemePrivateKey nr)
150     {
151         assert(nr.algoName == NRPublicKey.algoName);
152         m_nr = nr;
153         m_q = &m_nr.groupQ();
154         m_x = &m_nr.getX();
155         m_powermod_g_p = FixedBasePowerMod(&m_nr.groupG(), &m_nr.groupP());
156         m_mod_q = ModularReducer(m_nr.groupQ());
157     }
158 
159     override SecureVector!ubyte sign(const(ubyte)* msg, size_t msg_len, RandomNumberGenerator rng)
160     {
161         rng.addEntropy(msg, msg_len);
162         
163         BigInt f = BigInt(msg, msg_len);
164         
165         if (f >= *m_q)
166             throw new InvalidArgument("NR_Signature_Operation: Input is out of range");
167         
168         BigInt c, d;
169         
170         while (c == 0)
171         {
172             BigInt k;
173             do
174                 k.randomize(rng, m_q.bits());
175             while (k >= *m_q);
176             auto pow_mod = (cast()*m_powermod_g_p)(&k);
177             c = m_mod_q.reduce(pow_mod + f);
178             d = m_mod_q.reduce(k - (*m_x) * c);
179         }
180         
181         SecureVector!ubyte output = SecureVector!ubyte(2*m_q.bytes());
182         c.binaryEncode(&output[output.length / 2 - c.bytes()]);
183         d.binaryEncode(&output[output.length - d.bytes()]);
184         return output;
185     }
186 private: 
187     const DLSchemePrivateKey m_nr;
188     const BigInt* m_q;
189     const BigInt* m_x;
190     FixedBasePowerMod m_powermod_g_p;
191     ModularReducer m_mod_q;
192 }
193 
194 /**
195 * Nyberg-Rueppel verification operation
196 */
197 final class NRVerificationOperation : Verification
198 {
199 public:
200     this(in PublicKey pkey) {
201         this(cast(DLSchemePublicKey) pkey);
202     }
203 
204     this(in NRPublicKey pkey) {
205         this(pkey.m_pub);
206     }
207 
208     this(in DLSchemePublicKey nr) 
209     {
210         assert(nr.algoName == NRPublicKey.algoName);
211         m_nr = nr;
212         m_q = &nr.groupQ();
213         m_y = &nr.getY();
214         m_p = &nr.groupP();
215         m_g = &nr.groupG();
216         m_powermod_g_p = FixedBasePowerMod(m_g, m_p);
217         m_powermod_y_p = FixedBasePowerMod(m_y, m_p);
218         m_mod_p = ModularReducer(nr.groupP());
219         m_mod_q = ModularReducer(nr.groupQ());
220     }
221 
222     override size_t messageParts() const { return 2; }
223     override size_t messagePartSize() const { return m_q.bytes(); }
224     override size_t maxInputBits() const { return (m_q.bits() - 1); }
225 
226     override bool withRecovery() const { return true; }
227 
228     override bool verify(const(ubyte)*, size_t, const(ubyte)*, size_t)
229     {
230         throw new InvalidState("Message recovery required");
231     }
232 
233     override SecureVector!ubyte verifyMr(const(ubyte)* msg, size_t msg_len)
234     {
235 		//import core.memory : GC; GC.disable(); scope(exit) GC.enable();
236         const BigInt* q = &m_mod_q.getModulus(); // TODO: why not use m_q?
237         if (msg_len != 2*q.bytes())
238             throw new InvalidArgument("NR verification: Invalid signature");
239         
240         BigInt c = BigInt(msg, q.bytes());
241         BigInt d = BigInt(msg + q.bytes(), q.bytes());
242         
243         if (c.isZero() || c >= *q || d >= *q)
244             throw new InvalidArgument("NR verification: Invalid signature");
245         BigInt g_d = (cast(FixedBasePowerModImpl)*m_powermod_g_p)(&d);
246         BigInt y_p = (cast(FixedBasePowerModImpl)*m_powermod_y_p)(&c);
247 		BigInt i = m_mod_p.multiply(&g_d, &y_p);
248         return BigInt.encodeLocked(m_mod_q.reduce(c - i));
249     }
250 private:
251     const DLSchemePublicKey m_nr;
252     const BigInt* m_q;
253     const BigInt* m_y;
254     const BigInt* m_p;
255     const BigInt* m_g;
256 
257     FixedBasePowerMod m_powermod_g_p, m_powermod_y_p;
258     ModularReducer m_mod_p, m_mod_q;
259 }
260 
261 
262 static if (BOTAN_TEST):
263 
264 import botan.test;
265 import botan.pubkey.test;
266 import botan.pubkey.pubkey;
267 import botan.codec.hex;
268 import botan.rng.auto_rng;
269 import core.atomic;
270 import memutils.hashmap;
271 
272 private shared size_t total_tests;
273 
274 size_t testPkKeygen(RandomNumberGenerator rng)
275 {    
276     size_t fails;
277     string[] nr_list = ["dsa/jce/1024", "dsa/botan/2048", "dsa/botan/3072"];
278 
279     foreach (nr; nr_list) {
280         atomicOp!"+="(total_tests, 1);
281         auto key = NRPrivateKey(rng, DLGroup(nr));
282         key.checkKey(rng, true);
283         fails += validateSaveAndLoad(key, rng);
284     }
285     
286     return fails;
287 }
288 
289 size_t nrSigKat(string p, string q, string g, string x, 
290                   string hash, string msg, string nonce, string signature)
291 {
292     //logTrace("msg: ", msg);
293     atomicOp!"+="(total_tests, 1);
294 	Unique!AutoSeededRNG rng = new AutoSeededRNG;
295     
296     BigInt p_bn = BigInt(p);
297     BigInt q_bn = BigInt(q);
298     BigInt g_bn = BigInt(g);
299     BigInt x_bn = BigInt(x);
300     
301     DLGroup group = DLGroup(p_bn, q_bn, g_bn);
302 
303     auto privkey = NRPrivateKey(*rng, group.move(), x_bn.move());
304     auto pubkey = NRPublicKey(privkey);
305     
306     const string padding = "EMSA1(" ~ hash ~ ")";
307     
308     PKVerifier verify = PKVerifier(pubkey, padding);
309     PKSigner sign = PKSigner(privkey, padding);
310     
311     return validateSignature(verify, sign, "nr/" ~ hash, msg, *rng, nonce, signature);
312 }
313 
314 static if (BOTAN_HAS_TESTS && !SKIP_NR_TEST) unittest
315 {
316     logDebug("Testing nr.d ...");
317     size_t fails = 0;
318     
319 	Unique!AutoSeededRNG rng = new AutoSeededRNG;
320     
321     File nr_sig = File("test_data/pubkey/nr.vec", "r");
322     
323     fails += runTestsBb(nr_sig, "NR Signature", "Signature", true,
324         (ref HashMap!(string, string) m) {
325             return nrSigKat(m["P"], m["Q"], m["G"], m["X"], m["Hash"], m["Msg"], m["Nonce"], m["Signature"]);
326         });
327 
328     fails += testPkKeygen(*rng);
329     
330     testReport("nr", total_tests, fails);
331 }