Криптоалгоритмы, формирование открытых ключей

 

Таблица 1.2 – Формирование последовательности операций умножения и возведения в квадрат

1	0	1	1	1
	S	SX	SX	SX

 

Двигаясь слева направо, получим  определяющую строку SSXSXSX. Помня, что S – это возведение в квадрат, а X – умножение на основание, получаем следующую последовательность операций:

 

,

 

что соответствует  действительности.

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

 

3. Формирование рабочих  ключей

 

Так, как система  Эль-Гамаля – это асимметричная криптосистема, то она имеет открытый и закрытый ключи. Открытый ключ – это набор чисел p, g и y; закрытый – число x. Числа p и g формируются согласно условиям, указанным в пункте 1.1 (см. формулы 1.4-1.7). Число y рассчитывается по формуле

 

.     (1.8)

 

Число x выбирается случайно в диапазоне .

Получив нужные для работы криптосистемы параметры  теперь можно перейти к алгоритму формирования ЭЦП.

 

4. Алгоритм формирования ЭЦП

 

ЭЦП осуществляется в два этапа. Сначала осуществляется генерация и распределение ключей, т.е. каждый пользователь, генерирует себе х_і ключ, сохраняет его себе в тайне, а открытый ключ вычисляется как:

.                                      (1.9)

Открытый  ключ Y_a пользователь распространяет всем корреспондентам системы, с которыми он имеет связь.

Эль – Гамаль предложил сформировать подпись как две компоненты ЭЦП: .

Эти компоненты формируются на основе решения  классического сравнения Эль  -Гамаля:

,                             (1.10)

где – первоначальный элемент в поле, – хеш-функция, – открытый ключ, причём

;                                            (4.11)

.                                       (4.12)

Подставим (1.9) и (1.12) в (1.10). В результате имеем, что:

откуда

.                             (1.15)

Выражение (4.15) является фундаментальным, поскольку позволяет вычислить вторую компоненту ЭЦП, а именно:

    (1.16)

или                                                        

.   (1.17)

 

6. Алгоритм проверки ЭЦП

 

Осуществляется всеми пользователями, которые обладают открытым ключом Y и общесистемных параметрами P, Q. Осуществляется на основе проверки сравнения(1.9). 
Устойчивость преобразования определяется сложностью решения сравнения (1.10) относительно .

 

7. Постановка задачи реализации

 

Программа будет состоять из трех частей:

1. Модуль генерации криптопараметров p и g размерностью 32 бита (см. п. 1.1):

Этот модуль должен генерировать простое число p, после чего проверять его на простоту с помощью теста Лемана (см. п. 1.1) и далее сформировать число g, являющееся первообразным корнем по модулю p. Оба числа сохраняются в бинарном файле.

2. Модуль генерации чисел x и y (так же размерностью 32 бита):

Этот модуль должен считывать из бинарного файла p и g и формировать числа y и x (см. п. 1.3). Число y рассчитывается по формуле (1.8), а x случайно выбирается в диапазоне . Оба числа сохраняются в отдельные бинарные файлы.

 

2. ОПИСАНИЕ  ПРОГРАММЫ ЭЦП Эль-Гамаля

 

 

2.1 Общие сведения

 

Для выполнения поставленной задачи программной реализации упрощенной одномодульной 32-битной версии ЭЦП была разработана специальная программа “ElGamal”.

Программа написана на языке программирования С++ в среде Microsoft Visual Studio 2010, запускается как консольное приложение и не требует дополнительно установленного программного обеспечения. Для ее работы достаточным является наличие любой операционной системы Windows8. Для компиляции кода вам потребуется программная среда Microsoft Visual Studio.

 

2.2 Функциональное назначение

 

Данная программа  предназначена для формирования ЭЦП текстовых файлов с помощью упрощенной версии системы Эль-Гамаля. Так же она содержит модуль генерации простых 32-битных чисел, который может использоваться отдельно. “ElGamal” – это учебно-демонстративный вариант криптосистемы Эль-Гамаля, поэтому она не может использоваться в целях защиты информации из-за малых размеров ключей (32 бита), что значительно занижает криптостойкость этой системы. Она может быть использована для обучения или для демонстрации работы системы Эль-Гамаля.

Основной  недостаток программы в том, что  она  работает с числами размерностью 32 бита. Также, при тестировании программы  использовались только текстовые файлы, поэтому результаты работы с другими  типами файлов неизвестны.

2.3 Описание  логической структуры

 

1. Реализована функция, выполняющая формирование пары рабочих ключей {X_i, Y_i}. При этом использована функция возведения в степень по модулю (бинарный метод).

2. Реализована функция, выполняющая формирование криптопараметров {P, q}. Сгенерированные ключи записываются в три двоичных файла:

{P, q} (открытая ключевые параметры);

Y_i (открытый ключ проверки ЭЦП); 

X_i (конфиденциальный ключ проверки ЭЦП).

 

3 Реализовано формирование хеш-значения H(M) от исходной информации М с помощью функции из библиотеки формирования контрольных сумм по алгоритмам CRC-32 .

4 Реализована функция, выполняющая формирование ЭЦП (пары чисел {R, S}) для некоторого сообщения М.

5 Реализована функция проверки ЭЦП:

проверка ЭЦП для заданного  исходного сообщения M (для поученного значения хеш-функции от сообщения H(M)) и заданных значений ЭЦП {R, S}) и вывод на экран результатов проверки ЭЦП.

Задание «поддельного» (измененного) сообщения M ^*. Повторная проверка ЭЦП для «поддельного» (измененного) сообщения M ^* (для измененного значения хеш-функции от сообщения H(M ^*) и корректных значений ЭЦП {R, S}). Вывод на экран результатов проверки ЭЦП.

Задание “поддельного” (измененного) значения второго компонента ЭЦП S ^*. Повторная проверка ЭЦП для заданного корректного исходного сообщения M (для начального значения хеш-функции от сообщения H(M)) и для “поддельных” (измененных) значений ЭЦП {R, S ^*}). Вывод на экран результатов проверки ЭЦП.

 

2.4 Используемые технические средства

 

Для работы программы  используется персональный компьютер  с операционной системой Windows. Обязательным условием работы программы является наличие установленной среды разработки Microsoft Visual Studio 2010 или более поздней версии. Программа тестировалась и прошла проверку на работоспособность на ПК с ОС Windows 7. Технические характеристики ПК: ОЗУ - 4096 Mb, процессор Intel Core i3 CPU 2310M 2.0 GHz.

 

2.5 Вызов и загрузка программы

 

Вызов программы  осуществляется через среду разработки Microsoft Visual Studio 2010.

2.6 Входные и выходные данные

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

 

 

ВЫВОДЫ

 

 

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

При разработке программы “ElGamal” я ознакомился с ГОСТами оформления программной продукции, получил навыки по написанию научных работ и разработке программного обеспечения на языке C++.

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

 

СПИОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

 

 

1. Горбенко І.Д., Гріненко Т.О. Захист інформації в інформаційно-телекомунікаційних системах: Навч. посібник, Ч. 1. Криптографічний захист інформації /  Горбенко І.Д., Гріненко Т.О.  – Харків: ХНУРЕ. – 2004. – 368 с.
2. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии / Василенко О. Н. — М.: МЦНМО, 2003.—328 с.
3. Вельшенбах М. Криптография на Си и С++ в действии. Учебное пособие / Вельшенбах М. – М.: Издательство Триумф. – 2004. – 464 с.
4. Кнут Д. Искусство программирования для ЭВМ. Получисленные алгоритмы / Кнут Д. – М.: Мир. – Том 2. – 1976. – 788 с.
5. Петров А.А.  Компьютерная безопасность. Криптографические методы защиты / Петров А.А. – М.: ДМК. – 2000.
6. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си / Шнайер Б. – М.: Триумф. – 2002.
7. http://ru.wikipedia.org/

 

ПРИЛОЖЕНИЕ А

ЭЦП Эль-Гамаля

 

#include <iostream>

#pragma comment(lib,"CRC32.lib")

#include <conio.h>

#include <time.h>

#include <math.h>

#include <string.h>

#include "CRC32.h"

 

#define EXIT "exit"

using namespace std;

 

bool GetD (unsigned int Fn, unsigned int E, unsigned int &D)//ф-ция вычисляет обратный эл-т (D) для (E) методом цепных дробей

{

unsigned int r, s, a=Fn, b=E, ai[3]={0,1};

int M(-1);//кол-во итераций

do

{

r=a/b;

s=a%b;

ai[2]=r*ai[1]+ai[0];//находим текущее а

ai[0]=ai[1];//записываем предыдущее а в пре-предыдущее

ai[1]=ai[2];

a=b;//записываем числитель

b=s;//записываем знаменаткль

++M;//наращиваем итерации

} while (s); //до тех пор, пока есть остаток

if (a!=1)//если последний знаменатель НЕ 1 (т.е. НОД(Fn,D)!=1)

return 1; // Ошибка

if (M%2==0)

D=ai[0];

else

D=Fn-ai[0];

return 0;

}

 

void Xpower (unsigned int x, unsigned int k, unsigned int N, unsigned int &y) // Возводит x в степень k  по модулю N

{

if(k==0) //если степень 0 возвращаем 1

{

y = 1;

return;

}

if (k==1) //если степень 1 возвращаем х по модулю

{

y = x%N;

return;

}

y = x; //присваеваем у=х

int i;

for(i = 31; i >= 0; --i)//ищем первый ненулевой бит степени с конца

if((k & (1<<i)) != 0)

break;

unsigned __int64 j;

--i; //начинаем считать с бита на 1 младше чем самый старший ненулевой

for(;i >= 0; --i)//цикл пока не дошли до 0

{ 

j = y;

j*= j;//возвели у в квадрат

y = j%N;//взяли по модулю

if ((k & (1<<i)) != 0)//если текущих бит 1

{

j = y;

j*= x;

y = j%N;//то умножили еще на Х и взяли по модулю

}

}

return;

}

 

bool Miller_Rabin (unsigned int n)

{

    if (n == 1)

return 1;

if ((n == 2) || (n == 3))

return 0; // Простое

unsigned int k = 100, s=0, d, a, x, f = 1;

    d = n - 1;

    while (!(d%2))

    {

       d/= 2;

       s++; // на сколько 2 делится d

    }

    for (int t = 0; t < k; t++)

    {

       a = (( (rand()<<16) | (rand()) )%(n-3)) +2;

//   (rand())%(n-3); // !!!!!

       Xpower(a, d, n, x); // Возводим a в степень d по модулю n

       if (!(x==1 || x==n-1))

       {

           for (int r = 1; r < s; r++)

           {

              Xpower(x, 2, n, x);

              if (x==1)

                 return 1;  // n составное      

              if (x==n-1) f=0;      

           }      

           if (f)

           return 1; // n составное     

       } 

    }

    return 0; // Проверку прошло

}

 

void GenPrime (unsigned int &P)

{

bool b = 0;

do

{

P = ((( (rand()<<16) | (rand()) )%(65533)) +2)|1; // 65533 = (0xFFFF) - 2

b = Miller_Rabin(P);  

}

while (b);

return;

}

 

bool IsPrime (unsigned int P)

{

bool b = Miller_Rabin(P);  

return b;

}

 

unsigned int Xv2_C (unsigned int x, unsigned int c, unsigned int Mod) // y=x^2+c(mod Mod)

{

unsigned int y;

unsigned __int64 k;

Xpower(x, 2, Mod, y);

k = y;

k+= c;

k%= Mod;

y = k;

return y;

}

 

unsigned int NOD(unsigned int m, unsigned int n, int k = 1)

{

if(!m && n)

return n*k;

if (m && !n)

return m*k;

if (m == n)

return m*k;

if((m == 1) && n)

return 1*k;

if (m && (n == 1))

return 1*k;

if (!(m&1) && !(n&1))

{

k*= 2;

m/= 2;

n/= 2;

NOD(m, n, k);

}

else if (!(m&1) && (n&1))

{

m/= 2;

NOD(m, n, k);

}

else if((m&1) && !(n&1))

{

n/=2;

NOD(m, n, k);

}

 else if((m&1) && (n&1))

{

if (n > m)

{

n%= m;

}

else

{

m%= n;

}

NOD(m, n, k);

}

}

 

bool Fact_PQ (unsigned int K, unsigned int &P, unsigned int &Q)//если ошибка, возвращает 1, иначе 0

{

unsigned __int64 d, razn, x[2], y[2], c;

do

{

c = ((rand()<<16) | rand())%(K-1);

}

while (!c);

do

{

x[0] = ((rand()<<16) | rand())%(K-1);

}

while (!x[0]);

y[0] = x[0];

do

{

x[1] = Xv2_C(x[0], c, K);

x[0] = x[1];

y[1] = Xv2_C(y[0], c, K);

y[1] = Xv2_C(y[1], c, K);

y[0] = y[1];

if (x[1] > y[1])

razn = x[1] - y[1];

else

razn = y[1] - x[1];

d = NOD(K, razn);

if (d == K)

return 1;

} while (d == 1);

P = d;

Q = K/P;

return 0;

}

 

void MakePg (unsigned int &P, unsigned int &g) // Генерирует ключевые параметры P и его первообразный корень g

{

unsigned int Fn, P1, Q1, y1, y2;

bool temp;

do

{

do

{

GenPrime(P);

Fn = P - 1;

}

while(Fact_PQ(Fn, P1, Q1));

}

while (IsPrime(P1) || IsPrime(Q1));

do

{

do

{

g = 1 + ((rand()<<16) | rand())%(P-1);

}

while((g == 1) || ( g== 0));

Xpower(g, P1, P, y1);

Xpower(g, Q1, P, y2);

}

while((y1 == 1) || (y2 == 1));

return;

}

 

void FormXY(unsigned int P, unsigned int g, unsigned int &X, unsigned int &Y) // Генерирует ключи X и Y

{

X=0; Y=0;

  X = ((( (rand()<<16) | (rand()) )%(P-1)) +1)|1;