Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

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




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

Определение (функция Эйлера). Пусть дано целое число 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 выбирает два числа cA и dA, такие что

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

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

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

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

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

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

и передает x2 к A.

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

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

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

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

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

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

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

.

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

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

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

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

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

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

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

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

В результате получаем таблицу

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...