FourQ椭圆曲线

2019/07/30 密码学

本文以FourQlib代码对椭圆曲线密码算法讨论,并提出基于FourQlib上的点加法,以及介绍基于FourQ的Schnorr签名方案。FourQlib的代码仓库地址是https://github.com/microsoft/FourQlib,下面是关于它的简介。

FourQlib implements essential elliptic curve and cryptographic functions based on FourQ, a high-security, high-performance elliptic curve that targets the 128-bit security level. At the high level, FourQlib consists of a set of implementations targeting different platforms with different levels of portability and performance. The cryptographic and elliptic curve API is common to all the implementations.

Weierstrass等式

设\(K\)为有限域,在\(K\)上的椭圆曲线可以定义为Weierstrass等式

\[E:y^{2}+a_{1}xy+a_{3}y=x^{3}+a_{2}x^{2}+a_{4}x+a_{6}\]

任何组\((x,y)\)满足上述等式称作曲线\(E\)上的点\(P\)。假设椭圆曲线\(E\)上有两个点\(P=(x_{1},y_{1}),Q=(x_{2},y_{2})\),下面是对该椭圆曲线的描述:

  • 零元:无穷远点\(\infty\)是该椭圆曲线\(E\)的加法群的零元。
  • 逆元:点\(P\)的逆元定义为\(-P=(x_{1},-y_{1}-a_{1}x_{1}-a_{3})\),并且\(P+(-P)=\infty\)。
  • 加法定律:加法定律描述为 \(P+Q=(t^{2}+a_{1}t-a_{2}-x_{1}-x_{2},t(x_{1}-x_{3})-y_{1}-a_{1}x_{3}-a_{3})\)

使用可行变量变换将素数域上的Weierstrass等式转化为曲线:

\[E:y^{2}=x^{3}+ax+b\]

下图是当\(a,b\)不同取值下的曲线在有理数域中的图像:

Montgomery曲线

1987年,Peter L.Montgomery提出了椭圆曲线的等价形式,令\(p\)为素数,\(F_{p}\)是素数域,其模为\(p\),在\(F_{p}\)上的Montgomery曲线定义为:

\[E:BY^{2}=X^{3}+AX^{2}+X\]

在仿射坐标系下的Montgomery椭圆曲线加法法则分别描述为:

\[P_{1}=(x_{1},y_{1}),P_{2}=(x_{2},y_{2})\] \[P_{3}=(x_{3},y_{3})=P_{1}+P_{2}\]

点加法公式(\(P_{1} \neq\pm P_{2}\))

\[t=(y_{1}-y_{2})/(x_{1}-x_{2})\] \[x_{3}=Bt^{2}-A-x_{1}-x_{2}\] \[y_{3}=t(x_{1}-x_{3})-y_{1}\]

点倍公式(\(P_{1}=P_{2}\))

\[t=(3x_{1}^{2}+2Ax_{1}+1)/(2By_{1})\] \[x_{3}=Bt^{2}-A-2x_{1}\] \[y_{3}=t(x_{1}-x_{3})-y_{1}\]

点倍公式可以计算\(2P\),进一步拓展至标量乘法,下面是Montgomery椭圆曲线上的标量乘法伪代码。

输入:n,P
输出:nP

len = bits of n
P1 = P
P2 = 2P
for i from len-2 down to 0 do
  if the_i_bit_of_n = 1 then
    P1 = P1 + P2
    P2 = 2P2
  else
    P2 = P1 + P2
    P1 = 2P1
  end if
end for
return P2

Edwards曲线

2007年,Harold M. Edwards提出了一种椭圆曲线的新表达形式。Daniel J. Bernstein和Tanja Lange讨论了这类曲线的细节并提出了特殊的点加法和点倍运算的快速实现。设\(K\)为有限域,其特征值不为2,在域\(K\)上的Edwards椭圆曲线可以由以下等式定义。

\[x^{2}+y^{2}=c^{2}(1+dx^{2}y^{2})\]

其中\(c\neq 0,d\neq 0\)且\(dc^{4}\neq 1\)。

对于Edwards曲线的群结构定义如下,令\(P_{1}=(x_{1},y_{1}),P_{2}=(x_{2},y_{2})\)为Edwards曲线\(x^{2}+y^{2}=c^{2}(1+dx^{2}y^{2})\)上的点。

  • 零元:\((0,c)\)
  • 逆元:Edwards曲线上点\(P_{1}=(x_{1},y_{1})\)的逆元为\(-P_{1}=(-x_{1},y_{1})\)
  • 加法法则:Edwards曲线上的点加加法法则为:

    \[P_{1}+P_{2}=(\frac{x_{1}y_{2}+y_{1}x_{2}}{c(1+dx_{1}y_{1}x_{2}y_{2})},\frac{y_{1}y_{2}-x_{1}x_{2}}{c(1-dx_{1}y_{1}x_{2}y_{2})})\]

采用标准投影坐标系将原始曲线公式转换为下面形式:

\[(X^{2}+Y^{2})Z^{2}=c^{2}(Z^{4}+dX^{2}Y^{2})\]

令\(P_{1}=(X_{1}:Y_{1}:Z_{1}),P_{2}=(X_{2}:Y_{2}:Z_{2})\),有\(P_{3}=P_{1}+P_{2}=(X_{3}:Y_{3}:Z_{3})\)。对该形式下的群结构定义为:

  • 零元:\((0:c:1)\)
  • 逆元:Edwards曲线上点\(P_{1}=(X_{1}:Y_{1}:Z_{1})\)的逆元为\(-P_{1}=(-X_{1}:Y_{1}:Z_{1})\)
  • 加法法则:Edwards曲线上的点加加法法则为:

    \[X_{3}=Z_{1}Z_{2}(Z_{1}^{2}Z_{2}^{2}-dX_{1}X_{2}Y_{1}Y_{2})((X_{1}+Y_{1})(X_{2}+Y_{2})-X_{1}X_{2}-Y_{1}Y_{2})\] \[Y_{3}=Z_{1}Z_{2}(Z_{1}^{2}Z_{2}^{2}+dX_{1}X_{2}Y_{1}Y_{2})(Y_{1}Y_{2}-X_{1}X_{2})\] \[Z_{3}=c(Z_{1}^{2}Z_{2}^{2}-dX_{1}X_{2}Y_{1}Y_{2})(Z_{1}^{2}Z_{2}^{2}+dX_{1}X_{2}Y_{1}Y_{2})\]

根据加法法则,容易得出点倍公式:

\[P_{3}=P_{1}+P_{1}=2P_{1}=(X_{3}:Y_{3}:Z_{3})\] \[X_{3}=c((X_{1}+Y_{1})^{2}-X_{1}^{2}-Y_{1}^{2})(X_{1}^{2}+Y_{1}^{2}-2(cZ_{1})^{2})\] \[Y_{3}=c(X_{1}^{2}+Y_{1}^{2})(X_{1}^{2}-Y_{1}^{2})\] \[Z_{3}=(X_{1}^{2}+Y_{1}^{2})(X_{1}^{2}+Y_{1}^{2}-2(cZ_{1})^{2})\]

扭曲的Edwards曲线

Bernstein等人在2008年提出了一个椭圆曲线族。令\(K\)为有限域,特征值不为2,在域\(K\)上的扭曲的Edwards曲线定义为:

\[E:ax^{2}+y^{2}=1+dx^{2}y^{2}\]

Edwards曲线是扭曲Edwards曲线在\(a=1\)情况下的特例。

2008年Hisil等人介绍了一种更加有效的方法表示点,叫做拓展的扭曲Edwards坐标系。表述形式为\((X:Y:T:Z)\),其中\(Z\neq 0,x=X/Z,y=Y/Z,T=XY/Z\)。此时群结构描述为:

  • 零元:\((0:1:0:1)\)
  • 逆元:扭曲的Edwards曲线上点\(P_{1}=(X_{1}:Y_{1}:T_{1}:Z_{1})\)的逆元为\(-P_{1}=(-X_{1}:Y_{1}:-T_{1}:Z_{1})\)
  • 加法法则:Edwards曲线上的点加加法法则为:

    \[X_{3}=((X_{1}+X_{2})(Y_{1}+Y_{2})-X_{1}Y_{1}-X_{2}Y_{2})(Z_{1}Z_{2}-dT_{1}T_{2})\] \[Y_{3}=(Y_{1}Y_{2}-aX_{1}X_{2})(Z_{1}Z_{2}+dT_{1}T_{2})\] \[T_{3}=(Y_{1}Y_{2}-aX_{1}X_{2})((X_{1}+X_{2})(Y_{1}+Y_{2})-X_{1}Y_{1}-X_{2}Y_{2})\] \[Z_{3}=(Z_{1}Z_{2}-dT_{1}T_{2})(Z_{1}Z_{2}+dT_{1}T_{2})\]

根据加法法则,容易得出点倍公式:

\[P_{3}=P_{1}+P_{1}=2P_{1}=(X_{3}:Y_{3}:T_{3}:Z_{3})\] \[X_{3}=2X_{1}Y_{2}(dT_{1}^{2}-Z_{1}^{2})\] \[Y_{3}=(aX_{1}^{2}-Y_{1}^{2})(Z_{1}^{2}+dT_{1}^{2})\] \[T_{3}=2X_{1}Y_{1}(aX_{1}^{2}-Y_{1}^{2})\] \[Z_{3}=(Z_{1}^{2}+dT_{1}^{2})(dT_{1}^{2}-Z_{1}^{2})\]

FourQ使用的曲线

FourQ使用的是扭曲的Edwards曲线,令\(p=2^{127}-1,i^{2}=-1\),在该域中定义曲线:

\[E:-x^{2}+y^{2}=1+dx^{2}y^{2}\] \[d=125317048443780598345676279555970305165i+4205857648805777768770\]

运行FourQlib

从github仓库clone源代码到本地,在Ubuntu操作系统下,执行下列命令:

cd FourQlib/FourQ_64bit_and_portable
make ARCH=x64

## 分别执行测试样例

./crypto_test
./ecc_test
./fp_test

基于FourQ的点加加法

在FourQlib代码中的公开API中,ECC对应的函数提供了4个,分别是

// Set generator G = (x,y)
void eccset(point_t G);

// Variable-base scalar multiplication Q = k*P
bool ecc_mul(point_t P, digit_t* k, point_t Q, bool clear_cofactor);

// Fixed-base scalar multiplication Q = k*G, where G is the generator
bool ecc_mul_fixed(digit_t* k, point_t Q);

// Double scalar multiplication R = k*G + l*Q, where G is the generator
bool ecc_mul_double(digit_t* k, point_t Q, digit_t* l, point_t R);

另外在内置函数库中,我发现有3个点加加法的函数:

// Complete point addition P = P+Q or P = P+P
void eccadd_ni(point_extproj_precomp_t Q, point_extproj_t P);
void eccadd(point_extproj_precomp_t Q, point_extproj_t P);
void eccadd_core(point_extproj_precomp_t P, point_extproj_precomp_t Q, point_extproj_t R); 

然而上述封装的函数并不能直接计算曲线上两个点的加法,因为后3个函数的参数列表中,点已经经过转换到拓展的扭曲EEdwards曲线表达形式。

下面是我给出的一个直接对曲线上两个点的加法的实现。

// Complete point addition R=P+Q
void eccadd_point(point_t P, point_t Q, point_t R){
    point_extproj_t PP, QQ, RR;
    point_extproj_precomp_t PPP, QQQ;
    point_setup(P, PP);
    point_setup(Q, QQ);
    R1_to_R2(PP, PPP);
    R1_to_R3(QQ, QQQ);
    eccadd_core(PPP, QQQ, RR);
    eccnorm(RR, R);
}

下面的函数对上述加法进行验算:

bool add_test(){
    point_t P, Q;
    point_t LF, RF;
    point_t G;
    eccset(G);
    uint64_t p[4], q[4];
    random_scalar_test(p);
    random_scalar_test(q);
    // P = pG
    ecc_mul_fixed((digit_t*)p, P);
    // Q = qG
    ecc_mul_fixed((digit_t*)q, Q);
    // LF = pG + qG = P + Q
    ecc_mul_double(p, G, q, LF);
    // RF = P + Q
    eccadd_point(P, Q, RF);

    mod1271(LF->x[0]); mod1271(LF->x[1]);
    mod1271(LF->y[0]); mod1271(LF->y[1]);
    mod1271(RF->x[0]); mod1271(RF->x[1]);
    mod1271(RF->y[0]); mod1271(RF->y[1]); 

    // LF =? RF
    if(fp2compare64((uint64_t*)LF->x, (uint64_t*)RF->x)!=0 || fp2compare64((uint64_t*)LF->y, (uint64_t*)RF->y)!=0){
        printf("False.\n");
        return false;
    } else {
        printf("Successed!\n");
        return true;
    }
}

基于FourQ的Schnorr签名方案

在FourQlib中分别提供了4个函数用于Schnorr签名,分别是

// SchnorrQ public key generation
// It produces a public key PublicKey, which is the encoding of P = s*G, where G is the generator and
// s is the output of hashing SecretKey and taking the least significant 32 bytes of the result.
// Input:  32-byte SecretKey
// Output: 32-byte PublicKey
ECCRYPTO_STATUS SchnorrQ_KeyGeneration(const unsigned char* SecretKey, unsigned char* PublicKey);

// SchnorrQ keypair generation
// It produces a private key SecretKey and computes the public key PublicKey, which is the encoding of P = s*G, 
// where G is the generator and s is the output of hashing SecretKey and taking the least significant 32 bytes of the result.
// Outputs: 32-byte SecretKey and 32-byte PublicKey
ECCRYPTO_STATUS SchnorrQ_FullKeyGeneration(unsigned char* SecretKey, unsigned char* PublicKey);

// SchnorrQ signature generation
// It produces the signature Signature of a message Message of size SizeMessage in bytes
// Inputs: 32-byte SecretKey, 32-byte PublicKey, and Message of size SizeMessage in bytes
// Output: 64-byte Signature 
ECCRYPTO_STATUS SchnorrQ_Sign(const unsigned char* SecretKey, const unsigned char* PublicKey, const unsigned char* Message, const unsigned int SizeMessage, unsigned char* Signature);

// SchnorrQ signature verification
// It verifies the signature Signature of a message Message of size SizeMessage in bytes
// Inputs: 32-byte PublicKey, 64-byte Signature, and Message of size SizeMessage in bytes
// Output: true (valid signature) or false (invalid signature)
ECCRYPTO_STATUS SchnorrQ_Verify(const unsigned char* PublicKey, const unsigned char* Message, const unsigned int SizeMessage, const unsigned char* Signature, unsigned int* valid);

下面分析其数学证明,这里先定义一个encode与decode函数。encode函数将曲线上的一个点转为一个32bit长度的字符串,而decode函数将一段32bit长度的字符串转为一个曲线上的点,并检查是否在该曲线上。它们满足相互逆运算,有公式decode(encode(P))=P。下面的符号中a[b:c]表示a数组的b位到c位的所有值,PublicKey和SecretKey为32bit,Hash的结果是64bit。

SecretKey与PublicKey之间的关系

  • SecretKey = RandomNumber
  • PublicKey = encode(Hash(SecretKey) * G)

签名过程

  1. k = Hash(SecretKey)
  2. r = Hash(k[32:63] + Message)
  3. R = r * G
  4. Sig[0:31] = encode(R)
  5. h = Hash(Sig[0:31] + PublicKey + Message)
  6. S = r - kh
  7. Sig[32:63] = S

验证过程

  1. A = decode(PublicKey)
  2. h = Hash(Sig[0:31] + PublicKey + Message)
  3. T = encode(Sig[32:63] * G + h * A)
  4. T =? Sig[0:31]

证明

T = encode(Sig[32:63] * G + h * A)
T = encode(SG + h * decode(PublicKey))
T = encode(SG + h * decode(encode(Hash(SecretKey) * G)))
T = encode(SG + h * Hash(SecretKey) * G)
T = encode(SG + hkG)
T = encode((r-kh)G + hkG)
T = encode(rG)
T = encode(R)
T = Sig[0:31]

证毕。

参考文献

  • FourQ: four-dimensional decompositions on a Q-curve over the Mersenne prime
  • SchnorrQ: Schnorr signatures on FourQ
  • Twisted Edwards Curves
  • Twisted Edwards Curves Revisited

Search

    Table of Contents