Thread: Point operations on an elliptic curve in a prime field in c

I am trying to write a program to perform point operations on a elliptic curve in a prime field I am using the standard formulaes for point additions and doubling in my code and these operations are performed by functions that are called but I am getting output for certain points but not all so please help me to fix the problem that are present in this code.

Code:

structure point_multiply(int x, int y, int k )
    {
    int xk;
    int yk,m;
    xk=x;
    yk=y;
    m=1;
    int xL,yL,s,e;
    e=findInverse((2*yk),211);
    if((((3*(xk*xk))*e)% 211)>0)
    {s = (((3*(xk*xk))*e)% 211);

    }
    else
        s=(((3*(xk*xk))*e)% 211)+ 211;
    if((((s*s)- (2*xk)) % 211)>0)
    {xL=(((s*s)- (2*xk)) % 211);
    }
            else
            xL=(((s*s)- (2*xk)) % 211) + 211;
            if(((-yk+ s*(xk-xL)) % 211) > 0)
            yL=(-yk+ s*(xk-xL)) % 211;
            else
            yL=(-yk+ s*(xk-xL)) % 211 + 211;
            xk=xL;
            yk=yL;
            m=m+1;

    while(k>m)
    {
        sn=point_addition(xk,yk,x,y);
        xk=sn.a;
        yk=sn.b;
        m++;


    }
    s1.a=xk;
    s1.b=yk;
    return s1;
}

    structure point_addition(int x1, int y1, int x2, int y2)
    {
    int s,xL,yL;
    if((x1-x2)!=0)
    {
        if ( x1 == 0 && y1 == 0 )
        {
            xL = x2;
            yL = y2;
            s7.a=xL;
            s7.b=yL;
            return s7;
        }
        if ( x2 == 0 && y2 == 0 )
        {
            xL = x1;
            yL = y1;
            s7.a=xL;
            s7.b=yL;
            return s7;
        }
        if ( y1 == -y2 )
        {
            xL = yL = 0;
            s7.a=xL;
            s7.b=yL;
            return s7;
        }
        l=findInverse((x1-x2),211);
        if ((((y1-y2)*l) % 211)>=0)
              s=((((y1-y2)*l) % 211));
        else
              s=(((y1-y2)*l) % 211) + 211;
        if ((((s*s)-(x1+x2)) % 211)>0)
              xL= (((s*s)-(x1+x2)) % 211) ;
        else
              xL= (((s*s)-(x1+x2)) % 211) + 211;
        if(((-y1+s*(x1-xL)))>=0)
              yL= ((-y1+s*(x1-xL)) % 211);
        else
              yL= ((-y1+s*(x1-xL)) % 211) + 211;
    }
    else

    {
        xL= 0 ;
        yL= 0;

    }

    s7.a= xL;
    s7.b= yL;

    return s7 ;
}

    int findInverse(int a, int b)
    {
     int x[3];
     int y[3];
     int quotient  = a / b;
     int remainder = a % b;
     x[0] = 0;
     y[0] = 1;
     x[1] = 1;
     y[1] = quotient * -1;
     int i = 2;
     for (; (b % (a%b)) != 0; i++)
     {
      a = b;
      b = remainder;
      quotient = a / b;
      remainder = a % b;
      x[i % 3] = (quotient * -1 * x[(i - 1) % 3]) + x[(i - 2) % 3];
      y[i % 3] = (quotient * -1 * y[(i - 1) % 3]) + y[(i - 2) % 3];
     }

     //x[i — 1 % 3] is inverse of a
     //y[i — 1 % 3] is inverse of b
     if(x[(i - 1) % 3]<0)
    return x[(i - 1) % 3]+211;
     else
     //x[i — 1 % 3] is inverse of a
     //y[i — 1 % 3] is inverse of b
     return x[(i - 1) % 3];
       }

Edited and added main c code which uses these function to perform elliptic curve cryptography

Code:

    int main()
    {
    int y,z=0,x=2,i[200],j[200],h=0,g,k;
        while(x<200)
        {
            y=(x*x*x)-4;
            z=modulo(y,211);
            if(z!=0)
            {
                i[h]=x;
                j[h]=z;
                s[h].a=i[h];
                s[h].b=j[h];
                s[h+1].a=i[h];
                s[h+1].b=(211 - j[h]);
                printf("\nh=%d X= %d Y= %d \nh=%d X= %d Y= %d",h,s[h].a,s[h].b,h+1,s[h+1].a,s[h+1].b);
                h=h+2;
            }
            x++;

        }
        printf("The total no of points we have on our elliptic curve for cryptography is %d",h-1);
        x=5;
        y=11;
        printf("\n %d %d\n",x,y );
        printf("\nEnter A number between 0 and   the private key");
        scanf("%d",&k);
        s2=point_multiply(x,y,k);
       printf("\n The public key is \n %d %d \n  ",s2.a,s2.b );
       printf("Enter a RANDOM number to generate the cipher texts");
    scanf("\n%d",&g);
    s3= point_multiply(x,y,g);
    s4=point_multiply(s2.a,s2.b,g );
    label:
    printf("\n Enter a number to send");
    scanf("%d",&h);
    s6=point_addition(s4.a,s4.b,s[h].a,s[h].b);
    printf("The points to be sent are X= %d Y=%d",s[h].a,s[h].b);
    printf(" \n X= %d Y=%d\n X = %d Y= %d ",s3.a,s3.b,s6.a,s6.b);
    //RECIEVER
    s8=point_multiply(s3.a,s3.b,k);
    s9=point_addition((s8.a) ,-((s8.b)%211),s6.a,s6.b);
    printf(" The decrypted points are \n %d %d",s9.a,s9.b);
            printf("\n If you have more no to send press 1 else press 0");
            scanf("\n %d", &x1);
            if(x1==1)
                goto label;
            else
                return 0;


 }

s1, s2, s3 etc are structures which hold a 2 integers which act as x and y co-ordinates
I am getting output by entering k=3,g=4, h=5 and many other cases mostly with small numbers but not for larger numbers. What could be wrong with the code?

I couldn't find the edit button so I am posting the indented version of the code here

Code:

#include<stdlib.h>
#include<stdio.h>
#include<math.h>
longintxp=0,yp=0,x1,f,l;
longintmodulo(longinta,longintp);
longintfindInverse(longinta,longintb);
typedefstruct
{
longinta;
longintb;
}structure;
structures1,s2,s3,s4,s5,s6,s7,s[143*2],s8,s9,sn;
structurepoint_addition(longintx,longinty,longintx2,longinty2);
structurepoint_multiply(longintx,longinty,longintk);
intmain()
{
longinty,z=0,x=0,i[260],j[260],h=0,g,k;
while(x<263)
{
y=(x*x*x+x+1);
z=modulo(y,263);
if(z!=0)
{
i[h]=x;
j[h]=z;
s[h].a=i[h];
s[h].b=j[h];
s[h+1].a=i[h];
s[h+1].b=(263-j[h]);
printf("\nh=%ldX=%ldY=%ld\nh=%ldX=%ldY=%ld",h,s[h].a,s[h].b,h+1,s[h+1].a,s[h+1].b);
h=h+2;
}
x++;

}
printf("\nThetotalnoofpointswehaveonourellipticcurveavailableforencryptingpointsis%ld\n",h-1);
x=148;
y=27;
printf("\nThegeneratorpointsare%ld%ld\n",x,y);
printf("\nEnteranumberbetween1and255whichwouldbetheprivatekey\n");
scanf("%ld",&k);
s2=point_multiply(x,y,k);
printf("\nThepublickeyis\n%ld%ld\n",s2.a,s2.b);
printf("EnteraRANDOMnumbertogeneratetheciphertexts");
scanf("\n%ld",&g);
s3=point_multiply(x,y,g);
s4=point_multiply(s2.a,s2.b,g);
label:
printf("\nEnteranumbertosend");
scanf("%ld",&h);
s6=point_addition(s4.a,s4.b,s[h].a,s[h].b);
printf("ThepointstobesentareX=%ldY=%ld",s[h].a,s[h].b);
printf("\nX=%ldY=%ld\nX=%ldY=%ld",s3.a,s3.b,s6.a,s6.b);
//RECIEVER
s8=point_multiply(s3.a,s3.b,k);
s9=point_addition((s8.a),-((s8.b)%263),s6.a,s6.b);
printf("Thedecryptedpointsare\n%ld%ld",s9.a,s9.b);
printf("\nIfyouhavemorenotosendpress1elsepress0");
scanf("\n%ld",&x1);
if(x1==1)
gotolabel;
else
return0;


}
longintmodulo(longinta,longintp)
{
longintx=0;
longintm=a%p;

if(1){

while((((x*x)%p)!=m))
{
if(x<263){

x++;}
else
{
return0;}

}
returnx;
}


else
returna%p;
}
structurepoint_multiply(longintx,longinty,longintk)
{
longintxk;
longintyk,m;
xk=x;
yk=y;
m=1;
longintxL,yL,s,e;
e=findInverse((2*yk),263);
if((((3*(xk*xk)+1)*e)%263)>0)
{s=(((3*(xk*xk)+1)*e)%263);

}
else
s=(((3*(xk*xk)+1)*e)%263)+263;
if((((s*s)-(2*xk))%263)>0)
{xL=(((s*s)-(2*xk))%263);
}
else
xL=(((s*s)-(2*xk))%263)+263;
if(((-yk+s*(xk-xL))%263)>0)
yL=(-yk+s*(xk-xL))%263;
else
yL=(-yk+s*(xk-xL))%263+263;
xk=xL;
yk=yL;
m=m+1;

while(k>m)
{
sn=point_addition(xk,yk,x,y);
xk=sn.a;
yk=sn.b;
m++;


}
s1.a=xk;
s1.b=yk;
returns1;
}
structurepoint_addition(longintx1,longinty1,longintx2,longinty2)
{
longints,xL,yL;
if((x1-x2)!=0)
{
if(x1==0&&y1==0)
{
xL=x2;
yL=y2;
if(xL<0)
xL=xL+263;
if(yL<0)
yL=yL+263;
s7.a=xL;
s7.b=yL;
returns7;
}
if(x2==0&&y2==0)
{
xL=x1;
yL=y1;
if(xL<0)
xL=xL+263;
if(yL<0)
yL=yL+263;

s7.a=xL;
s7.b=yL;
returns7;
}
if(y1==-y2)
{
xL=0;
yL=0;
s7.a=xL;
s7.b=yL;
returns7;
}
if(x1==x2)
{
xL=x1;
yL=y1;
s7.a=xL;
s7.b=yL;
returns7;
}
l=findInverse((x1-x2),263);
if((((y1-y2)*l)%263)>=0)
s=((((y1-y2)*l)%263));
else
s=(((y1-y2)*l)%263)+263;
if((((s)-(x1+x2))%263)>0)
xL=(((s)-(x1+x2))%263);
else
xL=(((s)-(x1+x2))%263)+263;
if(((-y1+s*(x1-xL)))>=0)
yL=((-y1+s*(x1-xL))%263);
else
yL=((-y1+s*(x1-xL))%263)+263;
}
else

{
xL=0;
yL=0;

}

s7.a=xL;
s7.b=yL;

returns7;
}
longintfindInverse(longinta,longintb)
{
longintx[3];
longinty[3];
longintquotient=a/b;
longintremainder=a%b;

x[0]=0;
y[0]=1;
x[1]=1;
y[1]=quotient*-1;

longinti=2;
for(;(b%(a%b))!=0;i++)
{
a=b;
b=remainder;
quotient=a/b;
remainder=a%b;
x[i%3]=(quotient*-1*x[(i-1)%3])+x[(i-2)%3];
y[i%3]=(quotient*-1*y[(i-1)%3])+y[(i-2)%3];
}

//x[i—1%3]isinverseofa
//y[i—1%3]isinverseofb
if(x[(i-1)%3]<0)
returnx[(i-1)%3]+263;
else
//x[i—1%3]isinverseofa
//y[i—1%3]isinverseofb
returnx[(i-1)%3];
} 

The input I am giving is 51 in the output window and the expected answer is <3,89> but I am getting <147,253> The sent points and decrypted points should be the same I guess there is a problme with the point multiplication code .. Please help me in telling how I can solve the probable errors in point multiplication function.