-1
嗨，大家好，請原諒，我的英語 我開發了一個大的整數函數C：ECC逆模怪的時候執行
#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;
}
現在prblem是爲256位整數逆模以0.005秒這是太多的ECC密碼因爲標量乘我會重複至少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的時間內，而這是測試主要只是執行INVERS模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次佔用1.422次以上執行除子和乘法10K時間甚至反模的核心都是用同樣的分頻和乘法功能建立的，對於這個數字它只是在150次內部幫助plz爲什麼