Книга: Золотой билет

Проблемы разрастаются

Проблемы разрастаются

Шифрование с открытым ключом базируется на «неприступности» таких NP-задач, как разложение на множители. Достаточно случайным образом выбрать два больших простых числа и перемножить их – и вы получите число, которое никто, кроме вас, на множители, скорее всего, не разложит.

Является ли задача разложения на множители NP-полной, мы не знаем; на самом деле это очень маловероятно. Впрочем, если бы она даже и была NP-полна, то из неравенства классов P и NP следовало бы лишь то, что некоторые числа трудно разложить на множители, а относительно всех случайных чисел мы не могли бы утверждать то же самое.

В основе современной криптографии лежит предположение о неравенстве классов P и NP и практической неразрешимости NP-полных задач – и в этом-то и состоит ее главная проблема.

Новый этап в развитии криптографии, начало которому в семидесятых годах положили Диффи и Хеллман, привел нас к криптографическим протоколам, базирующимся на практической неразрешимости некоторых задач. Чемпионы по кроссвордам, великие шахматисты и талантливые математики уже не способны были разгадывать шифры силой своего интеллекта.

Впрочем, игра в кошки-мышки по-прежнему продолжается. Современные мошенники уже не взламывают сами шифры, а ищут уязвимые места в системе. В протоколе, которым пользуются Элис и Боб, числа могут оказаться недостаточно случайными. В операционной системе или браузере могут найтись дефекты, позволяющие хакеру проникнуть в компьютер. Злоумышленники могут обмануть Элис и заставить ее сообщить секретный ключ. А придумав ненадежный пароль, Элис сама поставит себя под удар.

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

Никакой, пусть даже самый стойкий шифр не гарантирует стойкость всей системы; не исключено, что абсолютно надежный протокол мы так и не создадим.

Оглавление книги