Embedded SDK
Embedded SDK
Loading...
Searching...
No Matches
cx_ecschnorr.c
Go to the documentation of this file.
1
2/*******************************************************************************
3 * Ledger Nano S - Secure firmware
4 * (c) 2022 Ledger
5 *
6 * Licensed under the Apache License, Version 2.0 (the "License");
7 * you may not use this file except in compliance with the License.
8 * You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 ********************************************************************************/
18
19#ifdef HAVE_ECSCHNORR
20
21#include "cx_rng.h"
22#include "cx_ecfp.h"
23#include "cx_eddsa.h"
24#include "cx_hash.h"
25#include "cx_utils.h"
26#include "cx_ram.h"
27
28#include <string.h>
29
30// const char kr[] = {0xe5, 0xa8, 0xd1, 0xd5, 0x29, 0x97, 0x1c, 0x10, 0xca, 0x2a, 0xf3, 0x78, 0x44,
31// 0x4f, 0xb5, 0x44, 0xa2, 0x11, 0x70, 0x78, 0x92, 0xc8, 0x89, 0x8f, 0x91, 0xdc, 0xb1, 0x71, 0x58,
32// 0x4e, 0x3d, 0xb9};
33
34/* BIP0340 tags for computing the tagged hashes */
35const uint8_t BIP0340_challenge[]
36 = {'B', 'I', 'P', '0', '3', '4', '0', '/', 'c', 'h', 'a', 'l', 'l', 'e', 'n', 'g', 'e'};
37const uint8_t BIP0340_aux[] = {'B', 'I', 'P', '0', '3', '4', '0', '/', 'a', 'u', 'x'};
38const uint8_t BIP0340_nonce[] = {'B', 'I', 'P', '0', '3', '4', '0', '/', 'n', 'o', 'n', 'c', 'e'};
39
40cx_err_t cx_ecschnorr_sign_no_throw(const cx_ecfp_private_key_t *pv_key,
41 uint32_t mode,
42 cx_md_t hashID,
43 const uint8_t *msg,
44 size_t msg_len,
45 uint8_t *sig,
46 size_t *sig_len)
47{
48#define CX_MAX_TRIES 100
49#define H G_cx.sha256
50
51 size_t size;
52 cx_ecpoint_t Q;
53 cx_bn_t bn_k, bn_d, bn_r, bn_s, bn_n;
54 uint8_t R[33];
55 uint8_t S[32];
56 uint8_t P[32];
57 int odd;
58 uint8_t tries;
59 cx_err_t error;
60 int diff;
61
62 CX_CHECK(cx_ecdomain_parameters_length(pv_key->curve, &size));
63
64 // Only secp256k1 is allowed when using CX_ECSCHNORR_BIP0340
65 if (((mode & CX_MASK_EC) == CX_ECSCHNORR_BIP0340) && (pv_key->curve != CX_CURVE_SECP256K1)) {
66 return CX_EC_INVALID_CURVE;
67 }
68
69 // WARN: only accept weierstrass 256 bits curve for now
70 if (hashID != CX_SHA256 || size != 32 || !CX_CURVE_RANGE(pv_key->curve, WEIERSTRASS)
71 || pv_key->d_len != size) {
72 return CX_INVALID_PARAMETER;
73 }
74
75 // Schnorr BIP0340 signature is not DER encoded and is 64-byte long.
76 if (((mode & CX_MASK_EC) != CX_ECSCHNORR_BIP0340) && (*sig_len < (6 + 2 * (size + 1)))) {
77 return CX_INVALID_PARAMETER;
78 }
79
80 CX_CHECK(cx_bn_lock(size, 0));
81 CX_CHECK(cx_bn_alloc(&bn_n, size));
82 CX_CHECK(cx_ecdomain_parameter_bn(pv_key->curve, CX_CURVE_PARAM_Order, bn_n));
83 CX_CHECK(cx_bn_alloc(&bn_k, size));
84 CX_CHECK(cx_bn_alloc(&bn_d, size));
85 CX_CHECK(cx_bn_alloc(&bn_r, size));
86 CX_CHECK(cx_bn_alloc(&bn_s, size));
87 CX_CHECK(cx_ecpoint_alloc(&Q, pv_key->curve));
88
89 if ((mode & CX_MASK_EC) == CX_ECSCHNORR_BIP0340) {
90 // Q = [d].G
91 CX_CHECK(cx_ecdomain_generator_bn(pv_key->curve, &Q));
92 CX_CHECK(cx_ecpoint_rnd_fixed_scalarmul(&Q, pv_key->d, size));
93 // If Qy is even use d otherwise use n-d
94 CX_CHECK(cx_bn_init(bn_d, pv_key->d, size));
95 CX_CHECK(cx_ecpoint_export(&Q, NULL, 0, P, size));
96 odd = P[size - 1] & 1;
97 if (odd) {
98 CX_CHECK(cx_bn_sub(bn_d, bn_n, bn_d));
99 }
100 // tag_hash = SHA256("BIP0340/aux")
101 // SHA256(tag_hash || tag_hash || aux_rnd)
102 cx_sha256_init_no_throw(&H);
103 CX_CHECK(
104 cx_hash_no_throw((cx_hash_t *) &H, CX_LAST, BIP0340_aux, sizeof(BIP0340_aux), R, size));
105 cx_sha256_init_no_throw(&H);
106 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, R, size, NULL, 0));
107 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, R, size, NULL, 0));
108 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, CX_LAST | CX_NO_REINIT, sig, size, R, size));
109 // t = d ^ SHA256(tag_hash || tag_hash || aux_rnd)
110 CX_CHECK(cx_bn_init(bn_k, R, size));
111 CX_CHECK(cx_bn_xor(bn_r, bn_d, bn_k));
112 CX_CHECK(cx_bn_export(bn_r, sig, size));
113 // tag_hash = SHA256("BIP0340/nonce")
114 // SHA256(tag_hash || tag_hash || t || Qx || msg)
115 cx_sha256_init_no_throw(&H);
116 CX_CHECK(cx_hash_no_throw(
117 (cx_hash_t *) &H, CX_LAST, BIP0340_nonce, sizeof(BIP0340_nonce), R, size));
118 cx_sha256_init_no_throw(&H);
119 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, R, size, NULL, 0));
120 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, R, size, NULL, 0));
121 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, sig, size, NULL, 0));
122 CX_CHECK(cx_ecpoint_export(&Q, P, size, NULL, 0));
123 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, P, size, NULL, 0));
124 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, CX_LAST | CX_NO_REINIT, msg, size, sig, size));
125 }
126
127 // generate random
128 tries = 0;
129RETRY:
130 if (tries == CX_MAX_TRIES) {
131 goto end;
132 }
133
134 switch (mode & CX_MASK_RND) {
135 case CX_RND_PROVIDED:
136 if (tries) {
137 goto end;
138 }
139 CX_CHECK(cx_bn_init(bn_r, sig, size));
140 CX_CHECK(cx_bn_reduce(bn_k, bn_r, bn_n));
141 break;
142
143 case CX_RND_TRNG:
144 CX_CHECK(cx_bn_rng(bn_k, bn_n));
145 break;
146
147 default:
148 error = CX_INVALID_PARAMETER;
149 goto end;
150 }
151 if ((mode & CX_MASK_EC) == CX_ECSCHNORR_BIP0340) {
152 CX_CHECK(cx_bn_cmp_u32(bn_k, 0, &diff));
153 if (diff == 0) {
154 error = CX_INVALID_PARAMETER;
155 goto end;
156 }
157 }
158 CX_CHECK(cx_bn_export(bn_k, sig, size));
159
160 // sign
161 tries++;
162RETRY2:
163 CX_CHECK(cx_ecdomain_generator_bn(pv_key->curve, &Q));
164 CX_CHECK(cx_ecpoint_rnd_fixed_scalarmul(&Q, sig, size));
165
166 switch (mode & CX_MASK_EC) {
167 case CX_ECSCHNORR_ISO14888_XY:
168 case CX_ECSCHNORR_ISO14888_X:
169 // 1. Generate a random k from [1, ..., order-1]
170 // 2. Q = G*k
171 // 3. r = H(Q.x||Q.y||M)
172 // 4. s = (k+r*pv_key.d)%n
173 cx_sha256_init_no_throw(&H);
174 CX_CHECK(cx_ecpoint_export(&Q, sig, size, NULL, 0));
175 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, sig, size, NULL, 0));
176 if ((mode & CX_MASK_EC) == CX_ECSCHNORR_ISO14888_XY) {
177 CX_CHECK(cx_ecpoint_export(&Q, NULL, 0, sig, size));
178 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, sig, size, NULL, 0));
179 }
180 CX_CHECK(cx_hash_no_throw(
181 (cx_hash_t *) &H, CX_LAST | CX_NO_REINIT, msg, msg_len, R, sizeof(R)));
182
183 CX_CHECK(cx_bn_init(bn_d, R, 32));
184 CX_CHECK(cx_bn_reduce(bn_r, bn_d, bn_n));
185 CX_CHECK(cx_bn_cmp_u32(bn_r, 0, &diff));
186 if (diff == 0) {
187 cx_bn_unlock();
188 goto RETRY;
189 }
190
191 CX_CHECK(cx_bn_init(bn_d, pv_key->d, pv_key->d_len));
192 CX_CHECK(cx_bn_mod_mul(bn_s, bn_d, bn_r, bn_n));
193 CX_CHECK(cx_bn_mod_add(bn_s, bn_k, bn_s, bn_n));
194 CX_CHECK(cx_bn_set_u32(bn_k, 0));
195 CX_CHECK(cx_bn_mod_sub(bn_s, bn_s, bn_k, bn_n));
196
197 CX_CHECK(cx_bn_cmp_u32(bn_s, 0, &diff));
198 if (diff == 0) {
199 goto RETRY;
200 }
201 CX_CHECK(cx_bn_export(bn_s, S, 32));
202 break;
203
204 case CX_ECSCHNORR_BSI03111:
205 // 1. Q = G*k
206 // 2. r = H((msg+xQ), and r%n != 0
207 // 3. s = (k-r*pv_key.d)%n
208 // r = H((msg+xQ), and r%n != 0
209 cx_sha256_init_no_throw(&H);
210 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, msg, msg_len, NULL, 0));
211 CX_CHECK(cx_ecpoint_export(&Q, sig, size, NULL, 0));
212 CX_CHECK(cx_hash_no_throw(
213 (cx_hash_t *) &H, CX_LAST | CX_NO_REINIT, sig, size, R, sizeof(R)));
214
215 CX_CHECK(cx_bn_init(bn_d, R, CX_SHA256_SIZE));
216 CX_CHECK(cx_bn_reduce(bn_r, bn_d, bn_n));
217 CX_CHECK(cx_bn_cmp_u32(bn_r, 0, &diff));
218 if (diff == 0) {
219 goto RETRY;
220 }
221
222 // s = (k-r*pv_key.d)%n
223 CX_CHECK(cx_bn_init(bn_d, pv_key->d, pv_key->d_len));
224 CX_CHECK(cx_bn_mod_mul(bn_s, bn_d, bn_r, bn_n));
225 CX_CHECK(cx_bn_mod_sub(bn_s, bn_k, bn_s, bn_n));
226
227 CX_CHECK(cx_bn_cmp_u32(bn_s, 0, &diff));
228 if (diff == 0) {
229 goto RETRY;
230 }
231 CX_CHECK(cx_bn_export(bn_s, S, 32));
232 break;
233
234 case CX_ECSCHNORR_Z:
235 // https://github.com/Zilliqa/Zilliqa/blob/master/src/libCrypto/Schnorr.cpp#L580
236 // https://docs.zilliqa.com/whitepaper.pdf
237 // 1. Generate a random k from [1, ..., order-1]
238 // 2. Compute the commitment Q = kG, where G is the base point
239 // 3. Compute the challenge r = H(Q, kpub, m) [CME: mod n according to pdf/code, Q and
240 // kpub compressed "02|03 x" according to code)
241 // 4. If r = 0 mod(order), goto 1
242 // 4. Compute s = k - r*kpriv mod(order)
243 // 5. If s = 0 goto 1.
244 // 5 Signature on m is (r, s)
245
246 // Q
247 cx_sha256_init_no_throw(&H);
248 CX_CHECK(cx_ecpoint_export(&Q, NULL, 0, sig, size));
249 odd = sig[size - 1] & 1;
250 CX_CHECK(cx_ecpoint_export(&Q, sig + 1, size, NULL, 0));
251 sig[0] = odd ? 0x03 : 0x02;
252 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, sig, 1 + size, NULL, 0)); // Q
253 // kpub
254 CX_CHECK(cx_ecdomain_generator_bn(pv_key->curve, &Q));
255 CX_CHECK(cx_ecpoint_rnd_fixed_scalarmul(&Q, pv_key->d, pv_key->d_len));
256 CX_CHECK(cx_ecpoint_export(&Q, NULL, 0, sig, size));
257 odd = sig[size - 1] & 1;
258 CX_CHECK(cx_ecpoint_export(&Q, sig + 1, size, NULL, 0));
259 sig[0] = odd ? 0x03 : 0x02;
260 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, sig, 1 + size, NULL, 0)); // Q
261 // m
262 CX_CHECK(cx_hash_no_throw(
263 (cx_hash_t *) &H, CX_LAST | CX_NO_REINIT, msg, msg_len, R, sizeof(R)));
264
265 // Compute the challenge r = H(Q, kpub, m)
266 //[CME: mod n according to pdf/code, Q and kpub compressed "02|03 x" according to code)
267 CX_CHECK(cx_bn_init(bn_d, R, CX_SHA256_SIZE));
268 CX_CHECK(cx_bn_reduce(bn_r, bn_d, bn_n));
269 CX_CHECK(cx_bn_cmp_u32(bn_r, 0, &diff));
270 if (diff == 0) {
271 goto RETRY;
272 }
273 CX_CHECK(cx_bn_export(bn_r, R, 32));
274
275 CX_CHECK(cx_bn_init(bn_d, pv_key->d, pv_key->d_len));
276 CX_CHECK(cx_bn_mod_mul(bn_s, bn_d, bn_r, bn_n));
277 CX_CHECK(cx_bn_mod_sub(bn_s, bn_k, bn_s, bn_n));
278 CX_CHECK(cx_bn_cmp_u32(bn_s, 0, &diff));
279 if (diff == 0) {
280 goto RETRY;
281 }
282 CX_CHECK(cx_bn_export(bn_s, S, 32));
283 break;
284
285 case CX_ECSCHNORR_LIBSECP:
286 // Inputs: 32-byte message m, 32-byte scalar key x (!=0), 32-byte scalar nonce k (!=0)
287 // 1. Compute point R = k * G. Reject nonce if R's y coordinate is odd (or negate
288 // nonce).
289 // 2. Compute 32-byte r, the serialization of R's x coordinate.
290 // 3. Compute scalar h = Hash(r || m). Reject nonce if h == 0 or h >= order.
291 // 4. Compute scalar s = k - h * x.
292 // 5. The signature is (r, s).
293 // Q = G*k
294 CX_CHECK(cx_ecpoint_export(&Q, NULL, 0, sig, size));
295 odd = sig[size - 1] & 1;
296 if (odd) {
297 // if y is odd, k <- -k mod n = n-k, and retry
298 CX_CHECK(cx_bn_mod_sub(bn_k, bn_n, bn_k, bn_n));
299 CX_CHECK(cx_bn_export(bn_k, sig, size));
300 goto RETRY2;
301 }
302 // r = xQ
303 CX_CHECK(cx_ecpoint_export(&Q, R, size, NULL, 0));
304 CX_CHECK(cx_bn_init(bn_d, R, size));
305 CX_CHECK(cx_bn_reduce(bn_r, bn_d, bn_n));
306 CX_CHECK(cx_bn_cmp_u32(bn_r, 0, &diff));
307 if (diff == 0) {
308 goto RETRY;
309 }
310 // h = Hash(r || m).
311 cx_sha256_init_no_throw(&H);
312 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, R, size, NULL, 0));
313 CX_CHECK(cx_hash_no_throw(
314 (cx_hash_t *) &H, CX_LAST | CX_NO_REINIT, msg, msg_len, sig, sizeof(S)));
315 // Reject nonce if h == 0 or h >= order.
316 CX_CHECK(cx_bn_init(bn_r, sig, 32));
317 CX_CHECK(cx_bn_cmp_u32(bn_r, 0, &diff));
318 if (diff == 0) {
319 goto RETRY;
320 }
321 CX_CHECK(cx_bn_cmp(bn_r, bn_n, &diff));
322 if (diff >= 0) {
323 goto RETRY;
324 }
325 // s = k - h * x.
326 CX_CHECK(cx_bn_init(bn_d, pv_key->d, pv_key->d_len));
327 CX_CHECK(cx_bn_mod_mul(bn_s, bn_d, bn_r, bn_n));
328 CX_CHECK(cx_bn_mod_sub(bn_s, bn_k, bn_s, bn_n));
329 CX_CHECK(cx_bn_cmp_u32(bn_s, 0, &diff));
330 if (diff == 0) {
331 goto RETRY;
332 }
333 CX_CHECK(cx_bn_export(bn_s, S, 32));
334 break;
335
336 /* Schnorr signature with secp256k1 according to BIP0340
337 ** https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki */
338
339 case CX_ECSCHNORR_BIP0340:
340 CX_CHECK(cx_ecpoint_export(&Q, NULL, 0, sig, size));
341 odd = sig[size - 1] & 1;
342 if (odd) {
343 CX_CHECK(cx_bn_sub(bn_k, bn_n, bn_k));
344 CX_CHECK(cx_bn_export(bn_k, sig, size));
345 }
346 // Only take the x-coordinate
347 CX_CHECK(cx_ecpoint_export(&Q, R, size, NULL, 0));
348
349 // tag_hash = SHA256("BIP0340_challenge")
350 // e = SHA256(tag_hash || tag_hash || Rx || Px || msg)
351 cx_sha256_init_no_throw(&H);
352 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H,
353 CX_LAST,
354 BIP0340_challenge,
355 sizeof(BIP0340_challenge),
356 sig,
357 size));
358 cx_sha256_init_no_throw(&H);
359 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, sig, size, NULL, 0));
360 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, sig, size, NULL, 0));
361 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, R, size, NULL, 0));
362 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, P, size, NULL, 0));
363 CX_CHECK(cx_hash_no_throw(
364 (cx_hash_t *) &H, CX_LAST | CX_NO_REINIT, msg, msg_len, sig, size));
365
366 // e = e % n
367 CX_CHECK(cx_bn_init(bn_s, sig, size));
368 CX_CHECK(cx_bn_reduce(bn_r, bn_s, bn_n));
369
370 // s = (k + e *d) % n
371 CX_CHECK(cx_bn_mod_mul(bn_s, bn_d, bn_r, bn_n));
372 CX_CHECK(cx_bn_mod_add(bn_s, bn_k, bn_s, bn_n));
373 CX_CHECK(cx_bn_set_u32(bn_k, 0));
374 CX_CHECK(cx_bn_mod_sub(bn_s, bn_s, bn_k, bn_n));
375
376 CX_CHECK(cx_bn_export(bn_s, S, size));
377 break;
378
379 default:
380 error = CX_INVALID_PARAMETER;
381 goto end;
382 }
383
384end:
385 cx_hash_destroy((cx_hash_t *) &H);
386 cx_bn_unlock();
387 if (error == CX_OK) {
388 if ((mode & CX_MASK_EC) == CX_ECSCHNORR_BIP0340) {
389 *sig_len = 64;
390 memcpy(sig, R, 32);
391 memcpy(sig + 32, S, 32);
392 }
393 else {
394 // encoding
395 *sig_len = cx_ecfp_encode_sig_der(sig, *sig_len, R, size, S, size);
396 }
397 }
398 return error;
399}
400
401bool cx_ecschnorr_verify(const cx_ecfp_public_key_t *pu_key,
402 uint32_t mode,
403 cx_md_t hashID,
404 const uint8_t *msg,
405 size_t msg_len,
406 const uint8_t *sig,
407 size_t sig_len)
408{
409 size_t size;
410 const uint8_t *r, *s;
411 size_t r_len, s_len;
412 cx_ecpoint_t R, P, Q;
413 uint8_t x[33];
414 bool odd;
415 volatile int verified;
416 cx_err_t error;
417 int diff;
418 bool is_on_curve = false;
419
420 cx_bn_t bn_d, bn_r, bn_s, bn_n;
421 cx_bn_t bn_x, bn_y, bn_p;
422
423 CX_CHECK(cx_ecdomain_parameters_length(pu_key->curve, &size));
424
425 // ECSCHNORR BIP0340 is only defined for secp256k1
426 if (((mode & CX_MASK_EC) == CX_ECSCHNORR_BIP0340) && (pu_key->curve != CX_CURVE_SECP256K1)) {
427 error = CX_EC_INVALID_CURVE;
428 verified = false;
429 goto end;
430 }
431
432 if (!CX_CURVE_RANGE(pu_key->curve, WEIERSTRASS) || hashID != CX_SHA256 || size != 32
433 || pu_key->W_len != 1 + 2 * size) {
434 return false;
435 }
436
437 if ((mode & CX_MASK_EC) != CX_ECSCHNORR_BIP0340) {
438 if (!cx_ecfp_decode_sig_der(sig, sig_len, size, &r, &r_len, &s, &s_len)) {
439 return false;
440 }
441 }
442
443 CX_CHECK(cx_bn_lock(size, 0));
444 verified = false;
445
446 CX_CHECK(cx_bn_alloc(&bn_n, size));
447 CX_CHECK(cx_ecdomain_parameter_bn(pu_key->curve, CX_CURVE_PARAM_Order, bn_n));
448 if ((mode & CX_MASK_EC) == CX_ECSCHNORR_BIP0340) {
449 CX_CHECK(cx_bn_alloc_init(&bn_r, size, sig, size));
450 CX_CHECK(cx_bn_alloc_init(&bn_s, size, sig + size, size));
451 }
452 else {
453 CX_CHECK(cx_bn_alloc_init(&bn_r, size, r, r_len));
454 CX_CHECK(cx_bn_alloc_init(&bn_s, size, s, s_len));
455 }
456
457 CX_CHECK(cx_bn_alloc(&bn_d, size));
458
459 CX_CHECK(cx_bn_cmp_u32(bn_r, 0, &diff));
460 if (diff == 0) {
461 goto end;
462 }
463 CX_CHECK(cx_bn_cmp_u32(bn_s, 0, &diff));
464 if (diff == 0) {
465 goto end;
466 }
467
468 CX_CHECK(cx_ecpoint_alloc(&P, pu_key->curve));
469 CX_CHECK(cx_ecpoint_alloc(&Q, pu_key->curve));
470 CX_CHECK(cx_ecpoint_alloc(&R, pu_key->curve));
471 CX_CHECK(cx_ecdomain_generator_bn(pu_key->curve, &P));
472 CX_CHECK(cx_ecpoint_init(&Q, &pu_key->W[1], size, &pu_key->W[1 + size], size));
473
474 switch (mode & CX_MASK_EC) {
475 case CX_ECSCHNORR_ISO14888_XY:
476 case CX_ECSCHNORR_ISO14888_X:
477 // 1. check...
478 // 2. Q = [s]G - [r]W
479 // If Q = 0, output Error and terminate.
480 // 3. v = H(Qx||Qy||M).
481 // 4. Output True if v = r, and False otherwise.
482
483 // 1.
484 CX_CHECK(cx_bn_cmp_u32(bn_r, 0, &diff));
485 if (diff == 0) {
486 break;
487 }
488 CX_CHECK(cx_bn_cmp(bn_n, bn_s, &diff));
489 if (diff <= 0) {
490 break;
491 }
492 CX_CHECK(cx_bn_cmp_u32(bn_s, 0, &diff));
493 if (diff == 0) {
494 break;
495 }
496 CX_CHECK(cx_bn_cmp(bn_n, bn_s, &diff));
497 if (diff <= 0) {
498 break;
499 }
500
501 // 2.
502 // sG - rW
503 CX_CHECK(cx_ecpoint_neg(&Q));
504 CX_CHECK(cx_ecpoint_double_scalarmul_bn(&R, &P, &Q, bn_s, bn_r));
505 // 3.
506 cx_sha256_init_no_throw(&H);
507 CX_CHECK(cx_ecpoint_export(&R, x, size, NULL, 0));
508 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, x, size, NULL, 0));
509 if ((mode & CX_MASK_EC) == CX_ECSCHNORR_ISO14888_XY) {
510 CX_CHECK(cx_ecpoint_export(&R, NULL, 0, x, size));
511 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, x, size, NULL, 0));
512 }
513 CX_CHECK(cx_hash_no_throw(
514 (cx_hash_t *) &H, CX_LAST | CX_NO_REINIT, msg, msg_len, x, sizeof(x)));
515 // 4.
516 CX_CHECK(cx_bn_init(bn_s, x, CX_SHA256_SIZE));
517 CX_CHECK(cx_bn_cmp(bn_r, bn_s, &diff));
518 if (diff == 0) {
519 verified = true;
520 }
521 break;
522
523 case CX_ECSCHNORR_BSI03111:
524 // 1. Verify that r in {0, . . . , 2**t - 1} and s in {1, 2, . . . , n - 1}.
525 // If the check fails, output False and terminate.
526 // 2. Q = [s]G + [r]W
527 // If Q = 0, output Error and terminate.
528 // 3. v = H(M||Qx)
529 // 4. Output True if v = r, and False otherwise.
530
531 // 1.
532 CX_CHECK(cx_bn_cmp_u32(bn_r, 0, &diff));
533 if (diff == 0) {
534 break;
535 }
536 CX_CHECK(cx_bn_cmp_u32(bn_s, 0, &diff));
537 if (diff == 0) {
538 break;
539 }
540 CX_CHECK(cx_bn_cmp(bn_n, bn_s, &diff));
541 if (diff <= 0) {
542 break;
543 }
544
545 // 2.
546 CX_CHECK(cx_ecpoint_double_scalarmul_bn(&R, &P, &Q, bn_s, bn_r));
547 // 3.
548 cx_sha256_init_no_throw(&H);
549 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, msg, msg_len, NULL, 0));
550 CX_CHECK(cx_ecpoint_export(&R, x, size, NULL, 0));
551 CX_CHECK(
552 cx_hash_no_throw((cx_hash_t *) &H, CX_LAST | CX_NO_REINIT, x, size, x, sizeof(x)));
553 // 4.
554 CX_CHECK(cx_bn_init(bn_s, x, CX_SHA256_SIZE));
555 CX_CHECK(cx_bn_cmp(bn_r, bn_s, &diff));
556 if (diff == 0) {
557 verified = true;
558 }
559 break;
560
561 case CX_ECSCHNORR_Z:
562 // The algorithm to check the signature (r, s) on a message m using a public
563 // key kpub is as follows
564 // 1. Check if r,s is in [1, ..., order-1]
565 // 2. Compute Q = sG + r*kpub
566 // 3. If Q = O (the neutral point), return 0;
567 // 4. r' = H(Q, kpub, m) [CME: mod n and Q and kpub compressed "02|03 x" according to
568 // pdf/code]
569 // 5. return r' == r
570
571 // r,s is in [1, ..., order-1]
572 CX_CHECK(cx_bn_cmp_u32(bn_r, 0, &diff));
573 if (diff == 0) {
574 break;
575 }
576 CX_CHECK(cx_bn_cmp(bn_r, bn_n, &diff));
577 if (diff >= 0) {
578 break;
579 }
580 CX_CHECK(cx_bn_cmp_u32(bn_s, 0, &diff));
581 if (diff == 0) {
582 break;
583 }
584 CX_CHECK(cx_bn_cmp(bn_s, bn_n, &diff));
585 if (diff >= 0) {
586 break;
587 }
588
589 // Q = sG + r*kpub
590 CX_CHECK(cx_ecpoint_double_scalarmul_bn(&R, &P, &Q, bn_s, bn_r));
591 // r' = H(Q, kpub, m)
592 cx_sha256_init_no_throw(&H);
593 // Q
594 CX_CHECK(cx_ecpoint_export(&R, NULL, 0, x, size));
595 odd = x[size - 1] & 1;
596 CX_CHECK(cx_ecpoint_export(&R, x + 1, size, NULL, 0));
597 x[0] = odd ? 0x03 : 0x02;
598 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, x, 1 + size, NULL, 0)); // Q
599 // kpub
600 memmove(x + 1, &pu_key->W[1], size);
601 x[0] = (pu_key->W[1 + 2 * size - 1] & 1) ? 0x03 : 0x02;
602 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, x, 1 + size, NULL, 0)); // kpub
603 // m
604 CX_CHECK(cx_hash_no_throw(
605 (cx_hash_t *) &H, CX_LAST | CX_NO_REINIT, msg, msg_len, x, sizeof(x))); // m
606
607 CX_CHECK(cx_bn_init(bn_d, x, CX_SHA256_SIZE));
608 CX_CHECK(cx_bn_reduce(bn_s, bn_d, bn_n));
609 CX_CHECK(cx_bn_cmp(bn_r, bn_s, &diff));
610 if (diff == 0) {
611 verified = true;
612 }
613 break;
614
615 case CX_ECSCHNORR_LIBSECP:
616 // Verification:
617 // Inputs: 32-byte message m, public key point Q, signature: (32-byte r, scalar s)
618 // 1. Signature is invalid if s >= order.
619 // 2. Signature is invalid if r >= p.
620 // 3. Compute scalar h = Hash(r || m). Signature is invalid if h == 0 or h >= order.
621 // 4. Option 1 (faster for single verification):
622 // 5. Compute point R = h * Q + s * G. Signature is invalid if R is infinity or R's y
623 // coordinate is odd.
624 // 6. Signature is valid if the serialization of R's x coordinate equals r.
625 // s < order and r < field.
626
627 // 1. 2.
628 CX_CHECK(cx_bn_cmp_u32(bn_r, 0, &diff));
629 if (diff == 0) {
630 verified = false;
631 break;
632 }
633 CX_CHECK(cx_bn_cmp_u32(bn_s, 0, &diff));
634 if (diff == 0) {
635 verified = false;
636 break;
637 }
638 CX_CHECK(cx_bn_cmp(bn_n, bn_s, &diff));
639 if (diff <= 0) {
640 verified = false;
641 break;
642 }
643 // h = Hash(r||m), and h!=0, and h<order
644 cx_sha256_init_no_throw(&H);
645 CX_CHECK(cx_bn_export(bn_r, x, size));
646 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, x, size, NULL, 0));
647 CX_CHECK(cx_hash_no_throw(
648 (cx_hash_t *) &H, CX_LAST | CX_NO_REINIT, msg, msg_len, x, sizeof(x)));
649 CX_CHECK(cx_bn_init(bn_s, x, CX_SHA256_SIZE));
650 CX_CHECK(cx_bn_cmp_u32(bn_s, 0, &diff));
651 if (diff == 0) {
652 break;
653 }
654 CX_CHECK(cx_bn_cmp(bn_s, bn_n, &diff));
655 if (diff >= 0) {
656 break;
657 }
658 // R = h*W + s*G, and Ry is NOT odd, and Rx=r
659 CX_CHECK(cx_bn_init(bn_d, s, s_len));
660 CX_CHECK(cx_ecpoint_double_scalarmul_bn(&R, &P, &Q, bn_d, bn_s));
661 CX_CHECK(cx_ecpoint_export_bn(&R, &bn_s, &bn_d));
662 CX_CHECK(cx_bn_is_odd(bn_d, &odd));
663 if (odd) {
664 break;
665 }
666 CX_CHECK(cx_bn_cmp(bn_r, bn_s, &diff));
667 if (diff == 0) {
668 verified = true;
669 }
670 break;
671
672 /* Schnorr signature verification with secp256k1 according to BIP0340
673 ** https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki */
674
675 case CX_ECSCHNORR_BIP0340:
676 // Q = lift_x(pu_key)
677 CX_CHECK(cx_bn_alloc(&bn_x, size));
678 CX_CHECK(cx_bn_alloc(&bn_y, size));
679 CX_CHECK(cx_bn_alloc(&bn_p, size));
680 CX_CHECK(cx_ecdomain_parameter_bn(pu_key->curve, CX_CURVE_PARAM_Field, bn_p));
681 CX_CHECK(cx_ecpoint_export_bn(&Q, &bn_x, &bn_y));
682 // c = x^3 + 7 mod p
683 CX_CHECK(cx_bn_set_u32(bn_s, 3));
684 CX_CHECK(cx_bn_mod_pow_bn(bn_r, bn_x, bn_s, bn_p));
685 CX_CHECK(cx_bn_set_u32(bn_s, 7));
686 CX_CHECK(cx_bn_mod_add(bn_r, bn_r, bn_s, bn_p));
687 // y = c^(p+1)/4 mod p
688 CX_CHECK(cx_bn_copy(bn_s, bn_p));
689 CX_CHECK(cx_bn_set_u32(bn_d, 1));
690 CX_CHECK(cx_bn_add(bn_s, bn_s, bn_d));
691 CX_CHECK(cx_bn_shr(bn_s, 2));
692 CX_CHECK(cx_bn_mod_pow_bn(bn_y, bn_r, bn_s, bn_p));
693
694 CX_CHECK(cx_bn_is_odd(bn_y, &odd));
695 // If y is even, Qy = y otherwise Qy = p - y
696 if (odd) {
697 CX_CHECK(cx_bn_sub(bn_y, bn_p, bn_y));
698 }
699 CX_CHECK(cx_ecpoint_init_bn(&Q, bn_x, bn_y));
700 CX_CHECK(cx_ecpoint_is_on_curve(&Q, &is_on_curve));
701 if (!is_on_curve) {
702 error = CX_EC_INVALID_POINT;
703 goto end;
704 }
705 // tag_hash = SHA256("BIP0340/challenge")
706 // e = SHA256(tag_hash || tag_hash || r || pu_key || msg)
707 cx_sha256_init_no_throw(&H);
708 CX_CHECK(cx_hash_no_throw(
709 (cx_hash_t *) &H, CX_LAST, BIP0340_challenge, sizeof(BIP0340_challenge), x, size));
710 cx_sha256_init_no_throw(&H);
711 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, x, size, NULL, 0));
712 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, x, size, NULL, 0));
713 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, sig, size, NULL, 0));
714 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, &pu_key->W[1], size, NULL, 0));
715 CX_CHECK(
716 cx_hash_no_throw((cx_hash_t *) &H, CX_LAST | CX_NO_REINIT, msg, msg_len, x, size));
717
718 // e = e % n
719 CX_CHECK(cx_bn_init(bn_x, x, size));
720 CX_CHECK(cx_bn_reduce(bn_r, bn_x, bn_n));
721 // n - e
722 CX_CHECK(cx_bn_sub(bn_r, bn_n, bn_r));
723 // s
724 CX_CHECK(cx_bn_init(bn_s, sig + size, size));
725 // [s].P + [n-e].Q where P is the generator of the curve
726 // and Q is the point representing the public key.
727 CX_CHECK(cx_ecpoint_double_scalarmul_bn(&R, &P, &Q, bn_s, bn_r));
728 CX_CHECK(cx_ecpoint_export_bn(&R, &bn_x, &bn_y));
729 CX_CHECK(cx_bn_is_odd(bn_y, &odd));
730 // r
731 CX_CHECK(cx_bn_init(bn_r, sig, size));
732 CX_CHECK(cx_bn_cmp(bn_x, bn_r, &diff));
733
734 if (odd || (diff != 0)) {
735 error = CX_INVALID_PARAMETER;
736 goto end;
737 }
738 verified = true;
739 break;
740
741 default:
742 error = CX_INVALID_PARAMETER;
743 goto end;
744 }
745
746end:
747 cx_bn_unlock();
748 return error == CX_OK && verified;
749}
750
751#endif // HAVE_ECSCHNORR
cx_ecfp.h
cx_eddsa.h
cx_hash.h
cx_ram.h
cx_rng.h
cx_utils.h
CX_ECSCHNORR_ISO14888_X
#define CX_ECSCHNORR_ISO14888_X
Definition lcx_common.h:175
CX_MASK_RND
#define CX_MASK_RND
Definition lcx_common.h:161
CX_ECSCHNORR_BSI03111
#define CX_ECSCHNORR_BSI03111
Definition lcx_common.h:176
CX_NO_REINIT
#define CX_NO_REINIT
Definition lcx_common.h:183
CX_MASK_EC
#define CX_MASK_EC
Definition lcx_common.h:170
CX_ECSCHNORR_BIP0340
#define CX_ECSCHNORR_BIP0340
Definition lcx_common.h:171
CX_ECSCHNORR_Z
#define CX_ECSCHNORR_Z
Definition lcx_common.h:178
CX_RND_PROVIDED
#define CX_RND_PROVIDED
Definition lcx_common.h:165
CX_RND_TRNG
#define CX_RND_TRNG
Definition lcx_common.h:163
CX_ECSCHNORR_LIBSECP
#define CX_ECSCHNORR_LIBSECP
Definition lcx_common.h:177
CX_ECSCHNORR_ISO14888_XY
#define CX_ECSCHNORR_ISO14888_XY
Definition lcx_common.h:174
CX_LAST
#define CX_LAST
Definition lcx_common.h:115
uint8_t
unsigned char uint8_t
Definition usbd_conf.h:53
Generated by doxygen 1.9.8