#include <cECPGroup.h>

Inheritance diagram for GrayLib::cECPGroup:

Public Member Functions
	cECPGroup () noexcept

	~cECPGroup ()

void	SetEmptyECPGroup ()

ECPGroup_TYPE	get_ECPGroupId () const noexcept

const cECPGroupDef *	get_ECPGroupDef () const noexcept

HRESULT	put_ECPGroupDef (const cECPGroupDef *pECPGroupDef)

HRESULT	put_ECPGroupId (ECPGroup_TYPE eECPGroupId)

HRESULT	SetECParameters (const cASNBuf &params)

HRESULT	DoMult (OUT cECPPoint &R, const cBigUnsigned &m, const cECPPoint &P, IRandomNoise *pRandom) const

HRESULT	SetCopyECP (const cECPGroup &rSrc)

HRESULT	GenerateKeys (cBigUnsigned &d, cECPPoint &Q, IRandomNoise *pRandom) const

HRESULT	IsValidPublicKey (const cECPPoint &pt) const

HRESULT	MakeSignatureECDSA (OUT cBigInteger &r, OUT cBigInteger &s, const cBigInteger &d, const BYTE buf, size_t nSizeBuffer, IRandomNoise pRandom) const

HRESULT	VerifySignatureECDSA (const BYTE *buf, size_t nSizeBuffer, const cECPPoint &Q, const cBigInteger &r, const cBigInteger &s) const

	UNITTEST_FRIEND (cECPGroup)

Public Member Functions inherited from GrayLib::cECPGroupParams
	cECPGroupParams ()

ECP_CurveType_t	get_ECP_CurveType () const

size_t	get_SizeP () const

void	DoModPLo (OUT cBigInteger &N) const

void	DoModPHi (OUT cBigInteger &N) const

bool	IsMatchECPParams (const cECPGroupParams &ref) const

HRESULT	IsValidPrivateKey (const cBigUnsigned &d) const

void	UpdateBits ()

void	InjectCommon ()

HRESULT	SetCopyECP (const THIS_t &rSrc)

void	SetEmptyECPGroup ()

HRESULT	ReadSpecifiedECDomain (cASNReader &r)

HRESULT	SetECPGroupFromStr (RADIX_t radix, const char p, const char b, const char gx, const char gy, const char *n)

HRESULT	ReadBigIntECDSA (OUT cBigInteger &x, const BYTE *buf, size_t nSizeBuffer) const

Public Attributes
const cECPGroupDef *	m_pECPGroupDef
	internal group identifier. predefined curve. More...

cArrayStruct< cECPPoint >	m_aT
	pre-computed points for Comb_mul() More...

Public Attributes inherited from GrayLib::cECPGroupParams
cBigInteger	m_P
	prime modulus of the base field More...

BIT_ENUM_t	m_nPBits
	number of used bits in P. m_P.get_Highest1Bit(); More...

cBigInteger	m_A

cBigInteger	m_B

cECPPoint	m_G
	generator of the (sub)group used More...

cBigInteger	m_N

BIT_ENUM_t	m_nNBits
	number of used bits get_Highest1Bit() in 1. m_N, or 2. private keys More...

Static Public Attributes
static const int	k_ECP_WINDOW_SIZE = 6
	Maximum window size used. 2 to 7 are valid. More...

static cECPStats	sm_ECPStats

Static Public Attributes inherited from GrayLib::cECPGroupParams
static const char *	k_pszPEM = "EC PARAMETERS"
	"EC PARAMETERS" More...

static const WORD	k_ECP_MAX_BITS = 521
	Maximum bit size of groups (that is, of N and P) More...

static const WORD	k_ECP_MAX_BYTES = GETSIZEBYTES(k_ECP_MAX_BITS)

static const WORD	k_COMB_MAX_D = (k_ECP_MAX_BITS + 1) / 2

Protected Member Functions
HRESULT	DoModP (OUT cBigInteger &N) const

HRESULT	DoMulModP (OUT cBigInteger &X, const cBigInteger &Y, const cBigInteger &Z) const

HRESULT	DoAddMixed (OUT cECPPoint &R, const cECPPoint &P, const cECPPoint &Q) const

HRESULT	Mxz_normalize (cECPPoint &P) const

HRESULT	Mxz_randomize (cECPPoint &P, IRandomNoise *pRandom) const

HRESULT	Mxz_add_double (cECPPoint &R, cECPPoint &S, const cECPPoint &P, const cECPPoint &Q, const cBigInteger &d) const

HRESULT	Mxz_mul (cECPPoint &R, const cBigInteger &m, const cECPPoint &P, IRandomNoise *pRandom) const

HRESULT	Jac_normalize (cECPPoint &pt) const

HRESULT	Jac_normalize_many (cECPPoint *pT[], ITERATE_t t_len) const

HRESULT	Jac_double (cECPPoint &R, const cECPPoint &P) const

HRESULT	Jac_randomize (cECPPoint &pt, IRandomNoise *pRandom) const

HRESULT	Jac_safe_invert (cECPPoint &Q, bool inv) const

HRESULT	Comb_precompute (cECPPoint T[], const cECPPoint &P, BYTE w, size_t d) const

HRESULT	Comb_mul_core (cECPPoint &R, const cECPPoint T[], BYTE t_len, const BYTE x[], size_t d, IRandomNoise *pRandom) const

HRESULT	Comb_mul (OUT cECPPoint &R, const cBigUnsigned &m, const cECPPoint &P, IRandomNoise *pRandom) const

HRESULT	Comb_select (cECPPoint &R, const cECPPoint T[], BYTE t_len, BYTE i) const

HRESULT	DoAdd (OUT cECPPoint &R, const cECPPoint &P, const cECPPoint &Q) const

HRESULT	DoSub (cECPPoint &R, const cECPPoint &P, const cECPPoint &Q) const

HRESULT	IsValidPublicKeyWS (const cECPPoint &pt) const

HRESULT	IsValidPublicKeyMX (const cECPPoint &pt) const

Static Protected Member Functions
static void	Comb_fixed (BYTE x[], size_t d, BYTE w, const cBigInteger &m)

Detailed Description

ECP group structure

We consider two types of curves equations: ECP_CurveType_t

Short Weierstrass y^2 = x^3 + A x + B mod P (SEC1 + RFC 4492)
Montgomery, y^2 = x^3 + A x^2 + x mod P (M255 + draft) ecdh_x25519

In both cases, a generator G for a prime-order subgroup is fixed. In the short Weierstrass, this subgroup is actually the whole curve, and its cardinal is denoted by N.

In the case of ECP_CurveType_SHORT_WEIERSTRASS, our code requires that N is an odd prime. (Use odd in DoMult() and prime in MakeSignatureECDSA() for blinding.)

In the case of ECP_CurveType_MONTGOMERY, we don't store A but (A + 2) / 4 which is the quantity actually used in the formulas. Also, nbits is not the size of N but the required size for private keys.

Constructor & Destructor Documentation

◆ cECPGroup()

GrayLib::cECPGroup::cECPGroup ( )

inlinenoexcept

◆ ~cECPGroup()

GrayLib::cECPGroup::~cECPGroup ( )

inline

Member Function Documentation

◆ Comb_fixed()

void GrayLib::cECPGroup::Comb_fixed	(	BYTE	x[],
		size_t	d,
		BYTE	w,
		const cBigInteger &	m
	)

staticprotected

Compute the representation of m that will be used with our comb method.

◆ Comb_mul()

HRESULT GrayLib::cECPGroup::Comb_mul	(	OUT cECPPoint &	R,
		const cBigUnsigned &	m,
		const cECPPoint &	P,
		IRandomNoise *	pRandom
	)		const

protected

Multiplication using the comb method, called via DoMult() for curves in ECP_CurveType_SHORT_WEIERSTRASS form we need N to be odd to transform m in an odd number, check now

◆ Comb_mul_core()

HRESULT GrayLib::cECPGroup::Comb_mul_core	(	cECPPoint &	R,
		const cECPPoint	T[],
		BYTE	t_len,
		const BYTE	x[],
		size_t	d,
		IRandomNoise *	pRandom
	)		const

protected

Core multiplication algorithm for the (modified) comb method. This part is actually common with the basic comb method (GECC 3.44) Cost: d A + d D + 1 R

◆ Comb_precompute()

HRESULT GrayLib::cECPGroup::Comb_precompute	(	cECPPoint	T[],
		const cECPPoint &	P,
		BYTE	w,
		size_t	d
	)		const

protected

Precompute points for the comb method

If i = i_{w-1} ... i_1 is the binary representation of i, then T[i] = i_{w-1} 2^{(w-1)d} P + ... + i_1 2^d P + P

T must be able to hold 2^{w - 1} elements

Cost: d(w-1) D + (2^{w-1} - 1) A + 1 N(w-1) + 1 N(2^{w-1} - 1)

◆ Comb_select()

HRESULT GrayLib::cECPGroup::Comb_select	(	cECPPoint &	R,
		const cECPPoint	T[],
		BYTE	t_len,
		BYTE	i
	)		const

protected

Select precomputed point: R = sign(i) * T[ ABS(i) / 2 ]

◆ DoAdd()

HRESULT GrayLib::cECPGroup::DoAdd	(	OUT cECPPoint &	R,
		const cECPPoint &	P,
		const cECPPoint &	Q
	)		const

protected

Addition: R = P + Q, result's coordinates normalized

R = Destination point
P = Left-hand point
Q = Right-hand point
Returns
0 = successful, E_OUTOFMEMORY if memory allocation failed

Note
This function does not support Montgomery curves, such as Curve25519.

◆ DoAddMixed()

HRESULT GrayLib::cECPGroup::DoAddMixed	(	OUT cECPPoint &	R,
		const cECPPoint &	P,
		const cECPPoint &	Q
	)		const

protected

Addition: R = P + Q, mixed affine-Jacobian coordinates (GECC 3.22)

The coordinates of Q must be normalized (= affine), but those of P don't need to. R is not normalized.

Special cases: (1) P or Q is zero, (2) R is zero, (3) P == Q. None of these cases can happen as intermediate step in Comb_mul():

at each step, P, Q and R are multiples of the base point, the factor being less than its order, so none of them is zero;
Q is an odd multiple of the base point, P an even multiple, due to the choice of precomputed points in the modified comb method. So branches for these cases do not leak secret information.

We accept Q.Z being unset (saving memory in tables) as meaning 1.

Cost: 1A := 8M + 3S

◆ DoModP()

HRESULT GrayLib::cECPGroup::DoModP ( OUT cBigInteger & N ) const

protected

Wrapper around fast quasi-modp functions, with fall-back to InitModulusU. See the documentation of class cECPGroup. This function is in the critical loop for DoMult, so pay attention to perf.

◆ DoMulModP()

HRESULT GrayLib::cECPGroup::DoMulModP	(	OUT cBigInteger &	X,
		const cBigInteger &	Y,
		const cBigInteger &	Z
	)		const

inlineprotected

◆ DoMult()

HRESULT GrayLib::cECPGroup::DoMult	(	OUT cECPPoint &	R,
		const cBigUnsigned &	m,
		const cECPPoint &	P,
		IRandomNoise *	pRandom
	)		const

Multiplication by an integer: R = m * P (Not thread-safe to use same group in multiple threads)

R = Destination point
m = Integer by which to multiply
P = Point to multiply
pRandom = RNG function (see notes)
Returns
0 if successful, NTE_BAD_KEY if m is not a valid privkey or P is not a valid pubkey, E_OUTOFMEMORY if memory allocation failed

Note
In order to prevent timing attacks, this function executes the exact same sequence of (base field) operations for any valid m. It avoids any if-branch or array index depending on the value of m.

If pRandom is not NULL, it is used to randomize intermediate results in order to prevent potential timing attacks targeting these results. It is recommended to always provide a non-NULL pRandom (the overhead is negligible).

◆ DoSub()

HRESULT GrayLib::cECPGroup::DoSub	(	cECPPoint &	R,
		const cECPPoint &	P,
		const cECPPoint &	Q
	)		const

protected

Subtraction: R = P - Q, result's coordinates normalized

R = Destination point
P = Left-hand point
Q = Right-hand point
Returns
0 if successful, E_OUTOFMEMORY if memory allocation failed

Note
This function does not support Montgomery curves, such as Curve25519.

◆ GenerateKeys()

HRESULT GrayLib::cECPGroup::GenerateKeys	(	cBigUnsigned &	d,
		cECPPoint &	Q,
		IRandomNoise *	pRandom
	)		const

Generate a key pair for ECDSA. d, Q

d = Destination MPI (secret part)
Q = Destination point (public part)
pRandom = RNG function
Returns
0 if successful, <0= error

Note
Uses bare components rather than an cKeyECPPair structure in order to ease use with other structures such as cKeyExECDH of cKeyECDSA.

◆ get_ECPGroupDef()

const cECPGroupDef* GrayLib::cECPGroup::get_ECPGroupDef ( ) const

inlinenoexcept

◆ get_ECPGroupId()

ECPGroup_TYPE GrayLib::cECPGroup::get_ECPGroupId ( ) const

inlinenoexcept

◆ IsValidPublicKey()

HRESULT GrayLib::cECPGroup::IsValidPublicKey ( const cECPPoint & pt ) const

Check that a point is valid as a public key Must use affine coordinates Check that a point is a valid public key on this curve

pt = Point to check
Returns
0 if point is a valid public key, NTE_BAD_PUBLIC_KEY otherwise.

Note
This function only checks the point is non-zero, has valid coordinates and lies on the curve, but not that it is indeed a multiple of G. This is additional check is more expensive, isn't required by standards, and shouldn't be necessary if the group used has a small cofactor. In particular, it is useless for the NIST groups which all have a cofactor of 1.

Uses bare components rather than an cKeyECPPair structure in order to ease use with other structures such as cKeyExECDH of cKeyECDSA.

◆ IsValidPublicKeyMX()

HRESULT GrayLib::cECPGroup::IsValidPublicKeyMX ( const cECPPoint & pt ) const

protected

ECP_CurveType_MONTGOMERY Check validity of a public key for ECP_CurveType_MONTGOMERY with x-only schemes [ecdh_x25519 M255 p. 5] Just check X is the correct number of bytes

◆ IsValidPublicKeyWS()

HRESULT GrayLib::cECPGroup::IsValidPublicKeyWS ( const cECPPoint & pt ) const

protected

ECP_CurveType_SHORT_WEIERSTRASS Check that an affine point is valid as a public key, short Weierstrass curves (SEC1 3.2.3.1)

◆ Jac_double()

HRESULT GrayLib::cECPGroup::Jac_double	(	cECPPoint &	R,
		const cECPPoint &	P
	)		const

protected

ECP_CurveType_SHORT_WEIERSTRASS Point doubling R = 2 P, Jacobian coordinates

Based on http://www.hyperelliptic.org/EFD/g1p/auto-shortw-Jacobian.html#doubling-dbl-1998-cmo-2 .

We follow the variable naming fairly closely. The formula variations that trade a MUL for a SQR (plus a few ADDs) aren't useful as our bignum implementation doesn't distinguish squaring.

Standard optimizations are applied when curve parameter A is one of { 0, -3 }.

Cost: 1D := 3M + 4S (A == 0) 4M + 4S (A == -3) 3M + 6S + 1a otherwise

◆ Jac_normalize()

HRESULT GrayLib::cECPGroup::Jac_normalize ( cECPPoint & pt ) const

protected

For curves in WEIERSTRASS form, we do all the internal operations in Jacobian coordinates. For multiplication, we'll use a comb method with counter measures against SPA, hence timing attacks. Normalize Jacobian coordinates so that Z == 0 || Z == 1 (GECC 3.2.1) Cost: 1N := 1I + 3M + 1S

◆ Jac_normalize_many()

HRESULT GrayLib::cECPGroup::Jac_normalize_many	(	cECPPoint *	pT[],
		ITERATE_t	t_len
	)		const

protected

ECP_CurveType_SHORT_WEIERSTRASS Normalize Jacobian coordinates of an array of (pointers to) points, using Montgomery's trick to perform only one inversion mod P. (See for example Cohen's "A Course in Computational Algebraic Number Theory", Algorithm 10.3.4.)

Warning: fails (returning an error) if one of the points is zero! This should never happen, see choice of w in Comb_mul().

Cost: 1N(t) := 1I + (6t - 3)M + 1S

◆ Jac_randomize()

HRESULT GrayLib::cECPGroup::Jac_randomize	(	cECPPoint &	pt,
		IRandomNoise *	pRandom
	)		const

protected

Randomize Jacobian coordinates: (X, Y, Z) -> (l^2 X, l^3 Y, l Z) for random l This is sort of the reverse operation of Jac_normalize(). This countermeasure was first suggested in [2].

◆ Jac_safe_invert()

HRESULT GrayLib::cECPGroup::Jac_safe_invert	(	cECPPoint &	Q,
		bool	inv
	)		const

protected

ECP_CurveType_SHORT_WEIERSTRASS Conditional point inversion: Q -> -Q = (Q.X, -Q.Y, Q.Z) without leak. "inv" must be 0 (don't invert) or 1 (invert) or the result will be invalid

◆ MakeSignatureECDSA()

HRESULT GrayLib::cECPGroup::MakeSignatureECDSA	(	OUT cBigInteger &	r,
		OUT cBigInteger &	s,
		const cBigInteger &	d,
		const BYTE *	buf,
		size_t	nSizeBuffer,
		IRandomNoise *	pRandom
	)		const

Compute ECDSA signature of a hashed message (SEC1 4.1.3) Obviously, compared to SEC1 4.1.3, we skip step 4 (hash message) Fail cleanly on curves such as Curve25519 that can't be used for ECDSA

r = First output integer
s = Second output integer
d = Private signing key
pBuffer = Message hash
nSizeBuffer = Length of pBuffer
pRandom = RNG parameter
Returns
0 if successful, <0 = error

◆ Mxz_add_double()

HRESULT GrayLib::cECPGroup::Mxz_add_double	(	cECPPoint &	R,
		cECPPoint &	S,
		const cECPPoint &	P,
		const cECPPoint &	Q,
		const cBigInteger &	d
	)		const

protected

For ECP_CurveType_MONTGOMERY Double-and-add: R = 2P, S = P + Q, with d = X(P - Q), for Montgomery curves in x/z coordinates. http://www.hyperelliptic.org/EFD/g1p/auto-code/montgom/xz/ladder/mladd-1987-m.op3 with: d = X1 P = (X2, Z2) Q = (X3, Z3) R = (X4, Z4) S = (X5, Z5) and eliminating temporary variables tO, ..., t4. Cost: 5M + 4S

◆ Mxz_mul()

HRESULT GrayLib::cECPGroup::Mxz_mul	(	cECPPoint &	R,
		const cBigInteger &	m,
		const cECPPoint &	P,
		IRandomNoise *	pRandom
	)		const

protected

ECP_CurveType_MONTGOMERY Multiplication with Montgomery ladder in x/z coordinates, for curves in Montgomery form. called via DoMult()

◆ Mxz_normalize()

HRESULT GrayLib::cECPGroup::Mxz_normalize ( cECPPoint & P ) const

protected

For ECP_CurveType_MONTGOMERY, we do all the internal arithmetic in projective coordinates. Import/export of points uses only the x coordinates, which is internally represented as X / Z. For scalar multiplication, we'll use a Montgomery ladder. Normalize Montgomery x/z coordinates: X = X/Z, Z = 1 Cost: 1M + 1I

◆ Mxz_randomize()

HRESULT GrayLib::cECPGroup::Mxz_randomize	(	cECPPoint &	P,
		IRandomNoise *	pRandom
	)		const

protected

Randomize projective x/z coordinates: (X, Z) -> (l X, l Z) for random l This is sort of the reverse operation of Mxz_normalize(). This countermeasure was first suggested in [2]. Cost: 2M

◆ put_ECPGroupDef()

HRESULT GrayLib::cECPGroup::put_ECPGroupDef ( const cECPGroupDef * pECPGroupDef )

◆ put_ECPGroupId()

HRESULT GrayLib::cECPGroup::put_ECPGroupId ( ECPGroup_TYPE eECPGroupId )

◆ SetCopyECP()

HRESULT GrayLib::cECPGroup::SetCopyECP ( const cECPGroup & rSrc )

Copy the contents of a group object

rSrc = Source group
Returns
0 if successful, E_OUTOFMEMORY if memory allocation failed

◆ SetECParameters()

HRESULT GrayLib::cECPGroup::SetECParameters ( const cASNBuf & params )

Use "EC PARAMETERS" to initialize an EC group ECParameters ::= CHOICE { namedCurve OBJECT IDENTIFIER specifiedCurve SpecifiedECDomain – = SEQUENCE { ... } – implicitCurve nullptr

◆ SetEmptyECPGroup()

void GrayLib::cECPGroup::SetEmptyECPGroup ( )

◆ UNITTEST_FRIEND()

GrayLib::cECPGroup::UNITTEST_FRIEND ( cECPGroup )

◆ VerifySignatureECDSA()

HRESULT GrayLib::cECPGroup::VerifySignatureECDSA	(	const BYTE *	buf,
		size_t	nSizeBuffer,
		const cECPPoint &	Q,
		const cBigInteger &	r,
		const cBigInteger &	s
	)		const

Verify ECDSA signature of hashed message (SEC1 4.1.4) Obviously, compared to SEC1 4.1.3, we skip step 2 (hash message) Fail cleanly on curves such as Curve25519 that can't be used for ECDSA

pBuffer = Message hash
nSizeBuffer = Length of buf
Q = Public key to use for verification
r = First integer of the signature
s = Second integer of the signature
Returns
0 if successful,

Member Data Documentation

◆ k_ECP_WINDOW_SIZE

const int GrayLib::cECPGroup::k_ECP_WINDOW_SIZE = 6

static

Maximum window size used. 2 to 7 are valid.

◆ m_aT

cArrayStruct<cECPPoint> GrayLib::cECPGroup::m_aT

mutable

pre-computed points for Comb_mul()

◆ m_pECPGroupDef

const cECPGroupDef* GrayLib::cECPGroup::m_pECPGroupDef

internal group identifier. predefined curve.

◆ sm_ECPStats

cECPStats GrayLib::cECPGroup::sm_ECPStats

static

The documentation for this class was generated from the following files:

c:/Dennis/Source/Gray/GrayLib/include/Key/cECPGroup.h
c:/Dennis/Source/Gray/GrayLib/src/Key/cECPGroup.cpp

Public Member Functions

Public Attributes

Static Public Attributes

Protected Member Functions

Static Protected Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ cECPGroup()

◆ ~cECPGroup()

Member Function Documentation

◆ Comb_fixed()

◆ Comb_mul()

◆ Comb_mul_core()

◆ Comb_precompute()

◆ Comb_select()

◆ DoAdd()

◆ DoAddMixed()

◆ DoModP()

◆ DoMulModP()

◆ DoMult()

◆ DoSub()

◆ GenerateKeys()

◆ get_ECPGroupDef()

◆ get_ECPGroupId()

◆ IsValidPublicKey()

◆ IsValidPublicKeyMX()

◆ IsValidPublicKeyWS()

◆ Jac_double()

◆ Jac_normalize()

◆ Jac_normalize_many()

◆ Jac_randomize()

◆ Jac_safe_invert()

◆ MakeSignatureECDSA()

◆ Mxz_add_double()

◆ Mxz_mul()

◆ Mxz_normalize()

◆ Mxz_randomize()

◆ put_ECPGroupDef()

◆ put_ECPGroupId()

◆ SetCopyECP()

◆ SetECParameters()

◆ SetEmptyECPGroup()

◆ UNITTEST_FRIEND()

◆ VerifySignatureECDSA()

Member Data Documentation

◆ k_ECP_WINDOW_SIZE

◆ m_aT

◆ m_pECPGroupDef

◆ sm_ECPStats