c - ECC 反模奇异时间执行

Question

大家好，请原谅我的英语我开发了一个大整数函数 c :

#ifndef __BIGINTEGER_H
#define __BIGINTEGER_H
#include <stdlib.h>
#include<stdint.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include "biginteger.h"
#define Maxbyte 19
typedef struct { uint32_t num[Maxbyte];
                 char sign ;
                 uint8_t lastblock ;} big_integer;


void init_biginteger(char *string_hex_number, big_integer *a);
big_integer Strassen_Multiplication(big_integer *a , big_integer *b );
big_integer add_biginteger(big_integer *a,big_integer *b );
big_integer sub_biginteger (big_integer *a,big_integer *b);
char  ABS_compare(big_integer *a , big_integer *b);
 void Lsh(big_integer *a , int shift, int bits);
 char div_mod(big_integer *a,big_integer *b,big_integer *Q,big_integer *R);
 char modulo(big_integer *a,big_integer *b,big_integer *c);
 char invers_modulo(big_integer *a ,big_integer *b,big_integer *c);
 void Rsh(big_integer *a , int shift,int bits);
  char zero(big_integer *a);
#endif

这是我的功能:

static void char_to_hex(char s , uint32_t *byte){

switch(s){
    case '0' : *byte = 0x0000000; break;
    case '1' : *byte = 0x0000001; break;
    case '2' : *byte = 0x0000002; break;
    case '3' : *byte = 0x0000003; break;  
    case '4' : *byte = 0x0000004; break; 
    case '5' : *byte = 0x0000005; break; 
    case '6' : *byte = 0x0000006; break; 
    case '7' : *byte = 0x0000007; break; 
    case '8' : *byte = 0x0000008; break; 
    case '9' : *byte = 0x0000009; break;
    case 'A' : *byte = 0x000000a; break;
    case 'B' : *byte = 0x000000b; break;
    case 'C' : *byte = 0x000000c; break; 
    case 'D' : *byte = 0x000000d; break;
    case 'E' : *byte = 0x000000e; break;
    case 'F' : *byte = 0x000000f; break;

} 
}
static uint64_t get_cary_add(uint64_t a , uint64_t b ) {
    uint64_t c,c1,max=0xFFFFFFFFFFFFFFFF;
    if(a>b){ c=a;
    c1=b;
    }else{c=b;
    c1=a;
    }
    if(max-c<c1){return 1;}else{


        return 0;}
}

static uint64_t safe_add64(uint64_t carry,uint64_t a, uint64_t b){
    if(carry==0){
        return a+b;}else{
            uint64_t a1=0,b1=0,c1=0;
            uint64_t a2=a,b2=b,s=0;
        a1= (a2 & 0x8000000000000000)>>63;
        b1= (b2 & 0x8000000000000000)>>63;
        a2=a2 & 0x7FFFFFFFFFFFFFFF;
        b2=b2 & 0x7FFFFFFFFFFFFFFF;
        s= a2+b2;
        c1=(uint64_t)(s)>>63;
        s=s & 0x7FFFFFFFFFFFFFFF;
        c1=(uint64_t) (a1+b1+c1)<<63;
        c1= (uint64_t)(s)| c1  ;
        return c1;

        }

    }

static uint32_t safe_add32(uint32_t carry,uint32_t a, uint32_t b){

    if(carry==0){
        return a+b;}else{
        uint32_t a1=0,b1=0,c1=0,s=0;
         uint32_t a2=a,b2=b;
        a1= (uint32_t) (a2 & 0x80000000) >> 31;
        b1= (uint32_t)((b2 & 0x80000000) >> 31);
        a2=a2 & 0x7FFFFFFF;
        b2=b2 & 0x7FFFFFFF;
        s= a2+b2;
        c1=(uint32_t)(s)>>31;
        s= s &  0x7FFFFFFF;
        c1=(uint32_t)(a1+b1+c1)<<31;
        c1= (uint32_t)(s)| c1  ;
        return c1;

        }

    }




static uint32_t get_carry_add(uint32_t a , uint32_t b ) {
    uint32_t c,c1,max=0xFFFFFFFF;
    if(a>b){ c=a;
    c1=b;
    }else{c=b;
    c1=a;
    }
    if(max-c<c1){return 1;}else{


        return 0;}
}

char  ABS_compare(big_integer *a , big_integer *b){
    int i=a->lastblock,k=-1;
    if(a->lastblock>b->lastblock){return 1;}
    else if (b->lastblock > a->lastblock){return 2;} 
    else{  

        while(k==-1){
        if(a->num[i]>b->num[i]){k=1;}
        else if(b->num[i]>a->num[i]){k=2;}
        else if( i==0 && k==-1){k=0;}
        i=i-1;
        }
         }
    return k;
}

void Lsh(big_integer *a , int shift,int bits){
    int i=0,j=0,k;
    //80000000;
    uint32_t temp=0;
    i=bits/32-1;
    k=i;
    for(j=0;j<shift;j++){

    if(i==0){
    a->num[0]=(a->num[0]<<1);

    }else{
   i=i-1;
    a->num[i+1]=(a->num[i+1]<<1);
    for(;i>=0;i--){
        temp=(a->num[i] & 0x80000000);
        temp=uint32_t(temp>>31);
        a->num[i]=(a->num[i]<<1);

        a->num[i+1]= a->num[i+1] | temp;

    }
    }

    }
    j=0;
    while(a->num[k]==0 && j==0){
        if(k!=0){
            k=k-1;}else {j=1;}

    }
    a->lastblock=k;

}


void Rsh(big_integer *a , int shift,int bits){
    int i=0,j=0,k=0;
    //80000000;
    uint32_t temp=0;
    i=bits/32-1;

    for(j=0;j<shift;j++){

    if(i==0){
    a->num[0]=(a->num[0]>>1);

    }else{

    //a->num[i+1]=(a->num[i+1]<<1);
    for(k=0;k<=i;k++){
        temp=(a->num[k+1] & 0x00000001);
        temp=uint32_t(temp<<31);
        a->num[k]=(a->num[k]>>1);

        a->num[k]= a->num[k] | temp;

    }
    }

    }
    j=0;
    while(a->num[k]==0 && j==0){
        if(k!=0){
            k=k-1;}else {j=1;}

    }
    a->lastblock=k;

}



void init_biginteger(char *string_hex_number, big_integer *a){
int i = strlen(string_hex_number)-1;
memset(a->num,NULL,Maxbyte*sizeof(uint32_t));
uint32_t byte=0;
int j=0,k=0;
for(i;i>=0;i--){
    if(string_hex_number[i]=='-'){a->sign=-1;}else{
    char_to_hex(string_hex_number[i],&byte);
  //  byte = string_hex_number[i] - 0x30;
    byte = (byte << j);
    a->num[k]=byte | a->num[k];
    j=j+4;
    if(j==32){
    k=k+1;
    j=0;
    }
    }

    }
if(string_hex_number[0]!='-') {a->sign = 1;}
if(k!=0){
    if(a->num[k]==0){k=k-1;}}

a->lastblock = k;
}

big_integer add_biginteger(big_integer *a,big_integer *b ){

    big_integer tempa,tempb,result,tempo;
    memset(result.num,NULL,Maxbyte*sizeof(uint32_t));
    tempa=*a;
    tempb=*b;
    int k,i;
    uint32_t carry=0,carry1=0,carry2=0;
    if(tempa.lastblock>tempb.lastblock){
        k=tempa.lastblock+1;
    }else { k=tempb.lastblock+1;}

    if(tempa.sign == tempb.sign){
        for(i=0;i<=k;i++){
            carry=(uint32_t)get_carry_add(tempa.num[i],tempb.num[i]);
            tempo.num[i]=safe_add32(carry,tempa.num[i],tempb.num[i]);
            //tempo.num[i]=(uint32_t)tempa.num[i] + tempb.num[i];
            carry2=(uint32_t)get_carry_add(tempo.num[i],carry1);
            //carry=+carry;
            result.num[i] = safe_add32(carry2, tempo.num[i] , carry1);
            carry1=carry2+carry;
            //carry1=carry;
        //carry1=carry+ get_carry_add(result.num[i],carry);

        } 

        while(result.num[i]==0){ i=i-1;  }
        result.lastblock=i;
        result.sign = tempa.sign;
        return result;
    }else if (tempb.sign==-1){
        tempb.sign=1;
        result = sub_biginteger(&tempa,&tempb);
        return result;
        }else {
            tempa.sign=1;
            result = sub_biginteger(&tempb,&tempa);
        return result;
        }





}


big_integer sub_biginteger (big_integer *a,big_integer *b){
    big_integer result,tempa,tempb;
    memset(result.num,NULL,Maxbyte*sizeof(uint32_t));
    tempa = *a;
    tempb=*b;
    int i,k;
    if(b->sign==-1 && a->sign==1){
        tempb.sign=1;
        result=add_biginteger(&tempa,&tempb);
        return result;  
    }else if(a->sign==-1 && b->sign==1){
        tempb.sign=-1;
        result=add_biginteger(&tempa,&tempb);
        return result;
    }else{


    k= ABS_compare(&tempa,&tempb);
    if(k==0){          
        result.lastblock=0;
        result.sign=1;
        return result;
    }else if(k==1){
        result.sign=1;
    }else { 
        result=tempb;
        tempb=tempa;
        tempa=result;

        result.sign=-1;}

    uint64_t tempo,temp,carry=0;
    for(i=0;i<tempa.lastblock+1;i++){
        if((uint64_t)tempa.num[i]< (uint64_t) (tempb.num[i]+carry)){

        temp=(uint64_t)tempa.num[i];
        tempo=(uint64_t)tempb.num[i]+carry;
        temp=(uint64_t)(temp+0x100000000 - tempo);
        result.num[i]=(uint32_t)temp;

        carry=1;
        }else{
            result.num[i]=tempa.num[i]-tempb.num[i]-carry;      
        carry=0;
        }}

    }

    while(result.num[i]==0){i=i-1;}
    result.lastblock=i;
    return result;

}



big_integer Strassen_Multiplication(big_integer *a , big_integer *b ){
    big_integer result ;
    big_integer tempa = *a;
    big_integer tempb = *b;
    uint32_t rest=0;
    uint64_t div=0,carry=0,carry1;
    int k,k1,i,j ,j2;
    if(a->lastblock > b->lastblock){ 
        k =tempa.lastblock+1;
        k1=tempb.lastblock+1;
        result= tempa;
        tempa=tempb;
        tempb=result;
    }else{
            k=tempb.lastblock+1;
            k1=tempa.lastblock+1;

        }

   uint64_t **arg=NULL;
   arg= (uint64_t ** ) calloc (k*2+3, sizeof(uint64_t *));
   if(arg==NULL){
   exit(1);
   }
for(i=0;i<k+3;i++){
    arg[i]= (uint64_t * ) calloc (k*2+3, sizeof(uint64_t));
  if(arg[i]==NULL){
   exit(1);
   }

}

j=0;

for(i=0;i<k1;i++){
    j2=0;

    for(j=i;j<k+i;j++){

        arg[i][j]=(uint64_t) tempb.num[j2]*tempa.num[i];
    // tab3[i][j]=arg3[i][j];
    j2=j2+1;
    }

}
memset(result.num,NULL,Maxbyte*sizeof(uint32_t));


for(j=0;j<(k1+k);j++){
for(i=0;i<k1;i++){
    carry=(uint64_t)carry+get_cary_add(arg[k+1][j],arg[i][j]  );
    arg[k+1][j]=(uint64_t)safe_add64 (carry,arg[i][j],arg[k+1][j]);

    }
carry1=get_cary_add(arg[k+1][j],div);
carry=carry+carry1;
arg[k+1][j]=(uint64_t)safe_add64(carry1,arg[k+1][j],div);
 div= (uint64_t) (arg[k+1][j] / 0x100000000) | (carry * 0x100000000) ;
 rest=(uint32_t)(arg[k+1][j] % 0x100000000);
 result.num[j]=(uint32_t)rest;
 carry=0;
}

result.sign = tempa.sign * tempb.sign;
while(result.num[j]==0 && j!=0){j=j-1;}
result.lastblock = j;
for(i=0;i<k*2+3;i++){
    free(arg[i]);}
free(arg);



    return result;
}







char div_mod(big_integer *a,big_integer *b,big_integer *Q,big_integer *R){
    int k;

    k=ABS_compare(a ,b);
    if(b->lastblock==0 && b->num[0]==0) {return -1;}
    else if(k==2){memset(R->num,NULL,Maxbyte*sizeof(uint32_t));
                  memset(Q->num,NULL,Maxbyte*sizeof(uint32_t));

                  Q->lastblock=0;
                  Q->sign=1;
                  *R=*a;
                  R->sign=a->sign;
                 }
    else if(k==0){memset(R->num,NULL,Maxbyte*sizeof(uint32_t));
                  memset(Q->num,NULL,Maxbyte*sizeof(uint32_t));
                  Q->num[0]=1;
                  Q->lastblock=0;
                  Q->sign = a->sign * b->sign;
                  R->sign=1;
                  R->lastblock=0;
                  R->num[0]=0;

    }

    else { memset(R->num,NULL,Maxbyte*sizeof(uint32_t));
           memset(Q->num,NULL,Maxbyte*sizeof(uint32_t));
           uint8_t lb=a->lastblock;
           big_integer tempa,tempb;
           tempa=*a;
           tempb=*b;
           tempb.lastblock = tempa.lastblock;
           R->lastblock = tempa.lastblock;
           Q->lastblock = tempa.lastblock;
           int i = tempa.lastblock,size = (lb+1)*32,j=0;

           uint32_t bits= 0x80000000,h;
           for(;i>=0;i--){
               for(j=31;j>=0;j--){
               Lsh(R,1,size);
               R->lastblock = lb;
               h=(tempa.num[i]<<(31-j));
               h=h>>31;
              // byte = byte & 0x01;
               R->num[0]=uint32_t(R->num[0] | h);
               if(ABS_compare(R ,&tempb)!=2){
               *R=sub_biginteger(R,&tempb );
               R->lastblock=lb;
               tempb.lastblock=lb;
               Q->num[i]=  Q->num[i] | ( bits>>(31-j));
               }
               }
           }
           Q->sign= a->sign * b->sign;
           R->sign= a->sign;
           j= lb;
           while(Q->num[j]==0 && j!=0){j=j-1;}
           Q->lastblock = j;
           j= lb;
           while(R->num[j]==0 && j!=0){j=j-1;}
           R->lastblock = j;


    }


return 1;
}


char modulo(big_integer *a,big_integer *b,big_integer *c){

    big_integer temp;
    char k;
    k=div_mod(a,b,&temp,c);
    if(k==-1){ return -1;}else{
        if(a->sign==-1){
            *c=add_biginteger(c ,b);}
    }
    return 1;

}

 char zero(big_integer *a){
    if(a->sign==-1){ return -1;       }else {
        /*int i=0,j=0;
        while(i!=a->lastblock && j==0){
            if(a->num[i]!=0){j=1;}
            i=i+1;

        }
        if(j=1){return 1;}else{
            return 0;}*/
        if(a->lastblock >0){return 1;}else{
            if(a->num[0]==0){return 0;}else{
                return 1;}
        }


}
}

 char invers_modulo(big_integer *a ,big_integer *b,big_integer *c){

    if( b->sign==-1){ return -1;}

     big_integer tempa=*a,tempb=*b;
    tempa.sign=1;
     big_integer d,t,x,v,tempo,d1;

    init_biginteger("1",&d);
    init_biginteger("0",&v);
    int conteur=0;

    //clock_t pp;
 //pp = clock();
    while(zero(&tempa)==1){
    x=tempa;
    //conteur = conteur +1;
    /*if(conteur==57){
    conteur = conteur;
    }*/
    //printf("%i \n", conteur);
    div_mod(&tempb,&tempa,&t,&tempo);
    tempa=tempo;
    tempb=x;
    x=d;
    d1=Strassen_Multiplication(&t ,&x );
    d= sub_biginteger (&v,&d1);
    v=x;
    }
    //printf("%i \n",conteur);
    // pp= clock() - pp; 
  //printf ("It took me %d clicks (%f seconds).\n",pp,(((double)pp)/CLOCKS_PER_SEC));
    tempb=*b;
    modulo(&v,&tempb,&tempo);
    if(v.sign==-1){
    modulo(&add_biginteger(&v,&tempb),&tempb,&tempo); }
    *c=tempo;

    //printf("%i \n",conteur);

return 1;

}

现在的问题是 256 位整数逆模取 0.005 s，这太多了 ECC 加密，因为在标量乘法中，我将在 double 中重复至少 256 次并添加算法

我已经做了一些关于时间的测试，这个测试主要是大约 10k 次，它在 0.69 秒内完成:

#include "biginteger.h"
#include "ECC.h"
#include <time.h>
void main(){

    clock_t t;
 t = clock();
    int p=1;

    big_integer a,b,c,r,q,a1,b1;
    ECC_domaine_parameter domain;
init_biginteger("580EC00D856434334CEF3F31ECAED4965B12AE37FA47055B1965C7B134EE45D0",  &a);
init_biginteger("FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF", &b);
while(p!=0 ){  div_mod(&b,&a,&q,&r);
               c=Strassen_Multiplication(&a , &b );
                c=sub_biginteger(&a,&b );

         a1=a;
         b1=b;
         b1=a;
         a1=b;
         a1=b1;
         p=p+1;
     if(p==10001){
         printf("end %i \n",p);
         p=0;}} 
 t = clock() - t; 
  printf ("It took me %d clicks (%f seconds).\n",t,(((double)t)/CLOCKS_PER_SEC));
}

现在相同 2 256 位整数的反模函数核心:

char invers_modulo(big_integer *a ,big_integer *b,big_integer *c){

    if( b->sign==-1){ return -1;}

     big_integer tempa=*a,tempb=*b;
    tempa.sign=1;
     big_integer d,t,x,v,tempo,d1;

    init_biginteger("1",&d);
    init_biginteger("0",&v);
    int conteur=0;
while(zero(&tempa)==1){ div_mod(&tempb,&tempa,&t,&tempo);
    tempa=tempo;
    tempb=x;
    x=d;
    d1=Strassen_Multiplication(&t ,&x );
    d= sub_biginteger (&v,&d1);
    v=x;
    }tempb=*b;
    modulo(&v,&tempb,&tempo);
    if(v.sign==-1){
    modulo(&add_biginteger(&v,&tempb),&tempb,&tempo); }
    *c=tempo;



return 1;
} 

对于逆模，它需要 150 时间，而这是测试主要，只需执行逆模 300 时间:

 void main(){

    clock_t t;
 t = clock();
    int p=1;

    big_integer a,b,c,r,q,a1,b1;
    ECC_domaine_parameter domain;
init_biginteger("580EC00D856434334CEF3F31ECAED4965B12AE37FA47055B1965C7B134EE45D0",  &a);
init_biginteger("FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF", &b);
 while(p!=0 ){ invers_modulo(&a ,&b,&c);

         a1=a;
         b1=b;
         b1=a;
         a1=b;
         a1=b1;
         p=p+1;
     if(p==300){
         printf("end %i \n",p);
         p=0;}}
 t = clock() - t; 
  printf ("It took me %d clicks (%f seconds).\n",t,(((double)t)/CLOCKS_PER_SEC));
}

逆模 300 次比执行除法、减法和乘法 10k 时间多花费 1.422 秒，即使逆模的核心是使用相同的除法、减法和乘法函数构建的，对于这个数字，它只在内部执行 150 次，同时帮助请教为什么

Answer 1

反转是一项非常密集的操作。您可以进行多种优化，例如最小化必须使用的反演数量或优化反演算法。要优化算法，您可以实现 Itoh-Tsujii 反演等。

为了减少所需的反转量，您可以从表示仿射坐标系中的点将其转换为投影表示。对于 ECC 系统，经常使用的投影坐标版本是所谓的 López-Dahab 坐标及其运算。