Question

Я пытаюсь расшифровать отправленный набор точек (кБ, 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;
}

Я не получаю ошибок.Однако я не получаю ожидаемого результата.

Topaco · Answer 1 · 30 июня 2019

Метод sclr_mult обычно изменяет 2-й параметр.В текущем примере 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)

Следующие пункты также проблематичны, но не вызывают ошибку в примере current :

Метод 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[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, ( здесь )

Очки:

(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

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

1 Ответ

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Реализация криптографии на эллиптических кривых в C

Пожалуйста, войдите или зарегистрируйтесь чтобы ответить на этот вопрос.

1 Ответ

Пожалуйста, войдите или зарегистрируйтесь что бы добавить комментарий.

Похожие темы