 |
Подтверждение подлинности отправителя
|
|
|
|
Факультет технической кибернетики
Кафедра информационных и управляющих систем
Реферат
«Цифровая подпись»
Студент Барташевич Е.Е.
Преподаватель Чистяков И.В.
Санкт-Петербург
2001
Содержание
1. Ассиметричные алгоритмы шифрования. 3
1.1. Стандарт ассимметричного шифрования RSA.. 4
1.1.1. Генерация ключей. 4
1.1.2. Шифрование/расшифрование. 5
1.2. Алгоритм ЭльГамаля. 6
1.2.1. Общие сведения. 6
1.2.2. Шифрование сообщений. 6
1.2.3. Подтверждение подлинности отправителя. 6
1.3. Алгоритм Шамира. 7
1.3.1. Общее описание. 7
1.3.2. Передача сообщений. 7
1.3.3. Пример использования. 8
1.4. Кpиптосистемы на основе эллиптических уpавнений. 8
2. Электронно-цифровая подпись. 9
2.1. Общие положения. 9
3. Алгоритм DSA.. 10
3.1. Генерация ЭЦП.. 11
3.2. Проверка ЭЦП.. 12
4. Стандарт на процедуры ЭЦП ГОСТ Р 34.10-94. 12
4.1. Генерация ЭЦП.. 13
4.2. Проверка ЭЦП.. 13
5. Цифровые подписи, основанные на симметричных криптосистемах. 13
6. Атаки на ЭЦП.. 22
7. Некоторые средства работы с ЭЦП.. 23
7.1. PGP. 23
7.2. GNU Privacy Guard (GnuPG) 24
7.3. Криптон. 24
7.4. ВербаО.. 24
8. Литература и ссылки. 26
Ассиметричные алгоритмы шифрования
Развитие основных типов криптографических протоколов (ключевой обмен, электронно-цифровая подпись (ЭЦП), аутентификация и др) было бы невозможно без создания открытых ключей и построенных на их основе ассиметричных протоколов шифрования.
Основная идея асимметричных криптоалгоритмов состоит в том, что для шифрования сообщения используется один ключ, а при дешифровании – другой. Кроме того, процедура шифрования выбрана так, что она необратима даже по известному ключу шифрования – это второе необходимое условие асимметричной криптографии. То есть, зная ключ шифрования и зашифрованный текст, невозможно восстановить исходное сообщение – прочесть его можно только с помощью второго ключа – ключа дешифрования. А раз так, то ключ шифрования для отправки писем какому-либо лицу можно вообще не скрывать – зная его все равно невозможно прочесть зашифрованное сообщение. Поэтому, ключ шифрования называют в асимметричных системах "открытым ключом", а вот ключ дешифрования получателю сообщений необходимо держать в секрете – он называется "закрытым ключом".
|
|
|
Таким образом, мы избавляемся от необходимости решать сложную задачу обмена секретными ключами.
Напрашивается вопрос: "Почему, зная открытый ключ, нельзя вычислить закрытый ключ?" – это третье необходимое условие асимметричной криптографии – алгоритмы шифрования и дешифрования создаются так, чтобы зная открытый ключ, невозможно вычислить закрытый ключ.
В целом система переписки при использовании асимметричного шифрования выглядит следующим образом. Для каждого из N абонентов, ведущих переписку, выбрана своя пара ключей: "открытый" Ej и "закрытый" Dj, где j – номер абонента. Все открытые ключи известны всем пользователям сети, каждый закрытый ключ, наоборот, хранится только у того абонента, которому он принадлежит. Если абонент, скажем под номером 7, собирается передать информацию абоненту под номером 9, он шифрует данные ключом шифрования E9 и отправляет ее абоненту 9. Несмотря на то, что все пользователи сети знают ключ E9 и, возможно, имеют доступ к каналу, по которому идет зашифрованное послание, они не могут прочесть исходный текст, так как процедура шифрования необратима по открытому ключу. И только абонент №9, получив послание, производит над ним преобразование с помощью известного только ему ключа D9 и восстанавливает текст послания. Заметьте, что если сообщение нужно отправить в противоположном направлении (от абонента 9 к абоненту 7), то нужно будет использовать уже другую пару ключей (для шифрования ключ E7, а для дешифрования – ключ D7).
|
|
|
Как мы видим, во-первых, в асимметричных системах количество существующих ключей связано с количеством абонентов линейно (в системе из N пользователей используются 2*N ключей), а не квадратично, как в симметричных системах. Во-вторых, при нарушении конфиденциальности k-ой рабочей станции злоумышленник узнает только ключ Dk: это позволяет ему читать все сообщения, приходящие абоненту k, но не позволяет вывадавать себя за него при отправке писем.
Стандарт ассимметричного шифрования RSA
Самым распространенным алгоритмом ассиметричного шифрования является алгоритм RSA. Он был предложен тремя исседователями-математиками Рональдом Ривестом (R.Rivest), Ади Шамиром (A.Shamir) и Леонардом Адльманом (L.Adleman) в 1977-78 годах. Разработчикам данного алгоритма удалось эффективно воплотить идею односторонних функций с секретом. Стойкость RSA базируется на сложности факторизации больших целых чисел. В 1993 году метод RSA был обнародован и принят в качестве стандарта (PKCS #1: RSA Encryption standart). RSA можно применять как для шифрования/расшифрования, так и для генерации/проверки электронно-цифровой подписи.
Генерация ключей
Первым этапом любого асимметричного алгоритма является создание пары ключей: открытого и закрытого и распространение открытого ключа "по всему миру". Для алгоритма RSA этап создания ключей состоит из следующих операций:
Выбираются два простых (!) числа p и q
Вычисляется их произведение n(=p*q)
Выбирается произвольное число e (e<n), такое, что НОД(e,(p-1)(q-1))=1, то есть e должно быть взаимно простым с числом (p-1)(q-1).
Методом Евклида решается в целых числах (!) уравнение e*d+(p-1)(q-1)*y=1. Здесь неизвестными являются переменные d и y – метод Евклида как раз и находит множество пар (d,y), каждая из которых является решением уравнения в целых числах.
Два числа (e,n) – публикуются как открытый ключ.
Число d хранится в строжайшем секрете – это и есть закрытый ключ, который позволит читать все послания, зашифрованные с помощью пары чисел (e,n).
|
|
|
Шифрование/расшифрование
Как же производится собственно шифрование с помощью этих чисел:
Отправитель разбивает свое сообщение на блоки, равные k=[log2(n)] бит, где квадратные скобки обозначают взятие целой части от дробного числа.
Подобный блок, как Вы знаете, может быть интерпретирован как число из диапазона (0;2k-1). Для каждого такого числа (назовем его mi) вычисляется выражение ci=((mi)e)mod n. Блоки ci и есть зашифрованное сообщение, и
их можно спокойно передавать по открытому каналу, поскольку операция возведения в степень по модулю простого числа, является необратимой математической задачей. Обратная ей задача носит название "логарифмирование в конечном поле" и является на несколько порядков более сложной задачей. То есть даже если злоумышленник знает числа e и n, то по ci прочесть исходные сообщения mi он не может никак, кроме как полным перебором mi.
А вот на приемной стороне процесс дешифрования все же возможен, и поможет нам в этом хранимое в секрете число d. Достаточно давно была доказана теорема Эйлера, частный случай которой утвержает, что если число n представимо в виде двух простых чисел p и q, то для любого x имеет место равенство (x(p-1)(q-1))mod n = 1. Для дешифрования RSA-сообщений воспользуемся этой формулой.
Возведем обе ее части в степень (-y): (x(-y)(p-1)(q-1))mod n = 1(-y) = 1.
Теперь умножим обе ее части на x: (x(-y)(p-1)(q-1)+1)mod n = 1*x = x.
А теперь вспомним как мы создавали открытый и закрытый ключи. Мы подбирали с помощью алгоритма Евклида d такое, что e*d+(p-1)(q-1)*y=1, то есть e*d=(-y)(p-1)(q-1)+1. А следовательно в последнем выражении предыдущего абзаца мы можем заменить показатель степени на число (e*d). Получаем (xe*d)mod n = x. То есть для того чтобы прочесть сообщение ci=((mi)e)mod n достаточно возвести его в степень d по модулю m:
((ci)d)mod n = ((mi)e*d)mod n = mi.
На самом деле операции возведения в степень больших чисел достаточно трудоемки для современных процессоров, даже если они производятся по оптимизированным по времени алгоритмам. Поэтому обычно весь текст сообщения кодируется обычным блочным шифром (намного более быстрым), но с использованием ключа сеанса, а вот сам ключ сеанса шифруется как раз асимметричным алгоритмом с помощью открытого ключа получателя и помещается в начало файла.
|
|
|
Алгоритм ЭльГамаля
Общие сведения
Криптографы со своей стороны вели поиски более эффективных систем открытого шифрования и в 1985 году Т.Эль-Гамаль (США) предложил следующую схему на основе возведения в степень по модулю большого простого числа P.
Задается большое простое число P и целое число A, 1 < A < P. Сообщения представляются целыми числами M из интервала 1 < M < P.
Шифрование сообщений
Протокол передачи сообщения M выглядит следующим образом.
абоненты знают числа A и P;
абоненты генерируют независимо друг от друга случайные числа:
Ka, Kb
удовлетворяющих условию:
1 < K < P
получатель вычисляет и передаёт отправителю число B, определяемое последовательностью:
В = A Kb mоd(P)
отправитель шифрует сообщение M и отправляет полученную последовательность получателю
C = M * B Ka mоd(P)
получатель расшифровывает полученное сообщение
D = (A Ka ) -Kb mоd(P)
M = C * D mоd(P)
В этой системе открытого шифрования та же степень защиты, что для алгоритма RSA с модулем N из 200 знаков, достигается уже при модуле P из 150 знаков. Это позволяет в 5-7 раз увеличить скорость обработки информации. Однако, в таком варианте открытого шифрования нет подтверждения подлинности сообщений.
Подтверждение подлинности отправителя
Для того, чтобы обеспечить при открытом шифровании по модулю простого числа P также и процедуру подтверждения подлинности отправителя Т.ЭльГамаль предложил следующий протокол передачи подписанного сообщения M:
абоненты знают числа A и P;
отправитель генерирует случайное число и хранит его в секрете:
Ka
удовлетворяющее условию:
1 < Ka < P
вычисляет и передаёт получателю число B, определяемое последователньостью:
В = A Ka mоd(P)
Для сообщения M (1 < M < P):
выбирает случайное число L (1 < L < P), удовлетворяющее условию
(L, P - 1) = 1
вычисляет число
R = A L mоd(P)
решает относительно S
M = Ka * R + L * S m о d (P)
передаёт подписанное сообщение
[ M, R, S ]
получатель проверяет правильность подписи
A M = (B R) * (R S) mоd(P)
В этой системе секретным ключом для подписывания сообщений является число X, а открытым ключом для проверки достоверности подписи число B. Процедура проверки подписи служит также и для проверки правильности расшифрования, если сообщения шифруются.
Алгоритм Шамира
Общее описание
Еще один интересный пример использования возведения в степень по модулю большого простого числа P для открытого шифрования предложил А.Shamir (один из авторов RSA). Как и в системе ЭльГамаля сообщения M представляются целыми числами из интервала 1 < M < P.
|
|
|
Передача сообщений
Передача сообщения происходит следующим образом:
абоненты знают числа P;
абоненты генерируют независимо друг от друга случайные числа:
Ka, Kb
удовлетворяющих условию:
1 < K < P
отправитель вычисляет значение и передаёт получателю:
C = M Ka mоd(P)
получатель вычисляет и передаёт отправителю число B, определяемое последовательностью:
D = C Kb mоd(P)
отправитель аннулирует свой шифр и отправляет полученную последовательность получателю
E=D(X-1) mоd(P) E = D Fa mоd(P)
где:
Fa = Ka -1
получатель расшифровывает полученное сообщение
M = E Fb mоd(P)
где:
Fb = Kb –1
Пример использования
Эта процедура ОШ может быть использована, например, для таких "экзотических" целей как игра в карты по телефону.
Действительно, если игрок A желает "сдать" игроку B, скажем, 5 карт из 52 как при игре в покер, он зашифровывает обозначения всех карт и передает их игроку B:
Ca = Ma Ka mоd(P)
где
I =1,2,..,52
Игрок B выбирает из них 5, зашифровывает своим ключом 22 и возвращает игроку А:
Da = Ca Kb mоd(P)
где
I =1,2...,5
Игрок A снимает с этих 5 карт свой шифр и выдает их игроку B.
Игрок B расшифровывает полученные карты:
Ma = Ea Fb mоd (P)
При этом оставшаяся часть колоды C(6)...C(52) теперь находится у игрока B, но он не может раскрыть эти карты, т.к. они зашифрованы на ключе его партнера A. Остальные процедуры игры проделываются аналогично.
|
|
|
