Криптосистема ГПТ (Габидулина-Парамонова-Третьякова) — криптосистема с открытыми ключами, основанная на ранговых кодах[1], разработанная в 1991 году Э. М. Габидулиным, А. В. Парамоновым и О. В. Третьяковым[2] на основе криптосистемы McEliece.
Данная криптосистема, в отличие от криптосистемы McEliece, более устойчива к атакам декодирования, а также имеет меньший размер ключа[3], что лучше подходит в условиях практического применения.
Большинство версий системы были взломаны Р. Овербеком[4].
Описание
Открытый текст
В качестве открытого текста может использоваться любой
-вектор
,
.
Открытый ключ
Открытым ключом является порождающая матрица размера
:
,
где:
— порождающая матрица
кода с максимальным ранговым расстоянием
для длины кода
с количеством символов
, задающаяся матрицей следующей формы:
![{\displaystyle G_{k}={\begin{bmatrix}g_{1}&g_{2}&\cdots &g_{n}\\g_{1}^{[1]}&g_{2}^{[1]}&\cdots &g_{n}^{[1]}\\\vdots &\vdots &\ddots &\vdots \\g_{1}^{[k-1]}&g_{2}^{[k-1]}&\cdots &g_{n}^{[k-1]}\end{bmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/16d2f2b8a0367ce06839c2ae6899c4ad0683f314)
- где
— любой набор элементов расширенного поля
, линейно независимых над полем
.
- главная матрица
используется для исправления ошибок. Ошибки ранга не более
могут быть исправлены.
- Cтроковый скремблер
— невырожденная квадратная матрица порядка
над полем 
— матрица искажений размера
над полем
со столбцовым рангом
|
и рангом
|
.
- Матрица
имеет столбцовый ранг
|
.
- Столбцовый скремблер
— квадратная матрица порядка
над полем
.
может быть больше
, но
.
Закрытый ключ
В качестве закрытого ключа выступает набор
, а также алгоритм быстрого декодирования МРР-кода, в котором используется матрица проверки четности
, такая, что 
,- где
— элементы расширенного поля
, линейно независимые над основным полем 
- Матрица
не используется для расшифровки криптотекста и может быть удалена после вычисления закрытого ключа.
Оптимальные параметры кода
- Длина кода
, - Размерность
, - Ранговое расстояние кода

Шифрование
Соответствующий открытому тексту криптотекст вычисляется следующим образом:
,
где
— искусственный вектор ошибок ранга не выше
, причем
.
Дешифрование
Законный получатель, получая
, выполняет следующие действия:
- Вычисляет
![{\displaystyle G_{k}]+eP^{-1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cefdaf7ba38eff133994684322148d98d9e44f9e)
- Из
выделяет подвектор
, где
— подвектор 
- Применяет алгоритм быстрого декодирования для исправления ошибки

- Получает

- Восстанавливает

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





- В общем случае
. Равенство достигается, если
— матрица над основным полем 
Описание атаки Овербека[4]
- Криптоаналитик вычисляет расширенный открытый ключ из открытого ключа:
![{\displaystyle G_{ext,pub}={\begin{Vmatrix}G_{pub}\\\sigma (G_{pub})\\\cdots \\\sigma ^{u}(G_{pub})\end{Vmatrix}}={\begin{Vmatrix}S&[X&G_{k}]&P\\\sigma (S)&[\sigma (X)&\sigma (G_{k})]&P\\\cdots &\cdots &\cdots &\cdots \\\sigma ^{u}(S)&[\sigma ^{u}(X)&\sigma ^{u}(G_{k}]&P\end{Vmatrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b724c8912ea5edad0f219e72e772193714e9fc68)
- Здесь использовано свойство 7 автоморфизма Фробениуса:
, так как
— матрица над основным полем
.
- Переписывает эту матрицу как
,
- где
,
,
.
- Выбирает
. - Определяет матрицы:
, получаемая из
удалением последней строки,
, получаемая из
удалением первой строки.
- Определяет линейное отображение
:
по следующему правилу:
- если
, тогда 
- Записывает

- С помощью матричных преобразований приводит расширенный открытый ключ к виду:

- где
— порождающая матрица
МРР-кода.
- Пробует найти решение системы
,
- где
— вектор-строка над расширенным полем
длины 
- Представляет вектор
в виде:

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

- Полагая верным условие
, видим, что указанная выше система имеет только тривиальное решение
. Следовательно, первое уравнение из системы преобразуется к виду:
.
Это позволит найти первую строку матрицы проверки четности для кода с данной порождающей матрицей
. Следовательно, это решение взламывает описанную криптосистему за полиномиальное время. Атака Овербека требует
операций над полем
, так как каждый шаг атаки имеет сложность не выше кубической на
.
Примечания
- ↑ Габидулин Э. М. Теория кодов с максимальным ранговым расстоянием (недоступная ссылка) // Пробл. передачи информ. Архивная копия от 20 декабря 2016 на Wayback Machine — 1985. — Т. 21, вып. 1. — С. 3—16.
- ↑ Gabidulin E.M., Paramonov A.V., Tretjakov O.V. Ideals over a Non-commutative Ring and Their Application in Cryptology Архивная копия от 16 сентября 2018 на Wayback Machine // Advances in Cryptology Архивная копия от 3 июня 2018 на Wayback Machine — Eurocrypt ’91, LNCS 547, 1991, pp. 482—489.
- ↑ Khan E., Gabidulin E. M., Honary B., Ahmed H. Modified Niederreiter type of GPT Cryptosystem based on Reducible Rank Codes Архивная копия от 9 июня 2018 на Wayback Machine // et al. Des. Codes Cryptogr. (2014) 70: 231. — ISSN 0925-1022
- ↑ 1 2 Overbeck R. Structural Attacks for Public Key Cryptosystems based on Gabidulin Codes Архивная копия от 1 марта 2018 на Wayback Machine // Journal of Cryptology: volume 21, number 2, april 2008 — ISSN 0933-2790
Литература
- Габидулин Э. М., Пилипчук Н. И., Хонари Б., Рашван Х. Защита информации в сети со случайным сетевым кодированием // Пробл. передачи информ., 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.