Математики, шпионы и хакеры

«БОЛЬШОЙ БРАТ» XXI ВЕКА.

Результатом создания жизнеспособного квантового компьютера станет не просто крах современной криптографии. Такая вычислительная мощность на службе государственных или частных интересов может сместить баланс сил в мире. Битва за то, чтобы стать первой страной, развившей такие технологии, может легко превратиться в еще одну технологическую гонку, похожую на гонки второй половины XX в.: за выход в космос и гонку вооружений. Логично предположить, что любой прогресс в этой области будет держаться в тайне из соображений национальной безопасности. Может, в каком-то уголке мира, в холодных подземных туннелях, уже готов к запуску квантовый компьютер, который навсегда изменит нашу жизнь?

ПРОЩАЙ, DES, ПРОЩАЙ

Через два года после того, как Шор продемонстрировал, что квантовый компьютер может взломать шифр RSA, другой американец, Лов Гровер

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

Конец криптографии?

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

Эта операция чрезвычайно трудоемкая, и пока не существует математической лазейки для ее решения. Может ли квантовой компьютер взять на себя задачу разложения числа на простые числа, которые использует шифр RSA? Американский ученый Питер Шор в 1994 г. дал на этот вопрос утвердительный ответ. Шор разработал алгоритм для квантового компьютера, способный разложить большие числа на множители за намного меньшее время, чем самый мощный обычный компьютер.

Если это поразительное устройство когда-либо будет построено, алгоритм Шора кирпичик за кирпичиком разрушит мощное криптографическое здание, построенное на RSA, и наступит день, когда вся самая тайная информация на планете станет явной. Все современные системы шифрования постигнет та же участь. Но, перефразируя Марка Твена, мы можем сказать, что слухи о смерти криптоанализа «сильно преувеличены».

Квантовая механика взяла, квантовая механика дала