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

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

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

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

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

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

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

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

Табл. 7-9.

Длины симметричных и открытых ключей с аналогичной устойчивостью к вскрытию грубой силой

Из этой таблица можно сделать вывод, что если вы достаточно беспокоитесь о своей безопасности, чтобы выбрать симметричный алгоритм со 112-битовым ключом, вам следует выбрать длину модуля в вашем алгоритме с открытыми ключами порядка 1792 бит. Однако, в общем случае следует выбирать длину открытого ключа более безопасную, чем длина вашего симметричного ключа . Открытые ключи обычно используются дольше и применяются для защиты большего количества информации .

7.4 Вскрытие в день рождения против однонаправленных хэш-функций

Существует два способа вскрытия однонаправленных хэш-функций грубой силой . Первый наиболее очевиден: дано значение хэш-функции сообщения, H(M), врагу хотелось бы суметь создать другой документ, М, такой, что H(M)=H(M). Второй способ более тонок: врагу хотелось бы найти два случайных сообщения, M и М, таких, что H(M)=H(M). Такой способ называется столкновением и является более простым, чем первый, способом вскрытия.

Парадокс дня рождения является стандартной статистической проблемой. Сколько человек должно собрат ь-ся в одной комнате, чтобы с вероятностью 1/2 хотя бы у кого-нибудь из них был бы общий с вами день рожд е-ния? Ответ - 183. Хорошо, а сколько людей должно собраться, чтобы с вероятностью 1/2 хотя бы у двоих из них был бы общий день рождения? Ответ удивителен - 23. 23 человека, находящихся в комнате, образуют 253 различных пары.

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

Предположим, что однонаправленная хэш-функция безопасна, и лучшим способом ее вскрытия является вскрытие грубой силой. Результатом функции является m-битовое число. Поиск сообщения, хэш-значение которого совпадает с заданным, в среднем потребовал бы хэширования 2 m случайных сообщений. А для обнаружения двух сообщений с одинаковым хэш-значением потребуется только 2 m/2 случайных сообщений. Компьютеру, который хэширует миллион сообщений в секунду, потребовалось бы 600000 лет, чтобы найти второе сообщение с тем же 64-битовым хэш-значением. Тот же компьютер сможет найти пару сообщений с общим хэш-значением примерно за час

Это значит, что, если вы опасаетесь вскрытия в день рождения, вы должны выбирать длину хэш-значения в два раза длиннее, чем вам потребовалось бы в противном случае . Например, если вы хотите уменьшить вероятность взлома вашей системы до 1 шанса из 2 80, используйте 160-битовую однонаправленную хэш-функцию .

7.5 Каков должны быть длина ключа?

На этот вопрос нет единого ответа, ответ этот зависит от ситуации . Чтобы понять, какая степень безопасн ости вам нужна, вы должны задать себе несколько вопросов . Сколько стоит ваша информация? Как долго она должна безопасно храниться? Каковы ресурсы ваших врагов?

Список клиентов может стоить $1000. Финансовая информация при неожиданном разводе могла бы стоить $10000. Реклама и данные маркетинга для большой корпорации могли бы стоить 1 миллион долларов . Главный ключ для системы электронных наличных может стоить миллиарды .

В мире торговли предметами потребления секреты должны только сохраняться в течение нескольких минут. В газетном бизнесе сегодняшние секреты - это завтрашние заголовки. Информация о разработке какого-то пр о-дукта, возможно, должна будет храниться в секрете в течение года или двух Изделия(программы) могла бы была бы должна остаться секретом в течение года или два. Данные переписи США в соответствии с законом должны храниться в секрете в течение 100 лет.

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

В этих терминах даже можно определить требования к безопасности Можно . Например:

Длина ключа должна быть такой, чтобы взломщик, готовый потратить 100 миллионов долларов, мог взломать систему в течение года с вероятностью не более, чем 1/2 32, даже с учетом скорости технического прогресса 30 процентов в год.

В -3-й, частично взятой из [150], приведены оценки требований к безопасности для различной информ ации:

Будущую вычислительную мощь оценить нелегко, но вот разумное эмпирическое правило : эффективность вычислительных средств удваивается каждые 18 месяцев и возрастает на порядок каждые 5 лет . Следовательно, через 50 лет самые быстрые компьютеры будут в 10 миллиардов быстрее, чем сегодня ! Кроме того, не забывайте, что эти числа относятся только к универсальным компьютерам, кто знает, какие специализированные ус тройства для вскрытия криптосистем будут разработаны в следующие 50 лет ?

Предполагая, что криптографический алгоритм будет использоваться в ближайшие 30 лет, вы можете пре д-ставить себе, насколько он должен быть безопасен . Алгоритм, созданный сегодня, возможно не станет широко использоваться до 2000 года, и все еще будет использоваться в 2025 для шифрования сообщений, которые должны оставаться в секрете до 2075 года и позже.

Табл. 7-10.

Требования к безопасности различной информации

Минимальная дли-

Типы трафикаВремя жизнина ключа (в битах)

Тактическая военная информацияминуты/часы56-64

Объявления о продуктах, слиянии компаний, процент-дни/недели64 ных ставках

Долговременны бизнес-планы годы64

Торговые секреты (например, рецепт кока-колы)десятилетия112

Секреты водородной бомбы >40 лет128

Личности шпионов >50 лет128

Личные дела >50 лет128

Дипломатические конфликты >65 лет128

Данные переписи США 100 летпо меньшей мере

7.6 Caveat emptor1

Вся эта глава - просто много чепухи. This entire chapter is a whole lot of nonsense. Смешно говорить даже о самом понятии предсказания вычислительной мощи на 10, а тем более на 50 лет вперед . Эти расчеты приведены только для ориентировки, ни для чего больше. Экстраполируя прошлое, мы получаем будущее, которое, возможно, будет иметь мало общего с грядущей реальностью .

Будьте консерваторами. Если ваши ключи длиннее, чем вам кажется необходимым, то меньшее количество технологических сюрпризов сможет повредить вам.

1 Да будет осмотрителен покупатель (латин.)