Bitcoin ABC  0.22.13
P2P Digital Currency
schnorr_impl.h
Go to the documentation of this file.
1 /***********************************************************************
2  * Copyright (c) 2017 Amaury SÉCHET *
3  * Distributed under the MIT software license, see the accompanying *
4  * file COPYING or http://www.opensource.org/licenses/mit-license.php. *
5  ***********************************************************************/
6 
7 #ifndef _SECP256K1_SCHNORR_IMPL_H_
8 #define _SECP256K1_SCHNORR_IMPL_H_
9 
10 #include <string.h>
11 
12 #include "schnorr.h"
13 #include "field.h"
14 #include "group.h"
15 #include "hash.h"
16 #include "ecmult.h"
17 #include "ecmult_gen.h"
18 
53  const unsigned char *sig64,
54  secp256k1_ge *pubkey,
55  const unsigned char *msg32
56 ) {
57  secp256k1_gej Pj, Rj;
58  secp256k1_fe Rx;
59  secp256k1_scalar e, s;
60  int overflow;
61 
63 
64  /* Extract s */
65  overflow = 0;
66  secp256k1_scalar_set_b32(&s, sig64 + 32, &overflow);
67  if (overflow) {
68  return 0;
69  }
70 
71  /* Extract R.x */
72  if (!secp256k1_fe_set_b32(&Rx, sig64)) {
73  return 0;
74  }
75 
76  /* Compute e */
77  secp256k1_schnorr_compute_e(&e, sig64, pubkey, msg32);
78 
79  /* Verify the signature */
81  secp256k1_gej_set_ge(&Pj, pubkey);
82  secp256k1_ecmult(ctx, &Rj, &Pj, &e, &s);
83  if (secp256k1_gej_is_infinity(&Rj)) {
84  return 0;
85  }
86 
87  /* Check that R.x is what we expect */
88  if (!secp256k1_gej_eq_x_var(&Rx, &Rj)) {
89  return 0;
90  }
91 
92  /* Check that jacobi(R.y) is 1 */
93  if (!secp256k1_gej_has_quad_y_var(&Rj)) {
94  return 0;
95  }
96 
97  /* All good, we have a valid signature. */
98  return 1;
99 }
100 
102  secp256k1_scalar* e,
103  const unsigned char *r,
104  secp256k1_ge *p,
105  const unsigned char *msg32
106 ) {
107  int overflow = 0;
108  size_t size = 0;
109  secp256k1_sha256 sha;
110  unsigned char buf[33];
112 
113  /* R.x */
114  secp256k1_sha256_write(&sha, r, 32);
115 
116  /* compressed P */
117  secp256k1_eckey_pubkey_serialize(p, buf, &size, 1);
118  VERIFY_CHECK(size == 33);
119  secp256k1_sha256_write(&sha, buf, 33);
120 
121  /* msg */
122  secp256k1_sha256_write(&sha, msg32, 32);
123 
124  /* compute e */
125  secp256k1_sha256_finalize(&sha, buf);
126  secp256k1_scalar_set_b32(e, buf, &overflow);
127  return !overflow & !secp256k1_scalar_is_zero(e);
128 }
129 
131  const secp256k1_context* ctx,
132  unsigned char *sig64,
133  const unsigned char *msg32,
134  const secp256k1_scalar *privkey,
135  secp256k1_ge *pubkey,
136  secp256k1_nonce_function noncefp,
137  const void *ndata
138 ) {
139  secp256k1_ge R;
140  secp256k1_gej Rj;
141  secp256k1_scalar k, e, s;
143 
146 
147  if (!secp256k1_schnorr_sig_generate_k(ctx, &k, msg32, privkey, noncefp, ndata)) {
148  return 0;
149  }
150 
151  /* Compute R */
152  secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &Rj, &k);
153  secp256k1_ge_set_gej(&R, &Rj);
154 
155  /*
156  * We declassify R to allow using it as a branch point.
157  * This is fine because R is not a secret.
158  */
159  secp256k1_declassify(ctx, &R, sizeof(R));
162 
163  /* Compute the signature. */
165  secp256k1_fe_get_b32(sig64, &R.x);
166  secp256k1_schnorr_compute_e(&e, sig64, pubkey, msg32);
167  secp256k1_scalar_mul(&s, &e, privkey);
168  secp256k1_scalar_add(&s, &s, &k);
169  secp256k1_scalar_get_b32(sig64 + 32, &s);
170 
171  /* Cleanup locals that may contain private data. */
173  return 1;
174 }
175 
177  const secp256k1_context* ctx,
178  secp256k1_scalar *k,
179  const unsigned char *msg32,
180  const secp256k1_scalar *privkey,
181  secp256k1_nonce_function noncefp,
182  const void *ndata
183 ) {
184  int ret = 0;
185  unsigned int count = 0;
186  unsigned char nonce32[32], seckey[32];
187 
188  /* Seed used to make sure we generate different values of k for schnorr */
189  const unsigned char secp256k1_schnorr_algo16[17] = "Schnorr+SHA256 ";
190 
191  if (noncefp == NULL) {
193  }
194 
195  secp256k1_scalar_get_b32(seckey, privkey);
196  while (1) {
197  int overflow;
198  ret = noncefp(nonce32, msg32, seckey, secp256k1_schnorr_algo16, (void*)ndata, count++);
199  if (!ret) {
200  break;
201  }
202 
203  secp256k1_scalar_set_b32(k, nonce32, &overflow);
204  overflow |= secp256k1_scalar_is_zero(k);
205  /* The nonce is still secret here, but it overflowing or being zero is is less likely than 1:2^255. */
206  secp256k1_declassify(ctx, &overflow, sizeof(overflow));
207  if (!overflow) {
208  break;
209  }
210 
212  }
213 
214  /* Cleanup locals that may contain private data. */
215  memset(seckey, 0, 32);
216  memset(nonce32, 0, 32);
217  return ret;
218 }
219 
220 #endif
static void secp256k1_scalar_mul(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b)
Multiply two scalars (modulo the group order).
static int secp256k1_ge_is_infinity(const secp256k1_ge *a)
Check whether a group element is the point at infinity.
#define VERIFY_CHECK(cond)
Definition: util.h:68
static int secp256k1_gej_is_infinity(const secp256k1_gej *a)
Check whether a group element is the point at infinity.
static int secp256k1_gej_has_quad_y_var(const secp256k1_gej *a)
Check whether a group element&#39;s y coordinate is a quadratic residue.
static void secp256k1_ecmult_gen(const secp256k1_ecmult_gen_context *ctx, secp256k1_gej *r, const secp256k1_scalar *a)
Multiply with the generator: R = a*G.
SECP256K1_API const secp256k1_nonce_function secp256k1_nonce_function_default
A default safe nonce generation function (currently equal to secp256k1_nonce_function_rfc6979).
Definition: secp256k1.c:478
static int secp256k1_schnorr_compute_e(secp256k1_scalar *e, const unsigned char *r, secp256k1_ge *p, const unsigned char *msg32)
Definition: schnorr_impl.h:101
secp256k1_context * ctx
static void secp256k1_scalar_negate(secp256k1_scalar *r, const secp256k1_scalar *a)
Compute the complement of a scalar (modulo the group order).
static int secp256k1_eckey_pubkey_serialize(secp256k1_ge *elem, unsigned char *pub, size_t *size, int compressed)
static int secp256k1_scalar_is_zero(const secp256k1_scalar *a)
Check whether a scalar equals zero.
static void secp256k1_ecmult(const secp256k1_ecmult_context *ctx, secp256k1_gej *r, const secp256k1_gej *a, const secp256k1_scalar *na, const secp256k1_scalar *ng)
Double multiply: R = na*A + ng*G.
static void secp256k1_scalar_set_b32(secp256k1_scalar *r, const unsigned char *bin, int *overflow)
Set a scalar from a big endian byte array.
A group element of the secp256k1 curve, in jacobian coordinates.
Definition: group.h:24
static SECP256K1_INLINE void secp256k1_declassify(const secp256k1_context *ctx, const void *p, size_t len)
Definition: secp256k1.c:236
secp256k1_ecmult_gen_context ecmult_gen_ctx
Definition: secp256k1.c:72
#define ARG_CHECK(cond)
Definition: secp256k1.c:29
static int secp256k1_schnorr_sig_verify(const secp256k1_ecmult_context *ctx, const unsigned char *sig64, secp256k1_ge *pubkey, const unsigned char *msg32)
Custom Schnorr-based signature scheme.
Definition: schnorr_impl.h:51
static void secp256k1_ge_set_gej(secp256k1_ge *r, secp256k1_gej *a)
Set a group element equal to another which is given in jacobian coordinates.
static int secp256k1_fe_is_quad_var(const secp256k1_fe *a)
Checks whether a field element is a quadratic residue.
static void secp256k1_scalar_clear(secp256k1_scalar *r)
Clear a scalar to prevent the leak of sensitive data.
A group element of the secp256k1 curve, in affine coordinates.
Definition: group.h:14
secp256k1_fe x
Definition: group.h:15
static int secp256k1_gej_eq_x_var(const secp256k1_fe *x, const secp256k1_gej *a)
Compare the X coordinate of a group element (jacobian).
A scalar modulo the group order of the secp256k1 curve.
Definition: scalar_4x64.h:13
static int secp256k1_scalar_cond_negate(secp256k1_scalar *a, int flag)
Conditionally negate a number, in constant time.
static void secp256k1_scalar_get_b32(unsigned char *bin, const secp256k1_scalar *a)
Convert a scalar to a byte array.
static void secp256k1_sha256_write(secp256k1_sha256 *hash, const unsigned char *data, size_t size)
static int secp256k1_fe_set_b32(secp256k1_fe *r, const unsigned char *a)
Set a field element equal to 32-byte big endian value.
static int secp256k1_schnorr_sig_sign(const secp256k1_context *ctx, unsigned char *sig64, const unsigned char *msg32, const secp256k1_scalar *privkey, secp256k1_ge *pubkey, secp256k1_nonce_function noncefp, const void *ndata)
Definition: schnorr_impl.h:130
static int secp256k1_scalar_add(secp256k1_scalar *r, const secp256k1_scalar *a, const secp256k1_scalar *b)
Add two scalars together (modulo the group order).
int(* secp256k1_nonce_function)(unsigned char *nonce32, const unsigned char *msg32, const unsigned char *key32, const unsigned char *algo16, void *data, unsigned int attempt)
A pointer to a function to deterministically generate a nonce.
Definition: secp256k1.h:100
static void secp256k1_fe_normalize(secp256k1_fe *r)
Field element module.
static void secp256k1_fe_get_b32(unsigned char *r, const secp256k1_fe *a)
Convert a field element to a 32-byte big endian value.
static int count
Definition: tests.c:35
static void secp256k1_sha256_initialize(secp256k1_sha256 *hash)
static void secp256k1_gej_set_ge(secp256k1_gej *r, const secp256k1_ge *a)
Set a group element (jacobian) equal to another which is given in affine coordinates.
static int secp256k1_schnorr_sig_generate_k(const secp256k1_context *ctx, secp256k1_scalar *k, const unsigned char *msg32, const secp256k1_scalar *privkey, secp256k1_nonce_function noncefp, const void *ndata)
Definition: schnorr_impl.h:176
secp256k1_fe y
Definition: group.h:16
static void secp256k1_sha256_finalize(secp256k1_sha256 *hash, unsigned char *out32)
static int secp256k1_ecmult_gen_context_is_built(const secp256k1_ecmult_gen_context *ctx)