Line data Source code
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 0 : _gcry_ecc_gost_sign (gcry_mpi_t input, ECC_secret_key *skey,
42 : gcry_mpi_t r, gcry_mpi_t s)
43 : {
44 0 : 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 0 : if (DBG_CIPHER)
53 0 : log_mpidump ("gost sign hash ", input );
54 :
55 0 : qbits = mpi_get_nbits (skey->E.n);
56 :
57 : /* Convert the INPUT into an MPI if needed. */
58 0 : if (mpi_is_opaque (input))
59 : {
60 0 : abuf = mpi_get_opaque (input, &abits);
61 0 : rc = _gcry_mpi_scan (&hash, GCRYMPI_FMT_USG, abuf, (abits+7)/8, NULL);
62 0 : if (rc)
63 0 : return rc;
64 0 : if (abits > qbits)
65 0 : mpi_rshift (hash, hash, abits - qbits);
66 : }
67 : else
68 0 : hash = input;
69 :
70 :
71 0 : k = NULL;
72 0 : dr = mpi_alloc (0);
73 0 : sum = mpi_alloc (0);
74 0 : ke = mpi_alloc (0);
75 0 : e = mpi_alloc (0);
76 0 : x = mpi_alloc (0);
77 0 : point_init (&I);
78 :
79 0 : 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 0 : mpi_mod (e, input, skey->E.n); /* e = hash mod n */
83 :
84 0 : if (!mpi_cmp_ui (e, 0))
85 0 : 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 0 : mpi_free (k);
95 0 : k = _gcry_dsa_gen_k (skey->E.n, GCRY_STRONG_RANDOM);
96 :
97 0 : _gcry_mpi_ec_mul_point (&I, k, &skey->E.G, ctx);
98 0 : if (_gcry_mpi_ec_get_affine (x, NULL, &I, ctx))
99 : {
100 0 : if (DBG_CIPHER)
101 0 : log_debug ("ecc sign: Failed to get affine coordinates\n");
102 0 : rc = GPG_ERR_BAD_SIGNATURE;
103 0 : goto leave;
104 : }
105 0 : mpi_mod (r, x, skey->E.n); /* r = x mod n */
106 : }
107 0 : while (!mpi_cmp_ui (r, 0));
108 0 : mpi_mulm (dr, skey->d, r, skey->E.n); /* dr = d*r mod n */
109 0 : mpi_mulm (ke, k, e, skey->E.n); /* ke = k*e mod n */
110 0 : mpi_addm (s, ke, dr, skey->E.n); /* sum = (k*e+ d*r) mod n */
111 : }
112 0 : while (!mpi_cmp_ui (s, 0));
113 :
114 0 : if (DBG_CIPHER)
115 : {
116 0 : log_mpidump ("gost sign result r ", r);
117 0 : log_mpidump ("gost sign result s ", s);
118 : }
119 :
120 : leave:
121 0 : _gcry_mpi_ec_free (ctx);
122 0 : point_free (&I);
123 0 : mpi_free (x);
124 0 : mpi_free (e);
125 0 : mpi_free (ke);
126 0 : mpi_free (sum);
127 0 : mpi_free (dr);
128 0 : mpi_free (k);
129 :
130 0 : if (hash != input)
131 0 : mpi_free (hash);
132 :
133 0 : 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 0 : _gcry_ecc_gost_verify (gcry_mpi_t input, ECC_public_key *pkey,
142 : gcry_mpi_t r, gcry_mpi_t s)
143 : {
144 0 : 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 0 : if( !(mpi_cmp_ui (r, 0) > 0 && mpi_cmp (r, pkey->E.n) < 0) )
150 0 : return GPG_ERR_BAD_SIGNATURE; /* Assertion 0 < r < n failed. */
151 0 : if( !(mpi_cmp_ui (s, 0) > 0 && mpi_cmp (s, pkey->E.n) < 0) )
152 0 : return GPG_ERR_BAD_SIGNATURE; /* Assertion 0 < s < n failed. */
153 :
154 0 : x = mpi_alloc (0);
155 0 : e = mpi_alloc (0);
156 0 : z1 = mpi_alloc (0);
157 0 : z2 = mpi_alloc (0);
158 0 : v = mpi_alloc (0);
159 0 : rv = mpi_alloc (0);
160 0 : zero = mpi_alloc (0);
161 :
162 0 : point_init (&Q);
163 0 : point_init (&Q1);
164 0 : point_init (&Q2);
165 :
166 0 : 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 0 : mpi_mod (e, input, pkey->E.n); /* e = hash mod n */
170 0 : if (!mpi_cmp_ui (e, 0))
171 0 : mpi_set_ui (e, 1);
172 0 : mpi_invm (v, e, pkey->E.n); /* v = e^(-1) (mod n) */
173 0 : mpi_mulm (z1, s, v, pkey->E.n); /* z1 = s*v (mod n) */
174 0 : mpi_mulm (rv, r, v, pkey->E.n); /* rv = s*v (mod n) */
175 0 : mpi_subm (z2, zero, rv, pkey->E.n); /* z2 = -r*v (mod n) */
176 :
177 0 : _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 0 : _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 0 : _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 0 : if (!mpi_cmp_ui (Q.z, 0))
191 : {
192 0 : if (DBG_CIPHER)
193 0 : log_debug ("ecc verify: Rejected\n");
194 0 : err = GPG_ERR_BAD_SIGNATURE;
195 0 : goto leave;
196 : }
197 0 : if (_gcry_mpi_ec_get_affine (x, NULL, &Q, ctx))
198 : {
199 0 : if (DBG_CIPHER)
200 0 : log_debug ("ecc verify: Failed to get affine coordinates\n");
201 0 : err = GPG_ERR_BAD_SIGNATURE;
202 0 : goto leave;
203 : }
204 0 : mpi_mod (x, x, pkey->E.n); /* x = x mod E_n */
205 0 : if (mpi_cmp (x, r)) /* x != r */
206 : {
207 0 : if (DBG_CIPHER)
208 : {
209 0 : log_mpidump (" x", x);
210 0 : log_mpidump (" r", r);
211 0 : log_mpidump (" s", s);
212 0 : log_debug ("ecc verify: Not verified\n");
213 : }
214 0 : err = GPG_ERR_BAD_SIGNATURE;
215 0 : goto leave;
216 : }
217 0 : if (DBG_CIPHER)
218 0 : log_debug ("ecc verify: Accepted\n");
219 :
220 : leave:
221 0 : _gcry_mpi_ec_free (ctx);
222 0 : point_free (&Q2);
223 0 : point_free (&Q1);
224 0 : point_free (&Q);
225 0 : mpi_free (zero);
226 0 : mpi_free (rv);
227 0 : mpi_free (v);
228 0 : mpi_free (z2);
229 0 : mpi_free (z1);
230 0 : mpi_free (x);
231 0 : mpi_free (e);
232 0 : return err;
233 : }
|
