Загрузка данных
//длинная арифметика Окулов Ф.М.+ отрицательные
#include <string.h>
#include <stdio.h>
#include <math.h>
#define MaxDig 1000 //Максимальное количество цифр — четырехзначных!
#define Osn 0x100 //Основание нашей системы счисления, в элементах массива храним двузначные шестнадцатиричные числа
#define mm 8 //число двоичных разрядов у Osn
//структура данных, количество "цифр" в массиве, сами цифры, они определяются системой счисления, знак числа
typedef struct{
int lm[MaxDig]; //массив чисел
int len; //размер массива, кол-во чисел
int sign; //знак числа (-1,+1);
} LDig;
//перевод строки в длинное число
void Read16Long1(LDig *A, char *S){
char ch;
int i,j, len;
len= strlen(S); //??????
for (i=0;i<len;i++){
//считываем символ
ch=S[i];
//еслм отрицательное, то устанавливаем sign
if (ch=='-'){
A->sign=-1;
i++;
ch=S[i];
}
switch (ch){
case 'a': ch=0xa;
break;
case 'A': ch=0xa;
break;
case 'b': ch=0xb;
break;
case 'B': ch=0xb;
break;
case 'c': ch=0xc;
break;
case 'C': ch=0xc;
break;
case 'd': ch=0xd;
break;
case 'D': ch=0xd;
break;
case 'e': ch=0xe;
break;
case 'E': ch=0xe;
break;
case 'f': ch=0xf;
break;
case 'F': ch=0xf;
break;
default: ch=ch-0x30;
break;
}
//вставляем в массив
for (j=A->len;j>=0;j--){
//"протаскивание" старшей цифры в числе из A[j]
//в младшую цифру числа из A[j+l]
A->lm[j+1] = A->lm[j+1] + (A->lm[j]*16)/Osn; //одна буква - 4 бита = 16, перетаскиваем на одну позицию
A->lm[j] = (A->lm[j]*16)%Osn;
}
A->lm[0] = A->lm[0] + ch;//добавляем младшую цифру к числу из А[1]}
//изменяем длину, число задействованных элементов массива А}
if (A->lm[A->len] > 0) A->len++;
if (A->lm[A->len+1] > 0) A->len++;
}
return;
}
void Read16Long(LDig *A, char *S){
char chs[3], s[256];
int i,len, b[100],ch,k=0 ;
if (S[0]=='-'){
A->sign = -1;
k=1;}
//для положительных
strcpy(chs,"");
len= strlen(S);
A->len = len/2;
for (i=k;i<len;i+=2){
chs[0]=S[i];
chs[1]=S[i+1];
chs[2]='\0';
sscanf(chs,"%02x",&ch);
b[i/2]=ch;
}
for(i=0; i<A->len;i++)
A->lm[A->len-1-i]=b[i];
}
//перевод короткого (целого - 2 байта) числа в строку
void Dig16Str(int k, char *s){
int num=0, d, os,i;
char s1[256];
d=k;
//формируем строку
do{
os=d%16;
switch (os){
case 10: s1[num]= 'a';
break;
case 11: s1[num]= 'b';
break;
case 12: s1[num]= 'c';
break;
case 13: s1[num]= 'd';
break;
case 14: s1[num]= 'e';
break;
case 15: s1[num]= 'f';
break;
default: s1[num]=os+0x30;
break;
}
d=d/16;
num++;
} while (d!=0);
//если отрицательное
if (k<0) {s1[num]='-'; num++;}
//запись числа задом наперед
s[num]= '\0';
for (i=num-1;i>=0;i--) s[num-1-i]=s1[i];
return;
}
//запись длинного числа в строку
void Write16Long(LDig *A, char *S){
char ls[256];
char s[10];
int i,j,k=0,n,len1;
//если отрицательное
if (A->sign<0) strcpy(S,"-");
else strcpy(S,"");
strcpy(s,"");
//рабочая строка
for (i=A->len-1;i>=0;i--){
sprintf(s,"%02x", A->lm[i]);
strcat(S,s);
}
return;
}
void Write16Long1(LDig *A, char *S){
char ls[256];
char s[256];
int i,j,k=0,n,len1;
//если отрицательное
if (A->sign<0) {S[k]='-';k++;}
//строка для основания системы счисления
Dig16Str(Osn/16,ls);
//рабочая строка
for (i=A->len-1;i>=0;i--){
Dig16Str(A->lm[i],s);
//заполняем нулями перед цифрами, если надо
while((strlen(s)<strlen(ls))&&(i!=A->len-1)){
len1=strlen(s);
//сдвигаем число
for (n=len1;n>0;n--) s[n]=s[n-1];
s[0]= '0' ; s[1]= '0';
s[len1+1]= '\0' ;
}
//вставляем в основную строку
for (j=0;j<strlen(s);j++) S[k+j]=s[j];
k=k+j;
}
S[k]='\0';
return;
}
//распечатка длинного числа
void ShowLong(LDig *A){
int i;
for (i=0; i<A->len;i++) printf("%d ",A->lm[i]);
printf("\n");
return;
}
//распечатка длинного числа в строку
void ShowLongS(LDig *A){
char S[256];
Write16Long(A, S);
printf("%s\n",S);
return;
}
//инициализация LDig
void InitLong(LDig *A){
int i;
for (i=0; i<MaxDig; i++) A->lm[i]=0;
A->len=1; A->sign=1; //положительное, нулевой вектор
return;
}
//перевод целого числа в массив
void DigToArray(int k, LDig *A){
int res, i=0, sign=1;
if (k<0) sign=-1;
res=fabs(k);
while (res>0){
A->lm[i]=res%Osn;
res/=Osn;
i++;
}
A->len=i;
A->sign=A->sign*sign;
return;
}
//Сравнение двух длинных чисел: равно (1), не равно (0)
int Eq(LDig *A, LDig *B){
int i;
if ((A->len!=B->len)||(A->sign!=B->sign)) return 0; //разные длины, знаки , нельзя сравнивать не равны
else {
i=0;
//сравниваем поразрядно
while ((i<A->len)&&(A->lm[i]==B->lm[i])) i++;
}
return i==A->len;
}
//Сравнение положительных |A|>|B| больше (1), |A|<|B| меньше (0)
int More(LDig *A, LDig *B) {
int i, sr=0;
if (A->len<B->len) sr=0; //меньше
else
if(A->len>B->len) sr=1; //больше
else{
i=A->len-1;
while ((i>0)&&(A->lm[i]==B->lm[i])) i--;
if (i==-1) sr=0;
else
if (A->lm[i]>B->lm[i]) sr=1;
else sr=0;
}
return sr;
}
//положительные
//сравнение со сдвигом, сдвигаем B
//результат 0, если |A|>|B|; 1, если |A|<|B|; 2, если |A|=|B|
int More_Shift(LDig *A, LDig *B, int sp){
int res,i;
if (A->len>B->len+sp) res=0;
else{
if (A->len<B->len+sp) res=1;
else{
i=A->len-1;
while ((i>sp-1)&&(A->lm[i]==B->lm[i-sp])) i--;
if (i==sp-1) {
res=0;
//совпадение чисел с учетом сдвига
for(i=0;i<sp-1;i++) if (A->lm[i]>0) return res;
res=2; //числа равны, "хвост" числа А равен нулю
}
else res=(A->lm[i]<B->lm[i-sp]);
}
}
return res;
}
//|A|<|B|
int Less(LDig*A, LDig *B){
return !(More(A,B)||Eq(A,B));
}
//|A|>=|B|
int More_Eq(LDig *A, LDig *B){
return More(A,B)||Eq(A,B);
}
//|A|<=|B|
int Less_Eq(LDig *A,LDig *B){
return !More(A,B);
}
//проверка на равенство нулю A=0 (1, иначе 0)
int IsNulLong(LDig *A){
if ((A->len==1)&&(A->lm[0]==0)) return 1;
else return 0;
}
//Умножение длинного числа на короткое (Osn), результат в C
void Mul(LDig *A, int K, LDig*C){
int i;
InitLong(C);
if (K!=0){
for (i=0;i<A->len;i++){
C->lm[i+1]=(C->lm[i]+A->lm[i]*fabs(K))/Osn;
C->lm[i]=(C->lm[i]+A->lm[i]*(int)fabs(K))%Osn;
}
//определяем длину результата
if (C->lm[A->len]>0) C->len=A->len+1;
else C->len=A->len;
}
C->sign=A->sign*(K/fabs(K));
return;
}
//Умножение длинного числа на короткое (<Osn), результат в A
void MulA(LDig *A, int K){
LDig C;
InitLong(&C);
Mul(A, K, &C);
*A=C;
return;
}
//положительные
//вычитание двух длинных чисел с учетом сдвига |A|>|B|, результат в A (вычитание модулей, без учета знака)
//sp- число разрядов для сдвига, сдвигаем B
void Sub_Shift(LDig *A, LDig *B, int sp){
int i,j;
//из А вычитаем В с учетом сдвига sp, результат вычитания в А
for (i=0; i<B->len;i++){
A->lm[i+sp]-=B->lm[i];
j=i;
//реализация сложного заимствования
while ((A->lm[j+sp]<0)&&(j<A->len-1)){
A->lm[j+sp]+=Osn;
A->lm[j+sp+1]--;
j++;
}
}
//корректировка длины результата операции
i = A->len-1;
while( (i > 0)&&(A->lm[i] == 0)) i--;
A->len = i+1;
return;
}
//положительные
//Сложение двух длинных чисел |A| и |B| с учетом сдвига, результат в A (сложение модулей без учета знака)
//sp- число разрядов для сдвига, сдвигаем B !!!нет у Окулова
void Sum_Shift(LDig *A, LDig*B, int sp){
int i,k;
if (A->len>B->len+sp) k=A->len;
else k=B->len+sp;
for (i=0;i<k;i++){
A->lm[i+sp+1]+=(A->lm[i+sp]+B->lm[i])/Osn;
A->lm[i+sp]=(A->lm[i+sp]+B->lm[i])%Osn;
}
if (A->lm[k]==0) A->len=k;
else A->len=k+1;
return;
}
//положительные
//сложение двух положительных чисел (столбиком), результат в C без учета знака
void SumTwo(LDig *A, LDig *B, LDig *C){
*C=*A;
Sum_Shift(C,B,0);
return;
}
//положительные
//вычитание |A|>|B|, результат в C
void SubTwo(LDig *A, LDig *B, LDig *C){
//из А вычитаем В с учетом сдвига sp, результат вычитания в А
*C=*A;
Sub_Shift(C,B,0);
return;
}
//сложение двух длинных со знаком, результат в C
void SumLong(LDig *A, LDig *B, LDig *C){
//Если оба одного знака - сумма
if (A->sign==B->sign){
SumTwo(A, B, C);
C->sign=A->sign;
}
//Знаки разные - разность
else{
if (A->len>B->len){
SubTwo(A, B, C);
C->sign=A->sign;
}
else{
SubTwo(B, A, C);
C->sign=B->sign;
}
}
return;
}
//сложение двух длинных со знаком, результат в A
void SumLongA(LDig *A, LDig *B){
LDig C;
InitLong(&C);
SumLong(A, B, &C);
*A=C;
return;
}
//вычитание двух длинных со знаком, результат в C
void SubLong(LDig *A, LDig *B, LDig *C){
//знаки разные - сумма
if (A->sign!=B->sign){
SumTwo(A, B, C);
C->sign=A->sign;
}
//знаки одинаковые
else{
if (More(A, B)){
SubTwo(A,B,C);
C->sign=A->sign;
}
else{
SubTwo(B, A, C);
C->sign=-B->sign;
}
}
return;
}
//вычитание двух длинных со знаком, результат в A
void SubLongA(LDig *A, LDig *B){
LDig C;
InitLong(&C);
SubLong(A, B, &C);
*A=C;
return;
}
//Умножение двух длинных чисел со знаком !!!нет у Окулова, результат в C
void MulTwoLong(LDig *A, LDig *B, LDig*C){
int i;
LDig C1;
InitLong(&C1);
for (i=0;i<B->len;i++){
Mul(A, B->lm[i], &C1);
Sum_Shift(C, &C1 , i);
}
C->sign=A->sign*B->sign;
return;
}
//Умножение двух длинных чисел со знаком !!!нет у Окулова, результат в A
void MulTwoLongA(LDig *A, LDig *B){
LDig C;
InitLong(&C);
MulTwoLong(A, B, &C);
*A=C;
return;
}
//деление двух длинных чисел (частное и остаток)
//=================================================
//двоичный поиск - подбираем результат деления
int FindBin(LDig *Ost, LDig *B, int sp){
int Down=0, Up=Osn,k;
LDig C;
InitLong(&C);
while(Up-1>Down){
Mul(B, (Up + Down)/2, &C);
k=More_Shift(Ost, &C, sp);
switch (k) {
case 0: Down = (Down + Up)/2;
break;
case 1: Up = (Up + Down)/2;
break;
case 2: Up = (Up + Down)/2;
Down = Up;
break;
}
}
Mul(B, (Up + Down)/2, &C);
//находим остаток от деления
if (More_Shift (Ost, &C, 0) == 0) Sub_Shift(Ost, &C, sp);
else {
Sub_Shift (&C, Ost, sp);
*Ost = C;
}
return (Up + Down)/2; //целая часть частного
}
void MakeDel(LDig *A, LDig *B, LDig *Res, LDig *Ost){
int sp;
//первоначальное значение остатка Ost=A
*Ost = *A;
sp=A->len-B->len;
if (More_Shift(A,B,sp)==1) sp--;
//B * Osn > A, в результате одна цифра
Res->len=sp+1;
while (sp>=0){
//находим очередную цифру результата
Res->lm[sp]=FindBin(Ost,B,sp);
sp--;
}
return;
}
//остаток может быть отрицательным
void LongDivLong(LDig *A, LDig *B, LDig *Res, LDig *Ost){
switch (More_Shift(A,B,0)){
case 0: MakeDel(A,B,Res,Ost);
break;
case 1: *Ost=*A; //А меньше В
break;
case 2: Res->lm[1]=1; //А равно В
break;
}
Res->sign=A->sign*B->sign;
Ost->sign=A->sign*B->sign;
return;
}
// ============ КОД ИЗ EllipLong.c ============
//параметры области определения
//================================================================================
//модуль
char ps[] = "fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f";
//параметры эллиптической фукции
int a = 0;
int b = 7;
//базовая точка
char xGs[] = "79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798";
char yGs[] = "483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8";
//порядок подгруппы
char ns[] = "fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141";
//кофактор
int h=1;
//====================================================================================
LDig P, xG, yG, n;
//инициализация параметров эллиптической кривой
void InitPar(){
InitLong(&P);
InitLong(&n);
InitLong(&xG);
InitLong(&yG);
Read16Long(&P,ps);
Read16Long(&n,ns);
Read16Long(&xG,xGs);
Read16Long(&yG,yGs);
return;
}
//длинный остаток от деления (mod), результат в Ost
void OstLong(LDig *A, LDig *Ost){
LDig Res;
InitLong(&Res);
LongDivLong(A, &P, &Res, Ost);
//если остаток - отрицательный
if ((Ost->sign<0)&&!IsNulLong(Ost)){
SumLongA(Ost, &P);
}
return;
}
void OstLongMod(LDig *A, LDig *Ost, LDig *mod){
LDig Res;
InitLong(&Res);
LongDivLong(A, mod, &Res, Ost);
//если остаток - отрицательный
if ((Ost->sign<0)&&!IsNulLong(Ost)){
SumLongA(Ost, mod);
}
return;
}
//длинный остаток от деления (mod), результат в A
void OstLongA(LDig *A){
LDig Ost;
InitLong(&Ost);
OstLong(A, &Ost);
*A=Ost;
return;
}
void OstLongAMod(LDig *A, LDig *mod){
LDig Ost;
InitLong(&Ost);
OstLongMod(A, &Ost, mod);
*A=Ost;
return;
}
//расширенный алгоритм Евклида для длинных чисел без s, не используется
void LongEnhEvklid(LDig *A, LDig *B, LDig *t, LDig *nod){
LDig *r1, *r2, *t1, *t2, *r, *q, *tt, *C;
int i=0;
char s1[256];
r1=malloc(sizeof(LDig));
r2=malloc(sizeof(LDig));
t1=malloc(sizeof(LDig));
t2=malloc(sizeof(LDig));
r=malloc(sizeof(LDig));
q=malloc(sizeof(LDig));
tt=malloc(sizeof(LDig));
C=malloc(sizeof(LDig));
InitLong(r1); InitLong(r2);
InitLong(t1); InitLong(t2);
InitLong(q); InitLong(r);
InitLong(tt);
InitLong(C);
//ShowLongS(A);
//начальные присвоения
*r1=*A; *r2=*B;
t1->lm[0]=0; t2->lm[0]=1;
Dig16Str(i, s1);
// printf("s1=%s\n",s1);
// WriteInFile(r2,s1);
while(!IsNulLong(r2)){
i++;
InitLong(q); InitLong(r);
if (i==0x7f){
// WriteInFile(r2,"r2");
// WriteInFile(r1,"r1");
}
LongDivLong(r1,r2,q,r);
*r1=*r2; *r2=*r;
InitLong(C);
InitLong(tt);
MulTwoLong(q, t2, C);
SubLong(t1,C,tt);
*t1=*t2; *t2=*tt;
Dig16Str(i, s1);
// printf("s1=%s\n",s1);
// WriteInFile(r2,s1);
}
// printf("i=%d\n",i);
*nod=*r1;
*t=*t1;
free(r1); free(r2);
free(t1); free(t2);
free(r); free(q);
free(tt); free(C);
return;
}
//Мультипликативная инверсия A*T=1 ищем T
void invA(LDig *A, LDig *T){
LDig t, nod, Ed;
InitLong(&t);
InitLong(&nod);
InitLong(&Ed);
Ed.lm[0]=1;
// ShowLongS(A);
LongEnhEvklid(&P, A, &t, &nod);
if(!Eq(&nod, &Ed)) printf("err\n");
// ShowLongS(&nod);
*T=t;
return;
}
//Мультипликативная инверсия по модулю A*T=1 mod n ищем T
void invAMod(LDig *A, LDig *T, LDig *n){
LDig t, nod, Ed;
InitLong(&t);
InitLong(&nod);
InitLong(&Ed);
Ed.lm[0]=1;
// ShowLongS(A);
LongEnhEvklid(n, A, &t, &nod);
if(!Eq(&nod, &Ed)) printf("err\n");
// ShowLongS(&nod);
*T=t;
return;
}
//сложение двух точек P+Q=R, результат в R
void AddPoint(LDig *xP, LDig *yP, LDig *xQ, LDig *yQ, LDig *xR, LDig *yR){
LDig *m, *s1, *s2, *C1, *C2, *C3;
m=malloc(sizeof(LDig));
s1=malloc(sizeof(LDig));
s2=malloc(sizeof(LDig));
C1=malloc(sizeof(LDig));
C2=malloc(sizeof(LDig));
C3=malloc(sizeof(LDig));
InitLong(m);
InitLong(s1);
InitLong(s2);
InitLong(C1);
InitLong(C2);
InitLong(C3);
SubLong(xP, xQ, C1); //C1=xP-xQ
OstLongA(C1);
// ShowLongS(C1);
SubLong(yP, yQ, C2); //C2=yP-yQ
OstLongA(C2);
//Проверка на особую точку
//Если P=0, то P+Q=Q
if(IsNulLong(xP)&&IsNulLong(yP)){
*xR=*xQ;
*yR=*yQ;
return;
}
//Если Q=0, то P+Q=P
if(IsNulLong(xQ)&&IsNulLong(yQ)){
*xR=*xP;
*yR=*yP;
return;
}
//Если P=-Q (xP=xQ и yP=-yQ) то R-особая точка
if(IsNulLong(C1)){
if (!IsNulLong(C2)){
SumLong(yP,yQ,C3);
OstLongA(C3);
if(IsNulLong(C3)){
InitLong(xR);
InitLong(yR);
// InitLong(C3);
return;
}
}
}
if (IsNulLong(C1)&&IsNulLong(C2)){
InitLong(C1);
InitLong(C2);
//s1=xP*xP*3+a (mod p)
MulTwoLong(xP, xP, C1); //C1=xP*xP
OstLongA(C1);
MulA(C1, 3); //C1=C1*3
DigToArray(a,C2);
SumLongA(C1,C2); //C1+a
OstLong(C1, s1); //s1=C1%p
InitLong(C1);
InitLong(C2);
//s2=(2*yP)^-1
Mul(yP, 2, C1); //C1=yP*2
OstLong(C1,C2);
if(IsNulLong(C2)) printf("null\n");
invA(C2, s2); //s2=C1^-1
OstLongA(s2);
}
else{
//s1=yP-yQ
OstLong(C2, s1); //s1=C2%p
//s2=xP-xQ
OstLong(C1,C3);
if(IsNulLong(C3)) printf("null\n");
// if ((i==0)&&(j==13)) WriteInFile(C3, "C3");
invA(C3, s2); //s2=C1^-1
OstLongA(s2);
}
InitLong(C1); //C1=0
InitLong(C2); //C2=0
//xR=m*m-(xP+xQ)
MulTwoLong(s1, s2, m); //m=s1*s2
OstLongA(m); //m=C1%p
MulTwoLong(m, m, C1); //C1=m*m
OstLongA(C1);
SumLong(xP, xQ, C2); //C2=xP+xQ
OstLongA(C2);
SubLong(C1, C2, xR); //xR=C1-C2
OstLongA(xR); //xR=C3%p
InitLong(C1); //C1=0
InitLong(C2); //C2=0
//yR=yP+m(xR-xP)
SubLong(xR, xP, C1); //C1=xR-xP
OstLongA(C1);
MulTwoLong(C1, m, C2); //C2=C1*m
OstLongA(C2);
SumLong(yP, C2, yR); //C3=yP+C2
OstLongA(yR);
//меняем знак yR=-yR
yR->sign=-yR->sign; //C1=-C1
OstLongA(yR); //yR=C1%p
// ShowLongS(yR);
free(m); free(s1); free(s2); free(C1); free(C2); free(C3);
return;
}
//сложение двух точек P+Q, результат в P
void AddPointP(LDig *xP, LDig *yP, LDig *xQ, LDig *yQ){
LDig *xR, *yR;
xR=malloc(sizeof(LDig));
yR=malloc(sizeof(LDig));
InitLong(xR);
InitLong(yR);
AddPoint(xP, yP, xQ, yQ, xR, yR);
*xP=*xR;
*yP=*yR;
free(xR); free(yR);
return;
}
// ============ КОНЕЦ КОДА ИЗ EllipLong.c ============
int main() {
printf("=== Задание №5: Сложение точек G + P ===\n");
printf("Используются параметры из EllipLong.c (secp256k1)\n\n");
// Инициализация параметров
InitPar();
printf("Параметры кривой:\n");
printf("p = "); ShowLongS(&P);
printf("a = %d\n", a);
printf("b = %d\n\n", b);
printf("Базовая точка G:\n");
printf("xG = "); ShowLongS(&xG);
printf("yG = "); ShowLongS(&yG);
printf("\n");
// Для примера возьмём точку P = G
LDig xP, yP;
InitLong(&xP);
InitLong(&yP);
xP = xG;
yP = yG;
printf("Точка P (взята равной G):\n");
printf("xP = "); ShowLongS(&xP);
printf("yP = "); ShowLongS(&yP);
printf("\n");
// Результат сложения G + P
LDig xR, yR;
InitLong(&xR);
InitLong(&yR);
printf("Вычисляем G + P...\n\n");
AddPoint(&xG, &yG, &xP, &yP, &xR, &yR);
printf("Результат G + P:\n");
printf("xR = "); ShowLongS(&xR);
printf("yR = "); ShowLongS(&yR);
return 0;
}