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
}
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).
p256PublicKey
The public key of priv: priv * G in the 65-byte uncompressed SEC 1 encoding.
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.
p256SignSha256
p256Sign of the SHA-256 of msg: ECDSA with SHA-256 over the whole message.
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.
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.
p256VerifySha256
p256Verify of the SHA-256 of msg.
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.
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[]>requiredThis side's private key, 32 big-endian bytes.
peerPointu8[]requiredThe 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[]>requiredThe private key, 32 big-endian bytes.
returnsu8[] | nullThe 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[]>requiredThe private key, 32 big-endian bytes.
digestu8[]requiredThe message's hash; only its leftmost 256 bits count.
returnsu8[] | nullThe 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[]>requiredThe private key, 32 big-endian bytes.
msgu8[]requiredThe whole message, hashed here.
returnsu8[] | nullThe 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
scP256SignScratchrequiredThe scratch to sign in, one per signer.
privSecret<u8[]>requiredThe private key, 32 big-endian bytes.
msgu8[]requiredThe array holding the message.
offi32requiredWhere the message starts in msg.
leni32requiredThe message's length in bytes.
outu8[]requiredThe array the signature is written into.
ati32requiredWhere the 64 bytes start in out.
returnsbooleantrue 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[]requiredThe signer's 65-byte uncompressed public key.
digestu8[]requiredThe message's hash; only its leftmost 256 bits count.
sigu8[]requiredThe 64-byte signature r || s.
returnsbooleantrue 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[]requiredThe signer's 65-byte uncompressed public key.
msgu8[]requiredThe whole message, hashed here.
sigu8[]requiredThe 64-byte signature r || s.
returnsbooleantrue 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.

