Просмотр кода страницы Q (шифр)

{{стиль статьи|дата=2018-10-29}}
'''Q''' — [[блочный шифр]] с прямой структурой [[SP-сеть|SP-сети]] c S-блоками. Q-шифр берет происхождение от шифров [[Advanced Encryption Standard|Rijndael]] и [[Serpent]]. Впервые он был представлен Лесли МакБрайд ({{lang-en|Leslie McBride}}) на конкурсе, проводившимся проектом [[NESSIE]]. Алгоритм использует 128-битный блок данных в виде байтового массива <math>4\times4</math>, над которым и проводятся операции<ref name=":0" />.

Теоретически [[алгоритм]] не имеет ограничения на размер используемых ключей шифрования. В рамках конкурса NESSIE рассматривалось только три фиксированных размера: 128, 192 и 256 битов<ref name=":1" />.

Алгоритм подвержен как дифференциальному, так и линейному [[криптоанализ]]у<ref>{{Статья|автор=Vincent Rijmen, Michal Misztal, Vladimir Furman, Eli Biham|заглавие=Differential Cryptanalysis of Q|ссылка=https://link.springer.com/chapter/10.1007/3-540-45473-X_15|язык=en|издание=Fast Software Encryption|издательство=Springer, Berlin, Heidelberg|год=2001-04-02|страницы=174–186|isbn=9783540438694, 9783540454731|doi=10.1007/3-540-45473-X_15|archivedate=2018-09-14|archiveurl=https://web.archive.org/web/20180914022557/https://link.springer.com/chapter/10.1007/3-540-45473-X_15}}</ref>.

== Общие сведения ==
Q использует три различных s-блока. Первый <math>8\times8</math> s-блок, называющийся S, и два блока <math>4\times4</math>, A и B (A взят из алгоритма Serpent, B — «Serpent-подобный»). Каждая стадия подстановки использует многократные копии s-блоков параллельно для обработки 128-битного входа (16 копий S и 32 копии A и B).<ref name=":0" />

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

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

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

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

Расшифровывание происходит аналогично шифрованию с небольшими изменениями<ref name=":1">{{Книга|автор=Сергей Панасенко|заглавие=Алгоритмы шифрования. Специальный справочник|ответственный=|издание=|место=Санкт-Петербург|издательство=БХВ-Петербург|год=2009|страницы=374—375|страниц=576|isbn=978-5-9775-0319-8|isbn2=}}</ref>:
# Меняются местами операции 5 и 6 в каждом раунде.
# Для 2, 4 и 6 — используются инверсные операции.
# Ключи <math>K_r</math> используются в обратной последовательности.

== Криптоанализ ==
В работе<ref name=":0">{{cite conference
| author=L. Keliher, H. Meijer, and Stafford Tavares
| date=12 September 2001
| title=High probability linear hulls in Q
| conference=Proceedings of Second Open [[NESSIE]] Workshop
| location=Surrey, England
| url=https://www.researchgate.net/publication/2408626
| accessdate=2018-09-13
| archive-date=2018-09-14
| archive-url=https://web.archive.org/web/20180914022753/https://www.researchgate.net/publication/2408626
| url-status=live
}} {{Cite web |url=https://www.researchgate.net/publication/2408626 |title=Источник |access-date=2018-10-29 |archive-date=2018-09-14 |archive-url=https://web.archive.org/web/20180914022753/https://www.researchgate.net/publication/2408626 |deadlink=unfit }}</ref> показано, что шифр неустойчив к линейному криптоанализу, с вероятностью 98,4 % 128-битный ключ будет восстановлен из <math>2^{97}</math> известных пар открытого текста — шифротекста.

== Примечания ==
{{примечания}}

== Ссылки ==
* [https://link.springer.com/chapter/10.1007/3-540-45473-X_15 Differential Cryptanalysis of Q]{{ref-en}}
{{изолированная статья|дата=2018-10-29}}
[[Категория:Блочные шифры]]