P256

Implementation of secp256r1 verification and recovery functions. The secp256r1 curve (also known as P256) is a NIST standard curve with wide support in modern devices and cryptographic standards. Some notable examples include Apple's Secure Enclave and Android's Keystore as well as authentication protocols like FIDO2. Based on the original https://github.com/itsobvioustech/aa-passkeys-wallet/blob/d3d423f28a4d8dfcb203c7fa0c47f42592a7378e/src/Secp256r1.sol[implementation of itsobvioustech] (GNU General Public License v3.0). Heavily inspired in https://github.com/maxrobot/elliptic-solidity/blob/c4bb1b6e8ae89534d8db3a6b3a6b52219100520f/contracts/Secp256r1.sol[maxrobot] and https://github.com/tdrerup/elliptic-curve-solidity/blob/59a9c25957d4d190eff53b6610731d81a077a15e/contracts/curves/EllipticCurve.sol[tdrerup] implementations. Available since v5.1.

State Variables

GX

Generator (x component)

uint256 internal constant GX = 0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296;

GY

Generator (y component)

uint256 internal constant GY = 0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5;

P

P (size of the field)

uint256 internal constant P = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF;

N

N (order of G)

uint256 internal constant N = 0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551;

A

A parameter of the weierstrass equation

uint256 internal constant A = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC;

B

B parameter of the weierstrass equation

uint256 internal constant B = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B;

P1DIV4

(P + 1) / 4. Useful to compute sqrt

uint256 private constant P1DIV4 = 0x3fffffffc0000000400000000000000000000000400000000000000000000000;

HALF_N

N/2 for excluding higher order s values

uint256 private constant HALF_N = 0x7fffffff800000007fffffffffffffffde737d56d38bcf4279dce5617e3192a8;

Functions

verify

Verifies a secp256r1 signature using the RIP-7212 precompile and falls back to the Solidity implementation if the precompile is not available. This version should work on all chains, but requires the deployment of more bytecode.

function verify(bytes32 h, bytes32 r, bytes32 s, bytes32 qx, bytes32 qy) internal view returns (bool);

Parameters

verifyNative

Same as verify, but it will revert if the required precompile is not available. Make sure any logic (code or precompile) deployed at that address is the expected one, otherwise the returned value may be misinterpreted as a positive boolean.

function verifyNative(bytes32 h, bytes32 r, bytes32 s, bytes32 qx, bytes32 qy) internal view returns (bool);

_tryVerifyNative

Same as verify, but it will return false if the required precompile is not available.

function _tryVerifyNative(bytes32 h, bytes32 r, bytes32 s, bytes32 qx, bytes32 qy)
    private
    view
    returns (bool valid, bool supported);

_rip7212

Low level helper for _tryVerifyNative. Calls the precompile and checks if there is a return value.

function _rip7212(bytes32 h, bytes32 r, bytes32 s, bytes32 qx, bytes32 qy) private view returns (bool isValid);

verifySolidity

Same as verify, but only the Solidity implementation is used.

function verifySolidity(bytes32 h, bytes32 r, bytes32 s, bytes32 qx, bytes32 qy) internal view returns (bool);

recovery

Public key recovery

function recovery(bytes32 h, uint8 v, bytes32 r, bytes32 s) internal view returns (bytes32 x, bytes32 y);

Parameters

isValidPublicKey

Checks if (x, y) are valid coordinates of a point on the curve. In particular this function checks that x < P and y < P.

function isValidPublicKey(bytes32 x, bytes32 y) internal pure returns (bool result);

_isProperSignature

Checks if (r, s) is a proper signature. In particular, this checks that s is in the "lower-range", making the signature non-malleable.

function _isProperSignature(bytes32 r, bytes32 s) private pure returns (bool);

_affineFromJacobian

Reduce from jacobian to affine coordinates

function _affineFromJacobian(uint256 jx, uint256 jy, uint256 jz) private view returns (uint256 ax, uint256 ay);

Parameters

Returns

_jAdd

*Point addition on the jacobian coordinates Reference: https://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#addition-add-1998-cmo-2 Note that:

• addition-add-1998-cmo-2 doesn't support identical input points. This version is modified to use the h and r values computed by addition-add-1998-cmo-2 to detect identical inputs, and fallback to doubling-dbl-1998-cmo-2 if needed.
• if one of the points is at infinity (i.e. z=0), the result is undefined.*

function _jAdd(JPoint memory p1, uint256 x2, uint256 y2, uint256 z2)
    private
    pure
    returns (uint256 rx, uint256 ry, uint256 rz);

_jDouble

Point doubling on the jacobian coordinates Reference: https://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-1998-cmo-2

function _jDouble(uint256 x, uint256 y, uint256 z) private pure returns (uint256 rx, uint256 ry, uint256 rz);

_jMultShamir

Compute G·u1 + P·u2 using the precomputed points for G and P (see _preComputeJacobianPoints). Uses Strauss Shamir trick for EC multiplication https://stackoverflow.com/questions/50993471/ec-scalar-multiplication-with-strauss-shamir-method We optimize this for 2 bits at a time rather than a single bit. The individual points for a single pass are precomputed. Overall this reduces the number of additions while keeping the same number of doublings

function _jMultShamir(JPoint[16] memory points, uint256 u1, uint256 u2) private view returns (uint256 rx, uint256 ry);

_preComputeJacobianPoints

Precompute a matrice of useful jacobian points associated with a given P. This can be seen as a 4x4 matrix that contains combination of P and G (generator) up to 3 times each. See the table below: ┌────┬─────────────────────┐ │ i │ 0 1 2 3 │ ├────┼─────────────────────┤ │ 0 │ 0 p 2p 3p │ │ 4 │ g g+p g+2p g+3p │ │ 8 │ 2g 2g+p 2g+2p 2g+3p │ │ 12 │ 3g 3g+p 3g+2p 3g+3p │ └────┴─────────────────────┘ Note that _jAdd (and thus _jAddPoint) does not handle the case where one of the inputs is a point at infinity (z = 0). However, we know that since N ≡ 1 mod 2 and N ≡ 1 mod 3, there is no point P such that 2P = 0 or 3P = 0. This guarantees that g, 2g, 3g, p, 2p, 3p are all non-zero, and that all _jAddPoint calls have valid inputs.

function _preComputeJacobianPoints(uint256 px, uint256 py) private pure returns (JPoint[16] memory points);

_jAddPoint

function _jAddPoint(JPoint memory p1, JPoint memory p2) private pure returns (JPoint memory);

_jDoublePoint

function _jDoublePoint(JPoint memory p) private pure returns (JPoint memory);

Structs

JPoint

struct JPoint {
    uint256 x;
    uint256 y;
    uint256 z;
}