Тест числа на простоту (стр. 2 из 2)
подпись вернаПоскольку цифровая подпись обеспечивает как аутентификацию автора сообщения, так и подтверждение целостности содержимого подписанного сообщения, она служит аналогом подписи, сделанной от руки в конце рукописного документа.
Важное свойство цифровой подписи заключается в том, что её может проверить каждый, кто имеет доступ к открытому ключу ее автора. Один из участников обмена сообщениями после проверки подлинности цифровой подписи может передать подписанное сообщение ещё кому-то, кто тоже в состоянии проверить эту подпись.
Заметим, что подписанное сообщение L1 не зашифровано. Оно пересылается в исходном виде и его содержимое не защищено. Путём совместного применения представленных выше схем шифрования и цифровой подписи в системе RSA можно создавать сообщения, которые будут и зашифрованы, и содержать цифровую подпись. Для этого автор сначала должен добавить к сообщению свою цифровую подпись, а затем - зашифровать получившуюся в результате пару (состоящую из самого сообщения и подписи к нему) с помощью открытого ключа принадлежащего получателю. Получатель расшифровывает полученное сообщение с помощью своего секретного ключа. Если проводить аналогию с пересылкой обычных бумажных документов, то этот процесс похож на то, как если бы автор документа поставил под ним свою печать, а затем положил его в бумажный конверт и запечатал, с тем чтобы конверт был распечатан только тем человеком, кому адресовано сообщение.
RSA
Пример
Сначала нужно сгенерировать ключ
Выбираем два простых ключа p=13, q=41
Вычисляем модуль n=p*q = 13*41 =533
Вычисляем функцию Эйлера φ (n) = (p-1) * (q-1) = (13-1) * (41-1) = 480
Выбираем открытый показатель е = 13
Вычисляем секретный показатель d = 37
Открытый ключ (e,n) = (13, 533)
Секретный ключ (d,n) = (37, 533)
Шифрование
Выбираем открытый текст L = 4545
Вычисляем шифротекст G (L) = Lemodn = 99
Расшифрование
Вычисляем исходное сообщение
N (C) = Сdmodn = 4545
Алгоритм Эль-Гамаля
Схема Эль-Гамаля (Elgamal) - криптосистема, предложенная в 1984 году. Схема Эль-Гамаля лежит в основе стандартов электронной цифровой подписи в США и России.
Генерация ключей
Генерируется случайное простое число p длины n.
Выбирается произвольное целое число g, являющееся первообразным корнем по модулю p.
Выбирается случайное число x из интервала (1,p), взаимно простое с p-1.
Вычисляется
Открытым ключом является тройка (p, g, y), закрытым ключом - число x.
Работа в режиме шифрования выглядит следующим образом:
шифруется сообщение М
Выбирается случайное секретное число k, взаимно простое с p − 1.
Вычисляется a = gk (mod p),b = yk M (mod p), где M - исходное сообщение.
Пара чисел (a,b) является шифротекстом.
Длина шифротекста в схеме Эль-Гамаля длиннее исходного сообщения M вдвое.
Расшифрование сообщение осуществляется следующим образом
Зная закрытый ключ x, исходное сообщение можно вычислить из шифротекста (a,b) по формуле:
и 
Режим подписи сообщения
При работе в режиме подписи предполагается наличие фиксированной хеш-функции h, значения которой лежат в интервале (1, p − 1).
Подпись сообщений
Для подписи сообщения M выполняются следующие операции:
Вычисляется дайджест сообщения M: m = h (M).
Выбирается случайное число 1 < k < p − 1 взаимно простое с p-1 и вычисляется
.С помощью расширенного алгоритма Евклида вычисляется число s, удовлетворяющее сравнению:
Подписью сообщения M является пара (r,s).
Проверка подписи
Зная открытый ключ (p,g,y), подпись (r,s) сообщения M проверяется следующим образом:
Проверяется выполнимость условий: 0 < r < p и 0 < s < p − 1. Если хотя бы одно из них не выполняется, то подпись считается неверной.
Вычисляется дайджест m = h (M).
Подпись считается верной, если выполняется сравнение:
.DSS (Digital Signature Standard) цифровой подпись
Алгоритм:
выбирается простое число q приблизительно в 160 бит (для этого используются генератор случайных чисел и тест на простату)
выбирается другое простое число р, сравнимое с 1 по модулю q размером приблизительно в 512 бит
выбирается порождающий элемент, для этого вычисляется
для случайного целого g0, если g ≠1, то он и будет порождающим элементомвыбирается секретный ключ как случайное целое число х из диапазона 0<x<q. В качестве открытого ключа берется
.Пример. Пусть А хочет подписать сообщение. Сначала А принимает своему ОТ хеш функцию и получает целое число h из диапазона 0<h<q. Затем А выбирает случайное целое kиз того же диапазона и вычисляет
. Пусть r- наименьший неотрицательный вычет по модулю qпоследнего выражение. Значит, gk сначала вычисляется по модулю р, а результат приводиться по меньшему простому модулю q. Наконец, А находит такое целое s, что 
. Пара (r,s) вычетов по модулю q является ее подписью.Чтобы проверить подпись, получатель В вычисляет
и 
. Потом он вычисляет 
. Если результат сравним с r по модулю q, то подпись считается подлинной.Литература
1. Дж. Андерсон, Дискретная математика и комбинаторика, М.: Вильямс - 2003.
2. Н. Коблиц, Курс теории чисел и криптографии, М.: научное изд-во ТВП, 2001.
3. http://ru. wikipedia.org