椭圆曲线密码的C语言实现

Question

我试图解密素域上椭圆曲线的一组发送点(kB，Pm+k.Pb)。然而，我却得到了错误的结果。我猜是点减法出了问题。有人能帮忙吗？

我遵循了执行ECC的所有程序，如达雷尔·汉克森、阿尔弗雷德·梅内泽斯和斯科特·范斯通在书“椭圆曲线密码学指南”中所述。根据这些，我编写了代码并测试了add()和sclr_mult()似乎运行良好的函数。然而，我似乎无法正确解密消息。我怀疑我在点减部分搞砸了。这个程序是作为概念的证明，而不是实际的实现，所以我把a、b和p的值作为小数字。目前我并不真正关心这个过程的优化，不过一旦我开始工作，我就会研究这个问题。我以点(0,0)作为起始点，并修改了add()。我非常感谢你能帮助我完成这项工作，并提出其他建议。请随意要求完整的代码。我可以寄给你作进一步的检查。谢谢。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

//Information about the curve and finite field

int a=4;//coefficient for elliptic curve
int b=20;//coefficient for elliptic curve
int p=29;//prime number to provide finite field

int points[1000][2];//to store a set of points satisfying the curve

//Information required for Encryption and Decryption

//Private Information
int PrivKey=11;//Private Key of Receiver

//Public Information
int PubKey[2]={0,0};//Public key of Receiver
int random=11;//Random Number required for Encoding
int Pbase[2]={0,0};//Base point for all operations

//Encrypted Point
int Enc[4]={0,0,0,0};

//Functions Used
int * sclr_mult(int k,int point[2]);
int * add(int A[2],int B[2]);
int inverse(int num);
int * encode(int m,int Pb[2],int random,int Pbase[2]);//(Message,Public Key)
int * genKey(int X,int P[2]);//(Private Key,Base Point)
int decode(int Enc[4],int PrivKey);//(Encrypted Message, Private key of the Receiver) Outputs Message
void generate();

int main()
{
    int *temp;

    generate();
    Pbase[0]=points[5][0];//Deciding the base point here
    Pbase[1]=points[5][1];

    temp=genKey(PrivKey,Pbase);
    PubKey[0]=*temp;
    PubKey[1]=*(temp+1);
    printf("\nThe Public Key is (%d,%d)\n",PubKey[0],PubKey[1]);

    int message[2];
    message[0]=points[5][0];
    message[1]=points[5][1];
    printf("The message point is (%d,%d)\n",message[0],message[1]);

    int P[2];
    temp=sclr_mult(random,Pbase);
    P[0]=*temp;
    P[1]=*(temp+1);

    int Q[2];
    temp=sclr_mult(random,PubKey);
    Q[0]=*temp;
    Q[1]=*(temp+1);

    int R[2];
    temp=add(message,Q);
    R[0]=*temp;
    R[1]=*(temp+1);

    printf("The encrypted point is [(%d,%d),(%d,%d)]\n",P[0],P[1],R[0],R[1]);

    temp=sclr_mult(PrivKey,P);
    int O[2];
    O[0]=*temp;
    O[1]=p-*(temp+1);

    temp=add(R,O);
    O[0]=*temp;
    O[1]=*(temp+1);
    printf("The message point is (%d,%d)\n",O[0],O[1]);
    return 0;
}

int * sclr_mult(int k,int P[2])//using LSB first algorithm
{
    int *temp,i;
    int *Q = calloc(2,sizeof(int));
    Q[0]=0;
    Q[1]=0;
    for(i=31;i>=0;i--)
    {
        if((k>>i)&1)
            break;
    }
    for(int j=0;j<=i;j++)
    {
        if((k>>j)&1)
        {
            temp=add(Q,P);
            Q[0]=*temp;
            Q[1]=*(temp+1);
        }
        temp=add(P,P);
        P[0]=*temp;
        P[1]=*(temp+1);
    }
    return Q;
}

int * add(int A[2],int B[2])
{
    int *C = calloc(2,sizeof(int));
    int x=0;
    if (A[0]==0 || A[1]==0)
    {
        return B;
    }
    if (B[0]==0 || B[1]==0)
    {
        return A;
    }
    if (A[1]==(p-B[1]))
    {
        return C;
    }
    if ((A[0]==B[0]) && (A[1]==B[1]))
    {
        x=((3*(A[0]*A[0]))+a)*inverse(2*A[1]);
        C[0]=((x*x)-(2*A[0]))%p;
        C[1]=((x*(A[0]-C[0]))-A[1])%p;
        //C[0]=((A[0]*A[0])%p+(b*inverse(A[0]*A[0]))%p)%p;//For Binary Curves
        //C[1]=((A[0]*A[0])%p+((A[0]+(A[1]*inverse(A[0]))*C[0]))%p+(C[0])%p)%p;//For Binary Curves
    }
    else
    {
        x=(B[1]-A[1])*inverse(B[0]-A[0]);
        C[0]=((x*x)-(A[0]+B[0]))%p;
        C[1]=((x*(A[0]-C[0]))-A[1])%p;
        //C[0]=((((A[1]+B[1])*inverse(A[0]+B[0]))*((A[1]+B[1])*inverse(A[0]+B[0])))%p + ((A[1]+B[1])*inverse(A[0]+B[0]))%p + A[0]%p + B[0]%p + a%p)%p;//For Binary Curves
        //C[1]=((((A[1]+B[1])*inverse(A[0]+B[0]))*(A[0]+C[0]))+C[0]+A[1])%p;//For Binary Curves
    }
    if (C[0]<0)
        C[0]=p+C[0];
    if (C[1]<0)
        C[1]=p+C[1];
    return C;
}
int inverse(int num)
{
    int i=1;
    if (num<0)
        num=p+num;
    for (i=1;i<p;i++)
    {
        if(((num*i)%p)==1)
            break;
    }
    //printf("inverse=%d,%d",i,num);
    return i;
}

void generate()
{
    int rhs,lhs,i=0;//to find set of points that satisfy the elliptic curve
    for(int x=0;x<p;x++)
    {
        rhs=((x*x*x)+(a*x)+b)%p;
        for(int y=0;y<p;y++)
        {
            lhs=(y*y)%p;
            if (lhs==rhs)
            {
                points[i][0]=x;
                points[i][1]=y;
                i+=1;
            }
        }
    }
    printf("\nNumber of points found on the curve is %d \n",i);
    for(int k=0;k<i;k++)
    {
        printf("%d(%d,%d)\n",(k),points[k][0],points[k][1]);
    }
}

int * genKey(int X,int P[2])
{
    int *temp;
    int *Q = calloc(2,sizeof(int));
    temp=sclr_mult(X,P);
    Q[0]=*temp;
    Q[1]=*(temp+1);
    return Q;
}

我不会犯错误。然而，我并没有得到我期望的结果。

Answer 1

sclr_mult方法通常会改变第二个参数。在当前示例中，Pbase在

temp = genKey(PrivKey, Pbase); // calls sclr_mult

值(2,23)，然后在

temp = sclr_mult(random, Pbase);

值(8,19)。由于Pbase是椭圆曲线上的参考点，这就是错误结果的原因。解决方案可以是传递Pbase的副本，也可以相应地修改sclr_mult。通过此更改，当前的示例工作如下：

The public key is                               (16,27)
The message point is                            (2,23)
The shared secret (random * PubKey) is          (6,17)
The encrypted point is                          [(16,27),(16,27)]
The shared secret (PrivKey * P) is              (6,17)
The inverse of the shared secret is             (6,12)
The decrypted message point is                  (2,23)

以下几点也是有问题的，但在当前示例中不会导致错误：

• add方法返回大小写A = (0,0)，B != (0,0)返回结果B，这意味着(0,0)表示PAI (指向无穷大，参见这里，第17-19页)。(0,0)不是最好的选择，因为也有一些曲线(b = 0)将(0,0)作为正则点。然而，对于当前曲线(b = 7)，(0,0)不是一个正则点，因此可以定义为PAI。 注意:如果一个非(0,0)的点被用作PAI (例如(p,p))，那么Q必须在sclr_mult中被初始化，其点代表PAI！
• add方法必须考虑以下三种情况(这里，第20页)： PAI + PAI = PAI A+ PAI =A PAI +B=B 此外，必须考虑垂直割线(点加法)和切线(点倍)的两种情况(这里，第3页)： (B )%p == 0垂直割线A1 %p == 0垂直切线 add方法可以修改如下，以考虑这些情况： *加上(int A2，int B2) { int *C =( int *)calloc(2，sizeof( int ))；int x= 0；if (isPAI(A) & isPAI(B)) // PAI + PAI = PAI { return (C)；} if (isPAI(A)) // PAI +B=B{ return；}如果(isPAI( B) ) // A+ PAI =A{返回A；}则((A == B)& (A1 == B1)) { //点加倍如果(A1 %p == 0) //垂直切线{返回getPAI(C)；} //如在当前代码// .} else { //点式加法如果((B - A) %p == 0) //垂直割线{返回getPAI(C)；} //在当前代码中// .} //在当前代码// .} 使用 布尔isPAI( int * point ) {返回点== 0 && point1 == 0；}int* getPAI(int * point ) {point= 0；point1 = 0；返回点；}
• 示例：a = 1, b = 7, p = 17，(这里) 点数： (1,3)，(1,14)，(2,0)，(5,1)，(5,16)，(6,5)，(6,12)，(7,0)，(8,0)，(12,8)，(12,9) 现行add方法的结果： (1,3) + (1,3) = (6,5) (6,5) + (1,3) = (2,0) (2,0) + (1,3) = (1,3) 修改后的add-method结果： (1,3) + (1,3) = (6,5) (6,5) + (1,3) = (2,0) (2,0) + (1,3) = (6,12) (6,12)+ (1,3) = (1,14) (1,14)+ (1,3) = (0,0) // PAI (0,0) + (1,3) = (1,3) .