На главную | Содержание | Назад | Вперёд
Наши друзья

 

 

Расширение ключа (Key Expansion)

Расширенный ключ представляет собой линейный массив 4-байтовых слов и обозначен как W[Nb*(Nr+l)]. Первые Nk слов содержат ключ шифрования. Все остальные слова определяются рекурсивно из слов с меньшими индексами. Алгоритм выработки
ключей зависит от величины Nk: ниже приведена версия для Nk, равного или меньшего 6, и версия для Nk, большего 6.
Для Nk<6 или Nk=6 мы имеем: KeyExpansion (CipherKey,W)
i
for   (i = 0;    i < Nk; W[I]   = CipherKey [i] ;
for   (j   = Nk;      j   <Nb*(Nk+l); j+=Nk) (
W[j]   =  W[j-Nk]   Л  SubByte(   Rotl (   W[j-1]   )    ) Л Rcon[j/Nk];
for  (i = 1;     i < Nk    &&   i+j < Nb* (Nr+1) ;
W[i+j]  = W[i+j-Nk]   Л W[i+j-l];
1
Как можно заметить, первые Nk слов заполняются ключом шифрования. Каждое последующее слово W[i] получается посредством EXOR предыдущего слова W[i-1] и слова на Nk позиций ранее W[i-Nk]. Для слов, позиция которых кратна Nk, перед EXOR применяется преобразование к W[i-l], а затем еще прибавляется цикловая константа. Преобразование содержит циклический сдвиг
байтов в слове, обозначенный как Rotl, затем следует SubByte -
применение замены байт.
Для Nk>6  мы имеем: KeyExpansion(CipherKey,W) {
for   (i=0;   i<Nk; W[i]=CipherKey [i] ;
for ,y.»tfk;. }<№>* (Nk+1) ;  j + = Nk) {
W[j]    =   W[j-Nk]    Л    SubByte(Rotl(W[j-l] ) ) Rcon[j/Nk];
for  (i-1;  i<4;   i++)      W[i+j]   = W[i+j-Nk]   Л W[i+j-
1] !
W[j+4]   = W[j+4-Nk]   л  SubByte (W [j+3 ]) ;
for   (i=5;   i<Nk;   i++)  W[i+j]   = H[i+j-Nk]   л W[i+j-
11;
)
}
Отличие для схемы при Nk>6 состоит в применении SubByte для каждого 4-го байта из Nk.
Цикловая   константа   независит   от   Nk   и определяется следующим образом:
Rcon[i]   =   ( RC[i],   '00'   ,   '00'   , ), где
RC[0]='01'
RC[i]=Xtime(Rcon[i-l])
Выбор циклового ключа
i-ый цикловой ключ получается из слов массива циклового ключа от W[Nb*i] и fl.oW[Nb(i+l)]. Это показано на рисунке 6.
V
I
Рисунок 6. Расширение ключа и выбор циклового ключа для Nb-C и Nk-4
Замечание: Алгоритм выработки ключей можно осуществлять и без использования массива
Для  реализаций,   в  которых  существенно  требование к занимаемой памяти, цикловые могут вычисляться на лету
посредством использования буфера из Nk слов.

Шифр
Шифр Rijndael состоит из:
♦ начального добавления циклового ключа; ) Nr-1 циклов;
* заключительного цикла.
На псевдо-Си это выглядит следующим образом: Rijndael  (State, CipherKey)
KeyExpansion (CipherKey, ExpandedKey) ; // Расширение ключа
AddRoundKey (State,    ExpandedKey); // Добавление
циклового ключа
For ( i-1 ; i<Nr ; i++) Round ( State, ExpandedKey+Nb*i) ;
// циклы
FinalRound(State, ExpandedKey+Nb*Nr) ; //
заключительный цикл
1
Если предварительно выполнена процедура расширения ключа, то Rijndael будет выглядеть следующим образом:

Rijndael (State, CipherKey)
{
AddRoundKey (State, ExpandedKey) ;
For  ( i-1      i<Nr Round (State,ExpandedKey+Nb*i) ;
FinalRound(State,ExpandedKey+Nb*Nr) ;
}
Замечание: Расширенный ключ должен всегда получаться из ключа шифрования и никогда не указывается напрямую. Нет никаких ограничений на выбор ключа шифрования.
Предварительные наброски по доработке LOKI
Эта статья представляет наброски по доработке LOKI — блочного шифра с секретным ключом. В настоящий момент я
предлагаю использовать его для 16-битного шифра Фейстеля со 128-битными данными и 256-битным ключевым расписанием, которое может быть получено из 128 , 192 или 256-битных ключей. 16 циклов вычисления данных используют сбалансированную петлю Фейстеля со сложной функцией f, которая объединяет два S-P слоя .256-битный алгоритм выработки ключей использует 33 цикла несбалансирован­ной петли Фейстеля, применяющей ту же сложную функцию f для генерации вспомогательных ключей.
LOKI91 — это 64-битный симметричный блочный шифр с 64-битным пользовательским ключом. Первоначально он был спроектирован L.Brown, J.Pieprzyk и J.Seberry в 1990 [BrPS90] и позже доработан L.Brown, M.Kwan, J.Pieprzyk и J.Seberry [BKPS91] (и переименован в
LOKI91) с улучшенной устойчивостью к разностному анализу.
Первоначальная версия LOKI89 была исследована Bil am и Shamir [BiSh91] и Knudsen [Knud91]. Они определили, что хотя версия LOKI89 с уменьшенным количеством циклов и чувствительна к разностному анализу, но полная 16-цикловая версия — нет.
Последующая доработка LOKI91 по усилению стойкости была
исследована Knudsen[Knud92]. Он определил, что нет характеристик, позволяющих с достаточно высокой вероятностью успешно проводить разностный анализ; что размер отображения f-функции в LOKI91
равен 8/13x2_; а также что есть атака по выбранному открытому
тексту, которая уменьшает поиск полным перебором ключей в
почти в 4 раза, используя 2j2+2 выбранных открытых текстов. В
последующих статьях Knudsen [Knud94] обсудил концепцию слабых
хэш-ключей в LOKI.
Biham ввел несколько новых типов криптоатак,
которые используют соотношения между вспомогательными ключами. Он применил такую атаку к обеим версиям LOKI. Для LOKI91 сложность подхода порядка 0(261), что быстрее, чем полный
перебор и сравнимо с результатами Knudsen-a.
Tokita, Sorimachi и Matsui [ToSM94] исследовали чувстви­тельность LOKI91 к линейному анализу и выяснили , что версии с 12 и более циклами устойчивы к нему. Впоследствии Knudsen и Robshaw [KnRo96] провели выгодные улучшения по эффективности поиска, используя нелинейную аппроксимацию, но 12 и более циклов
все еще остаются устойчивыми. Недавно Sakurai и Furuya[SaFu97] описали последующее увеличивающееся развитие...
В настоящее время LOKI91 считается шифром , действительно обеспечивающим защиту, устойчивым как к линейному, так и к разностному анализу, а его основные недостатки — это линейное ключевое расписание, из-за которого шифр чувствителен к некоторым атакам, связанным с ключом; и размер ключа, который, исходя из этих атак, необходимо брать 260.
LOKI91 был описан в Schneter |Sclm96], что привело к непрерывному продолжающемуся интересу его использования организациями, ищущими незагроможденный алгоритм шифрования. Похоже, что это продолжится в связи с реализацией небольшой быстрой Java-версии в публично доступной криптобиблиотеке [Crypt97].
Доработка LOKI
Основные  причины дальнейшей доработки  LOKI это
слабости, обусловленные его алгоритмом выработки ключей, и
происходящее развитие в области аппаратного обеспечения (продемонстрированное недавно восстановление грубой «животной» силой 56-битного ключа DES[RSAD97]), которое наглядно демонстрирует малые размеры ключевого пространства.
В осуждении доработки, я предлагаю здесь несколько статей, которые необходимо рассмотреть как с перспективы безопасности, так и с перспективы выполнения.
Факторы безопасности
Knudsen [Knud93] определил следующие необходимые условия безопасности для шифра Фейстеля:
отсутствие простых отношений;
все ключи одинаково хороши;
устойчивость к разностному анализу;
устойчивость к линейному анализу.
Основываясь на этих условиях, вышеприведенных рассмотрени­ях LOKI91 и комментариях по разработке блочных шифров в Schneier[Schn96],  некоторые  выводы,  которые,  как я думаю,
необходимо рассмотреть с точки зрения перспектив безопасности,
включают следующее:
Алгоритм выработки ключей должен быть нелинейным, чтобы предотвратить существование эквивалентных ключей и атак, связанных с ключами. Вспомогательные ключи должны быть получены путем использования нелинейных функций (очень подходит та же функция , что используется в циклах для данных), и, кроме того, биты вспомогательных ключей должны зависеть от
большого числа бит ключа:
нелинейная функция должна полностью обеспечивать лавинный эффект за одно использование сразу над всеми битами;
нелинейная функция должна быть максимально невосприим­чива как к разностному, так и к линейному анализу;
нелинейная функция должна быть составлена из набора S-блоков с высокой нелинейностью и с либо перестановками, либо со смешением операций, используемых для обеспечения эффекта
лавинности;
♦ возможно    создание    нескольких компонент-функций, зависящих только от ключевых битов (либо несколько входов блоков — только ключи, либо ключевые перестановки для избранного
обмена битами).

Факторы реализации
Результаты рассмотрения перспектив исполнения включают в
себя:
♦ S-блоки с 12 битами входа — наиболее широко подходящая часть для предварительно вычисляемого табличного задания;
♦ S-блоки должны быть определены функционально так, чтобы предварительно вычисляемые таблицы могли быть созданы во время выполнения/инициализации. Это необходимо, чтобы минимизиро­вать код при максимальной скорости;
♦ нелинейная функция должна вьгаисляться с помощью малого числа табличных заданий и других примитивных операций.
Уроки других шифров
При доработке я искал разнообразные моменты, чтобы учесть их, у шифров, которые были реализованы после первоначальной версии LOKI. Описание этих шифров взято из Schneier[Schn96] (если нет дополнительных отметок).

 

На главную | Содержание | Назад | Вперёд
 
Яндекс.Метрика