ГОСТ 3410 / Работа с длинными числами

@IS · Регистрация: 01.10.2008

Author24 — интернет-сервис помощи студентам

Начал делать курсовик по реализации ЭЦП по ГОСТ 34.10 (и соответственно 34.11 и 28147

). В качестве среды разработки выбрал C++ Builder.
Возник вопрос: Как работать с большими числами размером в 256,512,1024 бит? Они, ведь, ни в один тип данных не лезут (int только 32 бита). В контрольком примере дано число 57896044618658097711785492504343953926634992332820282019728792003956564821041.
P.S Чужая реализация 3410-01 Но, есть сильное подозрение а то, что препода "кинули" - подсунили ему в место ГОСТ 3410-2001, забугорский ECDSA.
Мой курсовик:
Недостатки:
1) Результат проверки не совпадает с генерированой подписью. Проблема в математике.
2) Нет создания хэша функции по ГОСТ 3411
3) Нет вычисленя параметров ЭК.
4) Длительное время работы (прога не зависла - она считает)

@Lord_Voodoo · 01.10.2008, 13:23

есть арифметика длинных чисел, почитай С. Оклов "Программирование в алгоритмах"

@IS · 06.10.2008, 18:11 **[ТС]**

А нельзя просто выделить память под переменную в 256 бит?

@Lord_Voodoo · 06.10.2008, 18:14

ну так в один бит ты как цифру записать собрался? глянь типы данных, там по-любому есть тип, который в себя вместит число, просто с помощью арифметики длинных числе можно реализовать быстрые алгоритмы для работы с такими числами

@IS · 20.10.2008, 10:30 **[ТС]**

Нашел материал по работе с длинными числами - Щербаков, Домашев Прикладная криптография. Но, к сожалению не могу заставить работать хотя бы первый алгоритм сложения - не выполняется перенос разряда. В чем проблема?
http://slil.ru/26253252 - все о госте
http://slil.ru/26253265 - не работающая прога
http://slil.ru/26253351 - Щербаков, Домашев Прикладная криптография

@Lord_Voodoo · 20.10.2008, 10:41

сложение длинных чисел

Код

void add(int a[N], int b[N], int c[N]){
  memset(c, 0, sizeof(int)*N);
  int i = 0;
  for(i = N - 1; i >= 0; i--){
    if(t.quot){
      c[i]++;
      if(i < ctrl) ctrl = i;
    }
    t = div((c[i] + a[i] + b[i]),10);
    c[i] = t.rem;
  }
}

@IS · 20.10.2008, 19:32 **[ТС]**

Объясните этот код:

C++

//---------------------------------------------------------------------------
 
#include <vcl.h>
#pragma hdrstop
 
#include "Unit1_math.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
 
#define LoDigit(T) ((int)(T))
#define HiDigit(T) ((int)((T)>>m))
 
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
        : TForm(Owner)
{
}
//---------------------------------------------------------------------------
void Assign (int A[], const int B[], int n);// A:=B
 
void AssignDigit( int A[],  int x, int n );// A:=число x
 
void Zero (int A[], int n);// A=0
 
int IsZero (int A[], int n);// равно ли A=0?
 
int Add (int C[], const int A[], const B[], int n)// сложение длинных чисел длиной n цифр
{
__int64 T; число длиною равной сумме длины числа A и числа B
int d=0;// перенос разряда
int i;
char m=32; //почему char 
 
for (i=0; i<=n; i++)
        {
        T=(__int64)A[i]+B[i]+d;//(__int64) - что значит
        C[i]=LoDigit (T);// младшие разряды числа T - как работает?
        d=HiDigit(T);// старшие разряды числа T - как работает?
        }
for (i=0; i<=n; i++) Form1->LabeledEdit1->Text=Form1->LabeledEdit1->Text+IntToStr(A[i]);
for (i=0; i<=n; i++) Form1->LabeledEdit2->Text=Form1->LabeledEdit2->Text+IntToStr(B[i]);
for (i=0; i<=n; i++) Form1->LabeledEdit3->Text=Form1->LabeledEdit3->Text+IntToStr(C[i]);
return d;
};
 
void __fastcall TForm1::Button1Click(TObject *Sender)
{
 
int a[]={2,2,9}, b[]={1,2,9,1},c[]={1,2,2,3};
Add(c,a,b,3);// вызов
 
}
//---------------------------------------------------------------------------

@Lord_Voodoo · 20.10.2008, 20:21

(__int64) - это приведение типа, LoDigit(T) - возвращает младшие 4 байта
HiDigit(T) - старшие 4 байта, чар используется для того, чтобы был один байт...
ну а вообще - алгоритм прост... иммитация сложения столбцом... только человек эффективнее использует элементы массива, в отличии от моего алгоритма... да и по-хорошему, ты бы мог и потрассировать алгоритм, тогда будет видно, что там и зачем делается

@IS · 20.10.2008, 20:35 **[ТС]**

1) Спасибо

2) Как работает #define HiDigit(T) ((int)((T)>>m))? Сам понял, что число T помещается в поток, а ((int)((T)>>m)) что делает? За счет, чего помещается в старшие 4 байта.
3) Почему при сложении int a[]={2,2,9} и b[]={1,2,9} получается С[i]={3,4,18} т.е нет переноса.
4) Трассировку хорошо бы сделать, но не ясно как. В меню Run можно выполнить только команду Run, а по шагам нельзя.

@Lord_Voodoo · 20.10.2008, 21:31

>> - это в данном случае сдвиг на 32 бита
ну так при выводе будет 1843... а переполнение - это когда число больше байта будет по идее...

@IS · 20.10.2008, 22:34 **[ТС]**

Unit1_math.cpp

C++

//---------------------------------------------------------------------------
 
#include <vcl.h>
#pragma hdrstop
 
#include "Unit1_math.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
 
#define LoDigit(T) ((int)(T))
#define HiDigit(T) ((int)((T)>>m))
 
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
        : TForm(Owner)
{
}
//---------------------------------------------------------------------------
 
void Assign (int A[], const int B[], int n);
 
void AssignDigit( int A[],  int x, int n );
 
void Zero (int A[], int n);
 
int IsZero (int A[], int n);
 
int Add (int C[], const int A[], const B[], int n)
{
__int64 T;
int d=0;
int i;
char m=32;
 
Form1->RichEdit1->Lines->Add(sizeof (T));
for (i=0; i<=n; i++)
        {
        T=(__int64)A[i]+B[i]+d;
        C[i]=LoDigit (T);
        d=HiDigit(T);
        Form1->RichEdit1->Lines->Add("i="+IntToStr(i)+" T="+IntToStr(T)+" C="+IntToStr(C[i])+" sizeof(C)="+IntToStr(sizeof(C[i]))+" d="+IntToStr(d)+ " sizeof(d)="+IntToStr(sizeof(HiDigit(T))));
        }
for (i=0; i<=n; i++) Form1->LabeledEdit1->Text=Form1->LabeledEdit1->Text+IntToStr(A[i]);
for (i=0; i<=n; i++) Form1->LabeledEdit2->Text=Form1->LabeledEdit2->Text+IntToStr(B[i]);
for (i=0; i<=n; i++) Form1->LabeledEdit3->Text=Form1->LabeledEdit3->Text+IntToStr(C[i])+";";
return d;
};
 
int Sub (int C[], const int A[], const B[], int n)
{
__int64 T;
int d=0;
int i;
char m=32;
 
Form1->RichEdit1->Lines->Add(sizeof (T));
for (i=0; i<=n; i++)
        {
        T=(__int64)A[i]-B[i]-d;
        C[i]=LoDigit (T);
        d=HiDigit(T);
        d=(0-d);
        Form1->RichEdit1->Lines->Add("i="+IntToStr(i)+" T="+IntToStr(T)+" C="+IntToStr(C[i])+" sizeof(C)="+IntToStr(sizeof(C[i]))+" d="+IntToStr(d)+ " sizeof(d)="+IntToStr(sizeof(HiDigit(T))));
        }
for (i=0; i<=n; i++) Form1->LabeledEdit1->Text=Form1->LabeledEdit1->Text+IntToStr(A[i]);
for (i=0; i<=n; i++) Form1->LabeledEdit2->Text=Form1->LabeledEdit2->Text+IntToStr(B[i]);
for (i=0; i<=n; i++) Form1->LabeledEdit3->Text=Form1->LabeledEdit3->Text+IntToStr(C[i])+";";
return d;
};
 
int Cmp (const int A[], const B[], int n)
{
int i;
char m=32;
 
for (i=n-1; (i>=n)&&(A[i]==B[i]); i--);
if (i<0) return 0;
if (A[i]>B[i]) return +1;
return -1;
};
 
void Mul (int C[], const int A[], const B[], int n)
{
int i,j;
int d;
__int64 T;
 
Zero(C,n);
 
for (i=0; i<=n; i++)
{
        d=0;
        for (j=0; j<n; j++)
        {
                T = (__int64)A[i]*B[j]+d;
                C[i+j]=LoDigit (T);
                d= HiDigit (T);
        }
        C[i+j]=d;
}
for (i=0; i<=n; i++) Form1->LabeledEdit1->Text=Form1->LabeledEdit1->Text+IntToStr(A[i]);
for (i=0; i<=n; i++) Form1->LabeledEdit2->Text=Form1->LabeledEdit2->Text+IntToStr(B[i]);
for (i=0; i<=n; i++) Form1->LabeledEdit3->Text=Form1->LabeledEdit3->Text+IntToStr(C[i])+";";
}
 
void ClearAllForm()
{
Form1->RichEdit1->Clear();
Form1->LabeledEdit1->Clear();
Form1->LabeledEdit2->Clear();
Form1->LabeledEdit3->Clear();
Form1->LabeledEdit4->Clear();
}
//------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
ClearAllForm();
int a[]={2,2,9}, b[]={1,2,9},c[]={1,2,2,3};
Form1->LabeledEdit4->Text=IntToStr(Add(c,a,b,2));
 
}
//---------------------------------------------------------------------------
 
void __fastcall TForm1::Button2Click(TObject *Sender)
{
ClearAllForm();
int a[]={2,2,8}, b[]={1,2,9},c[]={1,2,2,3};
Form1->LabeledEdit4->Text=IntToStr(Sub(c,a,b,2));
}
//---------------------------------------------------------------------------
 
void __fastcall TForm1::Button3Click(TObject *Sender)
{
ClearAllForm();
int a[]={2,2,9}, b[]={1,2,9};
Form1->LabeledEdit4->Text=IntToStr(Cmp(a,b,2));
}
 
void __fastcall TForm1::FormCreate(TObject *Sender)
{
Form1->Label1->Caption="Длина машинного слова m="+IntToStr(m)+" Количество цифр n=" + IntToStr(n);
}
//---------------------------------------------------------------------------
 
void __fastcall TForm1::Button4Click(TObject *Sender)
{
int a[]={2,2,9}, b[]={1,2,9},c[]={1,2,3,4,5,6,7,8,9};
Mul (c,a,b,n);
}
//---------------------------------------------------------------------------

Unit1_math.h

C++

//---------------------------------------------------------------------------
 
#ifndef Unit1_mathH
#define Unit1_mathH
//---------------------------------------------------------------------------
#include <Classes.hpp>
#include <Controls.hpp>
#include <StdCtrls.hpp>
#include <Forms.hpp>
#include <ExtCtrls.hpp>
#include <ComCtrls.hpp>
//---------------------------------------------------------------------------
class TForm1 : public TForm
{
__published:    // IDE-managed Components
        TLabeledEdit *LabeledEdit1;
        TLabeledEdit *LabeledEdit2;
        TLabeledEdit *LabeledEdit3;
        TButton *Button1;
        TRichEdit *RichEdit1;
        TButton *Button2;
        TButton *Button3;
        TLabeledEdit *LabeledEdit4;
        TLabel *Label1;
        TButton *Button4;
        void __fastcall Button1Click(TObject *Sender);
        void __fastcall Button2Click(TObject *Sender);
        void __fastcall Button3Click(TObject *Sender);
        void __fastcall FormCreate(TObject *Sender);
        void __fastcall Button4Click(TObject *Sender);
private:    // User declarations
public:     // User declarations
        __fastcall TForm1(TComponent* Owner);
 
};
//---------------------------------------------------------------------------
extern PACKAGE TForm1 *Form1;
int Mas[]={1,2,3,4,5,6,7,8,9,};
int n=2;
char m=32;
 
void Assign (int A[], const int B[], int n);
 
void AssignDigit( int A[],  int x, int n );
 
void Zero (int A[], int n);
 
int IsZero (int A[], int n);
 
int Add (int C[], const int A[], const B[], int n);
 
int Sub (int C[], const int A[], const B[], int n);
 
int Cmp (const int A[], const B[], int n);
 
void Mul (int C[], const int A[], const B[], int n);
 
//---------------------------------------------------------------------------
#endif

Выдает ошибку:
[Linker Error] Unresolved external 'Zero(int *, int)' referenced from D:\PROGRAM FILES\BORLAND\CBUILDER6\BIN\3410_ARIFMETIKA\UNIT1_MATH.OBJ

@Lord_Voodoo · 21.10.2008, 10:45

прототип Zero описан, даже есть вызов функции, ну а где же ее реализация-то?

@IS · 21.10.2008, 12:41 **[ТС]**

Возникли еще вопросы. Как работают функции, ведь в них есть только передача параметров:

C++

void Assign (int A[], const int B[], int n); // A=B
void AssignDigit( int A[],  int x, int n );// A=x, x - число
void Zero (int A[], int n);// A=0, A -число длиною в n цифр
int IsZero (int A[], int n);//равно ли нулю?

Или это стандартные функции C++?

Добавлено через 3 минуты 7 секунд
Второй вопрос.
Unit1_math.h:

C++

//---------------------------------------------------------------------------
 
#ifndef Unit1_mathH
#define Unit1_mathH
//---------------------------------------------------------------------------
#include <Classes.hpp>
#include <Controls.hpp>
#include <StdCtrls.hpp>
#include <Forms.hpp>
#include <ExtCtrls.hpp>
#include <ComCtrls.hpp>
//---------------------------------------------------------------------------
class TForm1 : public TForm
{
__published:    // IDE-managed Components
        TLabeledEdit *LabeledEdit1;
        TLabeledEdit *LabeledEdit2;
        TLabeledEdit *LabeledEdit3;
        TButton *Button1;
        TRichEdit *RichEdit1;
        TButton *Button2;
        TButton *Button3;
        TLabeledEdit *LabeledEdit4;
        TLabel *Label1;
        TButton *Button4;
        void __fastcall Button1Click(TObject *Sender);
        void __fastcall Button2Click(TObject *Sender);
        void __fastcall Button3Click(TObject *Sender);
        void __fastcall FormCreate(TObject *Sender);
        void __fastcall Button4Click(TObject *Sender);
private:    // User declarations
public:     // User declarations
        __fastcall TForm1(TComponent* Owner);
};
//---------------------------------------------------------------------------
extern PACKAGE TForm1 *Form1;
int Mas[]={1,2,3,4,5,6,7,8,9,};
int n=2;
char m=32;
 
void Assign (int A[], const int B[], int n);
 
void AssignDigit( int A[],  int x, int n );
 
void Zero (int A[], int n);
 
int IsZero (int A[], int n);
 
int Add (int C[], const int A[], const B[], int n);
 
int Sub (int C[], const int A[], const B[], int n);
 
int Cmp (const int A[], const B[], int n);
 
void Mul (int C[], const int A[], const B[], int n);
 
//---------------------------------------------------------------------------
#endif[/CODE]
 
[CODE]//---------------------------------------------------------------------------
 
#include <vcl.h>
#pragma hdrstop
 
#include "Unit1_math.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
 
#define LoDigit(T) ((int)(T))
#define HiDigit(T) ((int)((T)>>m))
 
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
        : TForm(Owner)
{
}
//---------------------------------------------------------------------------
 
void Assign (int A[], const int B[], int n);
 
void AssignDigit( int A[],  int x, int n );
 
void Zero (int A[], int n);
 
int IsZero (int A[], int n);
 
int Add (int C[], const int A[], const B[], int n)
{
__int64 T;
int d=0;
int i;
char m=32;
 
Form1->RichEdit1->Lines->Add(sizeof (T));
for (i=0; i<=n; i++)
        {
        T=(__int64)A[i]+B[i]+d;
        C[i]=LoDigit (T);
        d=HiDigit(T);
        Form1->RichEdit1->Lines->Add("i="+IntToStr(i)+" T="+IntToStr(T)+" C="+IntToStr(C[i])+" sizeof(C)="+IntToStr(sizeof(C[i]))+" d="+IntToStr(d)+ " sizeof(d)="+IntToStr(sizeof(HiDigit(T))));
        }
for (i=0; i<=n; i++) Form1->LabeledEdit1->Text=Form1->LabeledEdit1->Text+IntToStr(A[i]);
for (i=0; i<=n; i++) Form1->LabeledEdit2->Text=Form1->LabeledEdit2->Text+IntToStr(B[i]);
for (i=0; i<=n; i++) Form1->LabeledEdit3->Text=Form1->LabeledEdit3->Text+IntToStr(C[i])+";";
return d;
};
 
int Sub (int C[], const int A[], const B[], int n)
{
__int64 T;
int d=0;
int i;
char m=32;
 
Form1->RichEdit1->Lines->Add(sizeof (T));
for (i=0; i<=n; i++)
        {
        T=(__int64)A[i]-B[i]-d;
        C[i]=LoDigit (T);
        d=HiDigit(T);
        d=(0-d);
        Form1->RichEdit1->Lines->Add("i="+IntToStr(i)+" T="+IntToStr(T)+" C="+IntToStr(C[i])+" sizeof(C)="+IntToStr(sizeof(C[i]))+" d="+IntToStr(d)+ " sizeof(d)="+IntToStr(sizeof(HiDigit(T))));
        }
for (i=0; i<=n; i++) Form1->LabeledEdit1->Text=Form1->LabeledEdit1->Text+IntToStr(A[i]);
for (i=0; i<=n; i++) Form1->LabeledEdit2->Text=Form1->LabeledEdit2->Text+IntToStr(B[i]);
for (i=0; i<=n; i++) Form1->LabeledEdit3->Text=Form1->LabeledEdit3->Text+IntToStr(C[i])+";";
return d;
};
 
int Cmp (const int A[], const B[], int n)
{
int i;
char m=32;
 
for (i=n-1; (i>=n)&&(A[i]==B[i]); i--);
if (i<0) return 0;
if (A[i]>B[i]) return +1;
return -1;
};
 
void Mul (int C[], const int A[], const B[], int n)
{
int i,j;
int d;
__int64 T;
 
Zero(C,n);
 
for (i=0; i<=n; i++)
{
        d=0;
        for (j=0; j<n; j++)
        {
                T = (__int64)A[i]*B[j]+d;
                C[i+j]=LoDigit (T);
                d= HiDigit (T);
        }
        C[i+j]=d;
}
for (i=0; i<=n; i++) Form1->LabeledEdit1->Text=Form1->LabeledEdit1->Text+IntToStr(A[i]);
for (i=0; i<=n; i++) Form1->LabeledEdit2->Text=Form1->LabeledEdit2->Text+IntToStr(B[i]);
for (i=0; i<=n; i++) Form1->LabeledEdit3->Text=Form1->LabeledEdit3->Text+IntToStr(C[i])+";";
}
 
void ClearAllForm()
{
Form1->RichEdit1->Clear();
Form1->LabeledEdit1->Clear();
Form1->LabeledEdit2->Clear();
Form1->LabeledEdit3->Clear();
Form1->LabeledEdit4->Clear();
}
//------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
ClearAllForm();
int a[]={2,2,9}, b[]={1,2,9},c[]={1,2,2,3};
Form1->LabeledEdit4->Text=IntToStr(Add(c,a,b,2));
 
}
//---------------------------------------------------------------------------
 
void __fastcall TForm1::Button2Click(TObject *Sender)
{
ClearAllForm();
int a[]={2,2,8}, b[]={1,2,9},c[]={1,2,2,3};
Form1->LabeledEdit4->Text=IntToStr(Sub(c,a,b,2));
}
//---------------------------------------------------------------------------
 
void __fastcall TForm1::Button3Click(TObject *Sender)
{
ClearAllForm();
int a[]={2,2,9}, b[]={1,2,9};
Form1->LabeledEdit4->Text=IntToStr(Cmp(a,b,2));
}
 
void __fastcall TForm1::FormCreate(TObject *Sender)
{
Form1->Label1->Caption="Длина машинного слова m="+IntToStr(m)+" Количество цифр n=" + IntToStr(n);
}
//---------------------------------------------------------------------------
 
void __fastcall TForm1::Button4Click(TObject *Sender)
{
int a[]={2,2,9}, b[]={1,2,9},c[]={1,2,3,4,5,6,7,8,9};
Mul (c,a,b,n);
}
//---------------------------------------------------------------------------

Выдает ошибку: [Linker Error] Unresolved external 'Zero(int *, int)' referenced from D:\PROGRAM FILES\BORLAND\CBUILDER6\BIN\3410_ARIFMETIKA\UNIT1_MATH.OBJ
Как понял, проблемы с областью видимости функции zero. Что надо исправить?

@*bkmz · 21.10.2008, 12:43

Я возможно не по теме, но все же. У меня аналогичный курсовик (Реализация ГОСТ 34.10-94).
Вопрос к IS, у тебя есть нормальный вариант этого ГОСТа? Просто все что я находил в интернете содержит ошибки, да и из текста становится понятно, что некоторые операции написаны неверно.

@Lord_Voodoo · 21.10.2008, 12:57

*bkmz, вот бери его исходник и подгоняй под себя, а то на все готовенькое попасть - это же жутко скучно... а покой нам только снится

IS, где реализация функции zero? я что-то так и не нашел в твоем листинге...

@IS · 21.10.2008, 12:59 **[ТС]**

*bkmz, Свой гост брал на http://protect.gost.ru/, но сейчас что-то глючит.
реализация описана http://slil.ru/26253351 - Щербаков, Домашев Прикладная криптография. Но, как видешь, пока не могу заставить работать арифметические операции. Может у тебя получится. Если заработает, то сообщи.

@*bkmz · 21.10.2008, 13:19

Сообщение от WooDooMan

*bkmz, вот бери его исходник и подгоняй под себя, а то на все готовенькое попасть - это же жутко скучно... а покой нам только снится

Возможно был неправильно вопрос мой понят, мне не нужны исходники, а нужен нормальный текст ГОСТа. Что касается исходников, то я пишу все сам.

Свой гост брал на http://protect.gost.ru/, но сейчас что-то глючит.

Не получилось щас найти там 34.10. Наверно глючит... Буду искать.

Но, как видешь, пока не могу заставить работать арифметические операции. Может у тебя получится. Если заработает, то сообщи.

Я к счастью лишен этой проблемы благодаря замечательному (IMHO) классу java.math.BigInteger

@Lord_Voodoo · 21.10.2008, 13:28

IS, блин, да что там непонятно, у тебя нет реализации функции зеро, просто ее прототип и вызов в теле программы... напиши реализацию этой функции и будет тебе счастье

*bkmz, просто тут слишком часто просят именно сырцы... вот и поэтому я так тебе ответил, ничего личного...

@IS · 21.10.2008, 14:52 **[ТС]**

WooDooMan, Извиняюсь, просто не заметил, что появилась вторая страница и я решил, что сообщение не отправилось.
Теперь к делу. Действительно, нет реализации - у авторов эта функция так и приводится без реализации, не ясно за чем. Реализацию добавил.

C++

void Zero (int A[], int n)
{
for (int i=0; i<n; i++) A[i]=0;
};

С остальными разберусь.
Вопросы:
1) Что должен делать макрос #define MaxDigit ((int)(-1));?
2) Как определить количество элементов в массиве?

@*bkmz · 21.10.2008, 15:08

WooDooMan, да ничего страшного, понимаю..

@IS 13 / 13 / 2 Регистрация: 01.10.2008 Сообщений: 116
	21.10.2008, 12:59 [ТС]	16
	*bkmz, Свой гост брал на http://protect.gost.ru/, но сейчас что-то глючит. реализация описана http://slil.ru/26253351 - Щербаков, Домашев Прикладная криптография. Но, как видешь, пока не могу заставить работать арифметические операции. Может у тебя получится. Если заработает, то сообщи. 0

@IS 13 / 13 / 2 Регистрация: 01.10.2008 Сообщений: 116
		1
	ГОСТ 3410 / Работа с длинными числами 01.10.2008, 12:20. Показов 17701. Ответов 75 Метки нет (Все метки) Начал делать курсовик по реализации ЭЦП по ГОСТ 34.10 (и соответственно 34.11 и 28147 ). В качестве среды разработки выбрал C++ Builder. Возник вопрос: Как работать с большими числами размером в 256,512,1024 бит? Они, ведь, ни в один тип данных не лезут (int только 32 бита). В контрольком примере дано число 57896044618658097711785492504343953926634992332820282019728792003956564821041. P.S Чужая реализация 3410-01 Но, есть сильное подозрение а то, что препода "кинули" - подсунили ему в место ГОСТ 3410-2001, забугорский ECDSA. Мой курсовик: Недостатки: 1) Результат проверки не совпадает с генерированой подписью. Проблема в математике. 2) Нет создания хэша функции по ГОСТ 3411 3) Нет вычисленя параметров ЭК. 4) Длительное время работы (прога не зависла - она считает) 0

@Lord_Voodoo Супер-модератор 8783 / 2536 / 144 Регистрация: 07.03.2007 Сообщений: 11,873
	01.10.2008, 13:23	2
	есть арифметика длинных чисел, почитай С. Оклов "Программирование в алгоритмах" 0

@IS 13 / 13 / 2 Регистрация: 01.10.2008 Сообщений: 116
	06.10.2008, 18:11 [ТС]	3
	А нельзя просто выделить память под переменную в 256 бит? 0

@Lord_Voodoo Супер-модератор 8783 / 2536 / 144 Регистрация: 07.03.2007 Сообщений: 11,873
	06.10.2008, 18:14	4
	ну так в один бит ты как цифру записать собрался? глянь типы данных, там по-любому есть тип, который в себя вместит число, просто с помощью арифметики длинных числе можно реализовать быстрые алгоритмы для работы с такими числами 0

@IS 13 / 13 / 2 Регистрация: 01.10.2008 Сообщений: 116
	20.10.2008, 10:30 [ТС]	5
	Нашел материал по работе с длинными числами - Щербаков, Домашев Прикладная криптография. Но, к сожалению не могу заставить работать хотя бы первый алгоритм сложения - не выполняется перенос разряда. В чем проблема? http://slil.ru/26253252 - все о госте http://slil.ru/26253265 - не работающая прога http://slil.ru/26253351 - Щербаков, Домашев Прикладная криптография 0

@Lord_Voodoo Супер-модератор 8783 / 2536 / 144 Регистрация: 07.03.2007 Сообщений: 11,873
	20.10.2008, 20:21	8
	(__int64) - это приведение типа, LoDigit(T) - возвращает младшие 4 байта HiDigit(T) - старшие 4 байта, чар используется для того, чтобы был один байт... ну а вообще - алгоритм прост... иммитация сложения столбцом... только человек эффективнее использует элементы массива, в отличии от моего алгоритма... да и по-хорошему, ты бы мог и потрассировать алгоритм, тогда будет видно, что там и зачем делается 1

@IS 13 / 13 / 2 Регистрация: 01.10.2008 Сообщений: 116
	20.10.2008, 20:35 [ТС]	9
	1) Спасибо 2) Как работает #define HiDigit(T) ((int)((T)>>m))? Сам понял, что число T помещается в поток, а ((int)((T)>>m)) что делает? За счет, чего помещается в старшие 4 байта. 3) Почему при сложении int a[]={2,2,9} и b[]={1,2,9} получается С[i]={3,4,18} т.е нет переноса. 4) Трассировку хорошо бы сделать, но не ясно как. В меню Run можно выполнить только команду Run, а по шагам нельзя. 0

@Lord_Voodoo Супер-модератор 8783 / 2536 / 144 Регистрация: 07.03.2007 Сообщений: 11,873
	20.10.2008, 21:31	10
	>> - это в данном случае сдвиг на 32 бита ну так при выводе будет 1843... а переполнение - это когда число больше байта будет по идее... 0

@Lord_Voodoo Супер-модератор 8783 / 2536 / 144 Регистрация: 07.03.2007 Сообщений: 11,873
	21.10.2008, 10:45	12
	прототип Zero описан, даже есть вызов функции, ну а где же ее реализация-то? 0

@*bkmz 1 / 1 / 0 Регистрация: 21.10.2008 Сообщений: 25
	21.10.2008, 12:43	14
	Я возможно не по теме, но все же. У меня аналогичный курсовик (Реализация ГОСТ 34.10-94). Вопрос к IS, у тебя есть нормальный вариант этого ГОСТа? Просто все что я находил в интернете содержит ошибки, да и из текста становится понятно, что некоторые операции написаны неверно. 0

@Lord_Voodoo Супер-модератор 8783 / 2536 / 144 Регистрация: 07.03.2007 Сообщений: 11,873
	21.10.2008, 12:57	15
	*bkmz, вот бери его исходник и подгоняй под себя, а то на все готовенькое попасть - это же жутко скучно... а покой нам только снится IS, где реализация функции zero? я что-то так и не нашел в твоем листинге... 0

@*bkmz 1 / 1 / 0 Регистрация: 21.10.2008 Сообщений: 25
	21.10.2008, 13:19	17
	Сообщение от WooDooMan *bkmz, вот бери его исходник и подгоняй под себя, а то на все готовенькое попасть - это же жутко скучно... а покой нам только снится Возможно был неправильно вопрос мой понят, мне не нужны исходники, а нужен нормальный текст ГОСТа. Что касается исходников, то я пишу все сам. Свой гост брал на http://protect.gost.ru/, но сейчас что-то глючит. Не получилось щас найти там 34.10. Наверно глючит... Буду искать. Но, как видешь, пока не могу заставить работать арифметические операции. Может у тебя получится. Если заработает, то сообщи. Я к счастью лишен этой проблемы благодаря замечательному (IMHO) классу java.math.BigInteger 0

@Lord_Voodoo Супер-модератор 8783 / 2536 / 144 Регистрация: 07.03.2007 Сообщений: 11,873
	21.10.2008, 13:28	18
	IS, блин, да что там непонятно, у тебя нет реализации функции зеро, просто ее прототип и вызов в теле программы... напиши реализацию этой функции и будет тебе счастье *bkmz, просто тут слишком часто просят именно сырцы... вот и поэтому я так тебе ответил, ничего личного... 0

@*bkmz 1 / 1 / 0 Регистрация: 21.10.2008 Сообщений: 25
	21.10.2008, 15:08	20
	WooDooMan, да ничего страшного, понимаю.. 0