Шифр Шамира

Шифр Шамира (Adi Shamir) был первым, позволяющим организовать обмен секретными сообщениями по незащищенной линии связи без обмена секретными ключами. Рассмотренная ранее система Диффи — Хеллма- на позволяет сформировать только секретный ключ, а передача сообщения потребует использования некоторого шифра.

Шифр Шамира заключается в следующем. Пусть имеются два абонента А и В, соединенные линией связи, и А хочет передать секретное сообщение В. А выбирает большое простое число р и открыто передает его абоненту В. Затем А случайно выбирает два числа х{ и х2, такие, что они являются обратными друг другу по модулю р - 1:

Числа хх и х2 являются личным ключом абонента А он держит их в секрете и передавать не будет.

Абонент В также случайно выбирает два числа г/, и у2, такие, что:

Числа у{ и у2 являются личным ключом абонента В и держатся в секрете.

Числам и у{ выбираются абонентами случайно так, чтобы они были взаимно простыми с р - 1. Причем *, и г/, следует искать только среди нечетных чисел, так как р - 1 — четно. Числа х2 и у2 вычисляются с помощью расширенного алгоритма Евклида.

Теперь абонент А может передать свое сообщение М, используя трехступенчатый протокол. Сообщение М рассматривается как число. Если М < р, то М передается сразу; если же М > р, то перед отправкой сообщение представляется в виде последовательности mv mv ..., т(, где все т. < р. Сообщения mjf i = 1, t передаются последовательно, при этом для шифрования каждого mi рекомендуется случайно выбирать новые пары ключей хх и х2, г/, и у2; в противном случае надежность криптосистемы снижается. Таким образом, не умаляя общности, можно рассмотреть только случай М < р:

  • 1) А вычисляет число X, = Mv> mod р, где М — исходное сообщение, и пересылает X, абоненту В;
  • 2) В, получив X,, вычисляет число У, = Xf1 mod р и передает У, абоненту А,
  • 3) А вычисляет число Х2 = У*2 mod р и передает его В;
  • 4) В, получив Х2, вычисляет число У2 = Х22 mod р, У2 и есть исходное сообщение М.

Покажем, что У2 = М. Заметим, что на основании теоремы Ферма для любого целого е > 0 выполняется: x^modp = xk(j)~i)+r modp = (l***)modp = = x^.nod(^-i)mocj p? где r = emod(p - 1). Тогда

Значения XvX2n У, могут передаваться по открытому каналу, поскольку получение на их основе значений секретных ключей xv х2 и г/, практически невозможно (утверждение базируется на вычислительной сложности задачи дискретного логарифмирования при больших значениях р).

Никто другой, кроме абонента В, не сможет вычислить значения М, так как в вычислениях используются секретные ключи абонента В.

Пример 3.21

Пусть Л хочет передать В сообщение М = 10. Л выбирает простое р = 23, хх = 7 — взаимно простое с р - 1 = 22 (НОД(7, 22) = 1) и с помощью расширенного алгоритма Евклида вычисляет^ = хх 1 mod - 1) = 7 1 mod 22 = 19. Аналогично В выбирает параметры гу, = 5 — взаимно простое с 22 (НОД(5, 22) = 1) и вычисляет у2 = г/,-1 mod - 1) = 9. Протокол Шамира:

  • 1) А —? В: X, = МхЛ mod р = 107 mod 23 = 14;
  • 2) В — А: У, = ХуХ mod р = 145 mod 23 = 154;
  • 3) А — В: Х2 = Y* mod р = 1519 mod 23 = 19;
  • 4) В проводит расшифрование: У2 = Xyl mod р = 199 mod 23 = 10 = М.

Шифр Шамира может быть легко обобщен на произвольное число абонентов.

Основным недостатком шифра является необходимость многоступенчатого обмена данными между абонентами, что в ряде случаев может оказаться весьма неудобным.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >