Криптосистема ГПТ (Габидулина-Парамонова-Третьякова) — криптосистема с открытыми ключами, основанная на ранговых кодахГабидулин Э. М. Теория кодов с максимальным ранговым расстоянием // Пробл. передачи информ.  — 1985. — Т. 21, вып. 1. — С. 3—16., разработанная в 1991 году Э. М. Габидулиным, А. В. Парамоновым и О. В. ТретьяковымGabidulin E.M., Paramonov A.V., Tretjakov O.V. Ideals over a Non-commutative Ring and Their Application in Cryptology // Advances in Cryptology  — Eurocrypt ’91, LNCS 547, 1991, pp. 482—489. на основе криптосистемы McEliece.

Данная криптосистема, в отличие от криптосистемы McEliece, более устойчива к атакам декодирования, а также имеет меньший размер ключаKhan E., Gabidulin E. M., Honary B., Ahmed H. Modified Niederreiter type of GPT Cryptosystem based on Reducible Rank Codes // et al. Des. Codes Cryptogr. (2014) 70: 231. — ISSN 0925-1022, что лучше подходит в условиях практического применения.

Большинство версий системы были взломаны Р. ОвербекомOverbeck R. Structural Attacks for Public Key Cryptosystems based on Gabidulin Codes // Journal of Cryptology: volume 21, number 2, april 2008 — ISSN 0933-2790.

Описание

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

Открытый ключ Открытым ключом является порождающая матрица размера : ,

где:  — порождающая матрица кода с максимальным ранговым расстоянием для длины кода с количеством символов , задающаяся матрицей следующей формы:

где  — любой набор элементов расширенного поля , линейно независимых над полем . главная матрица используется для исправления ошибок. Ошибки ранга не более могут быть исправлены. Строковый скремблер  — невырожденная квадратная матрица порядка над полем  — матрица искажений размера над полем со столбцовым рангом | и рангом | . Матрица имеет столбцовый ранг | . Столбцовый скремблер  — квадратная матрица порядка над полем . может быть больше , но .

Закрытый ключ В качестве закрытого ключа выступает набор , а также алгоритм быстрого декодирования МРР-кода, в котором используется матрица проверки четности , такая, что , где  — элементы расширенного поля , линейно независимые над основным полем Матрица не используется для расшифровки криптотекста и может быть удалена после вычисления закрытого ключа.

Оптимальные параметры кода Длина кода , Размерность , Ранговое расстояние кода

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

Дешифрование Законный получатель, получая , выполняет следующие действия: Вычисляет Из выделяет подвектор , где  — подвектор Применяет алгоритм быстрого декодирования для исправления ошибки Получает Восстанавливает

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

Взлом

Автоморфизм Фробениуса Введем автоморфизм Фробениуса: . Он обладает следующими свойствами: Для матрицы над тем же полем Для любого целого s:

В общем случае . Равенство достигается, если  — матрица над основным полем

Описание атаки Овербека Криптоаналитик вычисляет расширенный открытый ключ из открытого ключа:

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

где  — порождающая матрица МРР-кода.

Пробует найти решение системы , где  — вектор-строка над расширенным полем длины Представляет вектор в виде:

где  — подвектор длины , а  — длины Теперь система уравнений эквивалентна следующей:

Полагая верным условие , видим, что указанная выше система имеет только тривиальное решение . Следовательно, первое уравнение из системы преобразуется к виду: . Это позволит найти первую строку матрицы проверки четности для кода с данной порождающей матрицей . Следовательно, это решение взламывает описанную криптосистему за полиномиальное время. Атака Овербека требует операций над полем , так как каждый шаг атаки имеет сложность не выше кубической на .

Примечания

Литература Габидулин Э. М., Пилипчук Н. И., Хонари Б., Рашван Х. Защита информации в сети со случайным сетевым кодированием // Пробл. передачи информ., 2013, том 49, выпуск 2, 92-106 Gadouleau M., Yan Zh. Security of GPT-type cryptosystems // Proc. 2006 IEEE Int. Sympos. on Information Theory (ISIT’2006). — ISIT.2006.261627 Rashwan H., Gabidulin E.M., Honary B. A smart approach for GPT Cryptosystem Based on Rank Codes // Proc. 2010 IEEE Int. Sympos. on Information Theory (ISIT’2010). Austin, Texas, USA. June 13-18, 2010. P. 2463—2467. Kshevetskiy A.S. Security of GPT-like cryptosystems based on linear rank codes // Signal Design and Its Applications in Communications, 2007. IWSDA 2007. On page(s): 143—147. Ourivski A. V., Gabidulin E. M. Column Scrambler for the GPT Cryptosystem // Discrete Applied Mathematics.128(1): 207—221 (2003). Overbeck R. Extending Gibson’s attacks on the GPT cryptosystem // In Proc. of WCC 2005, volume 3969 of LNCS, pp. 178–188, Springer Verlag,2006.

Категория:Криптография с открытым ключом