Розробка власного програмного засобу, рішення

Опис власного методу розв’язання задач

Визначення і допоміжні процедури.

Block послідовність біт, з яких складається input, output, State і Round Key. Також під Block можна розуміти послідовність байт.

CipherKey секретний, криптографічний ключ, який використовується Key Expansion процедурою, щоб провести набір ключів для раундів (Round Keys); може бути представлений як прямокутний масив байтів, що має чотири рядки і Nk колонок.

Ciphertext — вихідні дані алгоритму шифрування.

Key Expansion процедура використовується для генерації Round Keys з Cipher Key.

Round Key виходять з Cipher Key використовуючи процедуру Key Expansion. Вони застосовуються до State при шифруванні і розшифруванні.

State проміжний результат шифрування, який може бути представлений як прямокутний масив байтів має 4 рядки і Nb колонок.

S-box нелінійна таблиця замін, що використовується в декількох трансформаціях заміни байт і в процедурі Key Expansion для взаємно однозначної заміни значення байта. Попередньо розрахований S-box можна побачити в таблиці 3.1.

Nb число стовпців (32-ух бітних слів), що становлять State. Nb = 4.

Nk число 32-ух бітних слів, складових шифроключа. Nk = 4,6, або 8.

Nr число раундів, яке є функцією Nk і Nb. Для AES, Nr = 10, 12, 14.

Rcon [] масив, який складається з бітів 32-х розрядного слова і є постійним для даного раунду. Попередньо розрахований Rcon [] можна побачити в таблиці 3.2.

Таблиця 3.1 — Нелінійна таблиця замін

Таблиця 3.2 — Масив Rcon [].

Допоміжні процедури.

AddRoundKey () трансформація при шифруванні і зворотному шифруванні, при якій RoundKey XOR’иться з State. Довжина RoundKey дорівнює розміру State (ті, якщо Nb = 4, то довжина RoundKey дорівнює 128 біт або 16 байт).

InvMixColumns () трансформація при розшифруванні, яка є зворотною по відношенню до MixColumns ().

InvShiftRows () трансформація при розшифруванні, яка є зворотною по відношенню до ShiftRows ().

InvSubBytes () трансформація при розшифруванні, яка є зворотною по відношенню до SubBytes ().

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

RotWord () функція, що використовується в процедурі Key Expansion, яка бере 4-х байтне слово і проводить над ним циклічну перестановку.

ShiftRows () трансформації при шифруванні, які обробляють State, циклічно зміщуючи останні три рядки State на різні величини.

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

SubWord () функція, яка використовується в процедурі Key Expansion, яка бере на вході чотирибайтне слово і застосовуючи S-box до кожного з чотирьох байтів видає вихідне слово.

Шифрування.

AES є стандартом, заснованим на алгоритмі Rijndael. Для AES довжина input (блоку вхідних даних) і State (стану) постійна і дорівнює 128 біт, а довжина шифроключа K складає 128, 192, або 256 біт. При цьому, вихідний алгоритм Rijndael допускає довжину ключа і розмір блоку від 128 до 256 біт з кроком в 32 біта. Для позначення вибраних довжин input, State і Cipher Key в байтах використовується нотація Nb = 4 для input і State, Nk = 4, 6, 8 для Cipher Key відповідно для різних довжин ключів.

На початку шифрування input копіюється в масив State за правилом s [r, c] = in [r + 4c], для і. Після цього до State застосовується процедура AddRoundKey () і потім State проходить через процедуру трансформації (раунд) 10, 12, або 14 разів (в залежності від довжини ключа), при цьому треба врахувати, що останній раунд дещо відрізняється від попередніх. У підсумку, після завершення останнього раунду трансформації, State копіюється в output за правилом out [r + 4c] = s [r, c], для і .

Окремі трансформації SubBytes (), ShiftRows (), MixColumns (), і AddRoundKey () — обробляють State. Масив w [] - містить key schedule.

Рисунок 3.1 — Псевдокод для Cipher.

SubBytes ().

У процедурі SubBytes, кожен байт в State замінюється відповідним елементом у фіксованій 8-бітній таблиці пошуку S; bij = S (aij).

Рисунок 3.2 — Схема SubBytes ().

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

де, і де bi є i-ий біт b, а ci — i-ий біт константи c = 6316 = 9910 = 11 000 112. Таким чином, забезпечується захист від атак, заснованих на простих алгебраїчних властивостях.

Рисунок 3.3 — 8-бітна таблиця пошуку S.

ShiftRows ().

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

Рисунок 3.4 — Схема ShiftRows ()

ShiftRows працює з рядками State. При цій трансформації рядки стану циклічно зсуваються на r байт по горизонталі, залежно від номера рядка. Для нульового рядка r = 0, для першого рядка r = 1 і т.д. Таким чином кожна колонка вихідного стану після застосування процедури ShiftRows складається з байтів з кожної колонки початкового стану. Для алгоритму Rijndael патерн зсуву рядків для 128 — і 192-бітних рядків однаковий. Однак для блоку розміром 256 біт відрізняється від попередніх тим, що 2, 3, і 4-і рядки зміщуються на 1, 3, і 4 байта, відповідно.

MixColumns ().

У процедурі MixColumns, кожна колонка стану перемножується з фіксованим многочленом c (x).

Рисунок 3.5 — Схема MixColumns ()

У процедурі MixColumns, чотири байти кожної колонки State змішуються, використовуючи для цього оборотну лінійну трансформацію. MixColumns обробляє стани по колонках, трактуючи кожну з них як поліном четвертого степеня. Над цими поліномами проводиться множення в GF (28) по модулю x4 + 1 на фіксований многочлен c (x) = 3×3 + x2 + x + 2. Разом з ShiftRows, MixColumns вносить дифузію в шифр.

AddRoundKey ().

В процедурі AddRoundKey, кожен байт стану з'єднується з RoundKey використовуючи XOR operation.

Рисунок 3.6 — Схема AddRoundKey ()

В процедурі AddRoundKey, RoundKey кожного раунду об'єднується з State. Для кожного раунду RoundKey виходить з CipherKey використовуючи процедуру KeyExpansion, кожен RoundKey такого ж розміру, що і State. Процедура виробляє побітовий XOR кожного байта State з кожним байтом RoundKey.

Алгоритм обробки ключа Алгоритм обробки ключа складається з двох процедур:

• — Алгоритм розширення ключа.
• — Алгоритм вибору раундового ключа (ключа ітерації).

Алгоритм розширення ключа.

AES алгоритм, використовуючи процедуру KeyExpansion () і подаючи в неї Cipher Key, K, отримує ключі для всіх раундів. Всього вона отримує Nb * (Nr + 1) слів: спочатку для алгоритму потрібно набір з Nb слів, і кожному з Nr раундів потрібно Nb ключових набору даних. Отриманий масив ключів для раундів позначається як, .

Алгоритм KeyExpansion () показаний в псевдокоді на Рис. 3.7 Функція SubWord () бере чотирьохбайтове вхідне слово і застосовує S-box до кожного з чотирьох байтів те, що вийшло подається на вихід. На вхід RotWord () подається слово [a0, a1, a2, a3] яке вона циклічно переставляє і повертає [a1, a2, a3, a0]. Масив слів, постійний для даного раунду,, містить значення [xi — 1,00,00,00], де x = {02}, а xi — 1 є степенем x в (i починається з 1). З малюнка можна побачити, що перші Nk слів розширеного ключа заповнені CipherKey. У кожне наступне слово, w [i], кладеться значення отримане при операції XOR w [i — 1] і, ті XOR’а попереднього і на Nk позицій раніше слів. Для слів, позиція яких кратна Nk, перед XOR’ом до w [i-1] застосовується трасформація, за якою слідує XOR з константою раунду Rcon [i]. Зазначена вище трансформація складається з циклічного зсуву байтів в слові (RotWord ()), за якою йде процедура SubWord () — те ж саме, що і SubBytes (), тільки вхідні і вихідні дані будуть розміром в слово. Важливо зауважити, що процедура KeyExpansion () для 256 бітного CipherKey трохи відрізняється від тих, які застосовуються для 128 і 192 бітових шифроключей. Якщо Nk = 8 і i — 4 кратне Nk, то SubWord () застосовується до w [i — 1] до XOR’а.

Рисунок 3.7 — Псевдокод для KeyExpansion.

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

Рисунок 3.8 — Псевдокод для InverseCipher.

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