Квантовые вычисления со времен Демокрита - Скотт Ааронсон

взлом? Поразительно (если вы никогда прежде об этом не слышали), но ответ на этот вопрос оказывается положительным, и еще более поразительно, что такая система была открыта только в 1920-е гг. По причинам, о которых мы поговорим чуть позже, прототип системы, безопасной согласно теории информации, называется одноразовым ключом. Идея проста: текстовое сообщение представляется в виде двоичной строки p, над которой производится операция исключающего «или» (xor) со случайной двоичной ключевой строкой k той же длины. То есть зашифрованный текст c равен p ⊕ k, где знаком ⊕ обозначается побитовое сложение по модулю 2.

Получатель (которому известна k) может расшифровать шифрованное послание при помощи еще одной операции исключающего «или»:

c⊕k=p⊕k⊕k=p.

Для стороны, перехватившей послание и не знающей k, зашифрованный текст — это просто строка случайных бит, поскольку результатом операции исключающего «или» между произвольной строкой (посланием) и случайной строкой является еще одна случайная строка. Проблема с одноразовыми ключами, конечно, в том, что и отправителю, и получателю должен быть известен ключ, не менее длинный, чем само послание. Более того, если один и тот же ключ будет использован для шифрования двух или более посланий, то криптосистема перестанет быть безопасной с точки зрения теории информации. (Отсюда и название — «одноразовый ключ».) Чтобы понять, почему, предположим, что два текста p1 и p2 шифруются при помощи одного и того же ключа k и дают в результате шифрованные тексты c1 и c2 соответственно. Тогда мы имеем

c 1 ⊕ c 2 = p 1 ⊕ k ⊕ p 2 ⊕ k = p 1 ⊕ p 2,

и, следовательно, перехвативший может получить строку p1 ⊕ p2. Само по себе это может оказаться, а может и не оказаться полезным, но это, по крайней мере, позволяет противнику получить какую-то информацию об исходном тексте. Но ведь это всего лишь математическая диковинка, не правда ли? Ну, в 1940-е годы Советы проявили небрежность и использовали повторно некоторые из своих одноразовых ключей. В результате Агентство национальной безопасности АНБ в рамках проекта VENONA сумело восстановить некоторые (хотя и не все) зашифрованные таким способом сообщения. Кажется, именно так были пойманы Юлиус и Этель Розенберги.

В 1940-е гг. Клод Шеннон доказал, что теоретически надежная криптография требует, чтобы у отправителя и получателя был общий ключ длиной не менее длины того сообщения, которое они хотят передать. Как почти все результаты Шеннона, задним числом этот вывод кажется тривиальным. (Хорошо начинать с самого начала!) Вот его доказательство: если имеются шифрованный текст и ключ, лучше, чтобы исходный текст восстанавливался по этим данным однозначно. Иными словами, при любом фиксированном ключе функции, преобразующей исходный текст в шифрованный, лучше быть инъективной. Но из этого сразу же следует, что для заданного шифрованного текста c число исходных текстов, из которых в принципе мог получиться c, не превышает числа ключей. Иными словами, если возможных ключей меньше, чем исходных текстов, то противник сможет исключить некоторые из исходных текстов — те, из которых c не получится ни при каком значении ключа. Поэтому наша криптосистема не будет совершенно надежной. Следовательно, если мы хотим совершенной надежности, нужно иметь по крайней мере столько же ключей, как и исходных текстов — или, что эквивалентно, ключ должен содержать по крайней мере столько же бит, сколько содержится в исходном тексте.

Я уже упоминал, что передавать друг другу и хранить ключи громадной длины, как правило, непрактично, — даже КГБ не удавалось проделывать это без сучка без задоринки! Потому нам нужна криптосистема, которая позволяет обходиться менее длинными ключами. Конечно, результат Шеннона подразумевает, что такая система не будет надежной с точки зрения теории информации. Но что, если мы немного снизим требования? В частности, что, если мы будем считать, что перехвативший ограничен полиномиальным временем? Этот вопрос естественным образом переводит нас к нашей следующей теме…

Генераторы псевдослучайных последовательностей

Как я упоминал в предыдущей главе, генератор псевдослучайной последовательности PRG