Становление Rijndael

<

060114 2239 Rij1 Становление Rijndael

1.1 Недостатки DES.

 

Все началось еще в 1973 г., когда Национальное бюро стандартов (National Bureau of Standards, NBS, предшественник NIST) начало поиски алгоритма шифрования, которому суждено было стать стандартом DES. Бюро поручило проанализировать предварительный стандарт Агентству национальной безопасности (National Security Agency, NSA). Компания IBM предложила в качестве возможного кандидата на роль DES свой алгоритм шифрования под названием Lucifer. NSA рекомендовало внести два изменения, которые NBS одобрило прежде, чем предложить Lucifer в качестве нового федерального стандарта в 1975 г.

Предложенные NSA изменения разожгли страсти. Вместо 128-разрядного ключа, как это было в Lucifer, NSA хотело, чтобы в DES применялся 56-разрядный ключ. Уайтфилд Диффи и Мартин Хеллман, математики, разработавшие алгоритм открытых ключей Диффи-Хеллмана, в 1977 г. описали машину, способную за один день отыскать все возможные ключи для этого алгоритма. Ее стоимость оценивалась в 20 млн долларов. Хотя на первый взгляд подобная машина большинству хакеров была не по средствам, согласно закону Мура, 56-разрядный ключ шифрования недолго мог оставаться достаточно надежным.

Второе изменение, предложенное NSA, касалось таблиц шифрования данного алгоритма, называемых S-box. Эти таблицы описывают, каким образом в алгоритме выполняется замена одной последовательности бит на другую. DES шифрует данные, «тасуя» их и заменяя группы бит в соответствии с содержимым S-box, повторяя этот процесс 16 раз. Каждый повтор называется раундом.

Однако некоторые аналитики опасались, что изменения в S-box могли бы привести к появлению обходных путей, зная которые, взломщик мог расшифровать сообщения DES, не перебирая все возможные ключи. По существу, любое ослабление значительно сокращает число ключей, которое необходимо проверить злоумышленнику, чтобы взломать DES. Опасения еще больше усилились, когда NSA рекомендовало IBM не описывать критерии, используемые при составлении S-box.

Хотя сомнения относительно длины ключа оказались обоснованными, этого нельзя сказать о базовой архитектуре DES. К началу 1990-х гг. Потенциальные затраты на создание машины, способной взломать DES, снизились в десять раз. В 1997 г. группа из нескольких тысяч добровольцев, работавших параллельно в течение нескольких месяцев, расшифровала сообщение, закодированное с помощью DES. А в 1998 году разработчики, спонсируемые организацией Electronic Frontier Foundation, представили работоспособную машину для взлома DES. Эта машина стоимостью 210 тыс. долларов позволяет расшифровывать в среднем один ключ DES каждые 4,5 дня. Однако до сих пор ни один пользователь DES не заявил об утрате каких-либо данных из-за того, что кто-то подобрал ключ в результате перебора.

Никому также не удалось обнаружить какие-либо лазейки в DES или найти способ проведения какой-либо атаки, на осуществление которой требуется меньше времени, чем на атаку по методу «грубой силы». NBS давно приходится опровергать слухи об оставленных NSA «лазейках» в DES. После того как NIST опубликовал DES, специалисты по шифрованию продолжали его анализировать, но им так и не удалось обнаружить доказательства ненадежности архитектуры DES. Тем не менее слухи циркулируют по-прежнему, и идея использования лазеек в DES нашла отражения во многих фантастических боевиках.

 

1.2 Выбор AES

 

NIST предпринял первые шаги в поисках замены DES после демонстрации успешного взлома этого алгоритма и начал открытую процедуру анализа и выбора нового стандарта. Он опубликовал все несекретные данные о тестировании кандидатов на роль AES и потребовал от авторов алгоритмов сообщить о базовых принципах построения используемых в них констант, таблиц и S-box. В отличие от ситуации с DES, NIST при выборе AES не стал опираться на секретные и, как следствие, запрещенные к публикации данные об исследовании алгоритмов-кандидатов.

Из 21 кандидата на роль AES, представленных к июню 1998 г., шесть не соответствовали первоначальным требованиям и еще 10 были отвергнуты NIST после первого этапа тестирования. В августе 1999 г. были объявлены следующие пять финалистов.

  1. Rijndael, предложенный Джоан Димен из компании Proton World International и Винсентом Риджменом из бельгийского университета Katholieke Universiteit Leuven. В конце концов, именно Rijndael был выбран NIST в качестве нового AES.
  2. MARS, предложенный компанией IBM.
  3. RC6(tm), предложенный RSA Laboratories. Его название — это сокращение от Rivest Cipher #6, в соответствии с традицией названия созданных ранее RSA алгоритмов с закрытыми ключами, таких, как RC2, RC4 и RC5.
  4. Serpent, предложенный Россом Андерсоном из Кембриджского университета (Англия), Эли Бихамом из Technion (Израиль) и Ларсом Кнудсеном из Калифорнийского университета.
  5. Twofish, предложенный Брюсом Шнейером, Джоном Келси и Нильсом Фергюсоном из Counterpane Internet Security, Дэвидом Вагнером из Калифорнийского университета, Дугом Уайтингом из Hi/Fn и Крисом Холлом из Принстонского университета.

    Все пять отобранных алгоритмов представляли собой блоковые шифраторы, все предусматривали проведение нескольких раундов и были разработаны специально для конкурса на роль AES. При окончательном тестировании учитывались следующие девять характеристик: две касались защиты (общий уровень защиты и защищенность реализации), одна характеризовала гибкость, а остальные были связаны с эффективностью реализации. В Таблице приводятся комментарии к результатам тестирования, проведенного NIST.

    По результатам итогового тестирования NIST присвоил относительные оценки финалистам — «отлично», «хорошо» или «удовлетворительно» — по различным критериям. В Таблице эти оценки представлены различным числом звездочек, от одной до трех, где одна звездочка соответствует минимальной оценке в категории, а три — максимальной.

     

    1.3 Победитель AES – шифр Rijndael

     

    Данный алгоритм разработан двумя специалистами по криптографии из Бельгии. Он является нетрадиционным блочным шифром, поскольку не использует сеть Фейштеля для криптопреобразований. Алгоритм представляет каждый блок кодируемых данных в виде двумерного массива байт размером 4х4, 4х6 или 4х8 в зависимости от установленной длины блока. Далее на соответствующих этапах преобразования производятся либо над независимыми столбцами, либо над независимыми строками, либо вообще над отдельными байтами в таблице.

    Все преобразования в шифре имеют строгое математическое обоснование. Сама структура и последовательность операций позволяют выполнять данный алгоритм эффективно как на 8-битных так и на 32-битных процессорах. В структуре алгоритма заложена возможность параллельного исполнения некоторых операций, что на многопроцессорных рабочих станциях может еще поднять скорость шифрования в 4 раза.

    Алгоритм состоит из некоторого количества раундов (от 10 до 14 – это зависит от размера блока и длины ключа), в которых последовательно выполняются следующие операции :

  • ByteSub – табличная подстановка 8х8 бит (рис.1),

    060114 2239 Rij2 Становление Rijndael
    Рис.1.

  • ShiftRow – сдвиг строк в двумерном массиве на различные смещения (рис.2),

    060114 2239 Rij3 Становление Rijndael
    Рис.2.

  • MixColumn – математическое преобразование, перемешивающее данные внутри столбца (рис.3),

    060114 2239 Rij4 Становление Rijndael
    Рис.3.

  • AddRoundKey – добавление материала ключа операцией XOR (рис.4).

    060114 2239 Rij5 Становление Rijndael
    Рис.4.

    В последнем раунде операция перемешивания столбцов отсутствует, что делает всю последовательность операций симметричной.

    2. Схема алгоритма нелинейного преобразования.

    2.1 Нелинейное преобразование.

     

    Нелинейное преобразование F матрицы данных состоит из трех шагов: замены байтов матрицы на новые значения (S[]), циклического сдвига строк матрицы влево (R), умножения матрицы данных слева на постоянную матрицу-циркулянт M:

    X’ = F(X) = M× R (S(X)).

    Схема преобразования данных показана на рисунке 5, схема соответствующего алгоритма — на рисунке 6.

    060114 2239 Rij6 Становление Rijndael

    Рис. 5. Схема нелинейного преобразования блока данных.

     

    060114 2239 Rij7 Становление Rijndael

     

    Рис. 6. Схема алгоритма нелинейного преобразования.

    Все входные (X), выходные (X’) и промежуточные (Y, Z) значения преобразования являются матрицами байтов одинакового размера 4×n. Функция преобразования последнего раунда F’ отличается от регулярной функции преобразования F отсутствием шага умножения матрицы данных слева на постоянную матрицу, схема преобразования блока данных на последнем раунде и схема соответсвующего алгоритма приведены на рисунках 7 и 8 соответственно:

    060114 2239 Rij8 Становление Rijndael

    Рис. 7. Схема нелинейного преобразования последнего раунда.

     

    060114 2239 Rij9 Становление Rijndael

     

    Рис. 8. Схема алгоритма нелинейного преобразования последнего раунда.

     

    Вся нелинейность преобразования сосредоточена в его первом шаге — замене, второй и третий шаги являются линейными. Первый шаг служит для перемешивания информации внутри байтов, второй обепечивает «экспорт» изменений в другие столбцы, третий осуществляет диффузию изменений в одном элементе матрицы на весь соответствующий столбец. Таким образом, за два раунда достигается диффузия изменений в одном единственном бите на весь блок данных. Ниже каждый из указанных шагов рассмотрен подробно, при этом некоторые преобразования байтов определены в терминах операций в конечном поле GF(28), порожденном неприводимым полиномом m(x) над полем GF(2):

    m(x) = x8+x4+x3+x+1

    Операция сложения в этом поле является ни чем иным, как побитовым суммированием по модулю 2, умножение в соответствие с определением поля выполняется как обычное умножение полиномов над GF(2) по модулю полинома m(x). При манипулировании с байтами данных как с элементами поля GF(28) каждый бит соответсвует слагаемому вида xi в соответсвии со старшинством бита в байте. Можно сказать, что если байт с целочисленным значением b представлен в виде полинома B(x), то справедливо b = B(2).

     

    2.2 Побайтовая замена.

     

    В ходе побайтовой замены каждый байт матрицы данных заменяется на новое значение того же размера, индексируя общий для всех байтов вектор замен S 8-в-8 бит:

    yij = S[xij], 1 ≤ i ≤ 4, 1 ≤ j ≤ n,

    где n — число столбцов матрицы данных — 4,6 или 8. Единственный узел замен в шифре Rijndael конструируется с помощью следующего алгебраического соотношения:

    S[y] = (x4+x3+x2+x+1) + y-1(x7+x6+x5+x4+1) mod (x8+1).

    При этом обращение ненулевых байтов осуществляется в описанном выше конечном поле GF(28), для нулевого байта полагают 0-1 = 0. Таким образом, байтовая замена определяется как обращение элемента-байта в конечном поле GF(28), доопределенное для нулевого элемента поля, с последующим аффинным преобразованием результата. Коэффициенты этого преобразования выбраны таким образом, чтоб у полученного узла замен отсутсвовали точки неподвижности (S[y] = y), и «антинеподвижности» (S[y] = ~y). Тильдой (знаком «~») обозначена операция побитового дополнения своего аргумента.

    Естественно, указанная выше формула для построения узла замен не предназначена для использования непосредственно во время шифрования — гораздо эффективнее использовать уже готовый узел замен, приведенный в следующей таблице:

     

    x0 

    x1 

    x2 

    x3 

    x4 

    x5 

    x6 

    x7 

    x8 

    x9 

    xA 

    xB 

    xC 

    xD 

    xE 

    xF 

    0x 

    63 

    7c 

    77 

    7b 

    f2 

    6b 

    6f 

    c5 

    30 

    01 

    67 

    2b 

    fe 

    d7 

    ab 

    76 

    1x 

    ca 

    82 

    c9 

    7d 

    fa 

    59 

    47 

    f0 

    ad 

    d4 

    a2

    af 

    9c 

    a4 

    72 

    c0 

    2x 

    b7 

    fd 

    93 

    26 

    36 

    3f 

    f7 

    cc 

    34 

    a5 

    e5 

    f1 

    71 

    d8 

    31 

    15 

    3x 

    04 

    c7 

    23 

    c3 

    18 

    96 

    05 

    9a 

    07 

    12 

    80 

    e2 

    eb 

    27 

    b2 

    75 

    4x 

    09 

    83 

    2c 

    1a 

    1b 

    6e 

    <

    5a 

    a0 

    52 

    3b 

    d6 

    b3 

    29 

    e3 

    2f 

    84 

    5x 

    53 

    d1 

    00 

    ed 

    20 

    fc 

    b1 

    5b 

    6a 

    cb 

    be 

    39 

    4a 

    4c 

    58 

    cf 

    6x 

    d0 

    ef 

    aa 

    fb 

    43 

    4d 

    33 

    85 

    45 

    f9

    02 

    7f 

    50 

    3c 

    9f 

    a8 

    7x 

    51 

    a3 

    40 

    8f 

    92 

    9d 

    38 

    f5 

    bc 

    b6 

    da 

    21 

    10 

    ff 

    f3 

    d2 

    8x 

    cd 

    0c 

    13 

    ec 

    5f 

    97 

    44 

    17 

    c4 

    a7 

    7e 

    3d 

    64 

    5d 

    19 

    73 

    9x 

    60 

    81 

    4f 

    dc 

    22 

    2a 

    90 

    88 

    46 

    ee 

    b8 

    14 

    de 

    5e 

    0b 

    db 

    Ax 

    e0 

    32 

    3a 

    0a 

    49 

    06 

    24 

    5c 

    c2 

    d3 

    ac 

    62 

    91 

    95 

    e4 

    79 

    Bx 

    e7 

    c8 

    37 

    6d 

    8d 

    d5 

    4e 

    a9 

    6c 

    56 

    f4 

    ea 

    65 

    7a 

    ae 

    08 

    Cx 

    ba 

    78 

    25 

    2e 

    1c 

    a6 

    b4 

    c6 

    e8 

    dd 

    74 

    1f 

    4b 

    bd 

    8b 

    8a 

    Dx 

    70 

    3e 

    b5 

    66 

    48 

    03 

    f6 

    0e 

    61 

    35 

    57 

    b9 

    86 

    c1 

    1d 

    9e 

    Ex 

    e1 

    f8 

    98 

    11 

    69 

    d9 

    8e 

    94 

    9b 

    1e 

    87 

    e9 

    ce 

    55 

    28 

    df 

    Fx 

    8c 

    a1 

    89 

    0d 

    bf 

    e6 

    42 

    68 

    41 

    99 

    2d 

    0f 

    b0 

    54 

    bb 

    16 

     

    Табл. 1

     

    Заменяющее значение выбирается на пересечении строки, определяемой старшей 16-ричной цифрой заменяемого значения, и столбца, определяемого его младшей цифрой.

     

    2.3 Построчное вращение матрицы.

     

    В ходе данной операции каждая строка матрицы данных, кроме первой, вращается (циклически сдвигается) влево на определенное число позиций, зависящее от номера строки и от размера блока данных:

    060114 2239 Rij10 Становление Rijndael, 1 ≤ i ≤ 4, 1 ≤ j ≤ n.

    Первая строка всегда остается на месте: С1 = 0, для нее приведенная выше формула существенно упрощается: z1j = y1j. Ниже в таблице приведены величины сдвига для строк матрицы со второй по четвертую в зависимости от числа столбцов n в матрице:

     

    n 

    4 

    6 

    8 

    С2 

    1 

    1 

    1 

    С3 

    2 

    2 

    3 

    С4 

    3 

    3 

    4 

     

    Табл. 2. Умножение на постоянную матрицу.

     

    На этом шаге матрица данных слева умножается на постоянную матрицу-циркулянт M:

     

    X = M×X,

     

    060114 2239 Rij11 Становление Rijndael

     

    При выполнении матричного умножения операции сложения и умножения элементов обеих матриц выполняются в конечном поле GF(28). Матрица M является циркулянтом: каждая ее строка получается циклическим сдвигом предыдущей строки вправо на один элемент. Элементы матрицы выбраны таким образом, чтобы свести к минимуму трудоемкость операции умножения: в ней присутствуют лишь небольшие по значению числа 01, 02 и 03, половина элементов — единичные, т.е. реального умножения выполнять для них не требуется. Этим самым обеспечивается высокая эффективность возможных реализаций этой операции.

    Следует добавить, что операция умножения в конечном поле GF(28) является достаточно трудоемкой в программной реализации и никаким образом не сводится к обычному арифметическому умножению. Если умножение двоичных чисел реализуется сдвигами и обычным арифметическим суммированием, то умножение полиномов над полем GF(2) — теми же сдвигами и побитовым суммированием по модулю 2. Однако в шифре Rijndael одним из множителей всегда является константа и размер операндов невелик — один байт. Это позволяет реализовать умножение на константу в поле GF(28) как замену, что существенно повышает эффективность программной реализации. Для каждого множителя-константы при этом требуется свой отдельный узел замен. Напротив, наиболее эффективной аппаратной реализацией этой операции является реализация в виде серии сдвигов и побитовых сложений по модулю два в соответствие с ее непосредственным определением.

    Список использованных источников

     

  1. Страница НИСТ по выработке усовершенствованного стандарта http://www.nist.gov/aes/index.html
  2. Домашняя страница шифра Rijndael http://www.esat.kuleuven.ac.be/~rijmen/rijndael/
  3. Страница поклонников шифра Rijndael http://24.11.32.186/www.rijndael.com/index.html
  4. Шифр Rijndael на странице Джона Саварда. http://home.ecn.ab.ca/~jsavard/crypto/co040801.htm
  5. Венбо М. Современная криптография: теория и практика. М.: Вильямс, 2005 г, 768 с.
  6. И.М.Виноградов. Основы теории чисел. М.: гос. издат. тех.-теор. лит-ры, 1952 г, 182 с.
  7. Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003.—328 с.
  8. Шеннон К. Работы по теории информации и кибернетике. М.: Изд-во Ил, 1963.
<

Комментирование закрыто.

WordPress: 25.66MB | MySQL:119 | 1,973sec