Обчислення числа, оберненого до поданого, у кільці цілих чисел

Для обчислення елементу, оберненого до поданого, у довільному кільці застосовується алгоритм, який ґрунтується на алгоритмі Евкліда пошуку найбільшого спільного дільника двох чисел (елементів кільця). Розглянемо алгоритм Евкліда.

Будемо говорити, що a є дільником b (або a ділить b, це позначають a | b), якщо існує таке c, що a c = b. Якщо a ділить b, і a ділить c, кажуть, що a є спільним дільником a та b. В алгоритмі Евкліду використовується операція a mod b (a по модулю b), яка визначає таке c, що a = p b + c, і 0 £ c < b. Будемо позначати найбільший спільний дільник чисел a та b як НСД(a, b).

Алгоритм Евкліда складається з двох кроків.

1. Якщо a = 0, НСД(a, b) = b, кінець алгоритму.

2. Обчислити НСД(b mod a, a).

 

Симетричні шифри

Застосування симетричних шифрів передбачає два перетворення: c = E(m, k) m = D (c, k), де m – відкритий текст, E – функція шифрування, D – функція дешифрування, c – шифротекст. Згідно з принципом Керкгоффса функції E і D загальновідомі, і секретність c забезпечується секретністю ключа k. Іноді симетричні системи застосовують два ключі: один - для шифрування, другий – для дешифрування. Але між цими ключами існує відомий зв’язок, і за будь-яким відомим одним з них можна легко обчислити інший.

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

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

З метою підвищення стійкості довжина блоку обирається достатньо великою (64, 128 або більше бітів).

 

Шифр Фейстеля

Історично першим з сучасних блочних шифрів є DES (Data Encryption Standard), який ґрунтується на шифрі Г. Файстеля, який працював у фірмі IBM і виконав деякі з перших невійськових досліджень у галузі алгоритмів шифрування. Шифрування за алгоритмом Г. Файстеля являє собою ітераційну процедуру, тобто передбачає багаторазове повторення подібних дій. Традиційно ітерації в алгоритмах шифрування називають раундами. Блок-схема одного раунду показана на рис. 2.1.Особливість поданого алгоритму полягає в тому, що функція раунду має зворотну незалежно від того, яка функція застосовується в середині раунду. Кожний i-й раунд шифрування здійснюється згідно з правилами l_i = r_i-1, r_i = l_i-1 Å F(k_i, r_i-1). Отже, розшифровування відбувається згідно з перетвореннями r_i-1 = l_i, l_i-1 = r_i Å F(k_i, l_i). Наведені формули показують, що для розшифровування треба застосовувати ті ж підключі, що і при шифруванні, але у зворотному порядку. При цьому алгоритм розшифрування збігається з алгоритмом шифрування (рис. 2.2), якщо на вхід подати шифр, у якому переставлені ліва і права половини (r_s, l_s).

 

Алгоритм DES

Алгоритм DES складається з 16 раундів, довжина блоку – 64 біти, довжина ключа 56 бітів, а довжина кожного підключа (ключа раунду) – 48 бітів. Оскільки при сучасних обчислювальних методах довжина ключа 56 бітів може виявитися недостатньою, замість DES використовують 3DES, що являє собою послідовне виконання трьох алгоритмів DES з різними ключами.Алгоритм DES шифрування 64-бітового блоку складається з трьох кроків: 1) початкова перестановка бітів блоку згідно з фіксованою таблицею перестановок; 2) виконання 16 раундів алгоритму Файстеля до отриманого блоку; 3) перестановка зворотна до початкової.Початкова та кінцева перестановки представлені відповідно таблицями 2.1 та 2.2. Кожний елемент таблиці дорівнює номеру біту у вхідному блоці (до перестановки). Місце елементу в таблиці визначає розташування відповідного біту після перестановки. При цьому елементи першого рядка відповідають розташуванню бітів на місцях з першого по восьмий, другого – з 9-го по 16-ий і т.д. Наприклад, табл. 2.1 вказує, що на перше місце в результаті перестановки ставиться 58-й біт, а на друге – 50-й. Тому табл. 2.2 вказує, що на 58-е місце переставляється 1-й біт, а на 50-е – на другий.Тепер розглянемо функцію F, яка отримує два аргументи: r_i-1 - молодші 32 біти поточного стану блоку і ключ раунду k_i. Функція F послідовно виконує п’ять перетворень: 1) перестановка з розширенням; 2) обчислення суми за модулем 2 результату попереднього перетворення і ключа раунду; 3) розщеплення результату попереднього перетворення – отримання восьми груп бітів по 6 біт у кожній; 4) стиск кожної групи до 4-бітового коду; 5) утворення 32-бітового коду на виході F. У першому перетворенні 32-бітовий код розтягується до 48 бітів і перемішується згідно з таблицею 2.3, яка читається так само, як попередні. Це допомагає розсіювати зв’язки між вхідними бітами і вихідними, тобто створює лавинний ефект, коли мала відміна між двома вхідними наборами даних призводить до великих відмін на виході. Після порозрядного додавання за модулем 2 ключа раунду до отриманого 48-бітового коду у сумі послідовно виділяються групи по 6 біт: біти з першого по шостий утворюють першу групу, з сьомого по дванадцятий – другу і т.д. Остання, восьма група утворюється бітами з 43-го по 48-й. Кожна 6-бітова група перетворюється у 4-бітову за допомогою окремої таблиці, що називається S-блоком. Всього використовується вісім S-блоків (рис. 2.3). Перший і шостий біти групи визначають номер рядка S-блоку, а біти з другого по п’ятий – номер стовпця. Елемент S-блоку, що розташований на перетинанні визначених рядка та стовпця, у двійковому коді дорівнює вихідному 4-бітовому значенню.

 

Визначення поля GF(2⁸).

S-блоки почергово обробляють елементи рядків матриці станів. Елементи цієї матриці – байти, і над ними виконуються операції додавання та множення, визначені у полі GF(2⁸). Елементами цього поля є байти, що представляються упорядкованою послідовністю восьми бітів (a₇ a₆ a₅ a₄ a₃ a₂ a₁ a₀). Кожному байту ставиться у відповідність поліном a₇x⁷ + a₆x⁶ + a₅x⁵ + a₄x⁴ + a₃x³ + a₂x² + a₁x¹ + a₀x⁰. У полі GF(2⁸) операція додавання визначається як додавання за модулем 2 відповідних коефіцієнтів (тобто порозрядна операція Å). Операція множення визначається як множення відповідних поліномів за модулем простого поліному х⁸ + х⁴ + х³ + х + 1.

Виконання перетворення SubBytes

Функція раунду використовує чотири операції: SubBytes, ShiftRows, MixColumns, AddRoundKey.

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

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