Задачи для самостоятельной работы
1. Найти мультипликативную группу кольца классов-вычетов по модулю m. Выяснить, является ли найденная группа циклической, если:
а) m = 4; б) m = 5; в) m = 6; г) m = 7; д) m = 8; е) m = 9; ж) m = 10; з) m = 11; и) m = 12; к) m = 13; л) m = 14; м) m = 15.
В циклических группах найти все порождающие элементы.
2. Найти ключ, полученный Бобом и Алисой, при применении ими криптографического протокола Диффи – Хеллмана, для следующих значений p (простое число), g (порождающий элемент в мультипликативной группе конечного поля Z 
, a (секретный ключ Алисы), b (секретный ключ Боба):
а) p =23, g =10, a =3, b =7; б) p =23, g = 20, a =5, b =10;
в) p =43, g =3, a =3, b =9; г) p =43, g = 3, a =5, b =10;
д) p =103, g =5 , a =11, b =7; е) p =103, g =35 , a =2, b =7.
3. Найти ключ, полученный Бобом, Алисой и Дэйвом при применении ими криптографического протокола Диффи – Хеллмана, для следующих значений p (простое число), g (порождающий элемент в мультипликативной группе конечного поля Z , a (секретный ключ Алисы), b (секретный ключ Боба), c (секретный ключ Дэйва):
а)p =23, g =5, a =4, b =7, с =9; б)p =23, g = 5, a =5, b =10, с =9;
в)p =43, g =3, a =5, b =6, с =9; г)p =43, g = 3, a =7, b =11, с =9;
д) p =103, g =5 , a =11, b =7, с =2; е) p =103, g =5 , a =2, b =7, с =5.
Схема Эль – Гамаля
Схема была предложена Тахером Эль-Гамалем в 1984 году. Эль-Гамаль разработал один из вариантов алгоритма Диффи-Хеллмана. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. Существует большое количество алгоритмов, основанных на схеме Эль-Гамаля: это алгоритмы DSA, ECDSA, KCDSA, схема Шнорра.
|
|
|
Рассмотрим оба алгоритма Эль-Гамаля.
Алгоритм шифрования Эль-Гамаля
I. Генерация ключей.
1) Генерируется случайное простое число р длины п битов.
2) Выбирается произвольное целое число g, являющееся порождающим элементом в мультипликативной группе конечного поля Z .
3) Выбирается случайное целое число х такое, что 
.
4) Вычисляется 
.
5) Открытым ключом является тройка (р, g , у), закрытым ключом – число х.
II. Шифрование.
Сообщение М шифруется следующим образом:
1) Выбирается сессионный ключ – случайное целое число k такое, что 
.
2) Вычисляются числа 
и 
.
3) Пара чисел (a , b) является шифротекстом.
Видно, что длина шифротекста в схеме Эль – Гамаля длиннее исходного сообщения М вдвое.
III. Расшифрование.
Зная закрытый ключ х, исходное сообщение можно вычислить из шифротекста (a , b) по формуле:
.
При этом нетрудно проверить, что 
и поэтому
.
Пример 1. Зашифруем сообщение М =10.
Произведем генерацию ключей.
Пусть р = 23, g = 5. Выберем х = 4 – случайное целое число х, такое что 
.
Вычислим y = g 
mod 23 = 
mod 23 = 4.
Открытым ключом является тройка (р, g , у) = (23, 5, 4), а закрытым – число х = 4.
|
|
|
Произведем шифрование.
Выбираем случайное целое число k такое, что . Пусть k = 6.
Вычисляем число a = g 
mod 23 = 5 
mod 23 = 8.
Вычисляем число b = 
y M mod 23 = 4 10 mod 23 = 20.
Полученная пара (a , b) = (8, 20) является шифротекстом.
Произведем расшифрование.
Необходимо получить сообщение М = 5 по известному шифротексту (a , b) = (8, 20) и закрытому ключу х = 4.
Вычисляем М:
= 20 (8 
) 
= 20 (2) = 10.
Итак, получили исходное сообщение М = 10.
Так как в схему Эль-Гамаля вводится случайная величина k, то шифр Эль-Гамаля можно назвать шифром многозначной замены. Из-за случайности выбора числа k такую схему еще называют схемой вероятностного шифрования. Вероятностный характер шифрования является преимуществом для схемы Эль-Гамаля, так как у схем вероятностного шифрования наблюдается большая стойкость по сравнению со схемами с определенным процессом шифрования. Недостатком схемы шифрования Эль-Гамаля является удвоение длины зашифрованного текста по сравнению с начальным текстом.
Цифровая подпись Эль-Гамаля
Рассмотрим систему цифровой подписи Эль-Гамаля, основанную на схеме формирования открытых и секретных ключей, которая используется в методе Диффи-Хеллмана. Пусть мы имеем большое простое число p, такое, что разложение числа p – 1 содержит, по крайней мере, один большой простой множитель и порождающий элемент g мультипликативной группы конечного поля Z .
|
|
|
Механизм подписывания состоит в следующем. Абонент Алиса выбирает секретный ключ x, с помощью которого находит y = g . Тройка ( p , g , y ) является открытым ключом. Пусть абоненту Алисе нужно подписать документ M. Подписываемое сообщение должно иметь длину меньше простого модуля p, т.е. M < p . Для того, чтобы подписать сообщение, его сначала нужно перевести в числовую форму. Это делается с помощью некоторой хэш-функции.
Хэширование – преобразование по некоторому алгоритму входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свёртки, а их результаты называют хешем, хеш-кодом или дайджестом сообщения.
Хэш-функция определенным образом преобразовывает символы текста, так, чтобы в дайджесте не осталось ничего от свойств исходного текста. Теоретически может существовать множество разных текстов, имеющих одинаковый дайджест. Но хорошая хэш-функция отличается тем, что практически нереально подобрать текст под заданный дайджест.
|
|
|
Существует множество алгоритмов хеширования с различными свойствами. Выбор той или иной хеш-функции определяется спецификой решаемой задачи. Простейшим примером хеш-функций может служить контрольная сумма.
Итак, Алиса применяет некоторую хэш-функцию H ( X ), значениями которой могут быть целые числа в интервале (1, p-1)и получает дайджест H ( M ) = m сообщения M .
Подписью абонента Алисы под документом M служит пара чисел (r , s ) , где 0 ≤ r < p - 1 и 0 ≤ s < p – 1, которая удовлетворяет уравнению (g 
) = y 
r 
( mod p ).
Это уравнение служит для проверки того факта, что документ подписан абонентом Алиса.
Данная система электронной цифровой подписи основана на том, что только действительный владелец секретного ключа x может выработать пару чисел (r , s), удовлетворяющую уравнению проверки подписи. Используя значение x , абонент Алисавырабатывает подпись сообщения M по следующему алгоритму:
1) Вычисляет дайджест H ( M ) = m сообщения M .
2) Генерирует случайноечисло k, удовлетворяющее условию:
0 < k < p – 1 и НОД (k , p – 1) = 1.
3) Вычисляет r = g ( mod p ).
4) Вычисляет s = (m – xr)k (mod p-1).
5) Подписью сообщения M являетсяпара чисел (r , s).
Замечание. Выбор числа k так, чтобы НОД (k , p – 1) = 1 обусловлен тем, что в этом случае будет существовать элемент k .
Владелец секретного ключа в состоянии подписать документ, а его подпись может быть проверена по его открытому ключу. Нахождение пары чисел (r , s) без знания секретного ключа вычислительно сложно. Различных подписей, соответствующих данному документу, может быть чрезвычайно много, т.к. k может иметь различные значения, но выработать правильную подпись способен только владелец секретного ключа. Множество возможных подписей отличаются значением r, но для данного r найти соответствующее значение s без знания секретного ключа практически невозможно. Для вычисления секретного ключа по открытому ключу необходимо решить задачу дискретного логарифмирования, которая является вычислительно сложной.
Зная открытый ключ ( p , g , y ), подпись сообщения M проверяется следующим образом:
1) Проверяется выполнимость условий: 0 < r < p и 0 < s < p – 1 . Если хотя бы одно из них не выполняется, то подпись считается неверной.
2) Вычисляется дайджест H ( M ) = m сообщения M .
3) Подпись считается верной, если выполняется сравнение:
g = y r ( mod p ).
Пример 2. Подпишем сообщение М =ключ.
Произведем генерацию ключей.
Возьмем значения р, g, х, y как в примере 1. Открытым ключом является тройка (р, g , у) = (23, 5, 4), а закрытым – число х = 4.
Произведем шифрование.
1) Пусть дайджест H ( M ) = m сообщения M равен 7.
2) Выбираем случайное целое число k такое, что . Пусть k = 3. Вычисляем число r = g mod 23 = 5 
mod 23 = 10.
3) Вычисляем число
s = (m – xr)k (mod p-1) = (7 – 40) 15 mod 23 = 11.
4) Подписью сообщения M являетсяпара чисел (10, 11).
Произведем проверку подлинности полученного сообщения.
1) Проверяется выполнимость условий: 0 < 10 < 23,
0 < 11 < 23 .
2) Вычисляем дайджест H ( M ) = m = 7 сообщения M .
3) Проверяем сравнение g = y r mod p .
Вычислим левую часть по модулю 23: 5 
mod 23 = 17.
Вычислим правую часть по модулю 23: 4 
10 
( mod 23) =17.
Так как правая и левая части равны, то это означает, что подпись верна.
Главным преимуществом схемы цифровой подписи Эль-Гамаля является возможность вырабатывать цифровые подписи для большого числа сообщений с использованием только одного секретного ключа. Чтобы злоумышленнику подделать подпись, ему нужно решить сложные математические задачи с нахождением логарифма в поле Z . Следует сделать несколько комментариев:
Случайное число должно сразу после вычисления подписи уничтожаться, так как если злоумышленник знает случайное число и саму подпись, то он легко может найти секретный ключ и полностью подделать подпись.
Число k должно не должно дублироваться для различных подписей, полученных при одинаковом значении секретного ключа.
Цифровая подпись Эль-Гамаля стала примером построения других подписей, схожих по своим свойствам, в частности, для стандартов DSS (Digital Signature Standard) цифровой подписи США и ГОСТ Р34.10-1994, принятого в 1994 году в Российской Федерации.
С 2001 года используется новый ГОСТ Р 34.10-2001, использующий арифметику эллиптических кривых, определенных над простыми конечными полями.
Дата добавления: 2019-02-12; просмотров: 218; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!