C 中椭圆曲线密码学的实现

Question

我正在尝试解密素数域上椭圆曲线的一组已发送点 (kB, Pm+k.Pb)。但是，我得到了错误的结果。我的猜测是点减法有问题。有人可以帮忙吗？

我遵循了 Darrel Hankerson、Alfred Menezes 和 Scott Vanstone 合着的 "Guide to Elliptic Curve Cryptography" 书中描述的实施 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 有 in

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)

下面几点也是有问题的，但是不要在current的例子中造成错误：

加法returns对于caseA = (0,0)和B != (0,0)的结果B，也就是说(0,0)表示PAI（指向无穷远，参见 here，第 17 - 19 页）。 (0,0)不是最好的选择，因为还有曲线(b = 0) 以 (0,0) 作为常规点。但是对于当前曲线(b = 7)，(0,0)不是一个规则点，所以可以定义为PAI。

注：如果用(0,0)以外的点作为PAI（如(p,p)），Q必须在sclr_mult初始化用代表 PAI 的点！

add方法必须考虑以下三种情况(here, p. 20):

PAI + PAI = PAI   
A + PAI = A    
PAI + B = B

此外，垂直正割的两种情况（point addition) and tangent (point doubling) must be taken into account (here，p.3）：

(B[0] - A[0]) % p == 0    vertical secant     
A[1] % p == 0             vertical tangent

add 方法可以修改如下以考虑这些情况：

int * add(int A[2], int B[2])
{
    int *C = (int *)calloc(2, sizeof(int));
    int x = 0;

    if (isPAI(A) && isPAI(B))  // PAI + PAI = PAI
    {
        return getPAI(C);
    }
    else if (isPAI(A))         // PAI + B = B
    {
        return B;
    }
    else if (isPAI(B))         // A + PAI = A
    {
        return A;
    }
    else if ((A[0] == B[0]) && (A[1] == B[1]))
    {
        // Point doubling

        if (A[1] % p == 0)              // Vertical tangent
        {
            return getPAI(C);
        }

        // as in current code
        // ... 
    }
    else
    {
        // Point addition

        if ((B[0] - A[0]) % p == 0)    // Vertical secant
        {
            return getPAI(C);
        }

        // as in current code
        // ... 
    }

    // as in current code
    // ... 
}

和

bool isPAI(int *point) 
{
    return point[0] == 0 && point[1] == 0;
}

int* getPAI(int *point) 
{
    point[0] = 0;
    point[1] = 0;
    return point;
}

示例：a = 1, b = 7, p = 17、(here)

积分：

(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-方法的结果：

(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)
...

C 中椭圆曲线密码学的实现

Implementation of Elliptic Curve Cryptography in C

c

cryptography

elliptic-curve