Постквантовая криптография и закат RSA — реальная угроза или мнимое будущее?

1. Начнём с основ: чуть-чуть о криптографии

Что такое криптография и для чего она вообще нужна? Скажем, Алиса и Боб хотят обменяться сообщением, да так, чтобы его содержание оставалось в секрете. Очевидно, что у каждой из сторон должен быть свой ключ. И на этом этапе можно выделить два подвида криптосистем.

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

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

Интересная многоходовочка… Ну а как она реализуется, спросит пытливый %username%? Все дело в так называемых односторонних функциях. Пусть есть функция $$. По известному аргументу $$ вычислить значение функции $$ проще, чем захватить Вестерос с тремя драконами и армией безупречных. Однако вычисление аргумента $$ по известному значению функции $$ является довольно-таки трудоемкой задачей.

Наиболее известными кандидатами в односторонние функции являются задача факторизации числа, которая состоит в разложении числа на простые множители, и задача дискретного логарифмирования, которая заключается в поиске неизвестного $$ по известным значениям $$ и $$, которые удовлетворяют: $$. Первая, например, применяется в широко известной криптосистеме RSA, а вторую можно встретить в схеме установления ключа Диффи-Хэллмана.

Однако с учетом стремительного, как полет дракона, роста производительности вычислительных устройств, возникает необходимость в увеличении длины ключа, ну а это может стать критическим фактором для устройств с ограниченной мощностью…Эх, было бы так здорово, появись такая структура, которая бы позволила сократить размер ключа при таком же уровне стойкости… И, к счастью, она существует! Название сему чуду – эллиптическая кривая.

2. А теперь посложнее: эллиптические кривые

Если ваше лицо приняло подобное Гарольду выражение, не спешите закрывать статью и убегать, издавая нервный смех. Эллиптические кривые — это просто! Для начала дадим определение. Эллиптическая кривая — это, прежде всего, женщина неособая кубическая кривая. Неособой ее называют, потому что ко всем ее точкам можно однозначно провести касательную. Ну раз это кривая кубическая, то и задаваться она должна уравнением третьей степени, которое в обобщенной форме Вейерштрасса выглядит следующим образом:

Наверняка многие сталкивались с формой Вейерштрасса, ее называют канонической для полей с характеристикой $$:

Дискриминант не должен быть равен нулю, иначе кривая уже не будет эллиптической, так как будут существовать точки перегиба, как на кривой $$ на рисунке справа.

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

Нельзя не упомянуть еще одну характеристику эллиптических кривых, которая (СПОЙЛЕР!) еще одарит читателей своим присутствием в статье. Речь идет о $$ инварианте, постоянной величине. Его вычисление для эллиптической кривой в форме Вейерштрасса тоже не обладает устрашающим воздействием на организм:$$

Свойства группы

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

• Замкнутость означает, что результат сложения элементов группы тоже является элементом группы. Переведем в термины эллиптической кривой: при сложении точек эллиптической кривой получается точка, принадлежащая этой же кривой.
  
  
  
  Как видно из рисунков сверху, геометрический смысл сложения точек на эллиптической кривой состоит в следующем: необходимо провести секущую через складываемые точки и отразить точку пересечения этой прямой с эллиптической кривой относительно оси Ox.
• Ассоциативность означает независимость результата сложения от изменения порядка действия.
• В группе должен существовать нейтральный элемент. Результат сложения любого элемента группы $$ и нейтрального будет равен тому же элементу.В эллиптических кривых роль нейтрального элемента играет бесконечно удаленная точка: $$
  
  
• К каждому элементу должен существовать обратный к нему (относительно основной операции). При сложении элемента группы и обратного к нему получаем нейтральный элемент.
• Свойство коммутативности нам знакомо еще из школьной математики: от перестановки слагаемых сумма не меняется. Именно данное свойство и делает группу абелевой.

Пара слов о стойкости

Теперь поговорим немного о стойкости криптосистем, основанных на задаче дискретного логарифмирования. Пусть $$ – конечная циклическая группа, то есть, каждый ее элемент представим в виде степени одного-единственного элемента — образующей $$: img src="https://habrastorage.org/getpro/habr/formulas/41d/a01/f9e/41da01f9e2b9885222db9bea5fd45b95.svg" alt="$ = G={1, g^2, g^3, ...,g^{q-1}}$" data-tex="inline">.

В зависимости от выбора группы $$ существуют различные методы решения задачи дискретного логарифмирования. Так, для решения задачи дискретного логарифмирования в конечном поле, на общее не счастье существуют не только универсальные алгоритмы (метод Полига-Хеллмана, $$- метод Полларда и др.), которые имеют экспоненциальную сложность, но и специальные, имеющие субэкспоненциальную сложность (метод базы разложения, метод решета числового поля).

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

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

Данные кривые уязвимы к MOV атаке, которая позволяет сводить вычисление задачи дискретного логарифмирования в группе точек эллиптической кривой над полем $$ к задаче дискретного логарифмирования в конечном поле $$. Учитывая, что длина ключа в криптографии на эллиптических кривых меньше, и что для суперсингулярных кривых значение $$ не является большим, реализация данной атаки проходит крайне успешно для злоумышленника.

Ну так в чем же проблема? Используем подходящие эллиптические кривые и радуемся жизни! Но не тут-то было…

3. Квантовая угроза

В последнее время широкую популярность получают квантовые вычисления. Если в классическом компьютере наименьшая единица информации представляется битом, который может принимать значение либо 0, либо 1 в одно время, то в квантовом эту роль выполняют кубиты. Их особенность состоит в том, что кубит может находиться и в состоянии 0, и в состоянии 1 одновременно. Это и дает квантовым компьютерам их превосходящую вычислительную мощь. Например, если мы рассматриваем четыре бита информации, то из всевозможных 16 состояний мы можем выбрать лишь одно в один момент времени. 4 кубита же могут находиться в 16 состояниях одновременно, то есть в суперпозиции, и данная зависимость растет экспоненциально с каждым новым кубитом.

Если в классическом компьютере логические элементы получают на вход биты информации, а на выходе выдают однозначно определенный результат, то в квантовом компьютере в качестве логического элемента берется так называемый квантовый гейт (quantim gate), который манипулирует значением целой суперпозиции.

Важное явление, свойственное кубитам, – это запутанность. Например, имеем два запутанных кубита. Измерение состояния одного из них поможет узнать информацию о состоянии его пары без необходимости какой-либо проверки.

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

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

Об алгоритме Шора

Модификация данного алгоритма позволяет решить и задачу дискретного логарифмирования. Обобщенно метод Шора состоит в сведении сложновычислимой на классическом компьютере задачи к вычислению порядка некой функции. Если рассматривать разложение числа на множители, или задачу факторизации, то в качестве той самой функции берется $$, где $$ число, которое раскладывается, а $$ специально подобранное значение, взаимно простое с $$. Далее по ходу алгоритма находится период функции $$, который удовлетворяет соотношению:$$ и, как следствие, выполняется $$. По найденном периоду вычислить собственный делитель числа $$ можно с помощью алгоритма Евклида: $$.

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

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

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

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

4. Isogeny will save us!

Начнем с понятия: изогения – это рациональное отображение, переводящее точки одной эллиптической кривой в точки изогенной кривой, оставляя неподвижной бесконечно удаленную точку. Пусть имеем две изогенные эллиптические кривые $$ и $$. Изогенными они называются, если они заданы над одним полем и имеют одинаковое число точек.


Так вот, изогения — это, по сути, небольшой ВЖУХ, который берет точку кривой $$ на вход, а на выходе выдает точку кривой $$. Ядром изогении называется множество точек на кривой $$, которые переходят в бесконечно удаленную точку кривой $$.

Для каждой изогении существует единственная дуальная изогения, выполняющая обратное преобразование. То есть, если изогения имеет следующий вид:$$, то дуальная к ней: $$.

Если перемножить изогению и дуальную к ней, получим точку кривой $$, умноженную на целое число $$, которую называют степенью изогении. Изогении простых степеней могут задавать перестановки на множестве $$ инвариантов изогенных кривых. А последовательное наложение графов изогенных эллиптических кривых позволяет получить просто космически красивую звезду изогенных кривых, как на рисунке ниже.

Возможность применения изогений для построения криптосистем была предложена сравнительно недавно. В 2003 году автором E. Teske была опубликована работа, где изогении использовались в схеме с возможностью депонирования ключей. В 2006 году А. Г. Ростовцевым и А. Столбуновым схема шифрования Эль-Гамаля была адаптирована под изогении эллиптических кривых. В том же 2006 году для построения хэш-функций было предложено использовать графы изогенных суперсингулярных кривых. Важным и, можно сказать, переломным моментом в исследовании изогений является работа, опубликованная в 2010 году, где предлагается квантовый алгоритм, решающий задачу нахождения изогений несуперсингулярных кривых за субэкспоненциальное время. С этого момента исследования стали больше ориентированы на суперсингулярные кривые. Так, в сети уже можно найти схемы шифрования с открытым ключом, доказательства с нулевым разглашением, схему неоспоримой подписи и подписи вслепую.

5. Microsoft SIDH: что за покемон?

Компания Microsoft тоже не осталась в стороне и в 2016 году выпустила библиотеку SIDH(Supersingular Isogeny Key Exchange) с открытым исходным кодом. Одним из преимуществ данной библиотеки является возможность использования эллиптических кривых в форме Монтгомери, которые защищают от атак по времени.

SIDH реализована на языке C и поддерживает использование Microsoft Visual Studio на OC Windows и LNU GCC и clang на OC Linux. В библиотеке представлена реализация базовых арифметических функций с возможностью поддержки различных платформ, включая x64, x86 и ARM. Большим плюсом к производительности является оптимизированная реализация операций на эллиптических кривых.
В библиотеке реализован протокол разделения ключа Диффи-Хеллмана на изогениях суперсингулярных кривых.

Эта схема была предложена авторами Jao и DeFeo. Упрощенно ее можно описать следующим образом. В качестве параметров криптосистемы используется общеизвестная суперсингулярная кривая $$ и зафиксированные на ней точки $$. Для удобства за ходом протокола можно следить на рисунке ниже.

Пусть Алиса хочет разделить с Бобом не жизнь, а закрытый ключ. Для этого она генерирует случайные числа $$ и строит изогению $$, где ядро задается как img src="https://habrastorage.org/getpro/habr/formulas/131/a9f/d2f/131a9fd2fe2ec15f83885c0fea42c221.svg" alt="$< m_A P_A+n_AQ_A>$" data-tex="inline">.
Боб выполняет те же действия, но только строит уже изогению img src="https://habrastorage.org/getpro/habr/formulas/99d/c6e/885/99dc6e8858c875fc1c6312760cb15bbc.svg" alt="$< m_B P_B+n_BQ_B>$" data-tex="inline">, где в качестве ядра выбирается img src="https://habrastorage.org/getpro/habr/formulas/99d/c6e/885/99dc6e8858c875fc1c6312760cb15bbc.svg" alt="$< m_B P_B+n_BQ_B>$" data-tex="inline">.

Изогении $$ и $$ являются секретными и кому попало не передаются. Однако, и Боб, и Алиса могут без каких-либо последствий разделить точки на своих изогенных кривых, к тому же, переданы могут быть и сами кривые. Так и происходит на самом деле. Данный этап обозначен на рисунке пунктирной линией. Алиса передает Бобу точки $$ и $$, и саму кривую $$. Боб делает тоже самое: передает Алисе точки $$ и $$ и кривую $$.

А это вообще законно?! Можешь быть спокоен, %username%, зная обе изогенные кривые, злоумышленник не сможет вычислить саму изогению.

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

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

 CurveIsogeny = SIDH_curve_allocate(CurveIsogenyData);     if (CurveIsogeny == NULL) {         Status = CRYPTO_ERROR_NO_MEMORY;         goto cleanup;     }     Status = SIDH_curve_initialize(CurveIsogeny, &random_bytes_test, CurveIsogenyData);     if (Status != CRYPTO_SUCCESS) {         goto cleanup;     } 

 typedef struct {         CurveIsogeny_ID  CurveIsogeny;                                  unsigned int     pwordbits;                                    unsigned int     owordbits;                                    unsigned int     pbits;                                        uint64_t         prime[MAXWORDS_FIELD];                        uint64_t         A[MAXWORDS_FIELD];                            uint64_t         C[MAXWORDS_FIELD];                            unsigned int     oAbits;                                        uint64_t         Aorder[MAXWORDS_ORDER];                       unsigned int     oBbits;                                       unsigned int     eB;                                           uint64_t         Border[MAXWORDS_ORDER];                        uint64_t         PA[2*MAXWORDS_FIELD];                         uint64_t         PB[2*MAXWORDS_FIELD];                         unsigned int     BigMont_A24;                                  uint64_t         BigMont_order[BIGMONT_MAXWORDS_ORDER];        uint64_t         Montgomery_R2[MAXWORDS_FIELD];                uint64_t         Montgomery_pp[MAXWORDS_FIELD];                uint64_t         Montgomery_one[MAXWORDS_FIELD];           } CurveIsogenyStaticData; 

Чтобы Алисе и Бобу обменяться ключами, достаточно вызвать пару функций, которые не обязывают знать того, что же творится «под капотом». Генерация ключей происходит с помощью функций:

 Status = KeyGeneration_A(PrivateKeyA,PublicKeyA, CurveIsogeny); 

 Status = KeyGeneration_B(PrivateKeyB,PublicKeyAB CurveIsogeny); 

Алиса и Боб обмениваются вычисленными открытыми ключами и находят общий ключ:

 Status = SecretAgreement_A(PrivateKeyA, PublicKeyB, SharedSecretA, false, CurveIsogeny);  

 Status = SecretAgreement_B(PrivateKeyB, PublicKeyA, SharedSecretB, false, CurveIsogeny);  

Среди функций в библиотеке можно выделить и базовые арифметические, которые помогут в реализации своих протоколов. Это, например, j_inv, вычисляющая j-инвариант эллиптической кривой, inv_3_way, находящая значение мультипликативно обратного, удвоение точки и сложение точек – xDBLADD, утроение точки – xTPL и т.д. С полным описанием вы можете ознакомиться в публикации.

6. It's coding time!

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

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

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

 CurveIsogeny = SIDH_curve_allocate(CurveIsogenyData); Status = SIDH_curve_initialize(CurveIsogeny, &random_bytes_test, CurveIsogenyData); 

Открытый ключ здесь представлен в виде кортежа значений: $$ и случайного числа $$. Закрытый ключ представляется числами $$ и $$, с помощью которых строится изогения $$.

 Keys.PrivateKey = (unsigned char*)calloc(1, obytes);          Keys.PublicKey = (unsigned char*)calloc(1, 4 * 2 * pbytes);       random_bytes_test(10, Keys.k); Status = KeyGeneration_A(Keys.PrivateKey, Keys.PublicKey, CurveIsogeny); 

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

 Status = KeyGeneration_B(IsogenyB, imagesB, CurveIsogeny);  Status = SecretAgreement_B(IsogenyB, PublicKey, j, false, CurveIsogeny); 

Дальше можете выдохнуть. $$ инвариант общей кривой $$ конкатенируется со числом $$, и от этой мешанины берется хэш. Полученное значение ксорится с секретными данными. В случае приложения – это хэш от названия доклада.

 strncat(j, k, 10); shaCompute(j, hash);  for (i = 0; i < strlen(message); i++)           message[i] ^= hash[i]; 

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

 Status = SecretAgreement_A(PrivateKey, imagesB, j, false, CurveIsogeny);  strncat(j, k, 10);  shaCompute(j, hash);  for (i = 0; i < strlen(cipher); i++)            cipher[i] ^= hash[i]; 

При запуске приложения на сервер отправляется запрос, в ответ на который приходит список докладов. При желании пользователя проголосовать (ну и при нажатии соответствующей кнопки), сервер отправляет открытые параметры, необходимые для зашифрования голоса. Клиент, не теряясь, использует эти параметры, думает около 5-8 секунд, и отправляет необходимые параметры для расшифрования и шифр текст. Сервер это дело расшифровывает за каких-то 0.11 секунд и выдает клиенту результаты голосования.

Для того, чтобы «подружить» Java и C, была использована технология JNI. SIDH компилируется в библиотеку и подключается в коде на java:

 static {         System.loadLibrary("native-lib");     } 

Разработанное приложение можно было скачать на «Очной ставке» NeoQUEST 29 июня 2017 года! Многие слушатели воспользовались возможностью прикоснуться к, вероятно, будущему направлению в области криптографии и проголосовали за понравившийся доклад. Причем каждый голос был защищен от атак на квантовом компьютере! Ну а еще — приложение красивое!

И в заключение...