Q (шифр)

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

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

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

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

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

В шифре используются три линейные трансформации. Перестановка $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().$

Алгоритм

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$) состоит из:

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

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

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

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

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

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

Ссылки

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