Цитата:
Если приводить к фундаментальным математическим проблемам, то все существующие алгоритмы с открытым ключём стремятся построить таким образом что бы они были похожи на полиномиальные для владельца секретного ключа и на NP-полные проблемы для всех остальных.
В [1.2, pp. 461-482] приведено 9 таких систем (ну, скажем, популярные ныне элипические кривые это просто смена конечного поля, ещё парочку можно свести к другим, но 6 принципиально разных алгоритмов имеется).
В тоже время доказательств NP-полноты нет ни у большинства из них, а про RSA имеются серьёзные подозрения на его полиномиальность.
http://www.getinfo.ru/article244.html?print=Y