Многомерная криптография (Bukikbyjugx tjnhmkijgsnx)
Многомерная криптография или многомерная криптография открытого ключа — это общий термин, описывающий асимметричные криптографические схемы, построенные на решениях уравнений, основанных на многомерных полиномах над конечным полем .
Безопасность многомерной криптографии основывается на предположении, что решения системы квадратичных многочленов над конечным полем , в общем случае, является NP-полной задачей в сильном смысле или просто NP-полной. Вот почему эти схемы часто считаются хорошими кандидатами для постквантовой криптографии. [1]
История создания
[править | править код]Первая попытка построения криптографической схемы на основе многомерных квадратичных полиномов была сделана Онгом, Шнором и Шамиром [2], где они предлагали схему подписи, основанную на сложности решения уравнения:
;
Однако безопасность этой схемы по-прежнему основана на сложности факторизации и поэтому эта схема неустойчива к атакам при помощи квантовых компьютеров. Разработка многомерных криптографических схем в современном смысле началась в 1988 году со схемы С* Системы Матцумото-Имаи[3].
Мацумото и Имаи использовали биективное отображение над степенью полем расширения из формы:
.
Чтобы убедиться, что это преобразование обратимо, необходимо выбрать таким образом, что . Уравнение выше даёт, благодаря каноническому изоморфизму между и векторным пространством систему многомерных квадратичных уравнений на полем , объясняется это Эндоморфизмом Фробениуса. Для того чтобы спрятать структуру Мацумото и Имай использовали два аффинных преобразования и . Таким образом, они представили открытый ключ в форме:
.
Эта конструкция называемая биполярной. Она по-прежнему является стандартным методом построения многомерных криптосистем с открытым ключом. [4]
![Стандартная двухполярная конструкция](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9f/%D0%A1%D1%82%D0%B0%D0%BD%D0%B4%D0%B0%D1%80%D1%82%D0%BD%D0%B0%D1%8F_%D0%B4%D0%B2%D1%83%D1%85%D0%BF%D0%BE%D0%BB%D1%8F%D1%80%D0%BD%D0%B0%D1%8F_%D0%BA%D0%BE%D0%BD%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%86%D0%B8%D1%8F.jpg/300px-%D0%A1%D1%82%D0%B0%D0%BD%D0%B4%D0%B0%D1%80%D1%82%D0%BD%D0%B0%D1%8F_%D0%B4%D0%B2%D1%83%D1%85%D0%BF%D0%BE%D0%BB%D1%8F%D1%80%D0%BD%D0%B0%D1%8F_%D0%BA%D0%BE%D0%BD%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%86%D0%B8%D1%8F.jpg)
Многомерная криптография была активной областью исследований, однако, до сих пор отсутствуют многомерные схемы, такие как: протоколы обмена ключами и схемы подписи со специальными свойствами[5].
Актуальность и перспективы развития
[править | править код]Большинство криптосистем с открытым ключом, используемых на практике, основаны на целочисленной факторизации или дискретных логарифмах (в конечных полях или эллиптических кривых). [6] Однако, эти системы страдают от двух недостатков.
- Достижения в области теории чисел привели к снижению эффективности вычислений, поэтому размеры параметров должны быть увеличены в соответствии с требованиями безопасности.[1]
- Если можно построить достаточно большие квантовые компьютеры, алгоритм Шора сделает текущие системы полностью небезопасными. Поэтому важно искать альтернативные системы, которые способствуют эффективной и безопасной связи.[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]
Примеры многомерных криптосистем
[править | править код]- Треугольные криптосистемы [19].
- Системы Матцумото-Имаи [20].
- Минус-Плюс обобщения системы Мацумото-Имаи [21].
- Скрытые уравнения поля
- Unbalanced Oil and Vinegar
Примечания
[править | править код]- ↑ 1 2 3 4 5 JINTAI DING, DIETER SCHMIDT. Reuleaux Triangle (англ.). MULTIVARIABLE PUBLIC–KEY CRYPTOSYSTEMS. Дата обращения: 18 декабря 2017. Архивировано 9 августа 2016 года.
- ↑ 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.
- ↑ 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
- ↑ 1 2 Albrecht Petzoldt. Selecting and Reducing Key Sizes for Multivariate Cryptography (англ.). Дата обращения: 21 декабря 2017. Архивировано 8 августа 2017 года.
- ↑ 1 2 Jintai Ding, Jason Gower, and Deiter Schmidt Multivariate Public Key Cryptosystems // Springer : journal. — 2006.
- ↑ 1 2 3 4 5 Jintai Ding and Bo-Yin Yang. Multivariate Public Key Cryptography (англ.). Дата обращения: 4 декабря 2017. Архивировано 5 декабря 2017 года.
- ↑ 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 года.
- ↑ Introduction . Дата обращения: 16 декабря 2017. Архивировано 14 декабря 2017 года.
- ↑ Shuaiting Qiao, Wenbao Han, Yifa Li, and Luyao Jiao. Construction of Extended Multivariate Public Key Cryptosystems (англ.). Дата обращения: 21 декабря 2017. Архивировано 22 декабря 2017 года.
- ↑ Lih-Chung Wang, Bo-Yin Yang, Yu-Hua Hu, and Feipei Lai. A Medium-Field Multivariate Public-Key Encryption Scheme (англ.). Дата обращения: 18 декабря 2017. Архивировано 5 июля 2017 года.
- ↑ Jacques Patarin, Louis Goubin, and Nicolas Courtois. Reuleaux Triangle (англ.). Improved Algorithms for Isomorphisms of Polynomials (1998). Springer. Дата обращения: 21 декабря 2017. Архивировано 16 июля 2017 года.
- ↑ Jacques Patarin. IHidden Field Equations (HFE) and Isomorphisms of Polynomials (IP): two new Families of Asymmetric Algorithms (англ.). Дата обращения: 21 декабря 2017. Архивировано 15 декабря 2017 года.
- ↑ 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 года.
- ↑ 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
- ↑ 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
- ↑ 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
- ↑ B. Preneel The NESSIE project: Towards new cryptographic algorithms // Swww.cryptonessie.org — 2000
- ↑ Raymond Heindl. New Directions in Multivariate Public Key Cryptography (англ.). Дата обращения: 18 декабря 2017. Архивировано 26 декабря 2017 года.
- ↑ 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.
- ↑ 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.
- ↑ 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] Multivariate Public Key Cryptography