i align="justify"> M , на яку проводиться множення в ході раундового перетворення. Метою цього кроку є дифузія зміни в одному байті на весь стовпець матриці. При виборі матриці M крім традиційних вимог оборотності і простоти описи були прийняті до уваги наступні бажані характеристики перетворення:
· лінійність в поле GF (2);
· достатній рівень дифузії;
· швидкість реалізації на 8-бітових процесорах;
Даний крок перетворення може також бути представлений як множення стовпців преобразуемой матриці даних, що інтерпретуються як поліноми третього ступеня з коефіцієнтами з поля GF (28), на іншій поліном з коефіцієнтами з цього ж поля, по модулю полінома ( x 4 + 1). Згідно 3-му з перерахованих вище вимог, коефіцієнти множника повинні бути якомога менше. Автори шифру вибрали наступний поліном:
Та ж процедура, записана в матричній формі, еквівалентна множенню зліва на матрицю M - ціркулянт полінома c ( x ).
Таким чином, на відміну від ГОСТ 28147-89, раунд якого складено з традиційних для криптоалгоритмів «першої хвилі» операцій, - підстановок в малих бітових групах, бітових перестановок (зрушень) та адитивних операцій комбінування елементів даних , - при конструюванні шифру Rijndael широко використаний алгебраїчний підхід. Це стосується головним чином двох основних перетворень шифру - байтовой заміни та операції перемішування стовпців матриці даних за допомогою її множення зліва на матрицю M .
. Дифузійні характеристики
Розгляд характеристик стійкості алгоритмів почнемо з дослідження характеристик дифузії. Спочатку розглянемо поширення змін у вихідних даних на вихідне значення функції шифрування алгоритму ГОСТ. Припустимо, що у вхідному 32-бітовому значенні змінений один біт. Перша операція функції шифрування - це додавання по модулю 232, тобто з перенесенням з молодших розрядів в старші. Теоретично, зміна самого молодшого біта операнда може призвести до зміни всіх бітів суми. Однак ймовірність цієї події надзвичайно мала. Можна показати, що за умови равновероятного і незалежного розподілу бітів операндів на множині {0,1} ймовірність події, що вплив одного біта операнда поширюється вліво рівно на n бітів результату, дорівнює приблизно 2- n . Це означає, що якщо змінити значення одного біта операнда на протилежне, то крім відповідного йому біта результату, який інвертується в будь-якому випадку, рівно n бітів результату, що знаходяться лівіше інвертованого, також поміняють значення на протилежне з вказаною вище ймовірністю. Виходячи з цього, можна констатувати, що при складанні двох чисел по модулю 232 практичне значення має тільки вплив біта операнда на не більше ніж чотири старших біта результату.
Припустимо тепер, що в аргументі функції шифрування змінив значення один з бітів. Це призведе до того, що після підсумовування з ключовим елементом це зміна пошириться на групу з 5 бітів суми. Наступною операцією в функції шифрування є заміна в 4-бітових групах. Група з п'яти суміжних бітів суми покривається рівно двома такими групами. Отже, після виконання заміни зміна пошириться на 8 бітів, що входять в ці дві групи. Подальше обертання на 11 біт вліво не змінює числа порушених бітів, проте змінює їхнє положення в слові - ці 8 бітів виявляються розподіленими по трьом суміжним 4-бітовим групам, як показано нижче на малюнку 3. На малюнку кожен стовпчик відповідає 4-бітової групі, порушені зміною біти виділені сірим кольором. шифрування алгоритму ГОСТ28147-89.
Рис. 3. Дифузія зміни у вихідних даних через функцію шифрування алгоритму ГОСТ28147-89.
Тепер простежимо зміна у вихідних даних через кілька раундів шифрування в припущенні, що инвертирован біт з молодшої половини блоку. Відповідні діаграми наведені нижче на малюнку 4.
Рис. 4. Дифузія зміни у вихідних даних через кілька раундів шифрування алгоритму ГОСТ28147-89.
Як видно з малюнка 4, зміни в одному бите поширюються на весь шіфруемий блок після чотирьох раундів шифрування, якщо у вихідному блоці змінений біт з молодшої половини. Якщо ж буде інвертований біт зі старшої половини, то це число збільшиться на 1 і стане одно 5. Таким чином, за 32 раунду шифрування, передбачені ГОСТом, дані встигають повністю перемішатися приблизно 32: 5=6 разів.
Тепер розглянемо дифузійні характеристики алгоритму Rijndael. Перша операція раунду шифрування цього алгоритму - побітовое підсумовування з ключем по модулю 2 - не призводит...
