Функции с закрытыми дверями

Одностороннюю функцию по вполне понятным соображениям невозможно использовать в качестве шифровального устройства, так как , хотя f(X) -- надежно зашифрованное сообщение Х, никто (даже законный получатель) не сможет восстановить Х. Существует способ, позволяющий обойти эту трудность с помощью так называемой функции с закрытыми дверями. Такова, например, функция 

                    100    120
                 E:F   -->F  ,
имеющая обратную функцию 
                   120    100
                 D:F   -->F  ,
где обе функции D и Е легко вычислимы. Узнать обратную функцию по Е невозможно: до тех пор, пока вам не сообщат, что функция, обратная Е, существует, Е воспринимается как односторонняя функция. Функцию Е можно использовать для шифровки, а обратную функцию D -- для дешифровки, так как при всех Х из
D(E(X))=X.

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

Зная, как найти функции с закрытыми дверями, мы можем построить криптосистему с общественным ключом. Предположим, что существует группа людей, желающих беседовать друг с другом конфидециально. Каждый i член группы выбирает функцию с закрытыми дверями Еi , имеющую обратную функцию Di . Функции Еi перечисляют в общедоступном справочнике, в то время как "свою" обратную функцию Di каждый хранит в тайне. Если член j группы желает послать сообщение Х члену i группы, он просто передает

Y=Ei(X)
по общественному каналу связи. Так как обратная функция Di известна только члену i группы, он может вычислить
Di(Y)=Di(Ei(X))=X
и прочитать сообщение. Так мы приходим к сети связи, обеспечивающей секретность без использования ключей.
Содержание