Квантовые вычисления

А теперь еще большая фантастика. В основе квантовых вычислений используется двойственная природа м а-терии (и волна, и частица). Фотон может одновременно находиться в большом количестве состояний. Классич е-ским примером является то, что фотон ведет себя как волна, встречая частично прозрачное зеркало. Он одн о-временно и отражается и проходит через зеркало подобно тому, как морская волна, ударяясь о волнолом с н е-болыпим отверстием в нем, одновременно отразится от стены и пройдет сквозь нее. Однако, при измерении фотон ведет себя подобно частице, и только одно состояние может быть обнаружено.

В [1443] Питер Шор (Peter Shor) очертил принципы построения машины для разложения на множители, о с-нованной на законах квантовой механики. В отличие от обычного компьютера, который можно представить как машину, имеющее в каждый момент времени единственное фиксированное состояние, квантовый компьютер обладает внутренней волновой функцией, являющейся суперпозицией комбинаций возможных основных с о-стояний. Вычисления преобразуют волновую функцию, меняя весь набор состояний единым действием. Таким образом, квантовый компьютер имеет преимущество над классическим конечным автоматом: он использует квантовые свойства для числа разложения на множители за полиномиальное время, теоретически позволяя взломать криптосистемы, основанные на разложении на множители или задаче дискретного логарифма.

Общепризнанно, что квантовый компьютер не противоречит фундаментальным законам квантовой механ и-ки. Однако, непохоже, что квантовая машина для разложения на множители будет построена в обозримом б у-дущем... если вообще будет построена. Одним из главных препятствий является проблема некогерентности, которая является причиной потери отчетливости волновыми огибающими и приводит к сбою компьютера. Из-за некогерентности квантовый компьютер, работающий при 1К, будет сбиваться каждую наносекунду. Кроме того, для построения квантового устройства для разложения на множители потребуется огромное количество вент и-лей, а это может не дать построить машину. Для проекта Шора нужно совершенное устройство для возведения в степень. Внутренние часы не используются, поэтому для разложения на множители криптографически знач и-мых чисел могут потребоваться миллионы или, возможно, миллиарды индивидуальных вентилей. Если мини­мальная вероятность отказа каждого из п квантовых вентилей равна/;, то среднее количество испытаний, необ­ходимое для достижения успеха, составит (V(l-p)f. Число нужных вентилей, по видимому, растет полиноми­ально с ростом длины числа (в битах), поэтому число требуемых попыток будет расти с увеличением длины используемых чисел сверхэкспоненциально - хуже чем при разложении делением!

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

7.3 Сравнение длин симметричных и открытых ключей

Система взламывается обычно в ее слабейшем месте. Если вы проектируете систему, которая использует и симметричную криптографию, и криптографию с открытыми ключами, то длины ключей для криптографии каждого типа должны выбираться так, чтобы вскрыть любой из компонентов системы было одинаково трудно. Бессмысленно использовать симметричный алгоритм со 128-битовым ключом вместе с алгоритмом с открыт ы-ми ключами, использующим 386-битовый ключ. Точно так же бессмысленно использовать в одной системе симметричный алгоритм с 56-битовым ключом и алгоритм с открытыми ключами, применяющий 1024-битовый ключ.

В -2-й перечислены длины модулей открытых ключей, трудность разложения которых на множители ера в-нима со сложностью вскрытием грубой силой сопоставленных длин популярных симметричных ключей.

Табл. 7-9.

Длины симметричных и открытых ключей с аналогичной jc-