p751

Documentation

Overview

Package p751 provides implementation of field arithmetic used in SIDH and SIKE.

Index

• Constants
• Variables
• func CalcAplus2Over4(cparams *ProjectiveCurveParameters) (ret Fp2)
• func CalcCurveParamsEquiv3(cparams *ProjectiveCurveParameters) CurveCoefficientsEquiv
• func CalcCurveParamsEquiv4(cparams *ProjectiveCurveParameters) CurveCoefficientsEquiv
• func DeriveSecretA(ss, prv []byte, pub3Pt *[3]Fp2)
• func DeriveSecretB(ss, prv []byte, pub3Pt *[3]Fp2)
• func Fp2Batch3Inv(x1, x2, x3, y1, y2, y3 *Fp2)
• func FromMontgomery(out, in *common.Fp2)
• func Jinvariant(cparams *ProjectiveCurveParameters, j *Fp2)
• func Pow2k(xP *ProjectivePoint, params *CurveCoefficientsEquiv, k uint32)
• func Pow3k(xP *ProjectivePoint, params *CurveCoefficientsEquiv, k uint32)
• func PublicKeyGenA(pub3Pt *[3]Fp2, prvBytes []byte)
• func PublicKeyGenB(pub3Pt *[3]Fp2, prvBytes []byte)
• func PublicKeyValidation(cparams *ProjectiveCurveParameters, P, Q, PmQ *ProjectivePoint, nbits uint) error
• func RecoverCoordinateA(curve *ProjectiveCurveParameters, xp, xq, xr *Fp2)
• func RecoverCurveCoefficients3(cparams *ProjectiveCurveParameters, coefEq *CurveCoefficientsEquiv)
• func RecoverCurveCoefficients4(cparams *ProjectiveCurveParameters, coefEq *CurveCoefficientsEquiv)
• func ScalarMul3Pt(cparams *ProjectiveCurveParameters, P, Q, PmQ *ProjectivePoint, nbits uint, ...) ProjectivePoint
• func ToMontgomery(out, in *common.Fp2)

Constants

const (
	// Number of uint64 limbs used to store field element
	FpWords = 12
)

Variables

var (
	// HasBMI2 signals support for MULX which is in BMI2
	HasBMI2 = cpu.X86.HasBMI2
	// HasADXandBMI2 signals support for ADX and BMI2
	HasADXandBMI2 = cpu.X86.HasBMI2 && cpu.X86.HasADX
	// P751 is a prime used by field Fp751
	P751 = common.Fp{
		0xffffffffffffffff, 0xffffffffffffffff, 0xffffffffffffffff,
		0xffffffffffffffff, 0xffffffffffffffff, 0xeeafffffffffffff,
		0xe3ec968549f878a8, 0xda959b1a13f7cc76, 0x084e9867d6ebe876,
		0x8562b5045cb25748, 0x0e12909f97badc66, 0x00006fe5d541f71c,
	}

	// P751x2 = 2*p751 - 1
	P751x2 = common.Fp{
		0xFFFFFFFFFFFFFFFE, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF,
		0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xDD5FFFFFFFFFFFFF,
		0xC7D92D0A93F0F151, 0xB52B363427EF98ED, 0x109D30CFADD7D0ED,
		0x0AC56A08B964AE90, 0x1C25213F2F75B8CD, 0x0000DFCBAA83EE38,
	}

	// P751p1 = p751 + 1
	P751p1 = common.Fp{
		0x0000000000000000, 0x0000000000000000, 0x0000000000000000,
		0x0000000000000000, 0x0000000000000000, 0xeeb0000000000000,
		0xe3ec968549f878a8, 0xda959b1a13f7cc76, 0x084e9867d6ebe876,
		0x8562b5045cb25748, 0x0e12909f97badc66, 0x00006fe5d541f71c,
	}

	// P751R2 = (2^768)^2 mod p
	P751R2 = common.Fp{
		0x233046449DAD4058, 0xDB010161A696452A, 0x5E36941472E3FD8E,
		0xF40BFE2082A2E706, 0x4932CCA8904F8751, 0x1F735F1F1EE7FC81,
		0xA24F4D80C1048E18, 0xB56C383CCDB607C5, 0x441DD47B735F9C90,
		0x5673ED2C6A6AC82A, 0x06C905261132294B, 0x000041AD830F1F35,
	}

	// P751p1Zeros number of 0 digits in the least significant part of P751+1
	P751p1Zeros = 5
)

Functions

func CalcAplus2Over4

func CalcAplus2Over4(cparams *ProjectiveCurveParameters) (ret Fp2)

Helper function for RightToLeftLadder(). Returns A+2C / 4.

func CalcCurveParamsEquiv3

func CalcCurveParamsEquiv3(cparams *ProjectiveCurveParameters) CurveCoefficientsEquiv

Computes equivalence (A:C) ~ (A+2C : A-2C)

func CalcCurveParamsEquiv4

func CalcCurveParamsEquiv4(cparams *ProjectiveCurveParameters) CurveCoefficientsEquiv

Computes equivalence (A:C) ~ (A+2C : 4C)

func DeriveSecretA

func DeriveSecretA(ss, prv []byte, pub3Pt *[3]Fp2)

Establishing shared keys in in 2-torsion group

func DeriveSecretB

func DeriveSecretB(ss, prv []byte, pub3Pt *[3]Fp2)

Establishing shared keys in in 3-torsion group

func Fp2Batch3Inv

func Fp2Batch3Inv(x1, x2, x3, y1, y2, y3 *Fp2)

Set (y1, y2, y3) = (1/x1, 1/x2, 1/x3).

All xi, yi must be distinct.

func FromMontgomery

func FromMontgomery(out, in *common.Fp2)

Converts in.A and in.B from Montgomery domain and stores in 'out' out.A = in.A mod p out.B = in.B mod p

After returning from the call 'in' is not modified.

func Jinvariant

func Jinvariant(cparams *ProjectiveCurveParameters, j *Fp2)

Computes j-invariant for a curve y2=x3+A/Cx+x with A,C in F_(p^2). Result is returned in jBytes buffer, encoded in little-endian format. Caller provided jBytes buffer has to be big enough to j-invariant value. In case of SIDH, buffer size must be at least size of shared secret. Implementation corresponds to Algorithm 9 from SIKE.

func Pow2k

func Pow2k(xP *ProjectivePoint, params *CurveCoefficientsEquiv, k uint32)

Given the curve parameters, xP = x(P), computes xP = x([2^k]P) Safe to overlap xP, x2P.

func Pow3k

func Pow3k(xP *ProjectivePoint, params *CurveCoefficientsEquiv, k uint32)

Given the curve parameters, xP = x(P), and k >= 0, compute xP = x([3^k]P).

Safe to overlap xP, xR.

func PublicKeyGenA

func PublicKeyGenA(pub3Pt *[3]Fp2, prvBytes []byte)

Generate a public key in the 2-torsion group. Public key is a set of three x-coordinates: xP,xQ,x(P-Q), where P,Q are points on E_a(Fp2)

func PublicKeyGenB

func PublicKeyGenB(pub3Pt *[3]Fp2, prvBytes []byte)

Generate a public key in the 2-torsion group. Public key is a set of three x-coordinates: xP,xQ,x(P-Q), where P,Q are points on E_a(Fp2)

func PublicKeyValidation

func PublicKeyValidation(cparams *ProjectiveCurveParameters, P, Q, PmQ *ProjectivePoint, nbits uint) error

PublicKeyValidation preforms public key/ciphertext validation using the CLN test. CLN test: Check that P and Q are both of order 3^e3 and they generate the torsion E_A[3^e3] A countermeasure for remote timing attacks on SIKE; suggested by https://eprint.iacr.org/2022/054.pdf Any curve E_A (SIKE 434, 503, 751) that passes CLN test is supersingular. Input: The public key / ciphertext P, Q, PmQ. The projective coordinate A of the curve defined by (P, Q, PmQ) Outputs: Whether (P,Q,PmQ) follows the CLN test

func RecoverCoordinateA

func RecoverCoordinateA(curve *ProjectiveCurveParameters, xp, xq, xr *Fp2)

Given affine points x(P), x(Q) and x(Q-P) in a extension field F_{p^2}, function recovers projective coordinate A of a curve. This is Algorithm 10 from SIKE.

func RecoverCurveCoefficients3

func RecoverCurveCoefficients3(cparams *ProjectiveCurveParameters, coefEq *CurveCoefficientsEquiv)

Recovers (A:C) curve parameters from projectively equivalent (A+2C:A-2C).

func RecoverCurveCoefficients4

func RecoverCurveCoefficients4(cparams *ProjectiveCurveParameters, coefEq *CurveCoefficientsEquiv)

Recovers (A:C) curve parameters from projectively equivalent (A+2C:4C).

func ScalarMul3Pt

func ScalarMul3Pt(cparams *ProjectiveCurveParameters, P, Q, PmQ *ProjectivePoint, nbits uint, scalar []uint8) ProjectivePoint

Scalarmul3Pt is a right-to-left point multiplication that given the x-coordinate of P, Q and P-Q calculates the x-coordinate of R=Q+[scalar]P. nbits must be smaller or equal to len(scalar).

func ToMontgomery

func ToMontgomery(out, in *common.Fp2)

Converts in.A and in.B to Montgomery domain and stores in 'out' out.A = in.A * R mod p out.B = in.B * R mod p Performs v = v*R^2*R^(-1) mod p, for both in.A and in.B