Квантово-безопасная криптография
Криптотехнологии 1970-х годов пока еще не по зубам квантовым компьютерам
Вадим Любашевский,
PhD, IBM Research — Цюрих
«Коммерсантъ Наука» №6, март 2020
Создание квантовых компьютеров откроет принципиально новые возможности для человечества, но при этом существующие методы защиты информации утратят свою эффективность. Несмотря на то что пока квантовые компьютеры только выходят за пределы лабораторий, потребность в использовании квантово-безопасной, или, как ее еще называют, постквантовой криптографии есть уже сегодня.
Классическая криптография
Криптография изучает методы защиты конфиденциальности и целостности информации, а также процедуры проверки подлинности (аутентификации). Классическая криптография опирается на математические алгоритмы. Данные, которые пользователи передают по электронной почте, через облачные сервисы или мессенджеры, защищены тем или иным криптографическим протоколом. Каждый из этих протоколов включает в себя набор алгоритмов шифрования, то есть свод правил, определяющих, как именно будет преобразована информация.
Алгоритмы шифрования для данных в цифровом виде можно разделить на два основных типа: симметричные (например, AES) и асимметричные (самый распространенный — RSA). При симметричном шифровании стороны, обменивающиеся данными, используют один и тот же секретный ключ для шифрования и расшифровки данных. Этот ключ не известен третьей стороне, соответственно, она не имеет доступа к данным. Симметричные алгоритмы обычно используются для таких задач, как шифрование больших баз данных, файловых систем и хранилищ.
Асимметричные алгоритмы предполагают использование двух ключей — открытого и закрытого. Эти ключи связаны между собой математическими зависимостями. Для шифрования данных используется открытый ключ, а для их дешифровки — закрытый ключ из той же пары. Такая разновидность асимметричных алгоритмов называется алгоритмами с открытым ключом.
При симметричном шифровании стороны должны иметь общий закрытый ключ еще до начала обмена данными, а при асимметричном — начинают обмен без общей секретной информации: здесь одна сторона (получатель) знает оба ключа и передает второй (отправителю) только открытый ключ.
Многие криптографические протоколы являются гибридными. Начиная обмен информацией, стороны используют алгоритмы с открытым ключом для передачи одной строки, а затем переходят на гораздо более быстрые симметричные алгоритмы, где эта общая строка выступает в качестве секретного ключа.
Квантовая и постквантовая криптография
Помимо классической криптографии, основанной на математических алгоритмах, существует квантовая криптография. В ней ключ шифрования передается посредством элементарных частиц света — фотонов. Любой прибор, с помощью которого третья сторона попытается перехватить данные, неизбежно повлияет на состояние фотона, и ключ будет испорчен. Передавать фотоны можно с помощью выделенных оптоволоконных линий, на обоих концах такой линии потребуются специальные шифровальные устройства. Недостаток квантовой криптографии в том, что она требует больших затрат на инфраструктуру. При этом пока ключи удается передать только на очень ограниченное расстояние (50–100 км), скорость их генерации довольно низка, а на передачу фотонов влияет масса внешних факторов.
Постквантовая (квантово-безопасная) криптография, как и классическая, основана на решении математических задач. Однако новые алгоритмы шифрования должны быть иными, чтобы их не могли решить за приемлемое время не только обычные, но и квантовые компьютеры.
Криптография в эпоху квантовых компьютеров
Классическая криптография на сегодня надежно обеспечивает целостность и конфиденциальность данных. Даже мощному суперкомпьютеру понадобятся, пожалуй, сотни, а то и тысячи лет, чтобы решить сложные математические задачи, на которых она базируется. Но с появлением полномасштабного квантового компьютера аналогичную задачу можно будет решить за несколько дней или даже часов. Об этом свидетельствуют результаты исследования, которое провел американский ученый Питер Шор в Массачусетском технологическом институте еще в середине 90-х годов ХХ века.
Квантовые алгоритмы Шора и Гровера
В 1994 году Питер Шор предложил эффективный алгоритм факторизации, то есть разложения числа на простые множители для квантового компьютера. Спустя семь лет работоспособность этого алгоритма продемонстрировала группа специалистов IBM на числах, которые уже тогда могли разложить на множители при помощи классических компьютеров. Используя алгоритм Шора, квантовые компьютеры смогут взломать системы, основанные на алгоритмах с открытым ключом, так что использование таких алгоритмов фактически потеряет смысл.
В 1996 году американский математик Лов Гровер предложил другой квантовый алгоритм, основанный на методе перебора чисел. Этот алгоритм квантовые компьютеры смогут использовать для взлома систем симметричного шифрования. Чтобы сохранить текущий уровень безопасности, потребуется удвоить размер ключей.
Появление квантовых вычислений неизбежно приведет к изменениям в методах шифрования. В противном случае практически все существующие системы будут достаточно быстро взломаны. При этом появление квантовых компьютеров по-разному повлияет на безопасность классических криптографических алгоритмов: в алгоритмах с открытым ключом защита исчезнет полностью, а в симметричных алгоритмах ее эффективность снизится вдвое.
Идея о том, что популярные сегодня алгоритмы шифрования перестанут защищать данные, может прозвучать угрожающе. Но на самом деле алгоритмы, которые в первую очередь нужно исправить, — это цифровые подписи и шифрование с открытым ключом. После исправления этих алгоритмов все самые важные протоколы можно будет сделать квантово-безопасными. Наступит эпоха так называемой постквантовой криптографии.
Действовать на опережение
Разработку квантовых компьютеров ведут исследовательские группы со всего мира, но пока речь идет только о лабораторных образцах с весьма ограниченной мощностью и функциональностью. Может показаться, что внедрять квантово-безопасную криптографию еще рано, но на самом деле это не так.
Уже сегодня компании и пользователи накапливают и хранят данные, которые будут представлять ценность и через пять, десять и даже тридцать лет. Если не позаботиться об их защите сегодня, грядущие успехи в квантовых вычислениях сделают подобную информацию легкодоступной для третьих лиц. Нельзя исключать, что заинтересованные лица могут перехватить информацию сейчас, а расшифровать позднее, когда появится техническая возможность.
Кроме того, нужно учитывать и тот факт, что быстро обновить имеющуюся инфраструктуру будет затруднительно. Инвестируя в создание сетей и хранилищ критически значимых данных, разумно уже сейчас предусмотреть вероятное появление квантовых компьютеров в перспективе. Ведь инфраструктура, которую организация создает сегодня, вероятнее всего будет использоваться еще не одно десятилетие.
Когда будут взломаны существующие системы?
Большинство ИТ-специалистов уверено, что квантовые компьютеры рано или поздно выйдут на рынок. Никто точно не знает, когда именно это произойдет. Предположительно, для создания полнофункциональной квантовой вычислительной машины разработчикам потребуется еще от 10 до 30 лет.
Хорошая новость состоит в том, что элементы постквантовой криптографии уже существуют. Более того, они успешно работают на классических компьютерах. Таким образом, можно уже сейчас внедрять квантово-безопасные алгоритмы и тем самым защитить критически важные данные на десятилетия вперед. Понятно, что переход к квантово-безопасной криптографии целесообразен в тех случаях, когда ценность защищаемой информации выше, чем затраты на ее защиту.
Криптография на основе решеток — совокупность сверхнадежных протоколов безопасности, разработанных для защиты данных от возможных атак хакеров в будущем, когда они смогут прибегнуть к вычислительным возможностям квантовых компьютеров. Используя этот метод криптографии, можно скрывать данные в многомерной решетке. Как считают ученые, восстановление таких данных без знания секретного обходного пути невозможно даже при помощи квантовых вычислительных систем
Решетчатая криптография использует многомерные геометрические структуры для сокрытия информации. Решетка — это бесконечная сетка точек. Увеличивая размерность решетки, криптографы могут создавать настолько сложные задачи, что многие верят, что ничто не сможет их решить — даже универсальные отказоустойчивые квантовые компьютеры.
Алгоритмы постквантового мира
Главным успехом в сфере квантово-безопасной криптографии стало создание практичных алгоритмов шифрования на основе теории решеток. Эти алгоритмы базируются на линейной алгебре, в частности, включают задачу нахождения кратчайшего вектора.
Оказалось, что методы шифрования с открытым ключом и цифровой подписью, которые можно считать безопасными в мире квантовых компьютеров, были созданы еще в конце 1970-х годов, то есть раньше, чем исследователи задумались о возможных угрозах квантовых вычислений для криптографии. Однако предложенные в те годы алгоритмы были неудобны для практического применения, так как размер передаваемых ключей достигал нескольких мегабайт.
Благодаря исследованиям, проведенным международными консорциумами в последнее десятилетие, эту проблему удалось решить. На основе решеток были созданы асимметричные схемы шифрования и цифровой подписи с размером ключа, как у RSA (популярный сейчас алгоритм с открытым ключом), при этом работает новый алгоритм даже быстрее, чем классический. Таким образом, было доказано, что криптография на решетках позволяет создавать алгоритмы, которые прежде считались неосуществимыми.
В 2016 году Национальный институт стандартов и технологий США (NIST) инициировал проект по оценке и стандартизации одного или нескольких квантово-устойчивых алгоритмов с открытым ключом. Сбор заявок продолжался вплоть до 2018 года. После первого отборочного раунда участие в конкурсе продолжили 69 кандидатов, после второго — 26. Вероятно, уже в 2020 году состоится третий раунд, после чего начнется этап разработки стандартов. Планируется, что первый проект квантово-безопасного стандарта NIST представит между 2022 и 2024 годами.
Исследования в области криптографии на решетках
Один из международных консорциумов, развивающих криптографию на основе решеток, включает компанию IBM, Высшую нормальную школу Лиона (Франция), Рурский университет в Бохуме (Германия), Центр математики и информатики в Амстердаме и Университет Неймегена (оба — Нидерланды).
Консорциум предложил два алгоритма — на основе механизма инкапсуляции защищенного ключа Kyber и на основе концепции защищенной цифровой подписи Dilithium. Kyber и Dilithium входят в состав криптографического набора для алгебраических решеток под названием CRYSTALS. Этот набор в виде открытого исходного кода был передан в NIST для стандартизации.
Одним из фаворитов конкурса считаются алгоритмы на основе решеток, поскольку они имеют меньший размер и обеспечивают высокую производительность шифрования. Однако специалисты NIST полагают, что предпочтительнее стандартизировать несколько алгоритмов. Это позволит подстраховаться на случай, если квантовые компьютеры будущего все-таки смогут преодолеть сложность задач, содержащихся в одном из выбранных алгоритмов.
Кроме того, независимые участники (IBM является одним из них) поддерживают ряд проектов, которые развивают квантово-безопасные алгоритмы с открытым исходным кодом, к примеру, проект OpenQuantumSafe.org.
Страховка на случай квантового прорыва
Учитывая текущие успехи исследовательских групп в области квантовых вычислений, коммерческие компании и правительства стран должны задуматься о ценности своих данных. Для защиты информации, которая должна остаться конфиденциальной через 10–30 лет, внедрять квантово-безопасную криптографию рекомендуется уже сегодня, не дожидаясь стандартизации.
Важно понимать, что перейти на постквантовые алгоритмы немедленно после принятия стандартов не удастся. Понадобится большая подготовительная работа. Новые ключи могут иметь несколько большие размеры, и инфраструктура должна быть рассчитана для их передачи без потери привычной скорости коммуникации.
В то же время многие предложения, поданные в NIST, — это лишь незначительные изменения хорошо изученных задач. Можно выбрать одно или несколько из них и использовать в тандеме с текущей криптографией. Такой модульный переход к квантово-безопасной криптографии выглядит наилучшим решением, так как он гарантирует текущую безопасность данных, даже в том случае, если в постквантовых алгоритмах обнаружатся «болезни молодости», связанные с их внедрением в отсутствие универсальных квантовых компьютеров. При этом, внедрив элементы квантово-безопасной криптографии сейчас, собственники данных застрахуют себя на случай грядущего прорыва в квантовых вычислениях.
Сроки хранения конфиденциальных данных
- Записи налогового учета, согласно требованиям закона Сарбейнза — Оксли, — 7–10 лет в большинстве стран
- Срок засекречивания сведений, составляющих гостайну в России, — до 30 лет
- Документы по личному составу в Российской Федерации — не менее 50 лет
- Хранение неактивных банковских счетов, списков всех уничтоженных записей в США — бессрочно
- Чтобы обезопасить интернет-коммуникации, специалисты в области криптографии работают над созданием методов шифрования, которые не смогут обойти квантовые компьютеры будущего. Это значит, что к моменту распространения квантовых компьютеров у человечества в руках будут надежные способы защиты целостности и конфиденциальности данных, а также новые средства и процедуры аутентификации пользователей.
Фото: AP / Seth Wenig