Асимметричные алгоритмы шифрования

Развитие основных типов криптографических протоколов (ключевой обмен, электронно-цифровая подпись, аутентификация, так называемые эзотерические протоколы) было бы невозможно без создания открытых ключей и построенных на их основе асимметричных алгоритмов шифрования.
В данном разделе мы ограничимся кратким описанием идеи построения асимметричных алгоритмов (на примере алгоритма RSA), а также затронем вопросы теоретической стойкости подобных алгоритмов (в частности, практические аспекты обеспечения стойкости алгоритма RSA). В силу того, что с точки зрения практической реализации асимметричные алгоритмы по своей природе являются достаточно «медленными», здесь также будет уделено внимание вопросам ускорения основных типов вычислений, используемых в этих алгоритмах.
С одной стороны, идея асимметричных алгоритмов тесно связана с развитием теории односторонних функций, с другой - с теорией сложности. Под односторонней функцией мы будем понимать легко-вычисляемое отображение f(x): X-*Y, xeX. При этом, обратное отображение является сложной задачей. Она называется трудно-вычисляемой, если нет алгоритма для ее решения с полиномиальным временем работы.

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