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

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

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

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

Перейдем к описанию системы. Пусть есть два абонента А и В, соединенные линией связи. А хочет передать сообщение 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, такие, что

Статья в тему

Исследование преимуществ совмещенных систем позиционирования GPS и ГЛОНАСС
Совмещенные приемники спутниковых радионавигационных систем (СРНС) GPS/ГЛОНАСС давно и успешно реализуются на рынке профессиональной аппаратуры для высокоточных применений. Прежде всего это геодезическая аппаратура, в которой использование двух СРНС позволяет сократить время разрешения неоднозначнос ...