Математические методы криптографии

Атака на криптосистему ECC2 и криптосистему Мак-Элиса, построенную на эллиптических кодах

Ю. Д. Шкуратов


Аннотация: Работа посвящена кодовым криптосистемам типа Мак-Элиса, которые потенциально могут быть использованы в качестве постквантовых. Рассматриваются модификации криптосистемы Мак-Элиса на алгеброгеометрических кодах, ассоциированных с эллиптической кривой, в частности, криптосистема ECC2. Предложен полиномиальный алгоритм, использующий операции произведения Шура — Адамара линейных кодов и вычисления дуального кода, позволяющий восстановить эллиптическую кривую и дивизор $D$ по порождающей матрице соответствующего эллиптического $[n,k]_{q}$-кода $\mathcal{C}_{\mathcal{L}}(D,kP_{\infty})$ при $3<k<(n-4)/{2}$. Вычисляется сложность этого алгоритма, составляющая $O((k^{2}+q^{2})n^{2})$ операций в конечном поле.

Ключевые слова: криптосистема Мак-Элиса, ECC2, алгеброгеометрические коды, АГ-коды, эллиптические коды.

УДК: 519.725

DOI: 10.17223/2226308X/18/38