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 "lcx_ecfp.h"
22#include "lcx_eddsa.h"
23#include "cx_hash.h"
24#include "cx_utils.h"
25#include "cx_ram.h"
26
27#include <string.h>
28
29// const char kr[] = {0xe5, 0xa8, 0xd1, 0xd5, 0x29, 0x97, 0x1c, 0x10, 0xca, 0x2a, 0xf3, 0x78, 0x44,
30// 0x4f, 0xb5, 0x44, 0xa2, 0x11, 0x70, 0x78, 0x92, 0xc8, 0x89, 0x8f, 0x91, 0xdc, 0xb1, 0x71, 0x58,
31// 0x4e, 0x3d, 0xb9};
32
33/* BIP0340 tags for computing the tagged hashes */
34const uint8_t BIP0340_challenge[]
35 = {'B', 'I', 'P', '0', '3', '4', '0', '/', 'c', 'h', 'a', 'l', 'l', 'e', 'n', 'g', 'e'};
36const uint8_t BIP0340_aux[] = {'B', 'I', 'P', '0', '3', '4', '0', '/', 'a', 'u', 'x'};
37const uint8_t BIP0340_nonce[] = {'B', 'I', 'P', '0', '3', '4', '0', '/', 'n', 'o', 'n', 'c', 'e'};
38
39cx_err_t cx_ecschnorr_sign_no_throw(const cx_ecfp_private_key_t *pv_key,
40 uint32_t mode,
41 cx_md_t hashID,
42 const uint8_t *msg,
43 size_t msg_len,
44 uint8_t *sig,
45 size_t *sig_len)
46{
47#define CX_MAX_TRIES 100
48#define H G_cx.sha256
49
50 size_t size;
51 cx_ecpoint_t Q;
52 cx_bn_t bn_k, bn_d, bn_r, bn_s, bn_n;
53 uint8_t R[33];
54 uint8_t S[32];
55 uint8_t P[32];
56 int odd;
57 uint8_t tries;
58 cx_err_t error;
59 int diff;
60
61 CX_CHECK(cx_ecdomain_parameters_length(pv_key->curve, &size));
62
63 // Only secp256k1 is allowed when using CX_ECSCHNORR_BIP0340
64 if (((mode & CX_MASK_EC) == CX_ECSCHNORR_BIP0340) && (pv_key->curve != CX_CURVE_SECP256K1)) {
65 return CX_EC_INVALID_CURVE;
66 }
67
68 // WARN: only accept weierstrass 256 bits curve for now
69 if (hashID != CX_SHA256 || size != 32 || !CX_CURVE_RANGE(pv_key->curve, WEIERSTRASS)
70 || pv_key->d_len != size) {
71 return CX_INVALID_PARAMETER;
72 }
73
74 // Schnorr BIP0340 signature is not DER encoded and is 64-byte long.
75 if (((mode & CX_MASK_EC) != CX_ECSCHNORR_BIP0340) && (*sig_len < (6 + 2 * (size + 1)))) {
76 return CX_INVALID_PARAMETER;
77 }
78
79 CX_CHECK(cx_bn_lock(size, 0));
80 CX_CHECK(cx_bn_alloc(&bn_n, size));
81 CX_CHECK(cx_ecdomain_parameter_bn(pv_key->curve, CX_CURVE_PARAM_Order, bn_n));
82 CX_CHECK(cx_bn_alloc(&bn_k, size));
83 CX_CHECK(cx_bn_alloc(&bn_d, size));
84 CX_CHECK(cx_bn_alloc(&bn_r, size));
85 CX_CHECK(cx_bn_alloc(&bn_s, size));
86 CX_CHECK(cx_ecpoint_alloc(&Q, pv_key->curve));
87
88 if ((mode & CX_MASK_EC) == CX_ECSCHNORR_BIP0340) {
89 // Q = [d].G
90 CX_CHECK(cx_ecdomain_generator_bn(pv_key->curve, &Q));
91 CX_CHECK(cx_ecpoint_rnd_fixed_scalarmul(&Q, pv_key->d, size));
92 // If Qy is even use d otherwise use n-d
93 CX_CHECK(cx_bn_init(bn_d, pv_key->d, size));
94 CX_CHECK(cx_ecpoint_export(&Q, NULL, 0, P, size));
95 odd = P[size - 1] & 1;
96 if (odd) {
97 CX_CHECK(cx_bn_sub(bn_d, bn_n, bn_d));
98 }
99 // tag_hash = SHA256("BIP0340/aux")
100 // SHA256(tag_hash || tag_hash || aux_rnd)
101 cx_sha256_init_no_throw(&H);
102 CX_CHECK(
103 cx_hash_no_throw((cx_hash_t *) &H, CX_LAST, BIP0340_aux, sizeof(BIP0340_aux), R, size));
104 cx_sha256_init_no_throw(&H);
105 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, R, size, NULL, 0));
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, CX_LAST | CX_NO_REINIT, sig, size, R, size));
108 // t = d ^ SHA256(tag_hash || tag_hash || aux_rnd)
109 CX_CHECK(cx_bn_init(bn_k, R, size));
110 CX_CHECK(cx_bn_xor(bn_r, bn_d, bn_k));
111 CX_CHECK(cx_bn_export(bn_r, sig, size));
112 // tag_hash = SHA256("BIP0340/nonce")
113 // SHA256(tag_hash || tag_hash || t || Qx || msg)
114 cx_sha256_init_no_throw(&H);
115 CX_CHECK(cx_hash_no_throw(
116 (cx_hash_t *) &H, CX_LAST, BIP0340_nonce, sizeof(BIP0340_nonce), R, size));
117 cx_sha256_init_no_throw(&H);
118 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, R, size, NULL, 0));
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, sig, size, NULL, 0));
121 CX_CHECK(cx_ecpoint_export(&Q, P, size, NULL, 0));
122 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, P, size, NULL, 0));
123 CX_CHECK(
124 cx_hash_no_throw((cx_hash_t *) &H, CX_LAST | CX_NO_REINIT, msg, msg_len, 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 if (sig_len < 2 * size) {
450 verified = false;
451 goto end;
452 }
453 CX_CHECK(cx_bn_alloc_init(&bn_r, size, sig, size));
454 CX_CHECK(cx_bn_alloc_init(&bn_s, size, sig + size, size));
455 }
456 else {
457 CX_CHECK(cx_bn_alloc_init(&bn_r, size, r, r_len));
458 CX_CHECK(cx_bn_alloc_init(&bn_s, size, s, s_len));
459 }
460
461 CX_CHECK(cx_bn_alloc(&bn_d, size));
462
463 CX_CHECK(cx_bn_cmp_u32(bn_r, 0, &diff));
464 if (diff == 0) {
465 goto end;
466 }
467 CX_CHECK(cx_bn_cmp_u32(bn_s, 0, &diff));
468 if (diff == 0) {
469 goto end;
470 }
471
472 CX_CHECK(cx_ecpoint_alloc(&P, pu_key->curve));
473 CX_CHECK(cx_ecpoint_alloc(&Q, pu_key->curve));
474 CX_CHECK(cx_ecpoint_alloc(&R, pu_key->curve));
475 CX_CHECK(cx_ecdomain_generator_bn(pu_key->curve, &P));
476 CX_CHECK(cx_ecpoint_init(&Q, &pu_key->W[1], size, &pu_key->W[1 + size], size));
477
478 switch (mode & CX_MASK_EC) {
479 case CX_ECSCHNORR_ISO14888_XY:
480 case CX_ECSCHNORR_ISO14888_X:
481 // 1. check...
482 // 2. Q = [s]G - [r]W
483 // If Q = 0, output Error and terminate.
484 // 3. v = H(Qx||Qy||M).
485 // 4. Output True if v = r, and False otherwise.
486
487 // 1.
488 CX_CHECK(cx_bn_cmp_u32(bn_r, 0, &diff));
489 if (diff == 0) {
490 break;
491 }
492 CX_CHECK(cx_bn_cmp(bn_n, bn_s, &diff));
493 if (diff <= 0) {
494 break;
495 }
496 CX_CHECK(cx_bn_cmp_u32(bn_s, 0, &diff));
497 if (diff == 0) {
498 break;
499 }
500 CX_CHECK(cx_bn_cmp(bn_n, bn_s, &diff));
501 if (diff <= 0) {
502 break;
503 }
504
505 // 2.
506 // sG - rW
507 CX_CHECK(cx_ecpoint_neg(&Q));
508 CX_CHECK(cx_ecpoint_double_scalarmul_bn(&R, &P, &Q, bn_s, bn_r));
509 // 3.
510 cx_sha256_init_no_throw(&H);
511 CX_CHECK(cx_ecpoint_export(&R, x, size, NULL, 0));
512 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, x, size, NULL, 0));
513 if ((mode & CX_MASK_EC) == CX_ECSCHNORR_ISO14888_XY) {
514 CX_CHECK(cx_ecpoint_export(&R, NULL, 0, x, size));
515 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, x, size, NULL, 0));
516 }
517 CX_CHECK(cx_hash_no_throw(
518 (cx_hash_t *) &H, CX_LAST | CX_NO_REINIT, msg, msg_len, x, sizeof(x)));
519 // 4.
520 CX_CHECK(cx_bn_init(bn_s, x, CX_SHA256_SIZE));
521 CX_CHECK(cx_bn_cmp(bn_r, bn_s, &diff));
522 if (diff == 0) {
523 verified = true;
524 }
525 break;
526
527 case CX_ECSCHNORR_BSI03111:
528 // 1. Verify that r in {0, . . . , 2**t - 1} and s in {1, 2, . . . , n - 1}.
529 // If the check fails, output False and terminate.
530 // 2. Q = [s]G + [r]W
531 // If Q = 0, output Error and terminate.
532 // 3. v = H(M||Qx)
533 // 4. Output True if v = r, and False otherwise.
534
535 // 1.
536 CX_CHECK(cx_bn_cmp_u32(bn_r, 0, &diff));
537 if (diff == 0) {
538 break;
539 }
540 CX_CHECK(cx_bn_cmp_u32(bn_s, 0, &diff));
541 if (diff == 0) {
542 break;
543 }
544 CX_CHECK(cx_bn_cmp(bn_n, bn_s, &diff));
545 if (diff <= 0) {
546 break;
547 }
548
549 // 2.
550 CX_CHECK(cx_ecpoint_double_scalarmul_bn(&R, &P, &Q, bn_s, bn_r));
551 // 3.
552 cx_sha256_init_no_throw(&H);
553 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, msg, msg_len, NULL, 0));
554 CX_CHECK(cx_ecpoint_export(&R, x, size, NULL, 0));
555 CX_CHECK(
556 cx_hash_no_throw((cx_hash_t *) &H, CX_LAST | CX_NO_REINIT, x, size, x, sizeof(x)));
557 // 4.
558 CX_CHECK(cx_bn_init(bn_s, x, CX_SHA256_SIZE));
559 CX_CHECK(cx_bn_cmp(bn_r, bn_s, &diff));
560 if (diff == 0) {
561 verified = true;
562 }
563 break;
564
565 case CX_ECSCHNORR_Z:
566 // The algorithm to check the signature (r, s) on a message m using a public
567 // key kpub is as follows
568 // 1. Check if r,s is in [1, ..., order-1]
569 // 2. Compute Q = sG + r*kpub
570 // 3. If Q = O (the neutral point), return 0;
571 // 4. r' = H(Q, kpub, m) [CME: mod n and Q and kpub compressed "02|03 x" according to
572 // pdf/code]
573 // 5. return r' == r
574
575 // r,s is in [1, ..., order-1]
576 CX_CHECK(cx_bn_cmp_u32(bn_r, 0, &diff));
577 if (diff == 0) {
578 break;
579 }
580 CX_CHECK(cx_bn_cmp(bn_r, bn_n, &diff));
581 if (diff >= 0) {
582 break;
583 }
584 CX_CHECK(cx_bn_cmp_u32(bn_s, 0, &diff));
585 if (diff == 0) {
586 break;
587 }
588 CX_CHECK(cx_bn_cmp(bn_s, bn_n, &diff));
589 if (diff >= 0) {
590 break;
591 }
592
593 // Q = sG + r*kpub
594 CX_CHECK(cx_ecpoint_double_scalarmul_bn(&R, &P, &Q, bn_s, bn_r));
595 // r' = H(Q, kpub, m)
596 cx_sha256_init_no_throw(&H);
597 // Q
598 CX_CHECK(cx_ecpoint_export(&R, NULL, 0, x, size));
599 odd = x[size - 1] & 1;
600 CX_CHECK(cx_ecpoint_export(&R, x + 1, size, NULL, 0));
601 x[0] = odd ? 0x03 : 0x02;
602 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, x, 1 + size, NULL, 0)); // Q
603 // kpub
604 memmove(x + 1, &pu_key->W[1], size);
605 x[0] = (pu_key->W[1 + 2 * size - 1] & 1) ? 0x03 : 0x02;
606 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, x, 1 + size, NULL, 0)); // kpub
607 // m
608 CX_CHECK(cx_hash_no_throw(
609 (cx_hash_t *) &H, CX_LAST | CX_NO_REINIT, msg, msg_len, x, sizeof(x))); // m
610
611 CX_CHECK(cx_bn_init(bn_d, x, CX_SHA256_SIZE));
612 CX_CHECK(cx_bn_reduce(bn_s, bn_d, bn_n));
613 CX_CHECK(cx_bn_cmp(bn_r, bn_s, &diff));
614 if (diff == 0) {
615 verified = true;
616 }
617 break;
618
619 case CX_ECSCHNORR_LIBSECP:
620 // Verification:
621 // Inputs: 32-byte message m, public key point Q, signature: (32-byte r, scalar s)
622 // 1. Signature is invalid if s >= order.
623 // 2. Signature is invalid if r >= p.
624 // 3. Compute scalar h = Hash(r || m). Signature is invalid if h == 0 or h >= order.
625 // 4. Option 1 (faster for single verification):
626 // 5. Compute point R = h * Q + s * G. Signature is invalid if R is infinity or R's y
627 // coordinate is odd.
628 // 6. Signature is valid if the serialization of R's x coordinate equals r.
629 // s < order and r < field.
630
631 // 1. 2.
632 CX_CHECK(cx_bn_cmp_u32(bn_r, 0, &diff));
633 if (diff == 0) {
634 verified = false;
635 break;
636 }
637 CX_CHECK(cx_bn_cmp_u32(bn_s, 0, &diff));
638 if (diff == 0) {
639 verified = false;
640 break;
641 }
642 CX_CHECK(cx_bn_cmp(bn_n, bn_s, &diff));
643 if (diff <= 0) {
644 verified = false;
645 break;
646 }
647 // h = Hash(r||m), and h!=0, and h<order
648 cx_sha256_init_no_throw(&H);
649 CX_CHECK(cx_bn_export(bn_r, x, size));
650 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, x, size, NULL, 0));
651 CX_CHECK(cx_hash_no_throw(
652 (cx_hash_t *) &H, CX_LAST | CX_NO_REINIT, msg, msg_len, x, sizeof(x)));
653 CX_CHECK(cx_bn_init(bn_s, x, CX_SHA256_SIZE));
654 CX_CHECK(cx_bn_cmp_u32(bn_s, 0, &diff));
655 if (diff == 0) {
656 break;
657 }
658 CX_CHECK(cx_bn_cmp(bn_s, bn_n, &diff));
659 if (diff >= 0) {
660 break;
661 }
662 // R = h*W + s*G, and Ry is NOT odd, and Rx=r
663 CX_CHECK(cx_bn_init(bn_d, s, s_len));
664 CX_CHECK(cx_ecpoint_double_scalarmul_bn(&R, &P, &Q, bn_d, bn_s));
665 CX_CHECK(cx_ecpoint_export_bn(&R, &bn_s, &bn_d));
666 CX_CHECK(cx_bn_is_odd(bn_d, &odd));
667 if (odd) {
668 break;
669 }
670 CX_CHECK(cx_bn_cmp(bn_r, bn_s, &diff));
671 if (diff == 0) {
672 verified = true;
673 }
674 break;
675
676 /* Schnorr signature verification with secp256k1 according to BIP0340
677 ** https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki */
678
679 case CX_ECSCHNORR_BIP0340:
680 // Q = lift_x(pu_key)
681 CX_CHECK(cx_bn_alloc(&bn_x, size));
682 CX_CHECK(cx_bn_alloc(&bn_y, size));
683 CX_CHECK(cx_bn_alloc(&bn_p, size));
684 CX_CHECK(cx_ecdomain_parameter_bn(pu_key->curve, CX_CURVE_PARAM_Field, bn_p));
685 CX_CHECK(cx_ecpoint_export_bn(&Q, &bn_x, &bn_y));
686 // c = x^3 + 7 mod p
687 CX_CHECK(cx_bn_set_u32(bn_s, 3));
688 CX_CHECK(cx_bn_mod_pow_bn(bn_r, bn_x, bn_s, bn_p));
689 CX_CHECK(cx_bn_set_u32(bn_s, 7));
690 CX_CHECK(cx_bn_mod_add(bn_r, bn_r, bn_s, bn_p));
691 // y = c^(p+1)/4 mod p
692 CX_CHECK(cx_bn_copy(bn_s, bn_p));
693 CX_CHECK(cx_bn_set_u32(bn_d, 1));
694 CX_CHECK(cx_bn_add(bn_s, bn_s, bn_d));
695 CX_CHECK(cx_bn_shr(bn_s, 2));
696 CX_CHECK(cx_bn_mod_pow_bn(bn_y, bn_r, bn_s, bn_p));
697
698 CX_CHECK(cx_bn_is_odd(bn_y, &odd));
699 // If y is even, Qy = y otherwise Qy = p - y
700 if (odd) {
701 CX_CHECK(cx_bn_sub(bn_y, bn_p, bn_y));
702 }
703 CX_CHECK(cx_ecpoint_init_bn(&Q, bn_x, bn_y));
704 CX_CHECK(cx_ecpoint_is_on_curve(&Q, &is_on_curve));
705 if (!is_on_curve) {
706 error = CX_EC_INVALID_POINT;
707 goto end;
708 }
709 // tag_hash = SHA256("BIP0340/challenge")
710 // e = SHA256(tag_hash || tag_hash || r || pu_key || msg)
711 cx_sha256_init_no_throw(&H);
712 CX_CHECK(cx_hash_no_throw(
713 (cx_hash_t *) &H, CX_LAST, BIP0340_challenge, sizeof(BIP0340_challenge), x, size));
714 cx_sha256_init_no_throw(&H);
715 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, x, size, NULL, 0));
716 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, x, size, NULL, 0));
717 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, sig, size, NULL, 0));
718 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, &pu_key->W[1], size, NULL, 0));
719 CX_CHECK(
720 cx_hash_no_throw((cx_hash_t *) &H, CX_LAST | CX_NO_REINIT, msg, msg_len, x, size));
721
722 // e = e % n
723 CX_CHECK(cx_bn_init(bn_x, x, size));
724 CX_CHECK(cx_bn_reduce(bn_r, bn_x, bn_n));
725 // n - e
726 CX_CHECK(cx_bn_sub(bn_r, bn_n, bn_r));
727 // s
728 CX_CHECK(cx_bn_init(bn_s, sig + size, size));
729 // [s].P + [n-e].Q where P is the generator of the curve
730 // and Q is the point representing the public key.
731 CX_CHECK(cx_ecpoint_double_scalarmul_bn(&R, &P, &Q, bn_s, bn_r));
732 CX_CHECK(cx_ecpoint_export_bn(&R, &bn_x, &bn_y));
733 CX_CHECK(cx_bn_is_odd(bn_y, &odd));
734 // r
735 CX_CHECK(cx_bn_init(bn_r, sig, size));
736 CX_CHECK(cx_bn_cmp(bn_x, bn_r, &diff));
737
738 if (odd || (diff != 0)) {
739 error = CX_INVALID_PARAMETER;
740 goto end;
741 }
742 verified = true;
743 break;
744
745 default:
746 error = CX_INVALID_PARAMETER;
747 goto end;
748 }
749
750end:
751 cx_bn_unlock();
752 return error == CX_OK && verified;
753}
754
755#endif // HAVE_ECSCHNORR
cx_hash.h
cx_ram.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
lcx_ecfp.h
Key pair generation based on elliptic curves.
lcx_eddsa.h
EDDSA (Edwards Curve Digital Signature Algorithm)
Generated by doxygen 1.9.8