Суета заранее, или Постквантовые тайны криптографии

Компетентные инстанции по обе стороны Атлантики, занимающиеся установлением всеобщих технических стандартов, в настоящее время очень заметно озаботились проблемами так называемой квантово-безопасной криптографии. Под этим общим термином (в другой версии он же звучит как постквантовая криптография) в области защиты информации принято понимать широкий круг всевозможных алгоритмов, протоколов и устройств для коммуникаций, способных противостоять угрозам со стороны квантовых компьютеров. Если знать, что настоящий квантовый компьютер – это пока еще техника сугубо гипотетическая, а реальные задачи по быстрому взлому шифров такие вычислители смогут решать (согласно прикидкам авторитетных экспертов) лишь только лет эдак через 20-30, а может даже 40, то вполне естественно и удивиться. Почему вдруг именно сейчас такая суета?

У высоких инстанций, конечно же, всегда есть готовые ответы на подобные вопросы. Так что для поверхностных оценок несведущей публики представленные объяснения выглядят не только разумно, но и убедительно. Для специалистов, однако, картина куда менее ясна. Чем лучше эти люди понимают суть данного предмета, тем больше они видят неувязок и мутных умолчаний в предлагаемых объяснениях. Ну а для того, чтобы стало понятно, отчего все это очень важно и интересно даже для неспециалистов, надо чуть подробнее разъяснить, что же вообще происходит.

С 19 по 21 сентября 2016 года в городе Торонто, Канада, проходил очередной международный симпозиум под названием «Семинар ETSI/IQC по квантово-безопасной криптографии». Чтобы подчеркнуть значимость данного мероприятия, надо пояснить, что ETSI – это Европейский институт телекоммуникационных стандартов (то есть отраслевой аналог американского NIST, главного органа стандартизации в США). А IQC, соответственно, это Институт квантовых вычислений при Университете Ватерлоо, то есть один из главных в мире научно-исследовательских центров, не первый десяток лет занимающихся проблемами криптографии в контексте квантовых компьютеров.

При столь солидных организаторах мероприятия уже не так удивительно, что среди участников симпозиума отмечены не только ведущие ученые академических структур и индустрии, но и важные люди из руководства транснациональных корпораций и правительственных ведомств Европы, Северной Америки, Японии, Китая и Южной Кореи. А кроме того, еще и большие начальники спецслужб, занимающихся защитой информации в таких государствах, как Великобритания, Канада и Германия. И все эти сильно занятые люди, еще раз напомним, собрались ныне в Торонто для обсуждения того, каким образом пора всерьез укреплять криптографию для противостояния технологиям, которые, даже по самым оптимистичным оценкам, станут представлять реальную угрозу лет так лишь через двадцать самое меньшее. А скорее всего, и того позже.

Если же принять во внимание тот факт, что без какой-либо взаимосвязи с этим мероприятием, но практически синхронно – в августе 2016-го – НИСТ США официально объявил о запуске своей собственной крупномасштабной программы по переходу от традиционной криптографии к криптографии «постквантовой», то вывод будет вполне очевидным.

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

В США первый официальный сигнал о том, что с укреплением и модернизацией традиционной криптографии надо срочно что-то делать, был отмечен год назад – в августе 2015 года. Именно тогда Агентство национальной безопасности, как главный авторитет государства в области шифров, опубликовало заявление о существенных переменах в своей базовой политике – в связи с необходимостью разработки новых стандартов для постквантовой криптографии, или, кратко, PQC (National Security Agency, Cryptography today, August 2015).

Как и многие из других сторон, участвующих в этом процессе, АНБ заявило, что считает настоящий момент наиболее подходящим временем для того, чтобы вплотную заняться разработкой новых протоколов для криптографии с открытым ключом. Такой криптографии, где стойкость также будет зависеть от трудных задач математики, но только теперь это должны быть иные трудные задачи – не поддающиеся эффективному решению с помощью квантовых компьютеров.

Здесь можно пояснить, что для всех широко применяемых ныне алгоритмов и протоколов криптографии с открытым ключом (построенных на базе схем RSA и ЕСС, то есть криптографии на эллиптических кривых) стойкость выстроена на основе двух трудных в решении задач математики – разложения большого целого числа на пару простых сомножителей (что именуют факторизацией) и вычисления дискретного логарифма. Для обычных – классических – компьютеров обе задачи решить за приемлемое время считается невозможным. Или, если выражаться аккуратнее, никто и нигде таких методов пока не продемонстрировал.

Но случилось так, что, когда в начале 1990-х ученые вплотную занялись теорией создания компьютеров существенно новых, «квантовых» (работающих на основе принципов квантовой механики), очень быстро обнаружились квантовые методы для быстрого решения именно этих двух задач криптографии – факторизации и дискретного логарифмирования... То есть большая проблема с надежностью засекречивания коммуникаций обозначилась уже весьма давно, более 20 лет назад.

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

Так, во всяком случае, было принято считать вплоть до начала нынешней суеты с неотложными шагами по разработке и внедрению постквантовой криптографии. Причем — дополнительно подчеркнем — эти шаги предприняты в таких условиях, когда мировая криптографическая наука все еще не нашла тех самых трудных математических задач, которые окажутся гарантированно не по зубам для компьютеров квантовых.

Все изложенное выше – это, так сказать, общеизвестный для криптографов базовый контекст, в рамках которого у специалистов сразу же возникает естественный вопрос. Что такого очень серьезного могло произойти в самые последние годы, из-за чего столь энергично вдруг завертелись шестеренки в «машине перемен»?

Естественно, в качестве возможного ответа первой же приходит идея о том, что кто-то где-то втайне от остальных таки построил настоящий квантовый компьютер. И коль скоро наиболее заметную и решительную инициативу по скорейшему переходу к новой, квантово-безопасной криптографии демонстрирует АНБ США, несложно догадаться, какое именно государство приходит тут на ум в первую очередь. Обладающее не только самым огромным бюджетом для подобных инициатив, но и всеми нужными научно-техническими возможностями.

Однако даже если гипотеза эта и выглядит для кого-то правдоподобной, принять её в качестве рабочей сообщество специалистов не может. Хотя АНБ, спору нет, организация в высшей степени засекреченная и умеющая втайне применять наиболее мощные на планете суперкомпьютеры, имеется также и еще кое-какая достоверная информация. Благодаря сливам сверхсекретных документов от Сноудена точно известно, что в 2013 году квантового компьютера у АНБ не было и близко. Даже интерес к этой теме был лишь минимальный.

Как и все профессионалы, американская спецслужба тоже проявляет некоторое внимание к данному направлению. Однако собственные затраты на квантовые вычисления в бюджете АНБ занимают лишь небольшую долю в довольно скромной общей сумме (несколько десятков миллионов долларов), выделяемой в целом на перспективные исследования. Для сравнения: согласно экспертным прикидкам, под создание настоящего квантового компьютера, способного решать реальные задачи, потребуется сумма не менее миллиарда долларов – при условии, что уже будет в наличии подходящая технология. Но именно её-то пока что у ученых и нет...

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

Наиболее содержательной, пожалуй, обзорной работой, обобщающей и сопоставляющей все подобные гипотезы и предположения без итогового ответа, можно считать известную статью «Головоломка, окутанная загадкой», подготовленную весьма известными криптографами Нилом Коблицем и Альфредом Менезесом в конце 2015 года (Neal Koblitz and Alfred J. Menezes, “A Riddle Wrapped in an Enigma”).

Дабы стало понятнее, почему имеет смысл сосредоточить внимание на фактах именно из этой аналитической работы, следует вкратце прояснить два момента. Первый: какое место занимают ее авторы в открытой академической криптографии; и второй: насколько тесно и загадочно их собственные научные разработки переплетены с нынешними инициативами АНБ США по ускоренному переводу используемых криптографических алгоритмов на другие рельсы.

Американский математик и криптограф Нил Коблиц является (наряду с Виктором Миллером) одним из тех двух человек, которые в 1985 году одновременно и независимо друг от друга придумали новую криптосхему с открытым ключом, получившую название ECC (это, напомним, сокращение от Elliptic Curve Cryptography, то есть «криптография на эллиптических кривых»).

Здесь, ясное дело, совсем не место для углубления в технические детали этого метода и в его отличия от криптосхемы RSA, появившейся раньше и получившей наибольшее коммерческое распространение. Но следует подчеркнуть, что ECC с точки зрения практической эксплуатации обладает явными преимуществами, поскольку та же самая теоретическая стойкость алгоритма обеспечивается при намного меньшей длине ключа (для сравнения: 256-битные операции ECC эквивалентны работе с модулем длиной 3072 бита в RSA). А это, в свою очередь, сильно облегчает вычисления и существенно повышает быстродействие системы.

Второй важный момент (практически наверняка связанный с первым) заключается в том, что крайне скрытное АНБ США в своих криптографических предпочтениях с самого начала стало склоняться в пользу ECC. В первые годы и десятилетия это доносилось до академических и промышленных кругов лишь в неявном виде (когда, например, в 1997 году официальный сотрудник АНБ Джерри Солинас впервые выступил на открытой конференции Crypto – с докладом об их модификации известной схемы Коблица).

Ну а затем это было сделано отчетливо задокументированным образом, когда в 2005 году АНБ США опубликовало свои рекомендации по криптоалгоритмам в виде так называемого Suite B ("Набора Б") – комплекса открыто опубликованных шифров для сокрытия секретной и сверхсекретной информации в национальных системах связи. Все базовые алгоритмы и протоколы этого «набора» были выстроены на основе ECC, а для RSA отводилась вспомогательная роль «первого поколения», нужного лишь для плавного перехода к новой, более эффективной криптографии на эллиптических кривых...

На этом месте самое время вспомнить про Альфреда Менезеса, второго соавтора интересующей нас статьи про «Головоломку, окутанную загадкой». Ибо канадский математик-криптограф Менезес всю свою научную жизнь, начиная с середины 1980-х, работает в университете Ватерлоо – одном из заметнейших центров открытой академической криптографии. Именно здесь в 1980-е годы трое профессоров университета создали компанию Certicom, занявшуюся разработкой и коммерческим продвижением криптографии на эллиптических кривых.

Соответственно, Альфред Менезес со временем стал не только видным разработчиком Certicom и автором нескольких авторитетных книг по криптосхемам ECC, но и соавтором нескольких важных патентов, описывающих ECC. Ну а АНБ США, в свою очередь, когда запускало весь свой проект под названием Suite B, предварительно закупило у Certicom большой – на двадцать с лишним штук – пакет патентов, накрывающих «эллиптическую» криптографию.

Короче говоря, вся эта преамбула понадобилась для того, чтобы пояснить, почему Коблиц и Менезес – это именно те люди открытого сообщества математиков и компьютерщиков, которые по естественным причинам считали себя хорошо осведомленными о текущих делах и планах АНБ в области криптографической защиты информации. Однако и для них инициатива АНБ с резкой сменой курса на постквантовые алгоритмы стала полнейшей неожиданностью.

Особо, так сказать, задетыми из-за этой смены курса Коблиц и Менезес оказались по той причине, что они сразу же заметили и сопутствующие перемены в алгоритмах «Набора Б». Ибо тем же летом 2015 года АНБ по-тихому – абсолютно никому не разъясняя причин – убрало из своего комплекта ECC-алгоритм «P-256», одновременно оставив там его RSA-эквивалент с 3072-битным модулем. И более того, в сопутствующих заявлениях АНБ вполне отчетливо было сказано, что всем сторонам, внедряющим алгоритмы из Suite B, ныне уже нет никакого смысла переходить на ECC, а лучше просто увеличить длины ключей RSA и подождать, когда появятся новые постквантовые шифры...

Коблиц и Менезес имеют все основания считать себя людьми компетентными в области криптографии на эллиптических кривых, но при этом они абсолютно ничего не слышали о новых методах взлома, скомпрометировавших «их» криптосхему. Так что все происходящее вокруг ECC чрезвычайно удивило математиков и заставило предпринять дополнительное расследование. Однако и оно не дало ничего.

Имея давние и тесные контакты с индустрией, ученые знают, что обычно все крупные корпорации, делающие криптографические задания и оборудование для правительства США, всегда получают некое заблаговременное предупреждение о смене планов. Но в данном случае ничего такого не было.

Еще более неожиданным оказалось то, что и к людям из НИСТ США, отвечающим за открытые криптографические стандарты государства, никто из АНБ по этому поводу не обращался. Ну и наконец (поскольку Менезес имеет связи и там), даже собственные математики-криптографы АНБ из Управления защиты информации (IAD) были крайне удивлены тем сюрпризом, который преподнесло им руководство со своей постквантовой инициативой...

Формулируя все собранные авторами свидетельства чуть иначе, вполне можно сделать вывод, что те весьма влиятельные люди, которые в недрах АНБ инициировали публичную смену курса, делали это без какой-либо обратной связи и консультаций не только со специалистами промышленности и академии, но даже и со своими собственными экспертами. Именно к такому выводу, собственно, приходят в своих анализах и Коблиц с Менезесом. И с готовностью признают, что в итоге никто, получается, толком не понимает техническую подоплеку всего здесь происходящего.

Дабы столь странная и загадочная картина стала хотя бы отчасти более понятной, самое время отметить, что аналитическая статья Коблица и Менезеса выстроена по канонам пьес классического театра. То есть всему в ней происходящему присущи единство места, времени и действия. Место – США и Канада, время – сейчас, действие – обозначенная криптографическая суета.

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

И хотя именно об этих вещах у Коблица и Менезеса нет ни слова, для адекватного восприятия интриги очень желательно знать, что на самом деле принципы криптографии с открытым ключом были открыты практически одновременно – в 1970-х годах – сразу в двух принципиально разных местах. Сначала, на несколько лет раньше, это сделали три секретных криптографа в стенах британской спецслужбы GCHQ, аналога и ближайшего партнера американского АНБ в задачах радиоэлектронной разведки. Но как это издавна заведено у шпионов, сделано все было в глубокой тайне и «только для себя».

Причем сразу же уместно отметить здесь и один тонкий нюанс. Открытие сделали не шпионы GCHQ, а математики подразделения CESG, отвечающего за национальные шифры и защиту правительственных систем связи Великобритании. С другой стороны, тесное взаимодействие между GCHQ и АНБ США происходит прежде всего по линиям совместной разведывательной деятельности. Иначе говоря, поскольку в АНБ также есть собственное управление IAD (Information Assurance Directorate), специализирующееся на разработке криптоалгоритмов и защите информации, для математиков этого подразделения открытие британских коллег стало полнейшей неожиданностью. А впервые узнали о нем они от своих сослуживцев-шпионов, тесно общающихся с англичанами...

Как бы там ни было, однако, когда те же самые по сути алгоритмы «несекретного шифрования» – на основе факторизации и дискретного логарифмирования – независимо от спецслужб вскоре изобрели в США исследователи открытого сообщества (Диффи, Хеллман, Меркль, Райвест, Шамир, Адлеман), АНБ приложило гигантские усилия, чтобы запихать этого джинна обратно в бутылку.

Никак не раскрывая, что спецслужба уже имеет у себя эту математику, начальники АНБ просто пытались всячески помешать ученым в широкой публикации данной информации. Защитники национальной безопасности напирали на то, что стойкая криптография – это слишком серьезное оружие, а их новые алгоритмы шифрования с открытым ключом позволяют устраивать скрытые от контроля коммуникации кому угодно, даже людям и сторонам, никогда друг с другом не встречавшимся.

Как всем известно, абсолютно ничего с запретом на знания и с затыканием ртов ученым тогда у АНБ США не получилось. В результате же открытое научное сообщество очень на АНБ разозлилось. А кроме того, под давлением ученых и индустрии ведать разработкой и внедрением коммерческой криптографии в стране стала в итоге вовсе не шпионская спецслужба (как там ни старались), а гражданская структура, НИСТ США. И хотя история эта весьма давняя, ныне она вполне наглядно повторяется. Если, конечно, смотреть внимательно и обращать внимание на характерные детали.

Нынешний международный симпозиум ETSI/IQC по квантово-безопасной криптографии, с которого начинался данный рассказ, имеет сразу несколько примечательных особенностей. Во-первых, на нем весьма солидно – руководителями важных структур – были представлены спецслужбы Великобритании, Канады, Германии. Все эти национальные спецслужбы – аналоги американского АНБ. Однако от АНБ США в явном виде не упомянуто абсолютно никого. И это, конечно же, не случайность.

Имеется масса свидетельств как от лидеров бизнеса, так и непосредственно от начальников разведструктур, что после разоблачительных сливов от Эдварда Сноудена практически вся ИТ-индустрия США (не говоря уже о других странах) реагирует на деятельность АНБ в высшей степени отрицательно. Ибо в своей гиперактивности вокруг компрометации стойкой криптографии шпионы серьезнейшим образом подорвали доверие общества не только к флагманам американского ИТ-бизнеса, но даже и к НИСТ США (навязав им искусственно ослабленный алгоритм в качестве стандарта). Иначе говоря, на международных форумах, обсуждающих пути к усилению криптографии в свете новых угроз, для АНБ США сейчас благоразумнее просто не светиться.

Другая примечательная особенность происходящего заключается в том, что нынешний «рабочий семинар» в Торонто – уже далеко не первый, а четвертый по счету. Первый был в 2013 году в Париже, а второй – особенно для нас интересный – происходил осенью 2014-го в столице Канады, Оттаве. Интересным же данное мероприятие является по той причине, что там имел место в высшей степени необычный доклад от имени секретной британской спецслужбы GCHQ (P. Campbell, M. Groves, D. Shepherd, "Soliloquy: A Cautionary Tale"). Точнее говоря, доклад был не от шпионов, а от подразделения защиты информации CESG, причем сделал его лично Майкл Гроувс (Michael Groves), возглавляющий криптографические исследования в этой спецслужбе. Тут обязательно надо подчеркнуть, что людям из английских спецслужб совершенно не свойственно рассказывать о своих секретных разработках на открытых конференциях. Однако данный случай был воистину исключительным.

В своем докладе Гроувс не только рассказал, что британские криптографы уже давно, с начала 2000-х годов, занимаются разработкой квантово-безопасных алгоритмов, но и в подробностях описал одну из особо удачных, как казалось, схем такого рода – построенную в 2007 году на основе так называемых числовых циклических решеток. К сожалению, затем выяснилось, что данный криптоалгоритм – получивший от авторов имя Soliloquy – далеко не так силен, как предполагалось. В течение 2010-2013 годов для его эффективного взлома была придумана теоретическая атака с помощью квантового компьютера, а потому в итоге от алгоритма пришлось полностью отказаться.

При этом важно, что решение о полном отказе – а не об усилении-модернизации красивой конструкции – было в основном принято спецслужбой из-за очень мощной и сильно впечатлившей англичан атаки, разработанной в 2013 году группой исследователей открытого академического сообщества. В работе этих авторов (K. Eisentraeger, S. Hallgren, A. Kitaev, and F. Song. "A quantum algorithm for computing the unit group of an arbitrary degree number field". In STOC ACM, 2014) описывается существенно новая квантовая атака весьма общего типа, накрывающая, в частности, широкий круг «постквантовых» криптосхем, включая и никому неведомый в ту пору Soliloquy...

С одной стороны, эффект от этого «полуоткрытого» выступления большого криптографа английской спецслужбы оказался именно таким, каким, очевидно, и задумывался. Индустрия и академия, занимающиеся защитой информации, с готовностью приняли в качестве очень знающих консультантов людей из CESG (которые наглядно продемонстрировали не только свою «опережающую» компетентность, но и готовность делиться даже опытом неудач). На нынешнем форуме в Торонто, в частности, уже двум начальникам от CESG было доверено председательствовать на сессиях и модерировать дискуссии.

Но с другой стороны, тут же проявился и совсем иной эффект, обычно сопровождающий любое сотрудничество со спецслужбами. Имеются в виду, конечно же, всяческое напускание секретности и попытки заглушить даже уже опубликованные результаты исследований. История про выступление гранд-криптографа CESG на открытом симпозиуме чрезвычайно скупо освещалась в СМИ, а статью и слайды презентации про Soliloquy можно отыскать в Сети лишь тем, кто очень четко знает, что именно ищет (на сайте ETSI, где эксклюзивно лежат данные файлы, прямых ссылок к ним не обнаруживается).

Самое неприятное, однако, тут даже в ином. Если кто-либо интересующийся захочет ознакомиться с той самой статьей ученых открытого сообщества, которая сильно впечатлила английскую спецслужбу, то быстро выяснится, что и её отыскать не так-то просто. Данной статьи нет не только на сайте научных препринтов Arxiv.org, где уже давно наряду с физиками-математиками публикуются и компьютерщики-криптографы. Нет ее также и на специализированном сайте сугубо криптографических препринтов Eprint.iacr.org, принадлежащем IACR, или Международной ассоциации криптографических исследований. Причем каждый из авторов интересующей нас статьи имеет множество других публикаций и на том и на другом или даже на обоих этих сайтах – нет только лишь нужной работы.

Хуже того, если отправиться искать файл по личным веб-страницам исследователей на университетских сайтах, то и там поджидает засада. Наиболее известный из соавторов, Алексей Китаев, знаменит как суперзвезда на небосклоне квантовых вычислений, к криптографии имеет лишь сугубо касательное отношение, а ссылки на файлы своих публикаций вообще не накапливает — ни на веб-страницах Калтеха и Института теоретической физики Кавли в Калифорнии, где постоянно работает, ни где-либо еще.

Другой соавтор, Шон Холгрен, действительно известный именно как криптограф, подобно многим другим исследователям имел прежде обыкновение выкладывать на университетской веб-странице ссылки на свои публикации. Но вот именно на интересующей нас статье это дело вдруг прекратилось. Для всех предыдущих статей файлы имеются, а для нужной – лишь название. Для всех же последующих публикаций 2015-2016 гг. нет даже названий. Хотя в архивах препринтов такие работы обнаруживаются...

Действительно полноценный перечень всего, что было, есть и даже будет тут сделано (с подобающими ссылками на файлы), отыскивается лишь на сайте самого молодого из соавторов – по имени Фанг Сонг. Но, что существенно, не на его университетских веб-страницах, а на персональном веб-сайте FangSong.info. Причем даже тут обнаруживаются странные потери. Нужный нам PDF-файл с вариантом искомой статьи таки имеется, однако ссылки на примерно тот же файл, но с названиями типа «полная версия» и «Arxiv.org» оказываются битыми, зацикливая переход обратно на главную страницу. То есть файлы явно автором выкладывались, но и тут – как на сайте ArXiv – необъяснимо исчезли...

«Необъяснимыми» все пропажи такого рода (на самом деле подобных случаев довольно много) можно считать лишь при очень наивном и поверхностном взгляде на вещи. Чаще всего объяснение происходящему содержится уже в заголовках статей, где авторы – в соответствии с давно заведенными у ученых правилами – обязаны указывать источники финансирования и грантов, на деньги которых проведены исследования.

Конкретно же в нашем случае спонсором однозначно выдающейся статьи о новом методе квантово-криптографической атаки является – сюрприз! – Агентство национальной безопасности США. Ну а «кто за дэвушку платит, тот дэвушку и танцует», как известно. Понятно, что сами авторы исследования всегда заинтересованы в широком распространении своих результатов, однако у их спонсоров зачастую бывают прямо противоположные цели...

Единственным темным и действительно важным моментом, пока что оставшимся не освещенным во всей данной истории, является вот что. Какая может быть взаимосвязь между новым, очень эффективным (и весьма впечатлившим спецслужбы) алгоритмом для вскрытия всевозможных криптосхем с помощью гипотетического квантового компьютера в далеком будущем и нынешними поспешными шагами АНБ по изъятию из обращения криптографии на эллиптических кривых? Связь тут, как выясняется, имеется совершенно непосредственная. Но чтобы ее заметить, опять-таки надо не только соображать в криптографии, но еще и очень внимательно следить за происходящим.

Когда на рубеже 2014-2015 годов в открытом сообществе только-только стало известно о постквантовом алгоритме Soliloquy от британской спецслужбы, о его последующей компрометации и о параллельно изобретенной квантовой атаке, один из очень компетентных и хорошо осведомленных криптографов, Дэн Бернштейн, сделал интересное обобщение.

Сопоставив все известные на тот момент факты, Бернштейн выдвинул предположение, что на самом деле новый квантовый алгоритм от Холгрена, Фанг Сонга и компании указывает также путь и к существенно более мощным атакам с помощью традиционных классических компьютеров. Причем на основе известных, но весьма туманных комментариев англичан Бернштейн сделал вывод, что и в британской спецслужбе об этом знают – но предпочитают держать ото всех в секрете...

Ото всех или не ото всех — этого никто достоверно не знает, естественно. Но зато прекрасно известно, что было потом. Еще через несколько месяцев, в августе 2015-го, АНБ США вдруг сильно удивило весь криптографический мир своим резким отказом от криптографии ECC с относительно короткой длиной ключа. Единственными, кто тут вряд ли удивился, были, наверное, криптографы британской спецслужбы.

Ну а еще через полгода, в начале 2016-го, уже и в открытом криптографическом сообществе появились как минимум две независимые публикации от ученых-исследователей, которые в самых общих чертах подтвердили предположение Дэна Бернштейна (Ronald Cramer, Léo Ducas, Chris Peikert, Oded Regev. "Recovering Short Generators of Principal Ideals in Cyclotomic Rings". In Eurocrypt 2016; Jean-François Biasse and Fang Song, "Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields". In 27th ACM-SIAM Symposium on Discrete Algorithms).

Иначе говоря, теперь уже строго и для всех показано, что да, действительно, новые и вроде бы сугубо «квантовые» подходы к решению трудных криптографических задач на самом деле позволяют ощутимо снижать трудозатраты также и при взломе криптосхем с помощью компьютеров классических. Конкретно о компрометации схемы ECC пока нигде и ничего открыто не объявлено. Но это, похоже, уже лишь дело времени.

Дополнительное чтение

• О множестве других случаев с незаметным изъятием спецслужбами существенных фактов и знаний: «Выпиливание реальности».
• Об удивительной и отчасти мистической истории про одновременное открытие криптографии с открытым ключом в спецслужбах и в академических кругах: «Параллельные миры».
• О том, как спецслужбы с помощью грантов и стипендий контролируют разработки открытой академической криптографии: «Инженерия науки».