1 /**
2 * GOST 34.10-2001
3 * 
4 * Copyright:
5 * (C) 2007 Falko Strenzke, FlexSecure GmbH
6 *             Manuel Hartl, FlexSecure GmbH
7 * (C) 2008-2010 Jack Lloyd
8 * (C) 2014-2015 Etienne Cimon
9 *
10 * License:
11 * Botan is released under the Simplified BSD License (see LICENSE.md)
12 */
13 module botan.pubkey.algo.gost_3410;
14 
15 import botan.constants;
16 static if (BOTAN_HAS_PUBLIC_KEY_CRYPTO && BOTAN_HAS_GOST_34_10_2001):
17 
18 public import botan.pubkey.pubkey;
19 import botan.pubkey.algo.ecc_key;
20 import botan.pubkey.pk_ops;
21 import botan.pubkey.algo.gost_3410;
22 import botan.asn1.der_enc;
23 import botan.asn1.ber_dec;
24 import botan.math.ec_gfp.point_gfp;
25 import botan.rng.rng;
26 import std.algorithm;
27 import memutils.helpers : Embed;
28 
29 struct GOST3410Options // applied to ECPublicKey
30 {
31     enum algoName = "GOST-34.10";
32     enum msgParts = 2;
33 
34     static AlgorithmIdentifier algorithmIdentifier(in ECPublicKey pkey)
35     {
36         //logTrace("Encode algorithmIdentifier x509");
37         Vector!ubyte params = DEREncoder().startCons(ASN1Tag.SEQUENCE)
38                 .encode(OID(pkey.domain().getOid()))
39                 .endCons()
40                 .getContentsUnlocked();
41         
42         return AlgorithmIdentifier(pkey.getOid(), params);
43     }
44 
45     static Vector!ubyte x509SubjectPublicKey(in ECPublicKey pkey)
46     {
47         //logTrace("Encode x509SubjectPublicKey");
48         // Trust CryptoPro to come up with something obnoxious
49         const BigInt x = pkey.publicPoint().getAffineX();
50         const BigInt y = pkey.publicPoint().getAffineY();
51         
52         size_t part_size = max(x.bytes(), y.bytes());
53         
54         Vector!ubyte bits = Vector!ubyte(2*part_size);
55         
56         x.binaryEncode(&bits[part_size - x.bytes()]);
57         y.binaryEncode(&bits[2*part_size - y.bytes()]);
58         
59         // Keys are stored in little endian format (WTF)
60         foreach (size_t i; 0 .. (part_size / 2))
61         {
62             swap(bits[i], bits[part_size-1-i]);
63             swap(bits[part_size+i], bits[2*part_size-1-i]);
64         }
65         
66         return DEREncoder().encode(bits, ASN1Tag.OCTET_STRING).getContentsUnlocked();
67     }
68 }
69 
70 /**
71 * GOST-34.10 Public Key
72 */
73 struct GOST3410PublicKey
74 {
75 public:
76     alias Options = GOST3410Options;
77     __gshared immutable algoName = Options.algoName;
78     /**
79     * Construct a public key from a given public point.
80     *
81     * Params:
82     *  dom_par = the domain parameters associated with this key
83     *  public_point = the public point defining this key
84     */
85     this(const ref ECGroup dom_par, const ref PointGFp public_point) 
86     {
87 		m_owned = true;
88         m_pub = new ECPublicKey(Options(), dom_par, public_point);
89     }
90 
91     /**
92     * Construct from X.509 algorithm id and subject public key bits
93     */
94     this(in AlgorithmIdentifier alg_id, const ref SecureVector!ubyte key_bits)
95     {
96         //logTrace("Decode public key");
97         OID ecc_param_id = OID();
98         
99         // Also includes hash and cipher OIDs... brilliant design guys
100         BERDecoder(alg_id.parameters).startCons(ASN1Tag.SEQUENCE).decode(ecc_param_id);
101         
102         ECGroup domain_params = ECGroup(ecc_param_id);
103         SecureVector!ubyte bits;
104         BERDecoder(key_bits).decode(bits, ASN1Tag.OCTET_STRING);
105         
106         const size_t part_size = bits.length / 2;
107         
108         // Keys are stored in little endian format (WTF)
109         foreach (size_t i; 0 .. (part_size / 2))
110         {
111             swap(bits[i], bits[part_size-1-i]);
112             swap(bits[part_size+i], bits[2*part_size-1-i]);
113         }
114         
115         BigInt x = BigInt(bits.ptr, part_size);
116         BigInt y = BigInt(&bits[part_size], part_size);
117         
118         PointGFp public_point = PointGFp(domain_params.getCurve(), x, y);
119 		m_owned = true;
120         m_pub = new ECPublicKey(Options(), domain_params, public_point);
121         assert(public_point.onTheCurve(), "Loaded GOST 34.10 public key is on the curve");
122     }
123 
124     this(PublicKey pkey) { m_pub = cast(ECPublicKey) pkey; }
125 
126     this(PrivateKey pkey) { m_pub = cast(ECPublicKey) pkey; }
127 
128     mixin Embed!(m_pub, m_owned);
129 
130 	bool m_owned;
131     ECPublicKey m_pub;
132 }
133 
134 /**
135 * GOST-34.10 Private Key
136 */
137 struct GOST3410PrivateKey
138 {
139 public:
140     alias Options = GOST3410Options;
141     __gshared immutable algoName = Options.algoName;
142 
143     this(in AlgorithmIdentifier alg_id, const ref SecureVector!ubyte key_bits)
144     {
145 		m_owned = true;
146         m_priv = new ECPrivateKey(Options(), alg_id, key_bits);
147     }
148 
149     /**
150     * Generate a new private key
151     * Params:
152     *  rng = a random number generator
153     *  domain = parameters to used for this key
154     *  x = the private key; if zero, a new random key is generated
155     */
156     this(RandomNumberGenerator rng, const ref ECGroup domain, BigInt x = BigInt(0))
157     {
158 		m_owned = true;
159         m_priv = new ECPrivateKey(Options(), rng, domain, x);
160     }
161 
162     this(PrivateKey pkey) { m_priv = cast(ECPrivateKey) pkey; }
163 
164     mixin Embed!(m_priv, m_owned);
165 
166 	bool m_owned;
167     ECPrivateKey m_priv;
168 }
169 
170 /**
171 * GOST-34.10 signature operation
172 */
173 final class GOST3410SignatureOperation : Signature
174 {
175 public:    
176     this(in PrivateKey pkey) {
177         this(cast(ECPrivateKey) pkey);
178     }
179 
180     this(in GOST3410PrivateKey pkey) {
181         this(pkey.m_priv);
182     }
183 
184     this(in ECPrivateKey gost_3410)
185     {
186         assert(gost_3410.algoName == GOST3410PublicKey.algoName);
187         m_base_point = &gost_3410.domain().getBasePoint();
188         m_order = &gost_3410.domain().getOrder();
189         m_x = &gost_3410.privateValue();
190     }
191 
192     override size_t messageParts() const { return 2; }
193     override size_t messagePartSize() const { return m_order.bytes(); }
194     override size_t maxInputBits() const { return m_order.bits(); }
195 
196     override SecureVector!ubyte sign(const(ubyte)* msg, size_t msg_len,
197                                       RandomNumberGenerator rng)
198     {
199         BigInt k;
200         do
201             k.randomize(rng, m_order.bits()-1);
202         while (k >= *m_order);
203         
204         BigInt e = decodeLittleEndian(msg, msg_len);
205         
206         e %= *m_order;
207         if (e == 0)
208             e = 1;
209         
210         PointGFp k_times_P = (*m_base_point) * k;
211         
212         assert(k_times_P.onTheCurve(), "GOST 34.10 k*g is on the curve");
213         
214         BigInt r = k_times_P.getAffineX() % (*m_order);
215         
216         BigInt s = (r*(*m_x) + k*e) % (*m_order);
217         
218         if (r == 0 || s == 0)
219             throw new InvalidState("GOST 34.10: r == 0 || s == 0");
220         
221         SecureVector!ubyte output = SecureVector!ubyte(2*m_order.bytes());
222         s.binaryEncode(&output[output.length / 2 - s.bytes()]);
223         r.binaryEncode(&output[output.length - r.bytes()]);
224         return output;
225     }
226 
227 private:
228     const PointGFp* m_base_point;
229     const BigInt* m_order;
230     const BigInt* m_x;
231 }
232 
233 /**
234 * GOST-34.10 verification operation
235 */
236 final class GOST3410VerificationOperation : Verification
237 {
238 public:
239     this(in PublicKey pkey) {
240         this(cast(ECPublicKey) pkey);
241     }
242 
243     this(in GOST3410PublicKey pkey) {
244         this(pkey.m_pub);
245     }
246 
247     this(in ECPublicKey gost) 
248     {
249         assert(gost.algoName == GOST3410PublicKey.algoName);
250         m_base_point = &gost.domain().getBasePoint();
251         m_public_point = &gost.publicPoint();
252         m_order = &gost.domain().getOrder();
253     }
254 
255     override size_t messageParts() const { return 2; }
256     override size_t messagePartSize() const { return m_order.bytes(); }
257     override size_t maxInputBits() const { return m_order.bits(); }
258 
259     override bool withRecovery() const { return false; }
260 
261     override SecureVector!ubyte verifyMr(const(ubyte)*, size_t) { throw new InvalidState("Message recovery not supported"); }
262     override bool verify(const(ubyte)* msg, size_t msg_len,
263                          const(ubyte)* sig, size_t sig_len)
264     {
265         if (sig_len != m_order.bytes()*2)
266             return false;
267         
268         BigInt e = decodeLittleEndian(msg, msg_len);
269         
270         BigInt s = BigInt(sig, sig_len / 2);
271         BigInt r = BigInt(sig + sig_len / 2, sig_len / 2);
272         
273         if (r <= 0 || r >= (*m_order) || s <= 0 || s >= (*m_order))
274             return false;
275         
276         e %= (*m_order);
277         if (e == 0)
278             e = 1;
279         
280         BigInt v = inverseMod(e, (*m_order));
281         
282         BigInt z1 = (s*v) % (*m_order);
283         BigInt z2 = (-r*v) % (*m_order);
284         
285         PointGFp R = PointGFp.multiExponentiate(*m_base_point, z1,
286                                                 *m_public_point, z2);
287         
288         if (R.isZero())
289             return false;
290         
291         return (R.getAffineX() == r);
292     }
293    // const ~this() { destroy(cast(GOST3410VerificationOperation)this); }
294 private:
295     const PointGFp* m_base_point;
296     const PointGFp* m_public_point;
297     const BigInt* m_order;
298 }
299 
300 
301 private:
302 
303 BigInt decodeLittleEndian(const(ubyte)* msg, size_t msg_len)
304 {
305     SecureVector!ubyte msg_le = SecureVector!ubyte(msg[0 .. msg_len]);
306     
307     for (size_t i = 0; i != msg_le.length / 2; ++i)
308         swap(msg_le[i], msg_le[msg_le.length-1-i]);
309     
310     return BigInt(msg_le.ptr, msg_le.length);
311 }
312 
313 
314 static if (BOTAN_TEST):
315 
316 import botan.test;
317 import botan.pubkey.test;
318 import botan.rng.auto_rng;
319 import botan.pubkey.pubkey;
320 import botan.asn1.oids;
321 import botan.codec.hex;
322 import core.atomic;
323 import memutils.hashmap;
324 
325 private shared size_t total_tests;
326 
327 size_t testPkKeygen(RandomNumberGenerator rng)
328 {
329     size_t fails;
330     string[] gost_list = ["gost_256A", "secp112r1", "secp128r1", "secp160r1",
331         "secp192r1", "secp224r1", "secp256r1", "secp384r1", "secp521r1"];
332     
333     foreach (gost; gost_list) {
334         atomicOp!"+="(total_tests, 1);
335         auto ec = ECGroup(OIDS.lookup(gost));
336         auto key = GOST3410PrivateKey(rng, ec);
337         key.checkKey(rng, true);
338         fails += validateSaveAndLoad(key, rng);
339     }
340     
341     return fails;
342 }
343 
344 size_t gostVerify(string group_id,
345                    string x,
346                    string hash,
347                    string msg,
348                    string signature)
349 {
350     atomicOp!"+="(total_tests, 1);
351     
352     ECGroup group = ECGroup(OIDS.lookup(group_id));
353     auto x_dec = hexDecode(x);
354     PointGFp public_point = OS2ECP(x_dec, group.getCurve());
355     
356     auto gost = GOST3410PublicKey(group, public_point);
357     
358     const string padding = "EMSA1(" ~ hash ~ ")";
359     
360     PKVerifier v = PKVerifier(gost, padding);
361     
362     if (!v.verifyMessage(hexDecode(msg), hexDecode(signature)))
363         return 1;
364     
365     return 0;
366 }
367 
368 static if (BOTAN_HAS_TESTS && !SKIP_GOST_TEST) unittest
369 {
370     logDebug("Testing gost_3410.d ...");
371     size_t fails = 0;
372 
373 	Unique!AutoSeededRNG rng = new AutoSeededRNG;
374 
375     fails += testPkKeygen(*rng);
376 
377     File ecdsa_sig = File("../test_data/pubkey/gost_3410.vec", "r");
378     
379     fails += runTestsBb(ecdsa_sig, "GOST-34.10 Signature", "Signature", true,
380         (ref HashMap!(string, string) m) {
381             return gostVerify(m["Group"], m["Pubkey"], m["Hash"], m["Msg"], m["Signature"]);
382         });
383     
384     testReport("gost_3410", total_tests, fails);
385 }
386