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
)