Q (шифр)

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

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

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

Общие сведенияПравить

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

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

АлгоритмПравить

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

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

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

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

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

КриптоанализПравить

В работе^[1] показано, что шифр не устойчив к линейному криптоанализу, с вероятностью 98,4 % 128-битный ключ будет восстановлен из $\text{[math]}$ $\text{[math]}$ $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. Дата обращения 2018-09-13. Архивная копия от 14 сентября 2018 на Wayback Machine
↑ ¹ ² Сергей Панасенко. Алгоритмы шифрования. Специальный справочник. — Санкт-Петербург: БХВ-Петербург, 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. Дата обращения 2018-09-13. Архивная копия от 14 сентября 2018 на Wayback Machine

[: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]