// Copyright 2015 The Go Authors. All rights reserved.// Use of this source code is governed by a BSD-style// license that can be found in the LICENSE file.// This file contains the Go wrapper for the constant-time, 64-bit assembly// implementation of P256. The optimizations performed here are described in// detail in:// S.Gueron and V.Krasnov, "Fast prime field elliptic-curve cryptography with// 256-bit primes"// https://link.springer.com/article/10.1007%2Fs13389-014-0090-x// https://eprint.iacr.org/2013/816.pdf//go:build (amd64 || arm64 || ppc64le || s390x) && !puregopackage nistecimport (_)// p256Element is a P-256 base field element in [0, P-1] in the Montgomery// domain (with R 2²⁵⁶) as four limbs in little-endian order value.type p256Element [4]uint64// p256One is one in the Montgomery domain.var p256One = p256Element{0x0000000000000001, 0xffffffff00000000,0xffffffffffffffff, 0x00000000fffffffe}var p256Zero = p256Element{}// p256P is 2²⁵⁶ - 2²²⁴ + 2¹⁹² + 2⁹⁶ - 1 in the Montgomery domain.var p256P = p256Element{0xffffffffffffffff, 0x00000000ffffffff,0x0000000000000000, 0xffffffff00000001}// P256Point is a P-256 point. The zero value should not be assumed to be valid// (although it is in this implementation).typeP256Pointstruct {// (X:Y:Z) are Jacobian coordinates where x = X/Z² and y = Y/Z³. The point // at infinity can be represented by any set of coordinates with Z = 0. x, y, z p256Element}// NewP256Point returns a new P256Point representing the point at infinity.func () *P256Point {return &P256Point{x: p256One, y: p256One, z: p256Zero, }}// SetGenerator sets p to the canonical generator and returns p.func ( *P256Point) () *P256Point { .x = p256Element{0x79e730d418a9143c, 0x75ba95fc5fedb601,0x79fb732b77622510, 0x18905f76a53755c6} .y = p256Element{0xddf25357ce95560a, 0x8b4ab8e4ba19e45c,0xd2e88688dd21f325, 0x8571ff1825885d85} .z = p256Onereturn}// Set sets p = q and returns p.func ( *P256Point) ( *P256Point) *P256Point { .x, .y, .z = .x, .y, .zreturn}const p256ElementLength = 32const p256UncompressedLength = 1 + 2*p256ElementLengthconst p256CompressedLength = 1 + p256ElementLength// SetBytes sets p to the compressed, uncompressed, or infinity value encoded in// b, as specified in SEC 1, Version 2.0, Section 2.3.4. If the point is not on// the curve, it returns nil and an error, and the receiver is unchanged.// Otherwise, it returns p.func ( *P256Point) ( []byte) (*P256Point, error) {// p256Mul operates in the Montgomery domain with R = 2²⁵⁶ mod p. Thus rr // here is R in the Montgomery domain, or R×R mod p. See comment in // P256OrdInverse about how this is used. := p256Element{0x0000000000000003, 0xfffffffbffffffff,0xfffffffffffffffe, 0x00000004fffffffd}switch {// Point at infinity.caselen() == 1 && [0] == 0:return .Set(NewP256Point()), nil// Uncompressed form.caselen() == p256UncompressedLength && [0] == 4:varP256Pointp256BigToLittle(&.x, (*[32]byte)([1:33]))p256BigToLittle(&.y, (*[32]byte)([33:65]))ifp256LessThanP(&.x) == 0 || p256LessThanP(&.y) == 0 {returnnil, errors.New("invalid P256 element encoding") }p256Mul(&.x, &.x, &)p256Mul(&.y, &.y, &)if := p256CheckOnCurve(&.x, &.y); != nil {returnnil, } .z = p256Onereturn .Set(&), nil// Compressed form.caselen() == p256CompressedLength && ([0] == 2 || [0] == 3):varP256Pointp256BigToLittle(&.x, (*[32]byte)([1:33]))ifp256LessThanP(&.x) == 0 {returnnil, errors.New("invalid P256 element encoding") }p256Mul(&.x, &.x, &)// y² = x³ - 3x + bp256Polynomial(&.y, &.x)if !p256Sqrt(&.y, &.y) {returnnil, errors.New("invalid P256 compressed point encoding") }// Select the positive or negative root, as indicated by the least // significant bit, based on the encoding type byte. := new(p256Element)p256FromMont(, &.y) := int([0]&1) ^ int([0]&1)p256NegCond(&.y, ) .z = p256Onereturn .Set(&), nildefault:returnnil, errors.New("invalid P256 point encoding") }}// p256Polynomial sets y2 to x³ - 3x + b, and returns y2.func p256Polynomial(, *p256Element) *p256Element { := new(p256Element)p256Sqr(, , 1)p256Mul(, , ) := new(p256Element)p256Add(, , )p256Add(, , )p256NegCond(, 1) := &p256Element{0xd89cdf6229c4bddf, 0xacf005cd78843090,0xe5a220abf7212ed6, 0xdc30061d04874834}p256Add(, , )p256Add(, , ) * = *return}func p256CheckOnCurve(, *p256Element) error {// y² = x³ - 3x + b := p256Polynomial(new(p256Element), ) := new(p256Element)p256Sqr(, , 1)ifp256Equal(, ) != 1 {returnerrors.New("P256 point not on curve") }returnnil}// p256LessThanP returns 1 if x < p, and 0 otherwise. Note that a p256Element is// not allowed to be equal to or greater than p, so if this function returns 0// then x is invalid.func p256LessThanP( *p256Element) int {varuint64 _, = bits.Sub64([0], p256P[0], ) _, = bits.Sub64([1], p256P[1], ) _, = bits.Sub64([2], p256P[2], ) _, = bits.Sub64([3], p256P[3], )returnint()}// p256Add sets res = x + y.func p256Add(, , *p256Element) {var , uint64 := make([]uint64, 4) [0], = bits.Add64([0], [0], 0) [1], = bits.Add64([1], [1], ) [2], = bits.Add64([2], [2], ) [3], = bits.Add64([3], [3], ) := make([]uint64, 4) [0], = bits.Sub64([0], p256P[0], 0) [1], = bits.Sub64([1], p256P[1], ) [2], = bits.Sub64([2], p256P[2], ) [3], = bits.Sub64([3], p256P[3], )// Three options: // - a+b < p // then c is 0, b is 1, and t1 is correct // - p <= a+b < 2^256 // then c is 0, b is 0, and t2 is correct // - 2^256 <= a+b // then c is 1, b is 1, and t2 is correct := ( ^ ) - 1 [0] = ([0] & ^) | ([0] & ) [1] = ([1] & ^) | ([1] & ) [2] = ([2] & ^) | ([2] & ) [3] = ([3] & ^) | ([3] & )}// p256Sqrt sets e to a square root of x. If x is not a square, p256Sqrt returns// false and e is unchanged. e and x can overlap.func p256Sqrt(, *p256Element) ( bool) { , := new(p256Element), new(p256Element)// Since p = 3 mod 4, exponentiation by (p + 1) / 4 yields a square root candidate. // // The sequence of 7 multiplications and 253 squarings is derived from the // following addition chain generated with github.com/mmcloughlin/addchain v0.4.0. // // _10 = 2*1 // _11 = 1 + _10 // _1100 = _11 << 2 // _1111 = _11 + _1100 // _11110000 = _1111 << 4 // _11111111 = _1111 + _11110000 // x16 = _11111111 << 8 + _11111111 // x32 = x16 << 16 + x16 // return ((x32 << 32 + 1) << 96 + 1) << 94 //p256Sqr(, , 1)p256Mul(, , )p256Sqr(, , 2)p256Mul(, , )p256Sqr(, , 4)p256Mul(, , )p256Sqr(, , 8)p256Mul(, , )p256Sqr(, , 16)p256Mul(, , )p256Sqr(, , 32)p256Mul(, , )p256Sqr(, , 96)p256Mul(, , )p256Sqr(, , 94)p256Sqr(, , 1)ifp256Equal(, ) != 1 {returnfalse } * = *returntrue}// The following assembly functions are implemented in p256_asm_*.s// Montgomery multiplication. Sets res = in1 * in2 * R⁻¹ mod p.////go:noescapefunc p256Mul(, , *p256Element)// Montgomery square, repeated n times (n >= 1).////go:noescapefunc p256Sqr(, *p256Element, int)// Montgomery multiplication by R⁻¹, or 1 outside the domain.// Sets res = in * R⁻¹, bringing res out of the Montgomery domain.////go:noescapefunc p256FromMont(, *p256Element)// If cond is not 0, sets val = -val mod p.////go:noescapefunc p256NegCond( *p256Element, int)// If cond is 0, sets res = b, otherwise sets res = a.////go:noescapefunc p256MovCond(, , *P256Point, int)//go:noescapefunc p256BigToLittle( *p256Element, *[32]byte)//go:noescapefunc p256LittleToBig( *[32]byte, *p256Element)//go:noescapefunc p256OrdBigToLittle( *p256OrdElement, *[32]byte)//go:noescapefunc p256OrdLittleToBig( *[32]byte, *p256OrdElement)// p256Table is a table of the first 16 multiples of a point. Points are stored// at an index offset of -1 so [8]P is at index 7, P is at 0, and [16]P is at 15.// [0]P is the point at infinity and it's not stored.type p256Table [16]P256Point// p256Select sets res to the point at index idx in the table.// idx must be in [0, 15]. It executes in constant time.////go:noescapefunc p256Select( *P256Point, *p256Table, int)// p256AffinePoint is a point in affine coordinates (x, y). x and y are still// Montgomery domain elements. The point can't be the point at infinity.type p256AffinePoint struct { x, y p256Element}// p256AffineTable is a table of the first 32 multiples of a point. Points are// stored at an index offset of -1 like in p256Table, and [0]P is not stored.type p256AffineTable [32]p256AffinePoint// p256Precomputed is a series of precomputed multiples of G, the canonical// generator. The first p256AffineTable contains multiples of G. The second one// multiples of [2⁶]G, the third one of [2¹²]G, and so on, where each successive// table is the previous table doubled six times. Six is the width of the// sliding window used in p256ScalarMult, and having each table already// pre-doubled lets us avoid the doublings between windows entirely. This table// MUST NOT be modified, as it aliases into p256PrecomputedEmbed below.var p256Precomputed *[43]p256AffineTable//go:embed p256_asm_table.binvar p256PrecomputedEmbed stringfunc init() { := (*unsafe.Pointer)(unsafe.Pointer(&p256PrecomputedEmbed))ifruntime.GOARCH == "s390x" {var [43 * 32 * 2 * 4]uint64for , := range (*[43 * 32 * 2 * 4][8]byte)(*) { [] = byteorder.LeUint64([:]) } := unsafe.Pointer(&) = & }p256Precomputed = (*[43]p256AffineTable)(*)}// p256SelectAffine sets res to the point at index idx in the table.// idx must be in [0, 31]. It executes in constant time.////go:noescapefunc p256SelectAffine( *p256AffinePoint, *p256AffineTable, int)// Point addition with an affine point and constant time conditions.// If zero is 0, sets res = in2. If sel is 0, sets res = in1.// If sign is not 0, sets res = in1 + -in2. Otherwise, sets res = in1 + in2////go:noescapefunc p256PointAddAffineAsm(, *P256Point, *p256AffinePoint, , , int)// Point addition. Sets res = in1 + in2. Returns one if the two input points// were equal and zero otherwise. If in1 or in2 are the point at infinity, res// and the return value are undefined.////go:noescapefunc p256PointAddAsm(, , *P256Point) int// Point doubling. Sets res = in + in. in can be the point at infinity.////go:noescapefunc p256PointDoubleAsm(, *P256Point)// p256OrdElement is a P-256 scalar field element in [0, ord(G)-1] in the// Montgomery domain (with R 2²⁵⁶) as four uint64 limbs in little-endian order.type p256OrdElement [4]uint64// p256OrdReduce ensures s is in the range [0, ord(G)-1].func p256OrdReduce( *p256OrdElement) {// Since 2 * ord(G) > 2²⁵⁶, we can just conditionally subtract ord(G), // keeping the result if it doesn't underflow. , := bits.Sub64([0], 0xf3b9cac2fc632551, 0) , := bits.Sub64([1], 0xbce6faada7179e84, ) , := bits.Sub64([2], 0xffffffffffffffff, ) , := bits.Sub64([3], 0xffffffff00000000, ) := - 1// zero if subtraction underflowed [0] ^= ( ^ [0]) & [1] ^= ( ^ [1]) & [2] ^= ( ^ [2]) & [3] ^= ( ^ [3]) & }// Add sets q = p1 + p2, and returns q. The points may overlap.func ( *P256Point) (, *P256Point) *P256Point {var , P256Point := .isInfinity() := .isInfinity() := p256PointAddAsm(&, , )p256PointDoubleAsm(&, )p256MovCond(&, &, &, )p256MovCond(&, , &, )p256MovCond(&, , &, )return .Set(&)}// Double sets q = p + p, and returns q. The points may overlap.func ( *P256Point) ( *P256Point) *P256Point {varP256Pointp256PointDoubleAsm(&, )return .Set(&)}// ScalarBaseMult sets r = scalar * generator, where scalar is a 32-byte big// endian value, and returns r. If scalar is not 32 bytes long, ScalarBaseMult// returns an error and the receiver is unchanged.func ( *P256Point) ( []byte) (*P256Point, error) {iflen() != 32 {returnnil, errors.New("invalid scalar length") } := new(p256OrdElement)p256OrdBigToLittle(, (*[32]byte)())p256OrdReduce() .p256BaseMult()return , nil}// ScalarMult sets r = scalar * q, where scalar is a 32-byte big endian value,// and returns r. If scalar is not 32 bytes long, ScalarBaseMult returns an// error and the receiver is unchanged.func ( *P256Point) ( *P256Point, []byte) (*P256Point, error) {iflen() != 32 {returnnil, errors.New("invalid scalar length") } := new(p256OrdElement)p256OrdBigToLittle(, (*[32]byte)())p256OrdReduce() .Set().p256ScalarMult()return , nil}// uint64IsZero returns 1 if x is zero and zero otherwise.func uint64IsZero( uint64) int { = ^ &= >> 32 &= >> 16 &= >> 8 &= >> 4 &= >> 2 &= >> 1returnint( & 1)}// p256Equal returns 1 if a and b are equal and 0 otherwise.func p256Equal(, *p256Element) int {varuint64for := range { |= [] ^ [] }returnuint64IsZero()}// isInfinity returns 1 if p is the point at infinity and 0 otherwise.func ( *P256Point) () int {returnp256Equal(&.z, &p256Zero)}// Bytes returns the uncompressed or infinity encoding of p, as specified in// SEC 1, Version 2.0, Section 2.3.3. Note that the encoding of the point at// infinity is shorter than all other encodings.func ( *P256Point) () []byte {// This function is outlined to make the allocations inline in the caller // rather than happen on the heap.var [p256UncompressedLength]bytereturn .bytes(&)}func ( *P256Point) ( *[p256UncompressedLength]byte) []byte {// The proper representation of the point at infinity is a single zero byte.if .isInfinity() == 1 {returnappend([:0], 0) } , := new(p256Element), new(p256Element) .affineFromMont(, ) [0] = 4// Uncompressed form.p256LittleToBig((*[32]byte)([1:33]), )p256LittleToBig((*[32]byte)([33:65]), )return [:]}// affineFromMont sets (x, y) to the affine coordinates of p, converted out of the// Montgomery domain.func ( *P256Point) (, *p256Element) {p256Inverse(, &.z)p256Sqr(, , 1)p256Mul(, , )p256Mul(, &.x, )p256Mul(, &.y, )p256FromMont(, )p256FromMont(, )}// BytesX returns the encoding of the x-coordinate of p, as specified in SEC 1,// Version 2.0, Section 2.3.5, or an error if p is the point at infinity.func ( *P256Point) () ([]byte, error) {// This function is outlined to make the allocations inline in the caller // rather than happen on the heap.var [p256ElementLength]bytereturn .bytesX(&)}func ( *P256Point) ( *[p256ElementLength]byte) ([]byte, error) {if .isInfinity() == 1 {returnnil, errors.New("P256 point is the point at infinity") } := new(p256Element)p256Inverse(, &.z)p256Sqr(, , 1)p256Mul(, &.x, )p256FromMont(, )p256LittleToBig((*[32]byte)([:]), )return [:], nil}// BytesCompressed returns the compressed or infinity encoding of p, as// specified in SEC 1, Version 2.0, Section 2.3.3. Note that the encoding of the// point at infinity is shorter than all other encodings.func ( *P256Point) () []byte {// This function is outlined to make the allocations inline in the caller // rather than happen on the heap.var [p256CompressedLength]bytereturn .bytesCompressed(&)}func ( *P256Point) ( *[p256CompressedLength]byte) []byte {if .isInfinity() == 1 {returnappend([:0], 0) } , := new(p256Element), new(p256Element) .affineFromMont(, ) [0] = 2 | byte([0]&1)p256LittleToBig((*[32]byte)([1:33]), )return [:]}// Select sets q to p1 if cond == 1, and to p2 if cond == 0.func ( *P256Point) (, *P256Point, int) *P256Point {p256MovCond(, , , )return}// p256Inverse sets out to in⁻¹ mod p. If in is zero, out will be zero.func p256Inverse(, *p256Element) {// Inversion is calculated through exponentiation by p - 2, per Fermat's // little theorem. // // The sequence of 12 multiplications and 255 squarings is derived from the // following addition chain generated with github.com/mmcloughlin/addchain // v0.4.0. // // _10 = 2*1 // _11 = 1 + _10 // _110 = 2*_11 // _111 = 1 + _110 // _111000 = _111 << 3 // _111111 = _111 + _111000 // x12 = _111111 << 6 + _111111 // x15 = x12 << 3 + _111 // x16 = 2*x15 + 1 // x32 = x16 << 16 + x16 // i53 = x32 << 15 // x47 = x15 + i53 // i263 = ((i53 << 17 + 1) << 143 + x47) << 47 // return (x47 + i263) << 2 + 1 //var = new(p256Element)var = new(p256Element)var = new(p256Element)p256Sqr(, , 1)p256Mul(, , )p256Sqr(, , 1)p256Mul(, , )p256Sqr(, , 3)p256Mul(, , )p256Sqr(, , 6)p256Mul(, , )p256Sqr(, , 3)p256Mul(, , )p256Sqr(, , 1)p256Mul(, , )p256Sqr(, , 16)p256Mul(, , )p256Sqr(, , 15)p256Mul(, , )p256Sqr(, , 17)p256Mul(, , )p256Sqr(, , 143)p256Mul(, , )p256Sqr(, , 47)p256Mul(, , )p256Sqr(, , 2)p256Mul(, , )}func boothW5( uint) (int, int) {varuint = ^(( >> 5) - 1)varuint = (1 << 6) - - 1 = ( & ) | ( & (^)) = ( >> 1) + ( & 1)returnint(), int( & 1)}func boothW6( uint) (int, int) {varuint = ^(( >> 6) - 1)varuint = (1 << 7) - - 1 = ( & ) | ( & (^)) = ( >> 1) + ( & 1)returnint(), int( & 1)}func ( *P256Point) ( *p256OrdElement) {varp256AffinePoint := ([0] << 1) & 0x7f , := boothW6(uint())p256SelectAffine(&, &p256Precomputed[0], ) .x, .y, .z = .x, .y, p256Onep256NegCond(&.y, ) := uint(5) := for := 1; < 43; ++ {if < 192 { = (([/64] >> ( % 64)) + ([/64+1] << (64 - ( % 64)))) & 0x7f } else { = ([/64] >> ( % 64)) & 0x7f } += 6 , = boothW6(uint())p256SelectAffine(&, &p256Precomputed[], )p256PointAddAffineAsm(, , &, , , ) |= }// If the whole scalar was zero, set to the point at infinity.p256MovCond(, , NewP256Point(), )}func ( *P256Point) ( *p256OrdElement) {// precomp is a table of precomputed points that stores powers of p // from p^1 to p^16.varp256Tablevar , , , P256Point// Prepare the table [0] = * // 1p256PointDoubleAsm(&, )p256PointDoubleAsm(&, &)p256PointDoubleAsm(&, &)p256PointDoubleAsm(&, &) [1] = // 2 [3] = // 4 [7] = // 8 [15] = // 16p256PointAddAsm(&, &, )p256PointAddAsm(&, &, )p256PointAddAsm(&, &, ) [2] = // 3 [4] = // 5 [8] = // 9p256PointDoubleAsm(&, &)p256PointDoubleAsm(&, &) [5] = // 6 [9] = // 10p256PointAddAsm(&, &, )p256PointAddAsm(&, &, ) [6] = // 7 [10] = // 11p256PointDoubleAsm(&, &)p256PointDoubleAsm(&, &) [11] = // 12 [13] = // 14p256PointAddAsm(&, &, )p256PointAddAsm(&, &, ) [12] = // 13 [14] = // 15// Start scanning the window from top bit := uint(254)var , int := ([/64] >> ( % 64)) & 0x3f , _ = boothW5(uint())p256Select(, &, ) := for > 4 { -= 5p256PointDoubleAsm(, )p256PointDoubleAsm(, )p256PointDoubleAsm(, )p256PointDoubleAsm(, )p256PointDoubleAsm(, )if < 192 { = (([/64] >> ( % 64)) + ([/64+1] << (64 - ( % 64)))) & 0x3f } else { = ([/64] >> ( % 64)) & 0x3f } , = boothW5(uint())p256Select(&, &, )p256NegCond(&.y, )p256PointAddAsm(&, , &)p256MovCond(&, &, , )p256MovCond(, &, &, ) |= }p256PointDoubleAsm(, )p256PointDoubleAsm(, )p256PointDoubleAsm(, )p256PointDoubleAsm(, )p256PointDoubleAsm(, ) = ([0] << 1) & 0x3f , = boothW5(uint())p256Select(&, &, )p256NegCond(&.y, )p256PointAddAsm(&, , &)p256MovCond(&, &, , )p256MovCond(, &, &, )}
The pages are generated with Goldsv0.6.9-preview. (GOOS=linux GOARCH=amd64)
Golds is a Go 101 project developed by Tapir Liu.
PR and bug reports are welcome and can be submitted to the issue list.
Please follow @Go100and1 (reachable from the left QR code) to get the latest news of Golds.