Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Алгоритм електронного цифрового підпису RSA
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2006
Тип роботи:
Лабораторна робота
Предмет:
Інші
Група:
СКС
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет «Львівська політехніка»
Кафедра ЕОМ
Лабораторна робота №3
«Алгоритм електронного цифрового підпису RSA»
Львів-2006
1.Мета: засвоїти алгоритм електронного цифрового підпису RSA.
2.Теоретична частина:
Технологія застосування системи електронного цифрового підпису (ЕЦП) враховує наявність мережі абонентів, що посилають оди одному підписані цифрові документи. Для кожного абонента генерується пара ключів: секретний та відкритий. Секретний ключ зберігається абонентом у таємниці і використовується їм для формування ЕЦП. Відкритий ключ відомий усім іншим користувачам і призначений для перевірки ЕЦП одержувачем підписаного електронного документа.
В алгоритмах ЕЦП, як і в асиметричних системах шифрування, використовується різні математичні схеми, засновані на застосуванні одно направлених функцій. Ці схеми розділяються на дві групи. В основі такого поділу лежать відомі складні обчислювальні задачі:
задача факторизації (розкладання на множники) великих цілих чисел;
задача дискретного логарифмування;
Першою і найбільш відомою у всьому світі конкретною системою ЕЦП стала система RSA, математична схема якого була розроблена у 1977 році в Массачусетскому технологічному інституті США.
Спочатку необхідно обчислити пару ключів (секретний та відкритий). Для цього відправник (автор) електронних документів обчислює два великих простих числа P та Q, потім знаходить їх добуток
і значення функції
.
Далі відправник обчислює число Е з умов:
та число D з умов:
Пара чисел (E,N) є відкритим ключем, який автор передає партнерам по переписці для перевірки його цифрових підписів. Число D зберігається автором як секретний ключ для підпису.
Узагальнена схема формування і перевірки цифрового підпису RSA показана на рис.1.
Рис.1. Узагальнена схема система цифрового підпису RSA
Припустимо, що відправник хоче підписати повідомлення Ь перед його відправкою. Спочатку повідомлення М (блок інформації, файл, таблиця) стискаються з допомогою хеш-функції h(∙) у ціле число m:
m=h(M).
Потім обчислюють цифровий підпис S під електронним документом М, використовуючи хеш-значення m і секретний ключ D:
.
Пара (M,S) передається партнеру-одержувачу як електронний документ М, підписаний цифровим підписом S, причому підпис S сформований власником секретного ключа D.
Після приймання пари (M,S) отримувач обчислює хеш-значення повідомлення М двома різними способами. Насамперед він відновлює хеш-значення m’,застосовуючи криптографічне перетворення підпису S з використанням відкритого ключа Е:
.
Крім того, він знаходить результат хешування прийнятого повідомлення М з допомогою токої ж хеш-функції h(∙):
m=h(M).
Якщо спостерігається рівність обчислених значень, тобто
одержувач признає пару (M,S) дійсною. Доведено, що тільки власник секретного ключа D може сформувати цифровий підпис S по документу M, а визначити секретне число D по відкритому числу E не легше, ніж розкласти модуль N на множники.
Крім того, можна строго математично довести, що результат перевірки цифрового підпису S буде позитивним лише у тому випадку, якщо при обчисленні S був використаний секретний ключ D, що відповідає відкритому ключу E. Тому відкритий ключ E іноді називають «ідентифікатором» того, хто підписався.
Недоліки алгоритму цифрового підпису RSA:
При обчисленні модуля N, ключів E та D для системи цифрового підпису RSA необхідно перевіряти велику кількість додаткових умов, що зробити практично важко. Не виконання будь-якого з цих правил робить можливим фальсифікацію цифрового підпису з боку того, хто виявить таке не виконання. При підписанні важливих документів неможна допускати подібного риску навіть теоретично.
Для забезпечення крипостійкості цифрового підпису RSA по відношенню до спроби фальсифікації на рівні, наприклад, алгоритму шифрування DES, тобто 1018, необхідно використовувати при обчисленнях N,D та E цілі числа не менше 2512 (або біля 10154) кожне, що потребує більших обчислювальних затрат, що перевищують на 20-30% обчислювальні затрати інших алгоритмів цифрового підпису при збереженні того ж рівня крипостійкості.
Цифровий підпис RSA уразливий до так званої мультиплікативної атаки. Інакше кажучи, алгоритм цифрового підпису RSA дозволяє зловмиснику без знання секретного ключа D сформувати підписи під тими документами, в яких результат хешування можна обчислити як добуток хешування вже підписаних документів.
Приклад. Припустимо, що зловмисник може сконструювати три повідомлення М1, М2, М3, в яких хеш-значення
причому
.
Припустимо також, що для двох повідомлень М1 та М2 отримані законні підписи та .
Тоді зловмисник може легко обчислити підпис S3 для документа М3, навіть не знаючи секретного ключа D:
.
Дійсно,
.
Більш надійний і зручний для реалізації на персональних ЕОМ алгоритм цифрового підпису був розроблений у 1984 році американцем арабського походження Тахером Ель Гама лем. В 1991 році НІСТ США обґрунтував перед комісією Конгресу США вибір алгоритма цифрового підпису Ель Гамаля в якості основи для національного стандарта.
3.Текст програми:
//---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#include<math.h>
#include<stdlib.h>
#include <time.h>
#include<fstream.h>
#include<alloc.h>
#include "Main.h"
#include "MD5.cpp"
#include "MD5.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
bool Ed1=false;
bool Ed2=false;
int LowValue=0;
int HighValue=0;
int openKey1,openKey2,closeKey;
unsigned int * de_hash;
unsigned int * signature;
unsigned int * hash;
String Coded,UnCoded;
//---------------------------------------------------------------------------
// Початкові ініціалізації
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{ Blockage();
}
//---------------------------------------------------------------------------
int TForm1::SimpleCalculation(int first, int second)
{ int p,q,n,F,e,d,result=0;
int i=0,r=1;
p=SimpleNum(first,second);
Memo1->Lines->Add("Перше просте число p:");
Memo1->Lines->Add(p);
Edit3->Text=IntToStr(p);
do q=SimpleNum(first,second);
while(q==p);
Memo1->Lines->Add("Друге просте число q:");
Memo1->Lines->Add(q);
Edit4->Text=IntToStr(q);
n=p*q;
openKey2=n;
Memo1->Lines->Add("Їх добуток або один з відкритих ключів n:");
Memo1->Lines->Add(n);
Edit5->Text=IntToStr(n);
F=(p-1)*(q-1);
Memo1->Lines->Add("Обчислюється добуток F=(p-1)*(q-1):");
Memo1->Lines->Add(F);
while(n)
{ n/=10;
i++;
}
while(i!=1)
{ r*=10;
i--;
}
do {
do { e=SimpleNum (r,F);
} while (HCD(F,e)!=1);
openKey1=e;
d=Diafant(e,F,0,1,1,0);
} while((((e*d)%F)!=1)||(d<0));
Memo1->Lines->Add("Другий відкритий ключ e:");
Memo1->Lines->Add(e);
Memo1->Lines->Add("Закритий ключ:");
Memo1->Lines->Add(d);
closeKey=d;
Edit6->Text=IntToStr(e);
Edit7->Text=IntToStr(d);
Button2->Enabled=true;
return result;
}
//---------------------------------------------------------------------------
// Обчислення випадкового числа в межах
int TForm1::SimpleNum(int Low, int High)
{ int r;
int i;
time_t t;
srand((unsigned)time(&t));
while(t)
{ r=rand();
r%=High;
if((r/Low) != 0)
{ for (i=r-1;i>1;i--)
if((r%i)==0)break;
if(i==1) break;
}
}
return r;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{ LowValue=StrToInt(Edit1->Text);
HighValue=StrToInt(Edit2->Text);
if ((LowValue >= 2)&&(HighValue > 2)&&(LowValue<=HighValue))
SimpleCalculation(LowValue, HighValue);
else MessageBox(NULL,"Неправильно введені межі для формування простих чисел!","Помилка",MB_ICONWARNING);
}
//---------------------------------------------------------------------------
int TForm1::HCD(int a, int b)
{ int r0=a;
int r1=b;
int temp;
while(r1!=0)
{
temp=r0%r1;
r0=r1;
r1=temp;
}
return r0;
}
//---------------------------------------------------------------------------
int TForm1::Diafant(int a, int b, int P2, int P1, int Q2, int Q1)
{ int r0,r1;
int q,P,Q,c,y;
static int k=-1;
r0=a;r1=b;
q=r0/r1;
P=q*P1+P2;
Q=q*Q1+Q2;
c=r0%r1;
if (c!=0) { y=Diafant(r1,c,P1,P,Q1,Q); k++; }
else y=Q1*pow(-1,k-1) ;
return y;
}
//---------------------------------------------------------------------------
int* TForm1::encode(int* msg,int length)
{ int* enc;
enc = (int*) calloc(length,sizeof(int));
for(int i = 0; i < length; i++)
enc[i] = LR_bin_exp(msg[i],openKey1,openKey2);
return enc;
}
//----------------------------------------
int* TForm1::decode(int* msg,int length)
{ int *dec;
dec = (int*) calloc(length,sizeof(int));
for(int i = 0; i < length; i++)
dec[i] = LR_bin_exp(msg[i],closeKey,openKey2);
return dec;
}
//----------------------------------------
int TForm1::LR_bin_exp(int x, int n,int m)
{ int test = 0x40000000,y = 1;
for(int i = 30; i >= 0; i--, test >>= 1)
{ y = y * y % m;
if (n & test)
y = y * x % m;
}
return y;
}
//------------------------------------------
void __fastcall TForm1::Button2Click(TObject *Sender)
{ int len,len1;
String str;
unsigned char * InStr;
int * NumStr;
int * EncodeStr;
Button1->Enabled=false;
str=Edit9->Text;
len=str.Length();
md5.MD5initText(str.c_str(),len);
md5.MD5AddLength();
md5.MD5initReg();
md5.MD5transform();
Memo1->Lines->Add("Хеш-код, створений алгоритмом MD5");
Memo1->Lines->Add(transform(md5.GetA()) + transform(md5.GetB()) +
transform(md5.GetC()) + transform(md5.GetD()) );
AnsiString sttr=transform(md5.GetA()) + transform(md5.GetB()) +
transform(md5.GetC()) + transform(md5.GetD()) ;
Edit8->Text=sttr;
len1 = sttr.Length() / 2;
InStr = new unsigned char[2*len1];
NumStr = new int[len1];
EncodeStr = new int[len1];
strncpy( InStr, sttr.c_str(),2*len1);
NumStr = Str2Int(InStr,len1);
EncodeStr = encode(NumStr,len1);
AnsiString tempStr;
for(int i = 0; i < len1; i++)
tempStr += IntToHex(abs(EncodeStr[i]),4) ;
Memo1->Lines->Add("Закодоване повідомлення");
Memo1->Lines->Add(tempStr);
Coded=tempStr;
delete InStr;
delete NumStr;
delete EncodeStr;
Button2->Enabled=false;
Button3->Enabled=true;
}
//---------------------------------------------------------------------------
AnsiString TForm1::transform(unsigned long num)
{ unsigned long temp = 0;
for (int i=0; i < 4; i++)
((char*)(&temp))[i] = ((char*)(&num)) [3-i];
return IntToHex((int)temp,8);
}
//--------------------------------------------------
int* TForm1::Str2Int(const unsigned char * str, int len)
{ int* temp;
temp = new int[len];
char t[3] = {0,0,0};
for(int i = 0; i < len; i++)
{ t[0] = str[2*i];
t[1] = str[2*i+1];
temp[i] = StrToInt("0x" + AnsiString(t));
}
return temp;
}
//--------------------------------------------------
int* TForm1::Trnsf2Hex(unsigned char * str, int len)
{
int* temp;
temp = new int[len];
char t[5] = {0,0,0,0,0};
for(int i = 0; i < len; i++)
{ t[0] = str[4*i];
t[1] = str[4*i+1];
t[2] = str[4*i+2];
t[3] = str[4*i+3];
temp[i] = StrToInt("0x" + AnsiString(t));
}
return temp;
}
//--------------------------------------------------
void __fastcall TForm1::Button3Click(TObject *Sender)
{ unsigned char * InStr2;
int * NumStr;
int * DecodeStr;
int len ;
len = Coded.Length()/4 ;
InStr2 = new unsigned char[4*len];
NumStr = new int[len];
DecodeStr = new int[len];
strncpy(InStr2, Coded.c_str(),4 * len);
NumStr = Trnsf2Hex(InStr2,len);
DecodeStr = decode(NumStr , len);
AnsiString tempStr;
for(int i = 0; i < len; i++)
tempStr += IntToHex(abs(DecodeStr[i]),2) ;
Memo1->Lines->Add("Розкодоване повідомлення");
Memo1->Lines->Add(tempStr);
delete InStr2;
delete NumStr;
delete DecodeStr;
Blockage();
}
//---------------------------------------------------------------------------
// Початок нового сеансу
void __fastcall TForm1::Button4Click(TObject *Sender)
{ UnBlocking();
}
//---------------------------------------------------------------------------
// Блокування всіх контролів
void TForm1::Blockage()
{ UpDown1->Enabled=false;
UpDown2->Enabled=false;
Edit1->Enabled=false;
Edit2->Enabled=false;
Edit9->Enabled=false;
//---Кнопки не доступні------
Button1->Enabled=false;
Button2->Enabled=false;
Button3->Enabled=false;
Button4->Enabled=true;
}
//---------------------------------------------------------------------------
// Розблокування всіх контролів
void TForm1::UnBlocking()
{ Edit1->Text="2";
Edit2->Text="2";
Edit3->Text="";
Edit4->Text="";
Edit5->Text="";
Edit6->Text="";
Edit7->Text="";
Edit8->Text="";
Edit9->Text="";
UpDown1->Enabled=true;
UpDown2->Enabled=true;
Edit1->Enabled=true;
Edit2->Enabled=true;
Edit9->Enabled=true;
//---Кнопки не доступні------
Button1->Enabled=true;
Button2->Enabled=false;
Button3->Enabled=false;
Button4->Enabled=true;
Memo1->Lines->Clear();
}
//---------------------------------------------------------------------------
4.Приклад виконання:
5.Висновок: в процесі виконання лабораторної роботи засвоїла алгоритм електронного цифрового підпису RSA.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора