Эта операция чрезвычайно трудоемкая, и пока не существует математической лазейки для ее решения. Может ли квантовой компьютер взять на себя задачу разложения числа на простые числа, которые использует шифр RSA? Американский ученый Питер Шор в 1994 г. дал на этот вопрос утвердительный ответ. Шор разработал алгоритм для квантового компьютера, способный разложить большие числа на множители за намного меньшее время, чем самый мощный обычный компьютер.
Если это поразительное устройство когда-либо будет построено, алгоритм Шора кирпичик за кирпичиком разрушит мощное криптографическое здание, построенное на RSA, и наступит день, когда вся самая тайная информация на планете станет явной. Все современные системы шифрования постигнет та же участь. Но, перефразируя Марка Твена, мы можем сказать, что слухи о смерти криптоанализа «сильно преувеличены».
Одной из основ квантовой механики является принцип неопределенности, открытый Вернером Гейзенбергом в 1927 г. Хотя его точная формулировка очень сложна, сам Гейзенберг обобщил его следующим образом: «Мы в принципе не можем знать настоящее во всех подробностях». Более точно: невозможно определить с любой степенью точности те или иные свойства частицы в любой момент времени. Возьмем, например, частицы света (фотоны). Одной из их основных характеристик является поляризация — технический термин, связанный с колебаниями электромагнитных волн. [Хотя фотоны поляризованы во всех направлениях, в нашем примере мы будем считать, что они имеют поляризацию четырех типов: вертикальную 
, горизонтальную 
, по диагонали слева направо вниз 
, по диагонали слева направо вверх 
. Принцип Гейзенберга утверждает, что для определения поляризации фотона нужно пропустить его через фильтр, или «щель», которая, в свою очередь, может быть горизонтальной, вертикальной и диагональной: слева направо вниз или слева направо вверх. Фотоны, поляризованные горизонтально, пройдут горизонтальный фильтр без изменений, а поляризованные вертикально этот фильтр не пройдут. Что касается фотонов, которые поляризованы по диагонали, то половина из них пройдет через этот фильтр, поменяв поляризацию с диагональной на горизонтальную, а другая половина этот фильтр не пройдет. Это будет происходить случайным образом. Более того, после того как фотон пройдет фильтр, невозможно будет с уверенностью сказать, какова была его первоначальная поляризация.
Если мы пропустим ряд фотонов с различной поляризацией через горизонтальный фильтр, то увидим, что половина фотонов, поляризованных по диагонали, пройдет через фильтр, поменяв поляризацию на горизонтальную.
Какова связь между поляризацией фотонов и криптографией? Очень существенная, как мы увидим ниже. Для начала представим себе исследователя, который хочет определить поляризацию ряда фотонов. Для этого он выбирает фильтр с фиксированной ориентацией, например, горизонтальный. Предположим, что фотон прошел через фильтр. Какой вывод может сделать наш исследователь? Конечно, он может сказать, что исходная поляризация фотона не была вертикальной. А может он сделать другие предположения? Нет. Казалось бы, можно подумать, что более вероятно, что этот фотон был поляризован по горизонтали, а не по диагонали, потому что половина фотонов, поляризованных по диагонали, не проходит через фильтр.
Но зато число фотонов, поляризованных по диагонали, в два раза больше, чем с горизонтальной поляризацией. Важно подчеркнуть, что трудность определения поляризации фотона заключается не в каких-то технологических или теоретических проблемах, которые могут быть устранены в будущем; трудность является следствием самой природы мира частиц. Если использовать этот эффект надлежащим образом, то можно создать совершенно неуязвимый шифр, «святой грааль» криптографии.
Неуязвимый шифр
В 1984 г. американец Чарльз Беннет и канадец Жиль Брассар выдвинули идею системы шифрования на основе передачи поляризованных фотонов. Сначала отправитель и получатель договариваются, как разным поляризациям поставить в соответствие 0 или 1. В нашем примере это будет функцией двух видов поляризации: первый вид, называемый прямолинейной поляризацией и обозначаемый символом +, где 1 соответствует вертикальной поляризации , а 0 — горизонтальной , второй вид, называемый диагональной поляризацией и обозначаемый символом х, ставит в соответствие 1 диагональную поляризацию слева направо вверх , а 0 — диагональную поляризацию слева направо вниз .
Например, сообщение 0100101011 будет передано следующим образом:
Если шпион перехватит передачу, ему придется использовать фильтр с фиксированной ориентацией х:
Как мы видим, не зная изначального вида поляризации, шпион не может извлечь полезную информацию из поляризации, определенной фильтром. Даже зная правило соответствия 0 и 1, используемое отправителем и получателем, шпион будет ошибаться в трети из случаев, в которых вид поляризации выбирается случайным образом (в таблице показаны все возможные комбинации при описанных условиях). Однако проблема заключается в том, что получатель находится не в лучшем положении, чем шпион.
Хотя отправитель и получатель могут обойти эту проблему, послав друг другу последовательность видов поляризаций с помощью какого-то защищенного метода, например, RSA шифрования, но тогда шифр будет уязвим для гипотетических квантовых компьютеров.
Чтобы преодолеть это последнее препятствие, Брассару и Беннету пришлось усовершенствовать свой метод. Если читатель помнит, ахиллесовой пятой полиалфавитных шифров, таких как квадрат Виженера, являлось использование коротких повторяющихся ключей, из-за которых в шифре возникали закономерности, что создавало небольшую, но достаточную возможность для криптоаналитика взломать шифр. Но что было бы, если бы ключ представлял собой случайный набор символов и был длиннее, чем само послание, а каждое сообщение, даже самое незначительное, для большей безопасности было бы зашифровано другим ключом? Тогда бы у нас получился неуязвимый шифр.
Первым человеком, предложившим использовать полиалфавитный шифр с уникальным ключом, был Джозеф Моборн. Вскоре после Первой мировой войны, будучи начальником службы связи американского криптографического отдела, Моборн придумал блокнот с ключами, каждый из которых содержал более 100 случайных символов. Такие блокноты выдавались отправителю и получателю с инструкцией уничтожать использованный ключ и переходить к следующему. Эта система, известная как шифрблокнот одноразового назначения, является, как мы уже говорили, неуязвимой, и это можно доказать математически. И действительно, самые секретные послания между главами государств шифруются с помощью этого метода.