предполагается, что она должна быть легко проверяемой и каждый должен иметь возможность осуществить проверку подписи без получения доступа к секретному ключу. При возникновении спорной ситуации, связанной с отказом подписывающего от факта подписи им некоторого сообщения либо с попыткой подделки подписи, третья сторона должна иметь возможность разрешить спор.
Цифровая подпись позволяет решить следующие три за-
дачи:
-осуществить аутентификацию источника сообщения;
-установить целостность сообщения;
-обеспечить невозможность отказа от факта подписи конкретного сообщения.
Цифровая подпись обладает следующими свойствами:
-зависит от подписываемого текста, практически всегда разная;
-определяется секретным ключом, принадлежащим подписывающему лицу, может быть утеряна владельцем;
-легко отделима от документа, поэтому верна для всех его копий;
-требует дополнительных механизмов, реализующих
алгоритмы еѐ вычисления и проверки.
Для реализации схемы цифровой подписи необходимы два алгоритма:
-алгоритм вычисления цифровой подписи;
-алгоритм еѐ проверки.
Главные требования к этим алгоритмам заключаются в исключении возможности получения подписи без использования секретного ключа и гарантирования возможности проверки подписи без знания какой-либо секретной информации.
Надѐжность схемы цифровой подписи определяется сложностью следующих трѐх задач:
1)подделки подписи, то есть нахождения значения подписи под заданным документом лицом, не являющимся владельцем секретного ключа;
45
2)создания подписанного сообщения, то есть нахожде-
ния хотя бы одного сообщения с правильным значением подписи;
3)подмены сообщения, то есть подбора двух различных сообщений с одинаковыми значениями подписи.
Принципиальной сложностью, возникающей при использовании цифровой подписи на практике, является проблема создания инфраструктуры открытых ключей. Суть еѐ со-
стоит в том, что для алгоритма проверки подписи необходима дополнительная открытая информация, связанная с обеспечением возможности открытой проверки подписи и зависящая от секретного ключа автора подписи. Эту информацию можно назвать открытым ключом цифровой подписи. Для исключения возможности подделки этой информации (открытого ключа) лицами, которые хотят выступить от лица законного владельца подписи (секретного ключа), создаѐтся инфраструктура, состоящая из центров сертификации открытых ключей и обеспечивающая возможность своевременного подтверждения достоверности принадлежности данной открытой информации заявленному владельцу и обнаружения подлога.
При создании сертификационных центров имеются проблемы не с технической, а с юридической точки зрения. Суть состоит в том, что в случае возникновения споров, связанных с отказом от авторства или подделки подписи, такие центры должны нести юридическую ответственность за достоверность выдаваемых сертификатов. В частности, они должны возмещать понесѐнные убытки в случае конфликтных ситуаций, когда алгоритм проверки подписи подтверждает еѐ правильность. В связи с этим сложилась практика заключения договоров между участниками информационного взаимодействия с применением цифровых подписей. В таком договоре должно быть указано:
1)кто должен нести ответственность в случае, если подписанные сделки не состоятся;
46
2)кто должен нести ответственность в случае, если система окажется ненадѐжной и будет взломана, то есть будет выявлен факт подделки секретного ключа;
3)какова ответственность уполномоченного по сертификатам в случае, если открытый ключ будет сфальсифицирован;
4)кто несѐт ответственность за плохую реализацию системы в случае повреждения или разглашения секретного ключа;
5)каков порядок разрешения споров.
6.КРИПТОСИСТЕМА RSA
6.1.Основные положения
Вотличие от симметричного кодирования, при котором процедура расшифровки легко восстанавливается по процедуре шифрования и обратно, в схеме кодирования с открытым ключом невозможно вычислить процедуру расшифровки, зная процедуру шифрования. Более точно, время работы алгоритма, вычисляющего процедуру расшифровки, настолько велико, что его нельзя выполнить на любых современных компьютерах, равно как и на любых компьютерах будущего. Такие схемы кодирования называют асимметричными.
Итак, имеем два отображения:
E:S --> T
D: T --> S
где S -- множество всевозможных незашифрованных сообщений, T -- множество зашифрованных сообщений. Буква "E" -- первая буква слова "Encoding", буква "D" -- первая буква слова
"Decoding". Отображение
E: s |--> t
переводит исходное сообщение s в зашифрованное сообщение t, отображение
D: t |--> s
47
переводит зашифрованное сообщение t обратно в s. Тот факт, что D является декодирующей процедурой, на математическом языке означает, что композиция отображений DE является тождественным отображением: для всякого s справедливо
D(E(s)) = s.
или
DE = 1 (тождественное отображение в S).
Все это справедливо для любой схемы асимметричного кодирования. Перейдем непосредственно к схеме RSA, названной так по первым буквам фамилий ее авторов -- Rumley, Shamir, Adleman. Отметим сразу, что схема RSA обладает двумя дополнительными очень полезными свойствами.
1.Множество исходных сообщений S совпадает с множеством закодированных сообщений T; в качестве этого множества используется кольцо вычетов по модулю m, где m -- произведение двух больших простых чисел (десятичная запись m имеет длину не меньше 200).
2.Не только DE = 1, но и ED = 1! Таким образом, D и E -- два взаимно обратных отображения. Это позволяет владельцу секретной процедуры декодирования D применять ее для кодирования. При этом все могут раскодировать это сообщение, используя открытую процедуру E, но только владелец секретной процедуры D может послать его. Такая "обратная" схема применения открытого ключа позволяет удостоверить отправителя сообщения. В практических применениях (для аутентификации отправителя) обратная схема даже более важна, чем прямая.
Итак, в схеме RSA в качестве множества исходных и зашифрованных сообщений используется кольцо вычетов Zm, где
m = p * q --
произведение двух больших простых чисел (длина десятичной записи каждого из чисел p и q не меньше 100). Всякое сообщение представляется в виде элемента Zm. (Любое собщение -- это последовательность битов, которую можно рассмотреть как большое целое число. Если длина сообщения больше, чем
48
длина двоичной записи m, то она разбивается на блоки, и каждый блок шифруется отдельно.)
Число m открытое, однако разложение m на множители -- секретное. Разложение позволяет вычислить функцию Эйлера (следствие 3):
phi(m) = (p - 1) * (q - 1)
Нетрудно показать, что знание функции Эйлера дает возможность разложить число на множители, так что сложность задачи взламывания открытого ключа равна сложности задачи разложения на множители. Математики верят, что это действительно сложная задача, хотя никаких удовлетворительных оценок снизу в настоящее время не получено. (И вряд ли это NP-полная задача.)
6.2. Построение кодирующей процедуры E
Сгенерируем случайный элемент e в кольце вычетов по модулю phi(m), такой, что он обратим в этом кольце (т.е. взаимно прост с phi(m)). Пара (m, e) является открытым ключом. Отображение E состоит в возведении в степень e в кольце вычетов по модулю m.
E: s |--> s^e (mod m)
Для практического вычисления применяется алгоритм быстрого возведения в степень.
6.3. Построение декодирующей процедуры D
Для элемента e вычисляется обратный элемент d в кольце вычетов по модулю phi(m).
e * d == 1 (mod phi(m))
Это легко делается с помощью расширенного алгоритма Евклида. Пара (m, d) является секретным ключом. Отображение D состоит в возведении в степень d в кольце вычетов по модулю m.
D: t |--> t^d (mod m)
49