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

Практически любой блочный шифр может использоваться для подтверждения подлинности сообщения, но лучше использовать режимы, распространяющие единичную ошибку на весь последующий шифртекст (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).

Параметры:

pазмер блока, бит	128, 192, 256
pазмер ключа, бит	128, 192, 256
число раундов	10, 12, 14
pазмер ключевого элемента, бит	128, 192, 256 (равен размеру блока)
число ключевых элементов	11, 13, 15 (на 1 больше числа раундов)

Замечания:

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

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

pазмер ключа	128	192	256
размер блока
128	10	12	14
192	12	12	14
256	14	14	14

Иными словами, из двух размеров выбирается максимальный, и если он равен 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.

Рис. 1. Цикл шифрования Rijndael - схема преобразования данных.

Рис. 2. Цикл шифрования Rijndael - схема алгоритма.

На рисунках использованы следующие обозначения: 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.

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

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

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

Рис. 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.