Embedded SDK
Embedded SDK
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 */
35 const uint8_t BIP0340_challenge[]
36  = {'B', 'I', 'P', '0', '3', '4', '0', '/', 'c', 'h', 'a', 'l', 'l', 'e', 'n', 'g', 'e'};
37 const uint8_t BIP0340_aux[] = {'B', 'I', 'P', '0', '3', '4', '0', '/', 'a', 'u', 'x'};
38 const uint8_t BIP0340_nonce[] = {'B', 'I', 'P', '0', '3', '4', '0', '/', 'n', 'o', 'n', 'c', 'e'};
39 
40 cx_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;
129 RETRY:
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++;
162 RETRY2:
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 
384 end:
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 
401 bool 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 
746 end:
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.1