2015-10-22
3722
Система, предложенная Эль Гамалем, является, как и RSA системой с открытым ключом. Ее криптостойкость основана на трудоемкости вычисления дискретного логарифма (т. е. трудоемкости операции логарифмирования в целых числах по модулю N).
Ключи строятся так:
Выбирается целое число P;
Выбирается число W меньшее P-1, тогда WP-1 = 1 mod P, при этом, WD¹1 mod P при любом 1<D<(P-1);
Выбирается 1 < X < P-1; Y:= WX mod P;
Секретный ключ -- (X,P);
Открытый ключ -- (Y,W,P).
Шифрование блока B протекает следующим образом (открытый ключ):
1. Берется случайное число 1 < K < P-1;
2. R:= YK mod P;
3. Z:= WK;
4. C:= BÅR;;
5. Результат -- пара (C,Z).
Расшифрование протекает следующим образом (секретный ключ):
1. R:= ZX;
2. B:= CÅR.
Данная система является альтернативой RSA и при равном значении ключа обеспечивает ту же криптостойкость[5].
В отличие от RSA метод Эль-Гамаля основан на проблеме дискретного логарифма. Этим он похож на алгоритм Диффи-Хелмана. Если возводить число в степень в конечном поле достаточно легко, то восстановить аргумент по значению (то есть найти логарифм) довольно трудно, поскольку поиск решения ведётся методом перебора аргументов.
|
|
|
Ключом может быть любое число меньшее P потому что если P - простое число, то для любого X выполняется равенство (теорема Ферма)
Исследование цифровой подписи на примере алгоритма RSA
Цель работы
Изучить основные принципы генерации цифровой подписи. Освоить цифровую подпись на основе алгоритма RSA.
Домашнее задание
Изучить цифровую подпись на основе алгоритма RSA в соответствии с пунктом 4.6 данного методического руководства.
Записать вариант, соответствующий двум младшим цифрам номера студенческого билета.
По таблице простых чисел (?) выбрать 2 простых числа. Номер числа P = 9+последняя цифра студенческого билета, номер числа Q = 17 + предпоследняя цифра студенческого билета.
Вычислить произведение этих чисел N=P´Q и функцию Эйлера j(N)=M=(P-1)(Q-1);
Используя алгоритм Евклида найти такое число D, взаимно простое с M, которое не является простым.
Подписать сообщение и проверить подпись (сообщение = 143) по алгоритму RSA
Все вычисления должны быть занесены в протокол в виде?
Таблица 4.1 Цифровая подпись по алгоритму RSA
| Исследуемая величина | Домашнее задание | Лабораторное задание |
| Простое число Р | ||
| Простое число Q | ||
| N=PQ | ||
| M=(P-1)(Q-1) | ||
| D взаимно простое с M | ||
| E=1/D (mod M) | ||
| Секретный ключ (E, N) | ||
| Открытый ключ (D, N) | ||
| Исходное сообщение B | ||
| Подпись C=BE(mod N) | ||
| Проверка подписи B'=CD(mod N) |
Подготовиться к ответам на ключевые вопросы
Ключевые вопросы
|
|
|
1. Как формируется цифровая подпись
2. Как формируется цифровая сигнатура
3. Объяснить значение термина аутентификация
4. Объяснить значение термина отказ
5. Объяснить значение термина модификация
6. Объяснить значение термина подделка
7. Объяснить значение термина активный перехват
8. Объяснить значение термина маскировка
9. Объяснить значение термина повтор
10.Для защиты от каких нарушений используется цифровая подпись
11.Для защиты от каких нарушений используется цифровая сигнатура
12.Какие методы используются для борьбы с повторами
13.Чем отличается цифровая подпись на основе алгоритма RSA от алгоритма шифрования RSA
Содержание протокола
1. Название работы.
2. Цель работы.
3. Выполненное домашнее задание согласно номеру варианта
4. Результаты выполнения лабораторного задания
5. Выводы
Лабораторное задание
1. Предъявить преподавателю выполненное домашнее задание.
2. Найти в каталоге STUDENT файл под именем LabCrypt.exe и запустить эту программу.
3. Из появившегося меню вызвать форму для лабораторной работы №5
4. Записать в форму и таблицу свои числа Р и Q согласно номеру варианта
5. Вычислить N и M и занести в таблицу
6. Занести в форму D, вычисленное в домашнем задании
7. Вычислить Е обратное D по модулю N и занести в таблицу
8. Определить секретный и открытый ключи, занести их в таблицу
9. подписать и проверить подпись для заданного сообщения, результаты занести в таблицу.
10.Записать выводы, подготовить протокол к защите.
Ключевые положения
Электронная подпись
В чем состоит проблема аутентификации данных?
В конце обычного письма или документа исполнитель или ответственное лицо обычно ставит свою подпись. Подобное действие обычно преследует две цели. Во-первых, получатель имеет возможность убедиться в истинности письма, сличив подпись с имеющимся у него образцом. Во-вторых, личная подпись является юридическим гарантом авторства документа. Последний аспект особенно важен при заключении разного рода торговых сделок, составлении доверенностей, обязательств и т.д.
Если подделать подпись человека на бумаге весьма непросто, а установить авторство подписи современными криминалистическими методами - техническая деталь, то с подписью электронной дело обстоит иначе. Подделать цепочку битов, просто ее скопировав, или незаметно внести нелегальные исправления в документ сможет любой пользователь.
С широким распространением в современном мире электронных форм документов (в том числе и конфиденциальных) и средств их обработки особо актуальной стала проблема установления подлинности и авторства безбумажной документации.
В разделе криптографических систем с открытым ключом было показано, что при всех преимуществах современных систем шифрования они не позволяют обеспечить аутентификацию данных. Поэтому средства аутентификации должны использоваться в комплексе и криптографическими алгоритмами.
Итак, пусть имеются два пользователя Александр и Борис. От каких нарушений и действий злоумышленника должна защищать система аутентификации.
Отказ (ренегатство).
Александр заявляет, что он не посылал сообщение Борису, хотя на самом деле он все-таки посылал.
Для исключения этого нарушения используется электронная (или цифровая) подпись.
Модификация (переделка).
Борис изменяет сообщение и утверждает, что данное (измененное) сообщение послал ему Александр.
Подделка.
Борис формирует сообщение и утверждает, что данное (измененное) сообщение послал ему Александр.
Активный перехват.
Владимир перехватывает сообщения между Александром и Борисом с целью их скрытой модификации.
Для защиты от модификации, подделки и маскировки используются цифровые сигнатуры.
|
|
|
Маскировка (имитация).
Владимир посылает Борису сообщение от имени Александра.
В этом случае для защиты также используется электронная подпись.
Повтор.
Владимир повторяет ранее переданное сообщение, которое Александр посылал ранее Борису. Несмотря на то, что принимаются всевозможные меры защиты от повторов, именно на этот метод приходится большинство случаев незаконного снятия и траты денег в системах электронных платежей.
Наиболее действенным методом защиты от повтора являются
* использование имитовставок,
* учет входящих сообщений.
Цифровая сигнатура
Часто возникают ситуации, когда получатель должен уметь доказать подлинность сообщения внешнему лицу. Чтобы иметь такую возможность, к передаваемым сообщениям должны быть приписаны так называемые цифровые сигнатуры.
Цифровая сигнатура - это строка символов, зависящая как от идентификатора отправителя, так и содержания сообщения.
Никто при этом кроме пользователя А не может вычислить цифровую сигнатуру А для конкретного сообщения. Никто, даже сам пользователь не может изменить посланного сообщения так, чтобы сигнатура осталась неизменной. Хотя получатель должен иметь возможность проверить является ли цифровая сигнатура сообщения подлинной. Чтобы проверить цифровую сигнатуру, пользователь В должен представить посреднику С информацию, которую он сам использовал для верификации сигнатуры.
Если помеченное сигнатурой сообщение передается непосредственно от отправителя к получателю, минуя промежуточное звено, то в этом случае идет речь об истинной цифровой сигнатуре.
Рассмотрим типичную схему цифровой сигнатуры.
Пусть Е - функция симметричного шифрования и f - функция отображения некоторого множества сообщений на подмножество мощности р из последовательности {1,..., n }.
Например р=3 и n =9. Если m - сообщение, то в качестве f можно взять функцию f (m) = {2, 5, 7}.
Для каждого сообщения пользователь А выбирает некоторое множество ключей K =[ K 1,..., K n} и параметров V={v1,...,vn} для использования в качестве пометок сообщения, которое будет послано В. Множества V и V’={E(v1, K 1)..., E(vn, K n)} посылаются пользователю В и заранее выбранному посреднику С.
|
|
|
Пусть m - сообщение и idm - объединение идентификационных номеров отправителя, получателя и номера сообщения. Если f( {idm, m }), то цифровая сигнатура m есть множество K ’=[ K i,..., K j}. Сообщение m, идентификационный номер idm и цифровая сигнатура К’ посылаются В.
Получатель В проверяет сигнатуру следующим образом. Он вычисляет функцию f( {idm, m }) и проверяет ее равенство К’. Затем он проверяет, что подмножество {vi,...,vj} правильно зашифровано в виде подмножества {E(vi, K i)..., E(vj, K j)} множества V’.
В конфликтной ситуации В посылает С сообщение m, идентификационный номер idm и множество ключей K ’, которое В объявляет сигнатурой m. Тогда посредник С так же, как и В, будет способен проверить сигнатуру. Вероятность раскрытия двух сообщений с одним и тем же значением функции f должна быть очень мала. Чтобы гарантировать это, число n должно быть достаточно большим, а число р должно быть больше 1, но меньше n.
Ряд недостатков этой модели очевиден:
* должно быть третье лицо - посредник, которому доверяют как получатель, так и отправитель;
* получатель, отправитель и посредник должны обменяться существенным объемом информации, прежде чем будет передано реальное сообщение;
* передача этой информации должна осуществляться в закрытом виде;
* эта информация используется крайне неэффективно, поскольку множества K, V, V’ используются только один раз.
Тем не менее даже такая схема цифровой сигнатуры может использоваться в информационных системах, в которых необходимо обеспечить аутентификацию и защиту передаваемых сообщений.
