(7 оценок, среднее: 4,71 из 5)
Загрузка...
Учебная работа. Реферат: Реализация системы распространения ключей на основе алгоритма Диффи-Хеллмана длиной 256 бит
Реализация системы распространения ключей на базе
метода Диффи-Хеллмана
(длиной 256 бит)
Выполнил: Денисов А. П.
Проверил: Корниенко В. Т.
2010
ВВЕДЕНИЕ.. 3
Глава 1. Система открытого распределения ключей.. 4
1.1. История сотворения системы распределения ключей. 4
1.2. Система распределение ключей Диффи-Хеллмана. 6
1.3. Описание средств разработки. 7
Глава 2. Программная реализация открытого распространения ключей Диффи-Хеллмана. 9
2.1. Математические базы алгоритмов применяемых в работе. 9
2.1.1. Сложение и вычитание. 9
2.1.2. Умножение «в столбик». 10
2.1.3. Возведение целого числа в квадрат. 12
2.1.4. Деление. Вычисление остатка. 13
2.1.5. тест Рабина— Миллера. 16
2.1.6. Модульное возведение в степень. 18
2.1.7. Генерация обычного числа. 20
2.1.8. Разложение числа на обыкновенные множители. 23
2.1.9. Нахождение первообразного корня. 24
Глава 3. Оценка метода. 27
3.1. Оценка стойкости метода. 27
3.2. Оценка скорости работы метода. 27
ЗАКЛЮЧЕНИЕ.. 29
Литература. 30
ВВЕДЕНИЕ
Неувязка защиты инфы методом ее преобразования, исключающего его чтение сторонним лицом, тревожила человечий разум с давнешних времен. Актуальность данной для нас задачи не утратила собственной остроты и в истинное время, потому что в эру массового внедрения компьютерных технологий задачка защиты электрической инфы заполучила нрав широкомасштабной задачи. Возникновение ассиметричных криптосистем произвели реальный прорыв в современной криптографии и дозволили передавать сообщения меж абонентами без передачи секретного ключа.
Объектом исследования является метод распределения ключей Диффи-Хеллмана.
Предмет исследования – программная реализация метода распределения ключей Диффи-Хеллмана.
Цель работы — построение программного продукта на базе открытого распределения ключей Диффи-Хеллмана. Для ее решения были поставлены последующие задачки:
1. изучить криптографический метод
2. выстроить математическую модель комфортную для программирования
3. доказать алгоритмическое решение программки
4. произвести оценку метода
5. воплотить метод криптосистемы на базе открытого распределения ключей Диффи-Хеллмана на одном из языков программирования
6. произвести проверку работоспособности и правильности работы программки
Глава 1 Система открытого распределения ключей
.
1.1. История сотворения системы распределения ключей
В 1970 году Мартин Хеллман, юный доктор, занимавшийся вопросцами проектирования электронных систем в Стенфордском институте в Пало-Альто (шт. Калифорния). Хеллман увлекся неувязкой в 1968 году, когда работал в IBM в Пенсильвании, [Завгородный В.И., 2001].
Хеллман ведает, что он прозрел опосля того, как прочел статьи Клода Шенона по теории инфы и криптографии, которые опубликовались в 1948 и 1949 годах. «Ранее я и представить для себя не мог, как тесновато соединено шифрование и теория инфы«, — гласит он.
В статьях Шенона вопросцы кодировки рассматривались в связи с задачей понижения электростатических помех, мешающих передаче радиосигналов. «Шифрование, — увидел Хеллман, — решает диаметрально обратную задачку. Вы вносите преломления с помощью ключа. Для того, кто слышит сигнал и не понимает ключа, он будет смотреться очень искаженным. Но законный получатель, которому известен скрытый ключ, может удалить эти помехи».
Пока Хеллман находил пути для решения задачи, некоторый студент из MIT по имени Уайтфилд Диффи заинтересовался этим же самым. Но поиски Диффи начались существенно ранее. «Я увлекся шифрованием, когда мне было всего 10 лет, — вспоминает он. — У меня был учитель, который посвящал дилемме шифрования практически целые деньки. Я шел домой, а там меня ожидали книжки по этому предмету. отец приносил мне их из библиотеки института».
К 1973 году Диффи стал лаборантом и раздражал профессоров Стенфорда по искусственному уму тем, что растрачивал все свое время и энергию на шифрование. В конце концов, он оставил в покое собственного учителя, брал отпуск и, одержимый собственной мыслью, отправился в путешествие по Восточному и Западному побережью, где встречался с профессионалами по шифрованию и разыскивал редчайшие манускрипты.
А в это самое время Ральф Меркл, студент Института Беркли (шт. Калифорния), занимающийся только проектированием электронных систем, бродил по институтскому городу, снедаемый идеями о шифровании, [Завгородный В.И., 2001].
«Я задумывался о том, как обеспечить защиту коммуникаций меж терминалом и компом, — ведает Меркл. — Я сообразил, что если оба, и терминал, и комп, употребляют случайные числа, вернуть ключ при передаче по открытым линиям связи будет нереально».
Пытаясь соединить разрозненные идеи по шифрованию данных, Хеллман продолжал находить единомышленников. Но вышло напротив: в сентябре 1973 года его отыскал Диффи. Их получасовая встреча плавненько перебежала в обед у Хеллмана, при этом дискуссии затянулись далековато за полночь.
Хеллман и Диффи начали работать над созданием метода обеспечения защиты транзакций покупки и реализации, выполняемых с домашних терминалов. «Я разламывал голову над тем, как получить сообщение и конвертировать его таковым образом, чтоб его принимали лишь те, кому предназначено, а сторонним информация была недосягаема, — произнес Диффи. — Потом я сообразил, что с помощью сертификатов и подписи можно сделать сообщение, которое сумеет прочесть лишь один человек», [Завгородный В.И., 2001].
Хеллман и Диффи сказали, что их 1-ая статья по теории цифровых подписей вышла в декабре 1975 года. Представлена она была полгода спустя на Государственной компьютерной конференции в Нью-Йорке.
Оставаясь невидимым для конечных юзеров, открытый ключ употребляет открытый и скрытый ключи для шифрования и дешифрования сообщений совместно с цифровыми подписями, также для проверки личности отправителя. В его базе лежат достаточно сложные математические преобразования.
Опосля Беркли в 1975 году Меркл определил задачку защиты коммуникаций, несвязанную с подписью и сертификатом. Он взялся за решение задачи распространения открытого ключа, исходя из предпосылки внедрения смешения случайных чисел. Прочитав статью Хеллмана-Диффи, Меркл повстречался с первым, который уговорил Блекла перенести свою аспирантскую работу в Стенфорд.
В 1976 г. Мерклу удалось с помощью Хеллмана и Диффи совладать с задачей распространения открытого ключа и развить аппарат цифровой подписи. Они сделали и запатентовали систему, получившую имя Диффи-Хеллмана. Открытие обеспечило нашему трио внимание со стороны средств массовой инфы.
Но внимание это испарилось так же стремительно, как и появилось. Изобретатели обогнали свое время: задачка, решение которой они давали, еще не была сформулирована, [Завгородный В.И., 2001].
1.2. Система распределение ключей Диффи-Хеллмана
Зарождение двухключевой криптографии и главные криптосистемы с открытым ключом соединены с внедрением функции возведения в огромную дискретную степень по модулю огромного обычного числа
α x
(
где
— целое число. 1< x
k-битовое обычное число, α — первообразный корень по модулю
[Молдовян Н.А. и др., 2004].
Используя данную функцию, учеными Диффи и Хеллманом была показана возможность построения фактически стойких скрытых систем, которые не требуют передачи секретного ключа
Предложенная ими система получила заглавие способа открытого распространения ключей. В ней любой абонент выбирает случайным образом скрытый ключ
и производит открытый ключ
соответственный избранному секретному ключу, в согласовании с формулой
α х
(
Системой Диффи-Хеллмана именуется последующий метод использования дискретного возведения в степень для обмена скрытыми ключами меж юзерами сети с применением лишь открытых сообщений. Выбирается огромное обычное число р и соответственный ему первообразный корень
Для обеспечения стойкости рассматриваемой системы открытого шифрования на число
накладывается последующее условие: разложение числа
на множители обязано содержать, по последней мере, один большенный обычный множитель; размер числа
должен быть не наименее 512 бит.
Механизм распределения скрытых ключей по открытому каналу состоит в следующем. Любой абонент выбирает случайный скрытый ключ x и производит открытый ключ у, соответственный избранному секретному ключу, в согласовании с формулой
y =
x
(mod
Два абонента А и В могут установить секретную связь без передачи секретного ключа последующим образом. Абонент А берет из справочника открытый ключ
B
абонента В и, используя собственный скрытый ключ хА
,
вычисляет общий скрытый ключ:
Аналогично поступает абонент В:
Таковым образом, оба абонента сформировали однообразный скрытый ключ ZAB
без использования какого-нибудь заблаговременно обсужденного общего секрета. Владея лишь им известным секретом и используя его в качестве мастер-ключа, данная пара абонентов может зашифровывать направляемые друг другу сообщения. Обозначенные выше вычисления просто осуществимы для довольно огромных значений
и
(к примеру, имеющих в двоичном представлении длину 4096 бит и наиболее). Атакующему известны значения 
и 
но для того чтоб вычислить ZAB
, он должен решить задачку дискретного логарифмирования и найти или
A
, или
B
.
Просто отыскать огромные значения
(наиболее 1024 бит), для которых задачка дискретного логарифмирования является тяжело решаемой. Если будут найдены вычислительно действенные способы решения задачки дискретного логарифмирования, то способ Диффи-Хеллмана окажется несостоятельным — в связи с сиим молвят, что данный .способ открытого распределения ключей основан на трудности дискретного логарифмирования. В истинное время в общем случае задачка дискретного логарифмирования фактически неразрешима, что дает возможность широкого практического внедрения способа Диффи-Хеллмана и бессчетных систем ЭЦП, основанных на трудности вычисления дискретных логарифмов.
Не следует упускать из виду делему аутентификации открытых ключей. Правильность протоколов с внедрением асимметричных шифров быть может обеспечена лишь в случае, если все открытые ключи в справочнике открытых ключей являются подлинными. Если открытый ключ какого-нибудь абонента нарушителю получится подменить, то скрытые сообщения, посланные данному абоненту, будут доступны нарушителю. Таковым образом, двухключевые шифры обеспечивают решение задачи распределения скрытых ключей, но неувязка аутентификации сохраняется и имеет базовый нрав, хотя требование доказательства подлинности (аутентификации) относится уже к открытому, а не к секретному ключу. В неявном виде аутентификация открытого ключа содержит в себе аутентификацию секретного ключа
[Молдовян Н.А. и др., 2004].
1.3. Описание средств разработки.
Проект реализован при помощи среды C++Builder 6, которая дозволяет разрабатывать серверы и клиенты Web-служб. C++Builder 6 обеспечивает поддержку клиентов Web-служб, использующих как SOAP encoding, так и Document Literal style. Document Literal style употребляется в Microsoft. Net Web Services. Предоставляя набор выскокоуровненвых компонент и визардов, включая автоматическую публикацию WSDL-описателей Web-служб в run-time и генерацию кода на базе WSDL (WSDL Importer), C++Builder 6 дозволяет разрабам просто адаптировать имеющиеся приложения для работы в режиме Web-служб и доступа к ним как во внутрикорпоративной сети, так и через Web.
C++ Builder дозволяет использовать ранее сделанный начальный код на C и С++. Можно работать с унаследованными проектами и приложениями третьих компаний на Borland C++ и Visual C++ снутри встроенной среды разработки C++ Builder. Расширенная сопоставимость с начальным кодом MS Visual C++, включая поддержку начальных текстов MSDN и SDK, дозволяет применять новые версии библиотек MFC и ATL. За счет поддержки эталона C++, RTTI, библиотек STL, RTL, ATL и MFC, дозволяет составлять и собирать проекты, сделанные ранее на хороших от C++ Builder средствах разработки для C/C++.
Глава 2. Программная реализация открытого
распространения ключей Диффи-Хеллмана.
2.1. Математические базы алгоритмов применяемых в работе
При разработке программки появился вопросец: каким образом представлять огромные числа? Решение было принято о том что число можно занести в массив типа unsigned char в который помещается два шестнадцатеричных числа, которые обрабатываются как 256-разрядные:
Это дозволяет существенно упростить функции.
Размещение значений в массиве оборотное, т.е. число “FF AB C4” в массиве будет представлено как: unsigned char a[3]={0xC4, 0xAB, 0xFF};
Все функции в программке предусмотрены для работы с 256-битными значениями.
Методы математики целых чисел и полиномов почти во всем похожи, так как
где 0 < ai
< В, аналогично представлению полинома 
.
Ниже описаны методы, применяемые в программном продукте. Метод представлен по последующей структуре: теоретические базы и листинг программки.
2.1.1. Сложение и вычитание
Операции сложения и вычитания для чисел и полиномов производятся фактически идиентично. Отличие состоит в том, что при сложении (вычитании) чисел возникает перенос в последующий разряд, а при операциях над полиномами перенос отсутствует.
Пусть неотрицательные целые числа а и b заданы в системе счисления с основанием В:
где
ai
;
bi
<
Для удобства считаем, что оба числа имеют равную длину, по мере необходимости старшие разряды наименьшего числа заполняем нулями.
Сложение производится «в столбик».
метод 1
. Сложение целых чисел, [Молдовян Н.А. и др., 2004].
Целые числа 
, 
.
Сумма 
1. Положить 
2. Для i = 0, 1,
1 выполнить последующие деяния.
2.1. Вычислить 
2.2. Положить 
,
.
3. Положить сп
=
4. Итог: 
Переменная
значит перенос в старший разряд и постоянно воспринимает (при ai
+bi
+s < B) либо 1 (при ai
+bi
+s ≥ B). На шаге 2.1 Может произойти не наиболее 1-го переноса. Вправду:
ai
+bi
+1 < (B-1)+(B-1)+1 < 2B-1<2B.
Вычитание аналогично сложению изменение лишь в шаге 2.1. 
.
В этом случае если t отрицательное то у последующего элемента занимается 1.
Сложность метода сложения и вычитания равна
Код функции summa(сумма) :
for (i=0;i<=32;i++){
s=a[i]+b[i]+buf; //Общее
c[i]=s;//число заносимое в ячейку
buf=(s)>>8;//остаток
}
Код функции sub(разность) c = a-b :
for(i=0;i<=31;i++){
s=a[i]-b[i]+buf;
buf=s>>8;
c[i]=s;
}
2.1.2. Умножение «в столбик».
Операция умножения является одной из более трудозатратных и совместно с
функцией деления описывает время работы метода.
Пусть неотрицательные целые числа
и
заданы в системе счисления с основанием B.
где 0 ≤ ai
< B, 0 ≤ bi
< B
Самый тривиальный метод умножения — умножение «в столбик».
Метод 2
. Умножение целых чисел «в столбик», [Молдовян Н.А. и др., 2004].
Целые числа
, 
где 0 < b ≤ a
Произведение
1.
Для i = 0, 1,
1 положить ci
= 0
2.
Для i = 0, 1,
1 выполнить последующие деяния.
2.1. Для j = 0, 1,
1:
2.1.1. Положить
0.
2.1.2. Вычислить t = ci+j
+ai
bj
+s , ci+j
=t (mod B) , 
.
2.2. Положить ci
+
n
=s.
3. Итог: 
Во наружном цикле этого метода рассчитываются частичные произведения 
а во внутреннем — произведения 
, где j = 0, 1,
1. Текущий разряд произведения равен t (mod В), а очередной перенос: . При всем этом на шаге 2.1.2 производится неравенство:
Сложность умножения в «столбик»
n2
).
Функция умножения реализована как умножение с вычислением модуля.
Код функции mult_mod (умножение по модулю) c=a*b (mod mod):
void mult_mod(unsigned char a[33],unsigned char b[33],unsigned char c[33]){
int i,j,k,s,t;
unsigned char d[65]={0};
for (k=0;k<=31;k++) c[k]=0; //очищение переменной
for(i=0;i<=31;i++){
s=0;
for(j=0;j<=31;j++){
t=d[i+j]+a[i]*b[j]+s;
d[i+j]=t;
s=t>>8;
}
d[i+32]=s;
}
modul(d,mod,c); //вычисление модуля mod — глобальная переменная
}
2.1.3. Возведение целого числа в квадрат.
Раздельно реализована функция возведения в квадрат.
метод 3
. Возведение в квадрат, [Молдовян Н.А. и др., 2004].
. Целое положительное число .
.
1. Для i = 0, 1,
1 положить сi
= 0.
2. Для i = 0, 1,
1 выполнить последующие деяния.
2.1. Положить 
, 
, .
2.2. Для j = 0, 1,
1 вычислить t = ci
+
j
+ai
aj
+s , ci
+
j
=t (mod B) , 
.
2.3. Положить ci
+
n
=s.
Итог: с .
На шаге 2.2 метода производится неравенство:
Это значит что t может занимать наиболее 2-ух разрядов в системе исчисления B.
Сложность метода возведение в квадрат
Код функции step2 (возведение в квадрат) b=a^2 (mod mod):
void step2(unsigned char a[33],unsigned char b[33]){
unsigned char c[65]={0};
int t,s,i,j;
for(i=0;i<=32;i++){
t=c[2*i]+a[i]*a[i];
c[2*i]=t%256;
s=t>>8;
for(j=i+1;j<=32;j++){
t=c[i+j]+2*a[i]*a[j]+s;
c[i+j]=t%256;
s=t>>8;
}
c[i+33]=s;
}
modul(c,mod,b);//вычисление модуля
}
2.1.4. Деление. Вычисление остатка.
Для деления в общем случае употребляется метод Д. Бича . Будем разделять «в столбик» число 
на число . Найдем такое личное 
и остаток
что
.
При делении на любом шаге находим личное 
от деления некого (n+1)-разрядного числа 
на
где О < R/b<
. Неравенство R/b <
эквивалентно неравенству R/B<b
откуда
:
Полагая
—
получаем 0 <
Для определения числа
будем применять аппроксимацию
[1]
При 
получаем 
другими словами определение меньшего из 2-ух чисел в выражении
(1) сводится к проверке равенства .
Аксиома 1.
Пусть , , если 
то удовлетворяет неравенству 
, где
определяется из соотношения (1.1).
метод деления с остатком. Чтоб старший разряд делителя удовлетворял условию аксиомы 1.1, числа
необходимо помножить на некое целое число d>0, такое что 
где.
, 
Личное при всем этом не меняется: 
. Число разрядов 
недолжно превосходить число разрядов b, число разрядов в 
быть может на единицу больше, чем в
(если это не так, полагаем ат+п
= 0).Избираем
равным степени двойки, потому что умножение на
в этом случае производится сдвигом.
Метод 4
. Деление «в столбик», [Молдовян Н.А. и др., 2004].
Неотрицательные целые числа 
, 
Целые числа ,
такие, что
, 
.
1. Найти такое целое число d>0, что 
, где 
2. Положить 
3. Для
1, …,
выполнить последующие деяния
3.1. Если ri
=bn
-1
, то положить
; в неприятном случае отыскать 
где 
.
3.2. Пока 
считать 
3.3. При 
положить .
3.4. Вычислить 
и 
.
4. Итог: 
,
Сложность метода деления «в столбик» равна О(mn).
Реализованы две функции целочисленное деление и вычисление остатка.
Главный код функций:
for(i=64;i>=0;i—){
ai=i+1;
if(a[i]!=0)break;
}
for(i=32;i>=0;i—){
n=i+1;
if(b[i]!=0)break;
}
m=ai-n;
//printf(«b = %x «,b[n-1]);
d=1;
if(b[n-1]<128){
for(i=2;i<=7;i++){
d*=2;
if((b[n-1]*d)>=128) break;
}
}//оценить d шаг 1
mult(b,d,bt);//шаг 1 b~=b*d
for(i=0;i<=63;i++){r[i]=a[i];}//шаг 2
for(i=m+n;i>=n;i—){//шаг 3
s=0;
for(k=i-n;k<=i;k++){
t=r[k]*d+s;
rt[k]=t;
s=t>>8;
}// шаг 3.1 r~=r*d
if(rt[i]==bt[n-1]) qt=255;
else qt=((rt[i]*256+rt[i-1])/bt[n-1]);// шаг 3.1 r~=r*d
while((bt[n-2]*qt)>((rt[i]*256+rt[i-1]-qt*bt[n-1])*256+rt[i-2])){
qt-=1;
}// шаг 3.2
mult(b,qt,bqt);
for(k=i;k>=i-n;k—){
if(r[k]<bqt[k-m]){
qt-=1;
break;
}
if(rt[k]>bqt[k-m])break;
}// шаг 3.3
mult(b,qt,bqt);
s=0;
for(k=i-n;k<=i;k++){
t=r[k]-bqt[k-m]+s;
r[k]=t;
s=t>>8;
}
c[i-n]=qt;
m-=1;
}
В итоге: r — остаток от деления ,c – целое от деления.
2.1.5. тест Рабина
—Миллера
На нынешний денек для проверки чисел на простоту почаще всего употребляется тест Рабина-Миллера, основанный на последующем наблюдении. Пусть число
нечетное и 
, где
— нечетное. Если
обычное, то для хоть какого
взаимно обычного с
производится условие аксиомы Ферма (
r
= 1 (mod
)). Разложим число
на множители:
Тогда в крайнем произведении хотя бы одна из скобок делится на
другими словами или
r
=
1(mod
или посреди чисел
r
, …, 
найдется сопоставимое с -1 по модулю
Воззвание этого характеристики лежит в базе теста Рабина-Миллера.
метод 5
. тест Рабина-Миллера, [Молдовян Н.А. и др., 2004].
Нечетное целое число
5.
«Число
возможно, обычное» шли «Число
составное».
1. Представить
1 в виде
где число
нечетное.
2. Избрать случайное целое число
3. Вычислить 
4. При 
и 
выполнить последующие деяния.
4.1. Положить j = 1.
4.2. Если j ≤ s – 1 и .
4.2.1. Положить
y2
(mod
)
4.2.2. При
1 итог: «Числю
составное».
4.2.3. Положить j=j+1.
4.3. При 
итог: «Число
составное».
5. Итог: «Число
возможно, обычное».
В итоге выполнения теста для обычного числа
в последовательности
(mod
a2
r
(
…, (mod
непременно перед 1 обязана показаться -1 (либо, что то же самое,
1 (mod
Это значит, что для обычного числа
единственными решениями сопоставления y2
= 1 (mod
) являются у = ±1 (mod n). Если число
составное и имеет
1 разных обычных делителей (другими словами не является степенью обычного числа), то по китайской аксиоме о остатках существует
k
решений сопоставления у2
=
1 (mod
Вправду, для хоть какого обычного делителя pi
числа
существует два решения обозначенного сопоставления:
1 (mod
i
)
Потому
таковых сравнений дают
k
наборов решений по модулям pi
,
содержащих элементы ± 1.
Сложность метода равна 
Код функции rabin (поверка на простоту):
/*mod – проверяемое
st – степень числа при передаче в функцию sstep();
osn – основание при вычислении
Пр: osnst
(mod mod)
*/
int rabin(){
unsigned char c[33]={0};
int i,k,g,t,q,r,x,j,fl,w;
unsigned char d[33]={0};//для р.м. р-1
srand(time(0));
for(i=0;i<=31;i++) st[i]=mod[i];
st[0]-=1;
for(i=0;i<=31;i++){
d[i]=st[i];
}
for(i=0;;i++){
q=i+1;
r=0;
for(k=31;k>=0;k—){
t=st[k]+(r<<8);
st[k]=(t>>1);
r=t%2;
}
if(int(st[0])%2==1) break;
}//находим n-1=(2^s)*q где n-простое
for(i=0;i<=6;i++){
osn[i]=rand();
}//генерируем основание
step(c);
x=comp_sp(c,d);
if(x==2){
return 1;
}
x=rav(c);
if(x==0) return 1;
j=1;
while(j<=q-1){
step2(c,c);
x=rav(c);
if(x==0) return 0;
j++;
}
x=comp_sp(c,d);
if(x!=2){
return 0;
}
return 1;
}
2.1.6. Модульное возведение в степень
При обыкновенном рекурсивном методе: a0
=1,
n
=(
n-1
)
Требуется n-1 операций возведения в степень по модулю
другими словами
m2
)
операций модульного умножения. Если же за ранее представить показатель
в двоичном виде 
где
= [log2
n], и, 
, то
где 
. При таком методе вычисления будет нужно k модульных возведений в квадрат и 
модульных умножений. Беря во внимание, что любой разряд воспринимает m
модульных умножений.
метод 6
Модульное возведение в степень, [Молдовян Н.А. и др., 2004].
Целое число
1
показатель степени
Выход. с = ап
(mod
1. Положить
Для
выполнить последующие деяния.
2.1. Вычислить 
2.2. При ni
= 1 вычислить 
Итог: с.
Код функции step (степень):
osn, st, mod – глобальные переменные основание, степень, модуль соответственно.
с = osnst
(mod mod)
void step(unsigned char c[33]){
int i,k,t,r;
int pole[256]={0};
unsigned char d[33]={0};
for(i=0;i<=31;i++){
union{unsigned char pol;
struct{unsigned b0:1;
unsigned b1:1;
unsigned b2:1;
unsigned b3:1;
unsigned b4:1;
unsigned b5:1;
unsigned b6:1;
unsigned b7:1;
}bit;
}cod;
cod.pol=st[i];
pole[i*8+0]=cod.bit.b0;
pole[i*8+1]=cod.bit.b1;
pole[i*8+2]=cod.bit.b2;
pole[i*8+3]=cod.bit.b3;
pole[i*8+4]=cod.bit.b4;
pole[i*8+5]=cod.bit.b5;
pole[i*8+6]=cod.bit.b6;
pole[i*8+7]=cod.bit.b7;
}//
2.1.7. Генерация обычного числа
Есть разные методы генерации обычных чисел. Почти все из их вырабатывают числа, владеющие особыми качествами. Разглядим метод генерации, использующий вероятностные методы проверки чисел на простоту.
метод 7
Генерация обычного числа, [Молдовян Н.А. и др., 2004].
Разрядность
искомого числа
; параметр t ≥ 1
Число
обычное с вероятностью не наименее 
1. Сгенерировать случайное k-битное число 
2. Положить bk
=1 , b0
=1
3. Проверить, что
не делится на обыкновенные числа 3, 5, 7, …,251 .
4. Для i = 1,2,
выполнить последующие деяния.
4.1. Избрать случайное число
2.
4.2. Проверить число
тестом Миллера-Рабина для основания
Если число
не прошло тест, то p = p+2 и возвратиться на шаг 3.
5. Итог: p.
Равенство bk
=1 на шаге 2 гарантирует, что длина числа p в точности равна
бит, равенство b0
=1 обеспечивает нечетность числа p.
Код функции random (генерация обычного числа):
void random(unsigned char c[33]){
unsigned int prost[54]={2,3,5,7,…, 241,251};
unsigned char copy_mod[33]={0};
int w,x,i,k,t,s,f,g=2,r,z,flag=0;
srand(time(0));
for(i=0;i<=31;i++){
mod[i]=rand();
}//генерация обычного числа
mod[0]|=1;
mod[31]|=128; //не четное и 256 бит
st[0]=mod[0]-1;
for(k=1;k<=31;k++){
st[k]=mod[k];
}//st= простое-1
for(w=0;;w++){
for(r=0;r<=31;r++){
copy_mod[r]=mod[r];
mod2[r]=mod[r];
}
flag=0;
for(i=0;i<=53;i++){
r=0;
for(k=31;k>=0;k—){
t=mod[k]+(r<<8);
r=t%prost[i];
}//проверка на делимость на мелкие обыкновенные числа
if(r==0){//число составное
flag=1;
break;
}
}
if(flag==0){
x=rabin();//проверка на простоту
if(x==1){
for(k=0;k<=6;k++){//еще 7 проверок на простоту
st[0]=mod[0]-1;
for(f=1;f<=31;f++){
st[f]=mod[f];
}
x=rabin();
if(x==0)break;//ели не прошло тест
}
if(x!=0){
x=razlogenie();//если обычное
// нахождение первообр. корня
if(x==1)break;//если число разложено
//на обыкновенные и найден первообр. корень
}
}
for(r=0;r<=31;r++)mod[r]=copy_mod[r];
}
s=0;
g=2;
for(k=0;k<=31;k++){//прибавить к проверяемому 2
t=mod[k]+g+s;
g=0;
s=t>>8;
mod[k]=t;
if(s==0)break;
}
mod[0]|=1;
mod[31]|=128;
for(k=0;k<=31;k++){st[k]=mod[k];}
st[0]-=1;
}
}
2.1.8. Разложение числа на обыкновенные множители.
В процессе реализации пригодилось разложить огромное число на обыкновенные множители один из которых является огромным.
Метод 8
Разложение числа на обыкновенные множители, [Молдовян Н.А. и др., 2004].
Раскладываемое число n.
Число не раскладывается на обыкновенные множители (с огромным обычным множителем); число раскладывается на q1
,
q2
,…,
qk
разных обычных делителя.
1. Создание ряда обычных чисел p1
=2 ,p2
= 3,…, p844
= 6491;
2. Положить t = 0.
3. Для i = 1,2,
844 выполнить последующие деяния.
3.1. Если w=n/pi
целое, t = t + 1, qt
= pi
;
3.1. Пока w=n/pi
целое, n=n/pi
.
4. Проверить число
тестом Миллера-Рабина
Код функции разложение razlogenie()
int razlogenie(){
int i,r,k,t,x,w,fl=0,counter=0;;
unsigned char p[33]={0};
int mass[300]={0};
unsigned char c[33]={0};
unsigned int prost[6900]={2,3,5,7,…,69491,69493};
for(k=0;k<=32;k++) p[k]=mod[k];
p[0]-=1;
for(i=0;i<=6860;i++){
r=0;
for(k=31;k>=0;k—){
t=p[k]+(r<<8);
c[k]=t/prost[i];
r=t%prost[i];
}
for(k=0;k<=31;k++) p[k]=c[k];
if(r==0){
for(k=0;k<=31;k++) mod[k]=p[k];
if(fl!=i){
fl=i;
mass[counter]=prost[i];
counter++;
}
i—;
}
if(r!=0){
for(k=0;k<=31;k++) p[k]=mod[k];
}
}
x=rabin();
if(x==1){
pervoobr(mass);//вычисление первообразного корня
}
return x;
}
2.1.9. Нахождение первообразного корня.
Пусть q1
,
q2
,…,
qk
разные обыкновенные делители функции Эйлера 
от числа
Для того чтоб число g, взаимно обычное с
было первообразным корнем по модулю
нужно и довольно, чтоб это
не удовлетворяло ни одному из сравнений:
,
,…,
.
метод 9
Нахождение первообразного корня, [Молдовян Н.А. и др., 2004].
Обычное число n, q1
,
q2
,…,
qk
разные обыкновенные делители функции Эйлера 
Первообразный корень g.
1. Генерация числа 1 < g < n.
2. Для i = 1,2,
k выполнить последующие деяния.
2.1. Если 
перейти к шагу 1.
3. Число g первообразный корень по модулю n.
Код функции pervoobr (нахождение первообразного корня):
void pervoobr(int mass[300]){
unsigned char g[33]={0};
unsigned char c[33]={0};
unsigned char b[33]={0};
int i,k,t,x,flag;
srand(time(0));
for(i=0;i<=31;i++){
g[i]=mod[i];
mod[i]=mod2[i];
osn[i]=0;
}
for(k=0;k<=1000;k++){
flag=2;
for(i=0;i<=28;i++) osn[i]=rand();
del(mod,g,st);
step(c);
x=rav(c);
if(x!=0){
flag=1;
for(i=0;i<=31;i++){
c[i]=0;
for(i=0;i<=300;i++){
if(mass[i]!=0){
c[0]=mass[i];
c[1]=(mass[i]>>8);
del(mod,c,b);
for(t=0;t<=31;t++)st[t]=b[t];
step(b);
x=rav(b);
if(x==0) flag=0;
}
}
}
}
if(flag==1){
break;
}
}
}
Глава 3. Оценка метода.
3.1. Оценка криптостойкости метода
протокол обмена ключами Диффи–Хеллмана не обеспечивает аутентичности согласованного ключа. Активный противник, внедренный в канал связи меж 2-мя юзерами А и Б, может манипулировать сообщениями протокола и начать атаку “человек в центре” (man-in-the-middle attack).
В процессе данной для нас атаки Злодей перехватывает и перекрывает 1-ое сообщение от А к Б, т. е. число gа
, маскируется под А и отправляет Б последующее сообщение.
Злодей (под именованием А) — Б: gm
= gm
(mod p).
Б , следуя инструкциям протокола, возвращает Злодею (под именованием А) число gb
. Это число опять перехватывается и блокируется Злоумышленником. Сейчас Злодей и Б согласовали меж собой ключ gb
m
=(mod p) , хотя Б считает , что он поделил этот ключ с А.
Аналогично Злодей, имитируя Б, может согласовать иной ключ с А (т.е. число ga
m
(mod p)). Потом Злодей может применять оба ключа для чтения и замены “скрытых” сообщений, которыми обмениваются А и Б, либо попеременно имитировать этих юзеров.
Атака на протокол обмена ключами Диффи–Хеллмана полностью реальна, так как этот протокол не предугадывает проверки аутентичности источника сообщений. Для того чтоб ключи были согласованы лишь меж А и Б, обе стороны должны быть убеждены друг в друге.
Минусы программной реализации, снижающие стойкость:
-при вычислении функции step(), описанной чуть повыше, возникает ровная зависимость времени вычисления от количества единиц (при бинарном представлении) в степени. Что может отдать
3.2. Оценка скорости работы метода
Оценка выполнялась на компе:
Тип ЦП AMD Sempron, 1666 MHz ,2400+
Чипсет системной платы nVIDIA nForce2 Ultra 400
Системная память 1024 Мб (DDR SDRAM)
Более долгой является операция генерации огромного обычного числа p , такового что p-1 раскладывается на обыкновенные множители, при этом разложение обязано иметь один большенный обычный множитель, и нахождение первообразного корня. Этот процесс является вероятностным и может привести к неопределенной отсрочке.
Результаты тестирования программки приведены в таблице 1.
Таблица 1.
тест на время реализации базисных операций программного продукта
время генерации, сек.
Количество испытанных значений, ед.
Скорость проверки значений, ед./сек.
16
2700
168,8
34
7400
217,6
26
4400
169,2
160
23300
145,6
48
10000
208,3
83
17600
212,0
4
400
100,0
137
23900
174,5
5
600
120,0
Среднее
168,5
Основная перегрузка для проверки скорости работы лежит на функции вычисления степени по модулю. Скорость работы метода зависит от избранной степени, чем больше единиц в бинарном представлении степени, тем подольше будет происходить операция возведения в степень по модулю.
З
аключение
В процессе курсовой работы был исследован метод распределения ключей Диффи-Хеллмана и реализован на языке программирования С++. Приобретенный программный продукт отвечает требованиям, предъявляемым к системе открытого распространения ключей Диффи-Хеллмана.
У программного продукта есть недочеты:
-при вычислении функции step( ), описанной чуть повыше, возникает ровная зависимость времени вычисления от количества единиц (при бинарном представлении) в степени. Что может отдать задачки и на основании их изготовлены надлежащие выводы.
Литература
]]>