Реферат: Квантовые вычисления

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

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

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

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

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

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

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

Табл. 7-9.

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