Like Tree1Likes
  • 1 Post By Salem

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

This is a discussion on Point operations on an elliptic curve in a prime field in c within the C Programming forums, part of the General Programming Boards category; I am trying to write a program to perform point operations on a elliptic curve in a prime field I ...

  1. #1
    Registered User
    Join Date
    Apr 2013
    Posts
    2

    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?

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,344
    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).

    >
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Apr 2013
    Posts
    2
    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[i1%3]isinverseofa
    //y[i1%3]isinverseofb
    if(x[(i-1)%3]<0)
    returnx[(i-1)%3]+263;
    else
    //x[i1%3]isinverseofa
    //y[i1%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. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,344
    You really should try pressing the review button before pressing submit.
    AndiPersti likes this.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 02-06-2011, 02:34 AM
  2. nonlinear curve fitting with a fixed point
    By zeebo17 in forum C Programming
    Replies: 1
    Last Post: 01-18-2011, 04:10 PM
  3. Replies: 6
    Last Post: 07-15-2009, 10:50 AM
  4. Replies: 2
    Last Post: 06-07-2009, 08:49 AM
  5. Floating point operations
    By kjc197 in forum C Programming
    Replies: 5
    Last Post: 02-08-2003, 05:44 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21