Ни один из известных мне криптоалгоритмов с открытым ключом (ни RSA, ни Диффи-Хеллман) P<NP не используют. RSA использует то, что неизвестно алгоритмов разбиения числа на множители, существенно лучших, чем перебор пространства множителей. Диффи-Хеллман и его варианты на эллиптических функциях использует сложности с обращением целочисленных функций, вычисляемых по модулю.
Где-то, по моему у Кнута (лень проверять, но если интересно - поищу) я читал байку, что какой-то чувак предлагал алгоритм с публичным ключом на основе NP-полной задачи. Ривест (который R в RSA) его поимел в лет, основываясь на том факте, что на большинстве данных реальная NP-полная задача решается за вполне полиномиальное время с использованием жадного алгоритма или перебора с отсечениями ("динамики").
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
timeasmymeasure
Справедливости ради