Q (шифр)

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

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

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

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

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

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

Алгоритм

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

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

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

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

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

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

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

Примечания

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. Источник  (неопр.). Дата обращения: 29 октября 2018. Архивировано 14 сентября 2018 года.
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 года.

Ссылки

• Differential Cryptanalysis of Q (англ.)