Блок-схема алгоритма нахождения простых чисел не превышающих N
Блок-схема реализации алгоритма RSA
Листинг программы
#include <vcl.h>
#pragma hdrstop
#include "Unit1.h"
#include <math.h>
#pragma package(smart_init)
#pragma resource "*.dfm"
using namespace std;
TForm1 *Form1;
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
void __fastcall TForm1::Button2Click(TObject *Sender)
{
Close();
}
void __fastcall TForm1::Button1Click(TObject *Sender)
{
Log->Lines->Clear();
srand( GetTickCount() );
// Ввод P и Q
int p = StrToInt( Edit1->Text );
int q = StrToInt( Edit2->Text );
Log->Lines->Add( "p = " + IntToStr( p ) );
Log->Lines->Add( "q = " + IntToStr( q ) );
// Вычисление N
int N = p * q;
Log->Lines->Add( "N = p*q = " + IntToStr( N ) );
// Вычисление f(N)
int f = (p-1)*(q-1);
Log->Lines->Add( "f(n)=(p-1)(q-1) = " + IntToStr( f ) );
// Ввод открытого ключа K1
int k1 = StrToInt( edtOK->Text );
Log->Lines->Add( "k1 = " + IntToStr( k1 ) );
// Проверка условий существования открытого ключа
if( NOD( k1, f ) != 1 )
{
Log->Lines->Add( "открытый ключ и f(n) не взаимно простые. введите новые параметры" );
return;
}
// Нахождение секретного ключа
int k = ObrElem( k1, f );
Log->Lines->Add( "k = k1^(-1) mod f(n) = " + IntToStr( k ) );
AnsiString clear = Edit3->Text;
AnsiString coded;
// Шифрование и расшифрование сообщения
coded = "";
int *clear_c = new int[clear.Length()];
int *coded_c = new int[clear.Length()];
int *clr_c = new int[clear.Length()];
for( int i = 1; i <= clear.Length(); i++ )
{
clear_c[i-1] = (int)clear[i];
coded_c[i-1] = ModStep( clear_c[i-1], k1, N );
clr_c[i-1] = ModStep( coded_c[i-1], k, N );
|
|
char temp[256];
wsprintf( temp, "%c = %c = %c", clear[i], (char)coded_c[i-1], (char)clr_c[i-1] );
Log->Lines->Add( temp );
wsprintf( temp, "%c", (char)coded_c[i-1] );
coded += temp;
}
delete[] clr_c;
delete[] coded_c;
delete[] clear_c;
// Вывод полученных результатов
Log->Lines->Add( "clear text = " + clear );
Log->Lines->Add( "coded text = " + coded );
Log->Lines->Add( "" );
}
// Модуль нохождения НОД (a, b)
int __fastcall TForm1::NOD(int a, int b)
{
if( ( a == 0 )||( b == 0 ) )
{
return abs( a + b );
}
while( a != b )
{
if( a > b )
{
a -= b;
}
else
{
b -= a;
}
}
return b;
}
//Модуль нахождения обратного элемента по модулю N
int __fastcall TForm1::ObrElem(int a, int N)
{
int u1 = 0, u2 = 1, u3 = N;
int v1 = 1, v2 = 0, v3 = a;
int t1, t2, t3, q;
while(u3 != 1)
{
q = u3 / v3;
t1 = u1 - v1*q;
t2 = u2 - v2*q;
t3 = u3 - v3*q;
u1 = v1;
u2 = v2;
u3 = v3;
v1 = t1;
v2 = t2;
v3 = t3;
}
return u1 < 0 ? u1 + N : u1;
}
// Модуль возведения числа в степень по модулю N
int __fastcall TForm1::ModStep(int a, int d, int n)
{
int aBmodN = a;
int dtemp = d;
AnsiString binary = "";
while( dtemp > 1 )
{
binary += IntToStr( dtemp % 2 );
dtemp = floor( dtemp / 2 );
}
binary += dtemp;
for( int i = 1; i < binary.Length(); i++ )
{
aBmodN = aBmodN*aBmodN * ( binary[binary.Length() - i] == '0' ? 1 : a ) % n;
}
return aBmodN;
}
void __fastcall TForm1::Button3Click(TObject *Sender)
{
int q = 0;
int p = 0;
|
|
int *a = new int[256];
prost( a, 64 );
srand( GetTickCount() );
while( ( p == 0 )||( p > 64 ) )
{
p = a[ rand() % 64-1 ];
}
while( ( q == 0 )||( q > 64 ) )
{
q = a[ rand() % 64-1 ];
}
Edit1->Text = FloatToStr( p );
Edit2->Text = FloatToStr( q );
delete[] a;
}
// Модуль нахождения простых чисел на превышающих N методом решета Эратосфера
void __fastcall TForm1::prost( int *a, int n )
{
int b, c;
for( b = 1; b <= n; b++ )
{
a[b] = b;
}
for( b = 2; b <= floor( sqrt( n ) ); b++ )
{
c = 0;
c += ( b << 1 );
while( c <= n )
{
a[c] = 0;
c += b;
}
}
}
Цитированная литература
1. Бухштаб А. А. Теория чисел – М: Наука, 1975 г.
2. Айерленд К. Классическое введение в современную теорию чисел. М: Мир, 1987.
3. Акушинский И. Л., Юдицкий Д. И. Машинная арифметика в остаточных классах. – М. Советское радио, 1968.
4. Амербаев В. М. Теоретические основы мащинной арифметики, - Алма –Ата: Наука, 1976.
5. Червяков Н. И. Применение нейронных сетей для прямого и обратного преобразования кодов в СОК. Вестник СГУ, Физ.-мат. науки, 1999.
6. Червяков Н. И. Применение системы остаточных классов в цифровых системах обработки и передачи информации. – Ставрополь: СВВиУС, 1984.
7. Червяков Н. И. Преобразование цифровых позиционных и непозиционных кодов в системах управления и связи. – Ставрополь: СВВиУС, 1985.
|
|
8. Коляда А. А., Пак И. Т. Модулярные структуры конвейерной обработки цифровой информации, - Минск: Университетское, 1992.
9. Онищенко С. М. Применение гиперкомплексных чисел в теории инерциальной навигации. Автономные системы, - Киев: Наукова думка, 1983.
Дата добавления: 2019-07-15; просмотров: 435; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!