Expand description
NIST P-256 curve implementation.
This module implements generic group operations on the NIST P-256
elliptic curve, a short Weierstraß curve with equation y^2 = x^3 - 3*x + b for a given constant b. This curve is standardized in
FIPS 186-4 as well as in other standards such as SEC 2 or ANSI
X9:62. It is also known under the names “secp256r1” and “prime256v1”.
The curve has prime order. “Scalars” are integers modulo that prime
order, and are implemented by the Scalar structure. This structure
supports the usual arithmetic operators (+, -, *, /, and the
compound assignments +=, -=, *= and /=).
A point on the curve is represented by the Point structure. The
additive arithmetic operators can be applied on Point instances
(+, -, +=, -=); multiplications by an integer (u64 type) or
by a scalar (Scalar type) are also supported with the * and *=
operators. Point doublings can be performed with the double()
function (which is somewhat faster than general addition), and
additional optimizations are obtained in the context of multiple
successive doublings by calling the xdouble() function. All these
operations are implemented with fully constant-time code and are
complete, i.e. they work with all points, even when adding a point
with itself or when operations involve the curve point-at-infinity
(the neutral element for the curve as a group).
Scalars can be encoded over 32 bytes, using unsigned
little-endian convention) and decoded back. Encoding is always
canonical, and decoding always verifies that the value is indeed in
the canonical range. Take care that many standards related to P-256
tend to use big-endian for encoding scalars (and often use a
variable-length encoding, e.g. an ASN.1 INTEGER).
Points can be encoded in compressed (33 bytes) or uncompressed (65
bytes) formats. These formats internally use big-endian. The nominal
encoding of the point-at-infinity is a single byte of value 0x00; the
encode_compressed() and encode_uncompressed() functions cannot
produce that specific encoding (since they produce fixed-length
outputs), and instead yield a sequence of 33 or 65 zeros in that
case. Point decoding accepts compressed and uncompressed formats, and
also the one-byte encoding of the point-at-infinity, but they do not
accept a sequence of 33 or 65 zeros as a valid input. Thus, point
decoding is stricly standards-conforming. All decoding operations
enforce canonicality of encoding, and verify that the point is indeed
on the curve.
The PrivateKey structure represents a private key for the ECDSA
signature algorithm; it is basically a wrapper around a private
scalar value. The PrivateKey::encode() and PrivateKey::decode()
functions encode a private key to exactly 32 bytes, and decode it
back, this time using unsigned big-endian, as per SEC 1 encoding
rules (which represents private keys with the ASN.1 OCTET STRING
type). The PrivateKey::from_seed() allows generating a private key
from a source seed, which is presumed to have been obtained
from a cryptographically secure random source.
The PublicKey structure represents a public key for the ECDSA
signature algorithm; it is a wrapper around a Point. It has its own
decode(), encode_compressed() and encode_uncompressed() which
only wrap around the corresponding Point functions, except that
decode() explicitly rejects the point-at-infinity: an ECDSA public
key is never the identity point.
ECDSA signatures are generated with PrivateKey::sign_hash(), and
verified with PublicKey::verify_hash(). The signature process is
deterministic, using the SHA-256 function, following the description
in RFC 6979. The caller is provides the pre-hashed message
(normally, this hashing uses SHA-256, but the functions accept hash
values of any length). In this implementation, the ECDSA signatures
follow the non-ASN.1 format: the two r and s halves of the
signature are encoded in unsigned big-endian format and concatenated,
in that order. When generating a signature, exactly 32 bytes are used
for each of r and s, so the signature has length 64 bytes
exactly. When verifying a signature, any input size is accepted
provided that it is even (so that it is unambiguous where r stops
and s starts), and that the two r and s values are still in the
proper range (i.e. lower than the curve order).
Truncated Signatures
The PublicKey::verify_trunc_hash() function supports truncated
signatures: a 64-byte signature is provided, but the last few bits
are considered to have been reused for encoding other data, and thus
are ignored. The truncation requires that the original signature is
first processed through PrivateKey::prepare_truncate(); this
utility function does not use the private key itself, but it modifies
the encoding format of the s part of the signature so that
truncation removes the high-order bits of the value, instead of the
low-order bits.
The verification function then tries to recompute the complete, original, untruncated signature. This process is safe since neither truncation nor reconstruction involve usage of the private key, and the original signature is obtained as an outcome of the process. Up to 32 bits (i.e. four whole bytes) can be rebuilt by this implementation, which corresponds to shrinking the signature encoding size from 64 down to 60 bytes.
Signature reconstruction cost increases with the number of ignored bits (asymptotically, cost doubles for every 2 removed bits, so 32-bit truncation sboud be about 16 times more expensive than 24-bit truncation); when 32 bits are ignored, the verification cost is about 300 to 450 times the cost of verifying an untruncated signature.
Truncated signature verification on curve P-256 requires dynamic
memory allocation; it is not available if this library is compiled
without the std or alloc feature (default compilation uses std
and thus std::vec::Vec; without std but with alloc,
alloc::vec::Vec is used).
Structs
- A point on the short Weierstraß curve P-256.
- A P-256 private key simply wraps around a scalar.
- A P-256 public key simply wraps around a curve point.
Type Definitions
- Integers modulo the curve order n (a 256-bit prime).