Криптосистема ГПТ

Криптосистема ГПТ (Габидулина-Парамонова-Третьякова) — криптосистема с открытыми ключами, основанная на ранговых кодах, разработанная в 1991 году Э. М. Габидулиным, А. В. Парамоновым и О. В. Третьяковым на основе криптосистемы McEliece.

Данная криптосистема, в отличие от криптосистемы McEliece, более устойчива к атакам декодирования, а также имеет меньший размер ключа, что лучше подходит в условиях практического применения.

Большинство версий системы были взломаны Р. Овербеком.

Описание

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

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

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

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

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

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

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

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

Взлом

Автоморфизм Фробениуса 
Введем автоморфизм Фробениуса:  . Он обладает следующими свойствами:
 Для матрицы  над тем же полем 
 Для любого целого 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.

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