p503

Documentation

Overview

Package p503 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 = 8
)

Variables

var (
	// According to https://github.com/golang/go/issues/28230,
	// variables referred from the assembly must be in the same package.
	// 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

	// P503 is a prime used by field Fp503
	P503 = common.Fp{
		0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xABFFFFFFFFFFFFFF,
		0x13085BDA2211E7A0, 0x1B9BF6C87B7E7DAF, 0x6045C6BDDA77A4D0, 0x004066F541811E1E,
	}

	// P503x2 = 2*p503 - 1
	P503x2 = common.Fp{
		0xFFFFFFFFFFFFFFFE, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0x57FFFFFFFFFFFFFF,
		0x2610B7B44423CF41, 0x3737ED90F6FCFB5E, 0xC08B8D7BB4EF49A0, 0x0080CDEA83023C3C,
	}

	// P503p1 = p503 + 1
	P503p1 = common.Fp{
		0x0000000000000000, 0x0000000000000000, 0x0000000000000000, 0xAC00000000000000,
		0x13085BDA2211E7A0, 0x1B9BF6C87B7E7DAF, 0x6045C6BDDA77A4D0, 0x004066F541811E1E,
	}

	// P503R2 = (2^512)^2 mod p
	P503R2 = common.Fp{
		0x5289A0CF641D011F, 0x9B88257189FED2B9, 0xA3B365D58DC8F17A, 0x5BC57AB6EFF168EC,
		0x9E51998BD84D4423, 0xBF8999CBAC3B5695, 0x46E9127BCE14CDB6, 0x003F6CFCE8B81771,
	}

	// P503p1s8 = p503 + 1 left-shifted by 8, assuming little endianness
	P503p1s8 = common.Fp{
		0x0000000000000000, 0x0000000000000000, 0x0000000000000000, 0x0000000000000000,
		0x085BDA2211E7A0AC, 0x9BF6C87B7E7DAF13, 0x45C6BDDA77A4D01B, 0x4066F541811E1E60,
	}

	// P503p1Zeros number of 0 digits in the least significant part of P503+1
	P503p1Zeros = 3
)

P503 is a prime used by field Fp503

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 recorvers 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