Современная прикладная криптография

Для имеем:

KeyExpansion(CipherKey,W)

{

for (i = 0; i < Nk; i++) W[i] = CipherKey[i];

for (j = Nk; j < Nb*(Nk+1); 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); i++)

W[i+j] = W[i+j-Nk] ^ W[i+j-1];

}

}

Как можно заметить, первые слов заполняются ключом шифрования. Каждое последующее слово W[i] получается посредством XOR предыдущего слова W[i-1] и слова находящегося на позиций левее. Для слов, позиция которых кратна , перед операцией XOR применяется преобразование к W[i-1], а затем еще прибавляется цикловая константа. Преобразование содержит циклический сдвиг байтов в слове, обозначенный как Rotl, затем следует SubByte - замена байт, описанная выше.

Для имеем:

KeyExpansion(CipherKey,W)

{

for (i=0; i<Nk; i++) W[i]=CipherKey[i];

for (j=Nk; j<Nb*(Nk+1); j+=Nk)

{

W[j] = W[j-Nk] ^ SubByte(Rotl(W[j-1])) ^ 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] = W[i+j-Nk] ^ W[i+j-1];

}

}

Отличие по сравнению с ранее рассмотренной схемой состоит в применении SubByte для каждого 4-го байта из

Цикловая константа не зависит от и определяется следующим образом:

Rcon[i] = ( RC[i], '00' , '00' , '00' ), где

RC[0]='01'

RC[i]=xtime(Rcon[i-1])

Выбор циклового ключа

i-й цикловой ключ получается из слов массива циклового ключа от и до как показано на рис. (белым цветом обозначено начальное заполнение; серым цветом обозначены ключи, получаемые только посредством вычислений внутри итерации Б; а черным цветом обозначены ключи, к которым применяется дополнительное преобразование, выполняемое перед итерацией Б).

рис. Расширение ключа и выбор циклового ключа для и

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

Описание алгоритма

В качестве входных данных имеем открытый текст. Выходные данные - зашифрованный текст. Для шифрования открытого текста выполняем следующие действия:

· разбиваем текст на блоки (текст в блок записывается по столбцам);

· шифруем каждый блок.

Шифрование блока состоит из следующих этапов:

· начального добавления циклового ключа;

· циклов шифрования;

· заключительного цикла шифрования.

На псевдо-Си это выглядит следующим образом:

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); // заключительный цикл

}

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

Rijndael (State, CipherKey)

{

AddRoundKey(State, ExpandedKey);

For ( i=1 ; i<Nr ; i++) Round(State,ExpandedKey+Nb*i);

FinalRound(State, ExpandedKey+Nb*Nr);

}

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

Для расшифровки текста необходимо разбить текст на блоки и к каждому блоку применить обратный алгоритм (см. раздел 0).

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

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

InvRound (State, RoundKey)

{

AddRoundKey(State, RoundKey); // добавление циклового ключа

InvMixColumn(State); // перемешивание столбцов

InvShiftRow(State); // сдвиг строк

InvByteSub(State); // замена байтов

}

InvFinalRound(State, RoundKey)

{

AddRoundKey(State, RoundKey); // добавление циклового ключа

InvShiftRow(State); // сдвиг строк

InvByteSub(State); // замена байтов

}

Т.е. необходимо выполнить процедуру InvFinalRound, а затем определенное число раз процедуру InvRound.

Рассмотрим алгебраические свойства обратного преобразования шифра.

Во-первых, порядок операций InvShiftRow и InvByteSub безразличен, т.к. InvShiftRow переставляет байты, но не изменяет их значения, а InvByteSub работает со значениями байтов и не зависит от их позиций.

Во-вторых, последовательность операций:

AddRoundKey(State, RoundKey); // добавление циклового ключа

InvMixColumn(State); // перемешивание столбцов

может быть заменена последовательностью:

InvMixColumn(State); // перемешивание столбцов

AddRoundKey(State, InvRoundKey); // добавление циклового ключа,

где InvRoundKey получен применением InvMixColumn к соответствующему цикловому ключу.

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

AddRoundKey(State, ExpandedKey+2*Nb); // добавление циклового ключа

InvByteSub(State); // замена байтов

InvShiftRow(State); // сдвиг строк

InvMixColumn(State); // перемешивание столбцов

AddRoundKey(State, I_ExpandedKey+Nb); // добавление циклового ключа

InvByteSub(State); // замена байтов

InvShiftRow(State); // сдвиг строк

AddRoundKey(State, ExpandedKey); // добавление циклового ключа

Таким образом, получаем обратный шифр, имеющий ту же структуру, как и прямой шифр. Это может быть обобщено на произвольное число циклов. В результате, обратный шифр RIJNDAEL можно записать следующим образом:

I_Rijndael (State, CipherKey)

{

I_KeyExpansion(CipherKey, I_ExpandedKey); // Расширение ключа

AddRoundKey(State, I_ExpandedKey+Nb*Nr); // Добавление циклового ключа

For (i=Nr-1 ; i>0; i--) Round(State, I_ExpandedKey+Nb*i); // циклы

FinalRound(State, I_ExpandedKey); // заключительный цикл

}

А процедуру расширения ключа можно записать так:

I_KeyExpansion(CipherKey, I_Expanded)

{

KeyExpansion(CipherKey, I_ExpandedKey);

for(i=1; I<Nr; i++)

InvMixColumn(I_ExpandedKey+Nb*i);

}

Что касается эффективной реализации обратного алгоритма, то все рекомендации данные ранее для прямого шифра сохраняются в силе.

Следует отметить тот факт, что алгоритм расшифрования работает медленнее чем алгоритм зашифрования. Это связано с тем, что в нем для получения расширенного ключа на каждом шаге необходимо дополнительно применять к ключевому потоку достаточно медленную операцию MixColumn.

Новые режимы использования блочных шифров

Если проследить историю развития режимов шифрования, становится очевидной ее связь с развитием IT индустрии, в особенности с развитием аппаратной базы. Долгое время во всем мире возможность распараллелить вычисления бола малодоступна. В основном использовались режим шифрования CBC и режим аутентификации сообщений - CBC-MAC. Новые режимы, такие как IAPM или IACBC были лишь разработками. Совсем недавно технологии достигли того уровня, что для обеспечения потребностей пользователя уже не достаточно увеличивать скорость аппаратного обеспечения традиционным способом. В качестве нового направления некоторые производители выбрали распараллеливание задач (процессоры с технологией HyperThreading), а другие стали более бурно развивать 64-битные платформы (Athlon64, Opteron). В настоящее время уже существует режимы, ориентированные как на распараллеливание операций, так и режимы, которые быстро оперируют большими числами(PMAC/add).

Опишем основные свойства этих новых режимов и укажем на цели, которые преследовали их авторы и проблемы, которые данные режимы пытаются решить.

Прежде всего, необходимо дать определение, что такое режим работы блочного шифра и какие в связи с этим понятия или термины нам придётся ввести. Под режимом работы блочного шифра понимается алгоритм применения блочного шифра, используемый в целях защиты информации (В том числе подсчет MAC, MDC, …). Как видно из определения сам блочный шифр теперь является лишь частью другого алгоритма - алгоритма режима работы блочного шифра. Это обусловлено тем, что блочный шифр оперирует только с отдельным блоком данных, в то время как алгоритм режима работы блочного шифра имеет дело уже с целым сообщением, которое может состоять из некоторого числа n блоков. Более того, сообщение вообще не всегда можно разбить на целое число n блоков. В этом случае в разных режимах шифрования приходиться дополнять сообщение различным количеством бит. Такое дополнение почти неизбежно, но минимальная величина, к которой нужно "подтянуть" длину сообщения различна для разных режимов шифрования и напрямую зависит от длины порции сообщения, с которой работает каждая итерация алгоритма данного режима.

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

Кроме проблемы обеспечения конфиденциальности информации, в данное время обеспечение ее целостности также является важной задачей. Существует два основных способа обеспечения целостности информации - вычисление MAC(message authentication code) и MDC (manipulation detection code). Эти режимы используются совместно с режимами шифрования.

Для повышения производительности в последнее время были созданы режимы, обеспечивающие как конфиденциальность, так и целостность информации (Authenticated Encryption Modes). В этих режимах работы блочных шифров часто используется режим CTR (Counter).

Режимы шифрования

При создании системы защиты конфиденциальной информации любой заказчик интересуется: “Какой алгоритм шифрования использует Ваша система?” Вопрос, безусловно, важный, однако значительный вклад в качество и производительность системы шифрования вносят режимы, в которых используются алгоритмы шифрования. С семидесятых годов чаще всего использовались режимы схожие с режимами стандарта Data Encryption Standard - ECB,CBC,OFB,CFB. Каждый из этих режимов обладает своими достоинствами и недостатками: ECB - идеален для распараллеливания вычислений. С помощью него можно легко добиться больших скоростей шифрования, CBC более стойкий ко многим известным типам атак, OFB и CFB дают возможность работать с потоками информации, а не с блоками. Время выдвигает новые требования, и новые режимы шифрования пытаются их решить.

Режимы аутентификации

Режим Parallelizable Message Authentication Code (PMAC)

Параллелезируемый MAC - это новый код аутентификации сообщения. В отличие от других режимов аутентификации сообщения конструкция этого полностью параллелизируема. В современных условиях это свойство имеет огромное значение. В новой версии платформы Microsoft .NET 2.0 планируется реализовать этот режим, поэтому разберем его наиболее подробно.

В конструкции PMAC мало используются вызовы блочного шифрования, применяя только блочный шифр [|M|/n] раз, М - непустая строка, n - размерность блока блочного шифра.

В отличие от обычного CBC MAC, PMAC может быть применен к любому сообщению М; в частности, n необязательно делит |M|. Аналогично, сообщение с примененным MAC не обязательно должно иметь фиксированную длину; сообщения различных длин могут быть безопасно защищены от изменения этим алгоритмом.

Когда используется PMAC с AES, ключом для PMAC является простой AES ключ, и все обращения к AES происходят под этим ключом.

Конструкция PMAC подобна коду XOR MAC Bellare, Guerin, и Rogaway и подобному варианту у Bernstein. Хотя это даже больше подобно XECB MAC Gligor and Donescu. Последняя работа послужила вдохновением для этой. Но PMAC более эффективен, чем любой альтернативный ему.

Можно рассмотреть PMAC как еще одну оптимизированную версию MAC конструкции, попадающей под парадигму Carter-Wegman. Другие версии MAC, попадающие под эту парадигму, - параллелизуемы, если только они используют семейство параллелизируемых универсальных хэш-функций. Но определение и осуществление (некриптографической) универсальной хэш-функции создают более сложный механизм, чем тот, что дается здесь.

Обозначения:

Для работы алгоритма используется блочный шифр Е n-битным входным блоком (X) и к-битный ключ К. Блок шифр-текста - Y=E_k(X). Для E=AES мы получаем n=128 и k{128,192,256}.

Аутентификационные тэги, которые мы определяем, могут иметь любой номер битов, tagLen, от 1 и до n. Заданное по умолчанию значение tagLen=64, вероятно, должно быть хорошим.

Под 0ⁱ и 1ⁱ мы понимаем строки, соответственно, из i нулей и i единиц. Для строки А длиной меньше, чем n, под pad_n(A) мы понимаем строку 0^n-|A|-11 A: то есть, рассматриваем нулевые биты, а затем 1 бит равный 1.

Если А и В - строки, тогда АВ обозначает их конкатенацию.

Если А и В - строки равной длины. Под А[bit i] мы понимаем i-й бит А, где знаки пронумерованы с лева на право, начиная с 1. Под А[bits l to r] понимаем А[bit l]A[bit l+1]…..A[bit r]

Описание алгоритма PMAC.

Сложение, умножение и Final(^.)

Мы задаем операцию сложения “+” отображающую {0,1}ⁿx{0,1}ⁿ в {0,1}ⁿ , операцию умножения из {1,2,3,…….}x{0,1}ⁿ в {0,1}ⁿ. Мы также задаем отображение Final:{0,1}ⁿ {0,1}ⁿ .

PMAC/add

Для сложения по модулю 2ⁿ версии PMAC, PMAC/add, покажем операцию “+” на примере “компьютерного” сложения n-битных слов (игнорируя любой перенос ), и назовем iL, для i 1, повторным сложение. Пусть Final(L) -будет L, поразрядное дополнение к L.

(Более формальное определение: Пусть А,В {0,1}ⁿ. Под str2num(A) понимаем неотрицательное целое число, которое будет представлено А, то есть, ⁿ_i=1 2^n-iA[bit i]. Если а - целое число, то num2str_n(a) - уникальная n-битная строка А, так что num2str_n(A)=amod2ⁿ . Под А+В мы определяем num2str_n(num2str_n(А)+ num2str_n(В)). Под iA, где i 0 положительное целое число, мы понимаем строку num2str_n(i^.num2str_n(А)). Символ “^.” в последнем выражении значит умножение целых чисел.

Данный k-битный ключ К происходит от ключа L путем L=E_K(0ⁿ)V0^n-11. Это гарантирует, что L - нечетная.

Вычисление PMAC.

Теперь определим PMAC. Когда выполнены сложение и умножение, мы определяем PMAC/add. Данная строка М вычисляется, как показано ниже.

Так как MAC детерминирован, отдельный алгоритм не нужен; получатель сообщения должен вычислить MAC и сравнить его с MAC, который должен сопровождать сообщение.

Алгоритм использует основной k-битный ключ K, но этот ключ отображается в (K,L), где L - n-битный ключ. В типичной реализации, L должен быть вычислен один раз и сохранен.

Последовательное сложение L может быть использовано вместо этого, как:

Offset = L

for i = 1to m-1 do

C[i] =E_K(M[i] + Offset)

Offset = Offset + L

В цепочке сложений, показанной выше, может показаться, что PMAC (без умножения) фактически последователен.Это неверно.

Чтобы пояснить, что происходит в параллельной реализации, положим, что компьютер имеет два процессора, Р₁ и Р₂, и каждый должен вычислять MAC M=M[1]^…..M[m]. Процессор Р₁ начинает с Offset = 0ⁿ, а процессор Р₂ с Offset = L. Процессор Р₁ будет ответственен за нечетно индексированные слова, в то время как Р₂ обрабатывает четно-индексированные слова. Каждый увеличивает собственный Offset двумя L, но не одним L. Процессор Р₁ будет кодировать M[1];M[3];M[5]….. и XOR шифр-текст. Процессор Р₂ будет кодировать M[2] M[4] M[6] ….и XOR шифр-текст. Данные XOR шифр-тексты, заключительный MAC могут быть вычислены одним из процессоров.

Заметим, что ни создание MAC, ни его проверка не требуют использование функции Е^-1. Таким образом, Е^-1 не нужно реализовывать.

Заметим также, что если сообщение должно быть изменено путем замещения некоторых блоков, время пересчета исправленного MAC пропорционально r, предполагая, что каждый имеет сохраняемый старый (n-битный) MAC.

Начиная с n=128, n-битное сложения уже не тривиальная операция, особенно в высокоуровневых языках программирования (Это утверждение верно для современных 32-битных компьютеров, но в данное время появились машины класса Athlon64 - с 64 битной архитектурой и этот режим можно использовать для больших n).

Кроме варианта PMAC/add существуют PMAC/mod и PMAC/xor.

В варианте PMAC/mod вместо вычисления iL по модулю 2ⁿ используется модуль iL по модулю p.

Режим OMAC: One-Key CBC MAC

Здесь представляется режим работы блочного шифра One-key CBC MAC и доказывается его стойкость. Данный код аутентификации сообщений может быть применен для сообщений произвольной длины.

Базовая конструкция семейства OMAC.

Семейство ОМАС определяется блочным шифром Е: К_E^х{0,1}ⁿ{0,1}ⁿ , n-битной константой Cst, универсальной хэш-функцией H: {0,1}^{n х}X{0,1}ⁿ и двумя явными константами Cst1, Cst2 Х, где Х - конечная область Н.

Н, Cst1 и Cst2 должны удовлетворять следующим условиям, пока Cst является произвольной. Будем писать H_L(^.) для H(L,^.)

1. y{0,1}ⁿ, число L{0,1}ⁿ : H_L(Cst1)=y не более е₁^.2ⁿ для достаточно малого е₁.

2. y{0,1}ⁿ, число{0,1}ⁿ : H_L(Cst2)=y is не более е₂^.2ⁿ для достаточно малого е₂.

3. y{0,1}ⁿ, число L{0,1}ⁿ : H_L(Cst1) H_L(Cst2)=y не более е₃^.2ⁿ для достаточно малого е₃.

4. y{0,1}ⁿ, число L{0,1}ⁿ : H_L(Cst1) L=y не более е₄^.2ⁿ для достаточно малого е₄.

5. y{0,1}ⁿ, число L{0,1}ⁿ : H_L(Cst2) L=y не более е₅^.2ⁿ для достаточно малого е₅.

6. y{0,1}ⁿ, число L{0,1}ⁿ : H_L(Cst1) H_L(Cst2) L=y не более е₆^.2ⁿ для достаточно малого е₆.

Ремарка: свойства 1 и 2 говорят, что H_L(Cst1) и H_L(Cst2) почти равномерно распределены. Свойство 3 удовлетворено AXU (almost XOR universal) хэш-функцией. Свайства 4, 5, 6 - новые вводимые требования.

Ограничения метода:

1. CBC MAC шифры, и OMAC в их числе, не параллелизуемы.

2. Ограниченная возможность предобработки.

Преимущества метода:

1. Минимальная длина ключа. Минимальная длина ключа в OMAC равна k-бит, тогда как в XCBC она равна (k+2n)-бит, а в TMAC - (k+n)-бит.

2. Произвольная длина сообщений. Область определения в OMAC равна {0,1} и M не обязательно быть множеством блока длиной n.

3. Оптимальное количество обращений блочного шифра. Для генерации тэга для любого непустого сообщения M{0,1}; OMAC требуется n обращений блочного шифра. (Пустая последовательность - исключение, для нее требуется одно обращение).

4. Оптимальное количество разработок ключей блочного шифра. OMAC требуется однократный запрос ключа.

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

6. Не используется модуль расшифрования. Как и в любых других CBC MAC шифрах, OMAC не использует модуль расшифрования блочного шифра.

7. Простота. Благодаря простоте OMAC нетребователен ни к программным, ни к аппаратным средствам.

Также в марте 2003 года после анализа OMAC, Tetsu Iwata и Kaoru Kurosawa предложили новый вариант OMAC, названный OMAC1. В OMAC1 константа Cst1 равна некоторому u² вместо u^-1 в OMAC(он же OMAC2).

Режим Randomized MAC (RMAC)

A randomized MAC beyond the birthday paradox limit

Первым из методов в работе над AES, предложенным NIST (Национальным институтом стандартов и технологии США) был RMAC (Randomized Message Authentication Code, рандомизированный код аутентификации сообщений). Его преимуществом является наличие доказательства стойкости. По сути, если использовать тройной DES в качестве основы для RMAC (метод RMAC может работать с любым блочным шифром), то полученная конструкция будет доказуемо стойкой.

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

Если тройной DES может быть смоделирован идеальным шифром, то тройной DES-RMAC должен быть стойким. В действительности, стандарт RMAC, предложенный NIST, включает тройной DES-RMAC как одну из двух опций. (Другой опцией является AES-RMAC.) Однако было показано, что тройной DES не является стойким против атак со связанными ключами. Его атака требует выбора 2¹⁶ сообщений и около 2⁵⁶ вычислительных операций, что делает ее практически реализуемой с сегодняшними вычислительными ресурсами.

Доказательство стойкости для RMAC проходит только в том случае, когда предполагается использование идеального шифра. Если вы хотите сделать какие-либо выводы о RMAC с реальным блочным шифром наподобие тройного DES или AES, вы должны надеяться, что ваш реальный блочный шифр подобен идеальному шифру до такой степени, что то же самое доказательство переносится на этот случай. В случае тройного DES эта надежда оказалась ложной. Тройной DES не может быть хорошо смоделирован идеальным шифром, так как тройной DES поддается атакам со связанными ключами. И если существуют атаки со связанными ключами на ваш реальный блочный шифр, то это не только делает несостоятельным доказательство и "недействительной гарантию стойкости", но может также привести к серьезным атакам на RMAC.

В настоящее время наиболее интересным вопросом является вопрос о том, будет ли AES-RMAC стойким. Если вы хотите думать, что доказательство стойкости для RMAC что-нибудь говорит об AES-RMAC, то вы должны надеяться, что AES ведет себя наподобие идеального шифра. Одним из необходимых условий для последнего является стойкость AES против атак со связанными ключами.

AES - новый шифр, и его стойкость против атак со связанными ключами не была хорошо изучена. Главным образом, криптоаналитики сосредоточивают свое внимание на стандартной модели угроз (атаки с выбором открытого текста и шифр-текста), а атаки со связанными ключами изучались лишь изредка. Наши небольшие знания о стойкости AES против атак со связанными ключами наводят на мысль о том, AES имеет значительно меньшую стойкость против атак со связанными ключами, чем против нормальных атак: лучшая атака со связанными ключами (найденная после всего лишь нескольких недель анализа) разламывает за девять раундов». (Из перевода статьи в Crypto-Gram от 15 января 2003 г).

Существует разделение RMAC на два режима, слегка отличающихся друг от друга дополнениями к сообщению.

Размер MAC тэга в RMAC оптимален, и составляет 2 величины блочного шифра. Более того, благодаря его конструкции, вычислительные накладные расходы незначительны по сравнению с результатом простых нерандомизированных шифров CBC-MAC.

Режимы шифрования и аутентификации

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

Режим A Conventional Authenticated-Encryption Mode EAX

Данный режим работы блочного шифра, EAX предназначен для аутентифицированного шифрования со связанными данными (AEAD).

При заданном случайном числе N, сообщении М и заголовке H, режим предохраняет и секретность М, а также подлинность и М и H. Строки N, М, H {0,1} являются произвольными, и данный режим использует 2M/n+H/n+N+n запросы блочного шифра, когда эти строки не пусты, и n - длина блока основного блочного шифра. Среди характеристик метода EAX - то, что он является сетевым и фиксированный заголовок может быть предобработан, что эффективно снижает стоимость закрепления его в зашифрованный текст. EAX получен реализацией простого универсального композиционного метода, EAX2, и последующим слиянием его двух ключей в один.

EAX доказуемо стоек по стандартному сложностно-теоретическому допущению. EAX может быть альтернативой CCM, так как тоже не запатентован.

Описание режима:

Для начала введем функции, используемые в данном алгоритме:

Algorithm CTRNK (M) 20 m | |M|/n | 21 S EK(N)|| EK(N+1) … EK(N+m-1) 22 C M S [first |M| bits] 23 return C	Algorithm CBCK (M) 10 Let M1 …Mm M where |Mi| = n 11 C0 0n 12 for i =1 to m do 13 Ci EK(Mi Ci-1) 14 return Cm
Algorithm pad (M; B; P) 30 if |M| {n; 2n; 3n;…} 31 then return M ' B, 32 else return (M || 10n-1-(|M| mod n) ) ' P	Algorithm OMACK (M) 40 L EK(0n); B 2L; P 4L 41 return CBCK(pad (M; B; P)); Algorithm OMACtK (M) 50 return OMACK([t]n || M)

Здесь операция “'” - сложение по модулю 2 более короткой строки с концом более длинной.

Режим Counter with CBC-MAC (CCM)

Счетчик с режимом CBC-MAC (CCM) разработан, чтобы использовать блочный шифр с AES (Advanced Encryption Standard, улучшенный стандарт шифрования), или любые другие блочные шифры с размером блока 128 битов и больше, для обеспечения аутентификации и шифрования, используя единственный ключ блочного шифра, установленный заранее.

CCM предназначен для использования в пакетной среде; ввод открытого текста включает заголовок, который заверен, но не зашифрован, и полезный груз, который заверен и зашифрован.

CCM оперирует целыми пакетами; он не поддерживает ни частичную, ни потоковую обработку данных. Пакет должен быть целым числом октетов. Каждый пакет задается как единственное значение, так называемое «случайное число». Размер случайного числа определяет максимум количества пакетов, которые могут быть заверены и зашифрованы одним ключом блочного шифра. Общее количество октетов, защищенных единственным ключом, ограничено 2⁶⁴ октетов.

Обработка CCM увеличивает размер пакета, добавляя в конце зашифрованный опознавательный тэг. Успешная проверка опознавательного тэга гарантирует, что пакет преобразован

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

CCM допускает предвычисление ключевого потока, если известно значение случайного числа. Это позволяет вполовину снизить вычислительную нагрузку и увеличить эффективность работы.

И зашифрование CCM и операции расшифровки CCM используют только модуль шифрования блочного шифра. В AES, зашифрование и алгоритмы расшифровки имеют некоторые существенные различия. Таким образом, использование только модуля шифрования может вести к существенному уменьшению размера кода и снижению требований к аппаратным средствам.

Спецификация ССМ.

ССМ зашифрование может быть получено в итоге следующим образом. Во-первых, вычисляется СВС-МАС тэг Т функции кодирования (N,H,M), где N - вводимое случайное число фиксированной битовой длины k_n<k_b, где k_b - битовая длина блока шифрования псевдослучайной функции Е, на которой базируется ССМ, H - заголовок, M - сообщение.

Во-вторых, сообщение М зашифровывается в режиме CTR с блоками CTR, сгенерированными из случайного числа N с помощью . И, наконец, тэг Т зашифровывается с единственным CTR блоком.

Формально, зашифрование CCM определено следующим образом.

1. Вычисление СВС-МАС:

- Let B₀.B₁.^....B_r=(N,H,M).

- Let Y₀= E_k(B₀).

- For 1ir,let Y_i= E_k(Y_i-1B_i).

- Let T be equal to the k_t leftmost bits of Y_r.

2. Шифрование CTR:

- Let =[|M|/ k_b].

- For 0i, let A_i=(i,N,H,|M|).

- For 0i, let S_i= E_k(A_i).

- Let S be equal to the |M| leftmost bits of S₁.S₂.^....S and let S' be equal to the |T| leftmost bits of S₀.

- Let C=[MS].[TS'].

3. Output C.

Расшифрование ССМ шифр-текста С со случайным числом N и заголовком H определено очевидным образом: сначала чтобы получить сообщение М и тэг СВС-МАС Т, применяется к С обратный шаг 2; затем применяется СВС-МАС к (N,H,M) как в шаге 1 для получения тэга Т'. Если Т=Т', тогда С - достоверно, и сообщение М выходит. Иначе С - недостоверно и на выходе получается ошибка. Заметим, что операция расшифрования не должна «выпускать» сообщение или любую его часть, пока тэг не будет проверен. Это предотвращает получение противником выбранного шифр-текста, используя информацию о недопустимых запросах расшифрования.

1.3 Теория информации в криптологии

В 1949 году К.Шеннон заложил теоретическую базу для криптографии, опубликовав свою работу "Теория связи в секретных системах", где строго доказал безопасность некоторых криптосистем при определенных условиях. Окончился этап донаучной криптографии, основанной на вере. Результатам Шеннона во многом способствовало развитие теории информации. Остановимся на некоторых основных моментах. Материал составлен в основном по работам [1,24].

Формально количество информации в послании измеряется энтропией.

Пусть ..... есть n возможных сообщений, появляющихся с вероятностями

P(),….,P(),=1

Тогда энтропия данного сообщения x есть

H(x) = -

или будем записывать ее как сумму по всем сообщениям х:

H(x) = - = -

Аналогично, энтропия сообщения х при известном y (точнее, средняя энтропия) есть

H(x/y)=-=,

где р(х/у) - условная вероятность сообщения х при известном у. Энтропии (неопределенности) подчиняются таким правилам, как

H(x/y) = H(x) - H(y/x).

Например, необходимость только одного бита в разделе "Пол" подтверждается следующим: Р(муж.) = Р(жен.) = 0,5. Тогда

Н(х) = 0,5= 1

Интуитивно, каждый член в выражении для H(х) представляет число битов, необходимое для кодирования сообщения х оптимальным образом. Взвешенное среднее H(х) дает ожидаемое число битов при оптимальном кодировании. Так как 1/p(x) уменьшается при увеличении р(х), то при оптимальном кодировании используются короткие кодобозначения для часто появляющихся сообщений.

Пример. Рассмотрим для n = 3 сообщения в виде букв а, B, C, такие, что р(а) = 0.5, р(в) = р(с) = 0,25, Тогда

H(x) = 0,5 = 1,5

При оптимальном кодировании а заменяется одним битом, например о, а в и с - двумя битами. 10 и 11 соответственно.

При использовании этого кодирования 8-буквенное сообщение аваасавс преобразуется в 12-битовое 010001101011. Среднее число битов на букву сообщения равно 12/8=1,5.

Для данного n величина H(х) принимает максимальное значение. равное при P()=...=р() = 1/n, то есть. когда все сообщения одинаково вероятны.

Неопределенность H(х) уменьшается, когда распределение вероятностей сообщений становится более отличным от равновероятного, и достигает минимума H(х) = 0, когда P()=1 для некоторого сообщения .

Теория информации имеет отношение к двум связанным проблемам: проблеме передачи по каналу с шумом и проблеме секретности передачи. В канале с шумом получатель должен по полученному сообщению и восстановить истинное сообщение. В криптосистемах наложение шума соответствует шифрующему преобразованию, а полученное сообщение - шифртексту. Энтропия сообщения измеряет его неопределенность (uncertainty) в числе бит информации, которая должна быть восстановлена, когда сообщение было изменено в канале с шумом или скрыто для криптоаналитика в шифртексте.

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

По Шеннону совершенная секретность криптосистемы (perfect secrecy) означает, что открытый текст M и шифртекст С статистически независимы, то есть совпадают вероятности

р(м/с) = р(m)

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

Определение совершенной секретности можно представить и в терминах энтропии:

H(M/C) = h(M).

Пусть P(C/M)- условная вероятность получения шифртекста C при условии, что известно, что зашифрован текст M на некотором неизвестном ключе. Тогда

P(C/M) = P(K)

где P(k) - вероятность использования ключа k, - преобразование зашифрования на ключе k.

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

Необходимым и достаточным условием для совершенной секретности является то, что для каждого C и для всех M выполнено P(C/M) = P(C).

Последнее равенство означает, что вероятности получения конкретного шифртекста C при условии, что был зашифрован текст M, одинаковы для всех M.

Используя тот факт, что уменьшение объема известных сведений может лишь увеличить неопределенность, получаем соотношения

Н( М/С ) Н( М,К/С ) = Н( К/С ) + Н( Н/С,К ) = Н( К/С ) H( K ).

(В последнем равенстве, естественно, H( H/C,K ) = 0.). Другими словами, неопределенность секретного ключа должна быть не меньше неопределенности шифруемого с его помощью открытого текста. Отсюда можно сделать вывод, что размер секретного ключа не должен быть меньше размера открытого текста. Это, конечно, практически неудобно.

Примером совершенно секретной криптосистемы является система Вернама. При шифровании двоичного шифртекста M =(.... ,) с помощью двоичного ключа K = (.....) той же длины по правилу

C = M K =

при случайном равновероятном выборе секретного ключа (P(K)=)получаем для любых C и M очевидное равенство

(P(C/M)=),

из которого следует, что тексты M и C статистически независимы.

Помимо неудобств, связанных с большим объемом ключа, совершенно секретные системы, как отметил Рюппель (Rueppel) в [40], могут быть дешифрованы при известном открытом тексте (Known plaintext attack). Кроме того, чрезмерно предположение о противнике с неограниченными вычислительными мощностями, да и сама информация может иметь ограниченную временную ценность.

Поэтому Шеннон, помимо теоретической стойкости криптосистем, рассматривал и практическую стойкость. Для этого он ввел так называемую рабочую характеристику w(n) - среднее количество работы (измеренное в удобных единицах), требуемое для нахождения ключа на основе знания n знаков шифртекста с помощью наилучшего криптоаналитического алгоритма. Обычно криптосистемы оценивают с помощью достигнутой оценки рабочей характеристики при использовании наилучшего из известных методов дешифрования. Криптосистемы называются практически стойкими, если они не могут быть вскрыты в течение реального времени ( const ) всеми общедоступными методами. Хотя Шеннон исходил из анализа криптосистем лишь по шифртексту, определение подразумевает все типы анализа.

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

Важным понятием при изучении стойкости несовершенных шифров (криптосистем) является введенное Шенноном понятие расстояния единственности (unicity distance) шифра (криптосистемы). Оно определяется как наименьшее число знаков шифртекста, необходимое для однозначного определения ключа, то есть когда неопределенность H(K|c) при известном шифртексте данной длины равна (близка) нулю. (Величина Н(К]с) - key equivocation - иногда переводится как "ненадежность ключа"). Системы, которые не обладают совершенной секретностью, но, тем не менее, не вскрываемы, так как не дают достаточной информации в шифртексте для однозначного определения ключа, называются "идеально секретными" (ideal secrecy). У идеально секретных систем неопределенность H(K|C) не достигает нуля ни при какой длине шифртекста. Для "строго идеальных систем" выполняется соотношение H(K|C) = M(k). По определению, для величины H(K|c) имеем соотношение

Н(К|с) = - P(K|c) P(K|c)

где Р(K|c) - вероятность того, что данный ключ к использовался при получении данного шифртекста C. Большинство криптосистем слишком сложны, чтобы для них можно было определить все вероятности Р(K|с), встречающиеся в последнем соотношении. Тем не менее, Шеннон показал, что возможно оценить H(K|с), используя так называемую модель случайного шифра (random cipher model), для которого при любых K и C из соответствующих пространств, значение является независимой случайной величиной, равномерно распределенной на пространстве всех открытых текстов (в действительности полной независимости быть не может, так как при и любом k в силу однозначности зашифрования).

Пусть, для простоты изложения, мощности алфавитов открытого и шифрованного текстов равны L. Тогда существует = последовательностей длин n, где N = N (absolute rate of language). Например, при L=26 ( английский язык ) R = . Эти последовательностей разбиваются на два множества: множество из осмысленных текстов длины N и множество из - бессмысленных текстов. Здесь r (rate of the language) обозначает энтропию источника сообщений на один знак, то есть величину H(m)/N. Например, для английского языка при больших значениях n величина r заключена в границах I бит/буква и 1.5 бит/буква. Предполагается, что все осмысленные тексты имеют одинаковую вероятность . тогда как все бессмысленные - нулевую вероятность. Также естественно считать, что все ключей одинаково вероятны (P(K)= ) для использования, H(K) энтропия ключа (число битов в ключе).

Если шифртекст с = получен при каких-то истинных значениях k и m, то криптоаналитик противника может принять ложный ключ k за истинный в следующих двух случаях

с =

или с = ,

при том же или другом осмысленном тексте . Так как каждый открытый текст одинаково вероятен, то вероятность получить осмысленный открытый текст при случайно выбранном для расшифрования ключе из множества (-1) ложных ключей равна 2, где величина D= (N-r) называется избыточностью языка (redundency of the language). Таким образом, число ложных решений можно оценить величиной

(.

Отсюда видно, что число ложных решений равно нулю(единице), а значит, и неопределимость H(K|с) ключа тоже равна нулю при h(k)-dn=o или при n=n(k)/d. Величина N(k)/D является оценкой для расстояния единственности.

В качестве примеров, можно посчитать расстояние единственности для широко известных криптосистем Hagelin H-209, DES и SKIPJACK, у которых величина H(к) равна 131, 56 и 80 бит соответственно. Приняв для английского языка D=3,2, получим значения расстояния единственности соответственно в 40.9; 17,5; 25 букв.

Из отношения h(k)/d для расстояния единственности можно сделать некоторые выводы. Во-первых, если при любом n число возможных ключей так же велико, как число осмысленных открытых текстов, то

H(K)=-=rN

и если h(k)-dn = (r-D)N 0, то система является теоретически невскрываемой. Подобный принцип лежит в основе шифра Вернама (one-tine pad).

Во-вторых, при фиксированном размере ключа H(к) и нулевой избыточности языка D = R-r , расстояние единственности равно бесконечности, и криптоаналитик никогда не сможет раскрыть криптосистему, даже если число ключей много меньше числа осмысленных открытых текстов, и совершенная секретность не имеет места. Действительно, для любого шифртекста с все тексты при всех ключах к будут восприниматься криптоаналитиком как осмысленные открытые тексты. На основании этих рассуждений Шеннон предложил устранять избыточность открытого текста перед зашифрованием. Этого можно достичь, например, с помощью специального кодирования. Так, можно использовать архиваторы текстов перед зашифрованием.

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

В дальнейшем идеи Шеннона были развиты в работах Хеллмана, Джилберта, Мак Вильямса и Слоэна [68].

1.4 Теория сложности и криптология

Стойкость криптосистем определяется вычислительной сложностью (coeputatlonal complexity) алгоритмов, применяемых криптоаналитиками для дешифрования этих систем.

Вычислительная сложность алгоритма в свою очередь измеряется его временной (T) и емкостной (S) сложностями в зависимости от размера входных данных [13]. Временная сложность - это время, затрачиваемое алгоритмом для решения задачи, рассматриваемое как функция размера задачи или меры количества входных данных (например, размером задачи умножения матриц может быть наибольший размер матриц-сомножителей). Аналогично, емкостная сложность - это объем необходимой машинной памяти. Поведение этих сложностей в пределе при увеличении размера задачи называется асимптотическими сложностями. Эти сложности алгоритма определяют в итоге размер задач, которые можно решить этим алгоритмом.

Если при данном размере входа в качестве меры сложности берется наибольшая из сложностей по всем входам этого размера, то она называется сложностью в худшем случае. Если в качестве меры сложности берется "средняя" сложность по всем входам данного размера, то она называется средней или усредненной сложностью. Обычно среднюю сложность найти труднее, чем сложность в худшем случае.

Теория сложности в основном имеет дело со сложностью задач в худшем случае. Однако в криптологии более важна средняя сложность задачи, а алгоритм с наименьшей сложностью в худшем случае не обязательно имеет наименьшую среднюю сложность.

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

Другой пример: алгоритмы ветвей и границ [26], успешно решающие так называемую задачу о рюкзаке (см. далее), имеют также большую (экспоненциальную) временную сложность.

Естественно, для анализа работы алгоритма нужны модели вычислительных машин, достаточно простых для анализа, но в то же время точно отражающих основные черты реальных машин. Так, в работе [13] рассматриваются модели, включающие машину с произвольным доступом к памяти, машину с произвольным доступом к памяти и хранимой программой, детерминированную и недетерминированную машину Тьюринга и др.

Хотя отмечается, что общая тенденция в разработке программ для описания алгоритма состоит в использовании языков высокого уровня., следует иметь в виду, что в криптологии важно учитывать и реальный выигрыш во времени работы алгоритма от использования машинно-ориентированных языков и более сложных специальных моделей вычислительных машин.

Если алгоритм обрабатывает входы размера n за время cn², где с - некоторая постоянная, то говорят, что временная сложность этого алгоритма есть O(n²) (читается "порядка n²"). Точнее, неотрицательная функция g(n) есть O(f(n)) (пишут g(n)=O(f(n)), если существуют постоянные с и , для которых

g(n) c|f(n)| при .

Если g(n) = является полиномом степени m (deg g(n) = n), то g(n)=0(). Действительно, легко видеть, что

|g(n)| ||+||*n+…+ при 1.

Напомним некоторые операции с символом "большое 0". Так,

g(n) = O(g(n)); c*O(g(n)) = O(g(n)), если с = const ;

0(g(n))*0(g(n)) = O(g(n)); O(O(g(n))) = O(g(n));

O(f(n))*O(g(n)) = 0(f(n)g(n)); 0(f(n)g(n)) = f(n)0(g(n)).

Написанные равенства всегда односторонни. Так, пишется 3n²+n = 0(n²), но никогда не пишется 0(n²) = 3n²+n

Полиномиальным алгоритмом или алгоритмом полиномиальной временной сложности называется алгоритм, у которого временная сложность равна T = 0(р(n)), где р(n) - некоторый полином, а n - размер входа. Алгоритмы, временная сложность которых есть , где с = const, p(n) - полином, называются экспоненциальными.

В следующей таблице из работы [24] приведены времена для различных классов алгоритмов при n = 10⁶ на последовательной машине, выполняющей 10⁶ операций в секунду.

Класс Сложность алгоритма	Число операций для п=106	Реальное время
Полиномиальный	0(1)	1 11111	1 мс
Линейный Квадратичный Кубичный	0(n) 0(n2) 0(n3)		1 c 10 дней 27397 лет
Экспоненциальный	0()		лет

Задачи, которые решаются в полиномиальное время, называются решаемыми (tractable), так как они могут обычно быть решены для входа достаточно реального размера. Задачи, которые не могут быть систематически решаемыми за полиномиальное время, называют нерешаемыми (intractable), или просто трудными (hard).

Следует заметить, что существуют и алгоритмически неразрешимые задачи (undecidabie). Они настолько трудны, что невозможно создать алгоритм для их решения. Такова, например, десятая проблема Гильберта: существует ли алгоритм, решающий в целых числах уравнение = 0 для многочлена р с целыми коэффициентами. Ю.В. Матиясевич показал, что такого алгоритма в принципе не существует. Другие примеры неразрешимых задач были ранее указаны Тьюрингом.

Далее приведена классификация задач по сложности и дано наглядное возможное их соотношение друг с другом (такое соотношение неизвестно). Схема приведена по работе [24], но несколько изменена для удобства изображения.



Класс P или P-TIME (Poiyncriai) состоит из всех задач, решаемых за полиномальное время. Примеры приведены далее.

Класс NP или NP-TIME (Nondeterrlnlstic Polynomial) состоит из всех задач, решаемых за полиномиальное время на недетерминированной машине Тьюринга, способной параллельно выполнять неограниченное количество независимых вычислений. Это означает, что если вариант решения проверяется, то он может быть проверен на машине Тьюринга за полиномиальное время. Конечно, это не означает решить задачу, так как нет гарантии, что машина угадает правильное решение. Чтобы математически решать задачу из NP класса, надо, по-видимому, тратить экспоненциальное время. Примером такой задачи является "задача рюкзака" ("knapsack problem"): дано множество из n целых чисел а = {} и целое число S, требуется определить, существует ли множество чисел из а, сумма которых равна S. Ясно, что эта задача принадлежит np классу, так как для любого подмножества чисел в а легко проверить, равна ли их сумма числу s. Найти же подмножество чисел, сумма которых равна S, гораздо сложнее. Существует всего таких подмножеств (включая пустое множество), и проверка их всех имеет временную сложность T=0().

...