Як працює AES: покроковий розбір алгоритму та власна реалізація
AES - це симетричний блоковий шифр, який шифрує дані блоками по 128 біт через кілька раундів підстав, перестановок і лінійних перетворень, забезпечуючи швидкий і стандартизований криптографічний захист даних.
AES з’явився в результаті відкритого конкурсу NIST у 1997 році, де в 2000 році переміг алгоритм Rijndael від Вінсента Реймена і Йоана Даймена, після чого в 2001 році він був затверджений як федеральний стандарт шифрування США і став світовим стандартом симетричного шифрування.
Як працює AES
AES використовує блоки по 16 байтів та ключ.
Ключ та дані (які називають State) можна зобразити за допомогою матриці 4x4:
В AES байти записуються в state по стовпцях, а не по рядках. Це означає, що перші 4 байти утворюють перший стовпець, наступні 4 - другий і т.д.
AES використовує 4 операції над state:
- SubBytes
- ShiftRows
- MixColumns
- AddRoundKey
Увесь процес буде виглядати так:
SubBytes
Замінює кожен байт на інший за таблицею, щоб дані перестали бути впізнаваними.
Кожен байт в state замінюється за допомогою S-box:
Рядки - це перша частина байту, стовпчики - це друга частина байту, їх перетин дає нам вихідний байт.
Наприклад:
ShiftRows
Зсуває байти в рядках, щоб вони перемішалися між собою.
Зсув в рядку:
Рядок 0: без змін
Рядок 1: зсув на 1
Рядок 2: зсув на 2
Рядок 3: зсув на 3Приклад:
Перетворюємо на:
MixColumns
Перемішує байти всередині кожного стовпця, посилюючи плутанину.
Ми беремо стовпчик:
Після чого множимо його за допомогою матриці:
В результаті отримуємо нові значення:
Робимо це і для інших стовпчиків:
Правила множення:
AddRoundKey
Пов’язує стан із секретним ключем, роблячи дешифрування неможливим без знання ключа.
Найпростіша операція, все що нам потрібно зробити XOR між байтами ключа та state.
Key Schedule
Key Schedule в AES — це алгоритм, який з одного короткого секретного ключа генерує набір раундових ключів, по одному на кожен раунд шифрування.
Початковий ключ, як і state, представляється у вигляді матриці 4×4 байтів:
На практиці зручніше думати про ключ як про 4 слова по 4 байти:
де кожне W — це:
Генеруємо перше слово в новому ключі
- Беремо останнє слово з минулого ключа:
- Робимо RotWord (Циклічно зсуваємо байти вліво):
- SubWord. Кожен байт отриманого слова пропускається через той самий S-box, що й у SubBytes.
- До першого байта слова застосовується XOR з раундовою константою Rcon:
- Також потрібно зробити XOR з першим словом в минулому ключі:
Це буде перше слово нашого нового ключа.
Генеруємо інші слова
Наступні слова будуть генеруватися за правилом:
Тобто друге слово це - минуле слово та друге слово в початковаму ключі:
Трете слово - минуле слово та третье слово з початкового ключа:
І останнє слово - це минуле слова та останнє слово з початкового ключа:
Новий ключ буде виглядати так:
Або можемо записати як строку:
2a21a9f95b159acd6827fca906428e9aЗа таким алгоритмом нам потрібно згенерувати ключі для раундів 2-10.
Шифруємо текст власноруч
Спочатку потрібно обрати текст для шифрування:
Hello from LD31DТа перетворити на Hex:
48 65 6c 6c 6f 20 66 72 6f 6d 20 4c 44 33 31 44
Також потрібно обрати ключ:
fajfq43432fdner3В hex:
66 61 6a 66 71 34 33 34 33 32 66 64 6e 65 72 33
Initial Round (тільки AddRoundKey)
Результат (новий State):
9 основних раундів
Нам потрібно зробити 9 раундів в кожному з яких виконати такі операції:
- SubBytes
- ShiftRows
- MixColumns
- AddRoundKey
Для прикладу ми розглянемо один раунд, всі інші будуть виконуватись за таким самим принципом.
SubBytes
Використовуючи S-box замінуюємо байти:
Результат:
ShiftRows
Результат:
MixColumns
Цей етап може здаватися не зрозумілим, тому розглянемо його більш детально.
Наш state зараз виглядає так:
Візьмемо з нього перший стовпчик:
Та помножимо його на задану матрицю:
Нові значення будуть обчислені за такими формулами:
Множення на 3:
Множення на 1:
Спростимо формули:
Тепер щоб обчислити множення на два нам потрібно перевести значення з hex до binary.
Це можна зробити за допомогою таблиці:
Наприклад щоб перевести 31 з hex до бінарного коду, ділемо байт на два півбайти та замінюємо значення:
Тепер дивлячись на байт в бінарному вигляді, потрібно зʼясувати чи MSB (старший біт байта, тобто найлівіший біт) 0 чи 1.
Якщо MSB - 0:
Якщо MSB - 1:
Щоб зробити xor нам потрібно перевести байти до бінарного вигляду та залишити одиниці тільки на тих позиціях де є лише 1 одиниця:
Обчислимо множення та отримуємо:
Тепер виконаємо XOR та отримаємо такі значення:
Це і будуть нові значення для нашої колонки. Тепер потрібно виконати множення на статичну матрицю для інших колонок.
Результат:
AddRoundKey
Не забуваємо використовувати новий RoundKey.
Результат:
Тепер нам потрібно повторити ці дії ще 8 раундів.
Final Round
В останьому раунді нам потрібно зробити всього 3 операції:
- SubBytes
- ShiftRows
- AddRoundKey
В результаті наш state буде виглядати так:
Залишилось повернути state до hex-строки:
15af731ceefd383586b97e6d349fd5ecЦе і є наш шифротекст, можемо розшифрувати його за допомогою CyberChef:
Код на Golang
package main
import (
"encoding/hex"
"fmt"
)
var sbox = [256]byte{
0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5,
0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76,
0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0,
0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0,
0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc,
0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15,
0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a,
0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75,
0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0,
0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84,
0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b,
0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf,
0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85,
0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8,
0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5,
0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2,
0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17,
0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73,
0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88,
0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb,
0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c,
0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79,
0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9,
0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08,
0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6,
0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a,
0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e,
0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e,
0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94,
0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf,
0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68,
0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16,
}
var rcon = [10]byte{
0x01, 0x02, 0x04, 0x08, 0x10,
0x20, 0x40, 0x80, 0x1b, 0x36,
}
func addRoundKey(state *[16]byte, roundKey [16]byte) {
for i := 0; i < len(state); i++ {
state[i] ^= roundKey[i]
}
}
func subBytes(state *[16]byte) {
for i := 0; i < 16; i++ {
state[i] = sbox[state[i]]
}
}
func shiftRows(state *[16]byte) {
// Row 1
state[1], state[5], state[9], state[13] = state[5], state[9], state[13], state[1]
// Row 2
state[2], state[6], state[10], state[14] = state[10], state[14], state[2], state[6]
// Row 3
state[3], state[7], state[11], state[15] = state[15], state[3], state[7], state[11]
}
func xtime(x byte) byte {
if x&0x80 != 0 {
return (x << 1) ^ 0x1b
}
return x << 1
}
func multiplication(x byte, y int) byte {
switch y {
case 3:
return xtime(x) ^ x
case 2:
return xtime(x)
default:
return x
}
}
func mixColumns(state *[16]byte) {
for column := 0; column < 4; column++ {
aIndex := column * 4
bIndex := column*4 + 1
cIndex := column*4 + 2
dIndex := column*4 + 3
a := state[aIndex]
b := state[bIndex]
c := state[cIndex]
d := state[dIndex]
// 2 3 1 1
state[aIndex] = multiplication(a, 2) ^ multiplication(b, 3) ^ c ^ d
// 1 2 3 1
state[bIndex] = a ^ multiplication(b, 2) ^ multiplication(c, 3) ^ d
// 1 1 2 3
state[cIndex] = a ^ b ^ multiplication(c, 2) ^ multiplication(d, 3)
// 3 1 1 2
state[dIndex] = multiplication(a, 3) ^ b ^ c ^ multiplication(d, 2)
}
}
func rotateWord(word [4]byte) [4]byte {
return [4]byte{word[1], word[2], word[3], word[0]}
}
func subWord(word [4]byte) [4]byte {
for i := 0; i < 4; i++ {
word[i] = sbox[word[i]]
}
return word
}
func keySchedule(key [16]byte) [11][16]byte {
var roundKeys [11][16]byte
roundKeys[0] = key
for round := 1; round <= 10; round++ {
prev := roundKeys[round-1]
var next [16]byte
word := [4]byte{prev[12], prev[13], prev[14], prev[15]}
word = rotateWord(word)
word = subWord(word)
word[0] ^= rcon[round-1]
for i := 0; i < 4; i++ {
next[i] = prev[i] ^ word[i]
}
for i := 4; i < 16; i++ {
next[i] = prev[i] ^ next[i-4]
}
roundKeys[round] = next
}
return roundKeys
}
func encryptBlock(block [16]byte, key [16]byte) [16]byte {
state := &block
roundKeys := keySchedule(key)
addRoundKey(state, roundKeys[0])
for i := 1; i < 10; i++ {
subBytes(state)
shiftRows(state)
mixColumns(state)
addRoundKey(state, roundKeys[i])
}
subBytes(state)
shiftRows(state)
addRoundKey(state, roundKeys[10])
return *state
}
func main() {
plaintext := "Hello from LD31D"
key := "fajfq43432fdner3"
if len(plaintext) != 16 {
fmt.Println("Plaintext must be 16 bytes long")
return
}
if len(key) != 16 {
fmt.Println("Key must be 16 bytes long")
return
}
fmt.Println("Plaintext:", plaintext)
fmt.Println("Key:", key)
var plaintextBytes [16]byte
copy(plaintextBytes[:], []byte(plaintext))
var keyBytes [16]byte
copy(keyBytes[:], []byte(key))
ciphertext := encryptBlock(plaintextBytes, keyBytes)
hexCiphertext := hex.EncodeToString(ciphertext[:])
fmt.Println("Ciphertext (hex):", hexCiphertext)
}Додаткові ресурси:
- Rijndael Animation
- AES Explained (Advanced Encryption Standard) - Computerphile
- AES steps (SubBytes, ShiftRows, MixColumns)
- AES: How to Design Secure Encryption
Резюме
Сьогодні ми розібралися як працює симетричний блоковий шифр AES та написали власну інмплементацію.
Ця реалізація зовсім не оптимізована та вразлива до Side-Channel атак, вона була створена лише для демонстрації принципа роботи.
Не в якому разі не cлід використовувати її у власних проектах, краще покладатися на вже готові популярні бібліотеки.
Завдання для самоперевірки
- Подивіться додаткові матеріали
- Опишіть які операції виконує AES та яку роль вони виконують
- Спробуйте самостійно зашифрувати якась повідомлення за допомогою звичайного блокнота
- Самостійно напишить код на комфортній для вас мові програмування, використовуючі засвоєні знання
- Проаналізуте cвій код та опишіть які вразливості є в реалізації
- Пошукайте в інтернеті інформацю про Padding та додайте його до своєї реалізації
- Додайте можливіть шифрування декількох блоків
- Додайте можливіть розшифрування шифротексту