Третий этап развития криптографии

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

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

Шифр Ривеста – Шамира – Алдемана

Первой и наиболее известной криптографической системой с открытым ключом была предложенная в 1978 году система RSA (Массачусетский технологический институт). Она основана на трудности разложения больших целых чисел на простые сомножители.

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

Пользователь , отправляющий сообщение , шифрует его следующим образом: . Этот текст получает только пользователь .

Чтобы восстановить исходный текст,  поступает следующим образом:

1. Находит число , такое, что  и .Это сравнение разрешимо единственным образом, поскольку .

Для решения сравнения  пользователь  должен вычислить .

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

Алгоритм применения RSA.

1. Отправитель выбирает два больших простых числа  и . Вычисляет два произведения  и

2. Затем он выбирает случайное число (целое), взаимно простое с , и вычисляет , удовлетворяющее условию .

3. После этого он публикует  и  как свой открытый ключ шифрования, сохраняя  как закрытый ключ.

4. Если – сообщение, длина которого, определяемая по значению выражаемого им целого числа, должна быть в интервале , то она превратится в криптограмму возведением в степень  по модулю и отправляется получателю в следующем виде .

5. Получатель сообщения расшифровывает его. Возводя в степень  по модулю , так как

Пояснение.

Таким образом, открытым ключом служит пара чисел  и , а секретным ключом число . Крипкостойкость системы RSA основана на том, что  не может быть просто вычислена без значения  и , нахождение этих сомножителей из  достаточно трудоемко.