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(cx_hash_no_throw((cx_hash_t *) &H, CX_LAST | CX_NO_REINIT, msg, size, sig, size));
124 }
125
126 // generate random
127 tries = 0;
128RETRY:
129 if (tries == CX_MAX_TRIES) {
130 goto end;
131 }
132
133 switch (mode & CX_MASK_RND) {
134 case CX_RND_PROVIDED:
135 if (tries) {
136 goto end;
137 }
138 CX_CHECK(cx_bn_init(bn_r, sig, size));
139 CX_CHECK(cx_bn_reduce(bn_k, bn_r, bn_n));
140 break;
141
142 case CX_RND_TRNG:
143 CX_CHECK(cx_bn_rng(bn_k, bn_n));
144 break;
145
146 default:
147 error = CX_INVALID_PARAMETER;
148 goto end;
149 }
150 if ((mode & CX_MASK_EC) == CX_ECSCHNORR_BIP0340) {
151 CX_CHECK(cx_bn_cmp_u32(bn_k, 0, &diff));
152 if (diff == 0) {
153 error = CX_INVALID_PARAMETER;
154 goto end;
155 }
156 }
157 CX_CHECK(cx_bn_export(bn_k, sig, size));
158
159 // sign
160 tries++;
161RETRY2:
162 CX_CHECK(cx_ecdomain_generator_bn(pv_key->curve, &Q));
163 CX_CHECK(cx_ecpoint_rnd_fixed_scalarmul(&Q, sig, size));
164
165 switch (mode & CX_MASK_EC) {
166 case CX_ECSCHNORR_ISO14888_XY:
167 case CX_ECSCHNORR_ISO14888_X:
168 // 1. Generate a random k from [1, ..., order-1]
169 // 2. Q = G*k
170 // 3. r = H(Q.x||Q.y||M)
171 // 4. s = (k+r*pv_key.d)%n
172 cx_sha256_init_no_throw(&H);
173 CX_CHECK(cx_ecpoint_export(&Q, sig, size, NULL, 0));
174 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, sig, size, NULL, 0));
175 if ((mode & CX_MASK_EC) == CX_ECSCHNORR_ISO14888_XY) {
176 CX_CHECK(cx_ecpoint_export(&Q, NULL, 0, sig, size));
177 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, sig, size, NULL, 0));
178 }
179 CX_CHECK(cx_hash_no_throw(
180 (cx_hash_t *) &H, CX_LAST | CX_NO_REINIT, msg, msg_len, R, sizeof(R)));
181
182 CX_CHECK(cx_bn_init(bn_d, R, 32));
183 CX_CHECK(cx_bn_reduce(bn_r, bn_d, bn_n));
184 CX_CHECK(cx_bn_cmp_u32(bn_r, 0, &diff));
185 if (diff == 0) {
186 cx_bn_unlock();
187 goto RETRY;
188 }
189
190 CX_CHECK(cx_bn_init(bn_d, pv_key->d, pv_key->d_len));
191 CX_CHECK(cx_bn_mod_mul(bn_s, bn_d, bn_r, bn_n));
192 CX_CHECK(cx_bn_mod_add(bn_s, bn_k, bn_s, bn_n));
193 CX_CHECK(cx_bn_set_u32(bn_k, 0));
194 CX_CHECK(cx_bn_mod_sub(bn_s, bn_s, bn_k, bn_n));
195
196 CX_CHECK(cx_bn_cmp_u32(bn_s, 0, &diff));
197 if (diff == 0) {
198 goto RETRY;
199 }
200 CX_CHECK(cx_bn_export(bn_s, S, 32));
201 break;
202
203 case CX_ECSCHNORR_BSI03111:
204 // 1. Q = G*k
205 // 2. r = H((msg+xQ), and r%n != 0
206 // 3. s = (k-r*pv_key.d)%n
207 // r = H((msg+xQ), and r%n != 0
208 cx_sha256_init_no_throw(&H);
209 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, msg, msg_len, NULL, 0));
210 CX_CHECK(cx_ecpoint_export(&Q, sig, size, NULL, 0));
211 CX_CHECK(cx_hash_no_throw(
212 (cx_hash_t *) &H, CX_LAST | CX_NO_REINIT, sig, size, R, sizeof(R)));
213
214 CX_CHECK(cx_bn_init(bn_d, R, CX_SHA256_SIZE));
215 CX_CHECK(cx_bn_reduce(bn_r, bn_d, bn_n));
216 CX_CHECK(cx_bn_cmp_u32(bn_r, 0, &diff));
217 if (diff == 0) {
218 goto RETRY;
219 }
220
221 // s = (k-r*pv_key.d)%n
222 CX_CHECK(cx_bn_init(bn_d, pv_key->d, pv_key->d_len));
223 CX_CHECK(cx_bn_mod_mul(bn_s, bn_d, bn_r, bn_n));
224 CX_CHECK(cx_bn_mod_sub(bn_s, bn_k, bn_s, bn_n));
225
226 CX_CHECK(cx_bn_cmp_u32(bn_s, 0, &diff));
227 if (diff == 0) {
228 goto RETRY;
229 }
230 CX_CHECK(cx_bn_export(bn_s, S, 32));
231 break;
232
233 case CX_ECSCHNORR_Z:
234 // https://github.com/Zilliqa/Zilliqa/blob/master/src/libCrypto/Schnorr.cpp#L580
235 // https://docs.zilliqa.com/whitepaper.pdf
236 // 1. Generate a random k from [1, ..., order-1]
237 // 2. Compute the commitment Q = kG, where G is the base point
238 // 3. Compute the challenge r = H(Q, kpub, m) [CME: mod n according to pdf/code, Q and
239 // kpub compressed "02|03 x" according to code)
240 // 4. If r = 0 mod(order), goto 1
241 // 4. Compute s = k - r*kpriv mod(order)
242 // 5. If s = 0 goto 1.
243 // 5 Signature on m is (r, s)
244
245 // Q
246 cx_sha256_init_no_throw(&H);
247 CX_CHECK(cx_ecpoint_export(&Q, NULL, 0, sig, size));
248 odd = sig[size - 1] & 1;
249 CX_CHECK(cx_ecpoint_export(&Q, sig + 1, size, NULL, 0));
250 sig[0] = odd ? 0x03 : 0x02;
251 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, sig, 1 + size, NULL, 0)); // Q
252 // kpub
253 CX_CHECK(cx_ecdomain_generator_bn(pv_key->curve, &Q));
254 CX_CHECK(cx_ecpoint_rnd_fixed_scalarmul(&Q, pv_key->d, pv_key->d_len));
255 CX_CHECK(cx_ecpoint_export(&Q, NULL, 0, sig, size));
256 odd = sig[size - 1] & 1;
257 CX_CHECK(cx_ecpoint_export(&Q, sig + 1, size, NULL, 0));
258 sig[0] = odd ? 0x03 : 0x02;
259 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, sig, 1 + size, NULL, 0)); // Q
260 // m
261 CX_CHECK(cx_hash_no_throw(
262 (cx_hash_t *) &H, CX_LAST | CX_NO_REINIT, msg, msg_len, R, sizeof(R)));
263
264 // Compute the challenge r = H(Q, kpub, m)
265 //[CME: mod n according to pdf/code, Q and kpub compressed "02|03 x" according to code)
266 CX_CHECK(cx_bn_init(bn_d, R, CX_SHA256_SIZE));
267 CX_CHECK(cx_bn_reduce(bn_r, bn_d, bn_n));
268 CX_CHECK(cx_bn_cmp_u32(bn_r, 0, &diff));
269 if (diff == 0) {
270 goto RETRY;
271 }
272 CX_CHECK(cx_bn_export(bn_r, R, 32));
273
274 CX_CHECK(cx_bn_init(bn_d, pv_key->d, pv_key->d_len));
275 CX_CHECK(cx_bn_mod_mul(bn_s, bn_d, bn_r, bn_n));
276 CX_CHECK(cx_bn_mod_sub(bn_s, bn_k, bn_s, bn_n));
277 CX_CHECK(cx_bn_cmp_u32(bn_s, 0, &diff));
278 if (diff == 0) {
279 goto RETRY;
280 }
281 CX_CHECK(cx_bn_export(bn_s, S, 32));
282 break;
283
284 case CX_ECSCHNORR_LIBSECP:
285 // Inputs: 32-byte message m, 32-byte scalar key x (!=0), 32-byte scalar nonce k (!=0)
286 // 1. Compute point R = k * G. Reject nonce if R's y coordinate is odd (or negate
287 // nonce).
288 // 2. Compute 32-byte r, the serialization of R's x coordinate.
289 // 3. Compute scalar h = Hash(r || m). Reject nonce if h == 0 or h >= order.
290 // 4. Compute scalar s = k - h * x.
291 // 5. The signature is (r, s).
292 // Q = G*k
293 CX_CHECK(cx_ecpoint_export(&Q, NULL, 0, sig, size));
294 odd = sig[size - 1] & 1;
295 if (odd) {
296 // if y is odd, k <- -k mod n = n-k, and retry
297 CX_CHECK(cx_bn_mod_sub(bn_k, bn_n, bn_k, bn_n));
298 CX_CHECK(cx_bn_export(bn_k, sig, size));
299 goto RETRY2;
300 }
301 // r = xQ
302 CX_CHECK(cx_ecpoint_export(&Q, R, size, NULL, 0));
303 CX_CHECK(cx_bn_init(bn_d, R, size));
304 CX_CHECK(cx_bn_reduce(bn_r, bn_d, bn_n));
305 CX_CHECK(cx_bn_cmp_u32(bn_r, 0, &diff));
306 if (diff == 0) {
307 goto RETRY;
308 }
309 // h = Hash(r || m).
310 cx_sha256_init_no_throw(&H);
311 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, R, size, NULL, 0));
312 CX_CHECK(cx_hash_no_throw(
313 (cx_hash_t *) &H, CX_LAST | CX_NO_REINIT, msg, msg_len, sig, sizeof(S)));
314 // Reject nonce if h == 0 or h >= order.
315 CX_CHECK(cx_bn_init(bn_r, sig, 32));
316 CX_CHECK(cx_bn_cmp_u32(bn_r, 0, &diff));
317 if (diff == 0) {
318 goto RETRY;
319 }
320 CX_CHECK(cx_bn_cmp(bn_r, bn_n, &diff));
321 if (diff >= 0) {
322 goto RETRY;
323 }
324 // s = k - h * x.
325 CX_CHECK(cx_bn_init(bn_d, pv_key->d, pv_key->d_len));
326 CX_CHECK(cx_bn_mod_mul(bn_s, bn_d, bn_r, bn_n));
327 CX_CHECK(cx_bn_mod_sub(bn_s, bn_k, bn_s, bn_n));
328 CX_CHECK(cx_bn_cmp_u32(bn_s, 0, &diff));
329 if (diff == 0) {
330 goto RETRY;
331 }
332 CX_CHECK(cx_bn_export(bn_s, S, 32));
333 break;
334
335 /* Schnorr signature with secp256k1 according to BIP0340
336 ** https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki */
337
338 case CX_ECSCHNORR_BIP0340:
339 CX_CHECK(cx_ecpoint_export(&Q, NULL, 0, sig, size));
340 odd = sig[size - 1] & 1;
341 if (odd) {
342 CX_CHECK(cx_bn_sub(bn_k, bn_n, bn_k));
343 CX_CHECK(cx_bn_export(bn_k, sig, size));
344 }
345 // Only take the x-coordinate
346 CX_CHECK(cx_ecpoint_export(&Q, R, size, NULL, 0));
347
348 // tag_hash = SHA256("BIP0340_challenge")
349 // e = SHA256(tag_hash || tag_hash || Rx || Px || msg)
350 cx_sha256_init_no_throw(&H);
351 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H,
352 CX_LAST,
353 BIP0340_challenge,
354 sizeof(BIP0340_challenge),
355 sig,
356 size));
357 cx_sha256_init_no_throw(&H);
358 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, sig, size, NULL, 0));
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, R, size, NULL, 0));
361 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, P, size, NULL, 0));
362 CX_CHECK(cx_hash_no_throw(
363 (cx_hash_t *) &H, CX_LAST | CX_NO_REINIT, msg, msg_len, sig, size));
364
365 // e = e % n
366 CX_CHECK(cx_bn_init(bn_s, sig, size));
367 CX_CHECK(cx_bn_reduce(bn_r, bn_s, bn_n));
368
369 // s = (k + e *d) % n
370 CX_CHECK(cx_bn_mod_mul(bn_s, bn_d, bn_r, bn_n));
371 CX_CHECK(cx_bn_mod_add(bn_s, bn_k, bn_s, bn_n));
372 CX_CHECK(cx_bn_set_u32(bn_k, 0));
373 CX_CHECK(cx_bn_mod_sub(bn_s, bn_s, bn_k, bn_n));
374
375 CX_CHECK(cx_bn_export(bn_s, S, size));
376 break;
377
378 default:
379 error = CX_INVALID_PARAMETER;
380 goto end;
381 }
382
383end:
384 cx_hash_destroy((cx_hash_t *) &H);
385 cx_bn_unlock();
386 if (error == CX_OK) {
387 if ((mode & CX_MASK_EC) == CX_ECSCHNORR_BIP0340) {
388 *sig_len = 64;
389 memcpy(sig, R, 32);
390 memcpy(sig + 32, S, 32);
391 }
392 else {
393 // encoding
394 *sig_len = cx_ecfp_encode_sig_der(sig, *sig_len, R, size, S, size);
395 }
396 }
397 return error;
398}
399
400bool cx_ecschnorr_verify(const cx_ecfp_public_key_t *pu_key,
401 uint32_t mode,
402 cx_md_t hashID,
403 const uint8_t *msg,
404 size_t msg_len,
405 const uint8_t *sig,
406 size_t sig_len)
407{
408 size_t size;
409 const uint8_t *r, *s;
410 size_t r_len, s_len;
411 cx_ecpoint_t R, P, Q;
412 uint8_t x[33];
413 bool odd;
414 volatile int verified;
415 cx_err_t error;
416 int diff;
417 bool is_on_curve = false;
418
419 cx_bn_t bn_d, bn_r, bn_s, bn_n;
420 cx_bn_t bn_x, bn_y, bn_p;
421
422 CX_CHECK(cx_ecdomain_parameters_length(pu_key->curve, &size));
423
424 // ECSCHNORR BIP0340 is only defined for secp256k1
425 if (((mode & CX_MASK_EC) == CX_ECSCHNORR_BIP0340) && (pu_key->curve != CX_CURVE_SECP256K1)) {
426 error = CX_EC_INVALID_CURVE;
427 verified = false;
428 goto end;
429 }
430
431 if (!CX_CURVE_RANGE(pu_key->curve, WEIERSTRASS) || hashID != CX_SHA256 || size != 32
432 || pu_key->W_len != 1 + 2 * size) {
433 return false;
434 }
435
436 if ((mode & CX_MASK_EC) != CX_ECSCHNORR_BIP0340) {
437 if (!cx_ecfp_decode_sig_der(sig, sig_len, size, &r, &r_len, &s, &s_len)) {
438 return false;
439 }
440 }
441
442 CX_CHECK(cx_bn_lock(size, 0));
443 verified = false;
444
445 CX_CHECK(cx_bn_alloc(&bn_n, size));
446 CX_CHECK(cx_ecdomain_parameter_bn(pu_key->curve, CX_CURVE_PARAM_Order, bn_n));
447 if ((mode & CX_MASK_EC) == CX_ECSCHNORR_BIP0340) {
448 CX_CHECK(cx_bn_alloc_init(&bn_r, size, sig, size));
449 CX_CHECK(cx_bn_alloc_init(&bn_s, size, sig + size, size));
450 }
451 else {
452 CX_CHECK(cx_bn_alloc_init(&bn_r, size, r, r_len));
453 CX_CHECK(cx_bn_alloc_init(&bn_s, size, s, s_len));
454 }
455
456 CX_CHECK(cx_bn_alloc(&bn_d, size));
457
458 CX_CHECK(cx_bn_cmp_u32(bn_r, 0, &diff));
459 if (diff == 0) {
460 goto end;
461 }
462 CX_CHECK(cx_bn_cmp_u32(bn_s, 0, &diff));
463 if (diff == 0) {
464 goto end;
465 }
466
467 CX_CHECK(cx_ecpoint_alloc(&P, pu_key->curve));
468 CX_CHECK(cx_ecpoint_alloc(&Q, pu_key->curve));
469 CX_CHECK(cx_ecpoint_alloc(&R, pu_key->curve));
470 CX_CHECK(cx_ecdomain_generator_bn(pu_key->curve, &P));
471 CX_CHECK(cx_ecpoint_init(&Q, &pu_key->W[1], size, &pu_key->W[1 + size], size));
472
473 switch (mode & CX_MASK_EC) {
474 case CX_ECSCHNORR_ISO14888_XY:
475 case CX_ECSCHNORR_ISO14888_X:
476 // 1. check...
477 // 2. Q = [s]G - [r]W
478 // If Q = 0, output Error and terminate.
479 // 3. v = H(Qx||Qy||M).
480 // 4. Output True if v = r, and False otherwise.
481
482 // 1.
483 CX_CHECK(cx_bn_cmp_u32(bn_r, 0, &diff));
484 if (diff == 0) {
485 break;
486 }
487 CX_CHECK(cx_bn_cmp(bn_n, bn_s, &diff));
488 if (diff <= 0) {
489 break;
490 }
491 CX_CHECK(cx_bn_cmp_u32(bn_s, 0, &diff));
492 if (diff == 0) {
493 break;
494 }
495 CX_CHECK(cx_bn_cmp(bn_n, bn_s, &diff));
496 if (diff <= 0) {
497 break;
498 }
499
500 // 2.
501 // sG - rW
502 CX_CHECK(cx_ecpoint_neg(&Q));
503 CX_CHECK(cx_ecpoint_double_scalarmul_bn(&R, &P, &Q, bn_s, bn_r));
504 // 3.
505 cx_sha256_init_no_throw(&H);
506 CX_CHECK(cx_ecpoint_export(&R, x, size, NULL, 0));
507 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, x, size, NULL, 0));
508 if ((mode & CX_MASK_EC) == CX_ECSCHNORR_ISO14888_XY) {
509 CX_CHECK(cx_ecpoint_export(&R, NULL, 0, x, size));
510 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, x, size, NULL, 0));
511 }
512 CX_CHECK(cx_hash_no_throw(
513 (cx_hash_t *) &H, CX_LAST | CX_NO_REINIT, msg, msg_len, x, sizeof(x)));
514 // 4.
515 CX_CHECK(cx_bn_init(bn_s, x, CX_SHA256_SIZE));
516 CX_CHECK(cx_bn_cmp(bn_r, bn_s, &diff));
517 if (diff == 0) {
518 verified = true;
519 }
520 break;
521
522 case CX_ECSCHNORR_BSI03111:
523 // 1. Verify that r in {0, . . . , 2**t - 1} and s in {1, 2, . . . , n - 1}.
524 // If the check fails, output False and terminate.
525 // 2. Q = [s]G + [r]W
526 // If Q = 0, output Error and terminate.
527 // 3. v = H(M||Qx)
528 // 4. Output True if v = r, and False otherwise.
529
530 // 1.
531 CX_CHECK(cx_bn_cmp_u32(bn_r, 0, &diff));
532 if (diff == 0) {
533 break;
534 }
535 CX_CHECK(cx_bn_cmp_u32(bn_s, 0, &diff));
536 if (diff == 0) {
537 break;
538 }
539 CX_CHECK(cx_bn_cmp(bn_n, bn_s, &diff));
540 if (diff <= 0) {
541 break;
542 }
543
544 // 2.
545 CX_CHECK(cx_ecpoint_double_scalarmul_bn(&R, &P, &Q, bn_s, bn_r));
546 // 3.
547 cx_sha256_init_no_throw(&H);
548 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, msg, msg_len, NULL, 0));
549 CX_CHECK(cx_ecpoint_export(&R, x, size, NULL, 0));
550 CX_CHECK(
551 cx_hash_no_throw((cx_hash_t *) &H, CX_LAST | CX_NO_REINIT, x, size, x, sizeof(x)));
552 // 4.
553 CX_CHECK(cx_bn_init(bn_s, x, CX_SHA256_SIZE));
554 CX_CHECK(cx_bn_cmp(bn_r, bn_s, &diff));
555 if (diff == 0) {
556 verified = true;
557 }
558 break;
559
560 case CX_ECSCHNORR_Z:
561 // The algorithm to check the signature (r, s) on a message m using a public
562 // key kpub is as follows
563 // 1. Check if r,s is in [1, ..., order-1]
564 // 2. Compute Q = sG + r*kpub
565 // 3. If Q = O (the neutral point), return 0;
566 // 4. r' = H(Q, kpub, m) [CME: mod n and Q and kpub compressed "02|03 x" according to
567 // pdf/code]
568 // 5. return r' == r
569
570 // r,s is in [1, ..., order-1]
571 CX_CHECK(cx_bn_cmp_u32(bn_r, 0, &diff));
572 if (diff == 0) {
573 break;
574 }
575 CX_CHECK(cx_bn_cmp(bn_r, bn_n, &diff));
576 if (diff >= 0) {
577 break;
578 }
579 CX_CHECK(cx_bn_cmp_u32(bn_s, 0, &diff));
580 if (diff == 0) {
581 break;
582 }
583 CX_CHECK(cx_bn_cmp(bn_s, bn_n, &diff));
584 if (diff >= 0) {
585 break;
586 }
587
588 // Q = sG + r*kpub
589 CX_CHECK(cx_ecpoint_double_scalarmul_bn(&R, &P, &Q, bn_s, bn_r));
590 // r' = H(Q, kpub, m)
591 cx_sha256_init_no_throw(&H);
592 // Q
593 CX_CHECK(cx_ecpoint_export(&R, NULL, 0, x, size));
594 odd = x[size - 1] & 1;
595 CX_CHECK(cx_ecpoint_export(&R, x + 1, size, NULL, 0));
596 x[0] = odd ? 0x03 : 0x02;
597 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, x, 1 + size, NULL, 0)); // Q
598 // kpub
599 memmove(x + 1, &pu_key->W[1], size);
600 x[0] = (pu_key->W[1 + 2 * size - 1] & 1) ? 0x03 : 0x02;
601 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, x, 1 + size, NULL, 0)); // kpub
602 // m
603 CX_CHECK(cx_hash_no_throw(
604 (cx_hash_t *) &H, CX_LAST | CX_NO_REINIT, msg, msg_len, x, sizeof(x))); // m
605
606 CX_CHECK(cx_bn_init(bn_d, x, CX_SHA256_SIZE));
607 CX_CHECK(cx_bn_reduce(bn_s, bn_d, bn_n));
608 CX_CHECK(cx_bn_cmp(bn_r, bn_s, &diff));
609 if (diff == 0) {
610 verified = true;
611 }
612 break;
613
614 case CX_ECSCHNORR_LIBSECP:
615 // Verification:
616 // Inputs: 32-byte message m, public key point Q, signature: (32-byte r, scalar s)
617 // 1. Signature is invalid if s >= order.
618 // 2. Signature is invalid if r >= p.
619 // 3. Compute scalar h = Hash(r || m). Signature is invalid if h == 0 or h >= order.
620 // 4. Option 1 (faster for single verification):
621 // 5. Compute point R = h * Q + s * G. Signature is invalid if R is infinity or R's y
622 // coordinate is odd.
623 // 6. Signature is valid if the serialization of R's x coordinate equals r.
624 // s < order and r < field.
625
626 // 1. 2.
627 CX_CHECK(cx_bn_cmp_u32(bn_r, 0, &diff));
628 if (diff == 0) {
629 verified = false;
630 break;
631 }
632 CX_CHECK(cx_bn_cmp_u32(bn_s, 0, &diff));
633 if (diff == 0) {
634 verified = false;
635 break;
636 }
637 CX_CHECK(cx_bn_cmp(bn_n, bn_s, &diff));
638 if (diff <= 0) {
639 verified = false;
640 break;
641 }
642 // h = Hash(r||m), and h!=0, and h<order
643 cx_sha256_init_no_throw(&H);
644 CX_CHECK(cx_bn_export(bn_r, x, size));
645 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, x, size, NULL, 0));
646 CX_CHECK(cx_hash_no_throw(
647 (cx_hash_t *) &H, CX_LAST | CX_NO_REINIT, msg, msg_len, x, sizeof(x)));
648 CX_CHECK(cx_bn_init(bn_s, x, CX_SHA256_SIZE));
649 CX_CHECK(cx_bn_cmp_u32(bn_s, 0, &diff));
650 if (diff == 0) {
651 break;
652 }
653 CX_CHECK(cx_bn_cmp(bn_s, bn_n, &diff));
654 if (diff >= 0) {
655 break;
656 }
657 // R = h*W + s*G, and Ry is NOT odd, and Rx=r
658 CX_CHECK(cx_bn_init(bn_d, s, s_len));
659 CX_CHECK(cx_ecpoint_double_scalarmul_bn(&R, &P, &Q, bn_d, bn_s));
660 CX_CHECK(cx_ecpoint_export_bn(&R, &bn_s, &bn_d));
661 CX_CHECK(cx_bn_is_odd(bn_d, &odd));
662 if (odd) {
663 break;
664 }
665 CX_CHECK(cx_bn_cmp(bn_r, bn_s, &diff));
666 if (diff == 0) {
667 verified = true;
668 }
669 break;
670
671 /* Schnorr signature verification with secp256k1 according to BIP0340
672 ** https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki */
673
674 case CX_ECSCHNORR_BIP0340:
675 // Q = lift_x(pu_key)
676 CX_CHECK(cx_bn_alloc(&bn_x, size));
677 CX_CHECK(cx_bn_alloc(&bn_y, size));
678 CX_CHECK(cx_bn_alloc(&bn_p, size));
679 CX_CHECK(cx_ecdomain_parameter_bn(pu_key->curve, CX_CURVE_PARAM_Field, bn_p));
680 CX_CHECK(cx_ecpoint_export_bn(&Q, &bn_x, &bn_y));
681 // c = x^3 + 7 mod p
682 CX_CHECK(cx_bn_set_u32(bn_s, 3));
683 CX_CHECK(cx_bn_mod_pow_bn(bn_r, bn_x, bn_s, bn_p));
684 CX_CHECK(cx_bn_set_u32(bn_s, 7));
685 CX_CHECK(cx_bn_mod_add(bn_r, bn_r, bn_s, bn_p));
686 // y = c^(p+1)/4 mod p
687 CX_CHECK(cx_bn_copy(bn_s, bn_p));
688 CX_CHECK(cx_bn_set_u32(bn_d, 1));
689 CX_CHECK(cx_bn_add(bn_s, bn_s, bn_d));
690 CX_CHECK(cx_bn_shr(bn_s, 2));
691 CX_CHECK(cx_bn_mod_pow_bn(bn_y, bn_r, bn_s, bn_p));
692
693 CX_CHECK(cx_bn_is_odd(bn_y, &odd));
694 // If y is even, Qy = y otherwise Qy = p - y
695 if (odd) {
696 CX_CHECK(cx_bn_sub(bn_y, bn_p, bn_y));
697 }
698 CX_CHECK(cx_ecpoint_init_bn(&Q, bn_x, bn_y));
699 CX_CHECK(cx_ecpoint_is_on_curve(&Q, &is_on_curve));
700 if (!is_on_curve) {
701 error = CX_EC_INVALID_POINT;
702 goto end;
703 }
704 // tag_hash = SHA256("BIP0340/challenge")
705 // e = SHA256(tag_hash || tag_hash || r || pu_key || msg)
706 cx_sha256_init_no_throw(&H);
707 CX_CHECK(cx_hash_no_throw(
708 (cx_hash_t *) &H, CX_LAST, BIP0340_challenge, sizeof(BIP0340_challenge), x, size));
709 cx_sha256_init_no_throw(&H);
710 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, x, size, NULL, 0));
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, sig, size, NULL, 0));
713 CX_CHECK(cx_hash_no_throw((cx_hash_t *) &H, 0, &pu_key->W[1], size, NULL, 0));
714 CX_CHECK(
715 cx_hash_no_throw((cx_hash_t *) &H, CX_LAST | CX_NO_REINIT, msg, msg_len, x, size));
716
717 // e = e % n
718 CX_CHECK(cx_bn_init(bn_x, x, size));
719 CX_CHECK(cx_bn_reduce(bn_r, bn_x, bn_n));
720 // n - e
721 CX_CHECK(cx_bn_sub(bn_r, bn_n, bn_r));
722 // s
723 CX_CHECK(cx_bn_init(bn_s, sig + size, size));
724 // [s].P + [n-e].Q where P is the generator of the curve
725 // and Q is the point representing the public key.
726 CX_CHECK(cx_ecpoint_double_scalarmul_bn(&R, &P, &Q, bn_s, bn_r));
727 CX_CHECK(cx_ecpoint_export_bn(&R, &bn_x, &bn_y));
728 CX_CHECK(cx_bn_is_odd(bn_y, &odd));
729 // r
730 CX_CHECK(cx_bn_init(bn_r, sig, size));
731 CX_CHECK(cx_bn_cmp(bn_x, bn_r, &diff));
732
733 if (odd || (diff != 0)) {
734 error = CX_INVALID_PARAMETER;
735 goto end;
736 }
737 verified = true;
738 break;
739
740 default:
741 error = CX_INVALID_PARAMETER;
742 goto end;
743 }
744
745end:
746 cx_bn_unlock();
747 return error == CX_OK && verified;
748}
749
750#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