Шифрування по держстандарт 28147 89

Відомий у суспільстві термін «продуктивність процесора» є об'єктивним, обчислюваним параметром, який міряють у флопах. Втім, більшість вимірює його в гігагерцях, за наївністю вважаючи, що це одне й те саме. Термін «продуктивність коду» не знає ніхто, і одразу поясню чому.

Причина в тому, що я його нещодавно придумав і поки що нікому про це не розповідав. Проте продуктивність коду, як і продуктивність процесора, має об'єктивні характеристики, які піддаються вимірам. Ця стаття – саме про продуктивність коду, що виконується процесорним ядром.

У чому вимірюється продуктивність коду? Оскільки я перший про це заговорив, то по праву першовідкривача його вимірюватиму в RTT-шках;).

Тепер серйозно. У сучасних процесорах основними перетвореннями є події над 32-бітними числами, решта за великим рахунком екзотика. Тому враховуватимемо головне – операції з 32-бітовими числами. Як ти вважаєш, скільки 32-бітових операцій одночасно може виконати ядро ​​сучасного процесора?

Студент відповість – одну, його викладач подумає і скаже, що чотири, професіонал – що поки що лише дванадцять операцій.

Так ось, програмний код, який завантажує всі виконавчі пристрої процесора одночасно протягом усього часу виконання коду, матиме продуктивність 12 RTT-шек. Максимум! Чесно зізнаюся, такого коду я раніше не писав, але в цій статті спробую зробити над собою зусилля.

Я доведу, що код із одночасним виконанням дванадцяти 32-бітових операцій – можливий

Програмний код, який використовує в процесорному ядрі один виконавчий пристрій, природно, матиме продуктивність 1 RTT-шку. Такою продуктивністю коду можуть похвалитися програми, що генеруються компіляторами мов високого рівня, та інтерпретатори віртуальних машин. Не слід вважати, що показник завантаження процесора, який можна побачити в диспетчері завдань ОС, може бути об'єктивним критерієм ефективності коду. Завантаження ядра процесора може бути 100%, але при цьому програмний код використовуватиме один виконавчий пристрій у ньому (продуктивність 1 RTT). У цьому випадку при 100% завантаженні процесорне ядро ​​працюватиме в 1/12 своєї максимальної продуктивності. Іншими словами, коли в диспетчері завдань ОС Windows показується максимальне завантаження процесора, його реальна продуктивність може змінюватись від 1 до 12 RTT. Побачивши у вікні продуктивності 100% завантаження на якому-небудь процесорному ядрі, неправильно вважати, що в цьому ядрі працюють всі виконавчі пристрої, аж ніяк!

Єдиним критерієм непрямої оцінки роботи процесорного ядра з максимальною продуктивністю може бути його енергоспоживання і, як наслідок, шум кулера. Ось якщо кулер зашумів, тоді так – завантаження пішло по максимуму. Втім, настав час закінчувати із загальними поняттями і переходити до суворої практики.

Традиційна реалізація ГОСТ 28147-89

Я не професіонал у галузі інформаційної безпеки, але все ж таки знайомий з темою шифрування. Зайнятися саме симетричним потоковим шифруванням мене спонукали розмови з професійним криптографом, якого я глибоко поважаю. І, зайнявшись цією темою, я постарався зробити саме добре і не просто добре, а ще й швидко, виконуючи максимальну кількість операцій за одиницю часу. Іншими словами, переді мною постало завдання написати програмний код з максимальним значенням RTT.

Криптографічне перетворення за ГОСТ 28147-89 використовується для потокового шифрування інформації в каналах зв'язку та дискових накопичувачах.

В даний час повсюдно застосовується програмна реалізація цього ГОСТу на РОН центрального процесора. У відомих методах реалізації ГОСТу вся секретна інформація (ключі шифрування, блоки замін) розміщуються в оперативній пам'яті. Це знижує надійність шифрування, оскільки, маючи дамп оперативної пам'яті, можна виявити всі секретні елементи криптопреобразования. Крім цього, метод має обмеження швидкодії, обумовлені розташуванням основних об'єктів криптоперетворення в ВП і неповним завантаженням виконавчих пристроїв ALU. Сучасні процесори, реалізуючи криптопроцедуру за відомим методом, можуть забезпечити швидкість шифрування на рівні 40-60 мегабайт на секунду. І якщо вже розбиратися до кінця, то причиною низької швидкодії та слабкої захищеності криптоперетворення є програмна реалізація блоку підстановок. Опис його в ГОСТ див. на рис. 1.

За п. 1.2 ГОСТу цей блок реалізує зошитові (по чотири біти) перестановки в 32-бітному слові, але архітектура процесора х86/64 та його система команд не здатна ефективно маніпулювати зошитами.

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

У більш розвинених реалізаціях ці таблиці мають розмір 1024 байти (256 слів по чотири байти). Це зроблено для того, щоб реалізувати в таблицях додатково циклічне зрушення на 11 позицій отриманого в результаті підстановки 32-бітного слова (наступна операція алгоритму перетворення за ГОСТом). Приклад реалізації ДСТУ за цим методом показаний у додатку 1 (на диску).

Інформація блоку підстановок є секретним компонентом криптофункції (як це сформульовано у ГОСТі, див. рис. 2).

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

Коротше кажучи, ФСБ пропускає такі програмні реалізації криптопроцедури, незважаючи на явне зниження стійкості такого рішення та пряме порушення власних вимог за ГОСТом (п. 1.7). І це незважаючи на загальновідомі методи злому шифрів через знімання дампа пам'яті.

До питання зберігання ключів та блоків замін у внутрішніх регістрах процесора ми повернемося трохи пізніше (є красиве і швидке рішення), а поки що тільки ключі шифрування ми зберігатимемо в ММХ-регістрах, це надійніше.

Але вистачить лірики, важливо в рамках цієї теми те, що цей програмний код має продуктивність в 1 RTT-шку. Тепер напишемо код із продуктивністю 2 RTT-шки.

Багатопотокова реалізація ГОСТ 28147-89

Єдиною можливістю прискорити криптопроцедур у відомому алгоритмі є введення багатопоточності. Сенс такого зміни реалізації алгоритму у тому, щоб обраховувати відразу кілька блоків даних паралельно.

Більшість програмістів має на увазі під паралельною обробкою виключно роботу кількох процесорних ядер, синхронізованих через переривання та семафори в пам'яті.

Однак існує й інший варіант паралельної обробки даних на одному-єдиному ядрі процесора. Поясню цю неочевидну думку.

Сучасні процесори мають у своєму складі як мінімум два, а то й три-шість арифметико-логічних пристроїв. Ці АЛУ (FPU, блоки адресної арифметики тощо) можуть працювати незалежно один від одного, єдиною умовою їхньої паралельної роботи є непересічні програмні об'єкти, якими вони оперують. Іншими словами, у командах, які одночасно виконують АЛУ, адреси пам'яті та номери регістрів мають бути різними. Або загальні регістри та адреси пам'яті, до яких звертаються різні виконавчі пристрої процесора, повинно виконуватися операцій записи.

Завантаженням роботою всіх АЛУ управляє спеціальний апаратний блок усередині процесорного ядра - планувальник, який переглядає код форвардно, що виконується, на глибину до 32-64 байт. Якщо планувальник виявляє команди, які можна запускати на АЛУ без конфліктів, він їх запускає одночасно різних виконавчих пристроях. При цьому лічильник виконаних команд вказує на ту команду, що виконується (їх у такій схемі кілька), після якої всі команди вже виконані.

Більшість програмних послідовностей, що генеруються автоматично (компіляторами), не можуть завантажити всі АЛУ та FPU, що знаходяться в ядрі процесора. У цьому випадку обладнання процесора простоює, що значно знижує його результативну продуктивність. Розробники процесорів це розуміють та вводять режими збільшення частоти ядра, коли обладнання використовується не повністю. Також для цього призначені системи гіпертрейдингу, і цю систему я використовуватиму для пресування коду по максимуму надалі.

Компілятори, навіть найоптимізованіші, і тим більше – движки віртуальних машин, не можуть формувати оптимізований код з точки зору швидкодії. Тільки програміст із інженерними знаннями може написати такий оптимізований код, причому інструментом для його написання є виключно асемблер.

Характерною ілюстрацією можливості виконання кількох незалежних програмних потоків на одному ядрі процесора служить реалізація ГОСТу, що виконується у два потоки на єдиному ядрі процесора. Ідея коду проста: є два блоки даних для шифрації/дешифрації, але одне ядро ​​процесора, яке виконуватиме перетворення. Можна виконати цих двох блоків даних перетворення послідовно, і робиться до нашого часу. І тут час, необхідне виконання перетворень, подвоюється.

Але можна зробити й інакше: чергувати команди, які стосуються обробки різних блоків даних. Графічно ці варіанти представлені на рис. 3.

На малюнку верхній приклад показує нормальний порядок виконання обробки двох незалежних блоків даних. Спочатку обробляється перший блок, потім процесор переходить до обробки другого блоку. Природно, результуючий час дорівнює подвоєному часу, який необхідний обробки одного блоку, а виконавчі пристрої ядра процесора завантажені в повному обсязі.

Далі показаний приклад із чергуванням команд із різних потоків обробки. У цьому випадку команди, що належать до різних блоків даних, чергуються. Планувальник вибирає незалежні одна від одної команди і передає їх на виконання в АЛУ1 та АЛУ2. Угруповання команд першого і другого потоку на цих АЛУ здійснюється автоматично, оскільки в алгоритм роботи планувальника закладено угруповання команд із зачепленням за загальним даними на тому самому виконавчому пристрої.

Щоб такий програмний код працював без простоїв АЛУ, необхідно, щоб кожен програмний потік працював зі своїм набором регістрів. Кеш у цій схемі стає вузьким місцем (у нього лише два порти видачі даних), тому ключі зберігаємо у MMX-регістрах. Оскільки у разі вузли заміни (і зсуву) у пам'яті лише читаються, всі вони можуть бути загальними обох програмних потоків.

Це, звичайно, дуже спрощене пояснення принципу паралельного виконання програмних потоків на єдиному ядрі, реально набагато складніше. На практиці потрібно враховувати конвеєрну архітектуру виконавчих пристроїв, обмеження на одночасний доступ до кешу та блоку регістрів РОН, наявність вузлів адресної арифметики, комутаторів і багато чого ще… Так що це – тема для професіоналів, яких можна перерахувати на пальцях… однієї руки.

Метод паралельного шифрування ефективно реалізується тільки для 64-бітного режиму роботи процесора, оскільки в цьому режимі є достатньо РОН (цілих 16 штук!). Приклад реалізації ДСТУ за цим методом показаний у додатку 2 (на диску).

Зрозуміло, що ця реалізація ГОСТу має продуктивність коду 2 RTT-шки. А тепер подивимося, як це позначається на часі виконання.

Цикл шифрування одного потоку (додаток 1) становить 352 такту, і цей час обраховується 8 байт даних, для двопоточної реалізації ГОСТа (додаток 2) потрібно 416 тактів процесора, але при цьому обраховується 16 байт. Таким чином, результуюча швидкість перетворення збільшується з 80 до 144 мегабайт для процесора частотою 3,6 ГГц.

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

Теоретично код із другого прикладу повинен виконуватися за таку ж кількість тактів, що й код із першого прикладу, але вузол планувальника розробляють хоч і інженери фірми Intel, але теж люди, а ми всі далекі від досконалості. Отже є можливість оцінити ефективність їх творіння. Цей код працюватиме і на процесорі AMD, і можна порівняти їхні результати.

Якщо хтось мені не вірить на слово, то для таких невіруючих на диску додаються тестові програми з лічильниками тактів. Програми у вихідних кодах, звичайно на асемблері, так що є можливість перевірити мої слова, а заразом і підглянути деякі хитрощі професійного кодингу.

Використання SSE-регістрів та AVX-команд сучасних процесорів для реалізації ГОСТ 28147-89

Сучасні процесори архітектури х86/64 мають у своєму складі набір регістрів SSE розміром 16 байт та спеціалізовані FPU (як мінімум два) для виконання різних операцій над цими регістрів. Можлива реалізація ГОСТу цьому обладнанні, причому у разі вузли заміни можна розміщувати над вигляді таблиць в оперативної пам'яті, а безпосередньо на виділених SSE-регістрах.

На одному SSE-реєстрі можна розмістити одразу дві таблиці із 16 рядків. Таким чином, чотири SSE-регістри дозволять повністю розмістити всі таблиці замін. Єдиною умовою такого розміщення є вимога чергування, згідно з якою зошити одного байта повинні поміщатися у різні SSE-регістри. Крім цього, доцільно розміщувати молодші та старші зошити вхідних байтів відповідно у молодших та старших зошитах байтів SSE-регістрів.

Ці вимоги обумовлюються оптимізацією під наявний набір AVX-команд. Таким чином, кожен байт SSE-реєстру буде містити два зошити, що відносяться до різних байтів вхідного регістра блоку підстановок, при цьому позиція байта на SSE-реєстрі однозначно відповідає індексу таблиці заміни блоку підстановки.

Схема одного з можливих розміщень вузлів заміни на SSE-регістрах показана на рис. 4.

Розміщення секретної інформації вузлів замін на SSE-регістрах підвищує захищеність криптопроцедури, але повна ізоляція цієї секретної інформації можлива за таких умов:

• Ядро процесора переведено в режим хоста гіпервізора і в ньому примусово відключено блок переривань (APIC). У цьому випадку ядро ​​процесора повністю ізольоване від ОС та додатків, що функціонують на обчислювальній установці.
• Завантаження SSE-регістрів та ізоляція обчислювального ядра проводиться до початку старту ОС, оптимальним є виконання цих процедур із модуля довіреного завантаження (МДЗ).
• Програми криптопроцедур по ГОСТу розташовуються в області пам'яті обчислювальної установки, що немодифікується (або БІОС, або у флеш-пам'яті МДЗ).

Виконання цих вимог дозволить гарантувати повну ізоляцію та незмінність програмного коду криптопроцедур і секретної інформації, що використовується в них.

Для ефективної вибірки з SSE-регістрів зошит використовуються багатовходові байтові комутатори, що є у складі блоків FPU. Ці комутатори дозволяють здійснювати пересилання з будь-якого байта джерела будь-який байт приймача, за індексами, що знаходяться в спеціальному індексному SSE-реєстрі. Причому паралельно виконується пересилання всім 16 байт SSE-регістра-приймача.

Маючи вузли зберігання підстановок на SSE-регістрах та багатовхідний комутатор у блоках FPU, можна організувати наступне перетворення у блоці підстановок (рис. 5).

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

• Створити відповідний дизайн чипа, але це для нас фантастика.
• Перепрограмувати мікрокод та створити власну процесорну команду для реалізації цієї функції на існуючих процесорах – це вже не фантастика, але, на жаль, нереально у нинішніх умовах.
• Написати програму на офіційних командах AVX. Варіант нехай і не дуже ефективний, зате здійснимо «тут і зараз». Тож цим і займемося далі.

Роботою комутаторів керує спеціальна триадресна команда AVX VPSHUFB. Її перший операнд є приймачем інформації з комутаторів, другий - джерелом, якого підключені входи комутаторів. Третій операнд є регістром для комутаторів, кожен байт якого асоційований з відповідним комутатором; значення у ньому задає номер напряму, з якого комутатор зчитує інформацію. Опис цієї команди з офіційної документації Intel див. на рис. 5. На рис. 6 наведено схему роботи цієї команди - зображена тільки половина SSE-регістрів, для другої половини все аналогічно.

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

Програма з вибіркою зошит через комутатори FPU була написана, але я навіть не став поміщати її у додаток – надто убого. Мати регістр розміром 128 біт і використовувати у ньому лише 32 біти - непрофесійно.

Як то кажуть, «Наш фініш – горизонт», тому вичавлювати так вичавлювати... пресуватимемо і складатимемо в пакети!

Це не гра слів, а сувора FPUшна реальність – регістри SSE можна розбивати на рівні частини та виконувати над цими частинами однакові перетворення однією командою. Для того щоб процесор це зрозумів, є магічна літера «Р» - пакет, яка ставиться перед мнемонікою команди, і не менш магічні літери «Q», «D», «W», «B», які ставляться в кінці і оголошують, які частини розбиті у цій команді регістри SSE.

Нас цікавить пакетний режим з розбивкою SSE-реєстру на чотири 32-бітові блоки; відповідно, всі команди матимуть префікс «P», а наприкінці – символ «D». Це дає можливість однією процесорною командою паралельно обробляти відразу чотири блоки по 32 біти, тобто паралель розраховувати чотири блоки даних.

Програма, що реалізує цей метод, є в додатку 3, там же – всі пояснення.

Втім, пресувати так пресувати! У сучасних процесорах є як мінімум два блоки FPU, і для їх повного завантаження можна використовувати два потоки незалежних команд. Якщо грамотно чергувати команди з незалежних потоків, то можна завантажити роботою обидва блоки FPU повністю і отримати відразу вісім потоків даних, що паралельно обробляються. Така програма була написана, і її можна подивитися в додатку 4, тільки дивитися потрібно обережно - можна злетіти з котушок. Це, як то кажуть, «код не для всіх...».

Ціна запитання

Використання SSE-регістрів для зберігання вузлів заміни зрозуміло - воно дає певну гарантію ізоляції секретної інформації, а ось сенс розрахунку самої криптофункції на FPU не є очевидним. Тому були проведені виміри часу виконання стандартних процедур за методом прямої заміни відповідно до ГОСТу для чотирьох та восьми потоків.

Для чотирьох потоків було отримано швидкість виконання 472 процесорних такту. Таким чином, для процесора з частотою 3,6 ГГц один потік вважається зі швидкістю 59 мегабайт на секунду, а чотири потоки відповідно зі швидкістю 236 мегабайт на секунду.

Для восьми потоків було отримано швидкість виконання 580 процесорних тактів. Таким чином, для процесора з частотою 3,6 ГГц один потік вважається зі швидкістю 49 мегабайт на секунду, а вісім потоків зі швидкістю 392 мегабайт на секунду.

Як може помітити читач, код прикладі № 3 має продуктивність 4 RTT, а код у прикладі № 4 має продуктивність 8 RTT. У цих прикладах на SSE-регістрах закономірності ті ж, що і при використанні РОН, тільки планувальник знизив свою ефективність. Зараз він забезпечує 20% збільшення тривалості при двократному збільшенні довжини коду.

Ці результати були отримані з використанням універсальних AVX-команд, наявних як у процесорах Intel, так і в процесорах AMD. Якщо виконати оптимізацію під процесор AMD, результат буде значно кращим. Звучить упоперек тренду, але це правда, і ось чому: процесори AMD мають додатковий набір команд, так зване XOP-розширення, і в цьому додатковому наборі команд є такі, які значно спрощують реалізацію алгоритму ГОСТу.

Йдеться про команди логічного пакетного зсуву байтів і пакетного циклічного зсуву подвійних слів. У прикладах, наведених у додатках 3 і 4, використовуються послідовності універсальних команд, що реалізують необхідне перетворення: у першому випадку одна «зайва» команда, а в іншому випадку відразу чотири зайві команди. Отже, резерви оптимізації є, і чималі.

Якщо мова зайшла про подальшу оптимізацію, не зайве пам'ятати про наявність 256-бітних регістрів (YMM-регістри), використовуючи які можна теоретично подвоїти швидкість обчислень. Але поки це тільки перспектива, на даний момент процесори дуже сповільнюються, коли виконують 256-бітові інструкції (FPU мають ширину тракту 128 біт). Експерименти показали, що на сучасних процесорах рахунок у 16 ​​потоків на YMM-регістрах виграшу не дає. Але це тільки поки що, на нових моделях процесорів, безсумнівно, буде збільшено швидкодію 256-бітових команд, і тоді використання 16 паралельних потоків стане доцільним і призведе до ще більшого збільшення швидкості роботи криптопроцедури.

Теоретично можна розраховувати на швидкість 600-700 мегабайт за секунду за наявності в процесорі двох FPU з шириною робочого тракту 256 біт кожен. І тут можна говорити про написання коду з ефективністю 16 RTT, і це фантастика, а найближча перспектива.

Змішаний режим

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

Розраховувати на збільшення в 50% тут не доводиться, вузьким місцем стає кеш-пам'ять, де зберігаються технологічні маски, але збільшення в 100 додаткових мегабайт все ж таки отримати можна. Цей варіант не наведено в програмах (макроси аналогічні використовуваним у коді на 8 RTT), але він є у програмних файлах. Так що якщо хтось не вірить у можливість шифрування зі швидкістю 500 мегабайт в секунду на одному процесорному ядрі, нехай запустить тестові файли. Там є і тексти з коментарями, щоб ніхто не подумав, що я лукавлю.

Такий фокус можливий тільки на процесорах Intel, у AMD лише два блоки FPU на два процесорні модулі (аналог режиму гіпертрейдинг). Але є ще чотири АЛУ, які гріх не використовувати.

Можна загнати процесорні модулі "Бульдозера" в режим, аналогічний режиму гіпертрейдингу, але запускати на різних модулях в одному потоці перетворення на РОН, а в іншому потоці на SSE-регістрах і отримати ті ж 12 RTT. Цей варіант я не перевіряв, але, думаю, на AMD код 12 RTT буде працювати більш ефективно. Бажаючі можуть спробувати, тестові програми можна підкоригувати для роботи на "Бульдозерах" досить легко.

Кому це потрібно?

Серйозне питання, але з простою відповіддю – це потрібно всім. Скоро всі ми підсядемо на хмари, будемо там зберігати і дані і програми, а там як хочеться облаштувати свій власний, приватний куточок. Для цього доведеться шифрувати трафік і швидкість криптоперетворення буде головним визначальним фактором комфортної роботи в хмарі. Вибір алгоритму шифрування у нас невеликий - ГОСТ, або AES.

Причому, як це не дивно, вбудоване в процесори шифрування AES-алгоритмом виявляється значно повільніше, тести показують швидкість на рівні 100-150 мегабайт в секунду, і це при апаратній реалізації алгоритму! Проблема полягає в однопоточному рахунку та блоці замін, який оперує байтами (таблиця з 256 рядків). Отже, ГОСТ виявляється ефективнішим у реалізації на архітектурі х86/64, хто б міг подумати…

Це якщо говорити про досягнутий рівень швидкості шифрування. А якщо мати на увазі теоретичні вишукування в галузі підвищення ефективності коду, то, швидше за все, це нікому не потрібно. Фахівців рівня 3-6 RTT практично немає, компілятори взагалі генерують код на рівні 1-2,5 RTT, а основна маса програмістів не знає асемблера, а якщо знає його правопис, то не розуміє пристрої сучасного процесора. А без цих знань що асемблер, що якийсь там СІ-шарп - не має значення.

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

На відміну від американського DES у вітчизняному стандарті застосовується довший ключ - 256 біт. Крім того, російський стандарт пропонує використовувати 32 раунди шифрування, тоді як DES – лише 16.

Таким чином, основні параметри алгоритму криптографічного перетворення даних ГОСТ 28147-89 такі: розмір блоку становить 64 біти, розмір ключа - 256 біт, кількість раундів - 32.

Алгоритм є класичною мережею Фейштеля. Блок даних, що шифрується, розбивається на дві однакові частини, праву R і ліву L. Права частина складається з підключенням раунду і за допомогою деякого алгоритму шифрує ліву частину. Перед наступним раундом ліва та права частини міняються місцями. Така структура дозволяє використовувати той самий алгоритм як шифрування, так дешифрування блоку.

В алгоритмі шифрування використовуються такі операції:

• додавання слів за модулем 2 32;
• циклічний зсув слова вліво на вказане число біт;
• побітове додавання за модулем 2;
• заміна за таблицею.

На різних кроках алгоритмів ГОСТу дані, якими вони оперують, інтерпретуються та використовуються по-різному. У деяких випадках елементи даних обробляються як масиви незалежних бітів, в інших випадках – як ціле число без знака, у третіх – як складний елемент, що має структуру, що складається з декількох більш простих елементів.

Структура раунду ГОСТ 28147-89

Структура одного раунду ГОСТ 28147-89 наведено на рис. 5.1.

Блок даних, що шифрується, розбивається на дві частини, які потім обробляються як окремі 32-бітові цілі числа без знака. Спочатку права половина блоку та підключ раунду складаються за модулем 2 32 . Потім проводиться поблочна підстановка. 32-бітове значення отримане на попередньому кроці (позначимо його S ), інтерпретується як масив з восьми 4-бітових блоків коду: S=(S 0 ,S 1 ,S 2 ,S 3 ,S 4 ,S 5 ,S 6 ,S 7). Далі значення кожного з восьми блоків замінюється на нове, яке вибирається по таблиці замін наступним чином: значення блоку S i замінюється на S i -тий по порядку елемент (нумерація з нуля) i-го вузла замін (тобто i-того рядка таблиці замін, нумерація також із нуля). Іншими словами, як заміна для значення блоку вибирається елемент з номером рядка, рівним номеру блоку, що замінюється, і номером стовпця, рівним значенню блоку, що замінюється як 4-бітового цілого неотрицательного числа. У кожному рядку таблиці замін записано числа від 0 до 15 у довільному порядку без повторень. Значення елементів таблиці замін взяті від 0 до 15, так як у чотирьох бітах, які піддаються підстановці, може бути записано ціле число без знака в діапазоні від 0 до 15. Наприклад, перший рядок S-блоку може містити такі значення: 5, 8, 1, 13, 10, 3, 4, 2, 14, 15, 12, 7, 6, 0, 9, 11 . У цьому випадку значення блоку S 0 (чотири молодших біта 32-розрядного числа S) заміниться на число, що стоїть на позиції, номер якої дорівнює значенню блоку, що замінюється. Якщо S 0 = 0 , воно заміниться на 5 , якщо S 0 = 1 , воно заміниться на 8 тощо.

Рис. 5.1.

Після виконання підстановки всі 4-бітові блоки знову об'єднуються в єдине 32-бітове слово, яке потім циклічно зсувається на 11 бітів вліво. Нарешті, за допомогою побітової операції "сума за модулем 2"результат поєднується з лівою половиною, внаслідок чого виходить нова права половина R i . Нова ліва частина L i береться рівною молодшій частині блоку, що перетворюється: L i = R i-1 .

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

Процедури шифрування та розшифрування

ГОСТ 28147-89 є блоковим шифром, тому перетворення данихздійснюється блоками в так званих базових циклах. Базові цикли полягають у багаторазовому виконанні блоку даних основного раунду, розглянутого нами раніше, з використанням різних елементів ключа і відрізняються один від одного порядком використання ключових елементів. У кожному раунді використовується одна з восьми можливих 32-розрядних з'єднань.

Розглянемо процес створення підключів раундів. У ГОСТ ця процедура дуже проста, особливо в порівнянні з DES. 256-бітний ключ K розбивається на вісім 32-бітових підключів, що позначаються K 0 , K 1 , K 2 ,K 3 , K 4 , K 5 , K 6 , K 7 . Алгоритм включає 32 раунди, тому кожен підключ при шифруванні використовується в чотирьох раундах у послідовності, представленій на таблиці 5.1.

Процес розшифрування проводиться у тому алгоритму, як і шифрування . Єдина відмінність полягає в порядку використання підключів K i. При розшифруванні підключи повинні бути використані у зворотному порядку, а саме, як зазначено на

«Поки ти живий, не вмирай, на цей світ поглянь.
У багатьох душа мертва – вони мертві всередині.
Але ходять і сміються, не знаючи, що їх немає,
Не квапи свою смертну годину» – вона сказала мені.

Арія, «Там високо»

1. Вступ

1. Попередні відомості про блокові шифри

2.1 Мережі Файстеля.
2.2 Блоковий шифр ГОСТ 28147-89

1. Теоретичний мінімум

3.1 Ключова інформація
3.2 Основний крок криптоперетворення

3.3 Базові цикли:“ 32-З” , “ 32-Р” .

1. Практика

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.

1. Ця операція в літературі називається mod 2, мовою асемблера реалізується командою XOR. Але її правильніша назва mod 2 1 . Без цієї унікальної операції навряд чи можна побудувати швидкий алгоритм шифрування, що легко реалізується, і при цьому, щоб він був ще досить криптостійким. Унікальність цієї операції полягає в тому, що вона собі зворотна! Наприклад, якщо число А по XORити з числом Б, в результаті отримаємо, надалі достатньо переXORити числа Б і В між собою, щоб отримати колишнє значення А!

У цій операції ми отримали 1010 маючи числа 1110 і 0100, щоб отримати назад 1110, достатньо переXORрити між собою числа 0100 і 1010! Докладніше про цю операцію можна почитати у статті, яка вкладена на сайті www.wasm.ru, « Елементарний посібник зCRC_алгоритмам виявлення помилок» автор, якої Ross N. Williams. У цій праці є пункт — 5. Двійкова арифметика без урахування переносів». Ось саме в цій статті описана операція xor!Я вигукую тому, що в цій статті ця операція так розписана, що читач не просто розуміє як працює ця операція, він навіть починає її бачити, чути та відчувати!

1. Ця дія необхідна, щоб при розшифровуванні із шифрограми можна було отримати вихідні значення.

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 біти.

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

Перш ніж почати шифрувати блок розбивають на дві частини L і R, по 32 біта кожна. Вибирають елемент ключа і потім подають ці дві частини блоку, елемент ключа таблицю замін у функцію основного кроку, результат основного кроку це одна ітерація базового циклу, про який йтиметься в наступному пункті. Основний крок складається з наступних дій:

1. Додавання частина блоку R підсумовується з елементом ключа K по mod 2 32 . Про таку операцію я описав вище, тут теж тільки показник ступеня не «4», а «32» — результат цієї операції надалі позначатиму Smod.
2. Отриманий раніше результат Smod ділимо на чотири бітові елементи s7, s6, s5, s4, s3, s2, s1, s0 і подаємо у функцію заміни. Заміна відбувається наступним чином: вибирається елемент Smod - si, спочатку починаємо з молодшого елемента, і замінюємо значенням з таблиці замін по i - тому рядку і стовпцю, на який вказує значення елемента i. Переходимо до si +1 елементу і чинимо аналогічним чином і продовжуємо так, поки не замінимо значення останнього елемента Smod – результат цієї операції будемо позначати як Ssimple.
3. У цій операції значення Ssimple зрушуємо циклічно вліво на 11 біт і отримуємо Srol.
4. Вибираємо другу частину блоку L і складаємо по mod 2 з Srol, у результаті маємо Sxor.
5. На цій стадії частина блоку 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

практика.

Після того як ми познайомилися з теорією про те, як шифрувати інформацію настав подивитися, як відбувається шифрування на практиці.

Початкові дані:

Візьмемо блок інформації 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

1. Тепер сама хитромудра операція, але якщо придивитися по уважніше, то вона вже не така страшна, як здається спочатку. Представимо 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.

Про те, як це найпростіше реалізувати у вигляді команд асемблера, я розповім пізніше в наступному пункті, після того, як розповім про розширену таблицю.

1. Отримане значення Ssimple ми маємо зрушити на 11 біт вліво.

Рис. 8

Як видно, ця дія досить проста, і реалізується однією командою мови асемблера – rolта результат цієї операції Srol дорівнює 0819288Fh.

1. Тепер залишається частина L нашого блоку інформації по XORити зі значенням Srol. Я беру калькулятор з w2k sp4 і отримую Sxor = 091b2b8bh.
2. Це дія підсумкова і ми просто привласнюємо, чисти 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 бітів і кількість можливих ключів 2256 ! Тебе це не вражає? 🙂

- Критерій серій.

Якщо ми подивимося на наш ключ, який я навів у пункті « 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-ти;

Підсумкова таблиця коефіцієнтів:

Таблиця коефіцієнтів буде наступна (кому не ліниво може перерахувати)

Ну, в цій таблиці справи ще гірші - біти 1 і 2 групи залишаються незмінними! Криптоаналітику є, де розвернутися 🙂 З урахуванням усіх цих вимог простим перебором («в лоб») були знайдені таблиці перестановки відповідні зазначеній теорії (на сьогодні – 1276 поєднань) Ось деякі з них:

Список використаної литературы.

1. Стаття Андрія Винокурова:

Алгоритм шифрування ГОСТ 28147-89, його використання та реалізація

для комп'ютерів Intel X86.

(можна знайти за адресою: http://www.enlight.ru/crypto/frame.htm).

Тут і вихідні коди, з реалізації алгоритму шифрування.

1. Стаття Хорста Файстеля:

Криптографія та комп'ютерна безпека.

(можна знайти за тією ж адресою, що і попередню статтю)

1. 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: Цією статтею я не намагався когось перевершити. Вона була написана з наміром, полегшити вивчення ГОСТу і якщо у вас вийшли труднощі, то це не означає, що я винен у цьому. Будь розумними, і наберіться терпіння, всього вам доброго!

Алгоритм ГОСТ 28147-89 та шифр «Магма» (ГОСТ Р 34.12-2015)

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

Алгоритм ГОСТ 28147-89 (рис. 2.21) базується на схемі Фейстеля і шифрує інформацію блоками по 64 біт, які розбиваються на два підблоки по 32 біти (I, і R).Підблок R,обробляється функцією раундового перетворення, після чого значення складається зі значенням підблоку Lj, потім підблоки змінюються місцями. Алгоритм має 16 або 32 раунди в залежності від режиму шифрування (обчислення імітівставки або інші режими шифрування).

Рис. 2.21.

У кожному раунді алгоритму виконуються такі перетворення.

1. Накладення ключа.Зміст підблоку R iскладається за модулем 2 32 з ключем раунду К. Kj- це 32-бітова частина вихідного ключа, яка використовується як раундовий. Алгоритм ГОСТ 28147-89 нс використовує процедуру розширення ключа, вихідний 256-бітний ключ шифрування представляється у вигляді конкатенації (зчеплення) восьми 32-бітових підключів (рис. 2.22): К 0 , К ( , К т К, К А, К 5 К 6 К 7 .

У процесі шифрування використовується одна з цих підключень До

З 1-го по 24-й раунд - у прямій послідовності:

З 25-го та 32-го раунду - у зворотній послідовності:

Рис. 2.22. Будова ключа шифрування алгоритму ГОСТ 28147-89

2. Таблична заміна.Після накладання ключа підблокувати R iрозбивається на вісім частин але 4 біти, значення кожної з яких окремо замінюється відповідно до таблиці заміни (S-блоком). Усього використовується вісім S-блоків - S0, S, S2, S3, S4, S5, S6, S7. Кожен S-блок алгоритму ГОСТ 28147-89 є вектором (одномірний масив) з ^елементами, пронумерованими від 0 до 15. Значеннями S-блоку є 4-бітові числа, тобто. цілі числа від 0 до 15.

З таблиці S-блоку береться елемент, порядковий номер якого збігається зі значенням, що надходить на вхід підстановки.

приклад 2.6.

Нехай є S-блок такого вигляду:

Нехай на вхід цього S-блоку подано значення 0100 2 = 4. Виходом S-блоку буде 4 елемент таблиці замін, тобто. 15 = 11112 (нумерація елементів починається з нуля).

осіб замін не визначено стандартом, як це зроблено, наприклад, у шифрі DES. Змінні значення таблиць замін істотно ускладнюють криптоаналіз алгоритму. У той самий час стійкість алгоритму істотно залежить від своїх правильного вибору.

На жаль, алгоритм ДЕРЖСТАНДАРТ 28147-89 має «слабкі» таблиці замін, при використанні яких алгоритм може бути досить легко розкритий криптоаналітичними методами. До «слабких» належить, наприклад, тривіальна таблиця замін, у якій вхід дорівнює виходу (табл. 2.16).

Таблиця 2.16

Приклад слабкого S-блоку

Вважається, що конкретні значення таблиць замін повинні зберігатися в секреті і є довгостроковим ключовим елементом, тобто. діють протягом більш тривалого терміну, ніж окремі ключі. Однак секретні значення таблиць замін не є частиною ключа і не можуть збільшити його ефективну довжину.

Справді, секретні таблиці замін можуть бути обчислені за допомогою наступної атаки, яку можна застосовувати на практиці:

• встановлюється нульовий ключ і шукається «нульового вектора», тобто. значення z = F( 0), де F -функція раундового перетворення алгоритму Це вимагає близько 232 тестових операцій шифрування;
• за допомогою нульового вектора обчислюються значення таблиць замін, що займає не більше 2 11 операцій.

Однак навіть при порушенні конфіденційності таблиць замін стійкість шифру залишається надзвичайно високою і не стає нижчою за допустиму межу.

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

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

У сучасних алгоритмах S-блоки зазвичай є вектором (одномірний масив), що містить 2" т-бітові елементи. Вхід блоку визначає номер елемента, значення якого є виходом S-блоку.

Для проектування S-блоків було висунуто низку критеріїв. Таблиця замін повинна задовольняти:

• строгому лавинному критерію;
• критерієм незалежності бітів;
• вимогу нелінійності від вхідних значень.

Для виконання останньої вимоги було запропоновано задавати лінійну комбінацію iбітів ( i = 1, ..., т)значень таблиці замін бентфункціями(англ. bent -відхиляється, у разі - від лінійних функцій). Бент-функції утворюють спеціальний клас булевих функцій, що характеризуються вищим класом нелінійності та відповідністю суворому лавинному критерію.

У деяких роботах для S-блоків пропонується перевірка виконання гарантованого лавинного ефекту порядку у - при зміні одного вхідного біта змінюється принаймні у вихідних біт S-блоку. Властивість гарантованого лавинного ефекту порядку від 2 до 5 забезпечує досить хороші дифузійні характеристики S-блоків для будь-якого алгоритму шифрування.

При проектуванні досить великих таблиць замін можуть бути використані такі підходи:

• випадковий вибір (для S-блоків невеликого розміру може призвести до створення слабких таблиць замін);
• випадковий вибір з подальшою перевіркою на відповідність різним критеріям та відбраковуванням слабких S-блоків;
• ручний вибір (для S-блоків великих розмірів занадто трудомісткий);
• математичний підхід, наприклад, генерація з використанням бент-функцій (цей підхід застосований в алгоритмі CAST).

Можна запропонувати наступний порядок проектування окремих S-блоків алгоритму ГОСТ 28147-89:

• кожен S-блок може бути описаний четвіркою логічних функцій, кожна з функцій повинна мати чотири логічні аргументи;
• необхідно, щоб ці функції були досить складними. Цю вимогу складності неможливо висловити формально, однак як необхідну умову можна вимагати, щоб відповідні логічні функції, записані в мінімальній формі (тобто з мінімально можливою довжиною виразу) з використанням основних логічних операцій, не були коротшими від деякого необхідного значення;
• окремі функції, навіть використовувані у різних таблицях замін, повинні різнитися між собою достатньою мірою.

У 2011 р. запропоновано нову атаку «рефлексивна зустріч посередині», яка незначно знижує стійкість ГОСТ 28147-89 (з 2256 до 2225). Кращий результат криптоаналізу алгоритму станом на 2012 р. дозволяє знизити його стійкість до 2192, вимагаючи відносно великого розміру шифротексту та обсягу попередньо сформованих даних. Незважаючи на запропоновані атаки, на сучасному розвитку обчислювальної техніки ГОСТ 28147-89 зберігає практичну стійкість.

Шифр "Магма" (ГОСТ Р 34.12-2015).Стандарт ГОСТ 28147-89 діяв у Росії понад 25 років. За цей час він показав достатню стійкість та хорошу ефективність програмних та апаратних реалізацій, у тому числі на низькоресурсних пристроях. Хоча і були запропоновані криптоаналітичні атаки, що знижують оцінки його стійкості (найкраща – до 2192), вони далекі від можливості практичної реалізації. Тому було прийнято рішення про включення алгоритму ГОСТ 28147-89 до новоствореного стандарту симетричного шифрування.

У шопі 2015 р. прийнято два нові національні криптографічні стандарти: ГОСТ Р 34.12-2015 «Інформаційна технологія. Криптографічний захист інформації. Блокові шифри» та ГОСТ Р 34.13-2015 «Інформаційна технологія. Криптографічний захист інформації. Режими роботи блокових шифрів», які набувають чинності з 1 січня 2016 р.

Стандарт ГОСТ Р 34.12-2015 містить опис двох блокових шифрів із довжиною блоку 128 та 64 біт. Шифр ГОСТ 28147-89 із зафіксованими блоками нелінійної підстановки включений у новий ГОСТ Р 34.12-2015 як 64-бітовий шифр під назвою «Магма» («Magma»).

Нижче наведено закріплені в стандарті блоки замін:

Наведений у стандарті набір S-блоків забезпечує найкращі характеристики, що визначають стійкість криптоалгоритму до диференційного та лінійного криптоаналізу.

На думку технічного комітету зі стандартизації «Криптографічний захист інформації» (ТК 26), фіксація блоків нелінійної підстановки зробить алгоритм ГОСТ 28147-89 уніфікованішим і допоможе виключити використання «слабких» блоків нелінійної підстановки. Крім того, фіксація у стандарті всіх довгострокових параметрів шифру відповідає прийнятій міжнародній практиці. Новий стандарт ГОСТ Р 34.12-2015 термінологічно та концептуально пов'язаний із міжнародними стандартами ІСО/МЕК 10116 «Інформаційні технології. Методи забезпечення безпеки. Режими роботи для «-бітових блокових шифрів» (ISO/IEC 10116:2006 Information technology - Security techniques - Modes of operation for n-bit block cipher) та серії ІСО/МЕК 18033 «Інформаційні технології. Методи та засоби забезпечення безпеки. Алгоритми шифрування»: ІСО/МЕК 18033-1:2005 «Частина 1. Загальні положення» (ISO/IEC 18033-1:2005 2010 «Частина 3. Блокові шифри» (ISO/IEC 18033-3:2010 (Information technology - Security techniques - Encryption algorithms - Part 3: Block ciphers)).

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

Режими роботи блокових шифрів (простої заміни, гамування, гамування зі зворотним зв'язком по виходу, гамування зі зворотним зв'язком по шифротексту, простої заміни з зачепленням та вироблення імітувставки) виведені в окремий стандарт ГОСТ Р 34.13-2015, практиці. Ці режими застосовні як до шифру "Магма", так і до нового шифру "Коник".

• Здійснюється побітовий циклічний зсув вліво на 11 біт. Розшифрування здійснюється за цією ж схемою, але з іншим розкладом використання ключів: з 1-го по 8-й раунд розшифрування - у прямому порядку: з 9-го по 32-й раунд розшифрування - у зворотному порядку: У порівнянні з шифром DES у ГОСТ 28147-89 є такі переваги: ​​істотно більш довгий ключ (256 біт проти 56 у шифру DES), атака на який шляхом повного перебору ключової множини на даний момент представляється нездійсненною; простий розклад використання ключа, що спрощує реалізацію алгоритму та підвищує швидкість обчислень. Проектування S-блоків ГОСТ 28147-89. Вочевидь, що схема алгоритму ГОСТ 28147-89 дуже проста. Це означає, що найбільше навантаження на шифрування лягає саме на таблиці замін. Значення таб-
• Панасепко С. П. Алгоритми шифрування: спеціальний довідник. СПб: БХВ-Петер-бург, 2009.
• Kara О. Reflection Attacks on Product Ciphers. URL: http://eprint.iacr.org/2007/043.pdf
• Російський стандарт шифрування: знижена стійкість. URL: http://cryptofaq.ru/index.php/2010-12-23-18-20-21/2010-12-23-18-22-09/90-2011-02-01-07-47- 27
• Ачексєєв Є. К., Смишляєв С. В. ГОСТ 28147-89: «Не поспішай його ховати».

Алгоритм ГОСТ 28147-89

ГОСТ 28147-89 - радянський та російський стандарт симетричного шифрування, введений у 1990 році, також є стандартом СНД. Повна назва - «ГОСТ 28147-89 Системи обробки інформації. Захист криптографічний. Алгоритм криптографічного перетворення».

Рис. 4.

Блоковий шифроалгоритм. При використанні методу шифрування з гамуванням може виконувати функції потокового шифроалгоритму. ГОСТ 28147-89 - блоковий шифр з 256-бітним ключем і 32 циклами перетворення, що оперує 64-бітними блоками. Основа алгоритму шифру – мережа Фейстеля. Виділяють чотири режими роботи ГОСТ 28147-89: простий заміни, гамування, гамування зі зворотним зв'язком, режим вироблення імітівставки.

Переваги алгоритму: безперспективність силової атаки, ефективність реалізації та, відповідно, висока швидкодія на сучасних комп'ютерах, наявність захисту від нав'язування хибних даних (вироблення імітівставки) та однаковий цикл шифрування у всіх чотирьох алгоритмах ГОСТу, більший ключ порівняно з алгоритмом DESX.

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

Переваги IDEA перед аналогами

У програмній реалізації на Intel486SX в порівнянні з DES IDEA вдвічі швидше, що є суттєвим підвищенням швидкості, довжина ключа у IDEA має розмір 128 біт, проти 56 біт у DES, що є гарним покращенням проти повного перебору ключів. Імовірність використання слабких ключів дуже мала і становить 1/2 64 . IDEA швидше за алгоритм ГОСТ 28147-89 (у програмній реалізації на Intel486SX). Використання IDEA у паралельних режимах шифрування на процесорах Pentium III та Pentium MMX дозволяє отримувати високі швидкості. У порівнянні з фіналістами AES, 4-way IDEA лише трохи повільніше, ніж RC6 та Rijndael на Pentium II, але швидше, ніж Twofish та MARS. На Pentium III 4-way IDEA навіть швидше за RC6 і Rijndael. Перевагою також є хороша вивченість та стійкість до загальновідомих засобів криптоаналізу.