Q (шифр)

Q — блочный шифр с прямой структурой SP-сети c S-блоками. Q-шифр основывается на шифрах Rijndael и Serpent. Впервые он был представлен Лесли МакБрайд (англ. Leslie McBride) на конкурсе, проводившимся проектом NESSIE. Алгоритм использует 128-битный блок данных в виде байтового массива $4\times 4$ , над которым и проводятся операции^[1].

Теоретически алгоритм не имеет ограничения на размер используемых ключей шифрования. В рамках конкурса NESSIE рассматривалось только три фиксированных размера: 128, 192 и 256 битов^[2].

Алгоритм подвержен как дифференциальному, так и линейному криптоанализу^[3].

Общие сведения

Q использует три различных s-блока. Первый $8\times 8$ s-блок, называющийся S, и два блока $4\times 4$ A и B (A взят из алгоритма Serpent, B — «Serpent-подобный»). Каждая стадия подстановки использует многократные копии s-блоков параллельно для обработки 128-битного входа (16 копий S и 32 копии A и B).^[1]

В шифре используются три линейные трансформации. Перестановка $P$ работает на 128-битном блоке, представленном в виде четырёх 32-битных слов $W_{0},W_{1},W_{2},W_{3}$ следующим образом: $W_{0}$ не изменяется; $W_{1},W_{2},W_{3}$ поворачиваются на один байт, два байта и три байта соответственно. Другие две линейные трансформации назовём $PreSerpent()$ и $PostSerpent()$ , так как они применяются до и после блоков A и B. $PreSerpent()$ отправляет биты $W_{0}$ в первые биты 32-битных идентичных копий s-блока $4\times 4$ , биты $W_{1}$ — во вторые биты s-блоков и т. д. $PostSerpent()$ — просто инверсия $PreSerpent().$ ^[1]

Алгоритм

Q-шифр может иметь различные размеры ключей. Рассмотрим шифр с 128-битным ключом и с 8 полными раундами. Для усиленной защиты применяются 9 раундов. Алгоритм «key-scheduling algorithm» или «KSA» генерирует 12 128-битных подключ $KW_{1},KA,KB,K_{0},K_{1},...,K_{7},KW_{2}.$ Каждый раунд $r$ ( $0\leq r\leq 7$ ) состоит из:

$\oplus KA$ — первое наложение ключа $KA$ . Выполняется побитовое исключающее «или» (XOR), применяющееся к каждому биту обрабатываемого блока и соответствующему биту расширенного ключа.
Подстановка S ( $Substitution(S)$ ) — взята из алгоритма Rijndael.
$\oplus KB$ — второе наложение ключа $KB$ .
$PreSerpent(),A,PostSerpent()$ — операция унаследована от алгоритма Serpent.
$\oplus K_{r}$ — третье наложение ключа $K_{r}.$ Подключ $K_{r}$ уникален для каждого раунда.
Перестановка $P$ .
$PreSerpent(),B,PostSerpent()$ .

Полный алгоритм состоит из $\oplus KW_{1},Round_{0},...,Round_{7},\oplus KA,Substitution(S),\oplus KB,\oplus KW_{2}$ .

Расшифровывание происходит аналогично шифрованию с небольшими изменениями^[2]:

Меняются местами операции 5 и 6 в каждом раунде.
Для 2, 4 и 6 — используются инверсные операции.
Ключи $K_{r}$ используются в обратной последовательности.

Криптоанализ

В работе^[1] показано, что шифр неустойчив к линейному криптоанализу, с вероятностью 98,4 % 128-битный ключ будет восстановлен из $2^{97}$ известных пар открытого текста — шифротекста.

Примечания

↑ ¹ ² ³ ⁴ L. Keliher, H. Meijer, and Stafford Tavares (12 September 2001). High probability linear hulls in Q. Proceedings of Second Open NESSIE Workshop. Surrey, England. Архивировано 14 сентября 2018. Дата обращения: 13 сентября 2018.{{cite conference}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка) Источник (неопр.). Дата обращения: 29 октября 2018. Архивировано 14 сентября 2018 года.
↑ ¹ ² Сергей Панасенко. Алгоритмы шифрования. Специальный справочник. — Санкт-Петербург: БХВ-Петербург, 2009. — С. 374—375. — 576 с. — ISBN 978-5-9775-0319-8.
↑ Vincent Rijmen, Michal Misztal, Vladimir Furman, Eli Biham. Differential Cryptanalysis of Q (англ.) // Fast Software Encryption. — Springer, Berlin, Heidelberg, 2001-04-02. — P. 174–186. — ISBN 9783540438694, 9783540454731. — doi:10.1007/3-540-45473-X_15. Архивировано 14 сентября 2018 года.

Ссылки

Differential Cryptanalysis of Q (англ.)

[:0-1] ¹ ² ³ ⁴ L. Keliher, H. Meijer, and Stafford Tavares (12 September 2001). High probability linear hulls in Q. Proceedings of Second Open NESSIE Workshop. Surrey, England. Архивировано 14 сентября 2018. Дата обращения: 13 сентября 2018.{{cite conference}}: Википедия:Обслуживание CS1 (множественные имена: authors list) (ссылка) Источник (неопр.). Дата обращения: 29 октября 2018. Архивировано 14 сентября 2018 года.

[:1-2] ¹ ² Сергей Панасенко. Алгоритмы шифрования. Специальный справочник. — Санкт-Петербург: БХВ-Петербург, 2009. — С. 374—375. — 576 с. — ISBN 978-5-9775-0319-8.

[3] Vincent Rijmen, Michal Misztal, Vladimir Furman, Eli Biham. Differential Cryptanalysis of Q (англ.) // Fast Software Encryption. — Springer, Berlin, Heidelberg, 2001-04-02. — P. 174–186. — ISBN 9783540438694, 9783540454731. — doi:10.1007/3-540-45473-X_15. Архивировано 14 сентября 2018 года.

[1]

[2]

[3]