У нашій країні встановлено єдиний алгоритм криптографічного подання даних для систем обробки інформації в мережах ЕОМ, окремих обчислювальних комплексів та ЕОМ, що визначається ГОСТ 28147-89.
Цей алгоритм криптографічного перетворення даних являє собою 64-бітовий блоковий алгоритм з 256-бітовим ключем, призначений для апаратної та програмної реалізації, задовольняє криптографічним вимогам і не накладає обмежень на ступінь секретності інформації, що захищається.
При описі алгоритму використовуються такі позначення:
L та R - послідовності бітів;
LR - конкатенація послідовностей L і R, в якій біти послідовності R йдуть за бітами послідовності L;
(+) - порозрядне додавання за модулем 2 (операція "що виключає АБО");
[+] - додавання 32-розрядних чисел за модулем 2 32;
(+) - додавання 32-розрядних чисел за модулем 2 32 -1.
Числа підсумовуються за таким правилом:
A [+] B = A + B, якщо A + B< 2 32 ,
A [+] B = A + B - 2 32 якщо A + B >= 2 32 . A (+) B = A + B якщо A + B< 2^32 - 1,
A {+} B = A + B - (2^32 - 1), если A + B >= 2^32 - 1.
Алгоритм передбачає чотири режими роботи:
У будь-якому випадку для шифрування даних використовується 256-бітовий ключ K, який представляється у вигляді восьми 32-бітових підключів K i:
K = K 7 K 6 K 5 K 4 K 3 K 2 K 1 K 0 .
Розшифрування виконується за тим самим ключем, що і шифрування, але цей процес є інверсією процесу шифрування даних. Режим простої заміни
Перший і найпростіший режим - заміна. Дані, що підлягають шифруванню, розбивають на 64-бітові блоки. Процедура шифрування блоку відкритих даних T0 включає 32 цикли (j=1...32).
Блок T 0 поділяється на дві послідовності по 32 біти: В(0)A(0), де В(0) - ліві або старші біти, A(0) - праві або молодші біти.
Ці послідовності вводять накопичувачі N 1 і N 2 перед початком першого циклу шифрування.
Перший цикл (j=1) процедури шифрування 64-бітового блоку даних описується такими формулами:
Тут i означає номер ітерації (i = 1, 2,..., 32).
Функція f називається функцією шифрування. Її аргументом є сума за модулем 2 32 числа A(i), отриманого на попередньому кроці ітерації, та числа X(j) ключа (розмірність кожного з цих чисел дорівнює 32 знакам).
Функція шифрування включає дві операції над отриманою 32-розрядною сумою. Перша операція називається підстановкою До. Блок підстановки До складається з 8 вузлів заміни К(1) ... До(8) з пам'яттю 64 біт кожен. 32-розрядний вектор, що надходить на блок підстановки, розбивається на 8 послідовно йдуть 4-х розрядних векторів, кожен з яких перетворюється в 4-х розрядний вектор відповідним вузлом заміни, що представляє собою таблицю з 16 цілих чисел в діапазоні 0...15.
Вхідний вектор визначає адресу рядка в таблиці, число якої є вихідним вектором. Потім 4-розрядні вихідні вектори послідовно об'єднуються в 32-розрядний вектор. Таблиці блоку підстановки містить ключові елементи, загальні для мережі ЕОМ і рідко змінювані.
Друга операція - циклічне зрушення вліво 32-розрядного вектора, отриманого в результаті підстановки К. 64-розрядний блок зашифрованих даних Т ш представляється у вигляді Т ш =A(32)B(32).
Інші блоки відкритих даних у режимі простої заміни зашифровуються аналогічно.
Слід пам'ятати, що режим простої заміни можна використовувати для шифрування даних лише в обмежених випадках. До цих випадків відноситься вироблення ключа і зашифрування його із забезпеченням імітозахисту (захисту від нав'язування хибних даних) для передачі каналами зв'язку або зберігання в пам'яті ЕОМ. Режим гамування
Відкриті дані, розбиті на 64-розрядні блоки Т(i) (i=1, 2,..., m, де m визначається об'ємом даних, що шифруються), зашифровуються в режимі гамування шляхом порозрядного складання по модулю 2 з гамою шифру Г ш, яка виробляється блоками по 64 біт, тобто Г ш = (Г (1), Г (2), ..., Г (i), ..., Г (m)).
Рівняння зашифрування даних у режимі гамування може бути представлене у такому вигляді:
Ш(i) = A(Y(i-1) [+] C2, Z(i-1) (+) C1) (+) T(i) = Г(i) (+) T(i) .
Тут Ш(i) - 64-розрядний блок зашифрованого тексту,
A - функція шифрування в режимі простої заміни (аргументами цієї функції є два 32-розрядні числа),
С1 та С2 - константи, задані в ГОСТ 28147-89,
Y(i) та Z(i) - величини, які визначаються ітераційно у міру формування гами наступним чином:
(Y(0), Z(0)) = A(S), де S - 64-розрядна двійкова послідовність (синхропосилання);
(Y(i), Z(i)) = (Y(i-1) [+] C2, Z(i-1) (+) C1) для i = 1, 2,...,m.
Розшифрування даних можливе лише за наявності синхропосилання, яка не є секретним елементом шифру і може зберігатися в пам'яті ЕОМ або передаватися каналами зв'язку разом із зашированими даними. Режим гамування із зворотним зв'язком
Режим гамуванняз зворотним зв'язкомдуже схожий на режим гамування. Як і режимі гамування відкриті дані, розбиті на 64-розрядні блоки Т(i) (i=1, 2,..., m , де m визначається об'ємом даних, що шифруються), зашифровуються шляхом порозрядного складання по модулю 2 з гамою шифру Г ш, яка виробляється блоками по 64 біт:
Г ш = (Г (1), Г (2), ..., Г (i), ..., Г (m)).
Число двійкових розрядів у блоці Т(m) може бути менше 64, при цьому невикористана частина шифрування гами шифру з блоку Г(m) відкидається.
Рівняння зашифрування даних у режимі гамування зі зворотним зв'язком може бути представлене в наступному вигляді:
Тут Ш(i) - 64-розрядний блок зашифрованого тексту,
A – функція шифрування в режимі простої заміни. Аргументом функції першому кроці ітеративного алгоритму є 64-разрядная синхропосилання, але в всіх наступних - попередній блок зашифрованих даних Ш(i-1).
Вироблення імітівставки
Процес вироблення імітівстакиоднаковий для будь-якого з режимів шифрування даних.
Імітівставка - це блок з р біт (імітівставка Ір), який виробляється або перед шифруванням всього повідомлення, або паралельно з шифруванням по блоках. Перші блоки відкритих даних, які беруть участь у виробленні імітівставки, можуть містити службову інформацію (наприклад, адресну частину, час, синхропосилання) і не зашифровуватися. Значення параметра р (кількість двійкових розрядів в імітовставці) визначається криптографічними вимогами з урахуванням того, що ймовірність нав'язування хибних перешкод дорівнює 1/2^р.
Для отримання імітівставки відкриті дані подаються у вигляді 64-розрядних блоків Т(i) (i = 1, 2,..., m , де m визначається обсягом даних, що шифруються). Перший блок відкритих даних Т(1) піддається перетворенню, що відповідає першим 16 циклів алгоритму зашифрування в режимі простої заміни. Причому як ключ для вироблення імітівставки використовується ключ, яким шифруються дані.
Отримане після 16 циклів роботи 64-розрядне число підсумовується модулем 2 з другим блоком відкритих даних Т(2). Результат підсумовування знову перетворюється, що відповідає першим 16 циклам алгоритму зашифрування в режимі простої заміни. Отримане 64-розрядне число підсумовується модулем 2 з третім блоком відкритих даних Т(3) і т.д. Останній блок Т(m) при необхідності доповнений до повного 64-розрядного блоку нулями, підсумовується по модулю 2 з результатом роботи на кроці m-1, після чого зашифровується в режимі простої заміни перших 16 циклів роботи алгоритму. З отриманого 64-розрядного числа вибирається відрізок Ір довжиною рбіт.
Імітовставка Ір передається каналом зв'язку чи пам'ять ЕОМ після зашифрованих даних. Зашифровані дані, що надійшли, розшифровуються, і з отриманих блоків відкритих даних T(i) виробляється імітівставка Ір", яка потім порівнюється з імітівставкою Ір, отриманої з каналу зв'язку або з пам'яті ЕОМ. У разі розбіжності імітівставок всі розшифровані дані вважають помилковими.
Короткий опис шифру
ГОСТ 28147-89 - радянський та російський стандарт симетричного шифрування, введений у 1990 році, також є стандартом СНД. Повна назва – «ГОСТ 28147-89 Системи обробки інформації. Захист криптографічний. Алгоритм криптографічного перетворення». Блоковий шифроалгоритм. При використанні методу шифрування з гамуванням може виконувати функції потокового шифроалгоритму.
ГОСТ 28147-89 - блоковий шифр з 256-бітним ключем та 32 циклами перетворення, що оперує 64-бітними блоками. Основа алгоритму шифру – Мережа Фейстеля. Базовим режимом шифрування за ГОСТ 28147-89 є режим простої заміни (визначено також складніші режими гамування, гамування зі зворотним зв'язком та режим імітівставки).
Принцип роботи алгоритму
Алгоритм принципово не відрізняється від DES. У ньому також відбуваються цикли шифрування (їх 32) за схемою Фейстеля (Рис. 2.9).
Мал. 2.9. Раунди шифрування алгоритму ГОСТ 28147-89.
Для генерації підключів вихідний 256-бітний ключ розбивається на вісім 32-бітових блоків: k 1 … k 8 . Ключі k 9 … k 24 є циклічним повторенням ключів k 1 … k 8 (нумеруються від молодших біт до старших). Ключі k 25 … k 32 є ключами k 1 … k 8 , що у зворотному порядку.
Після виконання всіх 32 раундів алгоритму, блоки A 33 і B 33 склеюються (слід звернути увагу на те, що старшим бітом стає A 33 а молодшим - B 33) - результат є результат роботи алгоритму.
Функція f(A i ,K i) обчислюється наступним чином: A i і K i складаються за модулем 2 32 потім результат розбивається на вісім 4-бітових підпослідовностей, кожна з яких надходить на вхід свого вузла таблиці замін(у порядку зростання старшинства бітів), званого нижче S-блоком. Загальна кількість S-блоків ГОСТу – вісім, тобто стільки ж, скільки і підпослідовностей. Кожен S-блокявляє собою перестановку чисел від 0 до 15. Перша 4-бітна підпослідовність потрапляє на вхід першого S-блоку, друга - на вхід другого і т.д. ліворуч (до старших розрядів) на 11 бітів. Усі вісім S-блоків можуть бути різними. Фактично вони можуть бути додатковим ключовим матеріалом, але частіше є параметром схеми, загальним для певної групи користувачів. У тексті стандарту вказується, що постачання заповнення вузлів заміни (S-блоків) виробляється у порядку, тобто. розробником алгоритму. Спільнота російських розробників СКЗІ погодила вузли заміни, що використовуються в Інтернет.
Розшифрування виконується як і, як і зашифрування, але інвертується порядок підключень k i .
Режими роботи алгоритму ГОСТ 28147-89
Алгоритм ГОСТ 28147-89 має чотири режими роботи.
1. Режимпростий заміниприймає на вхід дані, розмір яких кратний 64-м бітам. Результатом шифрування є вхідний текст, перетворений блоками по 64 біта у разі зашифрування циклом "32-З", а у разі розшифрування - циклом "32-Р".
2. Режимгамуванняприймає на вхід дані будь-якого розміру, а також додатковий 64-бітовий параметр - синхропосилку. У ході роботи синхропосилання перетворюється в циклі «32-З», результат ділиться на дві частини. Перша частина складається за модулем 2 32 з постійним значенням 1010101 16 . Якщо друга частина дорівнює 232-1, то її значення не змінюється, інакше вона складається за модулем 232-1 з постійним значенням 1010104 16 . Отримане об'єднанням обох перетворених частин значення, зване гамою шифру, надходить цикл «32-З», його результат порязрядно складається за модулем 2 з 64-розрядним блоком вхідних даних. Якщо останній менше 64 розрядів, то зайві розряди отриманого значення відкидаються. Отримане значення подається на вихід. Якщо ще є вхідні дані, то дія повторюється: складений з 32-розрядних частин блок перетворюється частинами і так далі.
3. Режимгамування зі зворотним зв'язкомтакож приймає на вхід дані будь-якого розміру та синхропосилання. Блок вхідних даних порозрядно складається за модулем 2 з результатом перетворення в циклі «32-З» синхропосилання. Отримане значення подається на вихід. Значення синхропосилання замінюється у разі зашифрування вихідним блоком, а у разі розшифрування - вхідним, тобто зашифрованим. Якщо останній блок вхідних даних менше 64 розрядів, зайві розряди гами (виходу циклу «32-З») відкидаються. Якщо є вхідні дані, то дія повторюється: з результату зашифрування заміненого значення утворюється гамма шифру тощо.
4. Режим виробіткуімітівставкиприймає на вхід дані, розмір яких не менше двох повних 64-розрядних блоків, а повертає 64-розрядний блок даних, званий імітівставкою. Тимчасове 64-бітове значення встановлюється в 0, далі, поки є вхідні дані, воно складається по модулю 2 з результатом виконання циклу «16-З», на вхід якого подається блок вхідних даних. Після закінчення вхідних даних тимчасове значення повертається як наслідок.
Криптоаналіз шифру
У шифрі ГОСТ 28147-89 використовується 256-бітовий ключ і обсяг ключового простору становить 2256 . На жодному з існуючих в даний час комп'ютері загального застосування не можна підібрати ключ за час, менший за багато сотень років. Російський стандарт ГОСТ 28147-89 проектувався з великим запасом і за стійкістю на багато порядків перевершує американський стандарт DES з його реальним розміром ключа 56 біт і обсягом ключового простору всього 2 56 .
Існують атаки і на повнораундовий ГОСТ 28147-89 без будь-яких модифікацій. Одна з перших відкритих робіт, в яких було проведено аналіз алгоритму, використовує слабкість процедури розширення ключа ряду відомих алгоритмів шифрування. Зокрема, повнораундовий алгоритм ДЕРЖСТАНДАРТ 28147-89 може бути розкритий за допомогою диференціального криптоаналізу на зв'язаних ключах, але тільки у разі використання слабких таблиць замін. 24-раундовий варіант алгоритму (у якому відсутні перші 8 раундів) розкривається аналогічним чином при будь-яких таблицях замін, однак сильні таблиці замін роблять таку атаку абсолютно непрактичною.
Вітчизняні вчені О.Г. Ростовцев та Є.Б. Маховенко в 2001 р. запропонували принципово новий метод криптоаналізу шляхом формування цільової функції від відомого відкритого тексту, відповідного йому шифртексту та шуканого значення ключа та знаходження її екстремуму, що відповідає справжньому значенню ключа. Вони ж знайшли великий клас слабких ключів алгоритму ГОСТ 28147-89, які дозволяють розкрити алгоритм за допомогою всього 4-х вибраних відкритих текстів і відповідних шифротекстів з досить низькою складністю.
У 2004 році група фахівців із Кореї запропонувала атаку, за допомогою якої, використовуючи диференціальний криптоаналіз на зв'язаних ключах, можна отримати з ймовірністю 91,7% 12 біт секретного ключа. Для атаки потрібно 2 35 вибраних відкритих текстів та 2 36 операцій шифрування. Як видно, дана атака практично марна для реального розтину алгоритму.
Таблиця замін є довготривалим ключовим елементом, тобто діє протягом набагато більше тривалого термінуніж окремий ключ. Передбачається, що вона є спільною всім вузлів шифрування у межах однієї системи криптографічного захисту. Від якості таблиці залежить якість шифру. При "сильній" таблиці замін стійкість шифру не опускається нижче деякої допустимої межі навіть у разі її розголошення. І навпаки, використання "слабкої" таблиці може зменшити стійкість шифру до неприпустимо низької межі. Жодної інформації щодо якості таблиці замін у відкритого друкуРосії не публікувалося, однак існування "слабких" таблиць не викликає сумніву - прикладом може бути "тривіальна" таблиця замін, за якою кожне значення замінюється на нього самого. У ряді робіт помилково робиться висновок про те, що секретні таблиці замін алгоритму ГОСТ 28147-89 можуть бути частиною ключа і збільшувати його ефективну довжину (що несуттєво, оскільки алгоритм має дуже великий 256-бітний ключ).
Цей алгоритм є обов'язковим для застосування як алгоритму шифрування в державні організаціїРФ та ряді комерційних.
Опис алгоритму
Схема алгоритму показано на рис. 3.1. Як видно, схема цього алгоритму досить проста, що однозначно спрощує його програмну чи апаратну реалізацію.
Алгоритм ГОСТ 28147-89 шифрує інформацію блоками по 64 біти, які розбиваються на два субблоки по 32 біти (N1 та N2). Субблок N1 певним чином обробляється, після чого його значення складається
зі значенням субблоку N2 (додавання виконується за модулем 2), потім субблоки змінюються місцями. Таке перетворення виконується певну кількість раундів: 16 або 32, залежно від режиму роботи алгоритму (описано далі). У кожному раунді виконуються такі операції:
1. Накладення ключа. Вміст субблоку /VI складається з модуля 2 32 з частиною ключа Кх.
Ключ шифрування алгоритму ГОСТ 28147-89 має розмірність 256 бітів, а Кх це його 32-бітна частина, тобто 256-бітний ключ шифрування представляється у вигляді конкатенації 32-бітових підключів (рис. 3.2):
Щ ATI, АГ2, П, АГ4, К5, Кб, К7.
У процесі шифрування використовується одна з цих з'єднань — залежно від номера раунду та режиму роботи алгоритму.
Мал. 3.1. Схема алгоритму ГОСТ 28147-
Мал. 3.2. Ключ шифрування алгоритму ГОСТ 28147-89
2. Таблична заміна. Після накладання ключа субблок /VI розбивається на 8 частин по 4 біти, значення кожної з яких окремо замінюється відповідно до таблиці заміни цієї частини субблока. Табличні заміни (Substitution box, S-box) часто використовуються в сучасних алгоритмахшифрування, тому варто розглянути їх детальніше.
Таблична заміна використовується таким чином: на вхід подається блок даних певної розмірності (у цьому випадку - 4-бітний), числове подання якого визначає номер вихідного значення. Наприклад, маємо S-box такого вигляду:
4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1.
Нехай на вхід прийшов 4-бітний блок «0100», тобто значення 4. Відповідно до таблиці, вихідне значення дорівнюватиме 15, тобто. "1111" (0 замінюється на 4, 1 - на 11, значення 2 не змінюється і т. д.).
Як видно, схема алгоритму дуже проста, що означає, що найбільше навантаження шифрування даних лягає на таблиці замін. На жаль, алгоритм має ту властивість, що існують «слабкі» таблиці замін, при використанні яких алгоритм може бути розкритий криптоаналітичними методами. До слабких відноситься, наприклад, таблиця, в якій вихід дорівнює входу :
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.
3. Побітовий циклічний зсув вліво на 11 біт.
Режими роботи алгоритму
Алгоритм ГОСТ 28147-89 має 4 режими роботи:
□ режим простої заміни;
□ режим гамування;
режим гамування зі зворотним зв'язком;
□ режим вироблення імітоприставок.
Ці режими дещо відрізняються від загальноприйнятих (описаних у розд. 1.4), тому варто розглянути їх детальніше.
Дані режими мають різне призначення, але використовують те саме описане вище шифруюче перетворення.
Режим простої заміни
У режимі простої заміни для зашифровування кожного 64-бітного блоку інформації просто виконуються 32 описані вище раунди. 32-бітові підключи використовуються в наступній послідовності:
□ КО, Kl, К2, КЗ, К4, К5, Кб, АГ7, КО, ATI тощо — у раундах з 1-го по 24-й;
□ К1, Кб, К5, К4, КЗ, К2, К\, КО -в раундах з 25-го по 32-й.
Розшифровування в режимі простої заміни проводиться так само, але з дещо іншою послідовністю застосування підключень:
□ ДО, К\, К2, КЗ, К4, К5, Кб, КП - в раундах з 1-го по 8-й;
□ КП, Кб, К5, К4, КЗ, К2, К\, КО, К1, Кб і т. д. - в раундах з 9-го по 32-й.
Аналогічно стандартному режиму ЄСВ, через окреме шифрування блоків режим простої заміни категорично не рекомендується використовувати для шифрування даних; він повинен використовуватися тільки для шифрування інших ключів шифрування багатосхемних схемах.
Режим гамування
У режимі гамування (рис. 3.3) кожен блок відкритого тексту побітно складається по модулю 2 з гаммовим блоком шифру розміром 64 біта. Гама шифру - це спеціальна послідовність, яка виробляється за допомогою описаних вище перетворень таким чином:
1. У регістри N1 і N2 записується їх початкове заповнення-64-бітна величина, звана «синхропосилкою» (синхропосилка, практично, є аналогом вектора ініціалізації в режимах СВС, CFB і OFB).
2. Зашифровування вмісту регістрів /VI і N2 (в даному випадку — синхропосилання) виконується в режимі простої заміни.
3. Вміст N1 складається за модулем (2 32 – 1) з константою CI = 2 24 + 2 16 + 2 8 + 4 , результат додавання записується в регістр /VI.
4. Вміст N2 складається за модулем 2 з константою С2 = 2 24 + 2 16 + 2 8 +1, результат додавання записується в регістр N2.
5. Вміст регістрів /VI і N2 подається на вихід як 64-бітний блок гами шифру (тобто в даному випадку /VI і N2 утворюють перший блок гами).
6. Якщо необхідний наступний блок гами (тобто необхідно продовжити зашифрування або розшифрування), повертається до кроку 2.
Для розшифровування аналогічно виконується вироблення гами, потім знову застосовується операція XOR до біт зашифрованого тексту і гами.
Для вироблення тієї ж гами шифру у користувача, що розшифровує криптограму, повинен бути той самий ключ і те ж значення синхропосилання, які застосовувалися при зашифруванні інформації. В іншому випадку отримати вихідний текст із зашифрованого не вдасться.
У більшості реалізацій алгоритму ГОСТ 28147-89 синхропосилання не є секретним елементом, проте синхропосилання може бути так само секретна, як і ключ шифрування. В цьому випадку можна вважати, що ефективна довжина ключа алгоритму (256 бітів) збільшується ще на 64 біта синхропосилання, яку можна розглядати як додатковий ключовий елемент.
Режим гамування із зворотним зв'язком
У режимі гамування зі зворотним зв'язком як заповнення регістрів /VI і Л/2, починаючи з 2-го блоку, використовується не попередній блок гами, а результат зашифровування попереднього блоку відкритого тексту (рис. 3.4). Перший блок у цьому режимі генерується повністю аналогічно попередньому.
Мал. 3.4. Вироблення гами шифру в режимі гамування зі зворотним зв'язком
Режим вироблення імітоприставки
Імітоприставка — це криптографічна контрольна сума, яка обчислюється з використанням ключа шифрування та призначена для перевірки цілісності повідомлень. Для обчислення існує спеціальний режим алгоритму ГОСТ 28147-89.
Генерація імітоприставки виконується таким чином:
1. Перший 64-бітний блок інформації, для якої обчислюється імітоприставка, записується в регістри N1 і N2 і зашифровується в скороченому режимі простої заміни, в якому виконуються перші 16 з 32 раундів.
2. Отриманий результат підсумовується за модулем 2 з наступним блоком інформації зі збереженням результату N1 і N2.
3. М і N2 знову зашифровуються у скороченому режимі простої заміни тощо до останнього блоку інформації.
Імітоприставкою вважається 64-бітовий результуючий вміст регістрів N1 і N2 або його частина. Найчастіше використовується 32-бітна імітоприставка, тобто половина вмісту регістрів. Цього достатньо, оскільки, як і будь-яка контрольна сума, імітоприставка призначена насамперед для захисту від випадкових спотворень інформації. Для захисту ж від навмисної модифікації даних застосовуються інші криптографічні методи — насамперед електронна цифровий підпис(Див. Розд. 1.1).
Імітоприставка використовується наступним чином:
1. При зашифруванні будь-якої інформації обчислюється імітоприставка відкритого тексту та надсилається разом із шифртекстом.
2. Після розшифровування імітоприставка знову обчислюється та порівнюється з надісланою.
3. Якщо обчислена і надіслана імітоприставки не збігаються - шифр-текст був спотворений під час передачі або використовувалися невірні ключі при розшифровуванні.
Імітоприставка особливо корисна для перевірки правильності розшифровування ключової інформації під час використання багатоключових схем.
Імітоприставка - це деякий аналог коду аутентифікації повідомлень MAC, що обчислюється в режимі СВС; відмінність полягає в тому, що при обчисленні імітоприставки не використовується синхропосилання, тоді як при обчисленні MAC використовується вектор ініціалізації.
Криптостійкість алгоритму
У 1994 р. опис алгоритму ГОСТ 28147-89 було перекладено англійською мовою та опубліковано; саме після цього почали з'являтись результати його аналізу, виконаного закордонними фахівцями; проте протягом значного часу не було знайдено будь-яких атак, що наближаються до практично здійсненних.
□ великої довжини ключа – 256 бітів; разом із секретною синхропосилкою ефективна довжина ключа збільшується до 320 бітів;
□ 32 раундів перетворень; вже після 8 раундів досягається повний ефект розсіювання вхідних даних: зміна одного біта блоку відкритого тексту вплине на всі біти блоку шифртексту, і навпаки, тобто існує багаторазовий запас стійкості.
Розглянемо результати криптоаналізу алгоритму ГОСТ 28147-89.
Аналіз таблиць замін
Оскільки таблиці замін у стандарті не наведені, у низці робіт (наприклад, в ) висловлюється припущення, що «компетентна організація» може видати як «хороші», і «погані» таблиці замін. Однак у найвідоміший експерт Брюс Шнайєр називає такі припущення «чутками». Зрозуміло, що криптостойкость алгоритму великою мірою залежить від властивостей таблиць замін, відповідно, існують слабкі таблиці замін (приклад див. вище), застосування яких може спростити розкриття алгоритму. Тим не менш, можливість використання різних таблиць замін здається досить гідною ідеєю, на користь якої можна навести два наступні факти з історії стандарту шифрування DES (подробиці див. Розд. 3.15):
□ атаки за допомогою як лінійного, так і диференціального криптоаналізу алгоритму DES використовують конкретні особливості таблиць замін; при використанні інших таблиць криптоаналіз доведеться розпочинати спочатку;
□ були зроблені спроби посилити DES проти лінійного та диференціального криптоаналізу шляхом використання більш стійких таблиць замін; такі таблиці, дійсно більш стійкі, були запропоновані, наприклад, алгоритмі s 5 DES ; але, на жаль, замінити DES на s 5 DES було неможливо, оскільки таблиці замін жорстко визначені в стандарті, відповідно реалізації алгоритму напевно не підтримують можливість зміни таблиць на інші.
У ряді робіт (наприклад, , і ) помилково робиться висновок про те, що секретні таблиці замін алгоритму ГОСТ 28147-89 можуть бути частиною ключа і збільшувати його ефективну довжину (що несуттєво, оскільки алгоритм має дуже великий 256-бітний ключ). Однак у роботі доведено, що секретні таблиці замін можуть бути обчислені за допомогою наступної атаки, яка може бути застосована практично:
1. Встановлюється нульовий ключ та виконується пошук «нульового вектора», тобто значення z = /(0), де /() — функція раунду алгоритму. Цей етап займає близько двох операцій шифрування.
2. За допомогою нульового вектора обчислюються значення таблиць замін, що займає не більше 2 11 операцій.
Модифікації алгоритму та їх аналіз
У роботі проведено криптоаналіз модифікацій алгоритму ГОСТ 28147-89:
□ алгоритму GOST-H, в якому, щодо оригінального алгоритму, змінено порядок використання підключей, а саме в раундах з 25-го по 32-й підключи використовуються в прямому порядку, тобто так само, як і в попередніх раундах алгоритму ;
□ 20-раундовий алгоритм GOST®, в раунді якого для накладання ключа використовується операція XOR замість додавання за модулем 2 32 .
За результатами аналізу зроблено висновок про те, що GOST-H і GOST© слабші за вихідний алгоритм ГОСТ 28147-89, оскільки обидва мають класи слабких ключів. Варто зазначити, що в частині криптоаналізу GOST © робота слово в слово повторює розділ, присвячений криптоаналізу алгоритму ГОСТ 28147-89, що вийшла 2000 відомої роботи (без будь-яких посилань на оригінал). Це ставить під сумнів професіоналізм авторів роботи та її результати.
Дуже цікава модифікація алгоритму запропонована в роботі: таблиці S ... Ss обов'язково повинні бути різними; у кожному раунді алгоритму має виконуватися їх перестановка за певним законом. Ця перестановка може бути залежною від ключа шифрування, а може бути і секретною (тобто є частиною ключа шифрування більшого розміру порівняно з вихідним 256-бітним ключем). Обидва ці варіанти, на думку їх авторів, суттєво посилюють стійкість алгоритму проти лінійного та диференціального криптоаналізу.
І ще одна модифікація, пов'язана з таблицями замін, наведена в роботі, в якій аналізується один із можливих методів обчислення таблиць замін на основі ключа шифрування. Автори роботи зробили висновок, що подібна залежність послаблює алгоритм, оскільки призводить до наявності слабких ключів та деяких потенційних уразливостей алгоритму.
Аналіз повнораундового алгоритму
Існують атаки і на повнораундовий ГОСТ 28147-89 без будь-яких модифікацій. Одна з перших відкритих робіт, в яких був проведений аналіз алгоритму, - широко відома робота - присвячена атакам, що використовують слабкість процедури розширення ключа ряду відомих алгоритмів шифрування. Зокрема, повнораундовий алгоритм ДЕРЖСТАНДАРТ 28147-89 може бути розкритий за допомогою диференціального криптоаналізу на зв'язаних ключах, але тільки у разі використання слабких таблиць замін. 24-раундовий варіант алгоритму (в якому відсутні перші 8 раундів) розкривається аналогічним чином при будь-яких таблицях замін, проте сильні таблиці замін (наприклад, наведена в ) роблять таку атаку абсолютно непрактичною.
Вітчизняні вчені А. Г. Ростовцев та Є. Б. Маховенко у 2001 р. у роботі запропонували принципово новий метод криптоаналізу (на думку авторів, суттєво більш ефективний, ніж лінійний та диференціальний криптоаналіз) шляхом формування цільової функції від відомого відкритого тексту, що відповідає йому шифртексту та шуканого значення ключа та знаходження її екстремуму, що відповідає справжньому значенню ключа. Вони ж знайшли великий клас слабких ключів алгоритму ГОСТ 28147-89, які дозволяють розкрити алгоритм за допомогою всього 4-х вибраних відкритих текстів та відповідних шифртекстів з досить низькою складністю. Криптоаналіз алгоритму продовжено у роботі.
У 2004 р. група фахівців з Кореї запропонувала атаку, за допомогою якої, використовуючи диференціальний криптоаналіз на зв'язаних ключах, можна отримати з ймовірністю 91,7% 12 біт секретного ключа. Для атаки потрібно 2 35 вибраних відкритих текстів та 2 36 операцій шифрування. Як видно, дана атака практично непотрібна для реального розкриття алгоритму.
Алгоритм, який визначається ГОСТ 28147-89, має довжину ключа шифрування 256 біт. Він шифрує інформацію блоками по 64 біт (такі алгоритми називаються блоковими), які потім розбиваються на два субблоки по 32 біти (N1 і N2) (рисунок 1). Субблок N1 обробляється певним чином, після чого його значення складається зі значенням субблока N2 (складання виконується за модулем 2, тобто застосовується логічна операція XOR - «виключає або»), а потім субблоки змінюються місцями. Дане перетворення виконується кілька разів («раундів»): 16 чи 32 залежно від режиму роботи алгоритму. У кожному раунді виконуються дві операції.
Малюнок 1. Схема алгоритму ГОСТ 28147-89.
Перша – накладення ключа. Вміст субблоку N1 складається за модулем 2 з 32-біт частиною ключа Kx. Повний ключшифрування представляється як конкатенації 32-біт підключів: K0, K1, K2, K3, K4, K5, K6, K7. У процесі шифрування використовується один із цих підключів - залежно від номера раунду та режиму роботи алгоритму.
Друга операція – таблична заміна. Після накладання ключа субблок N1 розбивається на 8 частин по 4 біти, значення кожної з яких замінюється відповідно до таблиці заміни для цієї частини субблоку. Потім виконується побітовий циклічний зсув субблоку вліво на 11 біт.
Табличні заміни (Substitution box - S-box) часто використовуються у сучасних алгоритмах шифрування, тому варто пояснити, як організується така операція. У таблицю записуються вихідні значення блоків. Блок даних певної розмірності (у разі - 4-бит) має своє числове уявлення, яке визначає номер вихідного значення. Наприклад, якщо S-box має вигляд 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1 і на вхід прийшов 4-біт блок «0100» (значення 4), то, згідно з таблицею, вихідне значення дорівнюватиме 15, тобто «1111» (0 а 4, 1 а 11, 2 а 2 ...).
Алгоритм, що визначається ГОСТ 28147-89, передбачає чотири режими роботи: простий заміни, гамування, гамування зі зворотним зв'язком та генерації імітоприставок. Вони використовують одне й те описане вище шифруюче перетворення, але, оскільки призначення режимів по-різному, здійснюється це перетворення у кожному їх по-різному.
У режимі простої заміни для зашифрування кожного 64-біт блоку інформації виконуються 32 описані вище раунди. При цьому 32-біт підключи використовуються в наступній послідовності:
K0, K1, K2, K3, K4, K5, K6, K7, K0, K1 і т.д. - у раундах з 1-го по 24-й;
K7, K6, K5, K4, K3, K2, K1, K0 - у раундах з 25-го до 32-го.
Розшифрування в даному режимі проводиться так само, але з дещо іншою послідовністю застосування підключень:
K0, K1, K2, K3, K4, K5, K6, K7 – у раундах з 1-го по 8-й;
K7, K6, K5, K4, K3, K2, K1, K0, K7, K6 тощо - у раундах з 9-го по 32-й.
Усі блоки шифруються незалежно друг від друга, т. е. результат зашифрування кожного блоку залежить від його вмісту (відповідного блоку вихідного тексту). За наявності кількох однакових блоків вихідного (відкритого) тексту відповідні їм блоки шифртексту також будуть однакові, що дає додаткову корисну інформаціюдля того, хто намагається розкрити шифр криптоаналітика. Тому даний режим застосовується в основному для шифрування самих ключів шифрування (дуже часто реалізуються багатоключові схеми, в яких з міркувань ключі шифруються один на одному). Для шифрування власне інформації призначено два інші режими роботи - гамування та гамування зі зворотним зв'язком.
У режимі гамування кожен блок відкритого тексту побітно складається по модулю 2 блоком гами шифру розміром 64 біт. Гамма шифру - це спеціальна послідовність, яка у результаті певних операцій із регістрами N1 і N2.
- 1. У регістри N1 і N2 записується їхнє початкове заповнення - 64-біт величина, звана синхропосилкою.
- 2. Виконується зашифрування вмісту регістрів N1 і N2 (в даному випадку - синхропосилання) в режимі простої заміни.
- 3. Вміст регістру N1 складається за модулем (232 - 1) з константою C1 = 224 + 216 + 28 + 24, а результат додавання записується в регістр N1.
- 4. Вміст регістру N2 складається за модулем 232 з константою C2 = 224 + 216 + 28 + 1, а результат додавання записується в регістр N2.
- 5. Вміст регістрів N1 і N2 подається на вихід як 64-біт блоку гами шифру (в даному випадку N1 і N2 утворюють перший блок гами).
Якщо потрібний наступний блок гами (тобто необхідно продовжити зашифрування або розшифрування), виконується повернення до операції 2.
Для розшифрування гамма виробляється аналогічним чином, а потім до біт зашифрованого тексту та гами знову застосовується операція XOR. Оскільки ця операція оборотна, у разі правильно виробленої гами виходить вихідний текст (таблиця 1).
Таблиця 1.Зашифрування та розшифрування в режимі гамування
Для вироблення потрібної для розшифровки гами шифру у користувача, що розшифровує криптограму, повинен бути той самий ключ і те саме значення синхропосилання, які застосовувалися при зашифруванні інформації. В іншому випадку отримати вихідний текст із зашифрованого не вдасться.
У більшості реалізацій алгоритму ГОСТ 28147-89 синхропосилання не секретна, проте є системи, де синхропосилання - такий же секретний елемент, як і ключ шифрування. Для таких систем ефективна довжина ключа алгоритму (256 біт) збільшується ще на 64 біт секретної синхропосилання, яку також можна розглядати як ключовий елемент.
У режимі гамування із зворотним зв'язком для заповнення регістрів N1 і N2, починаючи з 2-го блоку, використовується не попередній блок гами, а результат зашифрування попереднього блоку відкритого тексту (рисунок 2). Перший блок у цьому режимі генерується повністю аналогічно попередньому.
Рисунок 2. Вироблення гами шифру як гамування зі зворотним зв'язком.
Розглядаючи режим генерації імітаторів, слід визначити поняття предмета генерації. Імітоприставка - це криптографічна контрольна сума, що обчислюється з використанням ключа шифрування та призначена для перевірки цілісності повідомлень. При генерації імітоприставки виконуються такі операції: перший 64-біт блок масиву інформації, для якого обчислюється імітоприставка, записується в регістри N1 і N2 і зашифровується в скороченому режимі простої заміни (виконуються перші 16 з 32 раундів). Отриманий результат підсумовується по модулю 2 з наступним блоком інформації зі збереженням результату N1 і N2.
Цикл повторюється до блоку інформації. В результаті цих перетворень 64-біт вміст регістрів N1 і N2 або його частина і називається імітоприставкою. Розмір імітоприставки вибирається, виходячи з необхідної достовірності повідомлень: при довжині імітоприставки r біт ймовірність, що зміна повідомлення залишиться непоміченим, дорівнює 2-r. Найчастіше використовується 32-біт імітоприставка, тобто половина вмісту регістрів. Цього достатньо, оскільки, як і будь-яка контрольна сума, імітоприставка призначена насамперед для захисту від випадкових спотворень інформації. Для захисту ж від навмисної модифікації даних застосовуються інші криптографічні методи- насамперед електронний цифровий підпис.
При обміні інформацією імітоприставка є свого роду додатковим засобом контролю. Вона обчислюється для відкритого тексту при зашифруванні будь-якої інформації та надсилається разом із шифртекстом. Після розшифрування обчислюється нове значення імітоприставки, яке порівнюється із надісланою. Якщо значення не збігаються - значить, шифртекст був спотворений під час передачі або під час розшифрування використовувалися неправильні ключі. Особливо корисна імітоприставка для перевірки правильності розшифрування ключової інформації під час використання багатоключових схем.
Алгоритм ДЕРЖСТАНДАРТ 28147-89 вважається дуже сильним алгоритмом - в даний час для його розкриття не запропоновано більш ефективних методів, ніж згаданий вище метод «грубою сили». Його висока стійкість досягається насамперед за рахунок великої довжини ключа – 256 біт. При використанні секретної синхропосилання ефективна довжина ключа збільшується до 320 біт, а засекречування таблиці замін додає додаткові біти. Крім того, криптостійкість залежить від кількості раундів перетворень, яких за ГОСТ 28147-89 має бути 32 (повний ефект розсіювання вхідних даних досягається після 8 раундів).
Достоїнствами ГОСТ 28147-89 є наявність захисту від нав'язування хибних даних (вироблення імітівставки) та однаковий цикл шифрування у всіх чотирьох алгоритмах ГОСТ.
Алгоритм шифрування ГОСТ 28147-89. Метод простої заміни. - Архів WASM.RU
«Поки ти живий, не вмирай, на цей світ поглянь.
У багатьох душа мертва – вони мертві всередині.
Але ходять і сміються, не знаючи, що їх немає,
Не квапи свою смертну годину» – вона сказала мені.Арія, «Там високо»
2.1 Мережі Файстеля.
2.2 Блоковий шифр ГОСТ 28147-893.1 Ключова інформація
3.2 Основний крок криптоперетворення3.3 Базові цикли:“ 32-З” , “ 32-Р” .
4.1 Реалізація основного кроку криптоперетворення
4.2 Збільшення швидкодії алгоритму
5. Вимоги до ключової інформації
6. Список використаної літератури
7. Подяки.Вступ.
Даний документ є моєю спробою описати метод простої заміни алгоритму шифрування ГОСТ 28147-89 найпростішою, проте технічно-грамотною мовою. Про те, наскільки це в мене вийшло, читач скаже свою думку після того, як прочитає перші шість пунктів.
Для того, щоб моя праця дала більше користірекомендую озброїтися працями авторів, зазначених у списку використаної літератури. Рекомендується також калькулятор, щоб у ньому були функції з розрахунку операції XOR, т.к. Прочитання статті передбачає, що читач має намір вивчити цей алгоритм шифрування. Хоча як довідковий посібник вона теж підійде, але я писав цю статтю саме як навчальну.
Попередні відомості про блокові шифри.
Перш ніж ми почнемо розглядати алгоритм, нам необхідно ознайомитися з історією створення таких шифрів. Алгоритм відноситься до розряду блокових шифрів, в архітектурі яких інформація розбивається на кінцеву кількість блоків, кінцевий, природно, може бути не повним. Процес шифрування відбувається саме над повними блоками, які утворюють шифрограму. Кінцевий блок, якщо він неповний доповнюється чимось (про нюанси за його доповненням я скажу нижче) і шифрується так само, як і повні блоки. Під шифрограмою я розумію, що результат дії функції шифрування над деякою кількістю даних, які користувач подав для шифрування. Тобто шифрограма - це кінцевий результат шифрування.
Історія розвитку блокових шифрів асоціюється з початком 70х років, коли компанія IBM усвідомивши необхідність захисту інформації при передачі даних каналами зв'язку ЕОМ, приступила до виконання власної програминаукових досліджень, присвячених захисту інформації в електронних мережах, у тому числі криптографії.
Групу дослідників – розробників фірми IBM, яка приступила до дослідження систем шифрування із симетричною схемою використання ключів, очолив лікар Хорст Файстель.
2.1 Мережі Файстеля
Запропонована Файстелем архітектура нового методу шифрування в класичній літературі отримала назву «Архітектура Файстеля», але на Наразіу російській та зарубіжній літературі використовується більш усталений термін - "мережа Файстеля" або Feistel `s NetWork. Згодом по цій архітектурі було побудовано шифр «Люцифер» - який був опублікований і викликав нову хвилю інтересу до криптографії загалом.
Ідея архітектури "мережі Файстеля" полягає в наступному: вхідний потік інформації розбивається на блоки розміром n бітів, де n парне число. Кожен блок ділиться на частини – L і R, далі ці частини подаються в ітеративний блоковий шифр, у якому результат j-го етапу визначається результатом попереднього етапу j-1! Сказане можна проілюструвати з прикладу:
Мал. 1
Де, функція А – це основна дія блокового шифру. Може бути простою дією, таким як операція XOR, а може мати більш складний вигляд бути послідовністю ряду простих дій - додавання по модулю, зсув вліво, заміна елементів і т.д., в сукупності ці прості діїутворюють так званий – основний крок криптоперетворення.
Слід зазначити, що ключовими елементами роботи функції є подача елементів ключів та операція XOR і тому наскільки добре продумані робота цих операцій, говорить про криптостойкости шифру загалом.
Щоб ідея мереж Файстеля була остаточна зрозуміла, розглянемо найпростіший випадок зображений на Мал. 1, де функції А – виступить операції “mod 2” (“xor”), але ці найпростішийвипадок, у більш серйозній ситуації, наприклад приховування інформації державної важливості, функція А може бути більш складною (скільки я бачив функція А дійсно буває дуже складною):
Вихідні дані:
L = 1110b, R = 0101, K = 1111b
Отримати шифрограму
1. (R + K) mod 2 4 = Smod, Smod = 0100b
2. (Smod + L) mod 2 = Sxor, Sxor = 1010b
3. L = R, R = Sxor
L = 0101b, R = 1010b
Пояснимо наші дії:
1. Ця операція складає mod 2 4 . На практиці така операція зводиться до простого додавання, де ми повинні скласти два числа і проігнорувати перенесення в 5-й розряд. Оскільки, якщо проставити над розрядами двійкового уявлення числа проставити показники ступеня, над п'ятим розрядом буде показник чотири, поглянемо на малюнок нижче, де зображені дії нашої операції:
Мал. 2
Тут я стрілкою вказав на показники ступеня, очевидно, результат повинен був вийти 10100, але так як при операції mod 2 4 ігнорується перенесення, ми отримуємо 0100.
2. Ця операція в літературі називається mod 2, мовою асемблера реалізується командою XOR. Але її правильніша назва mod 2 1 . Без цієї унікальної операції навряд чи можна побудувати швидкий алгоритм шифрування, що легко реалізується, і при цьому, щоб він був ще досить криптостійким. Унікальність цієї операції полягає в тому, що вона собі зворотна! Наприклад, якщо число А по XORити з числом Б, в результаті отримаємо, надалі достатньо переXORити числа Б і В між собою, щоб отримати колишнє значення А!
У цій операції ми отримали 1010 маючи числа 1110 і 0100, щоб отримати назад 1110, достатньо переXORрити між собою числа 0100 і 1010! Докладніше про цю операцію можна почитати у статті, яка вкладена на сайті www.wasm.ru, « Елементарний посібник зCRC_алгоритмам виявлення помилок» автор, якої Ross N. Williams. У цій праці є пункт - 5. Двійкова арифметика без урахування переносів». Ось саме в цій статті описана операція xor!Я вигукую тому, що в цій статті ця операція так розписана, що читач не просто розуміє як працює ця операція, він навіть починає її бачити, чути та відчувати!
3. Ця дія необхідна, щоб при розшифровуванні із шифрограми можна було отримати вихідні значення.
2.2 Блоковий шифр ГОСТ 28147-89
Алгоритм шифрування ГОСТ 28147 - 89 відноситься до розряду блокових шифрів працюючих по архітектурі збалансованих мереж Файстеля, де частини обраного блоку інформації мають рівний розмір. Алгоритм був розроблений у надрах восьмого відділу КДБ перетвореного нині у ФАПСІ і був закріплений як стандарт шифрування Російської Федерації ще 1989 року за СРСР.
Для роботи даного методуалгоритму необхідно розбити інформацію на блоки розміром 64 біти. Згенерувати або ввести в систему шифрування наступну ключову інформацію: ключ і таблицю замін. До вибору ключа та таблиці замін при шифруванні слід поставитися дуже серйозно, т.к. саме це є фундамент безпеки вашої інформації. Про те, які вимоги накладаються на ключ, та таблицю замін дивись пункт «Вимоги до ключової інформації».
При розгляді способу ми не загострюватимемо цьому уваги, т.к. ця стаття, як я вже говорив вище, написана з метою навчити читача, шифрувати дані за методом простої заміни даного алгоритмушифрування, але ми обов'язково торкнемося цього питання наприкінці статті.
Теоретичний мінімум.
3.1 Ключова інформація
Як я вже говорив вище, у шифруванні даних активну участь беруть:
3.1.1. Ключ – це послідовність восьми елементів розміром 32 біти кожен. Далі будемо позначати символом До, а елементи з яких він складається – k1, k2, k3, k4, k5, k6, k7, k8.
3.1.2 Таблиця замін – матриця з восьми рядків та шістнадцяти стовпців, надалі – Hij. Кожен елемент на перетині рядка i та стовпця j займає 4 біти.
3.2 Основний крок криптоперетворення
Основною дією в процесі шифрування є основний крок криптоперетворення. Це ніщо інше, як дія з шифрування даних за певним алгоритмом, тільки назву розробники ввели аж надто громіздке.
Перш ніж почати шифрувати блок розбивають на дві частини L і R, по 32 біта кожна. Вибирають елемент ключа і потім подають ці дві частини блоку, елемент ключа таблицю замін у функцію основного кроку, результат основного кроку це одна ітерація базового циклу, про який йтиметься в наступному пункті. Основний крок складається з наступних дій:
- Додавання частина блоку R підсумовується з елементом ключа K по mod 2 32 . Про таку операцію я описав вище, тут теж тільки показник ступеня не «4», а «32» - результат цієї операції надалі позначатиму Smod.
- Отриманий раніше результат Smod ділимо на чотири бітові елементи s7, s6, s5, s4, s3, s2, s1, s0 і подаємо у функцію заміни. Заміна відбувається наступним чином: вибирається елемент Smod - s i , спочатку починаємо з молодшого елемента, і замінюємо значенням з таблиці замін по i - тому рядку і стовпцю, на який вказує значення елемента s i . Переходимо до si +1 елементу і чинимо аналогічним чином і продовжуємо так, поки не замінимо значення останнього елемента Smod – результат цієї операції будемо позначати як Ssimple.
- У цій операції значення Ssimple зрушуємо циклічно вліво на 11 біт і отримуємо Srol.
- Вибираємо другу частину блоку L і складаємо по mod 2 з Srol, у результаті маємо Sxor.
- На цій стадії частина блоку L дорівнюватиме значенню частини R, а частина R у свою чергу ініціалізується результатом Sxor і на цьому функція основного кроку завершена!
3.3 Базові цикли: "32-З", "32-Р".
Для того щоб зашифрувати інформацію треба розбити її на блоки розміром 64 біти, природно останній блок може бути менше 64 бітів. Цей факт є ахіллесовою п'ятою цього методу «проста заміна». Так як його доповнення до 64 біт є дуже важливим завданням щодо збільшення криптостійкості шифрограми і до цього чутливого місця, якщо воно присутнє в масиві інформації, а його може і не бути (наприклад, файл розміром 512 байт!), слід поставитися з великою відповідальністю!
Після того, як ви розбили інформацію на блоки, слід розбити ключ на елементи:
K = k1, k2, k3, k4, k5, k6, k7, k8
Саме шифрування полягає у використанні, так званих базових циклів. Які у свою чергу включають n – кількість основних кроків криптоперетворення.
Базові цикли мають маркування: n – m. Де n – кількість основних кроків криптоперетворення у базовому циклі, а m – це «тип» базового циклу, тобто. про що йдеться, про «З» ашифрування або «Р» асшифрування даних.
Базовий цикл шифрування 32-З складається з 32 основних кроків криптоперетворення. У функцію реалізуючу дії кроку подають блок N і елемент ключа До, перший крок відбувається з к1, другий над отриманим результатом з елементом к2 і т.д. за наступною схемою:
k1,k2,k3,k4,k5,k6,k7,k8,k1,k2,k3,k4,k5,k6,k7,k8,k1,k2,k3,k4,k5,k6,k7,k8k8,k7, k6,k5,k4,k3,k2,k1
Процес розшифровування 32-Р відбувається аналогічним чином, але елементи ключа подаються у зворотній послідовності:
k1,k2,k3,k4,k5,k6,k7,k8,k8,k7,k6,k5,k4,k3,k2,k1,k8,k7,k6,k5,k4,k3,k2,k1,k8, k7,k6,k5,k4,k3,k2,k1
практика.
4.1 Реалізація основного кроку криптоперетворення
Після того як ми познайомилися з теорією про те, як шифрувати інформацію настав подивитися, як відбувається шифрування на практиці.
Вихідні дані:
Візьмемо блок інформації N = 0102030405060708h, тут частини L і R дорівнюють:
L = 01020304h, R = 05060708h, візьмемо ключ:
K = ' as28 zw37 q839 7342ui23 8e2t wqm2 ewp1’ (це ASCII – коди, для того, щоб подивитися шістнадцяткову виставу, можна відкрити цей файл у режим перегляду в Total Commanderнатиснувши клавішу « F3» і далі клавішу « 3 »). У цьому ключі значення елементів будуть:
k1 = 'as28', k2 = 'zw37', k3 = 'q839', k4 = '7342'
k5 = 'ui23', k6 = '8e2t', k7 = 'wqm2', k8 = 'ewp1'
Також візьмемо наступну таблицю замін:
Мал. 3
Тут рядки нумеруються від 0 до 7, стовпці від 0 до F.
Попередження:Вся інформація, в тому числі і ключ з таблицею замін, взята як приклад для розгляду алгоритму!
Використовуючи Вихідні дані, необхідно отримати результат дії основного кроку криптоперетворення.
1. Вибираємо частину R = 05060708h і елемент ключа k1 = 'as28', у шістнадцятковому вигляді елемент ключа виглядатиме так: 61733238h. Тепер же робимо операцію підсумовування за mod 2 32:
Мал. 4
Як видно на малюнку, у нас не відбулося перенесення в 33 біт позначений червоним кольором і з показником ступеня. 32 ». А якби в нас були інші значення R і елемента ключа – це цілком могло б статися, і тоді б ми його проігнорували, і надалі використовували тільки біти, помічені жовтим кольором.
Таку операцію я виконую командою асемблера add:
; eax = R, ebx = 'as28'
Результат цієї операції Smod = 66793940h
2. Тепер сама хитромудра операція, але якщо придивитися по уважніше, то вона вже не така страшна, як здається спочатку. Представимо Smod у такому вигляді:
Мал. 5
Я постарався наочно уявити елементи Smod на малюнку, але все одно поясню:
s0 = 0, s1 = 4, s2 = 9 і т.д.
Тепер, починаючи з молодшого елемента s0, виконуємо заміну. Згадуючи пункт « 3.2 Основний крок криптоперетворення» i – рядок, s i – стовпець, шукаємо в нульовому рядку та нульовому стовпці значення:
Рис.6
Таким чином, поточне значення Smod, не 6679394 0 h, а 6679394 5 h.
Починаємо замінювати s1, тобто. четвірку. Використовуючи перший рядок та четвертий стовпець (s1 = 4!). Дивимося на малюнок:
Мал. 7
Тепер значення Smod, не 667939 4 5h, 667939 2 5h. Я припускаю, що тепер алгоритм заміни читачеві зрозумілий, і я можу сказати, що після кінцевого результату Ssimple матиме наступне значення – 11e10325h.
Про те, як це найпростіше реалізувати у вигляді команд асемблера, я розповім пізніше в наступному пункті, після того, як розповім про розширену таблицю.
- Отримане значення Ssimple ми маємо зрушити на 11 біт вліво.
Мал. 8
Як видно, ця дія досить проста, і реалізується однією командою мови асемблера – rolта результат цієї операції Srol дорівнює 0819288Fh.
4. Тепер залишається частина L нашого блоку інформації по XORити зі значенням Srol. Я беру калькулятор з w2k sp4 і отримую Sxor = 091b2b8bh.
5. Це дія підсумкова і ми просто присвоюємо, чисти R значення частини L, а частину L ініціалізуємо значенням Sxor.
Кінцевий результат:
L = 091b2b8bh, R = 01020304h
4.2 Збільшення швидкодії алгоритму
Тепер поговоримо про оптимізацію алгоритму за швидкістю. У процесі реалізації, будь-якого проекту, доводиться враховувати, що програма, що з регістрами частіше, ніж із пам'яттю працює якнайшвидше і це судження теж дуже важливо, т.к. над одним блоком інформації цілих 32 дії шифрації!
Коли я реалізовував алгоритм шифрування у своїй програмі, я вчинив так:
1. Вибрав частину блоку L в регістр eax, а R - edx.
2. Регістр esi ініціалізував адресою розширеного ключа, про це нижче.
3. У регістр ebx надавав значення адреси розширеної таблиці замін, про це теж нижче
4. Передавав інформацію пунктів 1,2, 3 у функцію базового циклу 32 – З чи 32 – Р залежно від ситуації.
Якщо подивитися на схему подачі елементів ключа у пункті « Базові цикли: "32-З", "32-Р"», то наш ключ для базового циклу 32 - З можна представити наступним чином:
До 32-З =
'as28', 'zw37', 'q839', '7342', 'ui23', '8e2t', 'wqm2', 'ewp1',
'as28', 'zw37', 'q839', '7342', 'ui23', '8e2t', 'wqm2', 'ewp1',
'ewp1', 'wqm2', '8e2t', 'ui23', '7342', 'q839', 'zw37', 'as28'
Тобто. з початку йдуть k1,k2,k3,k4,k5,k6,k7,k8 - ‘ as28’, ‘zw37’, ‘q839', '7342', 'ui23’, ‘8e2t’, ‘wqm2’, ‘ewp1’тричі ця послідовність повторюється. Потім елементи йдуть у зворотному порядку, тобто: k8, k7, k6, k5, k4, k3, k2, k1 - 'ewp1', 'wqm2', '8e2t', 'ui23', '7342', 'q839', 'zw37', 'as28'.
Я заздалегідь розташував у масиві елементи в тому порядку, як вони повинні подаватися в 32 - З. Тим самим я збільшив пам'ять, необхідну під ключ, але позбавив себе деяких процесів мислення, які мені були не потрібні, і збільшив швидкість роботи алгоритму, рахунок зменшення часу звернення до пам'яті! Тут я описав тільки ключ для 32 - З, для циклу 32 - Р я надійшов аналогічно, але використовуючи іншу схему подачі елементів, яку я теж описував у пункті « Базові цикли: "32-З", "32-Р».
Настав час описати реалізацію роботи функції замін, як я обіцяв вище. Не міг описати раніше, т.к. це потребує введення нового поняття – розширена таблиця замін. Я не зможу пояснити, що це таке. Натомість я вам покажу її, а ви вже самі сформулюйте для себе, що ж це таке – розширена таблиця замін?
Отже, щоб розібратися, що таке розширена таблиця замін нам знадобиться таблиця замін, наприклад візьму ту, що зображено на рис. 3.
Наприклад, нам потрібно було замінити число 66793940h. Подаю його в наступному вигляді:
Мал. 9
Тепер, якщо взяти елементи s1,s0, тобто. молодший байт, то результат функції заміни дорівнюватиме 25h! Почитавши статтю Андрія Винокурова, яку я навів у пункті « Список використаної літератури», ви дійсно виявите, що якщо взяти два рядки можна отримати масив, що дозволяє швидко знаходити елементи заміни за допомогою команди асемблера xlat.Кажуть можна й іншим способом швидше, але Андрій Винокуров витратив на дослідження швидких алгоритмів для реалізації ГОСТу близько чотирьох років! Думаю, не варто винаходити велосипеда, коли він вже є.
Отже, про масив:
Візьмемо два перші рядки нульову та першу, створимо масив на 256 байт. Тепер спостерігаємо одну особливість, якщо треба перетворити 00h, то результат буде 75h (спираємося на рис.3) – кладемо це значення масив на зміщення 00h. Беремо значення 01h, результат функції замін 79h, кладемо його в масив на зсув 01 і так далі до 0FFh, яке нам дасть 0FCh, яке ми покладемо в масив зі зміщення 0FFh. Ось ми і отримали розширену таблицю замін для першої групи рядків: першої та нульової. Але ще є три групи: друга стор.2, стор.3, третя стор.4, стор. 5, четверта стор.6, стор.7. З цими трьома групами чинимо тим самим способом, що і з першою. Результат – розширена таблиця замін!
Тепер можна реалізувати алгоритм, який проводитиме заміну. Для цього беремо вихідні коди, які виклав Андрій Винокуров на своїй сторінці, дивись « Список використаної літератури».
lea ebx,extented_table_simple
mov eax,[покласти число, яке потрібно замінити]
add ebx,100h ;перехід до двох наступних вузлів
sub ebx,300h; щоб надалі ebx показував на таблицю
Тепер ще одна особливість, попередніми діями ми не лише замінили, а й зрушили число на 8 біт ліворуч! Нам залишається тільки зрушити число ще на 3 біти вліво:
і ми отримуємо результат операції rol eax,11!
Більше я нічого не можу додати по оптимізації, єдине, що можу наголосити на тому, що я говорив вище – використовуйте регістри частіше, ніж звернення до пам'яті. Думаю ці слова лише для новачків, досвідчені і без моїх слів це чудово розуміють.
Вимоги до ключової інформації.
Як сказано у статті Андрія Винокурова, ключ обирають за двома критеріями:
Критерій рівноймовірного розподілу бітів між значеннями 1 і 0. Зазвичай як критерій рівноймовірного розподілу бітів виступає критерій Пірсона («хі-квадрат»).
Це означає ключем, в принципі, може будь-яке число. Тобто, при формуванні чергового біта ключа ймовірність його ініціалізації одиницею або нулем 50/50!
Прошу помітити, що ключ із восьми елементів, кожен по 32 біти, таким чином всього в ключі 32*8 = 256 бітів і кількість можливих ключів 2 256 ! Тебе це не вражає?
Критерій серії.
Якщо ми подивимося на наш ключ, який я навів у пункті « 4.1 Реалізація основного кроку криптоперетворення», то ви помітите, що справедливий наступний запис:
Мал. 10
Однією фразою значення k 1 повинно повторитися над k 2 , над якомусь іншому елементі ключа.
Тобто ключ, який ми вибрали як розгляд алгоритму шифрування, цілком відповідає двом наведеним вище критеріям.
Тепер про вибір таблиці замін:
Тепер поговоримо про те, як правильно вибрати таблицю замін. Основна вимога до вибору таблиць замін - це явище «неповторюваності» елементів, кожен з яких розміром 4 біти. Як ви вже бачили вище, кожен рядок таблиці замін складається із значень 0h, 1h, 2h, 3h, …, 0fh. Так ось основна вимога говорить про те, що в кожному рядку є значення 0h, 1h, 2h, ..., 0fh і кожне таке значення в одному примірнику. Наприклад, послідовність:
1 2 3 4 5 6 7 8 9 A B C D E F
Цілком відповідає цій вимогі, але все ж таки! Таку послідовність як рядок вибирати не рекомендується. Так як якщо ви подасте значення на вхід функції, яка спирається на такий рядок, то на виході ви отримаєте таке значення! Не вірите? Тоді візьміть число 332DA43Fh і вісім таких рядків, як таблиця замін. Проведіть операцію заміни, та запевняю вас, на виході ви отримаєте число 332DA43Fh! Тобто таке саме, що ви подали на вхід операції! А це не є ознакою гарного тону при шифруванні, та й чи було?
Це була одна вимога, наступний критерій говорить про те, що кожен біт вихідного блоку повинен бути статистично незалежний від кожного біта вхідного блоку!
Як це виглядає простіше? А ось як, наприклад, ми вибрали із наведеного вище числа елемент s0 = 0Fh, 01111b. Імовірність того, що ми зараз замінимо перший біт одиницею або нулем дорівнює 0,5! Імовірність заміни другого, третього і четвертого біта, кожен біт, розглядаємо окремо, одиницями або нулями теж дорівнює 0, 5. При виборі s1 = 0Eh, ймовірність того, що ми нульовий біт, а це «0», замінимо нулем або одиницею теж дорівнює – 0,5! Таким чином, згідно з цим критерієм між заміною нульових бітів елементів s0, s1 немає жодної закономірності! Так, ви могли замінити одиницями, але ви також могли поставити та нулі.
Для оцінки таблиці за цим критерієм можна побудувати таблицю коефіцієнтів кореляції, розраховані за такою формулою:
Якщо p = 1, то значення біта j на виході дорівнює значенню біта i на вході за будь-яких комбінаціях біт на вході;
Якщо p = -1 то значення біта j на виході завжди є інверсією вхідного біта i;
Якщо p = 0, вихідний біт j з рівною ймовірністю приймає значення 0 і 1 при будь-якому фіксованому значенні вхідного біта i.
Візьмемо приклад одного рядка:
Розкладемо на «складові»:
Розрахуємо один коефіцієнт за наведеною вище формулою. Щоб простіше було зрозуміти, як це робиться, поясню докладніше:
Беремо 0-й біт 0-ого числа (0) на вході та 0-й біт 0-ого числа на виході (1) проводимо операцію 0 XOR 1 = 1.
Беремо 0-й біт 1-го числа (1) на вході та 0-й біт 1-ого числа на виході (1) проводимо операцію 1 XOR 1 = 0.
Беремо 0-й біт 2-го числа (0) на вході та 0-й біт 2-го числа на виході (0) проводимо операцію 0 XOR 0 = 0.
Беремо 0-й біт 3-го числа (1) на вході та 0-й біт 3-го числа на виході (1) проводимо операцію 1 XOR 1 = 0.
Провівши послідовно операції XOR у такій послідовності, підраховуємо кількість усіх ненульових значень, отримуємо значення 6. Звідси P 00 = 1-(6/2 4-1) = 0,25. Отже, з'ясувалося, що значення біта 0 на виході дорівнює значенню біта 0 на вході в 4 випадках з 16-ти;
Підсумкова таблиця коефіцієнтів:
Як видно з таблиці кореляційних коефіцієнтів біт 3 на вході інвертовано щодо біта 0 на виході в 14 випадках з 16, що становить 87.5%. Ось це вже не допустимо для нормальних систем шифрування. Для різноманітності візьмемо ще приклад:
Таблиця коефіцієнтів буде наступна (кому не ліниво може перерахувати)
Ну, в цій таблиці справи ще гірші - біти 1 і 2 групи залишаються незмінними! Криптоаналітику є, де розвернутися З урахуванням усіх цих вимог простим перебором («в лоб») було знайдено таблиці перестановки відповідні зазначеній теорії (на сьогодні – 1276 поєднань) Ось деякі з них:
09 0D 03 0E-06 02 05 08-0A 07 00 04-0C 01 0F 0B
00 05 0A 07-03 08 0F 0C-0E 0B 04 09-0D 06 01 02
06 0B 0F 00-0C 01 02 0D-08 07 09 04-05 0A 03 0E
04 0E 00 09-0B 01 0F 06-03 0D 07 0A-0C 02 08 05
04 02 08 0E-05 0F 03 09-0B 01 0D 07-0A 0C 06 00
07 03 09 0C-08 00 06 0F-0E 04 01 0A-0D 0B 02 05
06 0F 03 08-0D 04 0A 01-09 02 05 0C-00 0B 0E 07
0C 06 08 01-03 09 07 0E-0B 05 0F 02-04 0A 00 0D
04 0B 09 06-0E 01 00 0F-0A 05 03 0C-0D 02 07 08
00 0E 0F 01-07 08 09 06-04 0B 0A 05-03 0D 0C 02
0F 09 01 07-04 0A 08 06-0E 00 02 0C-05 03 0B 0D
0A 03 04 01-05 0C 0B 0E-08 06 0F 0D-07 09 00 02
0B 06 0F 01-04 0A 08 05-00 0D 0C 02-07 09 03 0E
0C 03 02 08-0D 06 0B 05-07 09 04 0F-0A 00 01 0E
02 0B 0F 04-09 00 06 0D-05 0E 01 08-0C 07 0A 03
Список використаної литературы.
- Стаття Андрія Винокурова:
Алгоритм шифрування ГОСТ 28147-89, його використання та реалізація
для комп'ютерів платформи Intel x86.
Тут і вихідні коди, з реалізації алгоритму шифрування.
- Стаття Хорста Файстеля:
Криптографія та комп'ютерна безпека.
(можна знайти за тією ж адресою, що і попередню статтю)
- Ross N. Williams:
Елементарний посібник з CRC алгоритмів виявлення помилок
Викладено на сайті www.wasm.ru.
Подяки.
Хотілося б висловити подяку всім відвідувачам форуму www.wasm.ru. Але особливо хотілося б подякувати ChS, який зараз відомий, як SteelRat, він допоміг мені зрозуміти такі речі, чого я б, напевно, ніколи б не зрозумів, а також допомогу при написанні пункту: « Вимоги до ключової інформації», основна частина цього пункту була написана ним. Також глибоко вдячний співробітнику КДТУ ім. О.М. Туполєва Анікіну Ігореві В'ячеславовичу і гріх було б не відзначити Кріса Касперскі, за те, що він є і Volodya/wasm.ru за його настанови. Ох, і дістається мені від нього. Також хочу відзначити Sega-Zero / Callipso зате, що доніс до мого розуму деякі математичні нетрі.
Це, мабуть, усе, що я хотів би сказати вам.
Буду вдячний за критику чи питання, пов'язані з цією статтею чи просто поради. Мої контактні дані: [email protected], ICQ - 337310594.
З повагою: Evil`s Interrupt.
PS: Цією статтею я не намагався когось перевершити. Вона була написана з наміром, полегшити вивчення ГОСТу і якщо у вас вийшли труднощі, то це не означає, що я винен у цьому. Будь розумними, і наберіться терпіння, всього вам доброго!
Завантаження...