АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Задание 2.2. Шифрование по алгоритму Шамира

Читайте также:
  1. А) Задание по вводу в действие производственных мощностей
  2. Аналитическое задание
  3. ДЗ Домашнее задание по теме «Алкалоиды»
  4. Домашнее задание
  5. Домашнее задание
  6. Домашнее задание к занятию № 1 по теме
  7. Домашнее задание к занятию № 2 по теме
  8. Домашнее задание №1
  9. Домашнее задание №2
  10. Домашнее задание №4
  11. Дополнительное задание
  12. Дополнительное задание.

 

Зашифровать сообщение по алгоритму Шамира для трех абонентов, взяв значение сообщения m и значение p из таблицы 2.3. По номеру i (предпоследняя цифра) студент выбирает сообщение для зашифровывания, по j – требуемые для реализации этого алгоритма число р. Выбор данных для других абонентов произвести циклически согласно процедуре (I + 1) и (G + 1). Например, последние цифры номера зачетной книжки – (26). Выбираем для трех абонентов (сообщение, p) - (16,49), (18,51), (20,53).

 

Таблица 2.3 – Исходные данные

I          
Сообщение          
G          
p          

 

I          
Сообщение          
G          
p          

Методические указания к заданию 2.2

 

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

Перейдем к описанию системы. Пусть есть два абонента А и В, соединенные линией связи. А хочет передать сообщение m абоненту B так, чтобы никто не узнал его содержание. А выбирает случай­ное большое простое число р и открыто передает его В. Затем А выбирает два числа сА и dA, такие, что

сАdA mod (р - 1) = 1. (2.1)

Эти числа А держит в секрете и передавать не будет. В тоже вы­бирает два секретных числа св и dв, такие, что

свdв mod (p - 1) = 1. (2.2)

После этого А передает свое сообщение m, используя трехсту­пенчатый протокол. Если m < р (m рассматривается как число), то сообщение т передается сразу, если же m р, то сообще­ние представляется в виде m1, m2,..., mt, где все mi < р, и затем передаются последовательно m1, m2,..., mt. При этом для кодиро­вания каждого mi лучше выбирать случайно новые пары (cA,dA) и (cB,dB) — в противном случае надежность системы понижается. В настоящее время такой шифр, как правило, используется для пере­дачи чисел, например, секретных ключей, значения которых меньше р. Таким образом, мы будем рассматривать только случай m < р.

Описание протокола.

Шаг 1. А вычисляет число

х1 =mСА modp, (2.3)

где m — исходное сообщение, и пересылает х1 к В.

Шаг 2. В, получив х1, вычисляет число

х2 = х1CB mod p. (2.4)

и передает х2 к А.

Шаг 3. А вычисляет число

х3 = х2dA mod p. (2.5)

и передает его В.

Шаг 4. В, получив х3, вычисляет число

Х4 = x3dB mod p. (2.6)

Схема обмена ключами по алгоритму Шамира представлена на рисунке 2.

Рисунок 2 - схема обмена ключами в системе Шамира

Утверждение (свойства протокола Шамира):

1) х4 = m, т.е. в результате реализации протокола от А к В действительно передается исходное сообщение;

2) злоумышленник не может узнать, какое сообщение было пе­редано.

Доказательство. Вначале заметим, что любое целое число е 0 может быть представлено в виде е = k(р — 1)+r, где r = е mod (p - 1). Поэтому на основании теоремы Ферма

 

. (2.7)

 

Справедливость первого пункта утверждения вытекает из следую­щей цепочки равенств:

(предпоследнее равенство следует из (2.7), а последнее выполняется в силу (2.1) и (2.2)).

 

Доказательство второго пункта утверждения основано на пред­положении, что для злоумышленника, пытающегося определить m, не существует стратегии более эффективной, чем следующая. Вначале он вычисляет CB из (2.4), затем находит dB и, наконец, вычисляет Х4 = m по (2.6). Но для осуществления этой стратегии злоумышленник должен решить задачу дискретного логарифмирования (2.4), что практически невозможно при больших р.

Опишем метод нахождения пар cA,dA и сB,dB, удовлетворяющих (2.1) и (2.2). Достаточно описать только действия для абонента А, так как действия для В совершенно аналогичны. Число сA выбираем случайно так, чтобы оно было взаимно простым с р-1 (по­иск целесообразно вести среди нечетных чисел, так как р - 1 четно), Затем вычисляем dA с помощью обобщенного алгоритма Евклида.

 

Пример.

Пусть А хочет передать В сообщение m = 10. А выбирает р = 23, сА = 7 (gcd(7,22) = 1) и вычисляет dA = 19. Аналогично, В выбирает параметры cB = 5 (взаимно простое с 22) и dB = 9.

Переходим к протоколу Шамира.

Шаг 1. x1 = 107 mod 23 = 14.

Шаг 2. х2 = 145 mod 23 = 15.

ШагЗ. x3= 1519 mod 23 = 19.

Шаг 4. х4 = 199 mod 23 = 10.

Таким образом, В получил передаваемое сообщение m = 10.

 

Контрольные вопросы

1. Дайте краткую характеристику системы шифрования по алгоритму Шамира.

2. Сколько пересылок между двумя абонентами необходимо совершить для передачи одного сообщения в данном алгоритме?

3. Какими преимуществами перед другими алгоритмами шифрования обладает система Шамира?

 


1 | 2 | 3 | 4 | 5 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.)