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

• 04-21-2013
jowin_c
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?
• 04-21-2013
Salem
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).

>
• 04-21-2013
jowin_c
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.
• 04-21-2013
Salem
You really should try pressing the review button before pressing submit.