Алгоритмические языки и программирование

Безопасность алгоритма RSA основана на трудоемкости разложения на множители (факторизации) больших чисел. Открытый и закрытый ключи являются функциями двух больших простых чисел, разрядностью 100-200 десятичных цифр и даже больше. Предполагается, что восстановление открытого текста по шифртексту и открытому ключу равносильно разложению числа на два больших простых множителя.

 

Для генерации двух ключей применяется два больших случайных  простых числа p и q. Для максимальной безопасности p и q должны иметь одинаковую длину.

Рассчитывается произведение n=p*q.

Затем произвольным образом выбирается ключ шифрования e, такой, что е и (p-1)*(q-1) являются взаимно простыми числами. Наконец, с помощью расширенного алгоритма Евклида вычисляется ключ расшифрования d, такой, что:

  , другими словами: .

Заметим что d и n также взаимно простые числа. Числа e и n - открытый ключ, а числа n и d – закрытый. Два простых числа p и q больше не нужны. Они могут быть отброшены но не должны быть раскрыты.

 

Зашифрование:

Расшифрование: .

 

Где m – очередной блок сообщения, с – зашифрованное сообщение, e и n, d и n – открытый и закрытый ключи соответственно.

Точно также сообщение  может быть зашифровано с помощью d, а расшифровано с помощью e. Тут возможен любой выбор.

 

Шифрование RSA выполняется намного быстрее при правильном выборе значения e. Тремя наиболее частыми вариантами являются 3,17,65537.

 

Скорости RSA для различных длин модулей при 8битовом открытом ключе (на SPARCII) представлены в следующей таблице:

 

	512 битов	768 битов	1024 бита
Зашифрование	0,03с	0,05с	0,08с
Расшифрование	0,16с	0,48с	0,93с
Подпись	0,16с	0,52с	0,97с
Проверка	0,02с	0,07с	0,08с

 

 

 

Стойкость алгоритма RSA полностью зависит от трудоемкости решения проблемы разложения на множители больших чисел.

На основании атак на реализации алгоритма RSA, Джудит Мур подытоживает следующие ограничения RSA:

•  Знание одной пары секретного /открытого ключа показателей для данного модуля позволяет взломщику разложить модуль на множители.
• Знание одной пары секретного /открытого показателей для данного модуля позволяет взломщику вычислить другие пары показателей, не разлагая модуль на множители.
• В протоколах сетей связи, применяющих RSA, не должен использоваться общий модуль.
• Для предотвращения вскрытия малого открытого показателя все сообщения должны быть дополнены случайными значениями.
• Секретный показатель должен быть большим числом.

 

«…Важно помнить, что недостаточно использовать стойкий криптографический алгоритм, должны быть безопасными вся криптосистема и криптографический протокол. Слабое место любого из трех этих компонентов сделает небезопасной всю систему…».[7]

 

Стандарты.

 

Алгоритм RSA является стандартом де-факто, принятым почти во всем мире. Организация ISO уже почти разработала стандарт цифровой подписи, основанный на RSA; RSA служит информационным дополнением стандарта ISO 9796. Французское банковское сообщество приняло RSA в качестве стандарта, также поступили и австралийцы. С США из-за давления АНБ и проблем, связанных с патентами, в настоящее время нет стандарта для шифрования с открытым ключом. Многие американские компании используют алгоритм PKCS, созданный компанией RSA Data Security, Inc. Спецификация RSA содержится и в черновике банковского стандарта ANSI.

 

Патенты.

 

Алгоритм RSA запатентован только в США и более ни в какой другой стране. Компания PKP получила лицензию вместе с другими патентами в области криптографии с открытым ключом. Срок действия патента США истек 20 сентября 2000 года.

 

6. Словесная схема алгоритма:

 

Шаг0. Выбор пункта основного меню.

Шаг1. Выбор 1ого пункта (“Create public and private keys”).

Шаг1.1 Выбор и расчет значений ключей.

    Шаг1.2 Запись открытого ключа в open_key.rsa  

      закрытого – pr_key.rsa.

Шаг1.3 Вывод сообщения об успешном создании ключей. Шаг0.

Шаг2. Выбор 2ого пункта (“Encoding information”).

Шаг2.1 Появление нового меню выбора. Проверка наличия  открытого            ключа. Если отсутствует то Error и Шаг0.

   Шаг2.1.1  Выбор пункта Чтение из файла bf.txt

   Шаг2.1.2 Чтение из файла очередной строки в буферную,                  добавление к основной строке, пока не конец файла.                  И Шаг2.3.

   Шаг2.2.1  Выбор пункта Чтение с клавиатуры.

   Шаг2.2.2  Чтение с клавиатуры до нажатия клавиши Enter, либо                   максимум 127 символов.

   Шаг2.2.3  Выбор пункта Exit – Выход из программы.    

Шаг2.3    Вывод Open key и кодов всех символов сообщения.   

Шаг2.4    Шифрование информации посимвольно.    

Шаг2.5    Вывод зашифрованных кодов всех символов. Шаг0.  

Шаг3. Выбор 3ого пункта (“Decoding information”).

Шаг3.1 Проверка наличия файла с секретным ключом, если нет то Error и        Шаг0.

Шаг3.2 Проверка наличия файла с зашифрованным текстом, если нет то        Error и Шаг0.

Шаг3.3 Вывод Private key, зашифрованных кодов всех символов на экран.

Шаг3.4 Дешифрование и вывод полученного текста на экран. Шаг0.

Шаг4. Выбор 4ого пункта (“About”).

Шаг4.1 Вывод на экран информации о программе. Шаг0.

Шаг5. Выбор 5ого пункта (“Exit”). Выход из программы.

 

Детали:

Выбор и  расчет значений происходит следующим образом: задан массив содержащий только простые числа. Операцией random() выбираем случайный индекс массива, затем записываем число под этим индексом в p; аналогично выбираем, и записываем в q; После расчет n=p*q;

phi=(p-1)*(q-1); e присваиваем простое число, также взаимно простое с phi (в данной программе выбрано число 65537, т.к. phi в любом случае меньше e, и следовательно они не имеют общих делителей); и d вычисляем как функцию eae(phi,e).

Операция  связанная с проверкой наличия  какого-либо файла происходит следующим образом:

FILE *pf; // pf файловая переменная

pf=fopen("<имя файла>","<чтение/запись>");

if(pf == NULL) // если файл пуст либо не найден

{ cout << “ERROR!”; }

Шифрование происходит функцией RsaEncode(<блок>,<n>,<e>)

Дешифрование происходит функцией RsaDecode(<блок>,<n>,<d>) 

7. Список используемых идентификаторов:
Переменные и указатели.
Long p; Long q; Long n; Long phi; Long e; Long d; Long *poiner; Char *strin1; Char *strin2; FILE *pf; FILE *bf; Int ch; Int ch2;	Список переменных, которые  используются почти в каждом блоке программы. p и q под два простых числа, n =p*q, phi =(p-1)*(q-1), e взаимно простое с phi, d находится функцией eae от e и phi. *pointer – рабочий указатель, необходимый как переходный буфер для запоминания данных, с последующей записью в файл или чтением из файла. Strin1 рабочая строковая переменная. Strin2 временная (буферная) строковая переменная. Bf файловая переменная под файл с исходным текстом. Pf файловая переменная для работы с остальными файлами. Ch переменная под пункты основного меню, ch2 под пункты подменю.
Int mas[…] массив содержащий простые числа для создания разных ключей.
Функции.
eae (long u, long v) Функция реализующая  расширенный алгоритм Евклида (для  нахождения d)
RsaEncode (long b, long n, long e) Функция реализующая шифрование
RsaDecode (long b, long n, long d) Функция реализующая  дешифрование
ingr () Функция реализующая  подключение графического режима
read_menu () Функция для  создания подменю шифрование (для  выбора варианта ввода текста)
about () Функция для  отображения информации о программе
initgraph (&gdriver, &gmode, ”<путь”>) Функция инициализирующая графический режим адаптера
outtextxy (x, y, ”<текст>”) Функция вывода текста, начиная с заданного положения  указателя
settextstyle (<шрифт>, направление>, <размер>) Функция устанавливающая  стиль текстового вывода на графический экран
setfillstyle (<тип заливки>,<цвет>) Функция устанавливающая  стиль штриховки
closegraph () Функция прекращающая работу адаптера в графическом режиме
Cleardevice() Стирает графический экран и перемещает указатель в начальную позицию (0,0)
Setcolor(<число>) Устанавливает текущий цвет.
Bioskey(int cmd) Исполняет различные действия клавиатуры используя BIOS прерывания
SWITCH … CASE Оператор выбора.
Do { <директивы> }; While (<условие>) Цикл, который выполняет директивы до тех пор, пока выполняется условие.
long *pointer;     создание указателя pointer=new long;  выделение памяти под указатель; delete pointer;    освобождение памяти выделенной под указа-                     тель.
abs(<значение>) Вычисляет модуль заданного значения, если                  необходимо обойтись без отрицательных чисел.
fopen(<файл>,<параметр>) открывает заданный файл. fwrite(<>) Выполняет запись информации в файл; fread (<>) Выполняет чтение из файла; fclose(<>) Выполняет закрытие файла
cin.getline (<строка>,<число>) Выполняет чтение с клавиатуры в заданную переменную, считывает заданное число символов.
fseek(pf,SEEK_SET,0) Запись начинать с  начала файла.
while(!feof(pf)) считывать до тех пор, пока не конец файла

 

 8. Инструкция к программе:

 

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

При появлении сообщений, следовать указаниям программы.

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

    

1. Драйвер графических устройств:

            Egavga.bgi

2. Файл с исходным текстом (если планируется ввод не с клавиатуры):

     А) bf.txt

    

 

9. Заключение:

 

Плюсы программы:

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

Минусы программы:

1. Не реализована работа программы со сверхдлинными числами, до 200 разрядов в десятичном виде.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

[1]. Редькина А. В. Программирование на языке С++. - К.: (часть I/II) издательство КГТУ, 2001г.

[2]. Герберт Шилдт: Полный справочник по С, четвертое издание.

[3]  А. В. Редькина: программирование на языке С++, 1,2 части.

  [4]. Д. Кнут: Искусство программирования для ЭВМ, т.2.

[5]. «Help» – Borland C++.

[6]. Символьный C++, К.Ш.ТАН, В.-Х.Стиб, Й.Харди, издательство Мир.

[7]. Брюс Шнейер "Прикладная криптография" (Bruce Schneier, Applied Cryptography).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

#include <stdlib.h>   //подключение библиотек

#include <string.h>

#include <math.h>

#include <iostream.h>

#include <conio.h>

#include <stdio.h>

#include <dos.h>

#include <bios.h>

#include <graphics.h>

 

long eae(long u, long v)  //функция реализующая расширенный алгоритм                           //Евклида

{

long u1, u2, u3, v1, v2, v3, t1, t2, t3, q;

u1 = 1;    //инициализация переменных

u2 = 0;

u3 = u;

v1 = 0;

v2 = 1;

v3 = v;

label:

;

if(v3 == 0)

goto end;

 

//целая часть от частного

 

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;

goto label;

end:

;

return u2;

}

 

long RsaEncode(long b, long n, long e)//Функция шифрования

{       //вычисление остатка

long result = 1;

for(long i=0; i<e; i++) //где b – блок, n и e ключ

{

result = (result*b) % n;

}

return result;

}

 

long RsaDecode (long b, long n, long d) //Функция дешифрования

{       //вычисление остатка

long result = 1;

for(long i=0; i<d; i++)//где b – блок, n и d ключ

{

result = (result*b) % n;

}

return result;

}

 

void ingr()  //Функция инициализации графического режима

 

{

int gdriver = DETECT, gmode, errorcode;

initgraph(&gdriver, &gmode, "c:\\borland\\bgi");

errorcode = graphresult();

if (errorcode != grOk)

{

printf("Graphics error: %s\n", grapherrormsg(errorcode));

printf("Press any key to halt:");

getch();

exit(1);

}

}

 

int main_menu()  //Функция рисования основного меню

{

int x=1,h,ch=0,ch2;

cleardevice();setcolor(4);    //меню

settextstyle(0,0,10);

outtextxy(250,100,"RSA");

setcolor(6);

settextstyle(10,0,10);

outtextxy(350,240,"Main MENU:");

settextstyle(0,0,1);

setcolor(4);

outtextxy(300,260,"Create PUBLIC and PRIVATE keys");

outtextxy(300,280,"ENCODE INFORMATION)");

outtextxy(300,300,"DECODE INFORMATION");

outtextxy(300,320,"About this program");

outtextxy(300,340,"EXIT");

 

setfillstyle(0,0);

do{

outtextxy(240,240+x*20,"<>"); //рисование курсора

h=bioskey(0)>>8;

bar(240,240+x*20,280,280+x*20);

 

switch(h){  //выбор пункта

 

case 72:{if(x>1)x=x-1;

else x=5;break;}

  case 80:{if(x<5)x=x+1;

else x=1;}

};

 

}while(h!=28); //выбирать пока не нажат ввод

 

cleardevice();

 

switch(x){ //выбор пункта

 

case 1:{ch=1;break;}

case 2:{ch=2;break;}

case 3:{ch=3;break;}

case 4:{ch=4;break;}

case 5:{closegraph();exit(0);}

  }

return (ch); //возврат значения для основного меню

}

int read_menu()//Функция рисования меню для пункта Encoding

{

int x=1,h,ch2=0;

 

cleardevice();

setcolor(4);    //рисование меню

settextstyle(0,0,10);

outtextxy(250,100,"RSA");

setcolor(6);

settextstyle(10,0,10);

outtextxy(320,240,"ENCODE :: READ Menu:");

settextstyle(0,0,1);

setcolor(4);

outtextxy(300,260,"Read from FILE 'bf.txt'");

outtextxy(300,280,"Read from keyboard");

outtextxy(300,300,"Exit program");

setfillstyle(0,0);

do{

outtextxy(240,240+x*20,"<>"); //рисование курсора

h=bioskey(0)>>8;

bar(220,220+x*20,280,280+x*280);

 

switch(h){ //выбор пункта

   

case 72:{if(x>1)x=x-1;

else x=3;break;}

  case 80:{if(x<3)x=x+1;

else x=1;}

};

 

}while(h!=28); //выбирать пока не нажат ввод

 

cleardevice();

  switch(x) //выбор пункта

  {

case 1:{ch2=1;break;}

case 2:{ch2=2;break;}

case 3:{ch2=3;closegraph();exit(0);}

  }

return (ch2); //возврат значения для доп. меню

}

 

void about()    //Функция выдает информацию о программе

{

 cleardevice();

 settextstyle(0,0,8);