Q (шифр)

Шаблон:Стиль статьи Q — блочный шифр с прямой структурой SP-сети c S-блоками. Q-шифр берет происхождение от шифров Rijndael и Serpent. Впервые он был представлен Лесли МакБрайд (Шаблон:Lang-en) на конкурсе, проводившимся проектом 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-битных подключ $K{W}_1,KA,KB,K_0,K_1,...,K_7,K{W}_2.$ Каждый раунд $r$ ($0\le r\le 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 K{W}_1,Roun{d}_0,...,Roun{d}_7,\oplus KA,Substitution(S),\oplus KB,\oplus K{W}_2$.

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

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

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

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

Ссылки

• Differential Cryptanalysis of QШаблон:Ref-en