Збочення з імпортозаміщенням. Працюємо з алгоритмом блокового шифрування «Коник» з ГОСТ 34.12-2015

1. Зміст статті Дивись, як цікаво виходить: вже майже три роки надходження вільного хакера на государеву...
2. WARNING
3. INFO
4. трохи теорії
5. Базові функції стандарту
6. Додавання двох довічних векторів по модулю 2
7. Нелінійне биективное перетворення (перетворення S)
8. Зворотне нелінійне биективное перетворення (зворотне перетворення S)
9. Лінійне перетворення (перетворення L)
10. Зворотне лінійне перетворення (зворотне перетворення L)
11. Продовження доступно тільки учасникам
12. Варіант 2. Відкрий один матеріал

Зміст статті

Дивись, як цікаво виходить: вже майже три роки надходження вільного хакера на государеву службу не вважається в очах колег по IT-ремеслу зашкваром. Те, що раніше здавалося принаймні дивним, зараз абсолютно нормально і виглядає до певної міри патріотично - на плечах і за спинами наших з тобою колег виразно проглядаються погони, червоні папки, колючий дріт та інші символи державності. Загалом, якщо слова «імпортозаміщення» і «цифровий суверенітет» не викликають у тебе легкого троллфейса, а ГОСТ ти вважаєш хорошим криптографічним алгоритмом (що, до речі, правда), то ця стаття тобі підійде точно.

Чотири слона вітчизняної криптографії

В даний час вітчизняна криптографія базується на кількох основних державних стандартах:

• ГОСТ 34.10. Інформаційна технологія. Криптографічний захист інформації. Процеси формування та перевірки електронного цифрового підпису (діюча на сьогодні редакція 2012 року);
• ГОСТ 34.11. Інформаційна технологія. Криптографічний захист інформації. Функція хешування (діюча на сьогодні редакція 2012 року);
• ГОСТ 34.12. Інформаційна технологія. Криптографічний захист інформації. Блокові шифри (діюча на сьогодні редакція 2015 року);
• ГОСТ 34.13. Інформаційна технологія. Криптографічний захист інформації. Режими роботи блокових шифрів (діюча на сьогодні редакція 2015 року).

Основні вітчизняні криптографічні ГОСТи

З ГОСТ 34.11-2012 ми вже познайомилися в минулій статті циклу. Це, якщо пам'ятаєш, був алгоритм обчислення хеш-суми під назвою «Стрибог». Сьогодні ми продовжимо розглядати вітчизняну криптографію, і на черзі у нас алгоритм блочного шифрування під назвою «Коник», який описаний в ГОСТ 34.12-2015.

Як і належить, даний ГОСТ розроблений в наукових надрах російських спецслужб і близько до них стоять організацій, а якщо говорити конкретніше, то це Центр захисту інформації та спеціального зв'язку ФСБ Росії і відкрите акціонерне товариство «Інформаційні технології та комунікаційні системи». Документ набув чинності з 1 січня 2016 року, і всі засоби шифрування, офіційно використовуються в різних структурах, які працюють з інформацією обмеженого доступу (держтаємниця, службова таємниця та інше), повинні йому відповідати.

У стандарті описуються два різновиди блочного шифру: «Коник» з довжиною блоку 128 біт і «Магма» з довжиною блоку 64 біта.

Алгоритм «Коник» більш сучасний і теоретично більш стійкий, ніж алгоритм «Магма» (який, по суті, практично без змін був узятий з старого ГОСТ 28147-89), і тому сьогодні ми розглянемо саме його. Що стосується «Магми», то про нього - як-небудь іншим разом в наступній статті циклу.

Як вже було сказано, довжина шифруемого блоку в алгоритмі «Коник» - 128 біт. Довжина ключа шифрування - 256 біт.

WARNING

При читанні ГОСТу врахуй, що в усіх 16-байтових масивах тестових послідовностей нульовий байт знаходиться в кінці масиву, а п'ятнадцятий, відповідно, на початку (якщо ти уважно читав статтю про «Стрибог», то ця особливість наших криптостандарта тобі повинна бути знайома).

INFO

Одна з головних легенд російської криптографії говорить, що назва алгоритму «Коник» ніякого відношення до зеленого комасі не має, а є скорочення від прізвищ творців алгоритму - Кузнєцова і Нечаєва. Швидше за все, це дійсно так, хоча ніде офіційного підтвердження цьому я знайти не зміг.

трохи теорії

Основу алгоритму становить не мережу Фейстеля, як в більшості блокових шифрів, а так звана SP - Substitution-Permutation network, або, по-російськи, підстановлювальний-перестановочность мережу. Шифр на основі SP-мережі отримує на вхід блок і ключ і робить кілька чергуються раундів, що складаються з стадій підстановки і стадій перестановки. У «коник» кожен раунд включає в себе лінійне і нелінійне перетворення плюс операцію накладення так званого итерационного ключа. Всього таких раундів дев'ять і один останній неповний раунд, в якому виконується тільки накладення останнього (десятого) итерационного ключа.

Схема роботи алгоритму при зашифрованими і при розшифрування

Ітераційні (або раундові) ключі виходять шляхом певних перетворень на основі майстер-ключа, довжина якого, як ми вже знаємо, становить 256 біт. Цей процес починається з розбиття майстер-ключа навпіл, так виходить перша пара раундовий ключів. Для генерації кожної наступної пари раундовий ключів застосовується вісім ітерацій мережі Фейстеля, в кожній ітерації використовується константа, яка обчислюється шляхом застосування лінійного перетворення алгоритму до значення номера ітерації.

Схема отримання ітераційних (раундовий) ключів

Отже, після короткого і невеликого занурення в теорію починаємо кодіть ...

Базові функції стандарту

Оскільки в алгоритмі використовуються 128-бітові блоки (у вигляді так званих довічних векторів), для початку визначимо цей самий блок:

#define BLOCK_SIZE 16 // Розмір блоку 16 байт (або 128 біт) ... typedef uint8_t vect [BLOCK_SIZE]; // Визначаємо тип vect як 16-байтовий масив

Додавання двох довічних векторів по модулю 2

Ця функція в стандарті визначена як X-перетворення. Кожен байт першого вектора КСОР з відповідним байтом другого вектора, і результат пишеться в третій (вихідний) вектор:

static void GOST_Kuz_X (const uint8_t * a, const uint8_t * b, uint8_t * c) {int i; for (i = 0; i <BLOCK_SIZE; i ++) c [i] = a [i] ^ b [i]; }

Нелінійне биективное перетворення (перетворення S)

Це перетворення в нашому випадку повторює S-перетворення з алгоритму «Стрибог» ГОСТ 34.11-2012. Масив S-перетворень теж аналогічний ГОСТ 34.11-2012:

static const unsigned char Pi [256] = {0xFC, 0xEE, 0xDD, ... 0x63, 0xB6};

Тут для економії місця показані в повному обсязі значення, визначені в стандарті, а тільки три перших і два останніх. Коли будеш писати код, не забудь про інші значення і про те, що в стандарті вони записані в десятковому вигляді.

Код самої функції перетворення S виходить такий:

static void GOST_Kuz_S (const uint8_t * in_data, uint8_t * out_data) {int i; for (i = 0; i <BLOCK_SIZE; i ++) out_data [i] = Pi [in_data [i]]; } перетворення S

Зворотне нелінійне биективное перетворення (зворотне перетворення S)

Оскільки нам потрібно не тільки зашифровувати повідомлення, але і розшифровувати теж, то кожному перетворенню зашифрования необхідно ставити у відповідність зворотне перетворення для розшифрування. Сама функція зворотного S-перетворення виглядає практично так само, як і пряме S-перетворення:

static void GOST_Kuz_reverse_S (const uint8_t * in_data, uint8_t * out_data) {int i; for (i = 0; i <BLOCK_SIZE; i ++) out_data [i] = reverse_Pi [in_data [i]]; }

Відмінність тільки в масиві перетворення, зворотне до масиву прямого перетворення (в стандарті цей масив не наводиться, тому напишемо тут його повністю):

static const unsigned char reverse_Pi [256] = {0xA5, 0x2D, ​​0x32, 0x8F, 0x0E, 0x30, 0x38, 0xC0, 0x54, 0xE6, 0x9E, 0x39, 0x55, 0x7E, 0x52, 0x91, 0x64, 0x03, 0x57, 0x5A, 0x1C, 0x60, 0x07, 0x18, 0x21, 0x72, 0xA8, 0xD1, 0x29, 0xC6, 0xA4, 0x3F, 0xE0, 0x27, 0x8D, 0x0C, 0x82, 0xEA, 0xAE, 0xB4, 0x9A, 0x63, 0x49, 0xE5, 0x42, 0xE4, 0x15, 0xB7, 0xC8, 0x06, 0x70, 0x9D, 0x41, 0x75, 0x19, 0xC9, 0xAA, 0xFC, 0x4D, 0xBF, 0x2A, 0x73, 0x84, 0xD5, 0xC3, 0xAF, 0x2B, 0x86, 0xA7, 0xB1, 0xB2, 0x5B, 0x46, 0xD3, 0x9F, 0xFD, 0xD4, 0x0F, 0x9C, 0x2F, 0x9B, 0x43, 0xEF, 0xD9, 0x79, 0xB6, 0x53, 0x7F, 0xC1, 0xF0, 0x23, 0xE7, 0x25, 0x5E, 0xB5, 0x1E, 0xA2, 0xDF, 0xA6, 0xFE, 0xAC, 0x22, 0xF9, 0xE2, 0x4A, 0xBC, 0x35, 0xCA, 0xEE, 0x78, 0x05, 0x6B, 0x51, 0xE1, 0x59, 0xA3, 0xF2, 0x71, 0x56, 0x11, 0x6A, 0x89, 0x94, 0x65, 0x8C, 0xBB, 0x77, 0x3C, 0x7B, 0x28, 0xAB, 0xD2, 0x31, 0xDE, 0xC4, 0x5F, 0xCC, 0xCF, 0x76, 0x2C, 0xB8, 0xD8, 0x2E, 0x36, 0xDB, 0x69, 0xB3, 0x14, 0x95, 0xBE, 0x62, 0xA1, 0x3B, 0x16, 0x66, 0xE9, 0x5C, 0x6C, 0x6D, 0xAD, 0x37, 0x61, 0x4B, 0xB9, 0xE3, 0xBA, 0xF1, 0xA0, 0x85, 0x83, 0xDA, 0x47, 0xC5, 0xB0, 0x33, 0xFA, 0x96, 0x6F, 0x6E, 0xC2, 0xF6, 0x50, 0xFF, 0x5D, 0xA9, 0x8E, 0x17, 0x1B, 0x97, 0x7D, 0xEC, 0x58, 0xF7, 0x1F, 0xFB, 0x7C, 0x09, 0x0D, 0x7A, 0x67, 0x45, 0x87, 0xDC, 0xE8, 0x4F, 0x1D, 0x4E, 0x04, 0xEB, 0xF8, 0xF3, 0x3E, 0x3D, 0xBD, 0x8A, 0x88, 0xDD, 0xCD, 0x0B, 0x13, 0x98, 0x02, 0x93, 0x80, 0x90, 0xD0, 0x24, 0x34, 0xCB, 0xED, 0xF4, 0xCE, 0x99, 0x10, 0x44, 0x40, 0x92, 0x3A, 0x01, 0x26, 0x12, 0x1A, 0x48, 0x68, 0xF5, 0x81, 0x8B, 0xC7, 0xD6, 0x20, 0x0A, 0x08, 0x00, 0x4C, 0xD7, 0x74};

Лінійне перетворення (перетворення L)

Для виконання даного перетворення необхідна функція множення чисел в кінцевому полі (або поле Галуа) над непріводімим полиномом x ^ 8 + x ^ 7 + x ^ 6 + x + 1. Це найскладніше місце для розуміння в даному стандарті (навіть Вікіпедія не надто допомагає ). Реалізується це таким чином:

static uint8_t GOST_Kuz_GF_mul (uint8_t a, uint8_t b) {uint8_t c = 0; uint8_t hi_bit; int i; for (i = 0; i <8; i ++) {if (b & 1) c ^ = a; hi_bit = a & 0x80; a << = 1; if (hi_bit) a ^ = 0xc3; // Полином x ^ 8 + x ^ 7 + x ^ 6 + x + 1 b >> = 1; } Return c; }

В цілому, якщо уважно подивитися на код, можна побачити, що це за великим рахунком множення в стовпчик з додаванням числа 0xс3, яке і являє потрібний нам поліном.

Далі, використовуючи наведену вище функцію, реалізуємо перетворення R, яке є частиною лінійного перетворення L. Перетворення R виконується з використанням лінійного регістра зсуву зі зворотним зв'язком. Кожен байт з блоку множиться за допомогою функції GOST_Kuz_GF_Mul на один з коефіцієнтів з ряду (148, 32, 133, 16, 194, 192, 1, 251, 1, 192, 194, 16, 133, 32, 148, 1) в залежності від порядкового номера байта. Байти складаються між собою за модулем 2, і всі 16 байт блоку зсуваються в бік молодшого розряду, а отримане число записується на місце ліченого байта.

Схема перетворення R

Для реалізації R-перетворення спочатку визначимо масив потрібних нам коефіцієнтів:

static const unsigned char l_vec [16] = {1, 148, 32, 133, 16, 194, 192, 1, 251, 1, 192, 194, 16, 133, 32, 148};

Далі пишемо саму функцію R-перетворення:

static void GOST_Kuz_R (uint8_t * state) {int i; uint8_t a_15 = 0; vect internal; for (i = 15; i> = 0; i--) {internal [i - 1] = state [i]; // Рухаємо байти в сторону молодшого розряду a_15 ^ = GOST_Kuz_GF_mul (state [i], l_vec [i] ); } // Пишемо в останній байт результат складання internal [15] = a_15; memcpy (state, internal, BLOCK_SIZE); }

Лінійне перетворення L утворюється зсувом регістра 16 разів, або шістнадцятикратний повторенням функції GOST_Kuz_R:

static void GOST_Kuz_L (const uint8_t * in_data, uint8_t * out_data) {int i; vect internal; memcpy (internal, in_data, BLOCK_SIZE); for (i = 0; i <16; i ++) GOST_Kuz_R (internal); memcpy (out_data, internal, BLOCK_SIZE); }

Зворотне лінійне перетворення (зворотне перетворення L)

Для того щоб можна було не тільки зашифровувати повідомлення, але і розшифровувати їх, нам необхідно зворотне лінійне перетворення.

Це запишеться наступним чином:

static void GOST_Kuz_reverse_L (const uint8_t * in_data, uint8_t * out_data) {int i; vect internal; memcpy (internal, in_data, BLOCK_SIZE); for (i = 0; i <16; i ++) GOST_Kuz_reverse_R (internal); memcpy (out_data, internal, BLOCK_SIZE); }

Як ти напевно здогадався, функція GOST_Kuz_reverse_R - це не що інше, як зворотне перетворення R. Виглядає це таким чином:

static void GOST_Kuz_reverse_R (uint8_t * state) {int i; uint8_t a_0; a_0 = state [15]; vect internal; for (i = 0; i <16; i ++) {internal [i] = state [i - 1]; // Рухаємо все на старі місця a_0 ^ = GOST_Kuz_GF_mul (internal [i], l_vec [i]); } Internal [0] = a_0; memcpy (state, internal, BLOCK_SIZE); }

Продовження доступно тільки учасникам

Варіант 1. Приєднайся до товариства «Xakep.ru», щоб читати всі матеріали на сайті

Членство в співтоваристві протягом зазначеного терміну відкриє тобі доступ до ВСІХ матеріалами «Хакера», збільшить особисту накопичувальну знижку і дозволить накопичувати професійний рейтинг Xakep Score! Детальніше

Варіант 2. Відкрий один матеріал

Зацікавила стаття, але немає можливості стати членом клубу «Xakep.ru»? Тоді цей варіант для тебе! Зверни увагу: цей спосіб підходить тільки для статей, опублікованих більше двох місяців тому.