Криптосистемы Полига-Хеллмана и Мак-Элиса

Коды MDPC характеризуются низкой способностью к исправлению, но высокой устойчивостью к структурным криптографическим атакам: в этом случае редкость матрицы проверки уже невозможна.Квазициклические кодыПорождающая матрица квазициклического кода низкой плотности (QC-LDPC) задается как конкатенация нескольких циклов. Вращение представляет собой (n, n)-матрицу, первая строка которой содержит многочлен, а остальные строки — его циклические сдвиги:Задавая код в таком виде, мы немного теряем в корректирующей способности, но можем хранить порождающую матрицу в компактной форме: теперь нам нужно хранить только порождающие полиномы, а построить порождающую матрицу можно выписав их циклические сдвиги.Давайте оценим, во сколько раз можно уменьшить наш приватный ключ, используя такой подход для (p, n)-QC-LDPC кода с параметрами n = 9602 и p = 4801 (размер одной циркулянты):Бинарная матрица перестановки P(n, n): ~11 Mb --> целочисленный вектор P’(n): ~9.5 Kb. В данном случае мы храним массив переставленных столбцов, избавляясь от огромной размерности.Порождающая матрица G(n, p): ~5.5 Mb --> полиномиальная форма G’(n): ~1.2 Kb.Бинарная матрица S(p, p): ~2.75 Mb --> полиномимальная форма S’(p): ~0.6 Kb. Используя S тоже в форме циркулянты, мы немного потеряем в криптостойкости, но сильно уменьшим затраты памяти.Уровень безопасностиУровень криптографической стойкости представляет собой двоичный логарифм числа итераций, необходимых злоумышленнику для взлома криптографической системы.Для сравнения: код MDPC с параметрами n=9602 и w=90 обеспечивает 80-битный уровень безопасности. При этом другие методы криптоанализа не известны, кроме атак на произвольный линейный код (например, декодирование в информационном пакете), и этот уровень в настоящее время считается достаточно надежным.атакиКриптографическая мощь системы основана на двух сложных вычислительных задачах: полном переборе ключевого пространства и декодировании с максимальной вероятностью. В литературе описано множество нападений на МакЭллиса. Некоторые атаки, называемые структурированными атаками, основаны на создании декодера/реверс-инжиниринга для кода открытого ключа. В случае успеха секретный ключ будет раскрыт, а криптосистема будет полностью уничтожена. Чтобы определить эквивалентный код, злоумышленник должен сравнить код, представляющий каждый класс. Поскольку альтернативные классы имеют очень низкую мощность, этот процесс не под силу даже самым мощным компьютерам.Другие атаки направлены на получение исходного текста сообщения из зашифрованного сообщения. Большинство из них основаны на расшифровке, обобщении и улучшении наборов данных. Существуют такие атаки, как итеративное декодирование и статическое декодирование, но они не увенчались успехом. Атака ISD оказалась самой сложной. В последние годы было описано несколько алгоритмов и их усовершенствований.ЗАКЛЮЧЕНИЕКриптография кода — относительно новая и интересная тема для изучения. Его актуальность отмечена увеличением мощности компьютеров, которые стали переноситься на классические криптосистемы.Широкому развитию кодовых криптосистем в основном препятствует большой размер ключей, однако ученые добились прогресса в этом направлении: квазициклические коды позволяют значительно уменьшить размер закрытого ключа.СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВВасиленко О.Н. Теоретико-числовые алгоритмы в криптографии. — Москва: МЦМНО, 2003. — С. 328. — ISBN 5-94057-103-4Pohlig S., Hellmann M. An improved algorithm for computing logarithms over GF(p) and its cryptographic significance. — IEEE Trans. Inform. Theory, V.5, 1978. — С. 106-110.Odlyzko A. M. Discrete logarithms in finite fields and their cryptographic significance // Advances in Crytology: Proceedings of EuroCrypt’84 /Thomas Beth, Norbert Cot, and IgemarIngemarsson, editors. Berlin: Springer-Verlag, 1984 (Lect. Notes in Computer Science; V. 209). P. 224-316.Марко Бальди, Марко Бодрато, Франко Чиаралук. Новый анализ криптосистемы Мак-Элиса на основе кодов QC-LDPC, БСК 2008, ЬКСБ 5229, стр. 246-262;БхаскарБисвас, Николас Сендриер. Внедрение криптосистемы Мак-Элиса: теория и практика. Исследовательский центр ШМА, Париж, Франция, 2008, LNCS 5299, рр. 47-62;Гордов Н.А. Криптосистемы Мак-Элиса и Нидеррайтера в атаках декодирования классической информации // Современные научныеисследования и инновации. 2020. № 6 [Электронный ресурс]. URL: http://web.snauka.ru/issues/ 2020/06/92527 (дата обращения: 10.04.2022);