Криптосистема без передачи ключей
Пусть абоненты условились организовать между собой секретную переписку. Для этой цели они выбирают достаточно большое простое число такое, что хорошо разлагается на не очень большие простые множители. Затем каждый из абонентов независимо один от другого выбирает себе некоторое натуральное число, взаимно простое с . Пусть число абонента - , абонента - и т.д. Числа
составляют первые секретные ключи соответствующих абонентов. Вторые секретные ключи ( для ,
для и т.д.) находятся из уравнений: для из , ; для - из , и т.д. Пересылаемые сообщения, коды-числа, должны быть меньше . В случае, когда сообщение больше или равно , оно разбивается на части таким образом, чтобы каждая часть была числом, меньшим .
Предположим абонент решил отправить сообщение
() . Для этого он сначала зашифровывает свое сообщение ключом , получая по формуле шифрованное сообщение , которое отправляется . , получив , зашифровывает его своим ключом , получая по формуле шифрованное сообщение , которое отправляется обратно к . шифрует полученное сообщение ключом по формуле и окончательно отправляет к . , используя ключ , сможет теперь расшифровать исходное сообщение . Действительно, , т.к. , следовательно, для некоторого целого
и , т.к. по теореме Эйлера-Ферма.
Пример. Абоненты и вместе выбрали (), выбрал , а - . Затем из уравнения
находит , а из подобного уравнения находит . При передаче сообщения от к
сначала отправляет к
, из
вычисляет и отправляет его обратно , из вычисляет для
, наконец, может прочитать посланное ему сообщение .
Упражнение 48
Между абонентами и установлен секретный канал связи без передачи ключей при заданных и их первых ключах 15 и 21. Описать процесс передачи сообщений 22 (от к ) и 17 (от к ).
