pubkey: Re-map all depreccated RSA algo numbers.
[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 rc = 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 = mpi_get_opaque (input, &abits);
61       rc = _gcry_mpi_scan (&hash, GCRYMPI_FMT_USG, abuf, (abits+7)/8, NULL);
62       if (rc)
63         return rc;
64       if (abits > qbits)
65         mpi_rshift (hash, hash, abits - qbits);
66     }
67   else
68     hash = input;
69
70
71   k = NULL;
72   dr = mpi_alloc (0);
73   sum = mpi_alloc (0);
74   ke = mpi_alloc (0);
75   e = mpi_alloc (0);
76   x = mpi_alloc (0);
77   point_init (&I);
78
79   ctx = _gcry_mpi_ec_p_internal_new (skey->E.model, skey->E.dialect, 0,
80                                      skey->E.p, skey->E.a, skey->E.b);
81
82   mpi_mod (e, input, skey->E.n); /* e = hash mod n */
83
84   if (!mpi_cmp_ui (e, 0))
85     mpi_set_ui (e, 1);
86
87   /* Two loops to avoid R or S are zero.  This is more of a joke than
88      a real demand because the probability of them being zero is less
89      than any hardware failure.  Some specs however require it.  */
90   do
91     {
92       do
93         {
94           mpi_free (k);
95           k = _gcry_dsa_gen_k (skey->E.n, GCRY_STRONG_RANDOM);
96
97           _gcry_mpi_ec_mul_point (&I, k, &skey->E.G, ctx);
98           if (_gcry_mpi_ec_get_affine (x, NULL, &I, ctx))
99             {
100               if (DBG_CIPHER)
101                 log_debug ("ecc sign: Failed to get affine coordinates\n");
102               rc = GPG_ERR_BAD_SIGNATURE;
103               goto leave;
104             }
105           mpi_mod (r, x, skey->E.n);  /* r = x mod n */
106         }
107       while (!mpi_cmp_ui (r, 0));
108       mpi_mulm (dr, skey->d, r, skey->E.n); /* dr = d*r mod n  */
109       mpi_mulm (ke, k, e, skey->E.n); /* ke = k*e mod n */
110       mpi_addm (s, ke, dr, skey->E.n); /* sum = (k*e+ d*r) mod n  */
111     }
112   while (!mpi_cmp_ui (s, 0));
113
114   if (DBG_CIPHER)
115     {
116       log_mpidump ("gost sign result r ", r);
117       log_mpidump ("gost sign result s ", s);
118     }
119
120  leave:
121   _gcry_mpi_ec_free (ctx);
122   point_free (&I);
123   mpi_free (x);
124   mpi_free (e);
125   mpi_free (ke);
126   mpi_free (sum);
127   mpi_free (dr);
128   mpi_free (k);
129
130   if (hash != input)
131     mpi_free (hash);
132
133   return rc;
134 }
135
136
137 /* Verify a GOST R 34.10-01/-12 signature.
138  * Check if R and S verifies INPUT.
139  */
140 gpg_err_code_t
141 _gcry_ecc_gost_verify (gcry_mpi_t input, ECC_public_key *pkey,
142                        gcry_mpi_t r, gcry_mpi_t s)
143 {
144   gpg_err_code_t err = 0;
145   gcry_mpi_t e, x, z1, z2, v, rv, zero;
146   mpi_point_struct Q, Q1, Q2;
147   mpi_ec_t ctx;
148
149   if( !(mpi_cmp_ui (r, 0) > 0 && mpi_cmp (r, pkey->E.n) < 0) )
150     return GPG_ERR_BAD_SIGNATURE; /* Assertion  0 < r < n  failed.  */
151   if( !(mpi_cmp_ui (s, 0) > 0 && mpi_cmp (s, pkey->E.n) < 0) )
152     return GPG_ERR_BAD_SIGNATURE; /* Assertion  0 < s < n  failed.  */
153
154   x = mpi_alloc (0);
155   e = mpi_alloc (0);
156   z1 = mpi_alloc (0);
157   z2 = mpi_alloc (0);
158   v = mpi_alloc (0);
159   rv = mpi_alloc (0);
160   zero = mpi_alloc (0);
161
162   point_init (&Q);
163   point_init (&Q1);
164   point_init (&Q2);
165
166   ctx = _gcry_mpi_ec_p_internal_new (pkey->E.model, pkey->E.dialect, 0,
167                                      pkey->E.p, pkey->E.a, pkey->E.b);
168
169   mpi_mod (e, input, pkey->E.n); /* e = hash mod n */
170   if (!mpi_cmp_ui (e, 0))
171     mpi_set_ui (e, 1);
172   mpi_invm (v, e, pkey->E.n); /* v = e^(-1) (mod n) */
173   mpi_mulm (z1, s, v, pkey->E.n); /* z1 = s*v (mod n) */
174   mpi_mulm (rv, r, v, pkey->E.n); /* rv = s*v (mod n) */
175   mpi_subm (z2, zero, rv, pkey->E.n); /* z2 = -r*v (mod n) */
176
177   _gcry_mpi_ec_mul_point (&Q1, z1, &pkey->E.G, ctx);
178 /*   log_mpidump ("Q1.x", Q1.x); */
179 /*   log_mpidump ("Q1.y", Q1.y); */
180 /*   log_mpidump ("Q1.z", Q1.z); */
181   _gcry_mpi_ec_mul_point (&Q2, z2, &pkey->Q, ctx);
182 /*   log_mpidump ("Q2.x", Q2.x); */
183 /*   log_mpidump ("Q2.y", Q2.y); */
184 /*   log_mpidump ("Q2.z", Q2.z); */
185   _gcry_mpi_ec_add_points (&Q, &Q1, &Q2, ctx);
186 /*   log_mpidump (" Q.x", Q.x); */
187 /*   log_mpidump (" Q.y", Q.y); */
188 /*   log_mpidump (" Q.z", Q.z); */
189
190   if (!mpi_cmp_ui (Q.z, 0))
191     {
192       if (DBG_CIPHER)
193           log_debug ("ecc verify: Rejected\n");
194       err = GPG_ERR_BAD_SIGNATURE;
195       goto leave;
196     }
197   if (_gcry_mpi_ec_get_affine (x, NULL, &Q, ctx))
198     {
199       if (DBG_CIPHER)
200         log_debug ("ecc verify: Failed to get affine coordinates\n");
201       err = GPG_ERR_BAD_SIGNATURE;
202       goto leave;
203     }
204   mpi_mod (x, x, pkey->E.n); /* x = x mod E_n */
205   if (mpi_cmp (x, r))   /* x != r */
206     {
207       if (DBG_CIPHER)
208         {
209           log_mpidump ("     x", x);
210           log_mpidump ("     r", r);
211           log_mpidump ("     s", s);
212           log_debug ("ecc verify: Not verified\n");
213         }
214       err = GPG_ERR_BAD_SIGNATURE;
215       goto leave;
216     }
217   if (DBG_CIPHER)
218     log_debug ("ecc verify: Accepted\n");
219
220  leave:
221   _gcry_mpi_ec_free (ctx);
222   point_free (&Q2);
223   point_free (&Q1);
224   point_free (&Q);
225   mpi_free (zero);
226   mpi_free (rv);
227   mpi_free (v);
228   mpi_free (z2);
229   mpi_free (z1);
230   mpi_free (x);
231   mpi_free (e);
232   return err;
233 }