Защита информации: Цифровая подпись
Страница 2
1.2. Алгоритм ЭльГамаля
1.2.1. Общие сведения
Криптографы со своей стороны вели поиски более эффективных систем открытого шифрования и в 1985 году Т.Эль-Гамаль (США) предложил следующую схему на основе возведения в степень по модулю большого простого числа P. Задается большое простое число P и целое число A, 1 < A < P. Сообщения представляются целыми числами M из интервала 1 < M < P.
1.2.2. Шифрование сообщений
Протокол передачи сообщения 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 раз увеличить скорость обработки информации. Однако, в таком варианте открытого шифрования нет подтверждения подлинности сообщений.
1.2.3. Подтверждение подлинности отправителя
Для того, чтобы обеспечить при открытом шифровании по модулю простого числа 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. Процедура проверки подписи служит также и для проверки правильности расшифрования, если сообщения шифруются.
1.3. Алгоритм Шамира
1.3.1. Общее описание
Еще один интересный пример использования возведения в степень по модулю большого простого числа P для открытого шифрования предложил А.Shamir (один из авторов RSA). Как и в системе ЭльГамаля сообщения M представляются целыми числами из интервала 1 < M < P.
1.3.2. Передача сообщений
Передача сообщения происходит следующим образом:
абоненты знают числа 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
1.3.3. Пример использования
Эта процедура ОШ может быть использована, например, для таких "экзотических" целей как игра в карты по телефону. Действительно, если игрок 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. Остальные процедуры игры проделываются аналогично.
1.4. Кpиптосистемы на основе эллиптических уpавнений
Эллиптические кpивые - математический объект, котоpый может опpеделен над любым полем (конечным, действительным, pациональным или комплексным). В кpиптогpафии обычно используются конечные поля. Эллиптическая кpивая есть множество точек (x,y), удовлетвоpяющее следующему уpавнению:
y2 = x3 + ax + b,
а также бесконечно удаленная точка. Для точек на кpивой довольно легко вводится опеpация сложения, котоpая игpает ту же pоль, что и опеpация умножения в кpиптосистемах RSA и Эль-Гамаля.
В pеальных кpиптосистемах на базе эллиптических уpавнений используется уpавнение
y2 = x3 + ax + b mod p,
где p - пpостое.
Пpоблема дискpетного логаpифма на эллиптической кpивой состоит в следующем: дана точка G на эллиптической кpивой поpядка r (количество точек на кpивой) и дpугая точка Y на этой же кpивой. Нужно найти единственную точку x такую, что Y = xG, то есть Y есть х-я степень G.
2. Электронно-цифровая подпись
2.1. Общие положения
При ведении деловой переписки, при заключении контрактов подпись ответственного лица является непременным аттрибутом документа, преследующим несколько целей:
- Гарантирование истинности письма путем сличения подписи с имеющимся образцом;
- Гарантирование авторства документа ( с юридической точки зрения)
Выполнение данных требовани основывается на следующих свойствах подписи:
- подпись аутентична, то есть с ее помощью получателю документа можно доказать, что она принадлежит подписывающему;
- подпись неподделываема; то есть служит доказательством, что только тот человек, чей автограф стоит на документе, мог подписать данный документ, и никто иной.
- Подпись непереносима, то есть является частью документа и поэтому перенести ее на другой документ невозможно.
- Документ с подписью является неизменяемым.
- Подпись неоспорима.
- Любое лицо, владеющее образцом подписи может удостоверится, что документ подписан вледельцем подписи.
Развитие современных средств безбумажного документооборота, средств электронных платежей немыслимо без развития средств доказательства подлинности и целостности документа. Таким средством является электронно-цифровая подпись (ЭЦП), которая сохранила основные свойства обычной подписи.
Существует несколько методов посторения ЭЦП, а именно:
- шифрование электронного документа (ЭД) на основе симметричных алгоритмов. Данная схема предусматривает наличие в системе третьего лица – арбитра, пользующегося доверием обеих сторон. Авторизацией документа в даной схеме является сам факт зашифрования ЭД секретным ключем и передача его арбитру.
- Использование ассиметричных алгоритмов шифрования. Фактом подписания документа является зашифрование его на секретном ключе отправителя.
- Развитием предыдущей идеи стала наиболее распространенныя схема ЭЦП – зашифрование окончательного результата обработки ЭД хеш-функцией при помощи ассиметричного алгоритма.
Кроме перечисленных, существуют и другие методы построения схем ЭЦП
- групповая подпись, неоспариваемая подпись, доверенная подпись и др. Появление этих разновидностей обусловлено разнообразием задач, решаемых с помощью электронных технологий передачи и обработки электронных документов.
3. Алгоритм DSA