Global Informatics

- Информатика и вычислительная техника

Шифрование по алгоритму Шамира

Зашифровать сообщение по алгоритму Шамира для трех абонентов, взяв значение сообщения m и значение p из таблицы 2. По номеру i (предпоследняя цифра) студент выбирает сообщение для зашифровывания, по j - требуемые для реализации этого алгоритма число р. Выбор данных для других абонентов произвести циклически согласно процедуре (i + 1) и (g + 1).

Последние цифры номера зачетной книжки - (00). Выбираем для трех абонентов (сообщение, p) - (12,29), (14,31), (16,37).

Таблица 2. Исходные данные для выбора сообщений (m)

I

0

1

2

Сообщение

14

16

18

J

0

1

2

p

31

37

41

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

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

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

св<dв mod (p - 1) = 1, (2.2)

и держит их в секрете.

После этого А передает свое сообщение 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, вычисляет число:

X2 = х1CB mod p (2.4),

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

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

X3 = х2dA mod p (2.5),

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

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

X4 = x3dB mod p (2.6).

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

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

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

Доказательство. Вначале заметим, что любое целое число е 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 с помощью обобщенного алгоритма Евклида.

Теорема Пусть a и b - два целых положительных числа. Тогда существуют целые (не обязательно положительные) числа x и y, такие, что

Перейти на страницу: 1 2

Статья в тему

Реконструкция внутризоновой сети на базе радиорелейной связи
Радиорелейная связь первоначально применялась для организации многоканальных линий телефонной связи, линий, в которых сообщения передавались с помощью аналогово-электрического сигнала. Первая такая линия с 5 телефонными каналами появилась в США в 1935 году. Она соединяла города Нью-Йорк и Филадельфи ...

Главные разделы


www.globalinformatics.ru © 2020 - Все права защищены!