Use correct blocksize of 32 bytes for GOSTR3411-94 HMAC
[libgcrypt.git] / cipher / ecc-gost.c
1 /* ecc-gots.c  -  Elliptic Curve GOST signatures
2  * Copyright (C) 2007, 2008, 2010, 2011 Free Software Foundation, Inc.
3  * Copyright (C) 2013 Dmitry Eremin-Solenikov
4  *
5  * This file is part of Libgcrypt.
6  *
7  * Libgcrypt is free software; you can redistribute it and/or modify
8  * it under the terms of the GNU Lesser General Public License as
9  * published by the Free Software Foundation; either version 2.1 of
10  * the License, or (at your option) any later version.
11  *
12  * Libgcrypt is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  * GNU Lesser General Public License for more details.
16  *
17  * You should have received a copy of the GNU Lesser General Public
18  * License along with this program; if not, see <http://www.gnu.org/licenses/>.
19  */
20
21 #include <config.h>
22 #include <stdio.h>
23 #include <stdlib.h>
24 #include <string.h>
25 #include <errno.h>
26
27 #include "g10lib.h"
28 #include "mpi.h"
29 #include "cipher.h"
30 #include "context.h"
31 #include "ec-context.h"
32 #include "ecc-common.h"
33 #include "pubkey-internal.h"
34
35
36 /* Compute an GOST R 34.10-01/-12 signature.
37  * Return the signature struct (r,s) from the message hash.  The caller
38  * must have allocated R and S.
39  */
40 gpg_err_code_t
41 _gcry_ecc_gost_sign (gcry_mpi_t input, ECC_secret_key *skey,
42                      gcry_mpi_t r, gcry_mpi_t s)
43 {
44   gpg_err_code_t err = 0;
45   gcry_mpi_t k, dr, sum, ke, x, e;
46   mpi_point_struct I;
47   gcry_mpi_t hash;
48   const void *abuf;
49   unsigned int abits, qbits;
50   mpi_ec_t ctx;
51
52   if (DBG_CIPHER)
53     log_mpidump ("gost sign hash  ", input );
54
55   qbits = mpi_get_nbits (skey->E.n);
56
57   /* Convert the INPUT into an MPI if needed.  */
58   if (mpi_is_opaque (input))
59     {
60       abuf = gcry_mpi_get_opaque (input, &abits);
61       err = gpg_err_code (gcry_mpi_scan (&hash, GCRYMPI_FMT_USG,
62                                          abuf, (abits+7)/8, NULL));
63       if (err)
64         return err;
65       if (abits > qbits)
66         gcry_mpi_rshift (hash, hash, abits - qbits);
67     }
68   else
69     hash = input;
70
71
72   k = NULL;
73   dr = mpi_alloc (0);
74   sum = mpi_alloc (0);
75   ke = mpi_alloc (0);
76   e = mpi_alloc (0);
77   x = mpi_alloc (0);
78   point_init (&I);
79
80   ctx = _gcry_mpi_ec_p_internal_new (skey->E.model, skey->E.dialect, 0,
81                                      skey->E.p, skey->E.a, skey->E.b);
82
83   mpi_mod (e, input, skey->E.n); /* e = hash mod n */
84
85   if (!mpi_cmp_ui (e, 0))
86     mpi_set_ui (e, 1);
87
88   /* Two loops to avoid R or S are zero.  This is more of a joke than
89      a real demand because the probability of them being zero is less
90      than any hardware failure.  Some specs however require it.  */
91   do
92     {
93       do
94         {
95           mpi_free (k);
96           k = _gcry_dsa_gen_k (skey->E.n, GCRY_STRONG_RANDOM);
97
98           _gcry_mpi_ec_mul_point (&I, k, &skey->E.G, ctx);
99           if (_gcry_mpi_ec_get_affine (x, NULL, &I, ctx))
100             {
101               if (DBG_CIPHER)
102                 log_debug ("ecc sign: Failed to get affine coordinates\n");
103               err = GPG_ERR_BAD_SIGNATURE;
104               goto leave;
105             }
106           mpi_mod (r, x, skey->E.n);  /* r = x mod n */
107         }
108       while (!mpi_cmp_ui (r, 0));
109       mpi_mulm (dr, skey->d, r, skey->E.n); /* dr = d*r mod n  */
110       mpi_mulm (ke, k, e, skey->E.n); /* ke = k*e mod n */
111       mpi_addm (s, ke, dr, skey->E.n); /* sum = (k*e+ d*r) mod n  */
112     }
113   while (!mpi_cmp_ui (s, 0));
114
115   if (DBG_CIPHER)
116     {
117       log_mpidump ("gost sign result r ", r);
118       log_mpidump ("gost sign result s ", s);
119     }
120
121  leave:
122   _gcry_mpi_ec_free (ctx);
123   point_free (&I);
124   mpi_free (x);
125   mpi_free (e);
126   mpi_free (ke);
127   mpi_free (sum);
128   mpi_free (dr);
129   mpi_free (k);
130
131   if (hash != input)
132     mpi_free (hash);
133
134   return err;
135 }
136
137
138 /* Verify a GOST R 34.10-01/-12 signature.
139  * Check if R and S verifies INPUT.
140  */
141 gpg_err_code_t
142 _gcry_ecc_gost_verify (gcry_mpi_t input, ECC_public_key *pkey,
143                        gcry_mpi_t r, gcry_mpi_t s)
144 {
145   gpg_err_code_t err = 0;
146   gcry_mpi_t e, x, z1, z2, v, rv, zero;
147   mpi_point_struct Q, Q1, Q2;
148   mpi_ec_t ctx;
149
150   if( !(mpi_cmp_ui (r, 0) > 0 && mpi_cmp (r, pkey->E.n) < 0) )
151     return GPG_ERR_BAD_SIGNATURE; /* Assertion  0 < r < n  failed.  */
152   if( !(mpi_cmp_ui (s, 0) > 0 && mpi_cmp (s, pkey->E.n) < 0) )
153     return GPG_ERR_BAD_SIGNATURE; /* Assertion  0 < s < n  failed.  */
154
155   x = mpi_alloc (0);
156   e = mpi_alloc (0);
157   z1 = mpi_alloc (0);
158   z2 = mpi_alloc (0);
159   v = mpi_alloc (0);
160   rv = mpi_alloc (0);
161   zero = mpi_alloc (0);
162
163   point_init (&Q);
164   point_init (&Q1);
165   point_init (&Q2);
166
167   ctx = _gcry_mpi_ec_p_internal_new (pkey->E.model, pkey->E.dialect, 0,
168                                      pkey->E.p, pkey->E.a, pkey->E.b);
169
170   mpi_mod (e, input, pkey->E.n); /* e = hash mod n */
171   if (!mpi_cmp_ui (e, 0))
172     mpi_set_ui (e, 1);
173   mpi_invm (v, e, pkey->E.n); /* v = e^(-1) (mod n) */
174   mpi_mulm (z1, s, v, pkey->E.n); /* z1 = s*v (mod n) */
175   mpi_mulm (rv, r, v, pkey->E.n); /* rv = s*v (mod n) */
176   mpi_subm (z2, zero, rv, pkey->E.n); /* z2 = -r*v (mod n) */
177
178   _gcry_mpi_ec_mul_point (&Q1, z1, &pkey->E.G, ctx);
179 /*   log_mpidump ("Q1.x", Q1.x); */
180 /*   log_mpidump ("Q1.y", Q1.y); */
181 /*   log_mpidump ("Q1.z", Q1.z); */
182   _gcry_mpi_ec_mul_point (&Q2, z2, &pkey->Q, ctx);
183 /*   log_mpidump ("Q2.x", Q2.x); */
184 /*   log_mpidump ("Q2.y", Q2.y); */
185 /*   log_mpidump ("Q2.z", Q2.z); */
186   _gcry_mpi_ec_add_points (&Q, &Q1, &Q2, ctx);
187 /*   log_mpidump (" Q.x", Q.x); */
188 /*   log_mpidump (" Q.y", Q.y); */
189 /*   log_mpidump (" Q.z", Q.z); */
190
191   if (!mpi_cmp_ui (Q.z, 0))
192     {
193       if (DBG_CIPHER)
194           log_debug ("ecc verify: Rejected\n");
195       err = GPG_ERR_BAD_SIGNATURE;
196       goto leave;
197     }
198   if (_gcry_mpi_ec_get_affine (x, NULL, &Q, ctx))
199     {
200       if (DBG_CIPHER)
201         log_debug ("ecc verify: Failed to get affine coordinates\n");
202       err = GPG_ERR_BAD_SIGNATURE;
203       goto leave;
204     }
205   mpi_mod (x, x, pkey->E.n); /* x = x mod E_n */
206   if (mpi_cmp (x, r))   /* x != r */
207     {
208       if (DBG_CIPHER)
209         {
210           log_mpidump ("     x", x);
211           log_mpidump ("     r", r);
212           log_mpidump ("     s", s);
213           log_debug ("ecc verify: Not verified\n");
214         }
215       err = GPG_ERR_BAD_SIGNATURE;
216       goto leave;
217     }
218   if (DBG_CIPHER)
219     log_debug ("ecc verify: Accepted\n");
220
221  leave:
222   _gcry_mpi_ec_free (ctx);
223   point_free (&Q2);
224   point_free (&Q1);
225   point_free (&Q);
226   mpi_free (zero);
227   mpi_free (rv);
228   mpi_free (v);
229   mpi_free (z2);
230   mpi_free (z1);
231   mpi_free (x);
232   mpi_free (e);
233   return err;
234 }