"Люди будут использовать его, даже не зная об этом" - Vincent Rijmen

"Я не верю, что когда-нибудь обнаружат атаку, которая позволит читать информацию, зашифрованную Rijndael" - Bruce Schneier

"У нас есть одно критическое замечание к AES: мы не совсем доверяем его безопасности. Что беспокоит нас больше всего в AES, так это его простая структура… Ни один другой блочный шифр не имеет столь простого алгебраического представления. Мы понятия не имеем, ведёт это к атаке или нет, но незнание этого является достаточной причиной, чтобы скептически относиться к использованию AES" - Niels Ferguson

Rijndael (авторы Vincent Rijmen, Joan Daemen) - алгоритм, признанный стандартом шифрования в 2001 году, ныне называемый AES (Advanced Encryption Standard).

"В июне 2003 года Агентство национальной безопасности США постановило, что шифр AES является достаточно надёжным, чтобы использовать его для защиты сведений, составляющих государственную тайну. Вплоть до уровня SECRET было разрешено использовать ключи длиной 128 бит, для уровня TOP SECRET требовались ключи длиной 192 и 256 бит"

Материалов про AES много, и я сразу выделю отличие этой статьи от других:

• приведена реализация шифра в функциональной парадигме;

• рассматривается полная версия Rijndael с 9 вариациями длин блока и ключа, а не урезанный AES до 3 вариаций;

• реализовано шифрование файлов;

• я старался объяснить математическую составляющую для неподготовленного читателя так, чтобы была понятна философия, смыслы и образы происходящего, а не мелкие технические детали;

• использоваться будет Haskell, однако для читателя знание этого языка не требуется, поскольку все конструкции будут пояснены.

Сам я написал это все после прочтения прекрасной книги Курта и в качестве первой своей практики на Haskell. В простоте изложения я буду стараться подражать Курту. Если опытные функциональщики или криптографы посмотрят и критично отнесутся, то будут правы. Я лишь любитель криптографии и функциональной парадигмы, а по складу ума и вовсе гуманитарий.

Целью статьи в первую очередь является изучение ФП, и уже только во вторую - криптографии. Кто впервые слышит про ФП, то кратко скажем, что в нижеследующей реализации:

• отсутствуют изменяемые переменные;

• отсутствуют циклы;

• вместо оператора "if" используются сопоставления с образцом и охранные выражения;

• имеются только "чистые" функции, каждая из которых детерминирована относительно аргументов и не взаимодействует с внешним миром;

• полностью контролируются побочные эффекты;

• программа является не набором команд, а больше похожа на набор математических формул.

Краткая история AES

С 1977 стандартом шифрования был DES (Data Encryption Standard), и под конец века требовал замены как минимум из-за того, что вычислительные мощности значительно увеличились и можно было его взломать полным перебором ключей, это заняло бы 2^56 операций.

Для принятия нового стандарта был организован конкурс AES, куда любой специалист мог прислать свой шифр для кандидатуры.

Требования к кандидатам были следующие:

• блочный шифр - открытые данные разбиваются на блоки, каждый из которых обрабатывается отдельно; длина блока обязана быть 128 бит;

• симметрия - для шифрования и расшифровки используется один и тот же ключ;

• длина ключа может быть 128, 192 или 256 бит;

• все операции эффективно реализуются аппаратно;

• алгоритм не подвергается атакам, известным на момент проведения конкурса;

• отсутствие статистических зависимостей; зашифрованное сообщение должно быть неотличимо от случайного шума;

• свободное распространение алгоритма, отсутствие ограничивающих использование патентов;

• алгоритм должен быть максимально простой, чтобы любой желающий мог самостоятельно его изучить и убедиться в отсутствии бэкдоров.

Было прислано 15 кандидатур, которые в течение нескольких лет всесторонне изучались мировыми криптографами. На многочисленных серверах Sun Ultra несколько месяцев проводились статистические тесты шифров для выявления закономерностей (было отброшено 6 из 15 шифров).

На завершающих конференциях, которые прошли 13 и 14 апреля 2000 года в Нью-Йорке, присутствовали 250 человек, многие из которых приехали из-за рубежа. Результаты голосования для выбора победителя следующие:

• Rijndael: 86 за, 10 против;

• Serpent: 59 за, 7 против;

• Twofish: 31 за, 21 против;

• RC6: 23 за, 37 против;

• MARS: 13 за, 83 против.

Шифр Rijndael стал победителем конкурса AES, и получил в его честь новое имя, как мы и привыкли его сейчас называть. AES используется в HTTPS, беспроводных сетях, биткоине, в технологиях, как LUKS, для шифрования жесткого диска и во многих других сферах. Если вы читаете эту статью в интернете, скорее всего, AES использовался для её доставки на ваш компьютер.

Для AES используется упрощенная версия Rijndael, в которой длина блока ровно 128 бит, в то время как исходный алгоритм может шифровать дополнительно 192 и 256 бит. Мы рассматриваем полную версию алгоритма.

Представление блока данных

На вход алгоритм получает открытый текст и ключ, каждый из которых вне зависимости от другого может принимать длину 16, 24 или 32 байта. Полученные последовательности преобразуются в матрицы размерами 4x4, 4x6 или 4x8. Укладывание последовательности байтов в матрицу происходит по столбцам.

import Data.Word
import Data.ByteString
import Data.Matrix.Storable as DMS
import Data.Vector.Storable as DVS
import Data.Vector.Storable.ByteString
import Data.Vector.Split


byteStringToMatrix :: ByteString -> Matrix Word8
byteStringToMatrix = fromColumns . chunksOf 4 . byteStringToVector

Основными используемыми типами данных являются:

• Word8 - слово из 8 бит или 1 байт, может принимать значения от 0 до 255 или же от 0x00 до 0xff;

• ByteString - последовательность байтов; будет использоваться только для входящих и исходящих данных; например, при бинарном чтении файла его содержимое представляется как ByteString;

• Matrix Word8 - матрица байтов, основной используемый тип алгоритма;

• Vector Word8 - одномерный вектор байтов, используется при рассмотрении отдельных строк или столбцов.

Показанная функция преобразует входящий блок данных в матричное представление, используемое в дальнейшем процессе. Через "::" объявлен тип функции (из последовательности байтов в матрицу). Разберем, как это работает:

• byteStringToVector :: ByteString -> Vector Word8 - конвертация между типами за O(1) без копирования; трактуем область памяти не как байтовую строку, а как вектор байтов;

• chunksOf 4 :: Vector Word8 -> [Vector Word8] - разлом вектора на части, каждая из которых по 4 байта (разбивка на столбцы);

• fromColumns :: [Vector Word8] -> Matrix Word8 - трактовка списка векторов как столбцов и построение по ним матрицы;

• ByteStringToMatrix :: ByteString -> Matrix Word8 - композиция трех вышеизложенных функций; синтаксически композиция происходит справа налево.

В Haskell основным типом для представления последовательности значений является не массив, а односвязный список, обозначаемый квадратными скобочками, так что "[Vector Word8]" обозначает список векторов. Обратное преобразование (из матрицы в байтовую строку) выглядит следующим образом:

matrixToByteString :: Matrix Word8 -> ByteString
matrixToByteString = vectorToByteString . DVS.concat . toColumns

• toColumns :: Matrix Word8 -> [Vector Word8] - извлечение всех столбцов из матрицы;

• DVS.concat :: [Vector Word8] -> Vector Word8 - конкатенация списка векторов в один большой вектор;

• vectorToByteString :: Vector Word8 -> ByteString - преобразование между типами за O(1) без копирования;

• matrixToByteString :: Matrix Word8 -> ByteString - композиция трех вышеизложенных функций.

Замена байтов

Первая рассматриваемая нами операция - замена байтов по заранее составленной таблице SBox.

Sbox представляется как:

import Data.Array as AR


sbox :: Array Word8 Word8
sbox = listArray (0, 255) [
      0x63, 0x7c, 0x77, 0x7b
    , 0xf2, 0x6b, 0x6f, 0xc5
    , 0x30, 0x01, 0x67, 0x2b
               ...
    , 0xbf, 0xe6, 0x42, 0x68
    , 0x41, 0x99, 0x2d, 0x0f
    , 0xb0, 0x54, 0xbb, 0x16
    ]

Чтобы не загромождать статью, я не буду приводить полное представление sbox. О нем стоит понимать, что это массив из 256 элементов, у которого индексами и элементами являются Word8.

Для применения операции к матрице используется следующий код:

subBytes :: Matrix Word8 -> Matrix Word8
subBytes = DMS.map (sbox AR.!)

• sbox AR.! :: Word8 -> Word8 - принимает x, возвращает sbox[x];

• DMS.map func :: Matrix Word8 -> Matrix Word8 - строит новую матрицу, где каждый элемент проходит преобразование "func". В качестве "func" у нас замена по sbox.

Цель SBox - внести нелинейность в алгоритм, накопление изменений, которые нельзя упростить. Если бы он отсутствовал или являлся линейным, то поскольку все остальные операции тоже являются линейными, весь алгоритм являлся бы таковым. А значит, сводимым к простой формуле. Есть хорошая статья "Ломаем модифицированный AES-256" про это.

Сдвиг строк

В этой операции циклически сдвигаются строки:

В первых двух случаях первая строка остается неизменной, вторая циклически сдвигается на один элемент влево, третья - на два элемента влево, четвертая - на три элемента влево. В случае, если размер блока 32 байта, то сдвиги будут на 0, 1, 3 и 4 соответственно.

rotl :: Int -> Vector Word8 -> Vector Word8
rotl n vec
  | 0 <= n && n < ln                     = rest DVS.++ f
  | otherwise                            = rotl (n `mod` ln) vec
  where (f, rest) = DVS.splitAt n vec
        ln = DVS.length vec

• rotl :: Int -> Vector Word8 -> Vector Word8 - функция циклического сдвига влево. Принимает размер сдвига, вектор, и возвращает сдвинутый вектор. Используются охранные выражения для ветвления;

• если размер сдвига меньше, чем размер вектора, то:

• (f, rest) = DVS.splitAt n vec - производит разлом вектора на две части. В первой части будет n элементов, во второй - все остальное. Первую называет f, остальное - rest;

• rest DVS.++ f - меняет части местами и склеивает их; Это будет возвращаемый результат в первом случае охранного выражения;

• otherwise - используется во всех остальных случаях, когда ни одно охранное выражение не подошло; в нашем случае, когда мы хотим сделать циклический сдвиг на большее число элементов, чем есть в векторе, или сдвиг на отрицательное число;

• тогда нужно делать циклический сдвиг не на n, а на остаток от деления n на длину вектора.

• мы знаем, что не будет вызова на на "неправильном" n, и в реальном исполнении всегда будет выполняется первое условие, и рассматривание случая с otherwise хоть и избыточно, но предоставлено для полноты.

Само преобразование матрицы выглядит следующим образом:

shifts :: Int -> [Int]
shifts 4 = [0,1,2,3]
shifts 6 = [0,1,2,3]
shifts 8 = [0,1,3,4]
shifts _ = error "incorrect columns count"

shiftRows :: Matrix Word8 -> Matrix Word8
shiftRows m = fromRows $ zipWith ($) fs $ toRows m
  where fs = map rotl $ shifts (cols m)

• cols :: Matrix Word8 -> Int - принимает матрицу, возвращает число столбцов в ней;

• shifts :: Int -> [Int] - принимает число столбцов, возвращает список "на какое число элементов должна быть сдвинута каждая строка";

• map rotl :: [Int] -> [Vector Word8 -> Vector Word8] - принимает список "на какое число элементов должна быть сдвинута каждая строка", мэпит это с функцией rotl и получается "список уникальных функций, каждая из которых делает свой сдвиг";

• Этот промежуточный результат называем fs :: [Vector Word8 -> Vector Word8], он является списком функций, каждая из которых принимает вектор и возвращает вектор.

• toRows :: Matrix Word8 -> [Vector Word8] - разбивает матрицу на строки;

• zipWith ($) fs :: [Vector Word8] -> [Vector Word8] - для каждой строки применяет соответствующую ей функцию сдвига;

• fromRows :: [Vector Word8] -> Matrix Word8 - склеивает строки обратно в матрицу.

Про error

В функции shifts может генерироваться ошибка, но это никак не указано в типовой аннотации. Некоторые программисты на Haskell такое не любят, и даже не используют функции из Prelude из-за этого, предпочитая более безопасные решения. Для простоты изложения я буду допускать подобное, и это встретится ещё не раз.

Добавление раундового ключа

На вход операции дается две матрицы: шифруемый текст, и раундовый ключ такого же размера. Результатом операции является матрица с поэлементным XOR между исходными.

Реализация на Haskell:

addRoundKey :: Matrix Word8 -> Matrix Word8 -> Matrix Word8
addRoundKey = DMS.zipWith xor

Можно думать, что происходит "втирание" ключа в открытый текст.

Смешивание столбцов

Простые преобразования на этом заканчиваются. Дальше идёт часть, связанная с математикой. Я постараюсь изложить минимум, требуемый для понимания.

Кратко про поля

Конечные поля - это конечные множества, на которых определены операции +,-,*,/ замкнутые относительно поля, не выходящие за его пределы, и имеющие различные полезные свойства, например дистрибутивность умножения относительно сложения: (a + b) * c = ac + bc; или ассоциативность умножения: a(bc) = (ab)c. Аксиом и свойств достаточно много, прочитать можно на Википедии. Чаще всего нужно придумать неинтуитивные операции сложения и умножения, которые значительно отличаются от обычных, чтобы операции удовлетворяли полю.

GF2

Поле GF2 состоит из двух элементов - из нуля и единицы. Операции сложения и умножения определены следующим образом:

Из нескучного 1+1=0, однако все аксиомы и свойства полей выполняются.

GF256

В GF256 256 элементов и представляются они как полиномы (многочлены), степени не большей семи, коэффициентами которых являются элементы GF2.

Примеры элементов GF256:

Не являются элементами GF256:

Элементы GF256 изоморфны байтам:

Данное представление используется в алгоритме, байты трактуются как элементы поля.

Сложение в GF256

Операция сложения полиномов в GF256 эквивалентна обычному для полиномов, но сложение коэффициентов происходит в GF2, а мы помним, что для них 1+1=0, и на самом деле это просто XOR.

От этого для байтов операция сложения в поле полностью эквивалентна XOR.

gfSum :: Word8 -> Word8 -> Word8
gfSum = xor

Умножение в GF256

Для умножения полиномов в GF256, сначала происходит обычное умножение полиномов (коэффициенты суммируются по правилам GF2). Мог получиться полином, выходящий за границы поля (степени большей семи). Нужно взять его по модулю какого-либо неприводимого многочлена, для AES этот многочлен фиксированный x^8 + x^4 + x^3 + x + 1 (0x11b)

Преобразование столбца

Теперь, узнав про GF256, можно переходить к описанию MixColumns. Каждый столбец таблички рассматривается как вектор в пространстве GF256^4, проходящий обратимое линейное преобразование. "+" и "*" не между числами, а элементами поля.

Маленькие числа на матрице были выбраны специально для оптимизации работы и реализаций. Для обратного преобразования нужно выполнить умножение на обратную матрицу.

Программная реализация умножения в GF256

Напишем функцию xtime, которая умножает произвольный элемент на x (на 0x02). Умножение на два эквивалентно байтовому сдвигу влево. Если мы сдвинули, и элемент остался в пределах поля, то умножение закончено. Если один бит вышел за пределы байта, то наш полином нужно взять по модулю, но в нашем простейшем случае можно будет просто вычесть полином m, то есть сделать xor с 0x11b (или для Word8 просто с 0x1b).

xtime :: Word8 -> Word8
xtime b
  | b >= 0x80     = (b `shiftL` 1) `xor` 0x1b
  | otherwise     =  b `shiftL` 1

Для ветвления здесь используются охранные выражения. Все числа, в которых старший бит является единицой, можно записать под условие "b >= 0x80". В этом случае идейно после сдвига берем остаток от деления, программно производим XOR. В остальных случаях делаем обычный сдвиг влево.

Для умножения на x^n нужно повторить xtime n раз:

xntime :: Int -> Word8 -> Word8
xntime n = foldr (.) id $ replicate n xtime

В haskell нет циклов, чтобы применить какую-либо функцию n раз. Вместо этого я сделал следующее решение:

• replicate n xtime - создает список, в котором n раз будет повторена функция xtime. Например, для n = 3, будет [xtime, xtime, xtime];

• id - функция, ничего не делающая. Для любого x, id x = x;

• список повторенных функций мы сворачиваем, используя для свёртки "оператор композиции", и в качестве начального значения аккумуляра функцию id.

id является нейтральным элементом для композиции, как 0 является нейтральным элементом для сложения, и как 1 нейтральным элементом для умножения. Если бы мы хотели свернуть список чисел с помощью суммы, использовался бы код "foldr (+) 0 [1, 2, 3, 4] == 10", где для свертки используется операция сложения, и начальное значения аккумуляра 0. Для умножения код был бы "foldr (*) 1 [1, 2, 3, 4] == 24". Аналогично сворачивается композиция, и [xtime, xtime, xtime] преобразуется в xtime^3 x = xtime(xtime(xtime(x))). Этот прием я использую в дальнейшем.

Для умножения на произвольный многочлен, например на (x^5 + x^3), нужно посчитать xntime 5, xntime 3 и сложить (проксорить) результаты. Для mixColumn умножать приходится только на 3 числа, одно из которых еще и 0x01. Для обратного преобразования еще на несколько констант. Так что достаточно будет реализовать лишь частичное умножение.

gfMul :: Word8 -> Word8 -> Word8
gfMul 0x01 p = p
gfMul 0x02 p = xtime p
gfMul 0x03 p = xtime p `gfSum` p
gfMul 0x09 p = xntime 3 p `gfSum` p
gfMul 0x0b p = xntime 3 p `gfSum`    xtime p `gfSum` p
gfMul 0x0d p = xntime 3 p `gfSum` xntime 2 p `gfSum` p
gfMul 0x0e p = xntime 3 p `gfSum` xntime 2 p `gfSum` xtime p
gfMul    _ _ = error "Rijndael not specified"

В данном коде я разложил все числа на бинарное представление, и подсчитал для каждого свою операцию умножения. Умножение на другие константы не предусмотрено.

Реализация MixColumns

Научившись достаточно умножать, можем написать полный код для MixColumns:

gfScalar :: [Word8] -> [Word8] -> Word8
gfScalar v1 v2 = foldl gfSum 0x00 $ zipWith gfMul v1 v2

mixColumnsTransform :: Vector Word8 -> Vector Word8
mixColumnsTransform column = DVS.fromList [y1, y2, y3, y4]
  where xs = DVS.toList column
        y1 = gfScalar [0x02, 0x03, 0x01, 0x01] xs
        y2 = gfScalar [0x01, 0x02, 0x03, 0x01] xs
        y3 = gfScalar [0x01, 0x01, 0x02, 0x03] xs
        y4 = gfScalar [0x03, 0x01, 0x01, 0x02] xs

mixColumns :: Matrix Word8 -> Matrix Word8
mixColumns = fromColumns . map mixColumnsTransform . toColumns

• gfScalar : [Word8] -> [Word8] -> Word8 - реализует скалярное произведение в GF256. Принимает два списка Word8, возвращает единичный Word8. Это делается с помощью:

• zipWith gfMul :: [Word8] -> [Word8] -> [Word8] - склеивает два спика, попарно умножая соответствующие элементы;

• foldl gfSum 0x00 :: [Word8] -> Word8 - сворачивает список с помощью операции gfSum, в качестве начального значения аккумуляра 0x00;

• mixColumnsTransform :: Vector Word8 -> Vector Word8 - производит трансформацию для одного столбца. Принимает столблец, возвращает смешанный столблец;

• xs = DVS.toList :: Vector Word8 -> [Word8] - распаковка столбца из типа данных Vector в спискок;

• yi = gfScalar [...] xs :: Word8 - рассчитывает каждый из новых байтов;

• DVS.fromList :: [Word8] -> Vector Word - упаковка новых байтов обратно в Vector Word8;

• mixColumns :: Matrix Word8 -> Matrix Word8 - операция над всей матрицей. Разбивает матрицу на столбцы, к каждому применяет преобразование, склеивает все обратно.

Шифрование блока

На текущий момент мы разобрали 4 операции над матрицей. 3 из них являются обычными преобразованиями, одна требует раундовый ключ.

Псевдокод для общего императивного алгоритма шифрования выглядит так:

Cipher(state, key):
    roundKeys <- expandKey

    addRoundKey
    for rounds:
        subBytes
        shiftRows
        mixColumns
        addRoundKey

    subBytes
    shiftRows
    addRoundKey

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

Объявим функцию с аннотацией:

buildRoundKeys :: Matrix Word8 -> Int -> [Matrix Word8]

которая на выходе генерирует раундовые ключи, но реализуем её после. Эта функция принимает ключ в матричной форме, количество столбцов в открытом блоке, а возвращает список матриц, которые являются раундовыми ключами. Напишем пока общий процесс шифрования.

Для начала, сделаем функцию, которая принимает раундовый ключ, и возвращает уникальную функцию раунда c вшитим в нее ключом:

buildEncryptRound :: Matrix Word8 -> (Matrix Word8 -> Matrix Word8)
buildEncryptRound key = addRoundKey key . mixColumns . shiftRows . subBytes

Функция для шифрования блока:

encryptBlock :: Matrix Word8 -> Matrix Word8 -> Matrix Word8
encryptBlock key block = localEncrypt block
  where roundKeys = buildRoundKeys key (DMS.cols block)

        firstKey = head roundKeys
        mainKeys = init $ tail roundKeys
        lastKey = last roundKeys

        pre = addRoundKey firstKey
        main = foldl (.) id (map buildEncryptRound $ reverse mainKeys)
        post = addRoundKey lastKey . shiftRows . subBytes

        localEncrypt = post . main . pre

• encryptBlock :: Matrix Word8 -> Matrix Word8 -> Matrix Word8 - является глобальным процессом шифрования блока. Принимает открытый текст и ключ в матричной форме, возвращает зашифрованный текст в матричной форме;

• roundKeys = buildRoundKeys key (DMS.cols block) - С помощью пока неопределенной функции генерирует раундовые ключи; имеет тип [Matrix Word8], то есть список матриц;

• firstKey = head roundKeys - выделяет первый (нулевой) раундовый ключ; имеет тип Matrix Word8;

• lastKey = last roundKeys - аналогично выделяет последний раундовый ключ;

• mainKeys = init $ tail roundKeys - выделяет все ключи, кроме первого и последнего; mainKeys имеет тип [Matrix Word8];

• pre :: Matrix Word8 -> Matrix Word8 - предобработка перед основными раундами; в императивном псевдокоде это та часть, которая выполняет преобразования после расширения ключа, но до цикла for;

• post :: Matrix Word8 -> Matrix Word8 - аналогичная часть, которая в императивном псевдокоде делает преобразования после цикла for;

• reverse mainKeys :: [Matrix Word8] - переворачивает список, поскольку дальнейшая композиция происходит справа налево, и первый ключ должен быть в правой части, а последний ключ - в левой;

• map buildEncryptRound :: [Matrix Word8] -> [Matrix Word8 -> Matrix Word8] - на ключи мэпит buildEncryptRound, которая из ключа создает функцию раунда; мы имеем список функций раундов со вшитыми в них ключами;

• foldl (.) id :: [Matrix Word8 -> Matrix Word8] -> (Matrix Word8 -> Matrix Word8) - объединяем все основные раунды в одну композицию, и называем main; на императивном псевдокоде эта часть соответствует всему циклу for;

• localEncrypt :: Matrix Word8 -> Matrix Word8 - функция зашифровки с вшитым в нее ключом; принимает открытый текст, возвращает зашифрованный;

• encryptBlock является применением localEncrypt к открытому тексту.

Расширение ключа

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

Пора определится с количеством раундов. Оно зависит от длины блока и ключа:

calcNr :: Int -> Int -> Int
calcNr 4 4 = 10
calcNr 4 6 = 12
calcNr 4 8 = 14
calcNr 6 4 = 12
calcNr 6 6 = 12
calcNr 6 8 = 14
calcNr 8 4 = 14
calcNr 8 6 = 14
calcNr 8 8 = 14
calcNr _ _ = error "Rijndael is not supported."

Ниже предоставлена управляющая функция для расширения ключа. Она рассчитывает число раундов (nr), считает, сколько столбцов должно быть в расширенной гармошке (expandedColumnsCount), создает эту гармошку (expandedKey), и разбивает её на раундовые ключи (splitRoundKeys).

buildRoundKeys :: Matrix Word8 -> Int -> [Matrix Word8]
buildRoundKeys key nb = roundKeys
  where nk = DMS.cols key
        nr = calcNr nb nk
        expandedColumnsCount = nb * (nr + 1)
        expandedKey = expandKey key expandedColumnsCount nb
        roundKeys = splitRoundKeys expandedKey nb

Для удобства работы со столбцами, сделаем синоним типа

type Column = Vector Word8

• nb - число столбцов в открытом тексте;

• nk - число столбцов в ключе;

• nr - число раундов;

• expandedColumnsCount - число столбцов в расширенной гармошке;

• expandedKey :: [Column] - расширенная гармошка; математически является матрицей 4 на expandedColumnsCount, программно записывается как список столбцов;

• roundKeys :: [Matrix Word8] - разбитая на подматрицы гармошка.

Код для расширения ключа:

expandKey :: Matrix Word8 -> Int -> Int -> [Column]
expandKey k stop nb = expanded
  where columns = DMS.toColumns k
        expanded = hexp 4 stop nb (reverse columns)

hexp :: Int -> Int -> Int -> [Column] -> [Column]
hexp ln stop nb columns
  | ln == stop                 = columns
  | ln `mod` nb == 0           = nextStep (case1 : columns)
  | ln `mod` nb == 4 && nb > 6 = nextStep (case2 : columns)
  | otherwise                  = nextStep (case3 : columns)
  where
    l1 = head columns
    l2 = columns !! 3
    case1 = (subBytesColumn . rotColumn) l1 `xorc` l2 `xorc` rcon (ln `div` nb)
    case2 = subBytesColumn l1 `xorc` l2
    case3 = l1 `xorc` l2
    nextStep = hexp (ln + 1) stop nb

• expandKey принимает ключ в матричной форме, количество столбцов, когда пора прекратить генерацию, и число столбцов в открытом блоке (nb); возвращает список столбцов;

• expandKey вызывает вспомогательную функцию hexp (help expand), которая выполняет всю сложную работу по расширению.

Основным используемым типом данных является [Column], то есть список столбцов. Для списков за O(1) происходит добавление в голову, чем мы и будем пользоваться. Будем считать, что голова нашего списка находится в правой части, а хвост - в левой. Расширение будет происходить в правую часть, то есть в голову. Поэтому перед вызовом hexp нужно было развернуть список, и после операции список тоже будет развернут обратно.

В дальнейшем тексте часто будет использоваться слово "аккумуляр". Оно означает промежуточное, накапливающее значение. Когда я говорю гармошка-аккмуляр, я буду иметь ввиду промежуточный результат, который происходит где-то посередине.

hexp принимает:

• 1 параметр - длину текущей гармошки-аккумуляра;

• 2 параметр - точку остановки генерации;

• 3 параметр - nb, число столбцов в открытом тексте;

• 4 параметр columns - текущая гармошка-аккумуляр;

• возвращает - расширенную гармошку.

Правила для расширения:

• Для ветвления используются охранные выражения. Если текущая длина совпадает с точкой остановки, то возвращает аккумуляр (1 условие);

• nextStep является функцией для вызова следующей итерации; ожидает аккумуляр с новым добавленным столбцом;

• l1 является самым правым на текущей момент столбцом;

• l2 является третьем с правой стороны столбцом;

• в большинстве случаев (условие othrwise), каждый следующий столбец является ксором между столбцами l1 и l2; в этом случае новый столбец определяется как case3; новая итерация происходит как nextStep (case : columns), то есть с добавлением в голову аккумуляра этого столбца (":" - оператор для добавление в голову списка элемента);

• если начат новый раундовый ключ (ln mod nb == 0, второе условие), то дополнительно делается subBytes и xor со столбцом из массива констант-столбцов, определяется как case1;

• если nb достаточно большой (третье условие), то на каждом четвертом столбце раундового ключа дополнительно делается subBytes для l1; опредлено как case2.

Вспомогательные функции:

rc :: Int -> Word8
rc 1 = 0x01
rc n = xtime $ rc (n - 1)

rcon :: Int -> Column
rcon x = DVS.fromList [rc x, 0x00, 0x00, 0x00]

subBytesColumn :: Column -> Column
subBytesColumn = DVS.map (sbox AR.!)

rotColumn :: Column -> Column
rotColumn v = rest DVS.++ f
  where (f, rest) = DVS.splitAt 1 v

xorc :: Column -> Column -> Column
xorc = DVS.zipWith xor

• rcon - массив столбцов констант; в нашем случае реализован как фунцкия, принимающая индекс; правила построения описаны в коде;

• остальные функции просты и не требуют дополнительного объяснения;

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

splitRoundKeys :: [Column] -> Int -> [Matrix Word8]
splitRoundKeys expanded nb = keys
  where columns = reverse expanded
        splited = chunksOf nb columns
        keys = map DMS.fromColumns splited

Тестирование

Мы написали весь код для шифрования блока, и можем его протестировать.

testEncryptBlock :: Test
testEncryptBlock = TestCase $ assertEqual message expected out
  where message = "Test encryptBlock"
        input = byteStringToMatrix $ pack [
            0x32, 0x43, 0xf6, 0xa8,
            0x88, 0x5a, 0x30, 0x8d,
            0x31, 0x31, 0x98, 0xa2,
            0xe0, 0x37, 0x07, 0x34
          ]
        key = byteStringToMatrix $ pack [
            0x2b, 0x7e, 0x15, 0x16,
            0x28, 0xae, 0xd2, 0xa6,
            0xab, 0xf7, 0x15, 0x88,
            0x09, 0xcf, 0x4f, 0x3c
          ]
        expected = byteStringToMatrix $ pack [
            0x39, 0x25, 0x84, 0x1d,
            0x02, 0xdc, 0x09, 0xfb,
            0xdc, 0x11, 0x85, 0x97,
            0x19, 0x6a, 0x0b, 0x32
          ]
        out = encryptBlock key input

Значения взяты из примеров с описания стандарта.

$ stack test
...
RijndaelHaskell> test (suite: RijndaelHaskell-test)
Cases: 11  Tried: 11  Errors: 0  Failures: 0
RijndaelHaskell> Test suite RijndaelHaskell-test passed
Completed 2 action(s).

Расшифровка

Над открытым текстом мы проделали большое количество изменений. Можно представить, что они скопились как большой стек, где в самом низу исходный блок. Для расшифровки, нужно проделать обратные операции в обратном порядке, то есть поэтапно снимать элементы стека изменений.

Так подробно можно их уже не описывать, поэтому просто оставляю код.

invSubBytes :: Matrix Word8 -> Matrix Word8
invSubBytes = DMS.map (invsbox AR.!)

rotr :: Int -> Vector Word8 -> Vector Word8
rotr n vec
  | 0 <= n && (n < DVS.length vec)       = f DVS.++ rest
  | otherwise                            = rotr (n `mod` ln) vec
  where (rest, f) = DVS.splitAt (ln - n) vec
        ln = DVS.length vec

invShiftRows :: Matrix Word8 -> Matrix Word8
invShiftRows m = fromRows $ zipWith ($) fs $ toRows m
  where fs = map rotr $ shifts (cols m)

invMixColumnsTransform :: Vector Word8 -> Vector Word8
invMixColumnsTransform column = DVS.fromList [y1, y2, y3, y4]
  where xs = DVS.toList column
        y1 = gfScalar [0x0e, 0x0b, 0x0d, 0x09] xs
        y2 = gfScalar [0x09, 0x0e, 0x0b, 0x0d] xs
        y3 = gfScalar [0x0d, 0x09, 0x0e, 0x0b] xs
        y4 = gfScalar [0x0b, 0x0d, 0x09, 0x0e] xs

invMixColumns :: Matrix Word8 -> Matrix Word8
invMixColumns = fromColumns . map invMixColumnsTransform . toColumns

Для addRoundKey отдельной обратной операции не требуется, его повторное применение и есть обратная операция по свойствам XOR.

buildDecryptRound :: Matrix Word8 -> (Matrix Word8 -> Matrix Word8)
buildDecryptRound key = invMixColumns . addRoundKey key . invSubBytes . invShiftRows

decryptBlock :: Matrix Word8 -> Matrix Word8 -> Matrix Word8
decryptBlock key block = decrypt block
  where roundKeys = buildRoundKeys key block

        firstKey =  head roundKeys
        mainKeys = init $ tail roundKeys
        lastKey = last roundKeys

        pre = addRoundKey lastKey
        main = foldl (.) id (map buildDecryptRound mainKeys)
        post = addRoundKey firstKey . invSubBytes . invShiftRows

        decrypt = post . main . pre

Потоковое шифрование

Научившись шифровать фиксированный блок (16, 24 или 32 байта), можно перейти к шифрованию произвольной последовательности. Наша цель - написать функцию с аннотацией Key -> ByteString -> ByteString, принимающая ключ и открытый текст произвольной длины, и возвращающая зашифрованный текст. Основным типом данных будут ленивые, а не энергичные байтовые строки (Data.ByteString.Lazy). Нужно постараться написать функцию, работающую за один проход. Тогда в теории, ленивый рантайм Haskell сможет зашифровывать файлы больше, чем объем оперативной памяти, в каждый момент времени загружая только дефолтный чанк в несколько килобайт, причем без явных действий для этого с нашей стороны.

Для простоты дальнейшей реализации, обработку файлов сделаем только для AES-128, в котором и длина блока, и длина ключа 128 бит.

blockSize :: Int
blockSize = 16

keySize :: Int
keySize = 16

Дополнение последовательности

Сперва последовательность делают кратной длине блока. Никакого стандарта для этого нет, и в каждой реализации может быть свой алгоритм. Я буду дописывать нули, и в конце оставлю число, сколько всего байтов было добавлено. Сделаем синонимы типов, которые вносят читабельность, но не более.

type Block          = Vector Word8
type KeyMatrix      = Matrix Word8
type UnpaddedBlocks = [Block]
type PaddedBlocks   = [Block]

• данные будут разбиваться на блоки по 16 байт. Каждый такой блок и будет принадлежать к синониму Block;

• UnpaddedBlocks обозначает данные, в которых не была произведения функция добавления; все кроме последнего блока имеют объем 16 байт, последний может быть неполным;

• PaddedBlocks обозначает дополненные данные; это список блоков, каждый из которых ровно 16 байт.

byteStringToBlocks :: BSL.ByteString -> UnpaddedBlocks
byteStringToBlocks = L.unfoldr extractBlock

extractBlock :: BSL.ByteString -> Maybe(Block, BSL.ByteString)
extractBlock b
  | BSL.null b            = Nothing
  | otherwise             = Just (block, rest)
  where (t, rest) = BSL.splitAt blockSize b
        block = byteStringToVector $ BSL.toStrict t

• byteStringToBlocks :: BSL.ByteString -> UnpaddedBlocks - разбивает ленивую строку на блоки, не делая дополнения в конец; это реализуется с помощью:

• extractBlock :: BSL.ByteString -> Maybe(Block, BSL.ByteString) - функция для извлечения одного блока из последовательности; принимает последовательность, возвращает пару, где первым элементов является изъятый блок, вторым - оставшаяся последовательность;

• разделение происходит с помощью Data.ByteString.Lazy.splitAt blockSize;

• изъятый блок конвертируется в Vector Word8 с помощью (byteStringToVector . BSL.toStrict);

• Функция использует обёртку Maybe(Just/Nothing); для пустой последовательности будет возвращен Nothing, во всех остальных случаях "Just что-то";

• unfoldr используя функцию для изъятия одного блока разобьет всю последовательность на блоки, пока не дойдет до Nothing;

Обратное преобразование проще:

blocksToByteString :: [Block] -> BSL.ByteString
blocksToByteString blocks = BSL.concat $ map (BSL.fromStrict . vectorToByteString) blocks

• map (BSL.fromStrict . vectorToByteString) :: Block -> BSL.ByteString - каждый блок конвертирует в ленивую байтовую строку;

• BLS.concat :: [BSL.ByteString] -> BSL.ByteString - конкатенирует все строки.

Реализуем добавление/удаление хвоста:

buildTail :: Block -> Block
buildTail b
  | ln < blockSize               = b <> zeros <> cnt
  | otherwise                    = error "block should be small"
  where toAdd = blockSize - ln 
        zeros = DVS.replicate (toAdd - 1) 0
        cnt = DVS.singleton $ fromIntegral toAdd
        ln = DVS.length b

deleteTail :: Block -> Block
deleteTail b = DVS.take toTake b
  where cnt = fromIntegral (DVS.last b)
        toTake = DVS.length b - cnt

• buildTail :: Block -> Block - принимает последний, неполный блок, и делает для него дополнение; для полных блоков будет вызвана ошибка;

• b :: Vector Word8 - исходный блок

• zeros :: Vector Word8 - содержит только нули;

• cnt :: Vector Word8 - в этом векторе ровно один элемент, обозначающий общее число добавленных байт;

• результат является конкатенацией b, zeros, cnt;

• deleteTail :: Block -> Block - удаляет из блока количество байтов, хранимое в самом правом байте блока.

Перейдем к обработке всей последовательности:

pad :: UnpaddedBlocks -> PaddedBlocks
pad []                              = [buildTail DVS.empty]
pad [x] | DVS.length x < blockSize  = [buildTail x]
pad [x] | DVS.length x == blockSize = x : pad []
pad (x:xs)                          = x : pad xs

• Если раскрыть синонимы, то преобразования имеют аннотацию [Block] -> [Block], то есть преобразуют списки;

• для ветвления используются не охранные выражения, а сопоставления с образцом;

• pad [] = [buildTail DVS.empty] - если нужно сделать добавление к пустой последовательности, то строим хвост от пустого блока и возвращаем его;

• pad [x] | DVS.length x < blockSize = [buildTail x] - если мы достигли последнего блока, и он оказался неполным, то дополняем его и возвращаем;

• pad [x] | DVS.length x == blockSize = x : pad [] - если мы достигли последнего блока, и он оказался полным, тогда дополнять его не будем, и присоединим к нему pad от пустой последовательности;

• pad (x:xs) = x : pad xs - если мы обрабатываем не последний блок, то перекладываем добавление на следующие элементы.

В обратную сторону:

unpad :: PaddedBlocks -> UnpaddedBlocks
unpad []     = undefined
unpad [x]    = [deleteTail x]
unpad (x:xs) = x : unpad xs

• unpad [] = undefined - удаление хвоста из пустой последовательности неопредлено; должен быть хотя бы один блок;

• unpad [x] = [deleteTail x] - если мы достигли последний элемент, то удаляем из него хвост и возвращаем его;

• unpad (x:xs) = x : unpad xs - если элемент не последний, то перекладываем удаление на следующие элементы.

По задумке, функции ленивы и работают за один проход, от этого добавление и удаление хвоста произойдет только тогда, когда шифрование и расшифровка достигнет последнего блока.

Режимы шифрования

На текущий момент, любая входящая последовательность дополняется и разбивается на блоки по 16 байт. Можно зашифровать их всех одним ключом, и это будет называться ECB режимом, и иметь следующую проблему:

На больших данных видно одинаковые блоки. Для исправления этого недочета есть альтернативные режимы, например ксорить каждый следующий блок с зашифрованный предыдущем. Но я буду использовать CTR (Counter Mode), который каждый блок перед шифрованием ксорит с его порядковым номером в последовательности блоков.

ctrMask :: Word64 -> Vector Word64
ctrMask n = DVS.fromList [0, n]

ctrMode :: Word64 -> PaddedBlocks -> PaddedBlocks
ctrMode _ [] = []
ctrMode k (x8:xs) = m8 : ctrMode (k + 1) xs
  where x64 = DVS.unsafeCast x8 :: Vector Word64
        m64 = DVS.zipWith xor x64 (ctrMask k) :: Vector Word64
        m8 = DVS.unsafeCast m64 :: Vector Word8

• ctrMask :: Word64 -> Vector Word64 - принимает порядковый номер, и возвращает ctr-маску для этого порядкового номера; она является вектором, в котором будет два Word64, в сумме дающие 128 бит, то есть размер блока;

• ctrMode :: Word64 -> PaddedBlocks -> PaddedBlocks - принимает начальное значение для нумерации блоков, дополненную последовательность, и возвращает модифицированную дополненную последовательность;

• ctrMode _ [] = [] - остановка функции; при пустой последовательности ничего не делает;

• ctrMode k (x8:xs) - парсинг аргументов. k - начальное значение для нумерации блоков; x8 - первый блок; xs - остальные блоки;

• x64 = DVS.unsafeCast x8 - за O(1) без копирования, блок трактуется не как Vector Word8, а Vector Word64;

• m64 = DVS.zipWith xor x64 (ctrMask k) - на больших регистрах проводится XOR с маской;

• m8 = DVS.unsafeCast m64 - результат обратно без копирования трактуется из Vector Word64 в Vector Word8;

• m8 : ctrMode (k + 1) xs - для списка блоков модифицируется первый блок, и рекурсивно вызывается для остальных в последовательности, увеличив k на 1.

Функция шифрования

Объединяем всё в общую композицию:

preEncrypt :: Word64 -> BSL.ByteString -> PaddedBlocks
preEncrypt = ctrMode 0x00 . pad . byteStringToBlocks

encryptBlocks :: KeyMatrix -> PaddedBlocks -> PaddedBlocks
encryptBlocks key = map (matrixToVector . encryptBlock key . vectorToMatrix)

encryptData :: KeyMatrix -> BSL.ByteString -> BSL.ByteString
encryptData key = blocksToByteString . encryptBlocks key . preEncrypt

• preEncrypt - дополняет данные и вводит CTR;

• encryptBlocks - производит шифрование списка блоков;

• encryptData - функция для шифрования произвольной последовательности; принимает ключ и ленивую байтовую строку, являющуюся открытым текстом; в нее может передаваться хоть как последовательности из 1-2 байтов, так и очень большие.

Вспомогательные функции:

vectorToMatrix :: Vector Word8 -> Matrix Word8
vectorToMatrix = DMS.fromColumns . chunksOf 4

matrixToVector :: Matrix Word8 -> Vector Word8
matrixToVector = DVS.concat . DMS.toColumns

Давайте попробуем впервые что-то зашифровать в ghci:

ghci> testKey = byteStringToMatrix $ B.pack [1..16]
ghci> message = BSL.pack [42, 42, 42]
ghci> enc = encryptData testKey message
ghci> enc
"=m\157\f6Y\SO\EOT8#1\231\229\244\209\ETX"
ghci> BSL.unpack enc
[61,109,157,12,54,89,14,4,56,35,49,231,229,244,209,3]

• BSL.pack :: [Word8] -> BSL.ByteString - упаковка списка байтов в ленивую байтовую строку;

• BSL.unpack :: BSL.ByteString -> [Word8] - распаковка;

• testKey - тестовый ключ, содержит байты от 1 до 16;

• message - сообщение, содержит байты "42 42 42";

• enc - зашифрованное с помощью testKey сообщение.

Как видно, получились непонятные символы, которые для наглядности были последней командой распакованы в десятичное представление.

Для расшифровки проделываем обратные операции в обратном порядке:

decryptBlocks :: KeyMatrix -> PaddedBlocks -> PaddedBlocks
decryptBlocks key = map (matrixToVector . decryptBlock key . vectorToMatrix)

postDecrypt :: PaddedBlocks -> BSL.ByteString
postDecrypt = blocksToByteString . unpad . ctrMode 0x00

decryptData :: Word64 -> KeyMatrix -> BSL.ByteString -> BSL.ByteString
decryptData key = postDecrypt . decryptBlocks key . byteStringToBlocks

Расшифровываем исходное сообщение:

ghci> dec = decryptData testKey enc
ghci> B.unpack dec
[42,42,42]

Выходим в мир

До текущего момента все наши функции были чистыми, и не взаимодействовали с внешним миром, как и принуждает в своем стиле писать Haskell. Напишем небольшую обертку для приема и записи файлов.

Для начала, спросим у пользователя пароль, содержащий ровно 16 символов. В реальном применении используется хеш, чтобы пароль был произвольной длины.

passwordToMatrix :: String -> KeyMatrix
passwordToMatrix s
  | length s == keySize = (byteStringToMatrix . BC.pack) s
  | otherwise           = error $ "Пароль должен содержать ровно "
                              ++ show keySize ++ " символов."

getPassword :: IO KeyMatrix
getPassword = do
  putStr "Введите пароль (16 символов): "
  hFlush stdout
  passwordToMatrix <$> getLine

• passwordToMatrix преобразует строку в матрицу, генерирует ошибку при неправильных данных;

• getPassword проводит интерактивный диалог с пользователем; возвращает IO KeyMatrix, что означает матрицу, полученную из внешнего мира, этот тип данных не равен обычному KeyMatrix, и требует обработки с помощью монад.

Напишем функцию main для исполняемого файла haes-encrypt:

main :: IO ()
main = do
  (inputFile:_) <- getArgs
  let outputFile = "enc_" ++ inputFile 
  key <- CTR.getPassword

  content <- BSL.readFile inputFile
  let encrypted = CTR.encryptData key content
  BSL.writeFile outputFile encrypted

• входящий файл парсится из аргументов командной строки;

• имя зашифрованного файла содержит приставку "enc_";

• спрашивается пароль в интерактивном диалоге с пользователем;

• content - ленивая байтовая строка, содержащая входящий файл;

• encrypted - зашифрованная ленивая байтовая строка;

• BSL.writeFile - записываем всё в файл.

Поскольку все наши функции работают за один проход, то весь процесс автоматически будет происходить по чанкам, и в единый момент времени в оперативной памяти будет сохранен только он.

Аналогично функция main для исполняемого файла haes-decrypt:

main :: IO ()
main = do
  (inputFile:_) <- getArgs
  let outputFile = "dec_" ++ inputFile 
  key <- CTR.getPassword

  content <- BSL.readFile inputFile
  let decrypted = CTR.decryptData key content
  BSL.writeFile outputFile decrypted

Смотрим как работает

$ dd if=/dev/zero of=./zeros bs=128 count=1
$ haes-encrypt zeros
Введите пароль (16 символов): 1234567887654321

$ hexdump enc_zeros 
0000000 3c31 15e7 0de7 13d9 3b11 cad2 e53a f0f6
0000010 e3b5 9a31 d756 7786 4f59 d573 d8ef 67b5
0000020 ed1a e342 2fb0 95b2 f4bf 159d a487 1e16
0000030 7afd 6ec2 3e9a 1d39 4646 5242 4b12 82ec
0000040 bb42 74ab 296a 5f68 ba28 8307 e544 87da
0000050 7f26 2604 aa95 0ccf 26a4 eef9 19d4 74b2
0000060 e482 990b ac99 8116 d1c2 e36a cc72 595a
0000070 8a78 df9a e6df 821b b60f 3130 425d 382f
0000080 3e43 9307 aa48 0227 7bae 2bf6 dba7 8b06

$ haes-decrypt enc_zeros
Введите пароль (16 символов): 1234567887654321
$ hexdump -v dec_enc_zeros                                                                                                                                                                     
0000000 0000 0000 0000 0000 0000 0000 0000 0000
0000010 0000 0000 0000 0000 0000 0000 0000 0000
0000020 0000 0000 0000 0000 0000 0000 0000 0000
0000030 0000 0000 0000 0000 0000 0000 0000 0000
0000040 0000 0000 0000 0000 0000 0000 0000 0000
0000050 0000 0000 0000 0000 0000 0000 0000 0000
0000060 0000 0000 0000 0000 0000 0000 0000 0000
0000070 0000 0000 0000 0000 0000 0000 0000 0000

Попробуем зашифровать и расшифровать картинку.

Как видим, Чаки с Тиффани успешно пережили шифрование и расшифровку и нисколько не пострадали (все хеши совпали).

"Мы старались получить безопасность, используя простые конструкции. Основным преимуществом простых конструкций является то, что размышлять о них становится легче, что позволяет ещё легче исследовать безопасность. Вы получаете некоторую «красоту» и математическую элегантность" - Vincent Rijmen