|
|
где e и m являются открытыми числами (известны всем абонентам сети).
Требуем, чтобы e и m были взаимно простыми числами (т.е. не числами общих делителей, кроме 1, причем ).
Оказывается, что зная y, e и m, найти x – сложнейшая математическая задача. Пока же продемонстрируем, как найти y по x, e, m.
Операция
(1.2)
находит целочисленный остаток a от деления b на m. Например,
2 = 17 mod 5
или
1 = 41 mod 8.
Но пусть требуется найти
630 mod 18 = ?
Это сделать посложнее. Мно записать
630 = 2*315 = 2*5*63 = 2*5*7*9 = 63*10.
Теперь можно использовать правило разложения на множители
.
В самом деле, пусть
,
,
.
Тогда
.
Последняя сумма дает остаток от деления на m, равный . Но , . Поэтому . Теперь нетрудно это правило применить, скажем, к
713 mod 8 = ?
Запишем . Имеем . Поэтому .
Обратимся теперь к формуле (6.16).
Пусть , , .
Найдем
.
Итак, . Это значение и будет передано по сети вместо x.
Теперь рассмотрим, как восстановить x по y, m, e. Для этой цели нужно найти число d, удовлетворяющее условию
,
(1.3)
где – значение функции Эйлера от числа m. Функция Эйлера вычисляется сравнительно просто. Так,
.
(1.4)
Если p простое число и r – целое, то
.
(1.5)
Формул (1.4) и (1.5) достаточно для того, чтобы найти функцию Эйлера для любого целого положительного числа. В нашем случае получаем:
.
Для любознательных читателей отметим, что значение равно числу целых чисел на отрезке 1..m, взаимно простых с m. Отыскание значения функции Эйлера для больших целых чисел является вычислительной задачей очень большой сложности.
Пример. . Все четыре числа: 1, 2, 3, 4 взаимно просты с m.
Теперь обратимся к уравнению (3.3). В этом уравнении d играет роль секретного ключа. Решить уравнение (3.3) путем перебора значений d можно, но если в числе m, например, 100 цифр, то на вычисление d уйдет достаточно много времени. Для небольших значений, таких как в нашем примере, можно воспользоваться алгоритмом решения уравнений в целых числах, который мы и приведем.
Итак, в нашем примере уравнение такое:
.
(1.6)
Уравнение (1.6) можно переписать следующим известным образом:
.
(1.7)
В (1.7) r и d неизвестные целые числа. Представим (1.7) в виде системы двух линейных неравенств.
,
,
или, что эквивалентно:
,
.
(1.8)
В неравенстве с положительной правой частью выделим член с минимальным по модулю коэффициентом и разрешим неравенство относительно этого члена:
,
.
Отсюда легко получить отсекающее неравенство:
(a) ,
(b) ,
(c) .
(1.9)
Здесь z – новая целочисленная переменная. Заметим, что переход от (a) к (b) в (1.9) правомерен, так как r , d, z – целочисленны.
Выполним подстановку (3.9) в систему (1.8). Получим новую систему:
,
.
(1.10)
Обратим внимание на следующее принципиальное обстоятельство. В сравнении с (1.8) значение минимального коэффициента понизилось. Этот факт можно строго обосновать. Следовательно, весь процесс должен закончиться рано или поздно одним из двух результатов:
1) минимальный коэффициент по модулю станет равным 1 (как в (1.10));
2) будет получена система вида
,
,
где a и b – взаимно просты (в этом случае нет решения в целых числах).
В первом случае процесс решения завершен. Получаем из (1.10) подстановку для d:
.
(1.11)
Тогда из (1.9) найдем:
.
(1.12)
Итак, формулы (1.11) и (1.12) и дают нам итоговые подстановки для d и r из (1.7). Например, пусть . Тогда , . Возьмем именно это значение для минимального d.
Итак, мы подошли к решающему моменту: наш секретный ключ . Получили число , , .Восстанавливаем x по формуле:
.
(1.13)
Итак, .
Все сошлось. Возьмем, например, . Тогда , :
(ответ тот же).
Таким образом, не имеет значения, какое z брать для получения d.
Метод RSA мы завершим следующим замечанием.
Метод RSA вообще говоря требует, чтобы m было большим простым числом. Для установления факта, что m – простое, можно использовать малую теорему Ферма:
.
(1.14)
В (1.14) a и p должны быть взаимно просты, а p – простое число.
Пример. , : .
, :
.
К сожалению, формула (1.14) справедлива также для некоторых составных чисел. Поэтому чтобы применить ее на практике, нудно выполнить проверку для некоторых различных a (идея алгоритма Рабина).
Принцип электронной подписи легко выводится из алгоритма RSA. Пусть нужно подписать текст T. Этот текст нудно «свернуть» в некое число y. Для свертки используют алгоритм хэширования. Теперь из уравнения (1.13) на основании секретного ключа получают подпись X. Число X и возвращается вместе с T и y в качестве подписи в документу Т. Не зная секретного ключа d (заменяющего фамилию), нельзя найти X. Проверяющий легко проверит (1.1), чтобы удостовериться, что X и y соответствуют друг другу. Заметим, что кто-либо может перехватить документ и подписать его своей подписью, если ему известно преобразование (1.13). Поэтому принятый «подделанный» документ должен быть «застрахован».
Для этого используется число e – открытый ключ подписавшего документ. Теперь очень легко проверить соотношение:
.
Подобрать секретный ключ d к открытому ключу e практически невозможно.
Метод Диффи и Хеллмана является двухключевым. Каждый абонент в сети имеет два ключа: один секретный – , второй открытый, вычисляемый по формуле
,
где p – большое простое число (взаимно простое с ); .
Число выбирается так, чтобы числа , , …, по модулю p давали некоторую перестановку чисел {1, 2, …, p-1}. Число называется первообразным корнем p. Все абоненты публикуют свои открытые ключи . Допустим, абоненты A и B хотят передать друг другу информацию. Тогда первый из них, например A, берет открытый ключ абонента B и вычисляет
.
Таким образом, оба абонента находят одно и то же число, которое они и используют в качестве ключа для обмена сообщениями. При этом секретные ключи абонентов остаются известными только им одним.
Алгоритм DES
Алгоритм DES (description encryption system) состоит в последовательности чередующихся операций подстановки и перемешивания. Алгоритм DES использует секретный ключ K. Пусть, например, блок данных есть , а ключ .
Подстановка есть сложение по модулю 2:
10010011
11001011
При использовании материалов активная ссылка на источник обязательна.