Автор статьи: Брюс Шнайер — американский криптограф, писатель и специалист по компьютерной безопасности. Автор нескольких книг по безопасности, криптографии и ИБ. Основатель криптографической компании Counterpane Internet Security, Inc., член совета директоров Международной ассоциации криптологических исследований и член консультативного совета Информационного центра электронной приватности.
Квантовые вычисления — это новый способ производить расчёты, который позволит человечеству выполнять вычисления, просто невозможные с использованием современных компьютеров. Возможность быстрого поиска сломает некоторые из современных алгоритмов шифрования. А лёгкая факторизация больших чисел сломает криптосистему RSA с любой длиной ключа.
Именно поэтому криптографы сейчас усиленно разрабатывают и анализируют «квантово-устойчивые» алгоритмы с открытым ключом. В настоящее время квантовые вычисления пока не готовы для нормальной оценки: что безопасно, а что нет. Но если предположить, что инопланетяне разработали технологию в полном объёме, то квантовые вычисления — не конец света для криптографии. Для симметричной криптографии квантово-устойчивость обеспечить элементарно, а сейчас мы ищем квантово-стойкие алгоритмы шифрования с открытым ключом. Если криптография с открытым ключом окажется временной аномалией, которая существует благодаря пробелам в наших математических знаниях и вычислительных способностях, мы всё равно выживем. И если какая-то немыслимая инопланетная технология сломает всю криптографию, у нас останется секретность, основанная на теории информации, пусть и со значительными потерями возможностей.
По сути, криптография опирается на математический выверт, что некоторые вещи легче сделать, чем отменить. Как легче разбить тарелку, чем склеить её обратно, также гораздо проще умножить два простых числа, чем разложить результат обратно. Асимметрии такого рода — односторонние функции и односторонние функции с потайным входом — лежат в основе всей криптографии.
Чтобы зашифровать сообщение, мы комбинируем его с ключом для формирования шифротекста. Без ключа обратить процесс сложнее. Не просто чуть сложнее, а астрономически сложнее. Современные алгоритмы шифрования настолько быстры, что зашифруют весь ваш жёсткий диск без особых подтормаживаний, а взлом шифра продолжится до тепловой смерти Вселенной.
С симметричной криптографией, используемой для шифрования сообщений, файлов и дисков, этот дисбаланс экспоненциален и усиливается по мере увеличения ключей. Добавление одного бита ключа увеличивает сложность шифрования менее чем на процент (грубо говоря), но удваивает сложность взлома. Таким образом, 256-битный ключ кажется лишь вдвое сложне, чем 128-битный, но (с нашими текущими знаниями математики) его в 340 282 366 920 938 463 463 374 607 431 768 211 456 раз сложнее сломать.
Шифрование с открытым ключом (используемое главным образом для обмена ключами) и цифровые подписи более сложны. Поскольку они полагаются на сложные математические проблемы, такие как факторизация, то существует больше разных трюков, чтобы их обратить. Таким образом, здесь вы увидите ключи длиной 2048 бит для RSA и 384 бита для алгоритмов, основанных на эллиптических кривых. Но опять же, взлом шифров с этими ключами выходит за пределы текущих возможностей человечества.
Поведение односторонних функций основано на наших математических знаниях. Когда вы слышите о криптографе, «ломающем» алгоритм, значит, он нашёл новый трюк, который упрощает реверсирование. Криптографы всё время находят новые трюки, поэтому мы склонны использовать ключи длиннее, чем строго необходимо. Это верно как для симметричных алгоритмов, так и для алгоритмов с открытым ключом: мы пытаемся гарантировать их надёжность в будущем.
Квантовые компьютеры обещают изменить многое из этого. По своей природе они хорошо приспособлены к вычислениям, которые необходимы для обращения этих односторонних функций. Для симметричной криптографии это не так уж плохо. Алгоритм Гровера показывает, что квантовый компьютер ускоряет атаки настолько, что эффективная длина ключа уменьшается вдвое. То есть 256-битный ключ так же сложен для квантового компьютера, как 128-битный ключ для обычного компьютера: оба они безопасны в обозримом будущем.
Для криптографии с открытым ключом результаты страшнее. Алгоритм Шора легко ломает все популярные алгоритмы с открытым ключом, основанные как на факторизации, так и на дискретном логарифмировании. Удвоение длины ключа увеличивает сложность взлома в восемь раз. Этого недостаточно для устойчивого развития.
По поводу двух последних абзацев есть много оговорок, главная из которых заключается в том, что квантовые компьютеры, способные делать что-либо подобное, в настоящее время не существуют, и никто не знает, когда мы сможем построить такой — и сможем ли вообще. Мы также не знаем, какие практические трудности возникнут, когда мы попытаемся реализовать алгоритмы Гровера или Шора на чём-нибудь кроме ключей игрушечного размера (механизм коррекции ошибок на квантовом компьютере легко может стать непреодолимой проблемой). С другой стороны, мы не знаем, какие ещё методы будут обнаружены, как только люди начнут работать с настоящими квантовыми компьютерами. Я ставлю на то, что мы преодолеем инженерные проблемы, и что будет много достижений и новых методов, но понадобится время, чтобы их изобрести. Так же, как нам потребовались десятилетия, чтобы сконструировать карманные суперкомпьютеры, потребуются десятилетия, чтобы проработать все инженерные проблемы, необходимые для создания достаточно мощных квантовых компьютеров.
В краткосрочной перспективе криптографы прилагают значительные усилия для разработки и анализа квантово-устойчивых алгоритмов. Наверное, они останутся в безопасности на протяжении десятилетий. Процесс наверняка будет идти медленно, потому что хороший криптоанализ требует времени. К счастью, у нас есть время. Реальные квантовые вычисления на практике как будто всегда «в десяти годах в будущем». Другими словами, ни у кого нет ни малейшего представления.
Но всегда есть вероятность, что алгоритмы взломают инопланетяне с лучшими квантовыми технологиями. Я меньше беспокоюсь о симметричной криптографии, где алгоритм Гровера — по сути максимальный предел возможности квантовых вычислений. А вот алгоритмы с открытым ключом, основанные на теории чисел, кажутся более хрупкими. Вполне возможно, что квантовые компьютеры когда-нибудь сломают их все — даже те, которые сегодня считаются квантово-устойчивыми.
Если это произойдёт, мы останемся в мире без криптографии с открытым ключом. Это станет огромным ударом по безопасности и сломает многие системы, но мы сможем адаптироваться. В 1980-х годах Kerberos была полностью симметричной системой аутентификации и шифрования. И сейчас стандарт сотовой связи GSM выполняет как аутентификацию, так и распределение ключей — в большом масштабе — только с симметричной криптографией. Да, эти системы имеют централизованные точки доверия и отказа, но можно разработать другие системы, которые используют как секретное разделение, так и секретное совместное использование, чтобы свести к минимуму этот риск. (Представьте, что пара участников связи получает часть ключа сеанса от каждого из пяти различных серверов ключей). Повсеместное распространение коммуникаций облегчает ситуацию. Мы можем использовать внеполосные протоколы: например, ваш телефон поможет сгенерировать ключ для компьютера. Для дополнительной безопасности можно использовать личную регистрацию: возможно, в магазине, где вы покупаете смартфон или регистрируете интернет-сервис. Развитие аппаратного обеспечения тоже поможет защитить ключи в этом мире. Я ничего не пытаюсь изобрести, только говорю, что что есть много возможностей. Мы знаем, что криптография основана на доверии, и у нас гораздо больше методов управления доверием, чем в первые годы существования интернета. Некоторые важные технологии, такие как прямая секретность, станут гораздо сложнее, но пока симметричная криптография работает, у нас сохранится защита.
Это странное будущее. Возможно, вся идея криптографии на теории чисел, как современные системы с открытым ключом — это временный феномен, существующий благодаря пробелам в модели вычислений. Теперь, когда модель расширилась и включила в себя квантовые вычисления, мы можем оказаться там, где были в конце 1970-х и начале 1980-х: симметричная криптография, криптография на основе кодов, подписи Меркла. Это будет забавно и иронично.
Да, я знаю, что распределение квантовых ключей является потенциальной заменой криптографии с открытым ключом. Но давайте честно: кто-нибудь вообще верит, что система, требующая специализированного коммуникационного оборудования и кабелей, будет использоваться для чего-либо, кроме нишевых приложений? Будущее — за мобильными, постоянно включенными вычислительными устройствами. Все системы безопасности для них будут только программными.
Есть ещё один сценарий будущего, не говоря о квантовых компьютеров. В основе односторонних функций лежат несколько математических теорий, которые ещё не доказаны. Это одна из открытых проблем в компьютерной науке. Так же, как умный криптограф может найти новый трюк, который облегчает взлом определённого алгоритма, мы можем представить себе инопланетян с достаточной математической теорией, чтобы сломать все алгоритмы шифрования. Для нас сегодня это просто смешно. Криптография с открытым ключом — это теория чисел, потенциально уязвимая для математически более грамотных пришельцев. Симметричная криптография настолько нелинейно сложна, а длина ключа так легко увеличивается, что будущее сложно вообразить. Представьте вариант AES с 512-битным блоком и размером ключа, и шифрованием в 128 раундов. Если только не придумать принципиально новую математику, такое шифрование будет безопасно до тех пор, пока компьютеры не сделают из чего-то другого, кроме материи, в каком-нибудь другом измерении.
Но если случится невообразимое, то останется криптография, основанная исключительно на теории информации: одноразовые блокноты и их варианты. Это будет огромный удар по безопасности. Одноразовые блокноты могут быть теоретически безопасными, но в практическом плане они непригодны для чего-то, кроме специализированных нишевых приложений. Сегодня только психи пытаются строить системы общего пользования на основе одноразовых блокнотов — и криптографы смеются над ними, потому что они заменяют проблемы разработки алгоритмов (лёгкие) проблемами управления ключами и проблемами физической безопасности (что намного, намного сложнее). Возможно, в нашем фантастическом будущем, охваченном пришельцами, у нас останется только такой выход.
Против этих богоподобных пришельцев криптография останется единственной технологией, в которой мы можем быть уверены. Ядерные бомбы могут не взорваться, а истребители могут упасть с неба, но мы всё равно сможем безопасно общаться, используя одноразовые блокноты. В этом есть определённый оптимизм.
Квантовые вычисления — это новый способ производить расчёты, который позволит человечеству выполнять вычисления, просто невозможные с использованием современных компьютеров. Возможность быстрого поиска сломает некоторые из современных алгоритмов шифрования. А лёгкая факторизация больших чисел сломает криптосистему RSA с любой длиной ключа.Именно поэтому криптографы сейчас усиленно разрабатывают и анализируют «квантово-устойчивые» алгоритмы с открытым ключом. В настоящее время квантовые вычисления пока не готовы для нормальной оценки: что безопасно, а что нет. Но если предположить, что инопланетяне разработали технологию в полном объёме, то квантовые вычисления — не конец света для криптографии. Для симметричной криптографии квантово-устойчивость обеспечить элементарно, а сейчас мы ищем квантово-стойкие алгоритмы шифрования с открытым ключом. Если криптография с открытым ключом окажется временной аномалией, которая существует благодаря пробелам в наших математических знаниях и вычислительных способностях, мы всё равно выживем. И если какая-то немыслимая инопланетная технология сломает всю криптографию, у нас останется секретность, основанная на теории информации, пусть и со значительными потерями возможностей.
По сути, криптография опирается на математический выверт, что некоторые вещи легче сделать, чем отменить. Как легче разбить тарелку, чем склеить её обратно, также гораздо проще умножить два простых числа, чем разложить результат обратно. Асимметрии такого рода — односторонние функции и односторонние функции с потайным входом — лежат в основе всей криптографии.
Чтобы зашифровать сообщение, мы комбинируем его с ключом для формирования шифротекста. Без ключа обратить процесс сложнее. Не просто чуть сложнее, а астрономически сложнее. Современные алгоритмы шифрования настолько быстры, что зашифруют весь ваш жёсткий диск без особых подтормаживаний, а взлом шифра продолжится до тепловой смерти Вселенной.
С симметричной криптографией, используемой для шифрования сообщений, файлов и дисков, этот дисбаланс экспоненциален и усиливается по мере увеличения ключей. Добавление одного бита ключа увеличивает сложность шифрования менее чем на процент (грубо говоря), но удваивает сложность взлома. Таким образом, 256-битный ключ кажется лишь вдвое сложне, чем 128-битный, но (с нашими текущими знаниями математики) его в 340 282 366 920 938 463 463 374 607 431 768 211 456 раз сложнее сломать.
Шифрование с открытым ключом (используемое главным образом для обмена ключами) и цифровые подписи более сложны. Поскольку они полагаются на сложные математические проблемы, такие как факторизация, то существует больше разных трюков, чтобы их обратить. Таким образом, здесь вы увидите ключи длиной 2048 бит для RSA и 384 бита для алгоритмов, основанных на эллиптических кривых. Но опять же, взлом шифров с этими ключами выходит за пределы текущих возможностей человечества.
Поведение односторонних функций основано на наших математических знаниях. Когда вы слышите о криптографе, «ломающем» алгоритм, значит, он нашёл новый трюк, который упрощает реверсирование. Криптографы всё время находят новые трюки, поэтому мы склонны использовать ключи длиннее, чем строго необходимо. Это верно как для симметричных алгоритмов, так и для алгоритмов с открытым ключом: мы пытаемся гарантировать их надёжность в будущем.
Квантовые компьютеры обещают изменить многое из этого. По своей природе они хорошо приспособлены к вычислениям, которые необходимы для обращения этих односторонних функций. Для симметричной криптографии это не так уж плохо. Алгоритм Гровера показывает, что квантовый компьютер ускоряет атаки настолько, что эффективная длина ключа уменьшается вдвое. То есть 256-битный ключ так же сложен для квантового компьютера, как 128-битный ключ для обычного компьютера: оба они безопасны в обозримом будущем.
Для криптографии с открытым ключом результаты страшнее. Алгоритм Шора легко ломает все популярные алгоритмы с открытым ключом, основанные как на факторизации, так и на дискретном логарифмировании. Удвоение длины ключа увеличивает сложность взлома в восемь раз. Этого недостаточно для устойчивого развития.
По поводу двух последних абзацев есть много оговорок, главная из которых заключается в том, что квантовые компьютеры, способные делать что-либо подобное, в настоящее время не существуют, и никто не знает, когда мы сможем построить такой — и сможем ли вообще. Мы также не знаем, какие практические трудности возникнут, когда мы попытаемся реализовать алгоритмы Гровера или Шора на чём-нибудь кроме ключей игрушечного размера (механизм коррекции ошибок на квантовом компьютере легко может стать непреодолимой проблемой). С другой стороны, мы не знаем, какие ещё методы будут обнаружены, как только люди начнут работать с настоящими квантовыми компьютерами. Я ставлю на то, что мы преодолеем инженерные проблемы, и что будет много достижений и новых методов, но понадобится время, чтобы их изобрести. Так же, как нам потребовались десятилетия, чтобы сконструировать карманные суперкомпьютеры, потребуются десятилетия, чтобы проработать все инженерные проблемы, необходимые для создания достаточно мощных квантовых компьютеров.
В краткосрочной перспективе криптографы прилагают значительные усилия для разработки и анализа квантово-устойчивых алгоритмов. Наверное, они останутся в безопасности на протяжении десятилетий. Процесс наверняка будет идти медленно, потому что хороший криптоанализ требует времени. К счастью, у нас есть время. Реальные квантовые вычисления на практике как будто всегда «в десяти годах в будущем». Другими словами, ни у кого нет ни малейшего представления.
Но всегда есть вероятность, что алгоритмы взломают инопланетяне с лучшими квантовыми технологиями. Я меньше беспокоюсь о симметричной криптографии, где алгоритм Гровера — по сути максимальный предел возможности квантовых вычислений. А вот алгоритмы с открытым ключом, основанные на теории чисел, кажутся более хрупкими. Вполне возможно, что квантовые компьютеры когда-нибудь сломают их все — даже те, которые сегодня считаются квантово-устойчивыми.
Если это произойдёт, мы останемся в мире без криптографии с открытым ключом. Это станет огромным ударом по безопасности и сломает многие системы, но мы сможем адаптироваться. В 1980-х годах Kerberos была полностью симметричной системой аутентификации и шифрования. И сейчас стандарт сотовой связи GSM выполняет как аутентификацию, так и распределение ключей — в большом масштабе — только с симметричной криптографией. Да, эти системы имеют централизованные точки доверия и отказа, но можно разработать другие системы, которые используют как секретное разделение, так и секретное совместное использование, чтобы свести к минимуму этот риск. (Представьте, что пара участников связи получает часть ключа сеанса от каждого из пяти различных серверов ключей). Повсеместное распространение коммуникаций облегчает ситуацию. Мы можем использовать внеполосные протоколы: например, ваш телефон поможет сгенерировать ключ для компьютера. Для дополнительной безопасности можно использовать личную регистрацию: возможно, в магазине, где вы покупаете смартфон или регистрируете интернет-сервис. Развитие аппаратного обеспечения тоже поможет защитить ключи в этом мире. Я ничего не пытаюсь изобрести, только говорю, что что есть много возможностей. Мы знаем, что криптография основана на доверии, и у нас гораздо больше методов управления доверием, чем в первые годы существования интернета. Некоторые важные технологии, такие как прямая секретность, станут гораздо сложнее, но пока симметричная криптография работает, у нас сохранится защита.
Это странное будущее. Возможно, вся идея криптографии на теории чисел, как современные системы с открытым ключом — это временный феномен, существующий благодаря пробелам в модели вычислений. Теперь, когда модель расширилась и включила в себя квантовые вычисления, мы можем оказаться там, где были в конце 1970-х и начале 1980-х: симметричная криптография, криптография на основе кодов, подписи Меркла. Это будет забавно и иронично.
Да, я знаю, что распределение квантовых ключей является потенциальной заменой криптографии с открытым ключом. Но давайте честно: кто-нибудь вообще верит, что система, требующая специализированного коммуникационного оборудования и кабелей, будет использоваться для чего-либо, кроме нишевых приложений? Будущее — за мобильными, постоянно включенными вычислительными устройствами. Все системы безопасности для них будут только программными.
Есть ещё один сценарий будущего, не говоря о квантовых компьютеров. В основе односторонних функций лежат несколько математических теорий, которые ещё не доказаны. Это одна из открытых проблем в компьютерной науке. Так же, как умный криптограф может найти новый трюк, который облегчает взлом определённого алгоритма, мы можем представить себе инопланетян с достаточной математической теорией, чтобы сломать все алгоритмы шифрования. Для нас сегодня это просто смешно. Криптография с открытым ключом — это теория чисел, потенциально уязвимая для математически более грамотных пришельцев. Симметричная криптография настолько нелинейно сложна, а длина ключа так легко увеличивается, что будущее сложно вообразить. Представьте вариант AES с 512-битным блоком и размером ключа, и шифрованием в 128 раундов. Если только не придумать принципиально новую математику, такое шифрование будет безопасно до тех пор, пока компьютеры не сделают из чего-то другого, кроме материи, в каком-нибудь другом измерении.
Но если случится невообразимое, то останется криптография, основанная исключительно на теории информации: одноразовые блокноты и их варианты. Это будет огромный удар по безопасности. Одноразовые блокноты могут быть теоретически безопасными, но в практическом плане они непригодны для чего-то, кроме специализированных нишевых приложений. Сегодня только психи пытаются строить системы общего пользования на основе одноразовых блокнотов — и криптографы смеются над ними, потому что они заменяют проблемы разработки алгоритмов (лёгкие) проблемами управления ключами и проблемами физической безопасности (что намного, намного сложнее). Возможно, в нашем фантастическом будущем, охваченном пришельцами, у нас останется только такой выход.
Против этих богоподобных пришельцев криптография останется единственной технологией, в которой мы можем быть уверены. Ядерные бомбы могут не взорваться, а истребители могут упасть с неба, но мы всё равно сможем безопасно общаться, используя одноразовые блокноты. В этом есть определённый оптимизм.
