Головна → Налаштування Wi-Fi Вітчизняний стандарт шифрування даних. Вітчизняний стандарт шифрування даних Блочний шифр гост 28147 89

Вітчизняний стандарт шифрування даних. Вітчизняний стандарт шифрування даних Блочний шифр гост 28147 89

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

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

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

Рис. 2.21.

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

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

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

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

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

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

2. Таблична заміна. Після накладення ключа подблок R i розбивається на вісім частин але 4 біта, значення кожної з яких окремо замінюється відповідно до своєї таблицею заміни (S-блоком). Всього використовується вісім S-блоків - S 0, S, S 2, S 3, S 4, S 5, S 6, S 7. Кожен S-блок алгоритму ГОСТ 28147-89 являє собою вектор (одновимірний масив) з ^ елементами, пронумерованими від 0 до 15. Значеннями S-блоку є 4-бітові числа, тобто цілі числа від 0 до 15.

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

Приклад 2.6.

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

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

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

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

Таблиця 2.16

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вступ

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

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

теоретичний мінімум

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

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

Практика

4.1 Реалізація основного кроку криптоперетворень
4.2 Збільшення швидкодії алгоритму
5.
6. Список використаної літератури
7. Подяки.

Вступ.

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

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

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

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

Історія розвитку блокових шифрів асоціюється з початком 70-х років, коли компанія IBM усвідомивши необхідність захисту інформації при передачі даних по каналах зв'язку ЕОМ, приступила до виконання своєї програми наукових досліджень, присвячених захисту інформації в електронних мережах, в тому числі і криптографії.

Групу дослідників - розробників фірми IBM, яка приступила до дослідження систем шифрування із симетричною схемою використання ключів, очолив доктор Хорст Файстеля.

2.1 Мережі Файстеля

Запропонована Файстеля архітектура нового методу шифрування в класичній літературі отримала назву «Архітектура Файстеля», але на даний момент в російській і зарубіжній літературі використовується більш усталений термін - «мережа Файстеля» або Feistel`s NetWork. Надалі по даній архітектурі був побудований шифр «Люцифер» - який пізніше був опублікований і викликав нову хвилю інтересу до криптографії в цілому.

Ідея архітектури «мережі Файстеля» полягає в наступному: вхідний потік інформації розбивається на блоки розміром в n бітів, де n парне число. Кожен блок ділиться на дві частини - L і R, далі ці частини подаються в ітеративний блочний шифр, в якому результат j-го етапу визначається результатом попереднього етапу j-1! Сказане можна проілюструвати на прикладі:

Рис. 1

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

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

Для того щоб ідея мереж Файстеля була остаточна ясна, розглянемо найпростіший випадок зображений на рис. 1, Де в функції А - виступить операції "mod 2" ( "xor"), але це найпростішийвипадок, в більш серйозній ситуації, наприклад приховування інформації державної важливості функція А може бути більш складною (скільки я бачив функція А дійсно буває дуже складною):

Вихідні дані:

L \u003d 1110b, R \u003d 0101, K \u003d 1111b

отримати шифрограму

(R + K) mod 2 4 \u003d Smod, Smod \u003d 0100b
(Smod + L) mod 2 \u003d Sxor, Sxor \u003d 1010b
L \u003d R, R \u003d Sxor

L \u003d 0101b, R \u003d 1010b

Пояснимо наші дії:

Ця операція додавання по mod 2 4. На практиці така операція зводиться до простого додаванню, де ми повинні скласти два числа і проігнорувати перенесення в 5й розряд. Так як, якщо проставити над розрядами двійкового представлення числа проставити показники ступеня, над п'ятим розрядом якраз буде показник чотири, поглянемо на малюнок нижче, де зображені дії нашої операції:

Рис. 2

Тут я стрілкою вказав на показники ступеня, як видно, результат повинен був вийти 10100, але так як при операції mod 2 4 ігнорується перенос, ми отримуємо 0100.

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

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

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

2.2 Блоковий шифр ГОСТ 28147-89

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

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

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

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

3.1 Ключова інформація

Як я вже говорив вище, в шифруванні даних активну участь беруть:

3.1.1. Ключ - це послідовність восьми елементів розміром в 32 біта кожен. Далі будемо позначати символом К, а елементи з яких він складається - k1, k2, k3, k4, k5, k6, k7, k8.

3.1.2 Таблиця замін - матриця з восьми рядків і шістнадцяти стовпців, в подальшому - Hij. Кожен елемент на перетині рядка i та стовпця j займає 4 біта.

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

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

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

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

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

Після того як ви розбили інформацію на блоки, слід розбити ключ на елементи:

K \u003d k1, k2, k3, k4, k5, k6, k7, k8

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

Базові цикли мають, як би це сказати, маркування: n - m. Де n - кількість основних кроків криптоперетворень в базовому циклі, а m - це «тип» базового циклу, тобто про що йде мова, про «З» ашіфровиваніі або «Р» асшіфровиваніі даних.

Базовий цикл шифрування 32-З складається з 32-х основних кроків криптоперетворень. У функцію реалізує дії кроку подають блок N і елемент ключа До причому, перший крок відбувається з к1, другий над отриманим результатом з елементом к2 і т.д. за такою схемою:

k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8k8, k7, k6, k5, k4, k3, k2, k1

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

k1, k2, k3, k4, k5, k6, k7, k8, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1

Практика.

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

Вихідні дані:

Візьмемо блок інформації N \u003d 0102030405060708h, тут частини L і R рівні:

L \u003d 01020304h, R \u003d 05060708h, візьмемо ключ:

K \u003d ' as28zw37 q8397342ui238e2t wqm2ewp1 '(це ASCII - коди, для того, щоб подивитися шістнадцяткове представлення, можна відкрити цей файл в режим перегляду в Total Commander натиснувши на клавішу « F3»І далі клавішу« 3 »). У цьому ключі значення елементів будуть:

k1 \u003d 'as28', k2 \u003d 'zw37', k3 \u003d 'q839', k4 \u003d '7342'

k5 \u003d 'ui23', k6 \u003d '8e2t', k7 \u003d 'wqm2', k8 \u003d 'ewp1'

Також візьмемо таку таблицю замін:

Рис. 3

Тут рядки нумеруються від 0 до 7, стовпці від 0 до F.

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

Використовуючи «Вихідні дані», необхідно отримати результат дії основного кроку криптоперетворень.

Вибираємо частина R \u003d 05060708h і елемент ключа k1 \u003d 'as28', в шістнадцятковому вигляді елемент ключа буде виглядати так: 61733238h. Тепер же робимо операцію підсумовування по mod 2 32:

Рис. 4

Як видно на малюнку у нас не відбулося перенесення в 33 біт позначений червоним кольором і з показником ступеня « 32 ». А якби у нас були б інші значення R і елемента ключа - це цілком могло б статися, і тоді б ми його проігнорували, і в подальшому використовували тільки біти, помічені жовтим кольором.

Таку операцію я виконую командою асемблера add:

; eax \u003d R, ebx \u003d 'as28'

Результат цієї операції Smod \u003d 66793940h

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

МАЛЮНОК НЕ ЗБЕРЕЖЕНО

Рис. 5

Я постарався наочно уявити елементи Smod на малюнку, але все одно поясню:

s0 \u003d 0, s1 \u003d 4, s2 \u003d 9 і т.д.

Тепер починаючи з молодшого елемента s0, виробляємо заміну. Згадуючи пункт « 3.2 Основний крок криптоперетворень»I - рядок, s i - стовпець, шукаємо в нульовий рядку і нульовому стовпці значення:

рис.6

Таким чином, поточне значення Smod, що не 6679394 0 h, а 6679394 5 h.

Приступаємо замінювати s1, тобто четвірку. Використовуючи перший рядок і четвертий стовпець (s1 \u003d 4!). Дивимося на малюнок:

Рис. 7

Тепер уже значення Smod, що не 667939 4 5h, 667939 2 5h. Я припускаю, що тепер алгоритм заміни читачеві зрозумілий, і я можу сказати, що після кінцевий результат Ssimple матиме таке значення - 11e10325h.

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

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

Рис. 8

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

Тепер же залишається частина L нашого блоку інформації поXORіть зі значенням Srol. Я беру калькулятор від w2k sp4 і отримую Sxor \u003d 091b2b8bh.
Ця дія підсумкове і ми просто присвоюємо, чисти R значення частини L, а частина L инициализируем значенням Sxor.

Кінцевий результат:

L \u003d 091b2b8bh, R \u003d 01020304h

4.2 Збільшення швидкодії алгоритму

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

Коли я реалізовував алгоритм шифрування в своїй програмі, я поступив таким чином:

Вибрав частину блоку L в регістр eax, а R в edx.
У регістр esi ініціалізувати адресою розширеного ключа, про це нижче.
У регістр ebx привласнював значення адреси розширеної таблиці замін, про це теж нижче
Передавав інформацію пунктів 1,2, 3 в функцію базового циклу 32 - З або 32 - Р, в залежності від ситуації.

Якщо подивитися на схему подачі елементів ключа в пункті « Базові цикли: "32-З", "32-Р"», То наш ключ для базового циклу 32 - З можна представити в наступному:

До 32-З \u003d

'As28', 'zw37', 'q839', '7342', 'ui23', '8e2t', 'wqm2', 'ewp1',

'Ewp1', 'wqm2', '8e2t', 'ui23', '7342', 'q839', 'zw37', 'as28'

Тобто з початку йдуть k1, k2, k3, k4, k5, k6, k7, k8 - ‘ as28 ','zw37 ','q839 ',' 7342 ','ui23 ',' 8e2t ','wqm2 ','ewp1 ' три рази ця послідовність повторюється. Потім елементи йдуть в зворотному порядку, тобто .: k8, k7, k6, k5, k4, k3, k2, k1 - 'Ewp1', 'wqm2', '8e2t', 'ui23', '7342', 'q839', 'zw37', 'as28'.

Я заздалегідь розташував в масиві елементи в тому порядку, як вони повинні подаватися в 32 - З. Тим самим я збільшив пам'ять, необхідну під ключ, але позбавив себе від деяких процесів мислення, які мені були не потрібні, і збільшив швидкість роботи алгоритму, за рахунок зменшення часу звернення до пам'яті! Тут я описав тільки ключ для 32 - З, для циклу 32 - Р я вчинив аналогічно, але використовуючи іншу схему подачі елементів, яку я теж описував в пункті « Базові цикли: "32-З", "32-Р».

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

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

Наприклад, нам потрібно було замінити, число 66793940h. Представлю його в наступному вигляді:

МАЛЮНОК НЕ ЗБЕРЕЖЕНО

Рис. 9

Тепер якщо взяти елементи s1, s0, тобто молодший байт, то результат функції заміни буде дорівнює 25h! Почитавши статтю Андрія Винокурова, яку я привів в пункті « Список використаної літератури», Ви дійсно виявите, що якщо взяти два рядки можна отримати масив, що дозволяє швидко знаходити елементи заміни за допомогою команди асемблера xlat.Кажуть можна і іншим способом більш швидким, але Андрій Винокуров витратив на дослідження швидких алгоритмів для реалізації ГОСТу близько чотирьох років! Думаю, не варто винаходити велосипед, коли він уже є.

Отже, про масиві:

Візьмемо дві перші рядки нульову і першу, створимо масив на 256 байт. Тепер спостерігаємо одну особливість, що якщо треба перетворити 00h, то результат буде 75h (спираємося на рис.3) - ставимо це значення в масив на зміщення 00h. Беремо значення 01h, результат функції замін 79h, кладемо його в масив на зміщення 01 і так далі до 0FFh, яке нам дасть 0FCh, яке ми покладемо в масив по зміщення 0FFh. Ось ми і отримали розширену таблицю замін для першої групи рядків: першої і нульовий. Але ще є три групи: друга стор.2, стор.3, третя стор.4, стор. 5, четверта стор.6, стор.7. З цим трьома групами чинимо тим же способом, що і з першою. Результат - розширена таблиця замін!

Тепер можна реалізувати алгоритм, який буде робити заміну. Для цього беремо вихідні коди, які виклав Андрій Винокуров на своїй сторінці, дивись « Список використаної літератури».

lea ebx, extented_table_simple

mov eax, [покласти число яке потрібно замінити]

add ebx, 100h; перехід до двох наступних вузлів

sub ebx, 300h; щоб в подальшому ebx показував на таблицю

Тепер ще одна особливість, попередніми діями ми не тільки замінили, але і зрушили число на 8 біт вліво! Нам залишається тільки зрушити число ще на 3 біти вліво:

і ми отримуємо результат операції rol eax, 11!

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

Вимоги до ключової інформації.

Як сказано в статті Андрія Винокурова ключ вибирають за двома критеріями:

- критерій равновероятного розподілу бітів між значеннями 1 і 0. Зазвичай в якості критерію равновероятного розподілу бітів - виступає критерій Пірсона ( «хі-квадрат»).

Це означає ключем, в принципі може будь-яке число. Тобто при формуванні чергового біта ключа ймовірність його ініціалізації одиницею або нулем 50/50!

Прошу зауважити, що ключ з восьми елементів, кожен по 32 біта, таким чином всього в ключі 32 * 8 \u003d 256 бітів і кількість можливих ключів 2 256! Тебе це не вражає? 🙂

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

Якщо ми подивимося на наш ключ, який я навів у пункті « 4.1 Реалізація основного кроку криптоперетворень», То ви помітите, що справедлива наступна запис:

Рис. 10

Однією фразою значення k 1 не повинно повторитися не в k 2, не в будь-якому іншому елементі ключа.

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

Тепер про вибір таблиці замін:

Тепер же поговоримо про те, як правильно вибрати таблицю замін. Основна вимога до вибору таблиць замін - це явище «неповторяемости» елементів, кожен з яких розміром в 4 біта. Як ви вже бачили вище, кожен рядок таблиці замін складається з значень 0h, 1h, 2h, 3h, ..., 0fh. Так ось основна вимога свідчить про те, що в кожному рядку є значення 0h, 1h, 2h, ..., 0fh і кожне таке значення в одному екземплярі. Наприклад, послідовність:

1 2 3 4 5 6 7 8 9 A B C D E F

Цілком відповідає цій вимозі, але все ж! Таку послідовність як рядки вибирати не рекомендується. Бо якщо ви подасте значення на вхід функції, яка спирається на такий рядок, то на виході ви отримаєте таке ж значення! Не вірите? Тоді візьміть число 332DA43Fh і вісім таких рядків, як таблиці замін. Проведіть операцію заміни, і запевняю вас, на виході ви отримаєте число 332DA43Fh! Тобто таке ж, що ви подали на вхід операції! А це не є ознакою хорошого тону при шифруванні, та й чи було? 🙂

Це було одне вимога, наступний критерій говорить про те, що - кожен біт вихідного блоку повинен бути статистично незалежний від кожного біта вхідного блоку!

Як це виглядає простіше? А ось як, наприклад, ми вибрали з наведеного вище числа елемент s0 \u003d 0Fh, 01111b. Імовірність того, що ми зараз замінимо перший біт одиницею або нулем дорівнює 0,5! Імовірність заміни другого, третього і четвертого біта, кожен біт, розглядаємо окремо, одиницями або нулями теж дорівнює 0, 5. При виборі s1 \u003d 0Eh, ймовірність того, що ми нульовий біт, а це «0», замінимо нулем або одиницею теж дорівнює - 0,5! Таким чином, згідно з цим критерієм між заміною нульових бітів елементів s0, s1 немає ніякої закономірності! Так, ви могли замінити одиницями, але ви також могли поставити і нулі. 🙂

Для оцінки таблиці за цим критерієм можна побудувати таблицю коефіцієнтів кореляції, розраховані за формулою:

- якщо p \u003d 1, то значення біта j на виході дорівнює значенню біта i на вході при будь-яких комбінаціях біт на вході;

- якщо p \u003d -1, то значення біта j на виході завжди є інверсією вхідного біта i;

- якщо p \u003d 0, то вихідний біт j з однаковою ймовірністю приймає значення 0 і 1 при будь-якому фіксованому значенні вхідної біта i.

Візьмемо приклад одного рядка:

D	B	4	1	3	F	5	9	0	A	E	7	6	8	2	C

Розкладемо на «складові»:

Розрахуємо один коефіцієнт за формулою наведеною вище. Щоб простіше було зрозуміти, як це робиться, поясню більш детально:

- беремо 0-й біт 0-ого числа (0) на вході і 0-й біт 0-ого числа на виході (1) проводимо операцію 0 XOR 1 \u003d 1.

- беремо 0-й біт 1-ого числа (1) на вході і 0-й біт 1-ого числа на виході (1) проводимо операцію 1 XOR 1 \u003d 0.

- беремо 0-й біт 2-ої числа (0) на вході і 0-й біт 2-ої числа на виході (0) проводимо операцію 0 XOR 0 \u003d 0.

- беремо 0-й біт 3-ого числа (1) на вході і 0-й біт 3-ого числа на виході (1) проводимо операцію 1 XOR 1 \u003d 0.

Провівши послідовно операції XOR в такій послідовності, підраховуємо кількість всіх ненульових значень, отримуємо значення 6. Звідси P 00 \u003d 1 (6/2 4-1) \u003d 0,25. Отже, з'ясувалося, що значення біта 0 на виході дорівнює значенню біта 0 на вході в 4-х випадках з 16-ти;

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

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

	Вхід
вихід		0	1	2	3
	0	-0,25	0,00	0,00	0,00
	1	0,00	1,00	0,00	0,00
	2	0,00	0,00	1,00	0,00
	3	0,00	0,00	0,00	-0,50

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

09 0D 03 0E-06 02 05 08-0A 07 00 04-0C 01 0F 0B

00 05 0A 07-03 08 0F 0C-0E 0B 04 09-0D 06 01 02

06 0B 0F 00-0C 01 02 0D-08 07 09 04-05 0A 03 0E

04 0E 00 09-0B 01 0F 06-03 0D 07 0A-0C 02 08 05

04 02 08 0E-05 0F 03 09-0B 01 0D 07-0A 0C 06 00

07 03 09 0C-08 00 06 0F-0E 04 01 0A-0D 0B 02 05

06 0F 03 08-0D 04 0A 01-09 02 05 0C-00 0B 0E 07

0C 06 08 01-03 09 07 0E-0B 05 0F 02-04 0A 00 0D

04 0B 09 06-0E 01 00 0F-0A 05 03 0C-0D 02 07 08

00 0E 0F 01-07 08 09 06-04 0B 0A 05-03 0D 0C 02

0F 09 01 07-04 0A 08 06-0E 00 02 0C-05 03 0B 0D

0A 03 04 01-05 0C 0B 0E-08 06 0F 0D-07 09 00 02

0B 06 0F 01-04 0A 08 05-00 0D 0C 02-07 09 03 0E

0C 03 02 08-0D 06 0B 05-07 09 04 0F-0A 00 01 0E

02 0B 0F 04-09 00 06 0D-05 0E 01 08-0C 07 0A 03

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

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

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

для комп'ютерів платформи Intel x86.

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

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

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

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

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

Ross N. Williams:

Елементарне керівництво по CRC алгоритмам виявлення помилок

Викладена на сайті www.wasm.ru.

Подяки.

Хотілося б висловити подяку всім відвідувачам форуму www.wasm.ru. Але особливо б хотілося б подякувати ChS, який зараз відомий, як SteelRat, він допоміг мені зрозуміти такі речі, чого я б, напевно, ніколи б не зрозумів, а так само допомогу при написанні пункту: « Вимоги до ключової інформації», Основною частина даного пункту була написана ним. Також глибоко вдячний співробітнику КДТУ ім. А.Н. Туполєва Анікіну Ігорю В'ячеславовичу і гріх було б не відзначити Кріса Касперски, за те, що він є і Volodya / wasm.ru за його настанови. Ох, і дістається мені від нього :). Так само хочу відзначити Sega-Zero / Callipso зате, що доніс до мого розуму деякі математичні нетрі.

Це, мабуть, все, що я хотів би сказати вам.

Буду, вдячний за критику або питання, пов'язані з цією статтею або просто поради. Мої контактні дані: [Email protected], ICQ - 337310594.

З повагою Evil`s Interrupt.

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

Завдання з інформаційної безпеки

Завдання на контрольну роботу 2

Приклади виконання завдань 3

Додаток А. Алгоритм шифрування ГОСТ 28147-89 10

Додаток Б. Символи кирилиці

(Альтернативна кодова таблиця ASCII) 13

Додаток В. Блок підстановки в алгоритмі шифрування

ГОСТ 28147-89 14

Додаток Г. Алгоритм шифрування RSA 15

Додаток Д. Таблиця простих чисел 17

Додаток Е. Функція хешування 18

Додаток Ж. Електронний цифровий підпис 19

Питання до заліку 21

література 22

Завдання №1. Шифр Цезаря.

Використовуючи шифр Цезаря, зашифруйте свої дані: Прізвище Ім'я По батькові.

Завдання №2. Алгоритм шифрування гост 28147-89.

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

Завдання №3. Алгоритм шифрування rsa.

Згенеруйте відкритий і закритий ключі в алгоритмі шифрування RSA, обравши прості числа p і q з першої сотні. Зашифруйте повідомлення, що складається з ваших ініціалів: ПІБ.

Завдання №4. Функція хешування.

Знайти хеш-образ своєї Прізвища, використовуючи хеш-функцію, гдеn \u003d pq.

Завдання №5. Електронний цифровий підпис.

Приклади виконання завдань

Завдання №1. Шифр Цезаря. Використовуючи шифр Цезаря, зашифруйте свої дані: Прізвище Ім'я По батькові.

Початковий текст:

« КОЗИНА ГАЛИНА ЛЕОНІДІВНА »

Використовуємо алфавіт, що містить 33 літери і пробіл, що стоїть після букви Я:

АБВГДЕЁЖЗІЙКЛМНОПРСТУФХЦЧШЩ'ИЬЕЮЯ пробіл

Ключем в шифрі Цезаря є число 3. Кожна буква в початковому тексті зсувається за алфавітом на 3 позиції. Таким чином, отримуємо:

Початковий текст					ЛЕОНИДОВНА
зашифрований текст					ОЗСРЛЖСЕРГ

Завдання №2. Алгоритм шифрування ГОСТ 28147-89.Виконайте перший цикл алгоритму шифрування ГОСТ 28147-89 в режимі простої заміни. Для отримання 64 біт вихідного тексту використовуйте 8 перших букв зі своїх даних: Прізвища Імені Вітчизни. Для отримання ключа (256 біт) використовують текст, що складається з 32 букв. Перший з'єднання містить перші 4 букви.

Вихідні дані для зашифрування: КОЗИНА Г

Для ключа візьмемо послідовність складається з 32 букв:

Аліна пішла в ліс збирати гриби

Для першого підключа Х використовуємо перші 4 букви ключа: Аліна.

Переводимо вихідний текст і перший з'єднання в двійкову послідовність (див. Додаток Б):

початковий текст

перший з'єднання X0

Таким чином, перші 64 біта визначають вхідну послідовність

L0: 11001010 11001110 11000111 11001000

R0: 11001101 11000000 00100000 11000011

наступні 32 біта визначають перший підключ

Х0: 11000000 11001011 11001000 11001101

I. Знайдемо значення функції перетворення f (R0, X0) (див. Додаток А)

1). Обчислення суми R0 і X0 по mod 2 32

R0: 1100 1101 1100 0000 0010 0000 1100 0011

Х0: 1100 0000 1100 1011 1100 1000 1100 1101

1000 1110 1000 1011 1110 1001 1001 0000

2). Перетворення в блоці підстановки

Результат підсумовування R0 + X0 по mod 2 32

1000 1110 1000 1011 1110 1001 1001 0000

перетворимо в блоці підстановки (див. Додаток В). Для кожного 4-бітного блоку обчислимо його адресу в таблиці підстановки. Номер блоку відповідає номеру стовпчика, десяткове значення блоку відповідає номеру рядка в таблиці. Таким чином, 5-тий блок (1011) замінюється заповненням 11-ої рядки і п'ятого стовпчика в таблиці підстановки (1110).

номера блоків

1000 1110 1000 1011 1110 1001 1001 0000

відповідні номери рядків в таблиці підстановки

8 14 8 11 14 9 9 0

заповнення

9 2 3 14 5 15 3 4

результат

1001 0010 0011 1110 0101 1111 0011 0100

3). Циклічний зсув результату п.2 на 11 біт вліво

Таким чином, знайшли значення функції f (R0, X0):

1111 0010 1111 1001 1010 0100 1001 0001

II. Обчислюємо R1 \u003d f (R0, X0) L0.

Результат перетворення функції f (R0, X0) складаємо з L0 по mod2:

L0: 1100 1010 1100 1110 1100 0111 1100 1000

f (R0, X0): 1111 0010 1111 1001 1010 0100 1001 0001

R1: 0011 1000 0011 0111 0110 0011 0101 1001

Завдання №3. алгоритм шифруванняRSA. Згенеруйте відкритому-тий і закритий ключі в алгоритмі шифрування RSA, обравши прості числа p і q з першої сотні. Зашифруйте повідомлення, що складається з ваших ініціалів: ПІБ.

I.Генерація ключів (див. Додаток Г).

Виберемо два простих числа р \u003d 13 і q \u003d 19 (див. Додаток Д).

тоді модуль

n = pq=13*19 = 247

і функція Ейлера

(n) = (p-1)(q-1) = 12*18 = 216.

закритий ключ d вибираємо з умов d <  (n) і d взаємно просто з  (n) , Тобто d і  (n) не мають спільних дільників.

нехай d = 25.

відкритий ключ e вибираємо з умов e< (n) і de=1(mod  (n)): e<216,

25e\u003d 1 (mod 216).

Остання умова означає, що число 25 e-1 має ділитися на 216 без залишку.

Таким чином, для визначення e потрібно підібрати таке число k, що

25e-1 = 216 k.

при k\u003d 14 отримуємо 25 e\u003d 3024 + 1 або

У нашому прикладі

(121, 247) - відкритий ключ,

(25, 247) - секретний ключ.

II. Шифрування.

Уявімо шіфруемого повідомлення «КГЛ» як послідовно-ність цілих чисел. Нехай буква «К» відповідає числу 12, літера «Г» - числу 4 і буква «Л» - числу 13.

Зашифруємо повідомлення, використовуючи відкритий ключ (121, 247):

З 1 \u003d (
) Mod 247 \u003d 12

З 2 \u003d (
) Mod 247 \u003d 199

З 3 \u003d (
) Mod 247 \u003d 91

Таким чином, вихідного повідомлення (12, 4, 13) відповідає криптограма (12, 199, 91).

III. розшифрування

Розшифруємо повідомлення (12, 199, 91), користуючись секретним ключем (25,247):

М 1 \u003d (
) Mod 247 \u003d 12

М 2 \u003d (
) Mod 247 \u003d 4

М З \u003d (
) Mod 247 \u003d 13

В результаті розшифрування було отримано початкове повідомлення (12, 4, 13), тобто "КГЛ".

Зауваження.

наприклад,

Для розглянутого прикладу отримаємо

Завдання №4. Функція хешування.Знайти хеш-образ своєї Прізвища, використовуючи хеш-функцію
, Гдеn \u003d pq, p, q взяти з Завдання №3.

Хешіруемое повідомлення «КОЗИНА». Візьмемо два простих числа p=13, q\u003d 19 (див. Додаток Е). визначимо n=pq\u003d 13 * 19 \u003d 247. вектор ініціалізації виберемо рівним 8 (вибираємо випадковим чином). Слово «КОЗИНА» можна уявити послідовник-ністю чисел (12, 16, 9, 10, 15, 1) за номерами букв в алфавіті. Таким чином,

n \u003d 247, H 0 \u003d 8, M 1 \u003d 12, M 2 \u003d 16, M 3 \u003d 9, M 4 \u003d 10, M 5 \u003d 15, M 6 \u003d 1.

використовуючи формулу

отримаємо хеш-образ повідомлення «КОЗИНА»:

H 1 \u003d (H 0 + M 1) 2 mod n \u003d (8 + 12) 2 mod 247 \u003d 400 mod 247 \u003d 153

H 2 \u003d (H 1 + M 2) 2 mod n \u003d (153 + 16) 2 mod 247 \u003d 28561 mod 247 \u003d 156

H 3 \u003d (H 2 + M 3) 2 mod n \u003d (156 + 9) 2 mod 247 \u003d 27225 mod 247 \u003d 55

H 4 \u003d (H 3 + M 4) 2 mod n \u003d (55 + 10) 2 mod 247 \u003d 4225 mod 247 \u003d 26

H 5 \u003d (H 4 + M 5) 2 mod n \u003d (26 + 15) 2 mod 247 \u003d 1681 mod 247 \u003d 199

H 6 \u003d (H 5 + M 6) 2 mod n \u003d (199 + 1) 2 mod 247 \u003d 40000 mod 247 \u003d 233

У підсумку отримуємо хеш-образ повідомлення «КОЗИНА», рівний 233.

Завдання №5. Електронний цифровий підпис.Використовуючи хеш-образ своєї Прізвища, обчисліть електронний цифровий підпис за схемою RSA.

Нехай хеш-образ Прізвища дорівнює 233, а закритий ключ алгоритму RSA дорівнює (25, 247). Тоді електронний цифровий підпис повідомлення, що складається з Прізвища, обчислюється за правилом (див. Додаток Ж)

s \u003d 233 25 mod 247 \u003d 168.

Для перевірки ЕЦП, використовуючи відкритий ключ (121, 247), знайдемо

H \u003d 168 121 mod 247 \u003d 233.

Оскільки хеш-образ повідомлення збігається зі знайденим значенням H, то підпис визнається справжньої.

Алгоритм шифрування ГОСТ 28147-89. Метод простої заміни. - Архів WASM.RU

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

3.1 ключова інформація
3.2 Основний крок криптоперетворень
3.3 Базові цикли:“ 32-З” , “ 32-Р” .

4.1 Реалізація основного кроку криптоперетворень
4.2 Збільшення швидкодії алгоритму
5. Вимоги до ключової інформації
6. Список використаної літератури
7. Подяки.

Вступ.

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

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

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

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

Історія розвитку блокових шифрів асоціюється з початком 70-х років, коли компанія IBM усвідомивши необхідність захисту інформації при передачі даних по каналах зв'язку ЕОМ, приступила до виконання своєї програми наукових досліджень, присвячених захисту інформації в електронних мережах, в тому числі і криптографії.

Групу дослідників - розробників фірми IBM, яка приступила до дослідження систем шифрування із симетричною схемою використання ключів, очолив доктор Хорст Файстеля.

2.1 Мережі Файстеля

Запропонована Файстеля архітектура нового методу шифрування в класичній літературі отримала назву «Архітектура Файстеля», але на даний момент в російській і зарубіжній літературі використовується більш усталений термін - "мережа Файстеля" або Feistel`s NetWork. Надалі по даній архітектурі був побудований шифр «Люцифер» - який пізніше був опублікований і викликав нову хвилю інтересу до криптографії в цілому.

Ідея архітектури "мережі Файстеля" полягає в наступному: вхідний потік інформації розбивається на блоки розміром в n бітів, де n парне число. Кожен блок ділиться на дві частини - L і R, далі ці частини подаються в ітеративний блочний шифр, в якому результат j-го етапу визначається результатом попереднього етапу j-1! Сказане можна проілюструвати на прикладі:

Рис. 1

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

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

Для того щоб ідея мереж Файстеля була остаточна ясна, розглянемо найпростіший випадок зображений на рис. 1, Де в функції А - виступить операції "mod 2" ( "xor"), але це найпростішийвипадок, в більш серйозній ситуації, наприклад приховування інформації державної важливості функція А може бути більш складною (скільки я бачив функція А дійсно буває дуже складною):

Вихідні дані:

L \u003d 1110b, R \u003d 0101, K \u003d 1111b

отримати шифрограму

1. (R + K) mod 2 4 \u003d Smod, Smod \u003d 0100b

2. (Smod + L) mod 2 \u003d Sxor, Sxor \u003d 1010b

3. L \u003d R, R \u003d Sxor

L \u003d 0101b, R \u003d 1010b

Пояснимо наші дії:

1. Ця операція додавання по mod 2 4. На практиці така операція зводиться до простого додаванню, де ми повинні скласти два числа і проігнорувати перенесення в 5й розряд. Так як, якщо проставити над розрядами двійкового представлення числа проставити показники ступеня, над п'ятим розрядом якраз буде показник чотири, поглянемо на малюнок нижче, де зображені дії нашої операції:

Рис. 2

Тут я стрілкою вказав на показники ступеня, як видно, результат повинен був вийти 10100, але так як при операції mod 2 4 ігнорується перенос, ми отримуємо 0100.

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

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

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

2.2 Блоковий шифр ГОСТ 28147-89

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

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

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

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

3.1 Ключова інформація

Як я вже говорив вище, в шифруванні даних активну участь беруть:

3.1.1. Ключ - це послідовність восьми елементів розміром в 32 біта кожен. Далі будемо позначати символом К, а елементи з яких він складається - k1, k2, k3, k4, k5, k6, k7, k8.

3.1.2 Таблиця замін - матриця з восьми рядків і шістнадцяти стовпців, в подальшому - Hij. Кожен елемент на перетині рядка i та стовпця j займає 4 біта.

3.2 Основний крок криптоперетворень

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

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

Додавання частина блоку R підсумовується з елементом ключа K по mod 2 32. Про подібної операції я описав вище, тут теж саме тільки показник ступені не «4», а «32» - результат цієї операції в подальшому буду позначати Smod.

Отриманий раніше результат Smod ділимо на чотирьох бітові елементи s7, s6, s5, s4, s3, s2, s1, s0 і подаємо в функцію заміни. Заміна відбувається таким чином: вибирається елемент Smod - s i, з початку починаємо з молодшого елемента, і замінюємо значенням з таблиці замін по i - тому рядку і стовпцю, на який вказує значення елементу s i. Переходимо до s i +1 елементу і чинимо аналогічним чином і продовжуємо так, поки не замінимо значення останнього елемента Smod - результат цієї операції будемо позначати як, Ssimple.

У цій операції значення Ssimple зрушуємо циклічно вліво на 11 біт і отримуємо Srol.

Вибираємо другу частину блоку L і складаємо по mod 2 з Srol, в підсумку маємо Sxor.

На цій стадії частина блоку L стає рівним значенню частини R, а частина R в свою чергу инициализируется результатом Sxor і на цьому функція основного кроку завершена!

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

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

Після того як ви розбили інформацію на блоки, слід розбити ключ на елементи:

K \u003d k1, k2, k3, k4, k5, k6, k7, k8

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

Базові цикли мають, як би це сказати, маркування: n - m. Де n - кількість основних кроків криптоперетворень в базовому циклі, а m - це «тип» базового циклу, тобто про що йде мова, про «З» ашіфровиваніі або «Р» асшіфровиваніі даних.

Базовий цикл шифрування 32-З складається з 32-х основних кроків криптоперетворень. У функцію реалізує дії кроку подають блок N і елемент ключа До причому, перший крок відбувається з к1, другий над отриманим результатом з елементом к2 і т.д. за такою схемою:

k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8, k1, k2, k3, k4, k5, k6, k7, k8k8, k7, k6, k5, k4, k3, k2, k1

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

k1, k2, k3, k4, k5, k6, k7, k8, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1, k8, k7, k6, k5, k4, k3, k2, k1

Практика.

4.1 Реалізація основного кроку криптоперетворень

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

Вихідні дані:

Візьмемо блок інформації N \u003d 0102030405060708h, тут частини L і R рівні:

L \u003d 01020304h, R \u003d 05060708h, візьмемо ключ:

K \u003d ' as28zw37 q8397342ui238e2t wqm2ewp1 '(це ASCII - коди, для того, щоб подивитися шістнадцяткове представлення, можна відкрити цей файл в режим перегляду в Total Commander натиснувши на клавішу « F3»І далі клавішу« 3 »). У цьому ключі значення елементів будуть:

k1 \u003d 'as28', k2 \u003d 'zw37', k3 \u003d 'q839', k4 \u003d '7342'

k5 \u003d 'ui23', k6 \u003d '8e2t', k7 \u003d 'wqm2', k8 \u003d 'ewp1'

Також візьмемо таку таблицю замін:

Рис. 3

Тут рядки нумеруються від 0 до 7, стовпці від 0 до F.

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

Використовуючи «Вихідні дані», необхідно отримати результат дії основного кроку криптоперетворень.

1. Вибираємо частина R \u003d 05060708h і елемент ключа k1 \u003d 'as28', в шістнадцятковому вигляді елемент ключа буде виглядати так: 61733238h. Тепер же робимо операцію підсумовування по mod 2 32:

Рис. 4

Як видно на малюнку у нас не відбулося перенесення в 33 біт позначений червоним кольором і з показником ступеня « 32 ». А якби у нас були б інші значення R і елемента ключа - це цілком могло б статися, і тоді б ми його проігнорували, і в подальшому використовували тільки біти, помічені жовтим кольором.

Таку операцію я виконую командою асемблера add:

; eax \u003d R, ebx \u003d 'as28'

Результат цієї операції Smod \u003d 66793940h

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

Рис. 5

Я постарався наочно уявити елементи Smod на малюнку, але все одно поясню:

s0 \u003d 0, s1 \u003d 4, s2 \u003d 9 і т.д.

Тепер починаючи з молодшого елемента s0, виробляємо заміну. Згадуючи пункт « 3.2 Основний крок криптоперетворень»I - рядок, s i - стовпець, шукаємо в нульовий рядку і нульовому стовпці значення:

рис.6

Таким чином, поточне значення Smod, що не 6679394 0 h, а 6679394 5 h.

Приступаємо замінювати s1, тобто четвірку. Використовуючи перший рядок і четвертий стовпець (s1 \u003d 4!). Дивимося на малюнок:

Рис. 7

Тепер уже значення Smod, що не 667939 4 5h, 667939 2 5h. Я припускаю, що тепер алгоритм заміни читачеві зрозумілий, і я можу сказати, що після кінцевий результат Ssimple матиме таке значення - 11e10325h.

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

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

Рис. 8

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

4. Тепер же залишається частина L нашого блоку інформації поXORіть зі значенням Srol. Я беру калькулятор від w2k sp4 і отримую Sxor \u003d 091b2b8bh.

5. Ця дія підсумкове і ми просто присвоюємо, чисти R значення частини L, а частина L инициализируем значенням Sxor.

Кінцевий результат:

L \u003d 091b2b8bh, R \u003d 01020304h

4.2 Збільшення швидкодії алгоритму

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

Коли я реалізовував алгоритм шифрування в своїй програмі, я поступив таким чином:

1. Вибрав частину блоку L в регістр eax, а R в edx.

2. У регістр esi ініціалізувати адресою розширеного ключа, про це нижче.

3. У регістр ebx привласнював значення адреси розширеної таблиці замін, про це теж нижче

4. передавав інформацію пунктів 1,2, 3 в функцію базового циклу 32 - З або 32 - Р, в залежності від ситуації.

Якщо подивитися на схему подачі елементів ключа в пункті « Базові цикли: "32-З", "32-Р"», То наш ключ для базового циклу 32 - З можна представити в наступному:

До 32-З \u003d

'As28', 'zw37', 'q839', '7342', 'ui23', '8e2t', 'wqm2', 'ewp1',

'As28', 'zw37', 'q839', '7342', 'ui23', '8e2t', 'wqm2', 'ewp1',

'Ewp1', 'wqm2', '8e2t', 'ui23', '7342', 'q839', 'zw37', 'as28'

Тобто з початку йдуть k1, k2, k3, k4, k5, k6, k7, k8 - ‘ as28 ','zw37 ','q839 ',' 7342 ','ui23 ',' 8e2t ','wqm2 ','ewp1 ' три рази ця послідовність повторюється. Потім елементи йдуть в зворотному порядку, тобто .: k8, k7, k6, k5, k4, k3, k2, k1 - 'Ewp1', 'wqm2', '8e2t', 'ui23', '7342', 'q839', 'zw37', 'as28'.

Я заздалегідь розташував в масиві елементи в тому порядку, як вони повинні подаватися в 32 - З. Тим самим я збільшив пам'ять, необхідну під ключ, але позбавив себе від деяких процесів мислення, які мені були не потрібні, і збільшив швидкість роботи алгоритму, за рахунок зменшення часу звернення до пам'яті! Тут я описав тільки ключ для 32 - З, для циклу 32 - Р я вчинив аналогічно, але використовуючи іншу схему подачі елементів, яку я теж описував в пункті « Базові цикли: "32-З", "32-Р».

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

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

Наприклад, нам потрібно було замінити, число 66793940h. Представлю його в наступному вигляді:

Рис. 9

Тепер якщо взяти елементи s1, s0, тобто молодший байт, то результат функції заміни буде дорівнює 25h! Почитавши статтю Андрія Винокурова, яку я привів в пункті « Список використаної літератури», Ви дійсно виявите, що якщо взяти два рядки можна отримати масив, що дозволяє швидко знаходити елементи заміни за допомогою команди асемблера xlat.Кажуть можна і іншим способом більш швидким, але Андрій Винокуров витратив на дослідження швидких алгоритмів для реалізації ГОСТу близько чотирьох років! Думаю, не варто винаходити велосипед, коли він уже є.

Отже, про масиві:

Візьмемо дві перші рядки нульову і першу, створимо масив на 256 байт. Тепер спостерігаємо одну особливість, що якщо треба перетворити 00h, то результат буде 75h (спираємося на рис.3) - ставимо це значення в масив на зміщення 00h. Беремо значення 01h, результат функції замін 79h, кладемо його в масив на зміщення 01 і так далі до 0FFh, яке нам дасть 0FCh, яке ми покладемо в масив по зміщення 0FFh. Ось ми і отримали розширену таблицю замін для першої групи рядків: першої і нульовий. Але ще є три групи: друга стор.2, стор.3, третя стор.4, стор. 5, четверта стор.6, стор.7. З цим трьома групами чинимо тим же способом, що і з першою. Результат - розширена таблиця замін!

Тепер можна реалізувати алгоритм, який буде робити заміну. Для цього беремо вихідні коди, які виклав Андрій Винокуров на своїй сторінці, дивись « Список використаної літератури».

lea ebx, extented_table_simple

mov eax, [покласти число яке потрібно замінити]

add ebx, 100h; перехід до двох наступних вузлів

sub ebx, 300h; щоб в подальшому ebx показував на таблицю

Тепер ще одна особливість, попередніми діями ми не тільки замінили, але і зрушили число на 8 біт вліво! Нам залишається тільки зрушити число ще на 3 біти вліво:

і ми отримуємо результат операції rol eax, 11!

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

Вимоги до ключової інформації.

Як сказано в статті Андрія Винокурова ключ вибирають за двома критеріями:

Критерій равновероятного розподілу бітів між значеннями 1 і 0. Зазвичай в якості критерію равновероятного розподілу бітів - виступає критерій Пірсона ( «хі-квадрат»).

Це означає ключем, в принципі може будь-яке число. Тобто при формуванні чергового біта ключа ймовірність його ініціалізації одиницею або нулем 50/50!

Прошу зауважити, що ключ з восьми елементів, кожен по 32 біта, таким чином всього в ключі 32 * 8 \u003d 256 бітів і кількість можливих ключів 2 256! Тебе це не вражає?

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

Якщо ми подивимося на наш ключ, який я навів у пункті « 4.1 Реалізація основного кроку криптоперетворень», То ви помітите, що справедлива наступна запис:

Рис. 10

Однією фразою значення k 1 не повинно повторитися не в k 2, не в будь-якому іншому елементі ключа.

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

Тепер про вибір таблиці замін:

Тепер же поговоримо про те, як правильно вибрати таблицю замін. Основна вимога до вибору таблиць замін - це явище «неповторяемости» елементів, кожен з яких розміром в 4 біта. Як ви вже бачили вище, кожен рядок таблиці замін складається з значень 0h, 1h, 2h, 3h, ..., 0fh. Так ось основна вимога свідчить про те, що в кожному рядку є значення 0h, 1h, 2h, ..., 0fh і кожне таке значення в одному екземплярі. Наприклад, послідовність:

1 2 3 4 5 6 7 8 9 A B C D E F

Цілком відповідає цій вимозі, але все ж! Таку послідовність як рядки вибирати не рекомендується. Бо якщо ви подасте значення на вхід функції, яка спирається на такий рядок, то на виході ви отримаєте таке ж значення! Не вірите? Тоді візьміть число 332DA43Fh і вісім таких рядків, як таблиці замін. Проведіть операцію заміни, і запевняю вас, на виході ви отримаєте число 332DA43Fh! Тобто таке ж, що ви подали на вхід операції! А це не є ознакою хорошого тону при шифруванні, та й чи було?

Це було одне вимога, наступний критерій говорить про те, що - кожен біт вихідного блоку повинен бути статистично незалежний від кожного біта вхідного блоку!

Як це виглядає простіше? А ось як, наприклад, ми вибрали з наведеного вище числа елемент s0 \u003d 0Fh, 01111b. Імовірність того, що ми зараз замінимо перший біт одиницею або нулем дорівнює 0,5! Імовірність заміни другого, третього і четвертого біта, кожен біт, розглядаємо окремо, одиницями або нулями теж дорівнює 0, 5. При виборі s1 \u003d 0Eh, ймовірність того, що ми нульовий біт, а це «0», замінимо нулем або одиницею теж дорівнює - 0,5! Таким чином, згідно з цим критерієм між заміною нульових бітів елементів s0, s1 немає ніякої закономірності! Так, ви могли замінити одиницями, але ви також могли поставити і нулі.

Для оцінки таблиці за цим критерієм можна побудувати таблицю коефіцієнтів кореляції, розраховані за формулою:

Якщо p \u003d 1, то значення біта j на виході дорівнює значенню біта i на вході при будь-яких комбінаціях біт на вході;

Якщо p \u003d -1, то значення біта j на виході завжди є інверсією вхідного біта i;

Якщо p \u003d 0, то вихідний біт j з однаковою ймовірністю приймає значення 0 і 1 при будь-якому фіксованому значенні вхідної біта i.

Візьмемо приклад одного рядка:

Розкладемо на «складові»:

Розрахуємо один коефіцієнт за формулою наведеною вище. Щоб простіше було зрозуміти, як це робиться, поясню більш детально:

Беремо 0-й біт 0-ого числа (0) на вході і 0-й біт 0-ого числа на виході (1) проводимо операцію 0 XOR 1 \u003d 1.

Беремо 0-й біт 1-ого числа (1) на вході і 0-й біт 1-ого числа на виході (1) проводимо операцію 1 XOR 1 \u003d 0.

Беремо 0-й біт 2-ої числа (0) на вході і 0-й біт 2-ої числа на виході (0) проводимо операцію 0 XOR 0 \u003d 0.

Беремо 0-й біт 3-ого числа (1) на вході і 0-й біт 3-ого числа на виході (1) проводимо операцію 1 XOR 1 \u003d 0.

Провівши послідовно операції XOR в такій послідовності, підраховуємо кількість всіх ненульових значень, отримуємо значення 6. Звідси P 00 \u003d 1 (6/2 4-1) \u003d 0,25. Отже, з'ясувалося, що значення біта 0 на виході дорівнює значенню біта 0 на вході в 4-х випадках з 16-ти;

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

Як видно з таблиці кореляційних коефіцієнтів біт 3 на вході инвертирован щодо біта 0 на виході в 14 випадках з 16, що становить 87.5% Ось це вже не допустимо для нормальних систем шифрування. Для різноманітності візьмемо ще прімерчік:

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

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

09 0D 03 0E-06 02 05 08-0A 07 00 04-0C 01 0F 0B

00 05 0A 07-03 08 0F 0C-0E 0B 04 09-0D 06 01 02

06 0B 0F 00-0C 01 02 0D-08 07 09 04-05 0A 03 0E

04 0E 00 09-0B 01 0F 06-03 0D 07 0A-0C 02 08 05

04 02 08 0E-05 0F 03 09-0B 01 0D 07-0A 0C 06 00

07 03 09 0C-08 00 06 0F-0E 04 01 0A-0D 0B 02 05

06 0F 03 08-0D 04 0A 01-09 02 05 0C-00 0B 0E 07

0C 06 08 01-03 09 07 0E-0B 05 0F 02-04 0A 00 0D

04 0B 09 06-0E 01 00 0F-0A 05 03 0C-0D 02 07 08

00 0E 0F 01-07 08 09 06-04 0B 0A 05-03 0D 0C 02

0F 09 01 07-04 0A 08 06-0E 00 02 0C-05 03 0B 0D

0A 03 04 01-05 0C 0B 0E-08 06 0F 0D-07 09 00 02

0B 06 0F 01-04 0A 08 05-00 0D 0C 02-07 09 03 0E

0C 03 02 08-0D 06 0B 05-07 09 04 0F-0A 00 01 0E

02 0B 0F 04-09 00 06 0D-05 0E 01 08-0C 07 0A 03

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

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

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

для комп'ютерів платформи Intel x86.

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

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

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

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

Ross N. Williams:

Елементарне керівництво по CRC алгоритмам виявлення помилок
Викладена на сайті www.wasm.ru.

Подяки.

Хотілося б висловити подяку всім відвідувачам форуму www.wasm.ru. Але особливо б хотілося б подякувати ChS, який зараз відомий, як SteelRat, він допоміг мені зрозуміти такі речі, чого я б, напевно, ніколи б не зрозумів, а так само допомогу при написанні пункту: « Вимоги до ключової інформації», Основною частина даного пункту була написана ним. Також глибоко вдячний співробітнику КДТУ ім. А.Н. Туполєва Анікіну Ігорю В'ячеславовичу і гріх було б не відзначити Кріса Касперски, за те, що він є і Volodya / wasm.ru за його настанови. Ох, і дістається мені від нього. Так само хочу відзначити Sega-Zero / Callipso зате, що доніс до мого розуму деякі математичні нетрі.

Це, мабуть, все, що я хотів би сказати вам.

Буду, вдячний за критику або питання, пов'язані з цією статтею або просто поради. Мої контактні дані: [Email protected] , ICQ - 337310594.

З повагою Evil`s Interrupt.

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

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

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

При описі алгоритму використовуються наступні позначення:

L і R - послідовності бітів;
LR - конкатенація послідовностей L і R, в якій біти послідовності R слідують за бітами послідовності L;
(+) - порозрядне додавання по модулю 2 (операція "виключає АБО");
[+] - складання 32-розрядних чисел по модулю 2 32;
(+) - додавання 32-розрядних чисел по модулю 2 32 -1.

Числа підсумовуються за наступним правилом:

A [+] B \u003d A + B, якщо A + B< 2 32 ,
A [+] B \u003d A + B - 2 32, якщо A + B\u003e \u003d 2 32. A (+) B \u003d 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 \u003d K 7 K 6 K 5 K 4 K 3 K 2 K 1 K 0.

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

Режим простої заміни

Перший і найпростіший режим - заміна. Дані, що підлягають шифруванню, розбивають на 64-бітові блоки. Процедура шифрування блоку відкритих даних T 0 включає 32 циклу (j \u003d 1 ... 32).

Блок T 0 розділяється на дві послідовності по 32 біта: В (0) A (0), де В (0) - ліві чи старші біти, A (0) - праві або молодші біти.

Ці послідовності вводять в накопичувачі N 1 та N 2 перед початком першого циклу шифрування.

Перший цикл (j \u003d 1) процедури шифрування 64-бітного блоку даних описується наступними формулами:

Тут i позначає номер ітерації (i \u003d 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-розрядний блок зашифрованих даних Т ш представляється у вигляді Т ш \u003d A (32) B (32).

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

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

режим гамування

Відкриті дані, розбиті на 64-розрядні блоки Т (i) (i \u003d 1, 2, ..., m, де m визначається об'ємом шифрованих даних), зашифровуються в режимі гамування шляхом порозрядного додавання за модулем 2 з гамою шифру Г ш, яка виробляється блоками по 64 біт, тобто Г ш \u003d (Г (1), Г (2), ..., Г (i), ..., Г (m)).

Рівняння зашифрування даних в режимі гамування може бути представлена \u200b\u200bв наступному вигляді:

Ш (i) \u003d A (Y (i-1) [+] C2, Z (i-1) (+) C1) (+) T (i) \u003d Р (i) (+) T (i).
Тут Ш (i) - 64-розрядний блок зашифрованого тексту,
A - функція шифрування в режимі простої заміни (аргументами цієї функції є два 32-розрядних числа),
С1 і С2 - константи, задані в ГОСТ 28147-89,
Y (i) і Z (i) - величини, які визначаються ітераційно по мірі формування гами наступним чином:
(Y (0), Z (0)) \u003d A (S), де S - 64-розрядна двійкова послідовність (сінхропосилка);
(Y (i), Z (i)) \u003d (Y (i-1) [+] C2, Z (i-1) (+) C1) для i \u003d 1, 2, ..., m.

Розшифрування даних можливе тільки при наявності сінхропосилкі, яка не є секретним елементом шифру і може зберігатися в пам'яті ЕОМ або передаватися по каналах зв'язку разом з зашірованнимі даними.

Режим гамування зі зворотним зв'язком

режим гамування зі зворотним зв'язком дуже схожий на режим гамування. Як в і режимі гамування відкриті дані, розбиті на 64-розрядні блоки Т (i) (i \u003d 1, 2, ..., m, де m визначається об'ємом шифрованих даних), зашифровуються шляхом порозрядного додавання за модулем 2 з гамою шифру Г ш, яка виробляється блоками по 64 біт:

Г ш \u003d (Г (1), Г (2), ..., Г (i), ..., Г (m)).

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

Рівняння зашифрування даних в режимі гамування зі зворотним зв'язком може бути представлено в наступному вигляді:

Тут Ш (i) - 64-розрядний блок зашифрованого тексту,
A - функція шифрування в режимі простої заміни. Аргументом функції на першому кроці ітеративного алгоритму є 64-розрядної сінхропосилка, а на всіх наступних - попередній блок зашифрованих даних Ш (i-1).

Bиработкі имитовставки

процес вироблення імітовстакі единообразен для будь-якого з режимів шифрування даних.

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

Для отримання имитовставки відкриті дані представляються у вигляді 64-розрядних блоків Т (i) (i \u003d 1, 2, ..., m, де m визначається обсягом шифрованих даних). Перший блок відкритих даних Т (1) піддається перетворенню, що відповідає першим 16 циклів алгоритму зашифрування в режимі простої заміни. Причому в якості ключа для вироблення имитовставки використовується ключ, по якому шифруються дані.

Отримане після 16 циклів роботи 64-розрядне число підсумовується по модулю 2 з другим блоком відкритих даних Т (2). Результат підсумовування знову піддається перетворенню, що відповідає першим 16 циклів алгоритму зашифрування в режимі простої заміни. Отримане 64-розрядне число підсумовується по модулю 2 з третім блоком відкритих даних Т (3) і т.д. Останній блок Т (m) при необхідності доповнений до повного 64-розрядної блоку нулями, підсумовується по модулю 2 з результатом роботи на кроці m-1, після чого зашифрована в режимі простої заміни за перші 16 циклів роботи алгоритму. З отриманого 64-розрядного числа вибирається відрізок Ір довжиною р біт.

Имитовставка Ір передається по каналу зв'язку або в пам'ять ЕОМ після зашифрованих даних. Надійшли зашифровані дані розшифровуються, і з отриманих блоків відкритих даних T (i) виробляється имитовставка Ір ", яка потім порівнюється з імітовставки Ір, отриманої з каналу зв'язку або з пам'яті ЕОМ. У разі розбіжності імітовставок все розшифровані дані вважають помилковими.

Це цікаво: