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

1. ## 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)
{
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);
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);
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?

2. One thing, your indentation is all over the place.
SourceForge.net: Indentation - cpwiki

Two, you don't give a specific example of failure.
For example, saying " k=300,g=400, h=500 produces x, but I expected y" would give us something specific to work on.
We could spend hours guessing what you mean by "large numbers".

For all we know, your issue is with cryptographically large numbers (as opposed to machine representable large numbers).

>

3. 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_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);
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);
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)
{
xk=sn.a;
yk=sn.b;
m++;

}
s1.a=xk;
s1.b=yk;
returns1;
}
{
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.

4. You really should try pressing the review button before pressing submit.