ecdsa_impl.h File Reference

#include "scalar.h"
#include "field.h"
#include "group.h"
#include "ecmult.h"
#include "ecmult_gen.h"
#include "ecdsa.h"

Go to the source code of this file.

Functions
static int	secp256k1_der_read_len (const unsigned char **sigp, const unsigned char *sigend)
static int	secp256k1_der_parse_integer (secp256k1_scalar *r, const unsigned char **sig, const unsigned char *sigend)
static int	secp256k1_ecdsa_sig_parse (secp256k1_scalar *rr, secp256k1_scalar *rs, const unsigned char *sig, size_t size)
static int	secp256k1_ecdsa_sig_serialize (unsigned char *sig, size_t *size, const secp256k1_scalar *ar, const secp256k1_scalar *as)
static int	secp256k1_ecdsa_sig_verify (const secp256k1_ecmult_context *ctx, const secp256k1_scalar *sigr, const secp256k1_scalar *sigs, const secp256k1_ge *pubkey, const secp256k1_scalar *message)
static int	secp256k1_ecdsa_sig_sign (const secp256k1_ecmult_gen_context *ctx, secp256k1_scalar *sigr, secp256k1_scalar *sigs, const secp256k1_scalar *seckey, const secp256k1_scalar *message, const secp256k1_scalar *nonce, int *recid)

Variables
static const secp256k1_fe	secp256k1_ecdsa_const_order_as_fe
static const secp256k1_fe	secp256k1_ecdsa_const_p_minus_order

Function Documentation

secp256k1_der_parse_integer()

static int secp256k1_der_parse_integer ( secp256k1_scalar *  r, const unsigned char **  sig, const unsigned char *  sigend  )

static

secp256k1_der_read_len()

static int secp256k1_der_read_len ( const unsigned char **  sigp, const unsigned char *  sigend  )

static

secp256k1_ecdsa_sig_parse()

static int secp256k1_ecdsa_sig_parse ( secp256k1_scalar *  rr, secp256k1_scalar *  rs, const unsigned char *  sig, size_t  size  )

static

secp256k1_ecdsa_sig_serialize()

static int secp256k1_ecdsa_sig_serialize ( unsigned char *  sig, size_t *  size, const secp256k1_scalar *  ar, const secp256k1_scalar *  as  )

static

secp256k1_ecdsa_sig_sign()

static int secp256k1_ecdsa_sig_sign ( const secp256k1_ecmult_gen_context *  ctx, secp256k1_scalar *  sigr, secp256k1_scalar *  sigs, const secp256k1_scalar *  seckey, const secp256k1_scalar *  message, const secp256k1_scalar *  nonce, int *  recid  )

static

secp256k1_ecdsa_sig_verify()

static int secp256k1_ecdsa_sig_verify ( const secp256k1_ecmult_context *  ctx, const secp256k1_scalar *  sigr, const secp256k1_scalar *  sigs, const secp256k1_ge *  pubkey, const secp256k1_scalar *  message  )

static

We now have the recomputed R point in pr, and its claimed x coordinate (modulo n) in xr. Naively, we would extract the x coordinate from pr (requiring a inversion modulo p), compute the remainder modulo n, and compare it to xr. However:

  xr == X(pr) mod n

<=> exists h. (xr + h * n < p && xr + h * n == X(pr)) [Since 2 * n > p, h can only be 0 or 1] <=> (xr == X(pr)) || (xr + n < p && xr + n == X(pr)) [In Jacobian coordinates, X(pr) is pr.x / pr.z^2 mod p] <=> (xr == pr.x / pr.z^2 mod p) || (xr + n < p && xr + n == pr.x / pr.z^2 mod p) [Multiplying both sides of the equations by pr.z^2 mod p] <=> (xr * pr.z^2 mod p == pr.x) || (xr + n < p && (xr + n) * pr.z^2 mod p == pr.x)

Thus, we can avoid the inversion, but we have to check both cases separately. secp256k1_gej_eq_x implements the (xr * pr.z^2 mod p == pr.x) test.

Variable Documentation

secp256k1_ecdsa_const_order_as_fe

const secp256k1_fe secp256k1_ecdsa_const_order_as_fe

static

Initial value:

= SECP256K1_FE_CONST(
    0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFEUL,
    0xBAAEDCE6UL, 0xAF48A03BUL, 0xBFD25E8CUL, 0xD0364141UL
)

Group order for secp256k1 defined as 'n' in "Standards for Efficient Cryptography" (SEC2) 2.7.1 sage: for t in xrange(1023, -1, -1): .. p = 2**256 - 2**32 - t .. if p.is_prime(): .. print 'x'p .. break 'fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f' sage: a = 0 sage: b = 7 sage: F = FiniteField (p) sage: 'x' % (EllipticCurve ([F (a), F (b)]).order()) 'fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141'

secp256k1_ecdsa_const_p_minus_order

const secp256k1_fe secp256k1_ecdsa_const_p_minus_order

static

Initial value:

= SECP256K1_FE_CONST(
    0, 0, 0, 1, 0x45512319UL, 0x50B75FC4UL, 0x402DA172UL, 0x2FC9BAEEUL
)

Difference between field and order, values 'p' and 'n' values defined in "Standards for Efficient Cryptography" (SEC2) 2.7.1. sage: p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F sage: a = 0 sage: b = 7 sage: F = FiniteField (p) sage: 'x' % (p - EllipticCurve ([F (a), F (b)]).order()) '14551231950b75fc4402da1722fc9baee'