dxdt.ru: занимательный интернет-журнал

Что-то довольно часто смешивают квантовый компьютер и квантовую криптографию – самым причудливым образом, особенно в этом преуспевают журналисты. Видимо, причина вот в чём: криптография в сознании обывателя теперь прочно привязана к компьютерам вообще (что, в общем, соответствует окружающей действительности), в этой канве и делаются “логические” привязки – неверные.

Между тем, квантовый компьютер – это гипотетическое устройство, которое может позволить выполнять некоторые “вычислительные” операции, используя, скажем так, “квантовые свойства материи”. Но, во-первых, в строгом смысле, квантовый компьютер ничего не вычисляет – вычисления на нём можно проводить лишь приведя некоторую задачу к физической модели, реализуемой в данном квантовом компьютере. (Сразу оговорюсь: только что приведённое описание ситуации – очень грубое.) А, во-вторых, практических квантовых компьютеров пока не создано. Например, про упражнения коммерческих компаний по созданию квантовых компьютеров я как-то писал в одной из колонок на “ИнфоБуме”.

Квантовая криптография – это метод создания канала связи, скрытное прослушивание которого “невозможно” (более строго: такое прослушивание будет обнаружено с очень высокой вероятностью). Квантовая криптография тоже использует “квантовые свойства материи”, но, вообще говоря, ничего не шифрует. А практическая польза квантовой криптографии состоит в том, что с её использованием можно организовать очень защищённый (законами квантовой механики) открытый обмен ключами. После того как ключи, с помощью “квантовой криптографии”, распределены между сторонами, шифрование производится вполне традиционным образом. Реальные системы квантовой криптографии уже созданы.

Теоретически, квантовый компьютер может дать инструмент для быстрой факторизации больших чисел [факторизация - это нахождение разложения числа (целого, понятно) на простые множители]. Для этого придуман особый алгоритм Шора. На сложности задачи факторизации основаны распространённые сегодня криптосистемы с открытым ключом (например, RSA). Таким образом, – теоретически, опять же, – появление квантового компьютера достаточной “разрядности” ставит под угрозу практическую стойкость этих криптосистем. Впрочем, оценка этой угрозы очень туманна: может так статься, что раньше, чем появится квантовый компьютер, придумают очередной аналитический метод факторизации, быстро работающий на традиционных компьютерах (исследования этого направления в математике не затихают).

Квантовая криптография абсолютна надёжна тоже только в теории, потому что на стойкость практической системы сильно влияют возможные ошибки в практической реализации протокола и электронных схем. Зашифрованная с помощью распределённых по “квантовому каналу” ключей информация вполне может быть расшифрована криптоаналитиком, вооружённым традиционным компьютером – квантовый компьютер тут совсем не является необходимым.

Bugtraq сообщает:

Немецкий любитель Иоахим Шютц (Joachim Schueth) победил в соревновании по дешифровке компьютер, спроектированный в свое время для взлома немецких шифров.

[...]

Реанимированный Colossus принял участие в соревновании по дешифровке радиосообщения, закодированного шифровальной машиной 38 года Lorenz SZ42 (предварительно его еще нужно было перехватить). В соревновании приглашались принять участие все желающие.

[...]

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

Исходный Colossus – это специализированная британская вычислительная машина 1943-го года. В 1945-м, после окончания войны, все Colossus разрушили, как очень секретную технику.

А на картинке ниже – германский шифратор Lorenz SZ42, представляющий другую сторону борьбы и войны:

(Фото: Matt Crypto)

Касперские рассказывают как вышло, что их антивирус оказался способным восстанавливать файлы, шифрованные троянской программой GpCode с помощью RSA. Эта “загадка”, помнится, вызывала некоторые споры: дело в том, что в типовом случае для дешифрования тут нужен секретный ключ, которого в шифрующем модуле не было. А поэтому спрашивали, где Касперские взяли секретный ключ? Но, конечно, в действительности все оказалось ожидаемо: автор вируса использовал нестойкий открытый ключ длиной в 56 бит. Понятно, что на его основе можно быстро раскрыть соответствующий ключ секретный. Теория заговора опять развалилась.

Киш (Laszlo Kish) продолжает полемику про свою абсолютно стойкую криптосистему с резисторами. Оказывается, появился ответ (physics/0602013) на возражения, высказанные ранее в статье physics/0509136.

(physics/0602013: We point out that the security of the idealized (mathematical model) scheme of the Kirchhoff-loop-Johnson(like)-noise (KLJN) cipher is absolute. On the other hand, practical realizations of any absolutely secure physical layer are never absolutely secure; and this statement is true for quantum communication, too. Then we address the basic mistakes in the Scheuer-Yariv paper.)

Update: На поверку все ж совсем пустая статья, ничего не доказывающая. Похоже, автор признает, что предложенная ранее схема действительно далека от абсолютной стойкости.

На немного нашумевшие резисторы, связываемые в статье physics/0509136 с “абсолютно” стойкой “классической криптографией”, – то есть, не квантовой, – пока нашелся только один сколь-нибудь обстоятельный ответ: physics/0601022 (авторы рассказывают о паре пассивных методов, делающих предложенную схему не абсолютно стойкой). Пока не ясно, кто ближе к истине.