Программная система "Обеспечение безопасности электронного документооборота"

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

"Оренбургский государственный университет"

Факультет информационных технологий

Кафедра программного обеспечения вычислительной техники и автоматизированных систем

ОГУ 230105.65.4014.062 О

Курсовой проект

Программная система "Обеспечение безопасности электронного документооборота"

Руководитель

Цыганков А.С.

Исполнитель

студент группы з-10ПОВТ(у)

Майборода З.П.

Оренбург 2014



Содержание

Введение

1. Постановка задачи

2. Теоретические предпосылки

2.1 Алгоритм RSA

2.1 Ассиметричные алгоритмы

3. Руководство пользователя

Заключение

Список использованных источников

Приложение А



Введение

Целью данной курсовой работы являлось написание программной системы, формирующей виртуальные защищенные каналы передачи данных, на языке программирования C# при помощи программного средства Visual Studio 2010. Написание программной системы осуществлялось с использованием классов т.д.

Задачами данной курсовой работы являлось повторение и закрепление полученных знаний, приобретенных во время занятий по дисциплине "Методы и средства защиты информации".

1. Постановка задачи

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

Программа должны выполнять следующие функции:

1. Генерация ключей для метода RSA, с сохранением в файл.

Размер ключа 32 бита (p и q, integer p и q берем длиной 32 бита).

Верхний порог генерации - 232

Нижний порог генерации - 231

Число длиной 32 бита

е - произвольно (3, 17…)

2. Шифрование файлов.

С помощью сгенерированных ранее ключей, с сохранением в файл (на форме показывать не надо, просто в новый файл).

3. Расшифрование с сохранением в файл.

Если ключ неправильный, то программа должна выдать зашифрованное.



2. Теоретические предпосылки

2.1 Алгоритм RSA

Алгоритм RSA стоит у истоков асимметричной криптографии. Он был предложен тремя исследователями-математиками Рональдом Ривестом (R. Rivest), Ади Шамиром (A. Shamir) и Леонардом Адльманом (L. Adleman) в 1977-78 годах.

Первым этапом любого асимметричного алгоритма является создание пары ключей: открытого и закрытого и распространение открытого ключа "по всему миру". Для алгоритма RSA этап создания ключей состоит из следующих операций:

1 Выбираются два простых (!) числа p и q.

2 Вычисляется их произведение n(=p*q).

3 Выбирается произвольное число e (e<n), такое, что НОД(e, (p-1)(q-1))=1, то есть e должно быть взаимно простым с числом (p-1)(q-1).

4 Методом Евклида решается в целых числах (!) уравнение e*d+(p-1)(q-1)*y=1. Здесь неизвестными являются переменные d и y - метод Евклида как раз и находит множество пар (d, y), каждая из которых является решением уравнения в целых числах.

5 Два числа (e, n) - публикуются как открытый ключ.

6 Число d хранится в строжайшем секрете - это и есть закрытый ключ, который позволит читать все послания, зашифрованные с помощью пары чисел (e, n).

Как же производится собственно шифрование с помощью этих чисел:

1 Отправитель разбивает свое сообщение на блоки, равные k=[log2(n)] бит, где квадратные скобки обозначают взятие целой части от дробного числа.

2 Подобный блок, как Вы знаете, может быть интерпретирован как число из диапазона (0; 2k-1). Для каждого такого числа (назовем его mi) вычисляется выражение ci=((mi)e)mod n. Блоки ci и есть зашифрованное сообщение Их можно спокойно передавать по открытому каналу, поскольку операция возведения в степень по модулю простого числа, является необратимой математической задачей. Обратная ей задача носит название "логарифмирование в конечном поле" и является на несколько порядков более сложной задачей. То есть даже если злоумышленник знает числа e и n, то по ci прочесть исходные сообщения mi он не может никак, кроме как полным перебором mi.

А вот на приемной стороне процесс дешифрования все же возможен, и поможет нам в этом хранимое в секрете число d. Достаточно давно была доказана теорема Эйлера, частный случай которой утверждает, что если число n представимо в виде двух простых чисел p и q, то для любого x имеет место равенство (x(p-1)(q-1))mod n =1. Для дешифрования RSA-сообщений воспользуемся этой формулой. Возведем обе ее части в степень (-y):

(x(-y)(p-1)(q-1))mod n =1(-y)=1.

Теперь умножим обе ее части на x:

(x(-y)(p-1)(q-1)+1)mod n =1*x=x.

А теперь вспомним как мы создавали открытый и закрытый ключи. Мы подбирали с помощью алгоритма Евклида d такое, что e*d+(p-1)(q-1)*y=1, то есть e*d=(-y)(p-1)(q-1)+1. А следовательно в последнем выражении предыдущего абзаца мы можем заменить показатель степени на число (e*d). Получаем (xe*d)mod n=x. То есть для того чтобы прочесть сообщение ci=((mi)e)mod n достаточно возвести его в степень d по модулю m:

((ci)d)mod n = ((mi)e*d)mod n = mi.



На самом деле операции возведения в степень больших чисел достаточно трудоемки для современных процессоров, даже если они производятся по оптимизированным по времени алгоритмам. Поэтому обычно весь текст сообщения кодируется обычным блочным шифром (намного более быстрым), но с использованием ключа сеанса, а вот сам ключ сеанса шифруется как раз асимметричным алгоритмом с помощью открытого ключа получателя и помещается в начало файла.

2.2 Ассиметричные алгоритмы

Ассиметричное шифрование предполагает наличие двух ключей. Первый ключ - открытый (public) - распространяется совершенно свободно, без всяких мер предосторожности, а второй - закрытый,личный (private), нужно держать в секрете. Любое сообщение, зашифрованное с использованием одного из этих ключей, может быть расшифровано только с использованием второго ключа. Как правило, отправитель сообщения пользуется открытым ключом получателя, а получатель - своим личным.

В ассиметричной схеме шифрования оба ключа являются производными от единого порождающегомастер-ключа (master-key), как это показано на рис. 6. Когда два ключа сформированы на основе одного, они зависимы в математическом смысле, но ни один из них не может быть вычислен на основе другого. После того, как вычислены оба ключа, мастер-ключ уничтожается и таким образом пресекается любая попытка восстановить в дальнейшем значения производных от него ключей.



Рисунок 1 - Схема ассиметричного шифрования

Идея асимметричных алгоритмов тесно связана с развитием теории односторонних функций и с теорией сложности. Под односторонней функцией мы будем понимать легковычисляемое отображение f(x): X Y, x X, при этом обратное отображение является сложной задачей. Она называется трудновычисляемой, если нет алгоритма для ее решения с полиномиальным временем работы. Легковычисляемой будем называть задачу, имеющую алгоритм со временем работы, представленным в виде полинома низкой степени относительно входного размера задачи, а еще лучше алгоритм с линейным временем работы.

Развитием идеи односторонних функций явилось построение односторонних функций с секретом (с потайным ходом). Такой функцией называется f(x) = y8, значение которой, как и в предыдущем случае, легко вычислить, тогда как обратное значение без знания некоторого секрета трудно вычислить. Знание же секрета позволяет достаточно просто реализовывать операцию обращения односторонних функций с секретом. На практике при применении асимметричного алгоритма шифрования в роле секретного ключа выступает само знание секрета, а в роле открытого ключа - знание процедуры вычисления односторонней функции с секретом.

Вместе с тем необходимо отметить, что стойкость большинства современных асимметричных алгоритмов базируется на двух математических проблемах, которые на данном этапе являются трудновычисляемыми даже для метода "грубой силы":

· дискретное логарифмирование в конечных полях;

· факторизация больших чисел.

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

Самым распространенным алгоритмом асимметричного шифрования является алгоритм RSA, названный по первым буквам имен его создателей (Rivest, Shamir, Adleman). Разработчиком данного алгоритма удалось эффективно воплотить идею односторонних функций с секретом. Стойкость RSA базируется на сложности факторизации больших целых чисел.

Алгоритм Евклида нахождения наибольшего общего делителя основывается на следующей теореме (приводим без доказательства).

Для любого неотрицательного числа X и любого положительного числа Y справедливо следующее:

gcd (X, Y) = gcd (Y, X mod Y),

где X>Y>0.

Чтобы определить наибольший общий делитель, приведенное выше равенство (1) необходимо использовать многократно (до получения значения Y = 0). Ниже приводится раскрытая запись

gcd (X, Y) = gcd (Y, X mod Y) = gcd (Y, X - (лX/Yы - целое частное) ґ Y)).



3. Руководство пользователя

Для запуска серверного приложения программы необходимо запустить файл "RSA.exe".

В появившемся окне можно выполнить следующие действия:

· Сгенерировать числа

· Сохранить и загрузить из файла

· Зашифровать

· Расшифровать

Рисунок 2 - Главное окно

Для генерации числа нужно нажать "Генерировать". Произойдет генерация ключей методом RSA с сохранением в файл.

При нажатие на кнопку "Зашифровать" и "Расшифровать" появляется окно, где нужно открыть файл ранее сгенерированный и сохраненный.



Рисунок 3 - Шифрование файла



Заключение

В ходе проделанной курсовой работы была написана программная система, формирующая виртуальные защищенные каналы передачи данных, на языке программирования C# при помощи программного средства Visual Studio 2010. Написание программной системы осуществлялось с использованием классов т.д.

Во время выполнения расчетно-графического задания было осуществлено закрепление и повтор теоретических и практических знаний, полученных на занятиях, при изучении дисциплины "Методы и средства защиты информации".



Список используемых источников

1. Троелсен Э. С# и платформа .NET. Библиотека программиста. - СПб.: Питер, 2004. -- 796 с.: ил.

2. Фаронов В.В. Программирование на языке C# - СПб.: Питер, 2007. -- 240 с.: ил.

3. Селентьева И.В. Программирование на языке высокого уровня, С# 2001 г. - 460 с.

4. Вильямс Книга C# 3.0: руководство для начинающих Герберта Шилдта 2005 г. - 330 с.

5. СТО 02069024.101-2010. Стандарт организации. Работы студенческие. Общие требования и правила оформления. Режим доступа: http://www.osu.ru/doc/381

6. Орлов С.А. Технология разработки программного обеспечения. - Спб.: Питер, 2002 - 464 с.

7. Пауэрс Л. Microsoft Visual Studio 2010 / Л. Пауэрс, М. Снелл: Пер. с англ. - СПб.: БХВ-Петербург, 2010. - 1200 с.: ил.

8. Либерти, Д.: Программирование на C#.-Пер. с англ..- СПб:Символ-Плюс, 2003.- 688с.

9. Петцольд Ч. Программирование для Microsoft Windows на C#. В 2-х томах, Том 1-2. - Пер. с англ. - М: Издательско-торговый дом "Русская редакция", 2002

10. Марченко А.Л. Основы программирования на C# 2.0 - М.: "Интернет-университет информационных технологий - ИНТУИТ.ру”, "БИНОМ. Лаборатория знаний” - 2007 г. - 552 стр.



Приложение А

(обязательное)

Текст программы

Unit1.cpp

#include <vcl.h>

#include <math.h>

#include <stdio.h>

#include <io.h>

#include <time.h>

#pragma hdrstop

#include "Unit1.h"

#include "RSAutil.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma resource "*.dfm"

TForm1 *Form1;

//---------------------------------------------------------------------------

__fastcall TForm1::TForm1(TComponent* Owner)

: TForm(Owner)

{

srand(time(NULL)); // Инициализация генератора случайных чисел

}

//---------------------------------------------------------------------------

void __fastcall TForm1::ButtonGenerateClick(TObject *Sender)

{

rsaPublicKey pubKey;

rsaPrivateKey privKey;

rsaGenerate(&pubKey, &privKey);

EditE->Text = IntToStr(pubKey.e);

EditN->Text = IntToStr(pubKey.n);

EditD->Text = IntToStr(privKey.d);

EditN2->Text = IntToStr(privKey.n);

btnPublicSave->Enabled = true;

btnPrivateSave->Enabled = true;

StatusBar1->SimpleText = "Ключи RSA сгенерированы";

}

//---------------------------------------------------------------------------

void __fastcall TForm1::btnPublicSaveClick(TObject *Sender)

{

if ( !SaveDialogPublicKeys->Execute() ) return;

AnsiString fname = SaveDialogPublicKeys->FileName;

if ( fname.SubString(fname.Length()-3, 4).LowerCase() != ".pbk" )

fname += ".pbk";

FILE *f = fopen(fname.c_str(), "wb");

if ( !f ) { // Файл не открылся

StatusBar1->SimpleText = "Ошибка открытия файла "+fname;

return;

}

Int32 e = atol(EditE->Text.c_str());

Int64 n = _atoi64(EditN->Text.c_str());

fwrite(&e, sizeof(Int32), 1, f);

fwrite(&n, sizeof(Int64), 1, f);

fclose(f);

StatusBar1->SimpleText = "Открытый ключ записан в файл "+fname;

}

//---------------------------------------------------------------------------

void __fastcall TForm1::btnPublicLoadClick(TObject *Sender)

{

if ( !OpenDialogPublicKeys->Execute() ) return;

FILE *f = fopen((OpenDialogPublicKeys->FileName).c_str(), "rb");

if ( !f ) { // Файл не открылся

StatusBar1->SimpleText = "Ошибка открытия файла "+ OpenDialogPublicKeys->FileName;

return;

}

Int32 e;

Int64 n;

fread(&e, sizeof(Int32), 1, f);

fread(&n, sizeof(Int64), 1, f);

fclose(f);

EditE->Text = IntToStr(e);

EditN->Text = IntToStr(n);

StatusBar1->SimpleText = "Открытый ключ загружен";

}

//---------------------------------------------------------------------------

void __fastcall TForm1::btnPrivateSaveClick(TObject *Sender)

{

if ( !SaveDialogPrivateKeys->Execute() ) return;

AnsiString fname = SaveDialogPrivateKeys->FileName;

if ( fname.SubString(fname.Length()-3, 4).LowerCase() != ".prk" )

fname += ".prk";

FILE *f = fopen(fname.c_str(), "wb");

if ( !f ) { // Файл не открылся

StatusBar1->SimpleText = "Ошибка открытия файла "+fname;

return;

}

Int64 d = _atoi64(EditD->Text.c_str());

Int64 n = _atoi64(EditN2->Text.c_str());

fwrite(&d, sizeof(Int64), 1, f);

fwrite(&n, sizeof(Int64), 1, f);

fclose(f);

StatusBar1->SimpleText = "Закрытый ключ записан в файл "+fname;

}

//---------------------------------------------------------------------------

void __fastcall TForm1::btnPrivateLoadClick(TObject *Sender)

{

if ( !OpenDialogPrivateKeys->Execute() ) return;

FILE *f = fopen((OpenDialogPrivateKeys->FileName).c_str(), "rb");

if ( !f ) { // Файл не открылся

StatusBar1->SimpleText = "Ошибка открытия файла "+ OpenDialogPrivateKeys->FileName;

return;

}

Int64 d;

Int64 n;

fread(&d, sizeof(Int64), 1, f);

fread(&n, sizeof(Int64), 1, f);

fclose(f);

EditD->Text = IntToStr(d);

EditN2->Text = IntToStr(n);

StatusBar1->SimpleText = "Закрытый ключ загружен";

}

//---------------------------------------------------------------------------

void __fastcall TForm1::btnEncryptClick(TObject *Sender)

{

if ( EditE->Text.IsEmpty() ) {

StatusBar1->SimpleText = "Не задана открытая экспонента e";

return;

}

if ( EditN->Text.IsEmpty() ) {

StatusBar1->SimpleText = "Не задан модуль n";

return;

}

rsaPublicKey pubKey;

pubKey.e = atol(EditE->Text.c_str());

pubKey.n = _atoi64(EditN->Text.c_str());

if ( !OpenDialogEncrypt->Execute() ) return;

FILE *f = fopen(OpenDialogEncrypt->FileName.c_str(), "rb");

if ( !f ) { // Файл не открылся

StatusBar1->SimpleText = "Ошибка открытия файла "+ OpenDialogEncrypt->FileName;

return;

}

FILE *g = fopen((OpenDialogEncrypt->FileName+".enc").c_str(), "wb");

if ( !g ) { // Файл не открылся

StatusBar1->SimpleText = "Ошибка создания файла "+ OpenDialogEncrypt->FileName+".enc";

fclose(f);

return;

}

Int32 m; // Считанное сообщение

Int32 me; // Зашифрованное сообщение

int r; // Счетчик считанных битов

ProgressBarEncrypt->Max = filelength(fileno(f))/sizeof(Int32);

ProgressBarEncrypt->Position = 0;

while (!feof(f)) {

r = fread(&m, 1, sizeof(Int32), f);

if ( r < sizeof(Int32) ) { // Последние байты, которых меньше 4, пишем без шифрации

fwrite(&m, 1, r, g);

break;

}

me = rsaEncrypt(m, &pubKey);

fwrite(&me, 1, r, g);

ProgressBarEncrypt->StepIt();

}

fclose(f);

fclose(g);

ProgressBarEncrypt->Position = 0;

StatusBar1->SimpleText = "Файл "+ OpenDialogEncrypt->FileName+" зашифрован";

}

//---------------------------------------------------------------------------

void __fastcall TForm1::btnDecryptClick(TObject *Sender)

{

if ( EditD->Text.IsEmpty() ) {

StatusBar1->SimpleText = "Не задана секретная экспонента d";

return;

}

if ( EditN2->Text.IsEmpty() ) {

StatusBar1->SimpleText = "Не задан модуль n";

return;

}

rsaPrivateKey privKey;

privKey.d = _atoi64(EditD->Text.c_str());

privKey.n = _atoi64(EditN2->Text.c_str());

if ( !OpenDialogDecrypt->Execute() ) return;

AnsiString fname = OpenDialogDecrypt->FileName;

if ( fname.SubString(fname.Length()-3, 4).LowerCase() == ".enc" )

fname = fname.SubString(0, fname.Length()-4);

SaveDialogDecrypt->FileName = fname;

if ( !SaveDialogDecrypt->Execute() ) return;

FILE *f = fopen(OpenDialogDecrypt->FileName.c_str(), "rb");

if ( !f ) { // Файл не открылся

StatusBar1->SimpleText = "Ошибка открытия файла "+ OpenDialogDecrypt->FileName;

return;

}

FILE *g = fopen(SaveDialogDecrypt->FileName.c_str(), "wb");

if ( !g ) { // Файл не открылся

StatusBar1->SimpleText = "Ошибка создания файла "+ OpenDialogEncrypt->FileName+".enc";

fclose(f);

return;

}

Int32 me; // Зашифрованное сообщение

Int32 m; // Расшифрованное сообщение

int r; // Счетчик считанных битов

ProgressBarDecrypt->Max = filelength(fileno(f))/sizeof(Int32);

ProgressBarDecrypt->Position = 0;

while (!feof(f)) {

r = fread(&me, 1, sizeof(Int32), f);

if ( r < sizeof(Int32) ) { // Последние байты, которых меньше 4, пишем без расшифрования

fwrite(&me, 1, r, g);

break;

}

m = rsaDecrypt(me, &privKey);

fwrite(&m, 1, r, g);

ProgressBarDecrypt->StepIt();

}

fclose(f);

fclose(g);

ProgressBarDecrypt->Position = 0;

StatusBar1->SimpleText = "Файл "+ OpenDialogDecrypt->FileName+" расшифрован";

}

//---------------------------------------------------------------------------

RSAutil.cpp

#pragma hdrstop

#include "RSAutil.h"

#include "Numeric.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

// Методы RSA

// Генерация ключей

void rsaGenerate(rsaPublicKey *pubKey, rsaPrivateKey *privKey) {

Int32 p, q, e;

Int64 n, f, d;

e = 3; // Выбираем отрытую экспоненту E

do {

p = RandomPrime(16); // Случайные факторы

q = RandomPrime(16); //

n = (Int64)p*q; // Модуль

f = (Int64)(p-1)*(q-1); // Функция Эйлера

// Проверяем, что E взаимно простое c f

if ( IsSimple(e, f) ) break;

}

while(1);

// Вычисляем секретную экспоненту

d = Inverse(e, f);

pubKey->e = e;

pubKey->n = n;

privKey->d = d;

privKey->n = n;

}

// Шифрование сообщения на открытом ключе

Int32 rsaEncrypt(Int32 m, rsaPublicKey *pubKey) {

Int32 me;

if (m < pubKey->n) {

me = ModPow(m, pubKey->e, pubKey->n);

if ( me < pubKey->n) return me;

return m;

}

else

return m; // Числа меньше модуля не шифруем

}

// Дешифрование сообщения на закрытом ключе

Int32 rsaDecrypt(Int32 c, rsaPrivateKey *privKey) {

if (c < privKey->n)

return ModPow(c, privKey->d, privKey->n);

else

return c; // Числа меньше модуля не расшифровываем

}

RSA.cpp

#include <vcl.h>

#pragma hdrstop

//---------------------------------------------------------------------------

USEFORM("Unit1.cpp", Form1);

//---------------------------------------------------------------------------

WINAPI WinMain(HINSTANCE, HINSTANCE, LPSTR, int)

{

try

{

Application->Initialize();

Application->Title = "Шифрование методом RSA";

Application->CreateForm(__classid(TForm1), &Form1);

Application->Run();

}

catch (Exception &exception)

{

Application->ShowException(&exception);

}

catch (...)

{

try

{

throw Exception("");

}

catch (Exception &exception)

{

Application->ShowException(&exception);

}

}

return 0;

}

Numeric.cpp

#pragma hdrstop

#include <math.h>

#include <limits.h>

#include <stdlib.h>

#include "Numeric.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

// Арифметические алгоритмы

// Расширенный алгоритм Евклида нахождения наибольшего общего делителя чисел A и B

void EGCD(Int64 a, Int64 b, Int64 *u) {

Int64 v[3];

Int64 t[3];

Int64 q;

int i;

// В массив u заносится большее число

u[0] = (a > b ? a : b); u[1] = 1; u[2] = 0;

v[0] = (a > b ? b : a); v[1] = 0; v[2] = 1;

while ( v[0] != 0 ) {

q = u[0] / v[0];

t[0] = u[0] % v[0];

t[1] = u[1] - q*v[1];

t[2] = u[2] - q*v[2];

for ( i = 0; i < 3; i++ ) u[i] = v[i];

for ( i = 0; i < 3; i++ ) v[i] = t[i];

}

// В результате в массиве v будут числа: НОД(a, b), x, y - значения такие, что a*x + b*y = НОД(a, b)

}

// НОД

Int64 GCD(Int64 a, Int64 b) {

Int64 v[3];

EGCD(a, b, v);

return v[0];

}

// Проверка взаимной простоты двух чисел

bool IsSimple(Int64 a, Int64 b) {

Int64 v[3];

EGCD(a, b, v);

if ( v[0] == (Int64) 1 )

return true; // Числа взаимно простые, если НОД = 1

else

return false;

}

// Инверсия C по модулю P

Int64 Inverse(Int64 c, Int64 p) {

Int64 v[3];

EGCD(p, c, v);

if ( v[2] < 0 )

return v[2] + p;

else

return v[2];

}

// Быстрое возведение A в степень X по модулю P

Int64 ModPow(Int64 a, Int64 x, Int64 p) {

Int64 r, b, s;

r = 1;

s = a;

b = 1L; // Устанавливаем бит в 1-ю позицию

while ( b < x ) {

if ( x & b ) { // Если в текущей позиции стоит единица

r = (r * s) % p;

}

s = (s * s) % p;

b *= 2; // Двигаем бит на следующую позицию

}

return r;

}

// Степень двойки

inline Int64 pow2(int t) {

Int64 x = 1;

return (x<<t);

}

// Таблица простых чисел решетом Эратосфена

#define MAXSIEVE 30000 // Размер решета

int *prime; // Таблица найденных чисел

int primeLen = 0; // Длина таблицы

// Просеивание

void Sieve() {

bool isPrime[MAXSIEVE];

int i, j;

for (i=0; i<MAXSIEVE; i++) isPrime[i] = true;

isPrime[0] = isPrime[1] = false;

for ( i = 2; (i*i) < MAXSIEVE; i++ )

if (isPrime[i])

for (int j=i*i; j<MAXSIEVE; j+=i )

isPrime[j] = false;

// Переписываем

for ( i = 2; i<MAXSIEVE;i++ )

if ( isPrime[i] ) primeLen++;

prime = (int *) calloc(primeLen, sizeof(Int32));

j = 0;

for ( i = 2; i<MAXSIEVE;i++ ) {

if ( isPrime[i] ) {

prime[j++] = i;

}

}

}

// Случайное нечетное число длиной k бит

Int64 OddRandom(long k) {

long i;

Int64 mask = 1, n;

k--;

for (i = 1; i <= k; i++)

mask |= 1 << i;

if (k < 16)

n = rand();

else

n = (rand() << 16) | rand();

n |= 1 << k;

n &= mask;

if ((n & 1) == 0) n++;

return n;

}

// Генерация простого числа размером 32 бита методом Маурера

// Взято из книги Handbook of Applied Cryptography. Часть 4. Алгоритм 4.62

Int32 RandomPrime(int k) {

if ( primeLen == 0 ) Sieve(); // Создаем таблицу простых чисел

Int32 p, s;

bool isPrime;

if ( k <= 20 ) { // Поиск случайного простого тривиальным делением, если число k достаточно маленькое

do {

p = OddRandom(k);

s = sqrt(p);

isPrime = true;

for( int i = 0; i < primeLen; i++ ) {

if ( prime[i] > s ) break;

if ( (p % prime[i]) == 0 ) {

isPrime = false;

break;

};

}

if ( isPrime )

break;

} while (true);

}

else { // Рекурсивное построение

double c = 0.1, r;

long m = 20;

long B = c*k*k; // Граница тривиального деления

// Генерируем r - случайное число длиной от k/2 до k-m бит

if (k > 2 * m)

do {

s = rand() / (double) RAND_MAX;

r = pow(2.0, s - 1.0);

} while (k - r * k <= m);

else

r = 0.5;

// Вычисляем простое меньшего размера

Int32 q = RandomPrime(r * k + 1);

Int32 I = floor(pow2(k-1)/(2.0*k));

Int32 R, n, a, b, d;

bool success = false;

while( !success ) {

// Выбираем кандидата в простые в интервале [I+1, 2I]

while(true) {

R = random(I);

if ( R < I) break;

}шифрование виртуальный алгоритм программа

R = R + I + 1;

n = 2*q*R + 1; // n - кандидат

// Проверка тривиальным делением по границе B

for( int i = 0; i < primeLen; i++ ) {

if ( (n % prime[i]) == 0 )

break;

if ( prime[i] >= B ) {

while(true) {

a = random(n-4) + 2;

if ( (a > 1) && (a < (n-1)) ) break;

}

b = ModPow(a, n-1, n);

if ( b == 1 ) {

b = ModPow(a, 2*R, n);

d = GCD(b-1, n);

if ( d == 1 ) {

return n;

}

}

break;

}

};

}

}

return p;

}

Размещено на Allbest.ru