Математические основы криптографии

Определение (функция Эйлера). Пусть дано целое число N > 1. Значение функции Эйлера равно количеству чисел в ряду 1, 2, 3, …, N-1, взаимно простых с N.

Пример

Утверждение Если p - простое число, то

Доказательство. В ряду все числа взаимно просты с р. так как р - простое число и по определению не делится ни на какое другое число.

Утверждение Пусть p и q – два различных простых числа . Тогда .

Доказательство. В ряду 1, 2, …, pq-1 не взаимнопростыми с pq будут числа

Всего таких чисел будет (q-1)+(p-1). Следовательно, количество чисел, взаимнопростых с pq, будет

Теорема (Эйлер). Пусть a и b – взаимно простые числа. Тогда

Теорема Если p и q – простые числа, и k – произвольное целое число, то

Теорема (Ферма). Пусть p – простое число и 0 < a < p. Тогда

Шифр Шамира

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

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

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

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

В настоящее время такой шифр, как правило, используется для передачи чисел, например, секретных ключей, значения которых меньше p. Таким образом, мы будем рассматривать только случай m < p. Дадим описание протокола.

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

где m – исходное сообщение, и пересылает x₁к B.

Шаг 2. B, получив x₁, вычисляет число

и передает x₂ к A.

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

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

Шаг 4. B, получив x₃, вычисляет число

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

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

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

Доказательство. Вначале заметим, что любое целое число может быть представлено в виде , где . Поэтому на основании теоремы Ферма

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

Доказательство второго пункта утверждения основано на предположении, что для злоумышленника, пытающегося определить m, не существует стратегии более эффективной, чем следующая. Вначале он вычисляет , затем находит и, наконец, вычисляет

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

нента A. так как действия для B совершенно аналогичны. Число выбираем случайно так. чтобы оно было взаимно простым с р - 1 (поиск целесообразно вести среди нечетных чисел, так как р - 1 четно). Затем вычисляем с помощью обобщенного алгоритма Евклида.

Шифр эль-гамаля

Пусть имеются абоненты А, В, С,..., которые хотят передавать друг другу зашифрованные сообщения, не имея никаких защищенных каналов связи. В этом разделе мы рассмотрим шифр, предложенный Эль-Гамалем (Taher ElGamal), который решает эту задачу, используя, в отличие от шифра Шамира, только одну пересылку сообщения. Фактически здесь используется схема Диффи-Хеллмана, чтобы сформировать общий секретный ключ для двух абонентов, передающих друг другу сообщение, и затем сообщение шифруется путем умножения его на этот ключ. Для каждого следующего сообщения секретный ключ вычисляется заново. Перейдем к точному описанию метода.

Для всей группы абонентов выбираются некоторое большое простое число р и число д, такие что различные степени д суть различные числа по модулю р Числа р и д передаются абонентам в открытом виде (они могут использоваться всеми абонентами сети).

Затем каждый абонент группы выбирает свое секретное число c_i, 1 < c_i < р - 1, и вычисляет соответствующее ему открытое число d_i,