Алгебраический криптоанализ криптосистемы на основе алгебраической поверхности, предложенной на конференции PKC’2009

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 21:45, 30 октября 2015.
Algebraic Cryptanalysis of the PKC’2009 Algebraic Surface Cryptosystem
AlgebraicCryptanalysis.png
Авторы Jean-Charles Faugère[@: 1] и
Pierre-Jean Spaenlehauer[@: 2]
Опубликован 2010 г.
Сайт Computer science research laboratory
Перевели Alexander Ivanov
Год перевода 2015 г.
Скачать оригинал


Аннотация.В этой статье мы полностью взломаем криптосистему на основе алгебраической поверхности (сокр. ASC - Algebraic Surface Cryptosystem), предложенную на конференции PKC’2009[1]. Эта система основана на необычной задаче в области многомерной криптографии: задача нахождения сечения. Дана алгебраическая поверхность такая, что , задача состоит в том, чтобы найти пару многочленов степеней , таких что . В ASC открытый ключ является поверхностью, а закрытый – сечением. Эта схема ассиметричного шифрования имеет целесообразные длины ключей: для рекомендованных параметров длина закрытого ключа составляет всего 102 бита, а длина открытого ключа – 500 бит. В этой статье мы предлагаем атаку восстановления сообщения, чья сложность квазилинейно зависима от длины закрытого ключа. Основная идея этой алгебраической атаки состоит в разложении идеалов, полученных из шифротекста, для того чтобы избежать решения задачи нахождения сечения. Результаты экспериментов показывают, что мы можем сломать шифр с рекомендуемыми параметрами (уровень защиты ) за 0.05 секунды. Более того, атака также осуществима, если закрытый ключ имеет очень большую длину (более 10000 бит). Сложность атаки – полиномиальная, с учётом всех параметров безопасности. В частности, сложность будет именно квази-линейной, при длине закрытого ключа . Этот результат довольно удивителен, поскольку алгебраическая атака чаще более эффективна, чем естественный алгоритм дешифрования.
Ключевые слова: Многомерная криптография, алгебраический криптоанализ, задача нахождения сечения (SFP), базис Грёбнера, разложение идеалов.

Введение

В 1994 году Шор разработал квантовый алгоритм для эффективного вычисления дискретного логарифма и факторизации[2]. С тех пор, если бы кто-нибудь построил квантовый компьютер, то множество надёжных криптосистем с открытым ключом, например, RSA или системы, основанные на эллиптической криптографии, были бы под серьёзной угрозой. Поэтому криптографы продолжают искать пост-квантовые альтернативы. Первый шаг к проектированию новых криптосистем – выявление трудных задач, чтобы использовать их в качестве односторонних функций с потайным входом. На данный момент большинство задач в пост-квантовой криптологии можно разделить на три категории: многомерная криптография, криптография на основе корректирующих кодов и криптография, основанная на решётках.

В данной ситуации, Akiyama, Goto и Miyake предлагают новый многомерный алгоритм с открытым ключом на конференции PKC’2009: криптосистема на основе алгебраической поверхности (сокр. ASC)[3]. Любопытно что их защита основана на сложной задаче, которая не является распространённой: Задача нахождения сечения. Имея алгебраическую поверхность, определённую многочленом (где обозначает конечное поле мощности ), необходимо найти два многочлена степени , таких что .

Как указано здесь[3], эта задача вычислительно трудная: единственно известный в настоящее время алгоритм ищет корни множества многомерных алгебраических уравнений. Следовательно, идея ASC – использовать поверхность как открытый ключ, а получение сечения этой поверхности как одностороннюю функцию с потайным ходом. В сравнении с HFE [4] или другими многомерными системами ASC обладает некоторыми интересными и необычными свойствами. В частности, ключи имеют неожиданно короткую длину. Безопасность многомерных система обычно основана на сложности нахождения решения системы многочленов низких степеней (часто квадратичной) с огромным количеством переменных. Например, в случае HFE, длина открытого ключа в точности равна количеству многомерных систем уравнений: 265680 бит при уровне защиты . В отличие от HFE, ASC обладает маленьким открытым ключом в 500 бит при уровне защиты . В общем случае, для уровня защиты , длина открытого ключа HFE должна составлять . Для сравнения, размер открытого ключа ASC является уникальным многочленом высокой степени, состоящим только из трёх переменных: его длина – бит при уровне защиты . На самом деле, авторы объясняют, что ключи ASC одни из самых кратчайших среди всех известных пост-квантовых криптосистем. Для более точной оценки обозначим буквой степень открытой поверхности в и . Для достижения уровня защиты длина закрытого ключа должна быть бит, и длина открытого ключа примерно . Главное наблюдение состоит в том, что длины ключей квазилинейно зависимы от , который определяет уровень защиты.

Несмотря на то, что совершенна другая версия ASC [1] была успешно атакована Ivanov и Voloch [5], Uchiyama и Tokunaga [6] и Iwami [7], новая версия ASC, представленная на PKC’2009, является стойкой ко всем известным атакам. Мы хотели бы отметить, что алгоритм дешифрования ставит некоторые вопросы. Более того, один из шагов этого алгоритма – восстановление некоторых множителей степени D многочлена от одной переменной. Для того, чтобы найти эти множители, создатели криптосистемы предлагают воссоединять неприводимые множители многочлена, решая задачу о рюкзаке. Однако эта задача является NP-трудной [8]. Поэтому не совсем ясно, будет ли криптосистема оставаться целесообразной при параметрах, обеспечивающих высокую безопасность.

Основные результаты. В этой статье мы описываем атаку восстановления сообщения, которая может взломать ASC за полиномиальное время. Один из важных шагов алгоритма дешифрования это разложение многочлена от одной переменной. Основная идея алгебраической атаки – выполнить этап разложения в неявном виде, путём разложения идеалов, полученных из шифротекста. Более того, разложение идеалов можно рассматривать как обобщение стандартного разложения многочленов. Следовательно, этот способ позволяет обойти задачу нахождения сечения, которая является трудной.

Мы представляем три варианта этой атаки. Атака 1 уровня высокоуровневая, детерминированная, позволяет увидеть используемые механизмы и может быть реализована прямо в системе компьютерной алгебры, такой как MAGMA (код находится в приложении B). Однако, эта версия не очень эффективна и не может взломать ASC с рекомендуемыми параметрами. Атака 2 уровня основана на следующем наблюдении: многочлены, появляющиеся в ASC, имеют высокую степень в и достаточно низкую степень в и . Исходя из этого, вполне естественно видеть выражение с коэффициентами , вместо многочленов степени t; другими словами, для того чтобы увеличить скорость атаки, мы должны выполнить вычисления в кольце (где – поле частных) вместо . В атаке уровня 3 мы заменяем базисное поле конечным полем для достаточно больших значений , чтобы избежать увеличения промежуточных коэффициентов и восстановить первоначальное сообщение по модулю . Действуя ещё более эффективно, мы можем разделить на несколько неразложимых делителей меньшей степени; Китайская теорема об остатках используется затем, чтобы воссоединить сравнения по модулю и получить исходное сообщение. В третьей версии атаки длина открытого текста определяет необходимое количество сравнений по модулю, а также размер рассматриваемого конечного поля. Поэтому сложность атаки 3 уровня, как ожидается, будет квазилинейно зависимой от длины закрытого ключа. Это поведение подтверждено экспериментальными данными и анализом сложности. Двоичная сложность[прим. 1] атаки 3 уровня (теорема 1):

где обозначает двоичный размер открытого текста, – степень в переменных и , и – "О мягкое" (см. пример, определение 25.8[9]). Поскольку длина закрытого ключа меньше, чем , атака также квазилинейно зависима от размера закрытого ключа. На практике, ≈ dwlog(p) (где – степень секретного сечения). Таким образом, сложность атаки:

Её можно сравнить с нижней границей двоичной сложности (см. раздел анализ сложности) алгоритма дешифрования:

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

Мы реализуем атаки трёх вариантов на MAGMA 2.15-7. Атака 3 уровня может взломать ASC с рекомендуемыми параметрами[3] (, , ) всего за 0.05 секунды. Эксперименты подтверждают, что увеличение длины закрытого ключа с параметрами и на самом деле не повышает безопасность системы. Мы всё ещё способны взломать его за несколько секунд, даже при размере закрытого ключа более 10000 бит! Мы также пытаемся увеличить параметр (степень в и открытой поверхности. При разумном размере открытого ключа (менее 4000 бит) сообщение может быть восстановлено за несколько часов. Наконец, мы можем выяснить, возможно ли защитить систему путём увеличения размера носителя поверхности (параметр ). Однако, как было предсказано анализом сложности, этот параметр имеет очень маленькое влияние на сложность атаки. Тем самым мы можем рассматривать систему как полностью взломанную.

Структура статьи. После этого вступления статья организована следующим образом: В разделе 2, мы дадим краткое описание криптосистемы ASC, как это сделано в [3]. Затем мы объясним теоретические основы атаки. В разделе 3 мы опишем три варианта атаки и покажем конкретное её применение, используя примеры из [3]. Мы так же выполним точный анализ сложности в разделе 5. Наконец, мы получим некоторые экспериментальные результаты, показывающие, что атака является масштабируемой.

Описание криптосистемы

Здесь мы дадим краткое описание ASC. Для более детального представления мы направляем читателя к [3]. Мы рассматриваем кольцо многочленов , где - простое число. Для любого многочлена из , обозначает его носитель в (то есть набор пар , таких, что - одночлен из .

Параметры

Криптосистема ASC имеет следующие параметры: - мощность базисного поля и - степень секретного сечения. Эти два параметра очень важны для безопасности. Они оказывают влияние на двоичный размер закрытого ключа, который равен . Другой параметр, - степень в и открытой поверхности . Последний параметр - , мощность (является носителем в ). Параметры , и влияют на длину открытого ключа, которая приблизительно равна бит.

Ключи

Закрытый ключ представляет собой пару многочленов степени . Открытый ключ задаётся:

  • Поверхностью, заданную неприводимым многочленом , таким что и мощность
  • , носителем многочлена открытого текста и степенью коэффициентов.
  • , носителем делителей многочлена и степенью коэффициентов.

Для шифрования/дешифрования необходимо, чтобы:

.
.
.
.

Шифрование/Дешифрование

Шифрование. Рассмотрим открытый текст, вложенный в многочлен

где . Выберем случайный делитель многочлена

где . Затем выберем 4 случайных многочлена , таких что для ,

и . Наконец, построим шифротекст , где


Дешифрование. Будем считать, что и вычислим разницу . Затем, найдём множитель степень которого равна . Пусть обозначает этот множитель. затем вычислим . Наконец, найдём , решив систему линейных уравнений:

.

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

Для нахождения множителей , степень которых равна , создатели системы предлагают разложить , затем воссоединить неприводимые множители путём решения задаче о рюкзаке. Однако, задача о рюкзаке является NP-трудной[8]. Исходя из этого, как указано в [3], не ясно, остаётся ли алгоритм дешифрования практичным при параметрах, обеспечивающих высокую безопасность системы.

Безопасность системы

Создатели криптосистемы предлагают использовать следующие параметры:

  • .
  • должно быть больше 50.
  • должно быть больше 5.
  • Нижняя граница – 3.

Размер закрытого ключа около 100 бит и размер открытого ключа близок к 500 битам. Согласно разработчикам ASC, до сих пор не существует известных атак, работающих быстрее, чем поиск методом полного перебора этих параметров. Поэтому уровень защищённости ASC предполагается равным стоимости поиска закрытого ключа методом полного перебора, а именно .

Описание атаки

Обзор атаки. В этом разделе мы предложим атаку восстановления сообщения криптосистемы, описанной выше. Суть атаки состоит в декомпозиции идеалов вместо разложения многочлена от одной переменной, полученного путём подсчёта в сечении . Таким образом мы можем в неявном виде оперировать так называемым делителем полинома , возникающим в процессе дешифрования. Вследствие этого мы можем избежать решения задачи нахождения сечения и получить полиномиальную атаку на ASC. В первую очередь, мы представим высокоуровневую и детерминированную версию атаки (Алгоритм 1), основанную на двух фундаментальных леммах. Затем, мы увеличим скорость алгоритма, рассматривая поля частных (Алгоритм 2). На самом деле, многочлены, появляющиеся в ASC, имеют высокую степень в . Поскольку сложность алгоритмов базиса Грёбнера линейно зависима от сложности арифметики в базисном поле, то разумно делать вычисления в поле частных . Наконец, мы будем использовать модульный подход к реализации эффективной атаки: мы будем выполнять вычисления в некоторых хорошо подобранных конечных полях и воссоединять результаты используя Китайскую теорему об остатках (Алгоритм 3). Таким образом, размер коэффициентов промежуточных величин будет ограничен (эти коэффициенты могут иметь большой размер, когда вычисления выполняются в поле частных). Это позволит нам сломать более защищённые системы ASC. В частности, мы можем сломать систему с рекомендуемыми параметрами за 0.05 секунд. В дальнейшем это позволит нам выполнить точный анализ сложности и показать, что эта атака квазилинейно зависима от длины закрытого ключа. Опытным путём было установлено, что в некоторых случаях мы можем взломать криптосистемы с длиной закрытого ключа превышающей 10000 бит. Сейчас мы сравним эффективность трёх версий атаки на небольшой задаче. К примеру, мы будем считать, что параметры системы принимают следующие значения: , , и , и мы будем использовать реализацию в системе MAGMA. Атака 1 уровня (код в приложении B) восстановит открытый текст за 136 секунд. Как было предсказано, атака 2 уровня быстрее и может взломать код за 74 секунды. Используя модульный подход в атаке 3 уровня, мы значительно увеличиваем скорость вычислений: восстановление текста происходит за 0.06 секунды.

Атака 1 уровня: разложение идеалов

Две следующие леммы являются ключевыми элементами атаки:

TemplateTheoremIcon.svg Теорема Лемма1
Пусть является идеалом, . Тогда , где и . В общем случае, идеалы и - простые идеалы в .
Доказательство

.

Лемма 1 показывает, что, как только нам удалось разложить идеал , мы можем в неявном виде оперировать многочленом с помощью . Замечание 1. Для того, чтобы разложить , необходимо избавиться от в с помощью вычисления базиса Грёбнера . В общем случае, базис Грёбнера содержит только один многочлен . Если достаточно большое, то в общем случае имеет два коэффициента, которые зависят от и (мы не рассматриваем множители из ). Это обстоятельство подтверждено экспериментально. Эти два множителя соответствуют и . Затем, мы можем построить (соотв. ) путём добавления к подходящего множителя . Поскольку , то множитель с наибольшей степенью – единственный, отвечающий за . Для поиска эффективного многочлена , зависящего от двух переменных, мы можем использовать, например, алгоритм [10].


TemplateTheoremIcon.svg Теорема Лемма2
Пусть является идеалом , порождённым . Тогда . Более того, - нульмерный идеал
Доказательство

.

Замечание 2. Лемма 2 показывает, что мы можем точно вычислить многопараметрический идеал, который содержит . Поскольку мы знаем , то можем восстановить , решив следующую систему линейный уравнений:

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

TemplateExampleIcon.svg Пример Алгоритм 1. Атака 1 уровня.
  1. Вычисляем базис Грёбнера идеала . В общем случае этот базис Грёбнера содержит только один многочлен .
  2. Раскладываем на множители . Пусть означает неприводимый множитель с наибольшей степенью в зависимости от .
  3. Вычисляем базис Грёбнера идеала .
  4. Для получения открытого текста (с точностью до умножения на скаляр) решим систему линейных уравнений над
5. Если система не имеет решений, переходим к шагу 2 и выбираем другой множитель .


Замечание 3. Для повышения производительности мы вычисляем базис Грёбнера относительно градуированного обратного лексикографического порядка (Определение 1 в приложении А). Вместо вычисления базиса Грёбнера можно также вычислить результант, чтобы избавиться от переменной .

Замечание 4. Каноническая форма - линейное приложение из на . В последнем шаге атаки мы ищем пересечение ядра с подпространством , порождённым (где обозначает носитель в ). Следовательно, система линейных уравнений имеет неизвестных и уравнений (, когда рассматривается как -векторное пространство). Из границы Безу[11]: . Для дешифрования алгоритма необходимо, чтобы (для того, чтобы решить итоговую линейную систему), и можно заметить, что (поскольку и ). Следовательно, система линейных уравнений имеет больше уравнений, чем неизвестных:

Атака 2 уровня: вычисление в поле частных Атака 2 уровня: вычисление в поле частных F p ( t ) {\displaystyle \mathbb {F} {p}(t)}

Многочлены, возникающие в ASC имеют достаточно высокую общую степень, но их степень в переменных и низкая. Следовательно, будет разумно рассматривать эти многочлены как многочлены от двух переменных и над полем частных . Действительно, степень в и полностью независима от параметра безопасности . В данном разделе мы объясним, как приспособить атаку для данного случая. Выполнив это, мы ожидаем понижения сложности. Действительно, сложность некоторых операций над идеалами - например, вычисления базиса Грёбнера - линейна в базисном поле.

С этого момента будет обозначать поле частных .

Первым делом, мы должны преобразовать леммы для данного случая. Для первой леммы это можно сделать без значительных изменений:

TemplateTheoremIcon.svg Теорема Лемма 3
Пусть является идеалом, (рассматривается как идеал ). Тогда существует два строгих идеала и из , таких что и .
Доказательство

Отсутствует.


К сожалению, лемма 2 не может быть непосредственно преобразована для поля частных. Действительно, множество идеала (рассматривается как идеал ) в общем случае пусто, поскольку он порождено тремя независимыми уравнениями. Следовательно, необходимо ввести новую переменную , для того чтобы сохранить нульмерный и строго включённый в идеал. Грубо говоря, переменная изменяет идеал для того, чтобы получить новые элементы в множестве:

TemplateTheoremIcon.svg Теорема Лемма 4
Пусть является идеалом . Тогда . Более того, - нульмерный идеал
Доказательство

.


TemplateExampleIcon.svg Пример Алгоритм 2. Атака 2 уровня: вычисление в поле частных
  1. Вычисляем результант
  2. Раскладываем на множители результант . Пусть обозначает неприводимый множитель самой высокой степени
  3. Вычисляем базис градуированного обратного лексикографического порядка Грёбнера идеала .
  4. Рассмотрим следующую систему линейных уравнений над
Если система не имеет решений, переходим к шагу 2 и выбираем другой множитель результанта.
5. Возвращаем значение , где - уникальное решение линейной системы.


Для восстановления открытого текста мы должны решить систему линейных уравнений с неизвестными и уравнениями. На практике, уравнений больше чем неизвестных. Таким образом, мы можем выбрать неверный множитель результанта (множитель, который не является делителем ), тогда система линейных уравнений не будет иметь решения и нам придётся начинать с шага 2, до тех пор пока мы не найдём подходящий множитель. На практике, неприводимый множитель результанта с наивысшей степенью всегда является хорошим выбором.

Замечание 5. Можно также совместить две версии атаки путём вычисления базиса Грёбнера идеала, исключения и разложения его в поле как это было сделано в атаке 1 уровня (шаги 1 и 2 в первом алгоритме). Затем, как только мы найдём , мы сможем восстановить сообщение, вычислив базис Грёбнера в поле частных (шаги 3,4,5 второго алгоритма).

Атака 3 уровня: вычисление в конечном поле Атака 3 уровня: вычисление в конечном поле F p m {\displaystyle \mathbb {F} {p^{m}}}

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

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

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

TemplateExampleIcon.svg Пример Алгоритм 3. Атака 3 уровня: вычисление в конечном поле
  1. Выбираем неприводимых многочленов степени , таких что
  2. for from 1 to do
    1. Рассмотрим
    2. Вычисляем результант .
    3. Раскладываем на множители результант . Пусть обозначает неприводимый множитель высшей степени .
    4. Вычисляем базис градуированного обратного лексикографического порядка Грёбнера идеала .
    5. Рассмотрим следующую систему линейных уравнений над
Если система не имеет решений, то переходим к шагу 2 и выбираем другой множитель результанта.
6. Возвращаем равенство , где - уникальное решение линейной системы
9. end for
10. Используем китайскую теорему об остатках, чтобы восстановить .


Замечание 6. Система линейных уравнений, описываемая в алгоритме 3 на шаге 7, имеет только неизвестных и уравнений. Для применяемых параметров, меньше, чем , поэтому система линейных уравнений переопределена и имеет в общем случае только одно решение. Этот факт подтверждается экспериментально.

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

Конкретный пример

Мы рассмотрим здесь небольшой пример, описанный в[3]. У нас есть:

  • Закрытый ключ
  • Открытая поверхность

.

  • Носители и :

Далее показано как восстановить сообщение из шифротекста (описано в[3]) с помощью атаки 3 уровня:

  1. Поскольку , мы выберем, например, неприводимыми, такими что . В частности:
,
,
,
.
Сначала мы рассмотрим конечное поле
  1. Вычислим результант в :
.
  1. Затем вычислим его множитель в :
.
  1. Рассмотрим как неприводимый множитель с наибольшей степенью:
.
  1. Вычислим базис Грёбнера в зависимости от градуированного обратного лексикографического порядка идеала
  1. Поскольку , вычислим :
.
  1. Решим систему линейный уравнений над
:
.
  1. Восстановим равенство:
  1. Повторим процесс с и
  1. Используем китайскую теорему об остатках, чтобы восстановить :
.

Анализ сложности

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

  1. Сначала оценим сложность вычисления результанта в зависимости от в (где . Согласно [9] (следствие 11.18), это может быть сделано за операций в , и степень результанта равна
  2. Вероятностный алгоритм Кантора-Цассенхауза[9] разлагает на множители многочлен степени над конечным полем за арифметических операций в поле . Исходя из этого арифметическая сложность разложения на множители результанта в поле равна:
.
  1. Степень регуляризации идеала является важнейшим показателем сложности вычисления базиса Грёбнера относительно градуированного обратного лексикографического порядка: именно самая высокая степень многочленов возникает в алгоритме. Согласно[11][12][13] если идеал образован общими уравнениями от переменных, тогда сложность вычисления базиса Грёбнера равна:
.
Поскольку идеал образован тремя независимыми уравнениями, то его степень регуляризации может быть оценена с помощью границы Маколея[11], как:
.
На практике: . Следовательно, . Арифметическая сложность вычисления базиса Грёбнера в равна:
.
  1. Наконец мы имеем систему линейных уравнения для решения. Количество переменных равно . На практике , которая меньше 1000 (рекомендуемый параметр ). Следовательно этот шаг незначителен для практического применения по сравнению с вычислением базиса Грёбнера, так как переопределённая система линейных уравнений с менее чем 1000 переменных в конечном поле может быть запросто решена. Более того, этот шаг аналогичен решению системы линейных уравнений в подлинном алгоритме декодирования, который должен быть эффективен для практических параметров.

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

TemplateTheoremIcon.svg Теорема Теорема 1

Общая двоичная сложность атаки 3 уровня:

      результант                   факторизация                           Грёбнер             Китайская теорема об остатках

Следовательно, общая верхняя асимптотическая граница сложности атаки:

.
Доказательство
Без доказательства.


TemplateLemmaIcon.svg Лемма «Следствие 1»

Если мы предположим, что (как это имеет место на практике), то двоичная сложность атаки равна


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

Нижняя граница сложности алгоритма дешифрования.

Сравним сложность этой атаки с нижней границей стоимости процесса дешифрования. В алгоритме дешифрования необходимо разложить на множители в поле . Степень этого многочлена по крайней мере равна . Насколько нам известно, лучшие вероятностные алгоритмы факторизации имеют сложность [9]. Более того, после факторизации необходимо решить задачу о рюкзаке. Сложность этого шага трудно оценить, поскольку мы не учитываем его здесь (помните, что мы стараемся установить нижнюю границу). Последний шаг процесса дешифрования - решений системы линейных уравнений с переменными: арифметическая сложность данного шага равна . Наконец, итоговую двоичная сложность алгоритма дешифрования можно оценить нечёткой нижней границей , которая находится в кубической зависимости от параметров и , и квадратичной от . Для сравнения, атака квазилинейна от , и многочлена степени 7 переменной

Экспериментальные результаты

Рабочая станция. Экспериментальные результаты были получены с помощью двупроцессорной системы Xeon 3.2 ГГц с 64 Гб RAM. Экземпляры криптосистемы ASC были получены с помощью Magma2.15-7. Для вычисления базиса Грёбнера мы будем использовать [14] реализации на MAGMA. Для генерации образцов криптосистем, выберем и рассмотрим следующие параметры:

- .
- .
- .
- .
- .
-

Построение и .

случайные многочлены степени . Для того, чтобы построить , выберем два случайных многочлена степени 20 и рассмотрим:

.

Затем убедимся, что неприводим. Если это не так, то выберем другие многочлены и . Таблица 1 показывает сложность атаки 3 уровня для различных величин и . Каждая запись в таблице является усреднённым результатом, который был получены в результате рассмотрении более 20 случайных экземпляров криптосистемы.

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

длина открытого ключа длина закрытого ключа оценка безопасности
2 50 5 3 310 бит 102 бита 0,02с 0,02с 0,01с 0,05с
2 100 5 3 560 бит 202 бита 0,03с 0,02с 0,02с 0,07с
2 200 5 3 1060 бит 402 бита 0,05с 0,05с 0,05с 0,15с
2 400 5 3 2060 бит 802 бита 0,1с 0,1с 0,1с 0,3с
2 800 5 3 4060 бит 1602 бита 0,2с 0,2с 0,2с 0,65с
2 1600 5 3 8060 бит 3202 бита 0,3с 0,3с 0,4с
2 2000 5 3 10060 бит 4002 бита 0,45с 0,4с 0,4с 1,3с
2 5000 5 3 25060 бит 10002 бита 0,8с 1,3с 0,8с 3,0с
17 50 5 3 1267 бит 409 бит 0,2с 2,4с 0,4с 3,0с
17 100 5 3 2289 бит 818 бит 0,3с 5,1с 0,6с 6,0с
17 400 5 3 8420 бит 3270 бит 1,45с 27,7с 3,9с 33,1с
17 800 5 3 16595 бит 6500 бит 3,1с 70с 9,5с 83с
10007 500 5 3 34019 бит 13289 бит 29с 217с 64с 310с
Таблица 1. Атака 3 уровня - экспериментальные результаты при

Объяснение результатов. Стоит заметить, что первая строка Таблицы 1 соответствует параметрам, рекомендуемым создателями системы[3], и полностью её можно взломать за 0,05 секунд. Основное наблюдение состоит в том, что сложность атаки квазилинейно зависит, как было предсказано в анализе сложности, от параметра . Мы также провели некоторые эксперименты, чтобы изучить влияние параметра (мощность носителя поверхности ) на сложность: как было предсказано, увеличение оказывает очень маленькое влияние на стоимость атаки. Подводя итог, из Таблицы 1 мы видим, что попытка улучшить безопасность системы путём увеличения размера закрытого ключа (то есть путём увеличения параметров и ) бесполезна: даже когда длина закрытого ключа превышает 10000 бит, система может быть взломана за несколько секунд.

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

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

длина открытого ключа длина закрытого ключа оценка безопасности
2 50 5 3 310 бит 102 бита 0,02с 0,02с 0,01с 0,001с 0,05с
2 50 15 3 560 бит 102 бита 0,7с 0,3с 4,4с 0,03с 5,4с
2 50 25 3 1310 бит 102 бита 32с 0,2с 37с
2 50 35 3 1810 бит 102 бита 10с 260с 274с
2 50 45 3 2310 бит 102 бита 30с 1352с 1393с
2 50 55 3 2810 бит 102 бита 70с 12с 4619 13с 4714с
2 50 65 3 3310 бит 102 бита 147с 22с 12408с 27с 12604с
2 50 75 3 3810 бит 102 бита 288с 38с 37900с 56с 38280с
Таблица 2. Атака 3 уровня - экспериментальные результаты при увеличении

Заключение

В этой статье мы проанализировали защищённость криптосистемы на основе алгебраической поверхности, предложенной на конференции PKC'2009. Мы рассмотрели три варианта атаки восстановления сообщений. Мы также очень точно оценили сложность атаки 3 уровня и показали, что она полиномиальна для всех параметров системы. Более того, она квазилинейно зависима от длины закрытого ключа, в то время как алгоритм дешифрования, предложенный в[3], имеет кубическую зависимость.

Экспериментальные результаты подтвердили теоретический анализ. Мы показали, что атака может легко взломать ASC с рекомендуемыми параметрами. Лучший способ попытаться защитить ASC от атаки - взять и как можно меньшими ( и ) и увеличить . Однако наша реализация атаки полиномиальна относительно и систему возможно взломать за несколько часов, даже когда (сравните это значение с первоначально предлагаемым ).

Таким образом, мы считаем, что система полностью взломана, но мы верим что задача нахождения сечения всё ещё является интересной проблемой; в этой статье мы просто показали как избежать её решения в контексте ASC

Благодарности. Мы хотим выразить благодарность анонимным рецензентам за их полезные комментарии и предложения. Мы также благодарны Maki Iwami за его (её) полезные обсуждения.

Приложение А. Базис Грёбнера и каноническая форма

В этом разделе мы кратко опишем некоторые основные понятия из коммутативной алгебры, которые будут полезны для атаки, представленной в этой статье. Для наиболее полного представления читатель может обратиться к [15][16]. Впредь будет обозначать поле, а будет обозначать кольцо . Предположим, учитывая допустимый мономиальный порядок для атаки мы рассмотрим градуированный обратный лексикографический порядок.

TemplateDifinitionIcon.svg Определение «Градуированный обратный лексикографический порядок»

Пусть два одночлена. Тогда если

  • или
  • и крайний правый ненулевой элемент из отрицателен.

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

TemplateDifinitionIcon.svg Определение «Каноническая форма»

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

Каноническая форма -линейного приложения и его основное свойство:

Утверждение 1. Пусть идеал из , и многочлен. тогда и только тогда, когда .

Для того чтобы вычислить каноническую форму, необходимо другое фундаментальное понятие: базис Грёбнера.

TemplateDifinitionIcon.svg Определение «Базис Грёбнера»

Пусть идеал из . Конечное множество многочленов называется базисом Грёбнера идеала (по отношению к мономиальному порядку ), если .

Приложение B. Код MAGMA для атаки 1 уровня

В следующем фрагменте кода p и d параметры системы. deg_t - степень относительно и Lambda_m обозначает носитель (эти величины открыты). F0 и F1 шифротекст, а X - открытая поверхность.

  R<x,y,t>:=PolynomialRing(GF(p),3,"grevlex");
  Res:=Resultant(R!(F0-F1),R!X,x); // Eliminate x
  F:=Factorization(Res); // Factor the resultant
  // Pick the irreducible factor of highest degree in y
  maxdeg:=Max([Degree(R!f[1],R!y) : f in F]);
  exists(Q0){f[1]:f in F| Degree(R!f[1],R!y) eq maxdeg};
  J:=Ideal([R!Q0,R!X,R!F0,R!F1]);
  Groebner(J); // Compute the Gröbner basis of J
  Coeffm:=PolynomialRing(GF(p),#Lambda_m*(deg_t+1));
  R2<x,y,t>:=PolynomialRing(Coeffm,3);
  // Construct the linear system
  plaintext:=&+[Coeffm.((i-1)*(deg_t+1)+j)*
  R2!NormalForm(R!x^Lambda_m[i][1]*
  R!y^Lambda_m[i][2]*R!t^(j-1),J) :
  i in [1..#Lambda_m], j in [1..deg_t+1]];
  // Solve the linear system:
  V:=Variety(Ideal(Coefficients(plaintext)));

Контакты авторов материала

  1. INRIA Centre Paris-Rocquencourt, SALSA Project E-mail: charles.faugere@inria.fr
  2. UPMC, Université Paris 06, LIP6 E-mail: jean.spaenlehauer@lip6.fr

Примечание

  1. Двоичная сложность – количество арифметических операций над битами, а арифметическая сложность – количество операций в базовом кольце.

Литература

  1. 1,0 1,1 K. Akiyama, Y. Goto, and H. Miyake. An Algebraic Surface Cryptosystem. In Proceedings of the 12th International Conference on Practice and Theory in Public Key Cryptography: PKC’09, page 442. Springer, 2009.
  2. P. W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In SFCS ’94: Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pages 124–134, Washington, DC, USA, 1994. IEEE Computer Society.
  3. 3,00 3,01 3,02 3,03 3,04 3,05 3,06 3,07 3,08 3,09 3,10 3,11 K. Akiyama, Y. Goto, and H. Miyake. An Algebraic Surface Cryptosystem. In Proceedings of the 12th International Conference on Practice and Theory in Public Key Cryptography: PKC’09, page 442. Springer, 2009.
  4. J. Patarin. Hidden fields equations (HFE) and isomorphisms of polynomials (IP): Two new families of asymmetric algorithms. Lecture Notes in Computer Science, 1070:33–48, 1996.
  5. P. Ivanov and J.F. Voloch. Breaking the Akiyama-Goto cryptosystem. Arithmetic, Geometry, Cryptography and Coding Theory, 487, 2009.
  6. S. Uchiyama and H. Tokunaga. On the Security of the Algebraic Surface Public-key Cryptosystems. In Proceedings of SCIS, 2007.
  7. M. Iwami. A Reduction Attack on Algebraic Surface Public-Key Cryptosystems. In Workshop of Research Institute for Mathematical Sciences (RIMS) Kyoto University, New development of research on Computer Algebra, RIMS Kokyuroku, volume 1572. Springer, 2007.
  8. 8,0 8,1 M.R. Garey, D.S. Johnson, et al. Computers and Intractability: A Guide to the Theory of NP-completeness. wh freeman San Francisco, 1979.
  9. 9,0 9,1 9,2 9,3 9,4 J. Von Zur Gathen and J. Gerhard. Modern computer algebra. Cambridge University Press, 2003.
  10. G. Lecerf. New recombination algorithms for bivariate polynomial factorization based on Hensel lifting. To appear in AAECC, 2007.
  11. 11,0 11,1 11,2 D. Lazard. Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations. In EUROCAL, volume 162, pages 146–156. Springer, 1983.
  12. M. Bardet, J.-C. Faugere, B. Salvy, and B.-Y. Yang. Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems. In Proceedings of the Eight International Symposium on Effective Methods in Algebraic Geometry (MEGA), 2005.
  13. M. Bardet, J.-C. Faugere, and B. Salvy. On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations. In Proceedings of the International Conference on Polynomial System Solving, pages 71–74, 2004.
  14. J.-C. Faug`ere. A new efficient algorithm for computing Gröbner bases (F4). Journal of Pure and Applied Algebra, 139:61–88, 1999.
  15. D.A. Cox, J.B. Little, and D. O’Shea. Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra. Springer Verlag, 1997
  16. W.W. Adams and P. Loustaunau. An introduction to Gröbner bases. American Mathematical Society, 1994.