nish/crypto/p256

ECDSA over NIST P-256 (secp256r1), with the deterministic nonces of RFC 6979.

import {
  P256SignScratch,
  P256_POINT_SIZE,
  P256_SCALAR_SIZE,
  P256_SIGNATURE_SIZE,
  p256Ecdh,
  p256PublicKey,
  p256Sign,
  p256SignSha256,
  p256SignSha256Into,
  p256Verify,
  p256VerifySha256,
} from "nish/crypto/p256";
import { p256PublicKey, p256SignSha256, p256VerifySha256 } from "nish/crypto/p256";
import { Secret, secret, wipe } from "nish:secret";

const raw: u8[] = new Array<u8>(32)
crypto.getRandomValues(raw)                              // in [1, n) but for about one draw in 2^32
const priv: Secret<u8[]> = secret(raw)
const message: u8[] = [104, 105]
const pub: u8[] | null = p256PublicKey(priv)             // 65 bytes, 0x04 || X || Y
const sig: u8[] | null = p256SignSha256(priv, message)   // 64 bytes, r || s
wipe(priv)
if (pub !== null && sig !== null) {
  p256VerifySha256(pub, message, sig)                    // true
}

A private key is 32 big-endian bytes holding a scalar in [1, n); a public key is the uncompressed SEC1 encoding of SEC 1 §2.3.3; a signature is r and s as 32 big-endian bytes each. DER, which X.509 and TLS wrap a signature in, is not this module's business. Anything of the wrong length, a private key of 0 or n or more, a public key that is not on the curve, and an r or s of 0 or n or more answer null from the signing side and false from the verifying side, never a panic.

Ported from fiat-crypto (https://github.com/mit-plv/fiat-crypto), fiat-c/src/p256_64.c, fiat-c/src/p256_32.c and fiat-c/src/p256_scalar_32.c. Copyright (c) 2015-2020 the fiat-crypto authors (see the AUTHORS file). Used under the MIT licence; see std/crypto/LICENSE-fiat-crypto.

Ported from libsecp256k1 (https://github.com/bitcoin-core/secp256k1), src/modinv32_impl.h. Copyright (c) 2020 Peter Dettman. Used under the MIT licence; see std/crypto/LICENSE-libsecp256k1.

What is ported and what is not

The p256Fiat* functions are fiat-crypto's generated, formally verified Montgomery arithmetic, statement for statement, with fiat's variable names: mul, square, add and sub mod p from the 64-bit file, on four u64 limbs, and selectznz, nonzero and set_one mod p and mul, add and set_one mod n from the 32-bit files, on eight u32 limbs with u64 products. Both represent an element by the same 256 bits with the same R = 2^256, so every element is stored as eight u32 words, low first, and the 64-bit functions read word pairs into u64 locals (arg1Limb0 is words 0 and 1) and write their limbs back as word pairs. That is one of four things the translation changes; nothing else changes. Reading every limb into a local before any arithmetic also keeps what the 32-bit square did on purpose: its input's pointer is not spilled in the way the aarch64 disassembly check once misread (#334), so ct_asm_p256 keeps reading square on aarch64.

C's out-pointers become answers. In the 32-bit functions each of fiat's addcarryx, subborrowx and mulx helpers answers its two outputs packed, the first in the low 32 bits and the second above them, and the caller splits them. In the 64-bit functions the two outputs need 65 or 128 bits, which Nish has no integer for, so each comes from its own helper: the sum, difference or low product by wrapping arithmetic, the carry or borrow from the top bits of the operands and the answer, and the high product from four 32-by-32 products (p256FiatMulxU64Hi). Either way only the outputs fiat goes on to read are declared. And each function opens with a length guard, so that the literal indices after it compile with no bounds check.

And constants above 2^53, which no literal can spell, are p256FiatWord64 of their halves. The scalar functions use the 32-bit field functions' four helpers, which fiat generates identically for both. The scalar inverse, p256ScalarInverse, and the field's, p256FieldInvert, are libsecp256k1's 32-bit safegcd (modinv32), function for function; the section that holds it says what changes. Everything else in this file — the curve, the encodings, the comb and ECDSA — is written for this module from the documents it names.

The curve

The curve is y^2 = x^3 - 3x + b over GF(p), p = 2^256 - 2^224 + 2^192 + 2^96 - 1, with the base point G and its order n from SEC 2 §2.4.2 (FIPS 186-4 §D.1.2.3).

Points are projective (X : Y : Z), Z = 0 the identity, and are added and doubled with the complete formulas of J. Renes, C. Costello and L. Batina, "Complete addition formulas for prime order elliptic curves" (EUROCRYPT 2016), Algorithms 4 and 6 for a = -3. Complete means no input is exceptional: P + P, P + (-P) and P + O all come out of the same straight line of field operations, so there is no case to branch on.

Constant time where a secret is involved

A private key and a nonce are only ever multiplied by G, and that by p256BaseMult, a signed all-bits-set comb (Hamburg, "Fast and compact elliptic-curve cryptography", 2012) over a precomputed table: 11 combs of 6 teeth 4 bits apart, 32 entries each, every entry the top tooth plus or minus each of the five below it, as affine points in the Montgomery domain (p256BaseTable, 22 KiB, written by scripts/gen-p256-table.mjs; ECC-7). The scalar is recoded to m = (k + 2^264 - 1) / 2 mod n, so that every bit of m stands for plus or minus its power of two; four rows of 11 mixed additions with a doubling between rows replace the 256 doublings and 64 additions of a window, whatever the scalar.

Every digit names an entry, none of them the identity, so every addition is kept. Each addition reads all 32 entries of its comb and keeps one by an all-ones mask from ctEq on the digit's low five bits (flipped when the top tooth is clear), ORing every entry's limbs under its mask, and negates its Y by fiat's conditional move on the top tooth, so neither a branch nor an address depends on the scalar. p256ScalarMult, a fixed 4-bit window over sixteen multiples of a point, is what ECDH multiplies the peer's key by, and the reference the comb is held to bit for bit (tests/link/crypto_p256_agree).

The signer inverts the nonce by Bernstein and Yang's safegcd, p256ScalarInverse: twenty batches of thirty divsteps, each a fixed run of masks and adds, whatever the scalar, so its loops count constants and no branch or address follows the nonce. Verification inverts its public s with the same function: a variable-time twin could stop once g is zero, but it would save at most the constant-time one's own cost, under 1% of a verification, and add a second path to audit. Fermat's a^(n - 2), which both used before, is the reference the safegcd is held to bit for bit, in the test's seam (tests/link/crypto_p256_inverse). Every field inversion — of a Z that follows the key or the nonce in the public key, ECDH and signing — is the same safegcd modulo p, p256FieldInvert, on the same divstep and update functions.

The branches that remain are on public facts: a length, a limb or bit position, whether a received key or signature is in range, and — once in about 2^32 signatures — RFC 6979's retry when a candidate nonce is not below n.

What is verified by disassembly and what is discipline

tests/cases/ct_asm_p256 holds copies of fiat's field multiply, square, add and subtract, its scalar multiply and its conditional move, the table read by a secret digit, the complete doubling and addition, one window step of p256ScalarMult, the comb's recoding (with fiat's scalar add), digit, masked entry move, signed entry read, mixed addition and one whole comb step, and safegcd's thirty divsteps and its two matrix updates, to the check of tests/ct-asm.js, which refuses any branch, call it cannot follow or secret-indexed access in them on x86-64 and aarch64, following each call into the field functions.

The copies of the point functions take coordinate arrays rather than points, the table reads' loops are written out there and their offsets computed with wrapping arithmetic, as that fixture's header says; its main runs RFC 6979 A.2.5 through them, by the window and by the comb, and three inverses through the safegcd copies. The 64-window and 4-row loops, the table build, the inversions (safegcd's twenty-batch loop, its conversions, normalisation and limb loops among them), the recoding's byte read, the encodings and the nonce derivation are constant time by construction rather than by that proof.

Verification is variable time, on public values only

p256Verify computes u1 G + u2 Q in one interleaved pass, p256DoubleMultPublic: both scalars recoded as width-5 wNAF, eight odd multiples of each point, the doublings shared, and both the digits and the table reads follow the scalars. Every input to it is the signature, the digest or the public key. Nothing secret may be passed to it.

The private key is a `Secret`

The private key is a Secret (nish:secret, docs/LANGUAGE.md "Secrets"). p256PublicKey and p256Sign read it only inside expose / exposeWith, whose function the checker holds to reaching no I/O and no C, and every intermediate the key or the nonce reaches is wiped before the signature is returned (ECC-2, docs/security/crypto-ecc.md). That is why RFC 6979's HMAC is written out over Sha256 here (p256Mac) rather than taken from nish/crypto/hmac: its key blocks and hasher state have to be this module's to wipe.

Private names carry the p256 prefix because a std/ module's private functions share the importing program's flat symbol namespace (docs/wp26-stdlib.md §3e).

Functions

p256Ecdh

The ECDH shared secret of priv and the peer's public key peerPoint (SEC 1 §3.3.1): the 32-byte big-endian x coordinate of priv * peerPoint, as TLS 1.3 uses it (RFC 8446 §7.4.2). Answers null unless priv is a private key p256PublicKey would take and peerPoint is a 65-byte uncompressed point on the curve, and for a product at infinity, which a valid key and point cannot give. An x of zero is a point like any other and is answered.

const p256Ecdh: (
  priv: Secret<u8[]>,
  peerPoint: u8[],
) => Secret<u8[]> | null
privSecret<u8[]>required

This side's private key, 32 big-endian bytes.

peerPointu8[]required

The peer's 65-byte uncompressed public key.

returnsSecret<u8[]> | null

The 32-byte shared secret, or null for a refused key or point and a product at infinity.

p256PublicKey

The public key of priv: priv * G in the 65-byte uncompressed SEC 1 encoding. Answers null unless priv is P256_SCALAR_SIZE bytes holding a scalar in [1, n) — 0 and n and everything above are not private keys.

const p256PublicKey: (priv: Secret<u8[]>) => u8[] | null
privSecret<u8[]>required

The private key, 32 big-endian bytes.

returnsu8[] | null

The 65-byte public key, or null for a key that is not one.

p256Sign

The ECDSA signature (FIPS 186-4 §6.4) of digest under priv, as r || s, 64 bytes, with the deterministic nonce of RFC 6979 §3.2 over HMAC-SHA-256. digest is the message's hash, taken as bits2int does: its leftmost 256 bits. The same key and digest always give the same signature, and s is not normalised to the lower half. Answers null for a private key p256PublicKey would refuse.

const p256Sign: (
  priv: Secret<u8[]>,
  digest: u8[],
) => u8[] | null
privSecret<u8[]>required

The private key, 32 big-endian bytes.

digestu8[]required

The message's hash; only its leftmost 256 bits count.

returnsu8[] | null

The 64-byte signature r || s, or null for a refused key.

p256SignSha256

p256Sign of the SHA-256 of msg: ECDSA with SHA-256 over the whole message.

const p256SignSha256: (
  priv: Secret<u8[]>,
  msg: u8[],
) => u8[] | null
privSecret<u8[]>required

The private key, 32 big-endian bytes.

msgu8[]required

The whole message, hashed here.

returnsu8[] | null

The 64-byte signature r || s, or null for a refused key.

p256SignSha256Into

p256SignSha256 of msg[off .. off + len) in scratch, written as r || s at out[at .. at + 64): the same 64 bytes p256SignSha256 answers for the same key and message. Answers false, writing nothing, for a private key p256PublicKey would refuse. A message or signature window outside its array panics before anything is read.

It runs inside an arena block of its own and stores nothing, so a signature leaves the arena where it was; every secret the scratch held — RFC 6979's K and V, the nonce's inverse, its point and the point scratch — is wiped before it returns, as are the fresh arrays the key's own steps worked in.

const p256SignSha256Into: (
  sc: P256SignScratch,
  priv: Secret<u8[]>,
  msg: u8[],
  off: i32,
  len: i32,
  out: u8[],
  at: i32,
) => boolean
scP256SignScratchrequired

The scratch to sign in, one per signer.

privSecret<u8[]>required

The private key, 32 big-endian bytes.

msgu8[]required

The array holding the message.

offi32required

Where the message starts in msg.

leni32required

The message's length in bytes.

outu8[]required

The array the signature is written into.

ati32required

Where the 64 bytes start in out.

returnsboolean

true once the signature is written, false for a refused key.

p256Verify

Whether sig (r || s) is a valid ECDSA signature of digest under the public key pub (FIPS 186-4 §6.4.2): r and s in [1, n), and the x-coordinate of u1 * G + u2 * Q equal to r mod n, with w = s^-1, u1 = z w and u2 = r w. A key or signature of the wrong length, a key that is not a point on the curve, and a sum that is the identity all answer false. Every value here is public, so the answer may be reached by branches, and u1 * G + u2 * Q is one variable-time Shamir pass over width-5 NAFs (p256DoubleMultPublic), not two constant-time multiplications: its time follows u1 and u2, which the signature and digest already disclose.

ECDSA is malleable, and so is this: when (r, s) verifies, (r, n - s) verifies too, as FIPS 186-4 and SEC 1 have it. Nothing here asks for the lower s, so a protocol that needs one signature per message and key (a signature used as an identifier, say) has to refuse the upper half itself.

const p256Verify: (
  pub: u8[],
  digest: u8[],
  sig: u8[],
) => boolean
pubu8[]required

The signer's 65-byte uncompressed public key.

digestu8[]required

The message's hash; only its leftmost 256 bits count.

sigu8[]required

The 64-byte signature r || s.

returnsboolean

true when the signature is valid, false for anything else.

p256VerifySha256

p256Verify of the SHA-256 of msg.

const p256VerifySha256: (
  pub: u8[],
  msg: u8[],
  sig: u8[],
) => boolean
pubu8[]required

The signer's 65-byte uncompressed public key.

msgu8[]required

The whole message, hashed here.

sigu8[]required

The 64-byte signature r || s.

returnsboolean

true when the signature is valid, false for anything else.

Classes

P256SignScratch

Everything p256SignSha256Into signs in, made once and reused: RFC 6979's K and V, the hashing's work arrays and round constants, the nonce's multiple of G with the comb table and point scratch, and the scalars of the signature. One per signer, not per connection: signing is synchronous, and every secret it held is wiped before p256SignSha256Into returns.

const scratch = new P256SignScratch();            // once, outside the loop
const sig: u8[] = new Array<u8>(P256_SIGNATURE_SIZE);
const ok: boolean = p256SignSha256Into(scratch, priv, msg, 0, msg.length, sig, 0);
class P256SignScratch
Member
new P256SignScratch() Makes the arrays every signature reuses, the round constants and the base point's comb table included, so the base-point multiplication works in them; what p256SignSha256Into still allocates per call is released when its arena block ends, so nothing is kept.

Constants

65

P256_POINT_SIZE: i32

The length in bytes of a public key: 0x04, then X and Y big-endian (SEC 1 §2.3.3).

32

P256_SCALAR_SIZE: i32

The length in bytes of a private key: one scalar, big-endian.

64

P256_SIGNATURE_SIZE: i32

The length in bytes of a signature: r then s, 32 big-endian bytes each.