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

- 3 -

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

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

Федеральное государственное образовательное учреждение высшего профессионального образования

«Чувашский государственный университет» им. И. Н. УЛЬЯНОВА

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

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

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

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

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

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

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

Терентьева Т .С.

Принял доцент

Михайлов А.Л.

Чебоксары 2007 г.



Задание

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

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

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

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



Содержание

Введение

1.Схема идентификации Феидж-Фиат-Шамир

1.1 Установка

1.2 Процедура

1.3 Безопасность

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

2.1 Требования к цифровой подписи

2.2 Стандарт цифровой подписи DSS

2.3 Алгоритм цифровой подписи

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

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

3.2. Выравнивание сообщения

3.3. Логические функции

3.4. Вывод SHA-1

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

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

4.2. Текст программы для реализации протокола

4.2.1 Реализация алгоритма FFS и ЭЦП DSS

4.2.2 Контроль целостности SHA

4.3 Результат работы программы

Заключение

Литература



Введение

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

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

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



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).

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

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

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

, где

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

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

Общеизвестные элементы
Q	простое число
A	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. Электронная цифровая подпись DSS

2.1 Требования к цифровой подписи

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

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

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

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

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

1. Должна быть возможность проверить автора, дату и время создания подписи.

2. Должна быть возможность аутентифицировать содержимое во время создания подписи.

3. Подпись должна быть проверяема третьей стороной для разрешения споров.

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

На основании этих свойств можно сформулировать следующие требования к цифровой подписи:

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

2. Подпись должна использовать некоторую уникальную информацию отправителя для предотвращения подделки или отказа.

3. Создавать цифровую подпись должно быть относительно легко.

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

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

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

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

Прямая и арбитражная цифровые подписи

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

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

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

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

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

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

Рассмотрим некоторые возможные технологии арбитражной цифровой подписи.

Симметричное шифрование, арбитр видит сообщение:

Х A: M || E_Kxa [ ID_X || H (M)]

Предполагается, что отправитель Х и арбитр А разделяют секретный ключ K_ХА и что А и Y разделяют секретный ключ K_АY. Х создает сообщение М и вычисляет его хэш-значение Н (М). Затем Х передает сообщение и подпись А. Подпись состоит из идентификатора Х и хэш-значения, все зашифровано с использованием ключа K_ХА. А дешифрует подпись и проверяет хэш-значение.

A Y: Е_Кay [ ID_X M

E_Kxa [ID_X H (M)], T ]

Затем А передает сообщение к Y, шифруя его K_AY. Сообщение включает ID_X, первоначальное сообщение от Х, подпись и отметку времени. Y может дешифровать его для получения сообщения и подписи. Отметка времени информирует Y о том, что данное сообщение не устарело и не является повтором. Y может сохранить М и подпись к нему. В случае спора Y, который утверждает, что получил сообщение М от Х, посылает следующее сообщение к А:



Е_Кay [ ID_X M E_Kxa [ID_X H (M)] ]

Арбитр использует K_AY для получения ID_Х, М и подписи, а затем, используя K_ХА, может дешифровать подпись и проверить хэш-код. По этой схеме Y не может прямо проверить подпись Х; подпись используется исключительно для разрешения споров. Y считает сообщение от Х аутентифицированным, потому что оно прошло через А. В данном сценарии обе стороны должны иметь высокую степень доверия к А:

1. Х должен доверять А в том, что тот не будет раскрывать K_ХА и создавать фальшивые подписи в форме Е_Kка [ID_X H (M)].

2. Y должен доверять А в том, что он будет посылать Е_Kay [ ID_X M E_Kxa [ID_X H (M)] ] только в том случае, если хэш-значение является корректным и подпись была создана Х.

3. Обе стороны должны доверять А в решении спорных вопросов.

Симметричное шифрование, арбитр не видит сообщение:

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

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

X A: ID_X E_Kхy [M]

E_Kxa [ID_X H (E_KXY [M]) ]

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

A Y: E_Kay [ ID_X E_KXY[M]

E_Kxa [ ID_X H ( E_KXY [M])], T]

А передает Y все, что он получил от Х плюс отметку времени, все шифруя с использованием ключа K_AY.

Хотя арбитр и не может прочитать сообщение, он в состоянии предотвратить подделку любого из участников, Х или Y. Остается проблема, как и в первом сценарии, что арбитр может сговориться с отправителем, отрицающим подписанное сообщение, или с получателем, для подделки подписи отправителя.

Шифрование открытым ключом, арбитр не видит сообщение:

Все обсуждаемые проблемы могут быть решены с помощью схемы открытого ключа.

X A: ID_X E_KRх [ ID_X E_KUy [E_KRx [M] ] ]

В этом случае Х осуществляет двойное шифрование сообщения М, сначала своим закрытым ключом KR_X, а затем открытым ключом Y KU_Y. Получается подписанная секретная версия сообщения. Теперь это подписанное сообщение вместе с идентификатором Х шифруется KR_X и вместе с ID_X посылается А. Внутреннее, дважды зашифрованное, сообщение недоступно арбитру (и всем, исключая Y). Однако А может дешифровать внешнюю шифрацию, чтобы убедиться, что сообщение пришло от Х (так как только Х имеет KR_X). Проверка дает гарантию, что пара закрытый/открытый ключ законна, и тем самым верифицирует сообщение.



A Y: E_KRa [ ID_X E_KUy [E_KRx [M] ] T ]

Затем А передает сообщение Y, шифруя его KR_A. Сообщение включает ID_X, дважды зашифрованное сообщение и отметку времени.

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

2.2 Стандарт цифровой подписи DSS

Национальный институт стандартов и технологии США (NIST) разработал федеральный стандарт цифровой подписи DSS. Для создания цифровой подписи используется алгоритм DSA (Digital Signature Algorithm). В качестве хэш-алгоритма стандарт предусматривает использование алгоритма SHA-1 (Secure Hash Algorithm). DSS первоначально был предложен в 1991 году и пересмотрен в 1993 году в ответ на публикации, касающиеся безопасности его схемы.

Подход DSS

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

Рассмотрим отличия подхода, используемого в DSS для создания цифровых подписей, от применения таких алгоритмов как RSA.



Рис. 2.2.1 Создание и проверка подписи с помощью алгоритма RSA

Рис. 2.2.2 Создание и проверка подписи с помощью стандарта DSS

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

Подход DSS также использует сильную хэш-функцию. Хэш-код является входом функции подписи вместе со случайным числом k, созданным для этой конкретной подписи. Функция подписи также зависит от закрытого ключа отправителя KR_a и множества параметров, известных всем участникам. Можно считать, что это множество состоит из глобального открытого ключа KU_G. Результатом является подпись, состоящая из двух компонент, обозначенных как s и r.

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

Теперь рассмотрим детали алгоритма, используемого в DSS.

2.3 Алгоритм цифровой подписи

DSS основан на трудности вычисления дискретных логарифмов и базируется на схеме, первоначально представленной ElGamal и Schnorr.

Общие компоненты группы пользователей

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

160-битное простое число q, т.е. 2¹⁵⁹ < q < 2¹⁶⁰.

Простое число р длиной между 512 и 1024 битами должно быть таким, чтобы q было делителем (р - 1), т.е. 2^L-1 < p < 2^L, где 512 < L < 1024 и (p-1)/q является целым.

g = h^(p-1)/q mod p,

где h является целым между 1 и (р-1) и g должно быть больше, чем 1,10.

Зная эти числа, каждый пользователь выбирает закрытый ключ и создает открытый ключ.

Закрытый ключ отправителя

Закрытый ключ х должен быть числом между 1 и (q-1) и должен быть выбран случайно или псевдослучайно.

x - случайное или псевдослучайное целое,

0 < x < q ,

Открытый ключ отправителя

Открытый ключ вычисляется из закрытого ключа как

у = g^x mod p.

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

y = g^x mod p

Случайное число, уникальное для каждой подписи

k - случайное или псевдослучайное целое, 0 < k < q, уникальное для каждого подписывания.

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

Для создания подписи отправитель вычисляет две величины, r и s, которые являются функцией от компонент открытого ключа (p, q, g), закрытого ключа пользователя (х), хэш-кода сообщения Н (М) и целого k, которое должно быть создано случайно или псевдослучайно и должно быть уникальным при каждом подписывании.

r = (g^k mod p) mod q

s = [ k^-1 (H (M) + xr) ] mod q

Подпись = (r, s)

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

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

w = s^-1 mod q

u₁ = [ H (M) w ] mod q

u₂ = r w mod q

v = [ (g^u1 y^u2) mod p ] mod q

подпись корректна, если v = r

Докажем, что v = r в случае корректной подписи.

Лемма 1. Для любого целого t, если

g = h^(p-1)/q mod p

то g^t mod p = g^{t mod q} mod p

По теореме Ферма, так как h является взаимнопростым с p, то h^p-1 mod p = 1. Следовательно, для любого неотрицательного целого n

gnq mod p	= (h(p-1)/q mod p)nq mod p
	= h((p-1)/q) nq mod p

	= h(p-1)n mod p
	= ((h(p-1) mod p)n) mod p
	= 1n mod p = 1

Таким образом, для неотрицательных целых n и z мы имеем

gnq+z mod p	= (gnq gz) mod p
	= ((gnq mod p) (gz mod p )) mod p
	= gz mod p

Любое неотрицательное целое t может быть представлено единственным образом как

t = nq + z,

где n и z являются неотрицательными целыми и 0 < z < q. Таким образом z = t mod q.

Лемма 2. Для неотрицательных чисел a и b:

g^{(a mod q + b mod q)} mod p = g^{(a+b) mod q} mod p.

По лемме 1 мы имеем

g^{(a mod q + b mod q)} mod p = g^{(a mod q + b mod q) mod q} mod p = g^{(a + b) mod q} mod p

Лемма 3.

y^{(rw) mod q} mod p = g^{(xrw) mod q} mod p

По определению

y = g^x mod p. Тогда:

y^{(rw) mod q} mod p = (g^x mod p)^{(rw) mod q} mod p по правилам

= g^{x ((rw) mod q)} mod p модульной арифметики

= g^{(x ((rw mod q))) mod q} mod p по лемме 1

= g^{(xrw) mod q} mod p

Лемма 4.

((H(M) + xr) w) mod q = k



По определению

s = (k^-1 (H(M) + xr)) mod q.

Кроме того, так как q является простым, любое неотрицательное целое меньшее q имеет мультипликативную инверсию. Т.е.

(k k^-1) mod q = 1.

Тогда:

(ks) mod q = (k((k^-1(H(M) + xr)) mod q)) mod q

= (k (k^-1(H(M) + xr))) mod q

= ((k^k-1) mod q) ((H(M) + xr) mod q) mod q

= (H(M) + xr) mod q

По определению

w = s^-1 mod q,

следовательно, (ws) mod q = 1. Следовательно:

((H(M) + xr) w) mod q = (((H(M) + xr) mod q) (w mod q)) mod q

= (((ks) mod q) (w mod q)) mod q

= (kws) mod q

= (k mod q) ((ws) mod q)) mod q

= k mod q

Так как 0 < k < q, то k mod q = k.



Теорема. Используя определения для v и r, докажем, что v=r.

v = ((g^u1 y^u2) mod p) mod q

= ((g^{(H(M) w) mod q} y^{(rw) mod q)} mod p) mod q

= ((g^{(H(M) w) mod q} g^{(xrw) mod q)} mod p) mod q

= ((g^{(H(M) w) mod q + (xrw) mod q)} mod p) mod q

= ((g^{(H(M) w + xrw) mod q)} mod p) mod q

= ((g^{w (H(M) + xr) mod q)} mod p) mod q

= (g^{k mod p)} mod q

= r



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

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

Алгоритм SHA-1 (Secure Hash Algorithm) используется в алгоритмах электронно-цифровых подписей (DSA - Digital Signature Algorithm). Для сообщения (потока данных) длиной меньше 2^64 бита, данный алгоритм вычисляет 160-битный хэш. Полученный хэш используется для генерации "подписи" к сообщению, а также для ее проверки. Любые изменения в исходном сообщении приведут к изменению хэша с очень большой вероятностью.

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

В данном алгоритме под "словом" понимается количество информации в 32 бита, "байт" - 8 бит. Целое число в промежутке от 0 до 2^32 - 1 включительно может быть представлено как слово, в котором старший байт записан первым, младший - последним. Целое z (0 <= z < 2^64) представляется в виде z = (2^32)x + y, где x и y - целые в промежутке от 0 до 2^32 - 1. Таким образом, z можно представить парой слов x и y. Блок из 512 бит может быть представлен последовательностью из 16 слов.

В алгоритме используются следующие операции:

x & y - побитовое "И"

x | y - побитовое "ИЛИ"

x ^ y - побитовое "исключающее ИЛИ"

~x - побитовое отрицание

x <<< y - циклический сдвиг x влево на y бит

x + y = (x + y) mod 2^32, т.е. рассматриваются младшие 32 бита результат.

3.2 Выравнивание сообщения

Длина сообщения принимается как количество бит во входном потоке (возможно пустое сообщение длиной 0 бит). Цель выравнивания: сделать длину сообщения кратной 512, т.к. алгоритм SHA-1 обрабатывает входной поток блоками по 512 бит. Выравнивание проиходит следующим образом: добавляется один бит '1' (a), затем следуют биты '0' (b), после чего записывается длина сообщения до выравнивания (c). В результате получаем длину потока равную n*512.

Пример: допустим входной поток бит имел следующий вид:

01100001 01100010 01100011 01100100 01100101 (40 бит)

после шага (a) cообщение принимает вид:

01100001 01100010 01100011 01100100 01100101 1 (41 бит)

на шаге (b) добавляются 407 '0', что в шестнадцатиричном виде выглядит так:

61626364 65800000 00000000 00000000

00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000000

00000000 00000000

на шаге (c) добавляем длину до выравнивания: 40 - 00000000 00000028 (hex); и получаем выравненное сообщение:

61626364 65800000 00000000 00000000

00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000028

Далее будем рассматривать входной поток как массив M[0 ... N-1] слов длиной N.

3.3 Логические функции

SHA-1 использует последовательность логических функций f(0), f(1), ... f(79), каждая из которых принимает 3 32-битных слова и вычисляет результат - слово. Функция f(t; B, C, D) определена следующим видом:

f(t; B, C, D) = (B & C) | (~B & D) 0 <= t <= 19

f(t; B, C, D) = B ^ C ^ D 20 <= t <= 39

f(t; B, C, D) = (B & C) | (B & D) | (C & D) 40 <= t <= 59

f(t; B, C, D) = B ^ C ^ D 60 <= t <= 79

Константы.

В данном алгоритме используется последовательность константных слов K(0), K(1), ... , K(79):

K(t) = 5A827999 0 <= t <= 19

K(t) = 6ED9EBA1 20 <= t <= 39

K(t) = 8F1BBCDC 40 <= t <= 59

K(t) = CA62C1D6 60 <= t <= 79

Вычисление

Для вычисления SHA-1 хэш функции используется буфер из 5 слов {H0, H1, H2, H3, H4}, который перед началом вычислений инициализируется следующими значениями:

H0 = 67452301

H1 = EFCDAB89

H2 = 98BADCFE

H3 = 10325476

H4 = C3D2E1F0

Для каждого блока M[i] выполняются следующие вычисления (MASK = 0x0F):

a. разложить M[i] на 16 слов W[0], ... , W[15], где W[0] - крайнее слева слово в M[i]

b. сохранить H0, H1, H2, H3, H4

A = H0, B = H1, C = H2, D = H3, E = H4

c.

for t = 0 to 79 do

{

s = t & MASK;

if (t >= 16)

W[s] = (W[(s + 13) & MASK] ^ W[(s + 8) & MASK] ^

W[(s + 2) & MASK] ^ w[s]) <<< 1;

temp = (A <<< 5) + f(t; B, C, D) + E + W[s] + K(t);

E = D; D = C; C = B <<< 30; B = A; A = temp;

}

d. H0 += A; H1 += B; H2 += C; H3 += D; H4 += E;



3.4 Вывод SHA-1

Результат вычислений записывается пятью словами в порядке H0, H1, H2, H3, H4. Вычисленный хэш имеет длину 160 бит.



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

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

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

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

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

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

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

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



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

нет да

+

4.2 Текст программы для реализации протокола

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

4.2.1 Реализация алгоритма FFS и ЭЦП DSS

#include "stdafx.h"

#include "math.h"

#include "Resource.h"

#include "FFS_SHA_DSSDlg.h"

#include "sha.h"

#include "Crypt.h"

bool keysGenerated = false;

uint32 p, q, n;

uint32 s, v;

/* параметры системы DSS */

uint32 dss_p = 2741, dss_q = 137, r = 20, h = 1699, g = 2476;

/* ключи для DSS */

uint32 keys[2];

void generateKeys()

{

randomize();

/* generate parameters for FFS */

p = findPrime(); OUTNUM(p);

q = findPrime(); OUTNUM(q);

n = p * q; OUTNUM(n);

s = random(1, n-1); OUTNUM(s);

v = s * s % n; OUTNUM(v);

/* generate keys for DSS */

keys[0] = random(1, dss_q-1); OUTNUM(keys[0]);

keys[1] = xymodn(g, keys[0], dss_p); OUTNUM(keys[1]);

keysGenerated = true;

}

void randomize()

{

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

}

uint32 random(uint32 limit)

{

return rand() % limit;

}

uint32 random(uint32 from, uint32 to)

{

return random(to - from) + from;

}

bool isPrime(uint32 a)

{

for (uint32 d=2; d<(uint32)sqrt( (double)a); d++)

if (a % d == 0)

return false;

return true;

}

uint32 findPrime()

{

while (true) {

uint32 r = random(0x100) + 2;

if (isPrime(r) )

return r;

}

}

uint32 extendedEuclid(sint32 a, sint32 b, sint32 &x, sint32 &y)

{

sint32 _a = a, _b = b;

sint32 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;

}

void outStr(wchar_t *s)

{

int index = mainDlg->m_log.GetCount();

mainDlg->m_log.InsertString(index, s);

}

void outNum(wchar_t *what, uint32 n)

{

wchar_t buf[1024], bufN[32];

_itow(n, bufN, 10);

wcscpy(buf, what);

wcscat(buf, bufN);

outStr(buf);

}

void outArray(wchar_t *what, uint32 *a, int n)

{

wchar_t buf[1024], bufN[32], space[] = L" ";

wcscpy(buf, what);

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

_itow(a[i], bufN, 10);

wcscat(buf, bufN);

wcscat(buf, space);

}

outStr(buf);

}

bool roll()

{

return rand() % 2 == 1;

}

bool feigeFiatShamir()

{

/* step 1 */

uint32 r = random(n - 2) + 1; OUTNUM(r);

bool sign = roll(); OUTBOOL(sign);

uint32 x = r * r % n;

if (sign)

x = n - x;

OUTNUM(x);

/* step 2 */

bool a = roll(); OUTBOOL(a);

/* step 3 */

uint32 y = r;

if (a)

y = y * s % n;

OUTNUM(y);

/* step 4 */

uint32 z = x;

if (a)

z = z * v % n;

if (sign)

z = n - z;

OUTNUM(z);

return z == y * y % n;

}

/** returns 0 if inverse does not exist */

uint32 invmod(uint32 a, uint32 p)

{

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

if (d != 1)

return 0;

while (x < 0)

x = x + p;

return (uint32)x;

}

uint32 xymodn(uint32 a, uint32 n, uint32 m)

{

uint32 p = 1;

uint32 q = a;

while (n > 0) {

if (n % 2 == 1)

p = (p * q) % m;

q = (q * q) % m;

n /= 2;

}

return p;

/*uint32 r = 1;

for (uint32 i=0; i<n; i++)

r = r * a % m;

return r;*/

}

uint32 findRelativePrime(uint32 n)

{

while (true) {

sint32 x = random(0x100);

sint32 a, b, d = extendedEuclid(x, n, a, b);

if (d == 1)

return (uint32)x;

}

}

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

{

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

uint32 x = privateKey;

uint32 y = publicKey;

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

uint32 dss_k = random(1, dss_q-1); OUTNUM(dss_k);

uint32 r = xymodn(g, dss_k, dss_p); OUTNUM(r);

uint32 e = hashSum(message, len, r); OUTNUM(e);

uint32 s = (dss_k + x * e % dss_q) % dss_q; OUTNUM(s);

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

uint32 rv1 = xymodn(g, s, dss_p); OUTNUM(rv1);

uint32 rv2 = invmod(xymodn(y, e, dss_p), dss_p); OUTNUM(rv2);

uint32 vv = rv1 * rv2 % dss_p; OUTNUM(vv);

uint32 v = hashSum(message, len, vv); OUTNUM(v);

if (v == e) {

int *pd = (int *)digest;

*pd = e;

pd++;

*pd = s;

return;

} else

outStr(L"signMessage: digest do not match\n");

}

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

{

int *pd = (int *)digest;

uint32 e = *pd; OUTNUM(e);

pd++;

uint32 s = *pd; OUTNUM(s);

uint32 y = publicKey; OUTNUM(y);

uint32 rv1 = xymodn(g, s, dss_p); OUTNUM(rv1);

uint32 rv2 = invmod(xymodn(y, e, dss_p), dss_p); OUTNUM(rv2);

uint32 vv = rv1 * rv2 % dss_p; OUTNUM(vv);

uint32 v = hashSum(message, len, vv); OUTNUM(v);

return (v == e);

}



4.2.2 Контроль целостности SHA

#include "stdafx.h"

#include <stdio.h>

#include <string.h>

typedef unsigned int uint32;

typedef unsigned char uint8;

/** циклический сдвиг влево */

uint32 rol(uint32 a, uint32 s)

{

__asm {

mov eax,a

mov ecx,s

rol eax,cl

mov a,eax

}

return a;

}

uint32 rev(uint32 n)

{

uint8 a0 = n & 0xff;

uint8 a1 = (n >> 8) & 0xff;

uint8 a2 = (n >> 16) & 0xff;

uint8 a3 = (n >> 24) & 0xff;

return ( ( ( ( (a0 << 8) + a1) << 8) + a2) << 8) + a3;

}

uint32 f(int t, uint32 B, uint32 C, uint32 D)

{

if (t <= 19)

return (B & C) | (~B & D);

else if (t <= 39)

return B ^ C ^ D;

else if (t <= 59)

return (B & C) | (B & D) | (C & D);

else if (t <= 79)

return B ^ C ^ D;

else

printf("f: bad t: %d\n", t);

}

uint32 K(int t)

{

/* if (t <= 19)

return 0x5A827999;

else if (t <= 39)

return 0x6ED9EBA1;

else if (t <= 59)

return 0x8F1BBCDC;

else if (t <= 79)

return 0xCA62C1D6;*/

if (t <= 19)

return rev(0x5A827999);

else if (t <= 39)

return rev(0x6ED9EBA1);

else if (t <= 59)

return rev(0x8F1BBCDC);

else if (t <= 79)

return rev(0xCA62C1D6);

else

printf("K: bad t: %d\n", t);

}

void sha(int turns, uint32 *data, uint32 *hash)

{

uint32 W[16];

uint32 H[5] = { rev(0x67452301), rev(0xEFCDAB89), rev(0x98BADCFE), rev(0x10325476), rev(0xC3D2E1F0) };

uint32 A, B, C, D, E;

for (int turn=0; turn<turns; turn++) {

/* a */

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

W[i] = *data;

data++;

}

/* b */

A = H[0];

B = H[1];

C = H[2];

D = H[3];

E = H[4];

/* c */

for (int t=0; t<80; t++) {

uint32 s = t & 0x0f;

if (t >= 16)

W[s] = rol(W[(s + 13) & 0x0f] ^ W[(s + 8) & 0x0f] ^ W[(s + 2) & 0x0f] ^ W[s], 1);

uint32 temp = rol(A, 5) + f(t, B, C, D) + E + W[s] + K(t);

E = D;

D = C;

C = rol(B, 30);

B = A;

A = temp;

}

/* d */

H[0] += A;

H[1] += B;

H[2] += C;

H[3] += D;

H[4] += E;

}

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

*hash = H[i];

hash++;

}

}

void dumpHex(char *data, int len)

{

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

printf("%02x ", *data & 0xff);

data++;

}

}

void shaBlock(char *data, int len, char *hash)

{

int oldLen = len;

if (len % 64 != 0) {

int requiredLen = (len / 64 + 1) * 64;

char *addByte = data + len;

*addByte = 0x70;

addByte++;

while (len != requiredLen) {

*addByte = 0;

addByte++;

len++;

}

uint32 *addLen = (uint32 *)data + (len / sizeof(uint32) ) - 1;

*addLen = rev(oldLen);

}

sha(len / 64, (uint32 *)data, (uint32 *)hash);

}

void test(char *word)

{

char data[8096];

char hash[20];

strcpy(data, word);

shaBlock(data, strlen(word), hash);

printf("%-20s", word);

dumpHex(hash, 20);

printf("\n");

}

uint32 hashSum(char *word, int len, uint32 add)

{

printf("hashSum: message = '%s', add = %d\n", word, add);

char data[8096];

char hash[20];

strcpy(data, word);

uint32 *addPlace = (uint32 *)(data + len);

*addPlace = add;

shaBlock(data, len + 4, hash);

uint32 r = 0;

uint32 *m = (uint32 *)hash;

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

r ^= *m;

m++;

}

return r & 0xffff;

}

4.3 Результат работы программы

Рис. 4.3.1 Генерация ключа

Рис. 4.3.2. Отправка сообщения

Рис.4.3.3. Сообщение в message.txt, а ЭЦП в файле sign.bin



Рис. 4.3.4. ЭЦП не изменилась.



Заключение

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



Литература

1. Прикладная криптография, 2-е изд., Брюс Шнайер - Нью-Йорк. .

2. Кнут Д. Искусство программирования, том 2. Получисленные алгоритмы, 3-е изд. -- М.: Издательский дом «Вильямс», 2001.

3. INTUIT.ru: Интернет-Университет Информационных Технологий, 10.лекция: Цифровая подпись

4. Учебный центр CITFORUM.RU

5. Wade Trappe, Lawrence C. Washington, Introduction to Cryptography with Coding Theory (Prentice-Hall, Inc., 2003), pp. 231-233.

Retrieved from "http://en.wikipedia.org/wiki/Feige-Fiat-Shamir_Identification_Scheme"

6. Учебный центр SecurityLab.ru