Многомерная криптография (Bukikbyjugx tjnhmkijgsnx)

Перейти к навигации Перейти к поиску

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

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

История создания

[править | править код]

Первая попытка построения криптографической схемы на основе многомерных квадратичных полиномов была сделана Онгом, Шнором и Шамиром [2], где они предлагали схему подписи, основанную на сложности решения уравнения:
;

Однако безопасность этой схемы по-прежнему основана на сложности факторизации и поэтому эта схема неустойчива к атакам при помощи квантовых компьютеров. Разработка многомерных криптографических схем в современном смысле началась в 1988 году со схемы С* Системы Матцумото-Имаи[3].

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

Эта конструкция называемая биполярной. Она по-прежнему является стандартным методом построения многомерных криптосистем с открытым ключом. [4]

Стандартная двухполярная конструкция
Стандартная двухполярная конструкция

Многомерная криптография была активной областью исследований, однако, до сих пор отсутствуют многомерные схемы, такие как: протоколы обмена ключами и схемы подписи со специальными свойствами[5].

Актуальность и перспективы развития

[править | править код]

Большинство криптосистем с открытым ключом, используемых на практике, основаны на целочисленной факторизации или дискретных логарифмах конечных полях или эллиптических кривых). [6] Однако, эти системы страдают от двух недостатков.

  1. Достижения в области теории чисел привели к снижению эффективности вычислений, поэтому размеры параметров должны быть увеличены в соответствии с требованиями безопасности.[1]
  2. Если можно построить достаточно большие квантовые компьютеры, алгоритм Шора сделает текущие системы полностью небезопасными. Поэтому важно искать альтернативные системы, которые способствуют эффективной и безопасной связи.[1]

Многомерная криптография с открытым ключом — одна из возможных альтернатив нынешних реализаций алгоритмов шифрования с открытым ключом. В 2003 году система подписи Sflash стала окончательным выбором проекта NESSIE (Новые европейские схемы подписи, целостности и шифрования) [7]. Первая книга о многомерной криптографии, написанная Дингом, Гауэром и Шмидтом, была опубликована в 2006 году [5]. Существует также международный воркшоп, PQCrypto, который посвящен вопросам постквантовой криптографии, в том числе многомерной криптографии.[8]

Основной алгоритм работы

[править | править код]

Основной идеей стандартного построения многомерной криптографии является выбор системы (центральное преобразование) из многомерных квадратичных многочленов от переменных, которые могут быть легко инвертированы. [9] После этого выбираются два случайных аффинных обратимых преобразования и для того, чтобы скрыть структуру центрального преобразования в открытом ключе. [10]

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

Закрытый ключ состоит из , , и следовательно, это позволяет инвертировать .

Построение публичного ключа

[править | править код]

Пусть — конечное поле. Публичный ключ алгоритмов многомерной криптографии — это полиномиальное отображение

; где многочлен второй степени.

Для шифрования и дешифрования считаем, что , для электронной подписи: . [1]

Шифрование

[править | править код]

Чтобы зашифровать сообщение или необходимо вычислить . Шифротекст полученного сообщения есть или . [6]

Расшифрование

[править | править код]

Что бы расшифровать шифротекст рекурсивно вычисляется: , и .

— это открытый текст шифротекста . Так как , то отображение из в , а следовательно, и результирующий открытый текст являются уникальными. [6]

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

Цифровая подпись

[править | править код]

Для того, что бы подписать документ , используется хеш-функция для вычисления значения .
Затем необходимо вычислить , и . Здесь означает один, возможно, много прообраз для центрального отображения . Так как , то такое отображение существует. Таким образом каждое сообщение может быть подписано. [6]

Проверка цифровой подписи

[править | править код]

Чтобы проверить подлинность документа, необходимо просто вычислить и значение хеш-функции от документа. Если , то подпись принимается, в противном случае отклоняется. [6]

Безопасность

[править | править код]

Безопасность алгоритмов многомерной криптографии опирается на следующее:

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

Решение случайной многомерной квадратичной системы над конечным полем является NP-полной задачей в сильном смысле или просто NP-полной. Сложность решения этой задачи препятствует злоумышленику вычислить закрытый ключ, зная открытый ключ. [11]

  • Изоморфизм многочленов.[12]

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

Преимущества систем, построенных на алгоритмах многомерной криптографии

[править | править код]
  • Скорость

Системы, построенные на алгоритмах многомерной криптографии достаточно быстры, особенно для подписи документов. Есть много предпосылок, что они могут быть быстрее, чем классические криптографические схемы с открытыми ключами, например RSA. [14] [15]

  • Скромные требования к вычислительным ресурсам

Математические операции, выполняемые многомерными схемами, обычно очень просты: большинству схем требуется только сложение и умножение по небольшим конечным полям. Поэтому многомерные схемы требуют скромных вычислительных ресурсов, что делает их привлекательными для использования на недорогих устройствах, таких как RFID чипы и смарт-карты, без необходимости наличия криптографического сопроцессора. Вариант схемы С*, называемый SFLASH, был предложен Европейской комиссией в качестве стандарта для схем подписи на недорогих устройствах. [16] [17]

В системе SFLASH [1] используется конечное поле также определяется отображение . Обозначение указывает, что уравнений были удалены из функции , которая построена следующим образом: . Здесь и — два обратимых линейных преобразования. Функция имеет вид:. Таким образом, открытый ключ состоит из квадратичных полиномов c переменными коэффициентами в . Каждый квадратичный полином будет иметь коэффициентов. Для этого требуется КБ памяти, если каждый коэффициент хранится в одном байте, также его можно уменьшить до КБ, если использовать только бит для каждого коэффициента

Атаки на системы многомерной криптографии

[править | править код]

Повторная линеаризация

[править | править код]

Атака релинеризации направлена на решение переопределенных систем многомерных квадратичных уравнений. Пусть - система из квадратичных уравнений по переменным . Основная идея заключается в введении новой переменной для каждого квадратичного одночлена . Таким образом, получается система линейных уравнений, если число уравнений достаточно велико, можно использовать метод Гаусса. Нужно удостовериться, действительно ли полученное таким образом решение является решением квадратичного система, при условии, что . Для решения системы квадратичных уравнений по переменным этим методом необходимо уравнений. Таким образом атака методом повторной линеаризации позволяет уменьшить количество неизвестных переменных в закрытом ключе т.е уменьшить его размерность. [18]

XL алгоритм

[править | править код]

Пусть — множество всех многочленов из степени .

XL-алгоритм:
Входные данные: множество квадратичных многочленов .
Выходные данные: вектор такой, что .

  • for to do
    • Фиксируется целое число .
    • Формируются все многочлены:, где и .
    • Необходимо воспользоваться методом Гауса для уравнений, полученных на предыдущем шаге, чтобы сгенерировать одно уравнение, содержащее только .
    • Если на предыдущем шаге получился, по крайней мере один одномерный многочлен от , то его необходимо решить, например при помощи алгоритма Берлекэмпа.
    • Необходимо упростить уравнения путем замены значения .
  • end for
  • return

Атака при помощи XL-алгритма позволяет уменьшить размерность закрытого ключа при помощи сведения системы уравнений к инварианту в некоторой переменной. Таким образом при помощи XL-алгоритма возможно проводить атаку на открытый ключ. [4]

Примеры многомерных криптосистем

[править | править код]
  1. Треугольные криптосистемы [19].
  2. Системы Матцумото-Имаи [20].
  3. Минус-Плюс обобщения системы Мацумото-Имаи [21].
  4. Скрытые уравнения поля
  5. Unbalanced Oil and Vinegar

Примечания

[править | править код]
  1. 1 2 3 4 5 JINTAI DING, DIETER SCHMIDT. Reuleaux Triangle (англ.). MULTIVARIABLE PUBLIC–KEY CRYPTOSYSTEMS. Дата обращения: 18 декабря 2017. Архивировано 9 августа 2016 года.
  2. H. Ong, C.-P. Schnorr and A. Shamir Efficient signature schemes based on polynomial equations. In CRYPTO, volume 196 of Lecture Notes in Computer Science // Springer : journal. — 1984, pages 37–46.
  3. T. Matsumoto and H. Imai EPublic quadratic polynomial-tuples for efficient signature verifi- cation and message-encryption. In EUROCRYPT, volume 330 of Lecture Notes in Computer Science // Springer : journal. — 1988, pages 419–553
  4. 1 2 Albrecht Petzoldt. Selecting and Reducing Key Sizes for Multivariate Cryptography (англ.). Дата обращения: 21 декабря 2017. Архивировано 8 августа 2017 года.
  5. 1 2 Jintai Ding, Jason Gower, and Deiter Schmidt Multivariate Public Key Cryptosystems // Springer : journal. — 2006.
  6. 1 2 3 4 5 Jintai Ding and Bo-Yin Yang. Multivariate Public Key Cryptography (англ.). Дата обращения: 4 декабря 2017. Архивировано 5 декабря 2017 года.
  7. NESSIE. Reuleaux Triangle (англ.). NESSIE: New European Schemes for Signatures, Integrity, and Encryption. NESSIE project announces final selection of crypto algorithms. Information Society Technologies Programme of the European Commission (IST-1999-12324). Дата обращения: 3 декабря 2017. Архивировано 12 июня 2018 года.
  8. Introduction. Дата обращения: 16 декабря 2017. Архивировано 14 декабря 2017 года.
  9. Shuaiting Qiao, Wenbao Han, Yifa Li, and Luyao Jiao. Construction of Extended Multivariate Public Key Cryptosystems (англ.). Дата обращения: 21 декабря 2017. Архивировано 22 декабря 2017 года.
  10. Lih-Chung Wang, Bo-Yin Yang, Yu-Hua Hu, and Feipei Lai. A Medium-Field Multivariate Public-Key Encryption Scheme (англ.). Дата обращения: 18 декабря 2017. Архивировано 5 июля 2017 года.
  11. Jacques Patarin, Louis Goubin, and Nicolas Courtois. Reuleaux Triangle (англ.). Improved Algorithms for Isomorphisms of Polynomials (1998). Springer. Дата обращения: 21 декабря 2017. Архивировано 16 июля 2017 года.
  12. Jacques Patarin. IHidden Field Equations (HFE) and Isomorphisms of Polynomials (IP): two new Families of Asymmetric Algorithms (англ.). Дата обращения: 21 декабря 2017. Архивировано 15 декабря 2017 года.
  13. Takanori Yasuda, Xavier Dahan, Yun-Ju Huang, Tsuyoshi Takagi and Kouichi Sakurai1. MQ Challenge (англ.). MQ Challenge: Hardness Evaluation of Solving Multivariate Quadratic Problems. Дата обращения: 3 декабря 2017. Архивировано 4 декабря 2017 года.
  14. I.-T. Chen, M.-S. Chen, T.-R. Chen, C.-M. Cheng, J. Ding, E. L.-H. Kuo, F. Y.-S. Lee and B.-Y. Yang SSE implementation of multivariate PKCs on modern x86 CPUs. In CHES, volume 5747 of Lecture Notes in Computer Science // Springer : journal. — 2009, pages 33–48
  15. A. Bogdanov, T. Eisenbarth, A. Rupp and C. Wolf Time-area optimized public-key engines: MQ-cryptosystems as replacement for elliptic curves? // Springer : CHES, volume 5154 of Lecture Notes in Computer Science. — 2008, pages 45–61
  16. J. Patarin, N. Courtois and L. Goubin Flash, a fast multivariate signature algorithm // Springer : In CT-RSA, volume 2020 of Lecture Notes in Computer Science. — 2001, pages 298–307
  17. B. Preneel The NESSIE project: Towards new cryptographic algorithms // Swww.cryptonessie.org — 2000
  18. Raymond Heindl. New Directions in Multivariate Public Key Cryptography (англ.). Дата обращения: 18 декабря 2017. Архивировано 26 декабря 2017 года.
  19. Harriet Fell and Whitfield Diffie Analysis of a public key approach based on polynomial substitution. In Advances in cryptology—CRYPTO ’85 (Santa Barbara, Calif.) // Springer : journal. — 1986. — volume 218, pages 340–349.
  20. T. Matsumoto and H. Imai Public quadratic polynomial-tuples for efficient signature verification and message encryption. In C. G. Guenther, editor, Advances in cryptology – EUROCRYPT ’88 // Springer : journal. — 1988. — volume 330, pages 419–453.
  21. Jacques Patarin, Louis Goubin, and Nicolas Courtois C∗−+ and HM: variations around two schemes of T. Matsumoto and H. Imai. In K. Ohta and D. Pei,editors, ASIACRYPT’98 // Springer : journal. — 1998. — volume 1514, pages 35–50.
  1. [1] Multivariate Public Key Cryptography