Передача аутентичного информационного сообщения по каналу связи

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

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

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

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

«Чувашский государственный университет»

Им. И. Н. Ульянова

Технический институт

факультет Дизайна и компьютерных технологий

Кафедра компьютерных технологий

КУРСОВОЙ ПРОЕКТ

Дисциплина: Методы и средства защиты информации

Тема: Передача аутентичного информационного сообщения по каналу связи

Выполнил студент гр. ДиКТ 21-04

Камалетдинов А.А.

Чебоксары 2007 г

Задание

Разработать на основе заданного варианта протокол установления связи с абонентом, а также аутентификацию и передачу информационного сообщения:

* Аутентификация с помощью алгоритма Диффи-Хеллмана;

* Электронная цифровая подпись Шнорра;

* Контроль целостности передаваемых сообщений MD5.

 Введение

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

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

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

1. Основные требования к алгоритмам асимметричного шифрования

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

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

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

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

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

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

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

Диффи и Хеллман описывают требования, которым должен удовлетворять алгоритм шифрования с открытым ключом.

1. Вычислительно легко создавать пару (открытый ключ , закрытый ключ ).

2. Вычислительно легко, имея открытый ключ и незашифрованное сообщение , создать соответствующее зашифрованное сообщение:

3. Вычислительно легко дешифровать сообщение, используя закрытый ключ:

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

5. Вычислительно невозможно, зная открытый ключ и зашифрованное сообщение , восстановить исходное сообщение .

Можно добавить шестое требование, хотя оно не выполняется для всех алгоритмов с открытым ключом:

6. Шифрующие и дешифрующие функции могут применяться в любом порядке:

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

- легко

- трудно

Обычно "легко" означает, что проблема может быть решена за полиномиальное время от длины входа. Таким образом, если длина входа имеет битов, то время вычисления функции пропорционально , где - фиксированная константа. Таким образом, говорят, что алгоритм принадлежит классу полиномиальных алгоритмов

Термин "трудно" означает более сложное понятие. В общем случае будем считать, что проблему решить невозможно, если усилия для ее решения больше полиномиального времени от величины входа. Например, если длина входа битов, и время вычисления функции пропорционально то это считается вычислительно невозможной задачей. К сожалению, тяжело определить, проявляет ли конкретный алгоритм такую сложность. Более того, традиционные представления о вычислительной сложности фокусируются на худшем случае или на среднем случае сложности алгоритма. Это неприемлемо для криптографии, где требуется невозможность инвертировать функцию для всех или почти всех значений входов.

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

-легко, если и известны

-легко, если и известны

-легко, если известно, но неизвестно

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

1.1 Криптоанализ алгоритмов с открытым ключом

Как и в случае симметричного шифрования, алгоритм шифрования с открытым ключом уязвим для лобовой атаки. Контрмера стандартная: использовать большие ключи.

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

Другая форма атаки состоит в том, чтобы найти способ вычисления закрытого ключа, зная открытый ключ. Невозможно математически доказать, что данная форма атаки исключена для конкретного алгоритма открытого ключа. Таким образом, любой алгоритм, включая широко используемый алгоритм RSA, является подозрительным. Наконец, существует форма атаки, специфичная для способов использования систем с открытым ключом. Это атака вероятного сообщения. Предположим, например, что посылаемое сообщение состоит исключительно из 56-битного ключа сессии для алгоритма симметричного шифрования. Противник может зашифровать все возможные ключи, используя открытый ключ, и может дешифровать любое сообщение, соответствующее передаваемому зашифрованному тексту. Таким образом, независимо от размера ключа схемы открытого ключа, атака сводится к лобовой атаке на 56-битный симметричный ключ. Защита от подобной атаки состоит в добавлении определенного количества случайных битов в простые сообщения

1.2 Основные способы использования алгоритмов с открытым ключом

Основными способами использования алгоритмов с открытым ключом являются шифрование/дешифрование, создание и проверка подписи и обмен ключа.

Шифрование с открытым ключом состоит из следующих шагов:

Рис. 1.2. Шифрование с открытым ключом

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

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

3. Если хочет послать сообщение , он шифрует сообщение, используя открытый ключ .

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

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

Создание и проверка подписи состоит из следующих шагов:

Рис. 1.3. Создание и проверка подписи

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

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

3. Если хочет послать подписанное сообщение , он создает подпись для этого сообщения, используя свой закрытый ключ.

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

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

В этой схеме все сообщение подписывается, причем для подтверждения целостности сообщения требуется много памяти. Каждое сообщение должно храниться в незашифрованном виде для использования в практических целях. Кроме того, копия сообщения также должна храниться в зашифрованном виде, чтобы можно было проверить в случае необходимости подпись. Более эффективным способом является шифрование небольшого блока битов, который является функцией от сообщения. Такой блок, называемый аутентификатором, должен обладать свойством невозможности изменения сообщения без изменения аутентификатора. Если аутентификатор зашифрован закрытым ключом отправителя, он является цифровой подписью, с помощью которой можно проверить исходное сообщение. Далее эта технология будет рассматриваться в деталях.

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

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

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

Перечислим наиболее популярные алгоритмы с открытым ключом и возможные способы их применения.

Алгоритм	Шифрование / дешифрование	Цифровая подпись	Обмен ключей
RSA	Да; непригоден для больших блоков	Да	Да
DSS	Нет	Да	Нет
Диффи-Хеллман	Нет	Нет	Да

1.3 Аутентификация с помощью алгоритма Диффи-Хеллмана

Данный параграф посвящен еще одному интересному алгоритму, который достаточно трудно классифицировать. Он помогает обмениваться секретным ключом для симметричных криптосистем, но использует метод, очень похожий на асимметричный алгоритм RSA. Алгоритм назван по фамилиям его создателей Диффи (Diffie) и Хеллмана (Hellman).

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

Алгоритм основан на трудности вычислений дискретных логарифмов. Дискретный логарифм определяется следующим образом. Вводится понятие примитивного корня простого числа как числа, чьи степени создают все целые от до . Это означает, что если является примитивным корнем простого числа , тогда числа

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

, где

Экспонента называется дискретным логарифмом, или индексом , по основанию. Это обозначается как

Теперь опишем алгоритм обмена ключей Диффи-Хеллмана.

Общеизвестные элементы
простое число
A < Q и A является примитивным корнем Q

Создание пары ключей пользователем I
Выбор случайного числа Хi (закрытый ключ)	Xi < Q
Вычисление числа Yi (открытый ключ)	Yi = AXi mod Q

Создание открытого ключа пользователем J
Выбор случайного числа Хj (закрытый ключ)	Xj < Q
Вычисление случайного числа Yj (открытый ключ)	Yj = AXj mod Q

Создание общего секретного ключа пользователем I
K = (Yj)Xi mod Q

Создание общего секретного ключа пользователем J
K = (Yi)Xj mod Q

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

Теперь пользователь вычисляет ключ как , и пользователь вычисляет ключ как

.

В результате оба получат одно и то же значение:

по правилам модульной арифметики

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



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

Следует заметить, что данный алгоритм уязвим для атак типа "man-in-the-middle". Если противник может осуществить активную атаку, т.е. имеет возможность не только перехватывать сообщения, но и заменять их другими, он может перехватить открытые ключи участников и , создать свою пару открытого и закрытого ключа (,) и послать каждому из участников свой открытый ключ. После этого каждый участник вычислит ключ, который будет общим с противником, а не с другим участником. Если нет контроля целостности, то участники не смогут обнаружить подобную подмену.

Необходимо еще раз отметить, что алгоритм Диффи-Хеллмана работает только на линиях связи, надежно защищенных от модификации. Если бы он был применим на любых открытых каналах, то давно снял бы проблему распространения ключей и, возможно, заменил собой всю асимметричную криптографию. Однако, в тех случаях, когда в канале возможна модификация данных, появляется очевидная возможность вклинивания в процесс генерации ключей "злоумышленника-посредника" по той же самой схеме, что и для асимметричной криптографии.

2. Электронная цифровая подпись

2.1 Общая схема цифровой подписи

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

Вероятностный алгоритм или система генерирования ключей. Каждый абонент получает пару ключей (,), где -- открытый ключ, а -- тайный.

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

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

Следует отметить, что для алгоритмов и для любого сообщения и пары ключей и должно выполнятся условие . Это соотношение определяет корректность системы цифровой подписи.

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

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

Итак, рассмотрев общую схему построения цифровой подписи, приступим к описанию конкретных систем цифровой подписи.

2.2 Система Шнорра

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

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

Вариант укорачивающей функции с ключом называется кодом достоверности. Если -- укорачивающая функция с ключом , то код достоверности сообщения равен .

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

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

Следует отметить, что каждую укорачивающую функцию можно преобразовать в функцию с ключом по такому правилу: .

Примером укорачивающей функции может служить функция, которая строится на основе RSA-функций. На практике же используются более быстрые укорачивающие функции, например, функции MD5 и SHA.

Разобравшись с вышеприведенным теоретическим материалом, приступим к рассмотрению системы Шнорра, названной в честь ее разработчика Клауса Шнорра.

Начнем с процесса генерирования ключей. Выбираем такое большое простое число , что имеет достаточно большой простой делитель (разработчиком системы рекомендуется выбирать , . Потом выбирают число , которое удовлетворяет соотношению: . Числа ,, не являются тайными. Далее абонент выбирает случайное число , такое что: . Теперь следует найти число . Открытым ключом будет число , для которого выполняется условие: . Тайным ключом выбирается число .

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

1. Выбирается случайное число .

2. Вычисляется .

3. Находится значение укорачивающей функции , где -- слияние сообщения и числа в один текст.

4. Вычисляется .

5. В качестве подписи принимается пара: .

Для проверки подписи абонент находит значение и проверяет равность .

3. Контроль целостности передаваемых сообщений MD5

3.1 Логика выполнения MD5

Рассмотрим алгоритм получения дайджеста сообщения MD5 (RFC 1321), разработанный Роном Ривестом из MIT.

Логика выполнения MD5:

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

Рис. 3.1. Логика выполнения MD5

Шаг 1: добавление недостающих битов

Сообщение дополняется таким образом, чтобы его длина стала равна 448 по модулю 512 (длина 448 mod 512). Это означает, что длина добавленного сообщения на 64 бита меньше, чем число, кратное 512. Добавление производится всегда, даже если сообщение имеет нужную длину. Например, если длина сообщения 448 битов, оно дополняется 512 битами до 960 битов. Таким образом, число добавляемых битов находится в диапазоне от 1 до 512.

Добавление состоит из единицы, за которой следует необходимое количество нулей.

Шаг 2: добавление длины

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

В результате первых двух шагов создается сообщение, длина которого кратна 512 битам. Это расширенное сообщение представляется как последовательность 512-битных блоков , ,..., , при этом общая длина расширенного сообщения равна битам. Таким образом, длина полученного расширенного сообщения кратна шестнадцати 32-битным словам.

Рис. 3.2. Структура расширенного сообщения

Шаг 3: инициализация MD-буфера

Используется 128-битный буфер для хранения промежуточных и окончательных результатов хэш-функции. Буфер может быть представлен как четыре 32-битных регистра (A, B, C, D). Эти регистры инициализируются следующими шестнадцатеричными числами:

А = 01234567

В = 89ABCDEF

C = FEDCBA98

D = 76543210

Шаг 4: обработка последовательности 512-битных (16-словных) блоков

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

Рис. 3.3. Обработка очередного 512-битного блока

Каждый цикл принимает в качестве входа текущий 512-битный блок , обрабатывающийся в данный момент, и 128-битное значение буфера , которое является промежуточным значением дайджеста, и изменяет содержимое этого буфера. Каждый цикл также использует четвертую часть 64-элементной таблицы , построенной на основе функции . -ый элемент , обозначаемый , имеет значение, равное целой части от , задано в радианах. Так как является числом между 0 и 1, каждый элемент является целым, которое может быть представлено 32 битами. Таблица обеспечивает "случайный" набор 32-битных значений, которые должны ликвидировать любую регулярность во входных данных.

Для получения выход четырех циклов складывается по модулю с . Сложение выполняется независимо для каждого из четырех слов в буфере.

Шаг 5: выход

После обработки всех 512-битных блоков выходом -ой стадии является 128-битный дайджест сообщения.

Рассмотрим более детально логику каждого из четырех циклов выполнения одного 512-битного блока. Каждый цикл состоит из 16 шагов, оперирующих с буфером . Каждый шаг можно представить в виде:

Рис. 3.4. Логика выполнения отдельного шага

,

где

- четыре слова буфера; после выполнения каждого отдельного шага происходит циклический сдвиг влево на одно слово;

- одна из элементарных функций , , ,;

- циклический сдвиг влево на битов 32-битного аргумента;

- -ое 32-битное слово в -ом 512 блоке сообщения;

- -ое 32-битное слово в матрице ;

+ - сложение по модулю

На каждом из четырех циклов алгоритма используется одна из четырех элементарных логических функций. Каждая элементарная функция получает три 32-битных слова на входе и на выходе создает одно 32-битное слово. Каждая функция является множеством побитовых логических операций, т.е. -ый бит выхода является функцией от -ого бита трех входов. Элементарные функции следующие:

Массив из 32-битных слов содержит значение текущего 512-битного входного блока, который обрабатывается в настоящий момент. Каждый цикл выполняется 16 раз, а так как каждый блок входного сообщения обрабатывается в четырех циклах, то каждый блок входного сообщения обрабатывается по схеме 64 раза. Если представить входной 512-битный блок в виде шестнадцати 32-битных слов, то каждое входное 32-битное слово используется четыре раза, по одному разу в каждом цикле, и каждый элемент таблицы , состоящей из 64 32-битных слов, используется только один раз. После каждого шага цикла происходит циклический сдвиг влево четырех слов , , и . На каждом шаге изменяется только одно из четырех слов буфера . Следовательно, каждое слово буфера изменяется 16 раз, и затем 17-ый раз в конце для получения окончательного выхода данного блока.

Можно суммировать алгоритм MD5 следующим образом:

где

- начальное значение буфера , определенное на шаге 3;

- -ый 512-битный блок сообщения;

- число блоков в сообщении (включая поля дополнения и длины);

- окончательное значение дайджеста сообщения

3.2 Усиление алгоритма в MD5

Алгоритм MD5 имеет следующее свойство: каждый бит хэш-кода является функцией от каждого бита входа. Комплексное повторение элементарных функций , , и обеспечивает то, что результат хорошо перемешан; то есть маловероятно, чтобы два сообщения, выбранные случайно, даже если они имеют явно похожие закономерности, имели одинаковый хэш-код. Считается, что MD5 является наиболее сильной хэш-функцией для 128-битного хэш-кода, то есть трудность нахождения двух сообщений, имеющих одинаковый дайджест, имеет порядок операций. В то время, как трудность нахождения сообщения с данным дайджестом имеет порядок операций.

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

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

4. Разработка протокола установления связи с абонентом

4.1 Протокол установления связи с абонентом

Алгоритм протокола:

1. С помощью алгоритма Диффи-Хеллмана выбираем ключ, который будет использоваться для шифрования передаваемого сообщения;

2. Шифруем сообщение. Для этого может использоваться любой симметричный шифр. Шифруем самым простым методом - побайтовый XOR исходного сообщения с ключем;

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

ключ отправителя; при этом в алгоритме происходит вычисление хеш-суммы MD5 сообщения;

4. На стороне получателя принимаем сообщение и проверяем цифровую подпись, используяоткрытый ключ отправителя;

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

Блок-схема алгоритма

4.2 Программная реализация протокола

Программа написана на Visual C++.

#include "stdafx.h"

#include <stdexcept>

#include <string>

#include "md5.h"

#include "data.h"

#include "numbers.h"

using namespace std;

CBigInt p = 2741, q = 137, r = 20, h = 1699, g = 2476;

void randomize()

{srand((unsigned int)time(NULL));}

int random(int limit)

{return rand() % limit;}

/** Дихотомическое возведение в степень */

CBigInt xymodn(CBigInt a, CBigInt n, CBigInt m)

{

/*CBigInt _a = a, _n = n, _m = m;

CBigInt p = 1;

CBigInt q = a;

while (n.getValue() > 0) {

if (n.isOdd())

p = multmod(p, q, m);

q = multmod(q, q, m);

n = n.getValue() >> 1;

}

return p;*/

int _a=a.getValue(), _n=n.getValue(), _m=m.getValue();

int p=1, q=a.getValue();

while (_n>0) {

if (_n & 0x01 != 0)

p = multmod(p, q, m).getValue();

q = multmod(q, q, m).getValue();

_n >>= 1;

}

return p;

}

CBigInt multmod(CBigInt a, CBigInt b, CBigInt m)

{

return (int)((__int64)a.getValue() * (__int64)b.getValue() % (__int64)m.getValue());

}

/** Сгенерировать ключи по алгоритму Диффи-Хеллмана */

void generateKeys()

{

/* Diffie-Hellman */

CBigInt _a = CBigInt::random(1, 0x7fffffff);

CBigInt _g = CBigInt::random(1, 0x7fffffff);

CBigInt _p = CBigInt::random(1, 0x7fffffff);

CBigInt _b = CBigInt::random(1, 0x7fffffff);

CBigInt _A = xymodn(_g, _a, _p);

CBigInt _B = xymodn(_g, _b, _p);

CBigInt _KA = xymodn(_B, _a, _p);

CBigInt _KB = xymodn(_A, _b, _p);

if (_KA != _KB)

throw logic_error("generateKeys: keys does not match!");

secretKey = _KA;

/* generate keys for digisign */

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

keys[i][0] = CBigInt::random(1, q-1);

keys[i][1] = xymodn(g, keys[i][0], p);//invmod(xymodn(h, a, p), p);

}

keyGenerated = true;

sayNumber("Diffie-Hellman: key generated: ", secretKey);

}

void sayNumber(char *msg, CBigInt &num)

{

string s = msg;

char tmp[4];

int parts[4];

int n = num.getValue();

for (int i=3; i>=0; i--) {

parts[i] = n & 0xff;

n >>= 8;

}

for (i=0; i<4; i++) {

sprintf(tmp, "%02x ", parts[i]);

s += tmp;

}

say((char *)s.c_str());

}

void encrypt(char *buf, int len)

{

int key = secretKey.getValue();

char keyParts[4];

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

keyParts[i] = key & 0xff;

key >>= 8;

}

int keyOffs = 0;

for (i=0; i<len; i++) {

int t = buf[i];

t ^= keyParts[keyOffs];

t &= 0xff;

buf[i] = t;

keyOffs++;

if (keyOffs == 2)

keyOffs = 0;

}

}

void decrypt(char *buf, int len)

{

encrypt(buf, len);

}

CBigInt extendedEuclid(CBigInt a, CBigInt b, CBigInt &x, CBigInt &y)

{

CBigInt _a = a, _b = b;

CBigInt q, r, x1, x2, y1, y2;

if (b == 0) {

x = 1;

y = 0;

return a;

}

x2 = 1,

x1 = 0,

y2 = 0,

y1 = 1;

while (b > 0) {

q = a / b;

r = a - q * b;

x = x2 - q * x1;

y = y2 - q * y1;

a = b;

b = r;

x2 = x1;

x1 = x;

y2 = y1;

y1 = y;

}

x = x2;

y = y2;

return a;

}

/** Инверсия элемента группы */

CBigInt invmod(CBigInt a, CBigInt p)

{

CBigInt x, y, d = extendedEuclid(a, p, x, y);

while (x < 0)

x = x + p;

return x;

}

#define ENSUREPOS(x) ASSERT(x.getValue() >= 0)

CBigInt hashSum(char *buf, int len, CBigInt add)

{

char *buf1 = new char[len + 4];

memcpy(buf1, buf, len);

char sum[16];

int *padd = (int *)(buf1 + len);

*padd = add.getValue();

md5_csum((unsigned char *)buf1, len + 4, (unsigned char *)sum);

int *cs0 = (int *)&sum[0];

int *cs1 = (int *)&sum[4];

int *cs2 = (int *)&sum[8];

int *cs3 = (int *)&sum[12];

return abs(*cs0 ^ *cs1 ^ *cs2 ^ *cs3) & 0xffffff;

}

int _multmod(int a, int b, int m)

{

return (int)((__int64)a * (__int64)b % (__int64)m);

}

/** Дихотомическое возведение в степень */

int _xymodn(int a, int n, int m)

{

int _a = a, _n = n, _m = m;

int p = 1;

int q = a;

while (n > 0) {

if (n & 0x01 != 0)

p = _multmod(p, q, m);

q = _multmod(q, q, m);

n >>= 1;

}

return p;

}

void signMessage(CBigInt privateKey, CBigInt publicKey, char *message, int len, char* digest)

{

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

CBigInt x = privateKey;

CBigInt y = publicKey;

/* подписывание */

CBigInt k = CBigInt::random(0, q-2)+1;

CBigInt r = xymodn(g, k, p);

CBigInt e = hashSum(message, len, r);

CBigInt s = (k + multmod(x, e, q)) % q;

/* проверка подписи */

CBigInt rv1 = xymodn(g, s, p);

CBigInt rv2 = invmod(xymodn(y, e, p), p);

CBigInt rv = multmod(rv1, rv2, p);

CBigInt ev = hashSum(message, len, rv);

if (e == ev) {

int *pd = (int *)digest;

*pd = e.getValue();

pd++;

*pd = s.getValue();

return;

} else

MessageBox(0, "No", NULL, 0);

}

bool checkSign(CBigInt publicKey, char *message, int len, char *digest)

{

int *pd = (int *)digest;

CBigInt e = *pd;

pd++;

CBigInt s = *pd;

CBigInt y = publicKey;

CBigInt rv1 = xymodn(g, s, p);

CBigInt rv2 = invmod(xymodn(y, e, p), p);

CBigInt rv = multmod(rv1, rv2, p);

CBigInt ev = hashSum(message, len, rv);

return (e == ev);

}



Результат выполнения программы:

Зашифрованное сообщение находится в файле message.bin:

Заключение

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



Приложение

Диффи-Хеллман:

Общеизвестные числа v и n:

n = 89a2e31

v = c1840ae

Абоненты загадывают числа x и y:

x = 79ec13

y = c90f54a

Абоненты вычисляют x = v^xmodn и y = v^ymodn:

x = 3acffad

y = b6d549d

Теперь оба абонента считают ключ:

K1 = x^y modn = b35dd

K2 = y^x modn = b35dd

K1 = K2 = K - ключ шифрования.

Подпись Шнорра:

Находим параметры щифрования:

1. р - простое число. р = 2741

2. находим q и r: p=q*r+1 и q - простое число

q = 137

r = 20

3. h: h^r ? 1(modp). h = 1699

4. g = h^r modp. g = 2476

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

1. x: 0<x<q. x = 67 - секретный ключ

2. y = g^x. y = 886 - открытый ключ

Подписывание:

1. k: 0<k<q. k = 40

2. r = g^kmodp. r = 95

3. e = f(М||r)

f - хэш-ф-я MD5, М - текст сообщения, || - операция сложения строк

е = 1701894956

4. s = (k + xe)modq. s = 125

Проверка подписи:

1. r_V = gs*ye. r_V=95

2. e_V = f(M||r_V). e_V=1701894956

e = e_V, подпись сошлась.