Перейти к содержанию

Q (шифр)

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

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

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

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

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

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

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

Алгоритм

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

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

Полный алгоритм состоит из [math]\displaystyle{ \oplus KW_1, Round_0, ..., Round_7, \oplus KA, Substitution(S), \oplus KB, \oplus KW_2 }[/math].

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

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

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

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

Примечания

  1. ↑ 1,0 1,1 1,2 1,3 L. Keliher, H. Meijer, and Stafford Tavares. High probability linear hulls in Q // (Proceedings of Second Open NESSIE Workshop). — Surrey, England. Архивная копия от 14 сентября 2018 на Wayback Machine
  2. ↑ 2,0 2,1 Сергей Панасенко. Алгоритмы шифрования. Специальный справочник. — Санкт-Петербург: БХВ-Петербург, 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 года.

Ссылки

Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Q_(шифр)&oldid=13369553