Квантовая дешифровка: Взлом 15-ти
Около 15-ти лет назад Питер Шор (Peter Shor) предсказал, что квантовые компьютеры легко и существенно превзойдут все существующие сегодня вычислительные системы. И это несмотря на то, что они способны выдавать лишь «приблизительный» ответ — о чем лучше всего прочесть в статье «Женская логика».
Тогда же Шор заметил, что для квантовых компьютеров популярные сегодня системы шифрования с открытым ключом не станут преградой. Идея, лежащая в основе таких криптосистем, весьма остроумна: для шифрования используется 2 ключа, один из которых передается по общедоступному каналу, а второй (секретный) используется для дешифровки сообщения. Чтобы проиллюстрировать схему его работы, часто прибегают к аналогии с телефонным справочником.
Допустим, вы хотите передать мне шифрованное сообщение: «машина». Вы берете телефонный справочник и ищете номера людей, чьи фамилии начинаются на соответствующую букву. Скажем: Мамонтов (222−2222), Апресов (333−3333), Шилов (111−1111) и так далее. Ваше сообщение будет выглядеть так: 222−2222, 333−3333, 111−1111 и так далее. Можно даже усложнить задачу, выбирая разных людей, чьи фамилии начинаются на одну и ту же букву. У меня на руках есть справочник (секретный ключ), в котором представлены все номера телефонов, в порядке возрастания, по которому я легко найду нужную фамилию и восстановлю ваше сообщение. Злоумышленник же, имея на руках только обычный телефонный справочник (открытый ключ), потратит уйму сил и времени, чтобы найти нужные номера и узнать, о чем мы переписываемся.
В действительности, конечно, никаких телефонных справочников не требуется. Зашифрованное сообщение предстает очень большим числом, которое получается в ходе шифрования как произведение других чисел, одно из которых — секретный ключ. Не зная его, практически нереально установить второй из множителей. Для взлома такой системы требуются очень большие вычислительные мощности, и шифрование с открытым ключом считается весьма безопасным. На его базе действуют защищенные интернет-протоколы TLS и SSL, и даже электронная цифровая подпись, которая по российскому законодательству считается достаточной для официальной идентификации автора электронного документа и используется компаниями и госструктурами в документообороте.
На практике, чтобы дешифровать криптосообщение с открытым ключом, зачастую требуется выполнить столько простых операций, что современным компьютерам на такое нужно огромное количество времени. Однако для квантовых компьютеров это не проблема: сам принцип их работы позволяет найти нужную комбинацию с легкостью. И подтверждение этому впервые продемонстрировано в деле: 26-миллиметровый микрочип, созданный британскими учеными Джереми О’Брайеном (Jeremy O’Brien), Джонатаном Мэттьюсом (Jonathan Matthews) и Альберто Полити (Alberto Politi), пока не готов к реальному взлому шифров, но ему удалось продемонстрировать свою работоспособность, разложив на множители число 15.
Отметить стоит и тот факт, что сам микрочип технически не представляет собой чего-то слишком сложного и состоит из обычного кремния, удобен и дешев в производстве. Правда, через него приходится пропускать не электричество, а фотоны, к тому же и квантово запутанные. И для их создания и измерений требуется пока что довольно сложная и громоздкая аппаратура. Но главное — принцип работает, и это — еще один шаг к сверх-миниатюрным и сверх-мощным квантовым компьютерам будущего.
По публикации New Scientist Tech
