Аутентификация сообщений

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

а1, а2, …аn – о.т., b1,b2, …bn – ш.т.

1. Сообщение передается в открытом виде (a1,a2…..an, U). U = bn – вектор аутентификации. Приемник зашифровывает (a1,a2…..an) и проверяет последний зашифрованный бит с U. Вероятность принять искажение за истину = ½ в степени n. Рекомендуется n =24.

2. Сообщение передается в шифрованном виде. U – первые m бит последнего зашифрованного блока. Угадать U практически невозможно. Передается (b1,b2…..bn, U). После получения сравниваем.

Шифр Rijndael выполнен в архитектуре "Квадрат" (Square).

Параметры:

Замечания:

(1) В качестве стандарта принят вариант шифра только с размером блока 128 бит.

(2) Число раундов шифрования определяется в зависимости от размера блока и ключа по следующей таблице:

Иными словами, из двух размеров выбирается максимальный, и если он равен 128 бит, то используется 10 раундов, если 192 бита, то 12, и если 256 - то 14 раундов шифрования.

В Rijndael блоки открытых и зашифрованных данных, соответственно T и T', представляются в виде массивов из 16, 24 или 32 байтов:

T = (t₁, t₂,...,t_N) T' = (t'₁, t'₂,...,t'_N) | t | = | t' | = 8, N {16, 24, 32}.

В соответсвии с использованными архитектурными принципами в ходе криптографических преобразований исходный и зашифрованный блоки данных, а также все промежуточные результаты процесса шифрования интерпретируются как матрицы байтов размером 4 n, откуда получаем n = N/4, n {4, 6, 8}. Матрицы заполняются байтами входного блока (открытых данных при зашифровании и зашифрованных данных при расшифровании соответсвенно) по столбцам сверху вниз и слева направо, и в точно таком же порядке извлекаются байты из матрицы-результата:

, .

Схема преобразования данных при зашифровании показана на рисунке 1, схема соответсвующего алгоритма - на русунке 2.

На рисунках использованы следующие обозначения: T, T' - открытый и зашифрованный блоки данных соответственно; k_i - i-тый ключевой элемент; F, F' - регулярное нелинейное преобразование и преобразование последнего раунда соответсвенно; X_i - промежуточное состояние шифруемого блока после прибавления i-того ключевого элемента.

Как видно из рисунков 1 и 2, процесс зашифрования состоит из чередующихся прибавлений ключевых элементов к блоку данных и нелинейного преобразования этого блока:

T' = E_K(T) = k_R+1 F'(k_R F(k_R-1 ... F(k₂ F(k₁ T))...)).

Число R раундов шифрования переменное и зависит от размера блока и данных ключа. Прибавление ключевых элементов, которым начинается и заканчивается процесс шифрования, а также некоторые другие операции раундового преобразования выполняется побайтно в конечном поле Галуа GF(2⁸), полевой операцией сложения в нем является побитовое суммирование по модулю 2. Соответсвенно, каждый ключевой элемент является байтовой матрицей того же самого размера, что и блок данных. За один раунд шифрования преобразуется полный блок данных, а не его часть, как в сетях Файстеля. На последнем раунде функция нелинейного преобразования отличается от аналогичной функции, используемой в остальных раундах - это сделано для обеспечения алгоритмической эквивалентности прямого и обратного преобразований шифрования.

Процесс расшифрования блока данных алгоритмически идентичен процессу его зашифрования и, следовательно, рисунки 1 и 2 также справедливы и для него, если через T обозначить блок зашифрованных данных, а через T' - открытых. Однако различия между этими двумя процедурами в архитектуре "Квадрат" несколько более существенны, чем в сетях Файстеля - они различаются не только порядком использовани ключевых элементов в раундах шифрования, но и самими этими элементами, и некоторыми другими константами, используемыми в алгоритме.

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

X' = F(X) = M (S(X)).

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

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

Вся нелинейность преобразования сосредоточена в его первом шаге - замене, второй и третий шаги являются линейными. Первый шаг служит для перемешивания информации внутри байтов, второй обепечивает "экспорт" изменений в другие столбцы, третий осуществляет диффузию изменений в одном элементе матрицы на весь соответсвующий столбец. Таким образом, за два раунда достигается диффузия изменений в одном единственном бите на весь блок данных. Ниже каждый из указанных шагов рассмотрен подробно, при этом некоторые преобразования байтов определены в терминах операций в конечном поле GF(2⁸), порожденном неприводимым полиномом m(x) над полем GF(2): m(x) = x⁸+x⁴+x³+x+1. Операция сложения в этом поле является ни чем иным, как побитовым суммированием по модулю 2, умножение в соответствие с определением поля выполняется как обычное умножение полиномов над GF(2) по модулю полинома m(x). При манипулировании с байтами данных как с элементами поля GF(2⁸) каждый бит соответсвует слагаемому вида xⁱ в соответсвии со старшинством бита в байте. Можно сказать, что если байт с целочисленным значением b представлен в виде полинома B(x), то справедливо b = B(2).

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

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

k₁, k₂, k₃, ... , k_R, k_R+1,

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

k_R+1, M ^-1 k_R, ... , M ^-1 k₃, M ^-1 k₂, k₁.

2. На шаге побайтовой замены используется узел замен S^-1 обратный тому, что применяется в процедуре зашифрования S. Это означает, что каково бы ни было байтовое значение b, всегда справедливо следующее соотношение:

S ^-1[S[b]] = b.

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

С_i' = n - C_i, 2 i 4.

4. На шаге умножения слева на постоянную матрицу используется матрица M ^-1, обратная используемой при зашифровании матрице M.

Размер ключа в шифре Rijndael равен 128, 192 или 256 бит. Размер ключевого элемента, используемого на раунде, совпадает с размером блока и также равен 128, 192 или 256 бит независимо от размера ключа. Число раундов шифрования находится в пределах от 10 до 14. Массив ключевых элементов вырабатывается из ключа шифрования с использованием описанной ниже процедуры "развертывания" ключа.

Как и блок данных, ключ может быть представлен в виде массива байтов:

K = (b₁, b₂, ... ,  ), n_K - размер ключа в байтах, n_K {16, 24, 32}.

Алгоритм развертывания ключа оперирует 32-битовыми ключевыми словами W_i, интерпретируя их как четырехбайтовые массивы:

W_i = (w_i1, w_i2, w_i3, w_i4), | w_ij | = 8.

Первые q = n_K /4 ключевых слов получаются простым разделением ключа K на 4-байтовые фрагменты аналогично тому, как байтами шифруемого блока заполняются столбцы матрицы данных:

W₀ = (b₁, b₂, b₃, b₄), W₁ = (b₅, b₆, b₇, b₈), ................................... .

Необходимое число ключевых элементов на 1 больше числа раундов R, каждый ключевой элемент по размеру равен блоку данных (n_B байт) и содержит q_B = n_B /4 ключевых слов. Таким образом, всего необходимо Q = (R+1) q_B ключевых слов. Первые q ключевых слов составлены из байтов ключа как показано выше, остальные Q - q вырабатываются по следующему алгоритму:

При размере ключа 16 или 24 байта (q {4,6}) используется следующая итерационная формула:

, i = q..Q-1,

а при размере ключа 32 байта (q = 8) следующая:

, i = q..Q-1.

В приведенных выше формулах использованы следующие обозначения:

S(W) - побайтовая замена 32-битового слова, т.е. замена всех четырех входящих в него байтов с использованием штатного узла замен S шифра: если W = (w₁, w₂, w₃, w₄), то S(W) = (S[w₁], S[w₂], S[w₃], S[w₄]);

- циклический сдвиг 4-байтового вектора на один элемент влево: если W = (w₁, w₂, w₃, w₄), то (W) = (w₂, w₃, w₄, w₁);

P_j - 4-байтовый вектор (массив), задаваемый следующей формулой: P_j = (02 ^j-1, 00, 00, 00), где возведение в степень выполняется в ранее описанном конечном поле GF(2⁸).

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

S( (W)) P_j = (S[w₂] 02 ^j-1, S[w₃], S[w₄], S[w₁]).

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

Сбалансированность

Отображение называется сбалансированным, если для всех элементов V_n мощность множества полного прообраза равна , т.е. для .

Определение: Множество всех прообразов для элемента y называется его полным прообразом и обозначается p^-1(y).

Сильная нелинейность

Отображение называется сильно нелинейным, если нелинейными являются все его координатные функции.

, т.е. для : .

Полное перемешивание (или совершенность)

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

Если функция существенно зависит от i-ой координаты, то на соседних по i-ой координате наборах функция принимает разные значения, следовательно, соответствующий бит суммы будет увеличен на 1 (т.к. сумма – не XOR, а обычное действительное суммирование).

Строгий лавинный критерий (СЛК)

Отображение удовлетворяет СЛК, если : .

На случайно выхваченной паре соседних по i-ой координате наборах векторов функция принимает разные значения с вероятностью ½, следовательно, независимость от переменных распространяется лавинообразно при перемножении функций. СЛК означает, что фактически, если мы изменяем 1 бит на входе, то каждый выходной бит изменяется с вероятностью ½.

Некоррелированность (корреляционный иммунитет)

Отображение называется некоррелированным, если для  допустимых i, j функция является равновероятной, т.е. . По сути это означает, что .

Связи между сформулированными критериями

• Если L подчиняется ЛСК, то каждая координатная функция отображения L(x)/j не линейна по всем переменным.

Следствие : Если L подчиняется ЛСК, то оно сильно нелинейно.

• Если L подчиняется ЛСК, то L совершенна.

• Если - обратимое отображение, то при n<3 оно не удовлетворяет СЛК.

Вопрос 32.2. Цифровая подпись вслепую и ее применение

Впервые понятие цифровой подписи вслепую ввел David Chaum на CRYPTO’82. Он же предложил и первую реализацию этого понятия, используя алгоритм RSA. Схема подписи подразумевает участие 3-х человек: автор, подписывающий, проверяющий. Рассмотрим этапы генерации подписи:

• Инициализация. Подписывающий всем объявляет, какой схемой подписи он будет пользоваться. Например: он говорит, что будет пользоваться ЭЦП RSA, открытый ключ (n,e);

• Подготовка запроса и запрос подписи. Автор должен подготовить (замаскировать) свой документ, под которым нужно ставить подпись. Для этого автор вырабатывает случайный секретный параметр k. Затем он вычисляет функцию M’ = B(M,k), где M – открытый текст, а B – функция затемнения.

• Подпись. Подписывающий подписывает сообщение M’ и возвращает sign (M’) автору. Обозначим sign (M’) через S’.

• Выделение подписи к документу М. S = U(S’,k), где U – функция деослепления.

Останавливаясь подробнее на последнем этапе, Chaum предложил использовать схему RSA. Таким образом, алгоритм цифровой подписи вслепую можно представить следующим образом:

• Подписывающий генерирует секретный ключ (p,q) и объявляет открытый ключ (n,e).

• Осуществляется затемнение: (mod n). M’ обозначим через B(M,k), где k – случайное число из диапазона от 1 до n.

• Подписание затемненного сообщения:

• (mod n) = ( mod n) = (mod n) = (mod n).

• Деослепление происходит по схеме: (mod n) = S.