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

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

У чому вимірюється продуктивність коду? Оскільки я перший про це заговорив, то по праву першовідкривача його вимірюватиму в 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, а основна маса програмістів не знає асемблера, а якщо знає його правопис, то не розуміє пристрої сучасного процесора. А без цих знань що асемблер, що якийсь там СІ-шарп - не має значення.

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

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

Ніколя Куртуа - «великий та жахливий»

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

У жовтні 2010 року розпочато процес розгляду питання про включення алгоритму ГОСТ 28147-89 до міжнародного стандарту ISO/IEC 18033-3. Вже у травні 2011 року на електронному архіві ePrint з'явилася стаття відомого криптографа Ніколя Куртуа, відзначеного вельми неоднозначним ставленням до нього світової криптографічної спільноти. Публікації Куртуа являють собою сумний приклад маніпулювання поняттями, яке не відкриває жодних нових властивостей об'єкта, що розглядається, але з претензією на сенсацію провокує поширення в некомпетентному середовищі помилкових думок про його дійсні властивості.

Алгебраїчний метод

Міркування Куртуа будуються навколо двох класів методів криптоаналізу: методів алгебри і диференціальних. Розглянемо перший клас методів.

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

Алгебраїчний метод, який експлуатується Куртуа, коротко можна описати так. На першому етапі використовуються такі властивості ГОСТ 28147-89 як існування нерухомої точки для частини шифруючого перетворення, а також так званої точки відображення (reflection point). Завдяки цим властивостям із досить великої кількості пар відкритих-шифрованих текстів вибирається кілька пар, які дозволяють розглядати перетворення не так на 32, а лише на 8 раундах. Другий етап полягає в тому, що за отриманими на першому етапі результатами 8 раундових перетворень будується система нелінійних рівнянь, невідомими в якій є біти ключа. Далі ця система вирішується (це звучить просто, але насправді є трудомісткою частиною методу, тому що система складається з нелінійних рівнянь).

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

Диференціальний метод

Розглянемо другий метод Куртуа, який ґрунтується на диференціальному криптоаналізі.

Загальний метод диференціального криптоаналізу базується на експлуатації властивостей використовуваних криптографічних примітивах нелінійних відображень, пов'язаних з впливом значення ключа на залежності між різницями пар вхідних і пар вихідних значень даних відображень. Наведемо основну ідею диференціального методу криптографічного аналізу блокового шифру. Зазвичай блокові шифри перетворюють вхідні дані поетапно за допомогою деякої кількості про раундових перетворень, причому кожне раундове перетворення використовує не весь ключ, а лише деяку його частину. Розглянемо трохи "усічений" шифр, який відрізняється від вихідного тим, що в ньому немає останнього раунду. Припустимо, що вдалося встановити, що в результаті зашифрування за допомогою такого «усіченого» шифру двох відкритих текстів, які відрізняються в деяких фіксованих позиціях, з великою ймовірністю виходять шифртексти, які також відрізняються в деяких фіксованих позиціях. Ця властивість показує, що «усічений» шифр з великою ймовірністю залишає залежність між деякими відкритими текстами та результатами їхнього зашифрування. Щоб за допомогою цього явного недоліку відновити частину ключа, необхідно мати можливість зашифрувати заздалегідь вибрані відкриті тексти на тому ключі, який ми хочемо відновити (так звана атака з вибраним відкритим текстом). На початку процедури «розкриття ключа» випадково генерується кілька пар відкритих текстів, які у тих самих фіксованих позиціях. Усі тексти зашифровуються за допомогою повного шифру. Отримані пари шифртекстів використовуються для відновлення тих біт ключа, які використовуються в останньому раундовому перетворенні, наступним чином. За допомогою деякого вибраного навмання значення бітів ключа, що шукаються, до всіх шифртекстів застосовується перетворення, зворотне останньому раундовому перетворення. По суті, якщо ми вгадали потрібне значення бітів ключа, ми отримаємо результат роботи «усіченого» шифру, а якщо не вгадали – ми фактично «ще більше зашифруємо дані», що тільки зменшить помічену вище залежність між блоками (відмінність у деяких фіксованих позиціях). Іншими словами, якщо серед результатів такої «дообробки» шифртекстів знайшлося досить багато пар, що відрізняються у відомих нам фіксованих позиціях, це означає, що ми вгадали шукані біти ключа. Інакше таких пар знайдеться значно менше. Оскільки в кожному раунді використовується тільки частина ключа, шуканих бітів (тобто бітів ключа, що використовуються в останньому раунді) не так багато, як бітів у повному ключі і їх можна просто перебрати, повторюючи наведені вище дії. У такому разі ми обов'язково колись натрапимо на правильне значення.

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

Куртуа використовує дещо модифікований варіант диференціального методу. Відразу зазначимо, що свій аналіз Куртуа проводить для S-блоків, відмінних від діючих і запропонованих ISO. У роботі наводяться диференціальні характеристики (ті самі номери, у яких мають відрізнятися блоки) для малого числа раундів. Обґрунтування продовження характеристик на більшу кількість раундів, як водиться, ґрунтується на «фактах». Куртуа висловлює, знову ж таки, нічим, крім його авторитету, не підкріплене припущення, що зміна S-блоків не вплине на стійкість ГОСТ 28147-89 проти його атаки (при цьому з незрозумілих причин S-блоки з 1-го робочого проекту доповнення до стандарту ISO/IEC 18033-3 не розглядалися). Аналіз, проведений авторами статті, показує, що навіть якщо прийняти на віру необґрунтовані «факти» Куртуа та провести аналіз ГОСТ 28147-89 з іншими S-блоками, то атака знову ж таки виявляється не кращою за повний перебір.

Детальний аналіз робіт Куртуа з докладним обгрунтуванням безпідставності всіх тверджень про зниження стійкості російського стандарту було проведено на роботах [ , ].

При цьому абсолютну відсутність акуратності викладок визнає навіть сам Куртуа! Наступний слайд взятий із презентації Куртуа на секції коротких оголошень FSE 2012.

Необхідно відзначити, що роботи Куртуа неодноразово критикувалися також зарубіжними дослідниками. Наприклад, його роботи з побудови атак на алгоритм блокового шифрування AES за допомогою XSL-методу містили ті ж принципові недоробки, що і роботи з аналізу російського стандарту: більшість оцінок трудомісткості з'являється в тексті абсолютно безпідставно і бездоказово - докладну критику можна знайти, наприклад, роботі. Крім того, сам Куртуа визнає повсюдні відмови в публікації його робіт на великих криптографічних конференціях і в визнаних журналах, що рецензуються, залишали йому часто лише можливість виступити на секції коротких оголошень. Про це, наприклад, можна прочитати у розділі 3 роботи. Ось деякі цитати, що наводяться самим Куртуа і пов'язані з його роботами:

• "Я думаю, що аудиторії з Asiacrypt не будуть зайняти ним інтерес". Рецензент Asiacrypt 2011
• «… there is a big, big, big problem: this attack, which is the main contribution of the paper has already been published at FSE'11 (it was even the best paper), …». Рецензент Crypto 2011

Таким чином, професійна частина міжнародної криптографічної громадськості відноситься до якості робіт Куртуа з не меншим сумнівом, ніж, скажімо, до не підтверджених жодними послідовними викладками заяв деяких російських фахівців про їхнє вміння зламувати AES за 2 100 або до чергових "доказів" на дві сторінки про нерівність складних класів P і NP.

Атаки Ісобі та Дінура-Данкельмана-Шаміра

Загальна ідея атак Ісобі () і Дінура-Данкельмана-Шаміра (далі: атака ДДШ) () полягає в побудові для певної (залежної від ключа) вузької множини відкритих текстів еквівалентного на цій множині перетворення, що має більш просту, ніж саме шифруюче перетворення, . У випадку методу Ісобі це безліч таких 64-бітових блоків x, що F 8 -1 (Swap(F 8 (z))) = z де z = F 16 (x), через F 8 (x) і F 16 ( x) позначені перші 8 та перші 16 раундів шифрування ГОСТ 28147-89 відповідно, через Swap - операція обміну місцями половинок 64-байтового слова. При попаданні відкритого тексту в це безліч результату повного 32-раундового перетворення ГОСТ 28147-89 збігається з результатом 16-раундового, що й експлуатується автором атаки. У разі методу ДДШ це безліч таких x, що F 8 (x) = x (нерухлива точка перетворення F 8). Для будь-якого відкритого тексту з цієї множини перетворення ГОСТ 28147-89 працює точно так само, як останні його 8 раундів, що і спрощує аналіз.

Трудомісткість атаки Ісобі становить 2224 операцій зашифрування, атаки ДДШ - 2192 . Однак всі питання про те, чи атаки Ісобі та ДДШ вносять нові обмеження на умови застосування нашого алгоритму, знімає оцінка вимог до обсягу матеріалу, необхідного для проведення кожної з атак: для методу Ісобі потрібно 2 32 пар відкритих і шифрованих текстів, а для методу ДДШ - 2 64 . Обробка таких обсягів матеріалу без зміни ключа апріорно неприйнятна для будь-якого блокового шифру з довжиною блоку 64: на матеріалі об'ємом 2 32 з урахуванням завдання про дні народження (див., наприклад, ), близька до 1/2 ймовірність появи блоків, що повторюються, що надасть порушнику можливість робити за шифрованими текстами деякі висновки про відкриті тексти без визначення ключа. Наявність же 264 пар відкритих і шифрованих текстів, отриманих на одному ключі, фактично дозволяє противнику здійснювати операції зашифрування і розшифрування взагалі без знання цього ключа. Це зумовлено суто комбінаторним властивістю: противник у разі має всієї таблицею шифруючого перетворення. Така ситуація абсолютно неприпустима за жодних розумних експлуатаційних вимог. Наприклад, у КриптоПро CSP є технічне обмеження на обсяг шифрованого (без перетворення ключа) матеріалу в 4 Мб (див. ). Таким чином, сувора заборона на використання ключа на матеріалі такого обсягу властивий будь-якому блоковому шифру з довжиною блоку 64 біта, а отже, атаки Ісобі і ДДШ жодним чином не звужують область використання алгоритму ГОСТ 28147-89 при збереженні максимально можливої ​​стійкості 2256 .

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

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

Зазначимо, що певні недбалості в оцінках середньої трудомісткості присутні й у роботі Дінура, Данкельмана та Шаміра. Так, при побудові атаки не приділяється належної уваги наступному моменту: для істотної частки ключів безліч відкритих текстів x, таких, що F 8 (x) = x є порожнім: нерухомих точок у 8 раундів перетворення може просто не бути. Існування нерухомих точок залежить також від вибору вузлів заміни. Таким чином, атака застосовується тільки при певних вузлах заміни та ключах.

Варто згадати також ще одну роботу з атакою на ГОСТ 28147-89. У лютому 2012 року на електронному архіві ePrint міжнародної криптографічної асоціації з'явилася оновлена ​​версія статті (від листопада 2011 року), яка містила нову атаку на ГОСТ 28147-89. Характеристики представленої атаки такі: обсяг матеріалу - 232 (як у Ісобі), а трудомісткість - 2192 (як у ДДШ). Таким чином, ця атака покращувала рекордну за часом атаку ДДШ за обсягом матеріалу з 264 до 232 . Зазначимо окремо, що автори чесно навели усі викладки з обґрунтуванням трудомісткості та обсягу матеріалу. Через 9 місяців у наведених викладках було знайдено принципову помилку, і з листопада 2012 року оновлена ​​версія статті в електронному архіві вже не містить жодних результатів щодо вітчизняного алгоритму.

Атаки у припущенні, що порушник знає «щось» про ключі

Зауважимо насамкінець, що у літературі також є кілька робіт (див., наприклад, і ), присвячених атакам на ГОСТ 28147-89 у так званої моделі зі зв'язаними ключами. Дана модель у своїй основі містить припущення про можливість порушника отримувати доступ для аналізу не просто до пар відкритих і шифрованих за допомогою шуканого ключа текстів, але також до пар відкритих і шифрованих текстів, отриманих за допомогою (також невідомих) ключів, що відрізняються від відомим регулярним (наприклад, у фіксованих бітових позиціях). У даній моделі дійсно вдається отримати цікаві результати про ГОСТ 28147-89, проте в цій моделі не менш сильні результати вдається отримувати і про, наприклад, стандарті AES, що отримав найбільш широке поширення в сучасних мережах загального користування (див., наприклад, ). Зауважимо, що умови для проведення таких атак виникають при використанні шифру в деякому протоколі. Не можна не відзначити, що результати такого роду, хоч і становлять безперечний академічний інтерес з погляду вивчення властивостей криптографічних перетворень, але фактично не належать до практики. Наприклад, всі сертифіковані ФСБ Росії засоби криптографічного захисту інформації виконують найсуворіші вимоги щодо схем вироблення ключів шифрування (див., наприклад, ). Як зазначено в результатах проведеного аналізу, за наявності 18 пов'язаних ключів і 2 10 пар блоків відкритого і шифрованого тексту трудомісткість повного розкриття закритого ключа, при ймовірності успіху 1-10 -4 , дійсно становить 2 26 . Однак при дотриманні згаданих вище вимог з вироблення ключового матеріалу ймовірність виявлення таких ключів дорівнює 2 -4352, тобто в 24096 разів менше, ніж якщо просто спробувати вгадати секретний ключ з першої спроби.

До робіт, що належать до моделі зі зв'язаними ключами, відноситься також і робота, що наробила в 2010 році багато шуму в російських електронних виданнях, які не страждають від звички уважно перевіряти матеріал у процесі гонки за сенсаціями. Результати, представлені в ній, не були підкріплені якимось суворим обґрунтуванням, зате містили гучні заяви про можливість зламувати державний стандарт Російської Федерації на слабкому ноутбуці за лічені секунди - загалом, стаття була написана в кращих традиціях Ніколя Куртуа. Але, незважаючи на цілком очевидну хоч трохи знайомому з основними принципами науковості публікацій читачеві безпідставність статті, саме для заспокоєння російської громадськості після роботи Рудським був написаний докладний і докладний текст, що містить всебічний аналіз цієї недостатності. У статті з назвою "Про нульову практичну значущість роботи "Key recovery attack on full GOST block cipher with zero time and memory"" наводиться обґрунтування того, що середня трудомісткість наведеного в методу не менше, ніж трудомісткість повного перебору.

Сухий залишок: яка стійкість практично?

На закінчення наведемо таблицю, що містить дані про всі відомі міжнародному криптографічного співтовариства результати строго описаних та обґрунтованих атак на ГОСТ 28147-89. Зазначимо, що складність наводиться в операціях зашифрування алгоритму ГОСТ 28147-89, а пам'ять та матеріал вказані в блоках алгоритму (64 біти = 8 байт).

Атака	Трудомісткість	Пам'ять	Необхідний матеріал
Ісобі	2 224	2 64	2 32
Дінур-Данкельман-Шамір, FP, 2DMitM	2 192	2 36	2 64
Дінур-Данкельман-Шамір, FP, low-memory	2 204	2 19	2 64
	2 224	2 36	2 32
Дінур-Данкельман-Шамір, Reflection, 2DMitM	2 236	2 19	2 32
Повний перебір	2 256	1	4
Кількість наносекунд із виникнення Всесвіту	2 89

Незважаючи на досить масштабний цикл досліджень у галузі стійкості алгоритму ГОСТ 28147-89, на даний момент не відомо жодної атаки, умови для здійснення якої були б досяжними при супутніх довжині блоку в 64 біт експлуатаційних вимогах. Випливають з параметрів шифру (бітова довжина ключа, бітова довжина блоку) обмеження на обсяг матеріалу, який може бути оброблений на одному ключі, істотно суворіше за мінімальний обсяг, який необхідний для здійснення будь-якої з відомих на даний момент атак. Отже, при виконанні існуючих експлуатаційних вимог жоден із запропонованих на даний момент методів криптоаналізу ГОСТ 28147-89 не дозволяє визначати ключ із меншою трудомісткістю повного перебору.

У нашій країні встановлено єдиний алгоритм криптографічного подання даних для систем обробки інформації в мережах ЕОМ, окремих обчислювальних комплексів та ЕОМ, що визначається ГОСТ 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, його використання та програмна реалізація для комп'ютерів платформи Intel x86.

Андрій Винокуров

Опис алгоритму.

Терміни та позначення.

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

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

Елементи даних у цій статті позначаються великими латинськими літерами з похилим зображенням (наприклад, X). Через | X| позначається розмір елемента даних Xу бітах. Таким чином, якщо інтерпретувати елемент даних Xяк ціле невід'ємне число, можна записати таку нерівність:.

Якщо елемент даних складається з кількох елементів меншого розміру, цей факт позначається так: X=(X 0 ,X 1 ,…,X n –1)=X 0 ||X 1 ||…||X n-1. Процедура об'єднання кількох елементів даних один називається конкатенацією даних та позначається символом «||». Звісно, ​​для розмірів елементів даних має виконуватися таке співвідношення: | X|=|X 0 |+|X 1 |+…+|X n-1 |. При заданні складних елементів даних та операції конкатенації складові елементи даних перераховуються у порядку зростання старшинства. Іншими словами, якщо інтерпретувати складовий елемент і всі елементи даних, що входять до нього, як цілі числа без знака, то можна записати таку рівність:

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

X=(x 0 ,x 1 ,…,x n –1)=x 0 +2 1 · x 1 +…+2 n-1 · x n –1 .

Таким чином, якщо ви звернули увагу, для ГОСТу прийнято т.зв. "little-endian" нумерація розрядів, тобто. всередині багаторозрядних слів даних окремі двійкові розряди та їх групи з меншими номерами менш значущі. Про це прямо йдеться у пункті 1.3 стандарту: «При складанні та циклічному зрушенні двійкових векторів старшими розрядами вважаються розряди накопичувачів з великими номерами». Далі, пункти стандарту 1.4, 2.1.1 та інші наказують починати заповнення даними регістрів-накопичувачів віртуального пристрою шифрування з молодших, тобто. менш значних розрядів. Такий самий порядок нумерації прийнятий у мікропроцесорній архітектурі Intel x86, саме тому при програмній реалізації шифру на даній архітектурі ніяких додаткових перестановок розрядів усередині слів даних не потрібно.

Якщо над елементами даних виконується деяка операція, має логічний сенс, то передбачається, що операція виконується над відповідними бітами елементів. Іншими словами A B=(a 0 b 0 ,a 1 b 1 ,…,a n –1 b n-1), де n=|A|=|B|, а символом «» позначається довільна бінарна логічна операція; як правило, мається на увазі операція виключає або , вона ж - операція підсумовування за модулем 2:

Логіка побудови шифру та структура ключової інформації ГОСТу.

Якщо уважно вивчити оригінал ГОСТ 28147-89, можна побачити, що він містить опис алгоритмів кількох рівнів. На верхньому знаходяться практичні алгоритми, призначені для шифрування масивів даних і вироблення для них імітівставки. Усі вони спираються на три алгоритми нижчого рівня, які називаються в тексті ГОСТу циклами . Ці фундаментальні алгоритми згадуються у цій статті як базові цикли , щоб відрізняти їх від інших циклів. Вони мають такі назви та позначення, останні наведені у дужках і зміст їх буде пояснений пізніше:

• цикл зашифрування (32-З);
• цикл розшифрування (32-Р);
• цикл вироблення імітівставки (16-З).

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

Таким чином, щоб розібратися у ГОСТі, треба зрозуміти три наступні речі:

• що таке основний крок криптоперетворення;
• як із основних кроків складаються базові цикли;
• як із трьох базових циклів складаються всі практичні алгоритми ДСТУ.

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

Основний крок криптоперетворення.

Основний крок криптоперетворення за своєю суттю є оператором, що визначає перетворення 64-бітового блоку даних. Додатковим параметром цього оператора є 32-бітовий блок, як який використовується якийсь елемент ключа. Схема алгоритму основного кроку наведено малюнку 1.

Малюнок 1. Схема основного кроку криптоперетворення алгоритму ГОСТ 28147-89.

Нижче наведено пояснення до алгоритму основного кроку:

Крок 0

• N- 64-бітовий блок даних, що перетворюється, в ході виконання кроку його молодша ( N 1) та старша ( N 2) частини обробляються окремі 32-битовые цілі числа без знака. Таким чином, можна записати N=(N 1 ,N 2).
• X- 32-бітовий елемент ключа;

Крок 1

Додавання з ключем. Молодша половина блоку, що перетворюється складається по модулю 2 32 з використовуваним на кроці елементом ключа, результат передається на наступний крок;

Крок 2

Побічна заміна. 32-бітове значення, отримане на попередньому кроці, інтерпретується як масив із восьми 4-бітових блоків коду: S=(S 0 , S 1 , S 2 , S 3 , S 4 , S 5 , S 6 , S 7), причому S 0 містить 4 наймолодших, а S 7 – 4 найстарші біти S.

Далі значення кожного з восьми блоків замінюється новим, яке вибирається за таблицею замін наступним чином: значення блоку S iзмінюється на S i-Тий по порядку елемент (нумерація з нуля) i-того вузла заміни (тобто. i-того рядка таблиці замін, нумерація також з нуля). Іншими словами, як заміна для значення блоку вибирається елемент з таблиці замін з номером рядка, рівним номеру блоку, що замінюється, і номером стовпця, рівним значенню замінного блоку як 4-бітового цілого неотрицательного числа. Звідси стає зрозумілим розмір таблиці замін: число рядків у ній дорівнює числу 4-бітових елементів у 32-бітовому блоці даних, тобто восьми, а число стовпців дорівнює числу різних значень 4-бітового блоку даних, що дорівнює як відомо 2 4 шістнадцяти.

Крок 3

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

Крок 4

Побітове додавання: значення, отримане на кроці 3, побітно складається по модулю 2 зі старшою половиною блоку, що перетворюється.

Крок 5

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

Крок 6

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

Основні цикли криптографічних перетворень.

Як зазначено на початку цієї статті, ДЕРЖСТАНДАРТ відноситься до класу блокових шифрів, тобто одиницею обробки інформації в ньому є блок даних. Отже, цілком логічно очікувати, що в ньому будуть визначені алгоритми для криптографічних перетворень, тобто для зашифрування, розшифрування та обліку в контрольній комбінації одного блоку даних. Саме ці алгоритми і називаються базовими циклами ГОСТу, що підкреслює їхнє фундаментальне значення для побудови цього шифру.

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

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

Цикл зашифрування 32-З:

K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 .

Малюнок 2а. Схема циклу зашифрування 32-З

Цикл розшифрування 32-Р:

K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 ,K 7 ,K 6 ,K 5 ,K 4 ,K 3 ,K 2 ,K 1 ,K 0 .

Малюнок 2б. Схема циклу розшифрування 32-Р

Цикл вироблення імітівставки 16-З:

K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 ,K 0 ,K 1 ,K 2 ,K 3 ,K 4 ,K 5 ,K 6 ,K 7 .

Малюнок 2в. Схема циклу вироблення імітівставки 16-З.

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

Цикл розшифрування має бути зворотним циклу зашифрування, тобто послідовне застосування цих двох циклів до довільного блоку має дати в результаті вихідний блок, що відображається таким співвідношенням: Ц 32-Р ( Ц 32-З ( T))=T, де T- Довільний 64-бітовий блок даних, Ц X ( T) – результат виконання циклу Xнад блоком даних T. Для виконання цієї умови для алгоритмів, подібних до ГОСТу, необхідно і достатньо, щоб порядок використання ключових елементів відповідними циклами був взаємно зворотним. У справедливості записаної умови для даного випадку легко переконатися, порівнявши наведені вище послідовності для циклів 32-З і 32-Р. Зі сказаного випливає одне цікаве наслідок: властивість циклу бути зворотним іншому циклу є взаємним, тобто цикл 32-З є зворотним по відношенню до циклу 32-Р. Іншими словами, зашифрування блоку даних теоретично може бути виконане за допомогою циклу розшифрування, у цьому випадку розшифрування блоку даних має бути виконане циклом зашифрування. З двох взаємно зворотних циклів будь-який може бути використаний для зашифрування, тоді другий повинен бути використаний для розшифрування даних, однак стандарт ГОСТ28147-89 закріплює ролі за циклами і не надає користувачеві права вибору цього питання.

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

Схеми базових циклів наведені малюнки 2а-в. Кожен з них приймає як аргумент і повертає як результат 64-бітовий блок даних, позначений на схемах N. Символ Крок( N,X) означає виконання основного кроку криптоперетворення для блоку даних Nз використанням ключового елемента X. Між циклами шифрування та обчислення імітівставки є ще одна відмінність, не згадана вище: наприкінці базових циклів шифрування старша та молодша частина блоку результату змінюються місцями, це необхідно для їхньої взаємної оборотності.

Основні режими шифрування.

ГОСТ 28147-89 передбачає три наступні режими шифрування даних:

• проста заміна,
• гамування,
• гамування зі зворотним зв'язком,

і один додатковий режим вироблення імітівставки.

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

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

Tо, Tш – масиви відповідно відкритих та зашифрованих даних;

, – i- ті по порядку 64-бітові блоки відповідно відкритих та зашифрованих даних: , , Останній блок може бути неповним: ;

n- Число 64-бітових блоків в масиві даних;

Ц X – функція перетворення 64-бітового блоку даних алгоритму базового циклу «X».

Тепер опишемо основні режими шифрування:

Проста заміна.

Зашифрування у цьому режимі полягає у застосуванні циклу 32-З до блоків відкритих даних, розшифрування – циклу 32-Р до блоків зашифрованих даних. Це найбільш простий режими, 64-бітові блоки даних обробляються в ньому незалежно один від одного. Схеми алгоритмів зашифрування та розшифрування в режимі простої заміни наведені на рисунках 3а і б відповідно, вони тривіальні і не потребують коментарів.

Малюнок. 3а. Алгоритм зашифрування даних у режимі простої заміни

Малюнок. 3б. Алгоритм розшифрування даних у режимі простої заміни

Розмір масиву відкритих або зашифрованих даних, що піддається відповідно до зашифрування або розшифрування, повинен бути кратний 64 бітам: | T про |=| T ш | = 64 · n після виконання операції розмір отриманого масиву даних не змінюється.

Режим шифрування простою заміною має такі особливості:

• Так як блоки даних шифруються незалежно один від одного і від їхньої позиції в масиві даних, при зашифруванні двох однакових блоків відкритого тексту виходять однакові блоки шифртексту і навпаки. Зазначене властивість дозволить криптоаналитику зробити висновок про тотожність блоків вихідних даних, якщо масиві зашифрованих даних йому зустрілися ідентичні блоки, що є неприпустимим для серйозного шифру.
• Якщо довжина масиву даних, що шифрується, не кратна 8 байтам або 64 бітам, виникає проблема, чим і як доповнювати останній неповний блок даних масиву до повних 64 біт. Це завдання не таке просте, як здається на перший погляд. Очевидні рішення типу «доповнити неповний блок нульовими бітами» або, більш загально, «доповнити неповний блок фіксованою комбінацією нульових і одиничних бітів» можуть за певних умов дати в руки криптоаналітика можливість методами перебору визначити вміст цього неповного блоку, і цей факт означає зниження стійкості шифру. Крім того, довжина шифртексту при цьому зміниться, збільшившись до найближчого цілого, кратного 64 біт, що часто буває небажаним.

На перший погляд, перелічені вище особливості роблять практично неможливим використання режиму простої заміни, адже він може застосовуватися тільки для шифрування масивів даних з розміром кратним 64 біт, що не містить 64-бітових блоків, що повторюються. Здається, що з будь-яких реальних даних гарантувати виконання зазначених умов неможливо. Це майже так, але є один дуже важливий виняток: згадайте, що розмір ключа становить 32 байти, а розмір таблиці замін – 64 байти. Крім того, наявність 8-байтових блоків, що повторюються, в ключі або таблиці замін буде говорити про їх дуже погану якість, тому в реальних ключових елементах такого повторення бути не може. Таким чином, ми з'ясували, що режим простої заміни цілком підходить для шифрування ключової інформації, тим більше що інші режими для цієї мети менш зручні, оскільки вимагають наявності додаткового синхронізуючого елемента даних – синхропосилання (див. наступний розділ). Наша здогад вірна, ГОСТ пропонує використовувати режим простої заміни виключно для шифрування ключових даних.

Гамування.

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

Тепер перейдемо безпосередньо до опису режиму гамування. Гамма для цього режиму виходить наступним чином: за допомогою деякого алгоритмічного рекурентного генератора послідовності чисел (РГПЧ) виробляються 64-бітові блоки даних, які піддаються перетворенню по циклу 32-З, тобто зашифрування в режимі простої заміни, в результаті виходять блоки гами. Завдяки тому, що накладання і зняття гами здійснюється за допомогою однієї і тієї ж операції побитового виключає або алгоритми зашифрування і розшифрування в режимі гамування ідентичні, їх загальна схема наведена на малюнку 4.

РГПЛ, що використовується для вироблення гами, є рекурентною функцією: – елементи рекурентної послідовності, f- Функція перетворення. Отже, неминуче виникає питання про його ініціалізацію, тобто про елемент Насправді цей елемент даних є параметром алгоритму для режимів гамування, на схемах він позначений як S, і називається у криптографії синхропосилкою , а в нашому ГОСТі – початковим заповненням одного з регістрів шифрувача. З певних міркувань розробники ДСТУ вирішили використовувати для ініціалізації РГПЛ не безпосередньо синхропосилку, а результат її перетворення за циклом 32-З: . Послідовність елементів, що виробляються РГПЛ, цілком залежить від початкового заповнення, тобто елементи цієї послідовності є функцією свого номера і початкового заповнення РГПЛ: де f i(X)=f(f i –1 (X)), f 0 (X)=X. З урахуванням перетворення за алгоритмом простої заміни додається ще й залежність від ключа:

де Г i– i-Тий елемент гами, K- Ключ.

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

Тепер докладно розглянемо РГПЛ, що використовується у ГОСТі для створення елементів гами. Насамперед, слід зазначити, що до нього не пред'являються вимоги забезпечення будь-яких статистичних характеристик послідовності чисел, що виробляється. РГПЛ спроектований розробниками ГОСТу, виходячи з необхідності виконання наступних умов:

• період повторення послідовності чисел, що виробляється РГПЛ, не повинен сильно (у відсотковому відношенні) відрізнятися від максимально можливого при заданому розмірі блоку значення 264;
• сусідні значення, що виробляються РГПЛ, повинні відрізнятися один від одного в кожному байті, інакше завдання криптоаналітика буде спрощено;
• РГПЧ має бути досить просто реалізований як апаратно, так і програмно на найбільш поширених типах процесорів, більшість з яких, як відомо, мають розрядність 32 біти.

З перелічених принципів, творці ГОСТу спроектували дуже зручний РГПЛ, має такі характеристики:

Де C 0 =1010101 16 ;

Де C 1 =1010104 16 ;

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

Друге вираження потребує коментарів, оскільки у тексті ГОСТу наведено щось інше: , з тим самим значенням константи C 1 . Але далі у тексті стандарту дається коментар, що, виявляється, під операцією взяття залишку за модулем 2 32 -1 тамрозуміється не те саме, що і в математиці. Відмінність полягає в тому, що згідно з ДСТУ (2 32 -1) mod(2 32 –1)=(2 32 –1), а чи не 0. Насправді, це спрощує реалізацію формули, а математично коректне вираз неї наведено вище.

• період повторення послідовності для молодшої частини становить 232, для старшої частини 232-1, для всієї послідовності період становить 232 (232-1), доказ цього факту, дуже нескладне, отримаєте самі. Перша формула з двох реалізується за одну команду, друга, незважаючи на її громіздкість, за дві команди на всіх сучасних 32-розрядних процесорах - першою командою йде звичайне додавання по модулю 2 32 із запам'ятовуванням біта переносу, а друга команда додає біт переносу до отриманого значенню.

Схему алгоритму шифрування в режимі гамування наведено на малюнку 4, нижче викладено пояснення до схеми:

Малюнок 4. Алгоритм зашифрування (розшифрування) даних як гаммування.

Крок 0

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

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

Крок 1

Початкове перетворення синхропосилання, яке виконується для її «рандомізації», тобто для усунення статистичних закономірностей, присутніх в ній, результат використовується як початкове заповнення РГПЛ;

Крок 2

Один крок роботи РГПЛ, що реалізує його рекурентний алгоритм. У ході цього кроку старша ( S 1) та молодша ( S 0) частини послідовності даних виробляються незалежно друг від друга;

Крок 3

Гамування. Черговий 64-бітовий елемент, вироблений РГПЧ, піддається процедурі зашифрування за циклом 32-З, результат використовується як елемент гами для зашифрування (розшифрування) чергового блоку відкритих (зашифрованих) даних того ж розміру.

Крок 4

Результат роботи алгоритму – зашифрований (розшифрований) масив даних.

Нижче наведено особливості гамування як режиму шифрування:

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

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

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

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

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

де позначає інвертоване по відношенню до tзначення біта ().

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

Гамування зі зворотним зв'язком.

Даний режим дуже схожий на режим гамування і відрізняється від нього тільки способом вироблення елементів гами - черговий елемент гами виробляється як результат перетворення за циклом 32-З попереднього блоку зашифрованих даних, а для зашифрування першого блоку масиву даних елемент гами виробляється як результат перетворення по тому ж циклу синхропосилки. Цим досягається зачеплення блоків – кожен блок шифртексту в цьому режимі залежить від відповідного та всіх попередніх блоків відкритого тексту. Тому цей режим іноді називається гамуванням з зачепленням блоків . На стійкість шифру факт зачеплення блоків не впливає.

Схема алгоритмів за- та розшифрування в режимі гамування зі зворотним зв'язком наведена на малюнку 5 і через свою простоту коментарів не потребує.

Малюнок 5. Алгоритм зашифрування (розшифрування) даних у режимі гамування зі зворотним зв'язком.

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

Гамування;

Гамування зі зворотним зв'язком;

Якщо режимі звичайного гамування зміни у певних бітах шифртексту впливають лише з відповідні біти відкритого тексту, то режимі гаммування зі зворотним зв'язком картина дещо складніше. Як видно з відповідного рівняння, при розшифруванні блоку даних у режимі гамування зі зворотним зв'язком блок відкритих даних залежить від відповідного і попереднього блоків зашифрованих даних. Тому, якщо внести спотворення в зашифрований блок, то після розшифрування спотвореними виявляться два блоки відкритих даних - відповідний і наступний за ним, причому спотворення в першому випадку будуть носити той же характер, що і в режимі гамування, а в другому - як в режимі простий заміни. Іншими словами, у відповідному блоці відкритих даних спотвореними виявляться ті ж біти, що і в блоці шифрованих даних, а в наступному блоці відкритих даних всі біти незалежно один від одного з ймовірністю 1 / 2 змінять свої значення.

Вироблення імітівставки до масиву даних.

У попередніх розділах ми обговорили вплив спотворення шифрованих даних на відповідні відкриті дані. Ми встановили, що при розшифруванні в режимі простої заміни відповідний блок відкритих даних виявляється непередбачуваним спотвореним чином, а при розшифруванні блоку в режимі гамування зміни передбачувані. У режимі гамування зі зворотним зв'язком спотвореними виявляються два блоки, один передбачуваним, а інший непередбачуваним чином. Чи означає це, що з погляду захисту від нав'язування хибних даних режим гамування є поганим, а режими простої заміни та гамування зі зворотним зв'язком хорошими? - Ні в якому разі. При аналізі даної ситуації необхідно врахувати те, що непередбачувані зміни в розшифрованому блоці даних можуть бути виявлені тільки у разі надмірності цих даних, причому, чим більший ступінь надмірності, тим вірогідніше виявлення спотворення. Дуже велика надмірність має місце, наприклад, для текстів на природних та штучних мовах, у цьому випадку факт спотворення виявляється практично неминуче. Однак в інших випадках, наприклад, при перекручуванні стислих оцифрованих звукових образів, ми отримаємо просто інший образ, який зможе сприйняти наше вухо. Спотворення в цьому випадку залишиться невиявленим, якщо, звичайно, немає апріорної інформації про характер звуку. Висновок тут такий: оскільки здатність деяких режимів шифрування виявляти спотворення, внесені в шифровані дані, істотно спирається на наявність і ступінь надмірності даних, що шифруються, ця здатність не є іманентною властивістю відповідних режимів і не може розглядатися як їх гідність.

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

• обчислення імітівставки для заданого відкритого масиву інформації;
• підбір відкритих даних під задану імітівставку;

Схема алгоритму вироблення імітівставки наведено малюнку 6.

Малюнок 6. Алгоритм вироблення імітівставки для масиву даних.

Як імітівставка береться частина блоку, отриманого на виході, зазвичай - 32 його молодших біта. При виборі розміру імітівставки треба брати до уваги, що ймовірність успішного нав'язування хибних даних дорівнює величині 2 - | I | одну спробу підбору, якщо у розпорядженні зловмисника немає ефективнішого методу підбору, ніж просте вгадування. При використанні імітівставки розміром 32 біти ця ймовірність дорівнює

Обговорення криптографічних алгоритмів ДСТУ.

Криптографічна стійкість Держстандарту.

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

• чи можна взагалі розкрити цей шифр;
• якщо так, то наскільки це важко зробити практично;

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

Усі сучасні криптосистеми побудовані за принципом Кірхгоффа, тобто секретність шифрованих повідомлень визначається секретністю ключа. Це означає, що навіть якщо сам алгоритм шифрування відомий криптоаналітику, той, проте, не в змозі розшифрувати повідомлення, якщо не має у своєму розпорядженні відповідного ключа. Шифр вважається добре спроектованим, якщо немає способу розкрити його ефективнішим способом, ніж повним перебором у всьому ключовому просторі, тобто. за всіма можливими значеннями ключа. ДЕРЖСТАНДАРТ, ймовірно, відповідає цьому принципу – за роки інтенсивних досліджень не було запропоновано жодного результативного способу його криптоаналізу. У плані стійкості він набагато порядків перевершує колишній американський стандарт шифрування, DES.

У ГОСТі використовується 256-бітовий ключ і обсяг ключового простору становить 2256 . На жодному з існуючих в даний час або передбачуваних до реалізації в недалекому майбутньому електронному пристрої не можна підібрати ключ за час, менший за багато сотень років. Ця величина стала фактичним стандартом розміру ключа для симетричних криптоалгоритмів у наші дні, так, новий стандарт шифрування США також його підтримує. Колишній американський стандарт, DES з його реальним розміром ключа в 56 біт і обсягом ключового простору всього 2 56 вже не є досить стійким у світлі можливостей сучасних обчислювальних засобів. Це було продемонстровано наприкінці 90-х кількома успішними спробами злому DES перебірним шляхом. Крім того, DES виявився схильний до спеціальних способів криптоаналізу, таких як диференціальний і лінійний. У зв'язку з цим DES може представляти швидше дослідний чи науковий, ніж практичний інтерес. У 1998 році його криптографічна слабкість була визнана офіційно – національний інститут стандартів США рекомендував використовувати триразове шифрування по DES. А наприкінці 2001 року було офіційно затверджено новий стандарт шифрування США, AES, побудований на інших принципах та вільний від недоліків свого попередника.

Зауваження щодо архітектури ГОСТу.

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

Алгоритми «основних кроків криптоперетворення» для шифрів, подібних до ГОСТу, побудовані ідентичним чином, і ця архітектура називається збалансована мережа Файстеля (balanced Feistel network) на ім'я людини, яка вперше запропонувала її. Схема перетворення даних одному циклі, або, як його прийнято називати, раунді , наведено малюнку 7.

Малюнок 7. Зміст основного кроку криптоперетворення для блокових шифрів, подібних до ГОСТу.

На вхід основного кроку подається блок парного розміру, старша та молодша половини якого обробляються окремо один від одного. У ході перетворення молодша половина блоку міститься на місце старшої, а старша, скомбінована за допомогою операції побітового виключає або з результатом обчислення деякої функції, на місце молодшої. Ця функція приймає як аргумент молодшу половину блоку і елемент ключової інформації ( X), є змістовною частиною шифру і називається його функцією шифрування . З різних міркувань виявилося вигідно розділити блок, що шифрується, на дві однакові за розміром частини: | N 1 |=|N 2 | – саме цей факт відбиває слово «збалансована» у назві архітектури. Втім, нестримні мережі, що шифрують, також використовуються час від часу, хоча і не так часто, як збалансовані. Крім того, міркування стійкості шифру вимагають, щоб розмір ключового елемента не був меншим за розмір половини блоку: у ГОСТі всі три розміри дорівнюють 32 бітам .

Якщо застосувати сказане до схеми основного кроку алгоритму ДЕРЖСТАНДАРТ, стане очевидним, що блоки 1,2,3 алгоритму (див. рис. 1) визначають обчислення його функції шифрування, а блоки 4 і 5 задають формування вихідного блоку основного кроку виходячи з вмісту вхідного блоку та значення функції шифрування. Докладніше про архітектури сучасних блокових шифрів із секретним ключем можна прочитати в класичних роботах, або, в адаптованій формі, в моїх роботах.

У попередньому розділі ми вже порівняли DES та ГОСТ за стійкістю, тепер ми порівняємо їх за функціональним змістом та зручністю реалізації. У циклах шифрування ДЕРЖСТАНДАРТ основний крок повторюється 32 рази, для DES ця величина дорівнює 16. Однак сама функція шифрування ГОСТу істотно простіше аналогічної функції DES, в якій присутня безліч нерегулярних бітових перестановок. Ці операції дуже неефективно реалізуються на сучасних неспеціалізованих процесорах. ГОСТ не містить подібних операцій, тому він значно зручніший для програмної реалізації.

Жодна з розглянутих автором реалізацій DESа для платформи Intel x86 не досягає навіть половини продуктивності запропонованої вашої уваги в цій статті реалізації ГОСТу незважаючи на вдвічі коротший цикл. Все сказане вище свідчить про те, що розробники ДСТУ врахували як позитивні, так і негативні сторони DESа, а також більш реально оцінили поточні та перспективні можливості криптоаналізу. Втім, брати DES за основу порівняно швидкодії реалізацій шифрів не актуально. У нового стандарту шифрування США справи з ефективністю йдуть набагато краще - при такому ж як у ДСТУ розмір ключа в 256 біт AES працює швидше за нього приблизно на 14% - це якщо порівнювати за кількістю «елементарних операцій». Крім того, ГОСТ практично не вдається розпаралелити, а у AES можливостей у цьому плані набагато більше. На деяких архітектурах ця перевага AES може бути меншою, на інших – більшою. Так, на процесорі Intel Pentium воно сягає 28%. Подробиці можна знайти у .

Вимоги до якості ключової інформації та джерела ключів.

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

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

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

Ключ

Ключ повинен бути масивом статистично незалежних бітів, що приймають з рівною ймовірністю значення 0 і 1. Не можна повністю виключити при цьому, що деякі конкретні значення ключа можуть виявитися слабкими, тобто шифр може не забезпечувати заданий рівень стійкості у разі їх використання. Однак, імовірно, частка таких значень у загальній масі всіх можливих ключів дуже мала. Принаймні, інтенсивні дослідження шифру досі не виявили жодного такого ключа для жодної з відомих (тобто запропонованих ФАПСІ) таблиць замін. Тому ключі, вироблені за допомогою деякого датчика випадкових чисел, будуть якісними з ймовірністю, що відрізняється від одиниці на мізерно малу величину. Якщо ж ключі виробляються за допомогою генератора псевдовипадкових чисел, то генератор, що використовується, повинен забезпечувати зазначені вище статистичні характеристики, і, крім того, володіти високою криптостійкістю, - не меншою, ніж у самого ГОСТу. Іншими словами, завдання визначення відсутніх членів послідовності елементів, що виробляється генератором, не повинна бути простішою, ніж завдання розкриття шифру. Крім того, для відбракування ключів із поганими статистичними характеристиками можуть бути використані різні статистичні критерії. Насправді зазвичай вистачає двох критеріїв – для перевірки рівноймовірного розподілу бітів ключа між значеннями 0 і 1 зазвичай використовується критерій Пірсона («хі квадрат»), а для перевірки незалежності бітів ключа – критерій серій. Про згадані критерії можна прочитати у підручниках або довідниках з математичної статистики.

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

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

Таблиця замін

Таблиця замін є довготривалим ключовим елементом, тобто діє протягом більш тривалого терміну, ніж окремий ключ. Передбачається, що вона є спільною всім вузлів шифрування у межах однієї системи криптографічного захисту. Навіть при порушенні конфіденційності таблиці замін стійкість шифру залишається надзвичайно високою і не знижується нижче за допустиму межу. Тому немає особливої ​​потреби тримати таблицю в секреті, і в більшості комерційних застосувань Держстандарту так воно й робиться. З іншого боку, таблиця замін є критично важливим елементом забезпечення стійкості всього шифру. Вибір неналежної таблиці може призвести до того, що шифр легко розкриватиметься відомими методами криптоаналізу. Критерії вироблення вузлів замін – таємниця за сімома печатками та ФАПСІ навряд чи їй поділиться з громадськістю в найближчому майбутньому. Зрештою, для того, щоб сказати, чи є дана конкретна таблиця замін хорошою чи поганою, необхідно провести величезний обсяг робіт – багато тисяч чоловіко- та машино-годин. Одного разу вибрана та використовувана таблиця підлягає заміні в тому і лише в тому випадку, якщо шифр з її використанням виявився вразливим до того чи іншого виду криптоаналізу. Тому найкращим вибором для рядового користувача шифру буде взяти одну з кількох таблиць, які стали оприлюдненими. Наприклад, із стандарту на хеш-функцію, вона ж «центробанківська»; відомості про ці таблиці можна знайти у відкритому друку та навіть в інтернеті, якщо добре пошукати.

Для тих, хто не звик йти легкими шляхами, нижче наведено загальну схему отримання якісних таблиць:

1. За допомогою тієї чи іншої методики виробляєте комплект із восьми вузлів замін із гарантованими характеристиками нелінійності. Таких методик є кілька, одна з них – використання так званих бент-функцій.
2. Перевіряєте виконання найпростіших «критеріїв якості» – наприклад, опублікованих для вузлів заміни DES. Ось ще кілька загальних міркувань щодо цього: Кожен вузол замін може бути описаний четвіркою логічних функцій від чотирьох логічних аргументів. Якщо ці функції записані в мінімальній формі(Тобто з мінімально можливою довжиною виразу) виявляться недостатньо складними, такий вузол заміни відкидається. Крім того, окремі функції в межах усієї таблиці замін повинні відрізнятися один від одного достатньою мірою. На цьому етапі відсіваються багато свідомо неякісних таблиць.
3. Для шифру з вибраними вами таблицями будуєте різні моделі раунду, що відповідають різним видам криптоаналізу, та вимірюєте відповідні «профільні» характеристики. Так, для лінійного криптоаналізу будуєте лінійний статистичний аналог раунду шифрування та обчислюєте "профільну" характеристику - показник нелінійності. Якщо вона виявляється недостатньою, таблиця замін відкидається.
4. Нарешті, використовуючи результати попереднього пункту, піддаєте шифр з обраною вами таблицею інтенсивним дослідженням – спробі криптоаналізу всіма відомими методами. Саме цей етап є найбільш складним та трудомістким. Але якщо він зроблений якісно, ​​то з високим ступенем ймовірності можна констатувати, що шифр із обраними вами таблицями не буде розкритий простими смертними, і, не виключено, виявиться не по зубах спецслужбам.

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

Щодо таблиці замін необхідно відзначити ще один цікавий факт. Для оборотності циклів шифрування «32-З» і «32-Р» не потрібно, щоб вузли замін були перестановками чисел від 0 до 15. Все працює навіть у тому випадку, якщо у вузлі замін є елементи, що повторюються, і заміна, яка визначається таким вузлом , Необоротна, - проте в цьому випадку знижується стійкість шифру. Чому це саме так, не розглядається у цій статті, проте у самому факті переконатися нескладно. Для цього достатньо спробувати спочатку зашифрувати, а потім розшифрувати блок даних, використовуючи таку «неповноцінну» таблицю замін, вузли якої містять значення, що повторюються.

Варіації на тему ГОСТу

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

Як зробити в цьому та аналогічному йому випадках, щоб збільшити швидкодію шифрування? Відповідь лежить на поверхні – використовувати модифікацію шифру з меншою кількістю основних кроків (раундів) у базових циклах. У скільки разів ми зменшуємо кількість раундів шифрування, у стільки ж разів зростає швидкодія. Зазначеної зміни можна досягти двома шляхами – зменшенням довжини ключа та зменшенням числа «циклів перегляду» ключа. Згадайте, що кількість основних кроків у базових циклах шифрування дорівнює N=n·m, де n- Число 32-бітових елементів у ключі, m- Число циклів використання ключових елементів, у стандарті n=8, m=4. Можна зменшити будь-яке із цих чисел, але найпростіший варіант – зменшувати довжину ключа, не чіпаючи схеми його використання.

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

Що стосується стійкості шифру до злому «екстенсивними» методами, тобто до «перебірної» атаки, то тут все більш менш ясно: ключ розміром 64 біта знаходиться десь на межі доступності цьому виду атаки, шифр з ключем 96 біт і вище ( пам'ятайте, що ключ повинен містити ціле число 32-бітових елементів) цілком стійкий проти нього. Дійсно, кілька років тому колишній стандарт шифрування США, DES, був неодноразово зламаний перебірним шляхом, – спочатку його зламала обчислювальна мережа, організована з урахуванням глобальної мережі Інтернет, та був – спеціалізована, тобто. сконструйована спеціально для цього обчислювальна машина. Приймемо, що стандартний варіант ДСТУ при програмній реалізації на сучасних процесорах працює вчетверо швидше за DES. Тоді 8-раундовий «редукований ГОСТ» працюватиме у 16 ​​разів швидше за DES. Приймемо також, що за час, що минув з моменту злому DES, продуктивність обчислювальної техніки відповідно до закону Мура зросла вчетверо. Отримуємо в результаті, що зараз перевірка одного 64-бітового ключа для «редукованого ГОСТу» з вісьмома циклами здійснюється в 64 рази швидше, ніж свого часу виконувалася перевірка одного ключа DES. Таким чином, перевага такого варіанту ГОСТу перед DES за трудомісткістю перебірної атаки скорочується з 264–56 = 28 = 256 до 256 / 64 = 4 разів. Погодьтеся, це дуже ілюзорна відмінність, майже нічого.

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

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

З іншого боку, ДЕРЖСТАНДАРТ проектувався з великим запасом міцності і на сьогоднішній день стійкий до всіх відомих видів криптоаналізу, включаючи диференціальний та лінійний. Стосовно ЛКА це означає, що для його успішного проведення потрібно більше пар «відкритий блок – зашифрований блок», ніж «існує в природі», тобто більше 2 64 . З урахуванням сказаного вище це означає, що для успішного ЛКА 16-раундового ГОСТу потрібно не менше блоків або 235 байтів або 32 Гбайта даних, а для 8-раундового - не менше блоків або 2 19 байтів або 0.5 Мбайт.

Висновки з усього, сказаного вище, наведено в наступній таблиці, що узагальнює характеристики редукованих варіантів ГОСТу.

Число раундів	Розмір ключа, біт	Індекс швидко-дії	Ймовірні характеристики шифру (дуже груба оцінка)
24	192	1,33	Стійкий до більшості відомих видів КА або перебувати на межі стійкості. Практична реалізація КА неможлива через високі вимоги до вихідних даних та трудомісткості.
16	128	2	Теоретично нестійкий до деяких видів криптоаналізу, проте їхня практична реалізація в більшості випадків утруднена через високі вимоги до вихідних даних та трудомісткості.
12	95	2,67	Нестійкий до деяких відомих видів криптоаналізу, проте підходить для забезпечення таємності невеликих обсягів даних (до десятків-сот Кбайт) на короткий термін.
8	64	4	Нестійкий до деяких відомих видів криптоаналізу, проте підходить для забезпечення таємності невеликих обсягів даних (до десятків Кбайт) на короткий термін.

Два останні варіанти, з 12 і 8 раундами, здатні забезпечити вельми обмежений у часі захист. Їх використання виправдане лише у завданнях, де потрібна лише короткострокова секретність даних, що закриваються, близько декількох годин. Можлива сфера застосування цих слабких варіантів шифру – закриття UDP-трафіку електронних біржових торгових систем. У цьому випадку кожен пакет даних (datagram, середня D з абревіатури UDP) шифрується на окремому 64-бітовому ключі, а сам ключ шифрується на сеансовому ключі (ключі, область дії якого - один сеанс зв'язку між двома комп'ютерами) і передається разом з даними.

Перш ніж закінчити з редукованими варіантами ГОСТу скажу, що всі наведені вище міркування носять спекулятивний характер. Стандарт забезпечує стійкість лише для одного, 32-раундового варіанта. І ніхто не може дати вам гарантій, що стійкість редукованих варіантів шифру до злому буде змінюватися вказаним вище чином. Якщо ви все ж таки зважилися їх використовувати у своїх розробках, пам'ятайте, що ви ступили на дуже хиткі ґрунти, які можуть у будь-який момент піти з-під ваших ніг. Якщо питання швидкості шифрування є для вас критичними, може, варто подумати про використання більш швидкого шифру або потужнішого комп'ютера? Ще одне міркування, з якого це варто зробити, полягає в тому, що ослаблені варіанти ГОСТу будуть максимально чутливі до якості вузлів заміни, що використовуються.

У питання, що розглядається, є і зворотний бік. Що якщо швидкість шифрування некритична, а вимоги до стійкості дуже жорсткі? Підвищити стійкість ДСТУ можна двома шляхами – умовно назвемо їх «екстенсивний» та «інтенсивний». Перший – це ні що інше, як просте збільшення числа раундів шифрування. Мені не зовсім зрозуміло, навіщо це може реально знадобитися, адже вітчизняний стандарт без цього забезпечує необхідну стійкість. Втім, якщо ви страждаєте на параної більше необхідного рівня (а всі «захисники інформації» просто зобов'язані нею страждати, це умова профпридатності така, питання тільки в тяжкості випадку:), це допоможе вам трохи заспокоїтися. Якщо ви не впевнені в цьому КГБ-шному шифрі або використовуваної вами таблиці замін, просто подвоїть, вчетверіть, і т.д. число раундів – кратність виберіть, виходячи з тяжкості вашого випадку. Зазначений підхід дозволяє реально збільшити стійкість шифру – якщо раніше криптоаналіз був просто неможливим, то тепер він неможливий у квадраті!

Хитрішим і цікавішим є питання, а чи можна збільшити стійкість шифру, не змінюючи кількості та структури основних кроків шифрування. Як не дивно, відповідь на нього позитивна, хоча ми знову ступаємо на хиткій грунт спекуляцій. Річ у тім, що у ГОСТі основному етапі перетворення передбачається виконання заміни 4 на 4 біт, але в практиці (мова про це ще попереду) всі програмні реалізації виконують заміну побайтно, тобто. 8 на 8 біт - так робиться з міркувань ефективності. Якщо відразу спроектувати таку заміну як 8-бітову, то ми суттєво покращимо характеристики одного раунду. По-перше, збільшиться «дифузійна» характеристика або показник «лавинності» – один біт вихідних даних та/або ключа впливатиме на більшу кількість біт результату. По-друге, для великих за розміром вузлів заміни можна отримати більш низькі диференціальну та лінійну характеристики, зменшивши тим самим схильність до шифру однойменним видам криптоаналізу. Особливо актуально це для редукованих циклів ГОСТу, а для 8 та 12-раундових варіантів такий крок просто необхідний. Це трохи компенсує втрату стійкості в них від зменшення кількості раундів. Що ускладнює використання цього прийому - так це те, що конструювати подібні «збільшені» вузли заміни вам доведеться самостійно. А також те, що більші вузли взагалі конструювати помітно важче, ніж менші за розміром.

Нестандартне використання стандарту.

Безумовно, основне призначення криптоалгоритмів ГОСТ – це шифрування та імітозахист даних. Однак їм можна знайти й інші застосування, пов'язані, звісно, ​​із захистом інформації. Коротко розповімо про них:

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

• Як зазначалося вище, гаму можна використовувати як «сировину» вироблення ключів. Для цього потрібно лише отримати відрізок гами потрібної довжини – 32 байти. У такий спосіб ключі можна виготовляти в міру необхідності і їх не треба буде зберігати, якщо такий ключ знадобиться повторно, буде досить легко його виробити знову. Треба тільки буде згадати, на якому ключі він був вироблений вихідно, яка використовувалася синхропосилання і з якого байта виробленої гами починався ключ. Вся інформація, крім використаного ключа, є несекретною. Даний підхід дозволить легко контролювати досить складну та розгалужену систему ключів, використовуючи лише один «майстер-ключ».
• Аналогічно попередньому, гаму можна використовувати як вихідну «сировину» для вироблення паролів. Тут може виникнути питання, навіщо взагалі потрібно їх генерувати, чи не простіше при необхідності їх просто вигадувати. Неспроможність такого підходу була наочно продемонстрована серією інцидентів у комп'ютерних мережах, найбільшим з яких був добовий параліч інтернету в листопаді 1988 року, викликаний «хробаком Морріса». Одним із способів проникнення зловмисної програми на комп'ютер був підбір паролів: програма намагалася увійти в систему, послідовно перебираючи паролі зі свого внутрішнього списку в кілька сотень, причому в значній частині випадків їй це вдавалося зробити. Фантазія людини з вигадування паролів виявилася дуже бідною. Саме тому в тих організаціях, де безпеці приділяється належна увага, паролі генерує та роздає користувачам системний адміністратор з безпеки. Вироблення паролів трохи складніше, ніж вироблення ключів, тому що при цьому "сиру" двійкову гаму необхідно перетворити до символьного вигляду, а не просто "нарізати" на шматки. Крім того, окремі значення, можливо, доведеться відкинути, щоб забезпечити рівну можливість появи всіх символів алфавіту в паролі.
• Ще один спосіб використання криптографічної гами – гарантоване затирання даних на магнітних носіях. Річ у тім, що навіть за перезапису інформації на магнітному носії залишаються сліди попередніх даних, які може відновити відповідна експертиза. Для знищення цих слідів такий перезапис треба виконати багаторазово. Виявилося, що потрібно перезаписувати інформацію на носій менше разів, якщо за такої процедури використовувати випадкові або псевдовипадкові дані, які залишаться невідомими експертам, які намагаються відновити затерту інформацію. Гамма шифру тут буде дуже доречним.

2. Не тільки криптографічна гамма, а й саме криптографічне перетворення може бути використане для потреб, безпосередньо не пов'язаних із шифруванням:

• Ми знаємо, що один із таких варіантів використання ГОСТу – вироблення імітівставки для масивів даних. Однак на базі будь-якого блочного шифру, і ГОСТу в тому числі, досить легко побудувати схему обчислення односторонньої хеш-функції, яка також називається в літературі MDC, що в різних джерелах розшифровується як код виявлення змін / маніпуляцій (M odification/ M anipulation D etection C ode) або дайджест повідомлення (M essage D igest C ode). Перше розшифрування з'явилося в літературі набагато раніше, друге, коротше, я думаю, придумали ті, кому виявилося не під силу запам'ятати першу:), – це був жарт. MDC може безпосередньо використовуватися в системах імітозахисту в якості аналога імітівставки, що не залежить, однак, від секретного ключа. Крім того, MDC широко використовується в схемах електронно-цифрового підпису (ЕЦП), адже більшість таких схем сконструйовано таким способом, що зручно підписувати блок даних фіксованого розміру. Як відомо, на базі обговорюваного стандарту ГОСТ 28147-89 побудовано стандарт Російської Федерації на обчислення односторонньої хеш-функції ГОСТ Р34.11-94.
• Менш відомо, що на базі будь-якого блочного шифру, і ГОСТу у тому числі, може бути побудована цілком функціональна схема ЕЦП, із секретним ключем підпису та відкритою перевірочною комбінацією. З ряду причин ця схема не набула широкого практичного поширення, проте в окремих випадках досі може розглядатися як вельми приваблива альтернатива домінуючим нині у світі «математичним» схемам ЕЦП.

Література

Системи опрацювання інформації. Захист криптографічний. Алгоритм криптографічного перетворення ГОСТ 28147-89. Держ. Ком. СРСР за стандартами, М., 1989. ftp://ftp.wtc-ural.ru/pub/ru.crypt/GOST-28147
Шеннон Клод. Математична теорія секретних систем. У збірнику «Роботи з теорії інформації та кібернетиці», М., ІЛ, 1963, с. 333-369. http://www.enlight.ru/crypto/articles/shannon/shann__i.htm
Зображення щодо Federal Information Processing Standard (FIPS) 197, Advanced Encryption Standard (AES), Federal Register Vol. 66, No. 235 / Thursday, December 6, 2001 / Notices, pp 63369-63371. http://csrc.nist.gov/encryption/aes/
Файстель Хорст. Криптографія та комп'ютерна безпека. Переклад А.Винокурова за виданням Horst Feistel. Cryptography and Computer Privacy, Scientific American, May 1973, Vol. 228, No. 5, pp. 15-23. http://www.enlight.ru/crypto/articles/feistel/feist_i.htm
Шнайєр Брюс. Прикладна криптографія. 2-ге вид. Протоколи, алгоритми та вихідні тексти мовою Сі., М., «Тріумф», 2002 http://www.ssl.stu.neva.ru/psw/crypto/appl_ukr/appl_cryp.htm
Menezes Alfred, van Oorschot Paul, Vanstone Scott. Handbook of applied cryptography. ttp://www.cacr.math.uwaterloo.ca/hac/
Винокуров Андрій. Як влаштований блоковий шифр? Рукопис. http://www.enlight.ru/crypto/articles/vinokurov/blcyph_i.htm
Винокуров Андрій. Випуски криптографії для електронного журналу iNFUSED BYTES online. http://www.enlight.ru/crypto/articles/ib/ib.htm
Винокуров Андрій, Применко Едуард. Текст доповіді «Про програмну реалізацію стандартів шифрування РФ і США», конференція з інформатизації, Москва, МІФІ, 28-29 січня 2001р. Опубліковано у матеріалах конференції.
Інформаційна технологія. Криптографічний захист інформації. Функція хешування ГОСТ Р34.11-94, Держстандарт РФ, М., 1994.

Цей алгоритм є обов'язковим для застосування як алгоритму шифрування в державних організаціях РФ та ряді комерційних.

Опис алгоритму

Схема алгоритму показано на рис. 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 операцій шифрування. Як видно, дана атака практично непотрібна для реального розкриття алгоритму.