Алгоритмы шифрования – участники конкурса NESSIE. Часть 2


Вторая и третья части статьи посвящены 128-битным алгоритмам блочного шифрования, не вышедшим во второй раунд конкурса NESSIE. Начнем с алгоритма Anubis.

Алгоритм Anubis

Блочный шифр Anubis разработан специально для участия в конкурсе NESSIE интернациональным дуэтом авторов: бельгийцем Винсентом Риджменом (Vincent Rijmen) и бразильцем Пауло Баррето (Paulo S.L.M. Barreto).

Алгоритм назван в честь древнеегипетского бога Анубиса – бога бальзамирования (embalming) и погребения (entombment); к его ведению авторы алгоритма решили отнести и криптографию [1].

Anubis шифрует данные блоками по 128 бит с использованием ключа размером от 128 до 320 бит; размер ключа должен быть кратен 32 битам.

Данный алгоритм продолжает серию алгоритмов, соавтором которых является Винсент Риджмен: Square, Shark и Rijndael (подробное описание этих алгоритмов на русском языке можно найти, например, в статьях [17], [18] и [19], соответственно). Все эти алгоритмы объединяет их относительно редко встречающаяся (напротив, частая среди алгоритмов – участников конкурса NESSIE) структура типа «квадрат» (square) – см. статью «Назначение и структура алгоритмов шифрования» – и весьма схожий набор выполняемых преобразований.

Структура алгоритма

Алгоритм представляет блок шифруемых данных в виде 16-байтового массива, который для удобства описания представлен виде квадрата 4 * 4 байт. В каждом раунде алгоритма выполняются следующие действия [1]:

  1. Табличная замена , выполняемая, согласно следующей таблице S (см. рис. 1):
    Операция y алгоритма Anubis
    Рис. 1. Операция алгоритма Anubis


    A7D3E671D0AC4D79
    3AC991FC1E4754BD
    8CA57AFB63B8DDD4
    E5B3C5BEA9880CA2
    39DF29DA2BA8CB4C
    4B22AA244170A6F9
    5AE2B0367DE433FF
    6020088B5EAB7F78
    7C2C57D2DC6D7E0D
    5394C32827065FAD
    675C55480E52EA42
    5B5D305851593C4E
    388A7214E7C6DE50
    8E92D17793459ACE
    2D0362B6B9BF966B
    3F0712AE4034463E
    DBCFECCCC1A1C0D6
    1DF4613B10D868A0
    B10A696C49FA76C4
    9E9B6E99C2B798BC
    8F851FB4F8112E00
    251C2A3D054F7BB2
    3290AF19A3F7739D
    1574EECA9F0F1B75
    86849C4A971A65F6
    ED09BB2683EB6F81
    046A430117E187F5
    8DE3238044166621
    FED531D935180264
    F2F156CD82C8BAF0
    EFE9E8FD89D7C7B5
    A42F95130BF3E037

    Значения таблицы выбраны псевдослучайным образом с учетом необходимости ее соответствия следующему соотношению:

    S[S[x]] = x.
  2. Операция – байтовая перестановка, простейшим образом преобразующая строку обрабатываемого блока ключевой информации в столбец (см. рис. 2):
    Операция алгоритма Anubis
    Рис. 2. Операция алгоритма Anubis

    bi,j = aj,i,

    где ai,j и bi,j – байты массива данных до и после выполнения текущей операции, соответственно.
  3. Операция , представляющая собой умножение массива на фиксированную матрицу H (см. рис. 3):
    Операция алгоритма Anubis
    Рис. 3. Операция алгоритма Anubis


    1246
    2164
    4612
    6421

    Умножение выполняется в конечном поле GF(28).

  4. Наложение ключа r-го раунда k[r] (процедура расширения ключа будет подробно описана далее); выполняется побитовой логической операцией «исключающее или» (XOR), применяемой к каждому биту массива данных и соответствующему биту k[r] (см. рис. 4):
    Операция алгоритма Anubis
    Рис. 4. Операция алгоритма Anubis

    bi,j = ai,j k[r]i,j.

    Данная операция обозначается как .

Перечисленные операции выполняются в каждом раунде в указанной последовательности , за исключением последнего раунда алгоритма, в котором не выполняется операция . Кроме того, перед первым раундом выполняется входное отбеливание данных, путем наложения на шифруемый блок операцией XOR нулевого подключа.

Стоит отметить, что все перечисленные операции являются обратными самим себе, соответственно, расшифрование выполняется с помощью тех же операций в том же порядке, что и при зашифровании. Меняется только порядок использования подключей на обратный.

Число раундов алгоритма R зависит от размера ключа шифрования и определяется следующим образом:

R = 8 + N,

где N – размер ключа в 32-битных фрагментах.

Некоторые криптоаналитики считают, что число раундов в алгоритме Anubis несколько завышено, видимо, с целью обеспечить более высокий запас криптостойкости [3].

Процедура расширения ключа

Процедура расширения ключа достаточно проста и основана, практически, на той же последовательности операций, которые применяются в раундах алгоритма. Расширение ключа выполняется следующим образом: сначала исходный ключ шифрования K представляется в виде байтового массива 4 * 4 (что обозначается как KI0), после чего в цикле выполняются следующие операции:

  1. Итеративно вычисляются остальные промежуточные ключи KI1...KIR:

    KIj = f(KIj-1),

    где f() – совокупность операций , , и ; в операции в качестве ключа раунда используется соответствующая из констант c[r], которые, в свою очередь, определяются следующим образом:

    c[r]0,j = S[4 * (r – 1) + j]

    для j = 0...3 (см. описание операции ). Остальные байты c[r]i,j являются нулевыми.

    Операция – циклический сдвиг столбцов таблицы вниз по следующему простому правилу: j-й столбец сдвигается на j позиций (см. рис.5).

    Операция алгоритма Anubis
    Рис. 5. Операция алгоритма Anubis


  2. На основе предварительных ключей вычисляются подключи k0...kr:

    kr = g(KIr),

    где функция g() представляет собой последовательное выполнение следующих операций: .

    Операции и были описаны выше, а представляет собой умножение блока на фиксированную матрицу V (аналогично операции – см. рис. 3), определенную следующим образом:

    1111
    1248
    1636216
    18640

    Стоит отметить, что при зашифровании данных процедура расширения ключа позволяет вычислять ключи «на лету», т.е. по мере необходимости. Однако, при расшифровании необходимо полностью выполнить расширение ключа до начала преобразований.

    Достоинства и недостатки алгоритма

    Прежде всего, стоит сказать, что на конкурсе NESSIE была рассмотрена нескоько модифицированная версия алгоритма Anubis, отличие которой от описанной здесь состояло лишь в операции . Модифицированная операция вместо одной табличной замены 8 * 8 бит выполняла 3 уровня табличных замен 4 * 4. Данная модификация произведена для упрощения аппаратной реализации алгоритма [12].

    Anubis был признан одним из наиболее быстродействующих алгоритмов шифрования (из участников конкурса) [13]. Еще одно явное достоинство алгоритма – отсутствие проблем с криптостойкостью [14]. Однако, злую шутку с алгоритмом Anubis сыграло его сходство с алгоритмом Rijndael (который, как известно, является новым стандартом шифрования США под названием AES [7] – см. статью «Алгоритмы шифрования – финалисты конкурса AES»), который также рассматривался в рамках конкурса NESSIE. Эксперты конкурса посчитали, что при таком явном сходстве Anubis не может иметь настолько серьезных преимуществ перед алгоритмом Rijndael, которые позволили бы ему выиграть у Rijndael в финале конкурса NESSIE [13, 15]. Поэтому Anubis не выбран во второй этап конкурса.

    Алгоритм Grand Cru

    Алгоритм Grand Cru разработан специально для участия в конкурсе NESSIE. Автор алгоритма – Йохан Борст (Johan Borst) из Католического Университета г. Лювен, Бельгия.

    Как и алгоритм Anubis, Grand Cru имеет структуру «квадрат». Данный алгоритм основан на алгоритме Rijndael, разработанном, как известно, Джоан Деймен (Joan Daemen) и упомянутым выше Винсентом Риджменом. Несомненно, тот факт, что Rijndael выиграл конкурс AES и в настоящее время является стандартом шифрования США AES, сподвигнул некоторых разработчиков алгоритмов шифрования на конструирование блочных шифров на его основе. Один из них – Anubis – был рассмотрен выше. Grand Cru – второй пример; фактически, он является глубокой модификацией алгоритма Rijndael.

    Как известно, среди четырех преобразований данных в каждом раунде алгоритма Rijndael существует только одна операция (наложение подключа операцией XOR), выполняющая зависящие от ключа преобразования [7]. По мнению автора алгоритма Grand Cru, увеличение количества ключевых преобразований в раунде алгоритма усилит криптостойкость алгоритма при том же количестве раундов или позволит уменьшить количество раундов (чем увеличить скорость шифрования) при заданном уровне криптостойкости. Соответственно, раунд Grand Cru – это, фактически, раунд Rijndael с добавлением двух ключевых операций вместо одной бесключевой [4].

    Алгоритм Grand Cru шифрует данные блоками по 128 бит с использованием только 128-битного ключа шифрования.

    Структура алгоритма

    Как было сказано выше, алгоритм имеет структуру «квадрат»: аналогично рассмотренному выше алгоритму Anubis, при шифровании данные представляются в виде таблицы 4 * 4 байт. Каждый раунд подразумевает выполнение следующих операций:

    1. Наложение фрагмента ключа r-го раунда k[r, 0] (см. ниже), которое выполняется с помощью операции XOR полностью аналогично операции алгоритма Anubis – см. рис. 4 (однако, в спецификации алгоритма Grand Cru [4] используется обратная нумерация столбцов – справа налево – как на рис. 6). Данная операция в алгоритме Grand Cru также обозначается как .

      Первый этап перестановки алгоритма Grand Cru
      Рис. 6. Первый этап перестановки алгоритма Grand Cru

      Как было сказано выше, раунд алгоритма содержит 3 операции с участием фрагментов расширенного ключа. Обозначим эти фрагменты следующим образом:

      • k[r, 0] – 128-битный фрагмент ключа раунда k[r] для наложения ключа,
      • k[r, 1] – 40-битный фрагмент для описанной ниже операции ,
      • k[r, 2] – 48-битный фрагмент для операции .
    2. Табличная замена , замещающая каждый байт массива согласно следующей таблице S:

      99124119123242107111197
      48110343254215171118
      2021302011252508971240
      173212162175156164114192
      183253147385463247204
      521652292411132164921
      419935195241505154
      71812822623539178117
      913144262711090160
      82592141794122747132
      8320902373225217791
      10620319057747688207
      208239170251677751133
      6924921278060159168
      811636414314615756245
      1881822183316255243210
      2051219236951516823
      196167126611009325115
      96129792203442144136
      70238184202229411219
      2245058107363692
      19421117298145149228121
      2312005510914121378169
      108862442341011221748
      186120374628166180198
      2322211163175189139138
      1126218110272324614
      97538718513419329158
      22524815217105217142148
      155301352332068540223
      1401611371319123066104
      6515345151768418722

      Данная операция также аналогична (но с другой таблицей замен) операции алгоритма Anubis – см. рис. 1.

    3. Зависящая от ключа перестановка . Использует 5-байтный фрагмент расширенного ключа k[r, 1], причем процедура расширения ключа гарантирует, что значение каждого байта k[r, 1] лежит в диапазоне от 1 до 24 включительно. Перестановка выполняется в 5 этапов:
      • На первом этапе выполняется перестановка строк массива данных. Для этого по первому байту ключа k[r, 1] (обозначим его значение как x) из следующей таблицы выбирается константа tx:

        xtx
        178
        236
        32D
        4C9
        593
        672
        74B
        89C
        987
        1063
        11D2
        1239
        138D
        141E
        15E4
        16B4
        176C
        18D8
        19E1
        20C6
        2127
        22B1
        234E
        241B

        tx представляется в виде четырех 2-битных значений tx[0]...tx[3]; подбор констант tx гарантирует, что значения tx[0]...tx[3] представляют собой последовательность из неповторяющихся значений от 0 до 3 включительно, например, для x = 1:

        tx[0] = 1,
        tx[1] = 3,
        tx[2] = 2,
        tx[3] = 0.

        Перестановка строк состоит в том, что i-я строка массива данных заменяется строкой, номер которой определяется значением tx[i] (см. пример для x = 1 на рис. 6).

      • Со второго по пятый этапы выполняют перестановку байт одного из столбцов массива данных: i-й этап переставляет байты i-2-го столбца, руководствуясь значением tx, выбираемым из приведенной выше таблицы согласно x – значению i-го байта ключа k[r, 1]. Перестановка байт выполняется абсолютно аналогично описанной выше перестановке строк – см. пример для этапа 2 и x = 2 на рис. 7.
        Второй этап перестановки алгоритма Grand Cru
        Рис. 7. Второй этап перестановки алгоритма Grand Cru
    4. Операция – умножение обрабатываемой таблицы на фиксированную матрицу H – аналогично одноименной операции Anubis (см. рис. 3). Матрица H унаследована от алгоритма Rijndael, в котором она определена следующим образом [7]:

      2311
      1231
      1123
      3112
    5. Зависящее от ключа вращение (операция ) каждого байта массива на переменное число бит, определяемое значениями соответствующих бит фрагмента ключа r-го раунда k[r, 2] (см. рис. 8):

      Операция алгоритма Grand Cru
      Рис. 8. Операция алгоритма Grand Cru

      bi,j = ai,j <<< xi,j,

      где в качестве xi,j используются значения трех последовательных бит фрагмента k[r, 2] в соответствии со следующей таблицей:

      ijИспользуемые биты k[r, 2]
      3345, 46, 47
      3242, 43, 44
      3139, 40, 41
      3036, 37, 38
      2333, 34, 35
      2230, 31, 32
      2127, 28, 29
      2024, 25, 26
      1321, 22, 23
      1218, 19, 20
      1115, 16, 17
      1012, 13, 14
      039, 10, 11
      026, 7, 8
      013, 4, 5
      000, 1, 2

    Таким образом, раунд алгоритма состоит из последовательно выполняемых операций: . Кроме того, перед первым по порядку (при зашифровании раунды нумеруются от 8 до 0) раундом выполняются операции и (составляющие предварительное преобразование), которые будут подробно описаны ниже. После последнего раунда выполняется заключительное преобразование – последовательность операций: , где -1 – операция, обратная к , также подробно описана ниже. Происхождение фрагментов расширенного ключа, используемых в ключевых операциях предварительного и заключительного преобразований, будет приведено в описании процедуры расширения ключа.

    Операции , выполняемые перед первым и после последнего раунда алгоритма, представляют собой входное и выходное отбеливание данных соответственно. Данные операции накладывают на обрабатываемый блок данных соответствующие фрагменты ключа (обозначим их kwi и kwo) с помощью операции сложения по модулю 256 (см. рис. 9).

    Операция алгоритма Grand Cru
    Рис. 9. Операция алгоритма Grand Cru

    Например, для входного отбеливания:

    bi,j = ai,j + kwii,j mod 256.

    представляет собой операцию бесключевого рассеивания данных и выполняется в два этапа:

    1. В цикле по n от 0 до 15 выполняется следующее действие:

      bn+1 mod 16 = a n+1 mod 16 S(an),

      где ax и bx – значения x-го байта данных до и после выполнения текущего действия соответственно (в данном случае блок данных представляется не в виде таблицы, а в виде последовательности байт).

    2. В цикле по n1 от 0 до 15 выполняется цикл по n2 от 0 до 15, в котором выполняется следующее действие:

      bn2 = an2 S(an1).

      Данное действие не выполняется при n2 = n1.

    Обратная к операция -1 определена так:

    1. В цикле по n1 от 15 до 0 выполняется цикл по n2 от 15 до 0 (кроме шага, в котором n2 = n1), в котором выполняется следующее действие:

      bn2 = an2 S(an1).
    2. В цикле по n от 0 до 15 выполняется следующее действие:

      bn+1 mod 16 = a n+1 mod 16 S(an).

    Расшифрование

    Расшифрование выполняется применением обратных операций в обратной последовательности:

    1. Обратное заключительное преобразование: , где – обратные операции к , , и соответственно и будут описаны ниже (обратная операция к эквивалентна самой операции ).
    2. 9 раундов (от 0-го до 8-го), в каждом из которых выполняется следующая последовательность действий: , где -1 – операция, обратная к .
    3. Обратное предварительное преобразование, состоящее из двух операций: -1 и -1.

    -1 выполняет наложение фрагментов расширенного ключа kwo и kwi путем вычитания по модулю 256, например:

    bi,j = ai,j - kwii,j mod 256.

    -1 выполняется аналогично операции , однако, вращение каждого байта блока данных выполняется не влево, а вправо:

    bi,j = ai,j >>> xi,j.

    -1 – обратная перестановка относительно операции – ее этапы выполняются в обратной последовательности; кроме того, в каждом этапе выполняется обратная перестановка.

    -1 аналогична прямой операции -1, но замена выполняется с помощью обратной таблицы S-1.

    -1 представляет собой умножение блока данных на обратную к H матрицу H-1, которая определена так:

    EBD9
    9EBD
    D9EB
    BD9E

    Расширение ключа

    Как видно из описания алгоритма шифрования, для выполняемых преобразований требуется достаточно большое количество фрагментов расширенного ключа различного размера. Поэтому процедура расширения ключа достаточно сложна3.

    Прежде всего, вычисляется последовательность промежуточных ключей K0...K3 следующим образом:

    1. 128-битный исходный ключ шифрования представляется в виде четырех столбцов, которые обозначаются K0’...K3.
    2. Формируется последовательность столбцов K4’...K15 путем следующих действий:

      K’i = K’i-4 G(R(K’i-1) ci/4),

      если i кратно четырем, иначе:

      K’i = K’i-4 K’i-1.

      Функция R() представляет собой побайтное вращение обрабатываемого столбца на 1 байт вверх.

      Функция G() обрабатывает каждый байт столбца с помощью описанной выше таблицы замен S, т.е. x-й байт столбца ax заменяется значением S(ax).

      Модифицирующие константы cx взяты из алгоритма Rijndael, где они определены согласно следующей таблице:

      xcx
      11
      22
      34

      В принципе, в алгоритме может использоваться ключ шифрования, больший 128 бит, но не превышающий 512 бит и кратный 32 битам. В этом случае последовательность K0’...K15 заполняется аналогичным образом 32-битными фрагментами ключа шифрования, насколько это возможно, а недостающие столбцы рассчитываются согласно приведенным выше формулам.

    3. Из столбцов, рассчитанных на предыдущем шаге, формируется последовательность промежуточных ключей K0...K3:

      Ki = (K’4i+3 | K’4i+2 | K’4i+1 | K’4i).

    Совокупность преобразований, используемых для получения промежуточного ключа Ki из исходного ключа шифрования (обозначим его KU) обозначим следующим образом:

    Ki = F(KU, i).

    В дальнейшем, с помощью аналогичных преобразований вычисляются необходимые подключи:

    1. Для операции требуются 9 128-битных подключей k[0, 0]...k[8, 0] – по одному для каждого раунда алгоритма, а также 2 подключа (k[9, 0] и k[10, 0]), поочередно используемые в заключительном преобразовании (в обратном заключительном преобразовании эти два подключа используются в обратном порядке). Данные 11 подключей вычисляются на основе промежуточного ключа K0 следующим образом:

      k[i, 0] = F(K0, i).
    2. Операция использует два 128-битных подключа kwi и kwo, которые вычисляются так:

      kwi = F(K3, 0),
      kwo = F(K3, 1).

      При расшифровании kwi и kwo применяются в обратном порядке.

    3. Для операции требуются 48-битные подключи k[0, 2]...k[8, 2] – по одному для каждого раунда, а также k[9, 2] для заключительного преобразования. Эти подключи вычисляются следующим образом: для каждого i = 0...9 выполняются следующие действия:
      • вычисляется еще один промежуточный ключ:

        K = F(K2, i);
      • вычисляется k[i, 2]:

        k[i, 2] = LSB3(K15) | LSB3(K14) | ... | LSB3(K0),

        где Kxx-й байт промежуточного ключа K,
        | – операция конкатенации,
        а LSB3(X) – три младших бита значения X.

    4. Для операции требуется 10 40-битных подключей: k[0, 1]...k[8, 1] для 9 раундов алгоритма и k[9, 1] для заключительного преобразования. Эти подключи для i = 0...9 вычисляются так:
      • вычисляется промежуточный ключ:

        K = F(K1, i);
      • K представляется в виде байтового массива из 16 элементов: K0...K15.
      • Из данного массива набираются первые 5 байт из тех, значения которых попадают в требуемый диапазон: от 1 до 24. Если в массиве таких байт меньше пяти, недостаточное количество набирается с начала массива, в качестве значения байта ключа берется остаток от деления значения используемого байта массива на 16 (вместо 0 используется значение 16).

    Достоинства и недостатки алгоритма

    Как видно из приведенного выше описания алгоритма Grand Cru, данный алгоритм является весьма сложным; причем, сложным и запутанным выглядит как шифрование, так и процедура расширения ключа. Из избыточной сложности алгоритма следует тот факт, что алгоритм Grand Cru оказался самым медленным (причем, с огромным отрывом от быстродействия большей части других алгоритмов) среди всех участников конкурса [14].

    В процессе изучения алгоритма в рамках конкурса NESSIE в нем не было обнаружено каких-либо слабостей, и, соответственно, каких-либо атак на данный алгоритм [16]. Тем не менее, эксперты конкурса посчитали, что возможно высокая (но недоказанная) криптостойкость данного алгоритма не компенсирует ужасающе низкой скорости шифрования, поэтому Grand Cru не был выбран во второй раунд конкурса [13].

    Алгоритм Noekeon

    Алгоритм Noekeon разработан в 2000 г. коллективом разработчиков из Бельгии, авторы алгоритма:

    • Джоан Деймен, Михаэль Петерс (Michael Peeters) и Жиль Ван Аске (Gilles Van Assche) из компании Proton World,
    • Винсент Риджмен из Католического Университета г. Лювен.

    И снова вспомним алгоритм Rijndael, поскольку среди автором алгоритма Noekeon присутствуют оба автора Rijndael – Джоан Деймен и Винсент Риджмен. Однако, Noekeon несравнимо меньше похож на Rijndael, чем рассмотренные ранее Anubis и Grand Cru.

    Noekeon шифрует данные 128-битными блоками с использованием 128-битного ключа шифрования. Алгоритм существует в двух режимах: прямом (direct mode) и косвенном (indirect mode), разница между которыми существует лишь в процедуре расширения ключа; оба режима будут рассмотрены ниже.

    Структура алгоритма

    Алгоритм Noekeon выполняет 16 раундов преобразований. Блок данных представляется в виде массива из четырех 32-битных строк a[0]...a[3]. В каждом раунде алгоритма выполняются следующие действия [6]:

    1. Верхняя строка массива данных складывается с помощью операции XOR с константой C1[r], где r – номер текущего раунда (начиная с 0). Константы C1[0]...C1[15] будут описаны ниже.
    2. Линейное преобразование выполняет следующие операции над строками массива данных с участием 128-битного «рабочего ключа» (working key), который также представляется в виде 32-битных строк k[0]..k[3] (см. рис. 10):

      Операция алгоритма Noekeon
      Рис. 10. Операция алгоритма Noekeon

      t = a[0] a[2],
      t = t (t >>> 8) (t <<< 8),
      a[1] = a[1] t,
      a[3] = a[3] t,
      a[0] = a[0] k[0],
      a[1] = a[1] k[1],
      a[2] = a[2] k[2],
      a[3] = a[3] k[3],
      t = a[1] a[3],
      t = t (t >>> 8) (t <<< 8),
      a[0] = a[0] t,
      a[2] = a[2] t,

      где t – временная переменная.

    3. Верхняя строка массива данных снова складывается операцией XOR с константой C1[r]. В каждом раунде только одна из констант C1[r] и C2[r] не является нулевой и равна константе раунда C[r]. При зашифровании нулю равны константы C2[r] (т.е., фактически, в каждом раунде не выполняется действие № 3). При расшифровании – наоборот, нулевыми являются константы C1[r] и, соответственно, не выполняются действия № 1.

      Каждая из констант C[r] содержит 3 нулевых байта и один (младший) байт с отличным от 0 значением, которое обозначим как C’[r]. Таким образом, в каждом раунде алгоритма совокупность действий № 1 и № 3 сводится к модификации только одного байта массива данных (см. рис. 11):

      Наложение раундовой константы в алгоритме Noekeon
      Рис. 11. Наложение раундовой константы в алгоритме Noekeon

      b0,3 = a0,3 C’[r]

      (где используется нотация, описанная выше для алгоритма Anubis).

      Константы C’[r] итеративно вычисляются по следующим правилам:

      • Инициализируется C’[0]:

        C’[0] = 804
      • Вычисляются последующие константы:

        C’[i] = (C’[i - 1] <<< 1) 1B,

        если C’[i - 1] & 80 > 0 (где & - побитовая логическая операция «и»), иначе:

        C’[i] = C’[i - 1] <<< 1.
    4. Вращение данных 1 выполняет побитовый циклический сдвиг влево трех строк массива данных (см. рис. 12):

      Операция алгоритма Noekeon
      Рис. 12. Операция 1 алгоритма Noekeon


      • строка a[1] сдвигается на 1 бит,
      • a[2] сдвигается на 5 бит,
      • a[3] – на 2 бита.
    5. Операция , представляющая собой табличную замену. Замена выполняется следующим образом (см. рис. 13):

      Операция алгоритма Noekeon
      Рис. 13. Операция алгоритма Noekeon


      • Массив данных представляется в виде 32 4-битных субблоков, i-й субблок Ti формируется значениями i-х бит каждой строки массива, т.е.:

        Ti = a[3]i * 8 + a[2]i * 4 + a[3]i * 2 + a[3]i,

        где a[n]ii-й бит n-й строки массива данных.

      • Значение каждого субблока заменяется согласно таблице замен:

        Входное значение0123456789ABCDEF
        Выходное значения7A2C48F0591E3DB6

        Данную табличную замену можно представить и в виде следующей последовательности операций над строками массива данных (см. рис. 14):

        Операция в виде последовательности операций
        Рис. 14. Операция в виде последовательности операций


        a[1] = a[1] (~a[3] & ~a[2]),
        a[0] = a[0] (a[2] & a[1]),
        t = a[3],
        a[3] = a[0],
        a[0] = t,
        a[2] = a[0] a[1] a[2] a[3],
        a[1] = a[1] (~a[3] & ~a[2]),
        a[0] = a[0] (a[2] & a[1]),

        где ~x – побитовый комплемент к x.

    6. Вращение данных 2 является обратным к 1, т.е. выполняет вращение тех же трех строк массива данных на указанное в описании операции 1 число бит вправо.

    Помимо описанных выше операций, после 16 раундов выполняется заключительное преобразование, состоящее из двух операций:

    • Наложение на a[0] константы C[16] операцией XOR.
    • Дополнительная операция над массивом данных.

    Расшифрование

    Процедура расшифрования практически идентичеа зашифрованию, за исключением следующих отличий:

    • Как было сказано выше, при расшифровании константы C1[r] и C2[r] меняются местами.
    • Вместо прямой операции выполняется обратная – в ней используется модифицированный рабочий ключ K’:

      K’ = (Null, K),

      где K – рабочий ключ,
      Null – 32-битный блок, состоящий из нулевых бит.
      Модификация рабочего ключа выполняется однократно до начала расшифрования, после чего K’ используется во всех операциях, где должен использоваться ключ K.

    • Раунды расшифрования нумеруются в обратном порядке – соответственно, в обратном порядке используются константы C[16]...C[1].
    • Иначе выполняется заключительное преобразование (после выполнения всех раундов расшифрования): сначала выполняется дополнительная операция (с участием K’), после чего выполняется наложение на a[1] константы C[0].

    Следует учесть, что для обеспечения вычисления констант C[16]...C[0] «на лету» в процессе расшифрования, данные константы могут вычисляться и в обратном порядке.

    Расширение ключа

    Расширение ключа алгоритма Noekeon выполняется исключительно просто, как в прямом, так и в косвенном режиме алгоритма:

    • В прямом режиме расширение ключа полностью отсутствует: 128-битный ключ шифрования используется в качестве 128-битного рабочего ключа.
    • В косвенном режиме рабочий ключ получается из ключа шифрования зашифрованием алгоритмом Noekeon значения Null на ключе шифрования (который в данном случае используется в качестве рабочего ключа).

    Авторы алгоритма рекомендуют использовать прямой режим шифрования только в том случае, когда невозможно выполнение потенциальным злоумышленником атак на связанных ключах (класс атак, использующих ключи, связанные определенным соотношением с искомым ключом).

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

    На рассмотрение в рамках конкурса AES были приняты оба режима алгоритма Noekeon. И оба режима оказались подвержены атаке на основе связанных ключей (в т. ч. косвенный режим), которую предложили криптологи Ларс Кнудсен (Lars Knudsen) и Хавард Раддум (Havard Raddum) в своей работе [8]. Кроме того, ими же было доказано, что критерии создания таблиц замен (используемых в операции ) не способствуют высокой криптостойкости алгоритма: при генерации согласно данным критериям таблицы замен результирующий алгоритм с вероятностью 85% окажется подвержен линейному и/или дифференциальному криптоанализу [8]. Этих причин оказалась достаточно для невыхода алгоритма Noekeon во второй раунд конкурса [13].

    Алгоритм Hierocrypt-3

    Hierocrypt-3 разработан тем же коллективом разработчиков из японской корпорации Toshiba, которые создали рассмотренный в первой части статьи алгоритм Hierocrypt-L1. Несмотря на то, что Hierocrypt-L1 и Hierocrypt-3 обрабатывают блоки данных различного размера: 64 и 128 бит соответственно, – они используют, практически, одни и те же преобразования, поэтому различия между ними минимальны [10, 11]:

    1. Фрагменты расширенного ключа i-го раунда Ki,1 и Ki,2 имеют размер по 128 бит (а не по 64 бита) для их наложения 128-битный блок данных в операции XS (см. первую часть статьи) аналогично алгоритму Hierocrypt-L1.
    2. Поскольку размер блока увеличился в 2 раза, операция PH и лежащая в ее основе матрица MH выглядят иначе, соответственно:



      1010101011011111
      1101110111100111
      1110111011110011
      0101010110101110
      1111101010101101
      0111110111011110
      0011111011101111
      1110010101011010
      1101111110101010
      1110011111011101
      1111001111101110
      1010111001010101
      1010110111111010
      1101111001111101
      1110111100111110
      0101101011100101


    3. Увеличилось количество раундов алгоритма (см. ниже).
    4. Существенно изменена процедура расширения ключа.

    Расширение ключа в алгоритме Hierocrypt-3

    В отличие от Hierocrypt-L1, в котором использовались только 128-битные ключи, Hierocrypt-3 позволяет использовать ключи нескольких размеров: 128, 192 и 256 бит. Поэтому процедура расширения ключа выглядит несколько более сложной. Она состоит из трех этапов:

    1. Дополнение ключа шифрования до 256-битного значения.
    2. Генерация промежуточных ключей на основе дополненного ключа.
    3. Вычисление расширенного ключа на основе промежуточных ключей.

    Дополнение ключа выполняется следующим образом: сначала ключ шифрования KI разбивается на 64-битные фрагменты:

    • KI1 и KI2 для 128-битного ключа,
    • KI1...KI3 для 192-битного ключа,
    • KI1...KI4 для 256-битного ключа.

    Затем формируется дополненный ключ KP, состоящий из фрагментов KP1...KP4, которые инициализируются согласно следующей таблице:

    Размер ключа, битKP1KP2KP3KP4
    128KI1KI2KI1H3 || H2
    192KI1KI2KI3H2 || H3
    256KI1KI2KI3KI4


    Константы H1...H4 были приведены в описании алгоритма Hierocrypt-L1.

    Генерация промежуточных ключей выполняется весьма похоже на Hierocrypt-L1 с учетом того факта, что фигурирующие в формулах величины KP1...KP4 и Z1...Z4 являются 64-битными:

    Z3 = P5E(KP3) (H1 || H0),
    Z4 = P5E(KP4),
    Z1 = KP2,
    Z2 = KP1 F(KP2 Z3),

    Операция P5E – это, фактически, операция P5 алгоритма Hierocrypt-L1, адаптированная для вычислений с 64-битными операндами:



    где x1...x8 и y1...y8 – 8-битные фрагменты, соответственно, входного и выходного значения, здесь используется матрица M5 из алгоритма Hierocrypt-L1, а матрица M5A определена так:

    1111
    0111
    0011
    1110

    Умножение выполняется в поле GF(28).

    Количество раундов алгоритма по сравнению с Hierocrypt-L1 осталось прежним (6 раундов) только для 128-битного ключа; шифрование с 192-битным ключом выполняется в 7 раундов, с 256-битным – в 8 раундов. Соответственно, изменилось количество раундов и в процедуре расширения ключа.

    Как и в алгоритме Hierocrypt-L1, вычисление расширенного ключа на основе промежуточных ключей выполняется с помощью нескольких «прямых» раундов и нескольких «обратных» раундов процедуры расширения ключа с участием модифицирующих констант H1...H4. Выбор типа раунда процедуры и соответствующей константы зависит от размера ключа и определяется по следующим таблицам:

    1. Для 128-битного ключа:

      Номер раундаТип раундаКонстанта G
      1прямойG0
      2прямойG1
      3прямойG2
      4прямойG3
      5обратныйG3
      6обратныйG2
      7обратныйG1


    2. Для 192-битного ключа:
      Номер раундаТип раундаКонстанта G
      1прямойG1
      2прямойG0
      3прямойG3
      4прямойG2
      5обратныйG2
      6обратныйG3
      7обратныйG0
      8обратныйG1


    3. Для 256-битного ключа:
      Номер раундаТип раундаКонстанта G
      1прямойG4
      2прямойG0
      3прямойG2
      4прямойG1
      5прямойG3
      6обратныйG3
      7обратныйG1
      8обратныйG2
      9обратныйG0


    Символами G0...G4 в приведенных выше таблицах обозначены 64-битные константы, получаемые путем конкатенации 32-битных констант H0...H3:

    G0 = H3 || H0,
    G1 = H2 || H1,
    G2 = H1 || H3,
    G3 = H0 || H2,
    G4 = H2 || H3.

    Прямой и обратный раунды процедуры расширения ключа также похожи на таковые в алгоритме Hierocrypt-L1 (см. первую часть статьи). Прямой раунд состоит из следующей последовательности операций:

    T1 || T2 = P32(X3 || X4),
    Y3 = P5E(T1) G,
    Y4 = P5E(T2),
    Y1 = X2,
    Y2 = X1 F(X2 Y3),

    После выполнения каждого прямого раунда происходит вычисление 128-битных подключей i-го раунда шифрования: Ki,1 и Ki,2; их 64-битные фрагменты Ki,j,1 и Ki,j,2 вычисляются следующим образом:

    T = F(X2 Y3),
    Ki,1,1 = X1 T,
    Ki,1,2 = Y3 T,
    Ki,2,1 = Y4 T,
    Ki,2,2 = Y1 Y4,

    где T – временная переменная.

    Обратный раунд определен так:

    Y1 = X2 F(X1 X3),
    Y2 = X1,
    T1 = PBE(X3 G),
    T2 = PBE(X4),
    Y3 || Y4 = P32-1(T1 || T2).

    Операция PBE аналогично описанной выше P5E разбивает обрабатываемый 64-битный фрагмент данных на две части по 32 бита, каждая из которых умножается на одну из приведенных ниже матриц:

    0101
    1010
    1101
    1011


    1100
    0110
    1011
    1001

    Фрагменты ключа шифрования по истечении каждого обратного раунда вычисляются следующим образом:

    T = F(X1 X3),
    Ki,1,1 = Y1 X3,
    Ki,1,2 = T1 T,
    Ki,2,1 = T2 T,
    Ki,2,2 = Y2 T2.

    Используемая в процедуре расширения ключа функция F тоже несколько отличается от таковой в алгоритме Hierocrypt-L1 тем, что разбивает обрабатываемые данные на 8 (а не на 4) 8-битных фрагментов, каждый из которых обрабатывается функцией P16, описанной в первой части статьи.

    И, наконец, функции P32 и P32-1 аналогичны функциям P16 и P16-1 соответственно, однако, при обработке они делят обрабатываемые данные на 4 фрагмента по 32 бита (а не по 16 бит); их умножение выполняется в поле GF(232).

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

    Недостатки алгоритмов Hierocrypt-3 и Hierocrypt-L1, практически, идентичны:

    1. Весьма медленная процедура расширения ключа, к тому же имеющая уязвимости [13].
    2. Предложено несколько атак на варианты алгоритма Hierocrypt-3 с усеченным числом раундов, что говорит о недостаточном запасе криптостойкости данного алгоритма [2, 5, 9].

    В результате, алгоритм Hierocrypt-3 не был выбран во второй раунд конкурса NESSIE [13].

    1. Barreto P.S.L.M., Rijmen V. The Anubis Block Cipher. // http://www.cosic.esat.kuleuven.be.
    2. Barreto P.S.L.M., Rijmen V., Nakahara J. Jr., Preneel B., Vandewalle J., Kim H.Y. Improved Square Attacks Against Reduced-Round Hierocrypt. // http://citeseer.ist.psu.edu.
    3. Biryukov A. Analysis of Involutional Ciphers: Khazad and Anubis. // http://citeseer.ist.psu.edu – 2003 – Katholieke Universiteit Leuven, Belgium.
    4. Borst J. The Block Cipher: Grand Cru. // http://www.cosic.esat.kuleuven.be. – K. U. Leuven, Heverlee, Belgium.
    5. Cheon J.H., Kim M. J. Kim K. Impossible Differential Cryptanalysis of Hierocrypt-3 Reduced to 3 Rounds. // http://www.math.snu.ac.kr.
    6. Daemen J., Peeters M., Van Assche G., Rijmen V. Nessie Proposal: Noekeon. // http://www.cosic.esat.kuleuben.be – 2000.
    7. FIPS Publication 197. Specification for the Advanced Encryption Standard. // http://csrc.nist.gov – November 26, 2001.
    8. Knudsen L.R., Raddum H. On Noekeon. // http://www.cosic.esat.kuleuven.be – April 24, 2001.
    9. Nakahara J. Jr. Cryptanalysis and Design of Block Ciphers. // http://citeseer.ist.psu.edu – Katholieke Universiteit Leuven – June 2003.
    10. Ohkuma K., Sano F., Muratani H., Motoyama M., Kawamura S. Specification of Hierocrypt-L1. // http://www.cosic.esat.kuleuven.be. – Toshiba Corporation – September 25, 2000.
    11. Ohkuma K., Sano F., Muratani H., Motoyama M., Kawamura S. Specification of Hierocrypt-3. // http://www.cosic.esat.kuleuven.be. – Toshiba Corporation – September 25, 2000.
    12. Preneel B., Biryukov A., Oswald E., Van Rompay B., Granboulan L., Dottax E., Murphy S., Dent A., White J., Dichtl M., Pyka S., Schafheutle M., Serf P., Biham E., Barkan E., Dunkelman O., Quisquater J-J., Ciet M., Sica F., Knudsen L., Parker M., Raddum H. NESSIE Public Report D20: NESSIE Security Report. // http://www.cosic.esat.kuleuven.be. – Version 2.0 – 19 February 2003.
    13. Preneel B., Bosselaers A., Ors S.B., Biryukov A., Granboulan L., Dottax E., Murphy S., Dent A., White J., Dichtl M., Pyka S., Serf P., Biham E., Barkan E., Dunkelman O., Ciet M., Sica F., Knudsen L., Raddum H. NESSIE Public Report D18: Update on the selection of algorithms for further investigation during the second round. // http://www.cosic.esat.kuleuven.be. – Version 1.0 – March 11, 2002.
    14. Preneel B., Van Rompay B., Granboulan L., Martinet G., Dichtl M., Schafheutle M., Serf P., Bibliovitz A., Biham E., Dunkelman O., Ciet M., Quisquater J-J., Sica F. NESSIE Public Report D14: Report on the Performance Evaluation of NESSIE Candidates I. // http://www.cosic.esat.kuleuven.be. – Version 3.3 – November 20, 2001.
    15. Preneel B., Van Rompay B., Granboulan L., Martinet G., Murphy S., Shipsey R., White J., Dichtl M., Serf P., Schafheutle M., Biham E., Dunkelman O., Ciet M., Quisquater J-J., Sica F., Knudsen L., Raddum H. NESSIE Phase I: Selection of Primitives. // http://www.cryptonessie.org. – 23 September 2001.
    16. Preneel B., Van Rompay B., Granboulan L., Martinet G., Murphy S., Shipsey R., White J., Dichtl M., Serf P., Schafheutle M., Biham E., Dunkelman O., Furman V., Ciet M., Quisquater J-J., Sica F., Knudsen L., Raddum H. NESSIE Public Report D13: Security Evaluation of NESSIE First Phase. // http://www.cosic.esat.kuleuven.be. – 23 September 2001.
    17. Панасенко С. Интересные алгоритмы шифрования. // BYTE/Россия. – 2006 - № 4 – с. 68-72.
    18. Панасенко С. Интересные алгоритмы шифрования, часть 2. // BYTE/Россия. – 2006 - № 5 – с. 74-79.
    19. Панасенко С. Стандарт шифрования США. // Мир и безопасность. – 2003 - № 6 – с. 29-31.


Дополнительно

iXBT BRAND 2016

«iXBT Brand 2016» — Выбор читателей в номинации «Процессоры (CPU)»:
Подробнее с условиями участия в розыгрыше можно ознакомиться здесь. Текущие результаты опроса доступны тут.

Нашли ошибку на сайте? Выделите текст и нажмите Shift+Enter

Код для блога бета

Выделите HTML-код в поле, скопируйте его в буфер и вставьте в свой блог.