14 July 2011

Реализация AES на Wolfram Mathematica

Programming
В статье Wolfram Mathematica: знакомство хаброчеловек 8bitjoey познакомил сообщество с отличным математическим пакетом Wolfram Mathematica.
Сегодня я продолжу экскурс в данный продукт. Чтобы совместить приятное с полезным, реализуем алгоритм AES при помощи данного продукта.



Вместо введения


Данная статья ориентирована на пользователей, которые уже хоть как-то знакомы с Mathematica. В рассматриваемом пакете очень детальная документация. Для вызова справки о функции, достаточно выделит её и нажать F1. Хорошее пояснение алгоритма AES (с примерами на JavaScript) было сделано в статье Как устроен AES.

Реализация AES


Для начала объявим глобальные переменные: подстановку (S-box), количество раундов (Nr), размер блока (Nb) и ключа (Nk).
Needs["FiniteFields`"];
fld = FiniteFields`GF[2, {1, 1, 0, 1, 1, 0, 0, 0, 1}];

Sbox = {99, 124, 119, 123, 242, 107, 111, 197, 48, 1, 103, 43, 254, 
   215, 171, 118, 202, 130, 201, 125, 250, 89, 71, 240, 173, 212, 162,
    175, 156, 164, 114, 192, 183, 253, 147, 38, 54, 63, 247, 204, 52, 
   165, 229, 241, 113, 216, 49, 21, 4, 199, 35, 195, 24, 150, 5, 154, 
   7, 18, 128, 226, 235, 39, 178, 117, 9, 131, 44, 26, 27, 110, 90, 
   160, 82, 59, 214, 179, 41, 227, 47, 132, 83, 209, 0, 237, 32, 252, 
   177, 91, 106, 203, 190, 57, 74, 76, 88, 207, 208, 239, 170, 251, 
   67, 77, 51, 133, 69, 249, 2, 127, 80, 60, 159, 168, 81, 163, 64, 
   143, 146, 157, 56, 245, 188, 182, 218, 33, 16, 255, 243, 210, 205, 
   12, 19, 236, 95, 151, 68, 23, 196, 167, 126, 61, 100, 93, 25, 115, 
   96, 129, 79, 220, 34, 42, 144, 136, 70, 238, 184, 20, 222, 94, 11, 
   219, 224, 50, 58, 10, 73, 6, 36, 92, 194, 211, 172, 98, 145, 149, 
   228, 121, 231, 200, 55, 109, 141, 213, 78, 169, 108, 86, 244, 234, 
   101, 122, 174, 8, 186, 120, 37, 46, 28, 166, 180, 198, 232, 221, 
   116, 31, 75, 189, 139, 138, 112, 62, 181, 102, 72, 3, 246, 14, 97, 
   53, 87, 185, 134, 193, 29, 158, 225, 248, 152, 17, 105, 217, 142, 
   148, 155, 30, 135, 233, 206, 85, 40, 223, 140, 161, 137, 13, 191, 
   230, 66, 104, 65, 153, 45, 15, 176, 84, 187, 22};

Nr = 10;
Nb = 4;
Nk = 4;



Первая строка подключает пакет для работы с конечнечными полями, а вторая объявляет его. {1, 1, 0, 1, 1, 0, 0, 0, 1}=1+x+x^3+x^4+x^8 — неприводимый полином в поле GF(256).

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

Rijndael[State_, CipherKey_] := Module[{ExpandedKey, i, tState},
   (
    tState = State; (*переписываем входное значение state для работы с ним*)
    ExpandedKey = KeyExpansion[CipherKey]; (*вызываем функцию разворачивания ключа и получаем массив ключей для всех раундов*)
    tState = AddRoundKey[tState, ExpandedKey[[1]]]; (*первое сложение с ключом*)
    
    For[i = 1, i < Nr, i++,
     (
      tState = RRound[tState, ExpandedKey[[i + 1]]]; (*раундовое преобразование*)
      )
     ];
    tState = FinalRRound[tState, ExpandedKey[[Nr + 1]]]; (*финальное преобразование*)
    
    Return[tState];
    )
   ];


Main[] := Module[{},
   (
    Plaintext = FromDigits["00112233445566778899aabbccddeeff", 16];
    Key = FromDigits["000102030405060708090a0b0c0d0e0f", 16];
    CipherText = Rijndael[Plaintext, Key];
    Print[BaseForm[CipherText, 16]];
    Print[CipherText == 16^^69c4e0d86a7b0430d8cdb78070b4c55a];
    )
   ];

Main[];


Уже по привычке любую функцию записываю через Module, даже с пустыми параметрами. Открытый текст (Plaintext ) и ключ (Key), указанные в функции Main, взяты из fips 197 для тестирования кода. Перевод из 16-ой системы в 10-ую можно осуществить двумя способами: через макрос «16^^» или функцию FromDigits.
При написании криптографических алгоритмов в Mathematica часто используются функции IntegerDigits и FromDigits. Первая переводит число в любой базис, а вторая выполняет обратное действие.
State всегда представляет Integer. Это сделано с целью простого понимания алгоритма.

Ниже представлен код функции разворачивания ключа:
KeyExpansion[CipherKey_] := Module[{i, j, k, ExpandedKey},
   (
    ExpandedKey = Array[#*0 &, Nr + 1]; (*объявляем массив размером Nr + 1 с нулевыми значениями*)
    ExpandedKey[[1]] = CipherKey;
    
    For[i = 1, i <= Nr + 1, i++,
     (
      ExpandedKey[[i]] = IntegerDigits[ExpandedKey[[i]], 2^8, 16]; (*разбиваем ключи на байты*)
      ExpandedKey[[i]] = Partition[ExpandedKey[[i]], 4]; (*записываем в виде матрицы*)
      )
     ];
    (*Вычисляем rcon*)
    Rcon = Array[{#*0, #*0, #*0, #*0} &, Nr];
    
    Rcon[[1, 1]] = 1;
    
    For[i = 2, i <= Nr, i++,
     (
      Rcon[[i, 1]] = Rcon[[i - 1, 1]]*2;
      If[Rcon[[i, 1]] >= 256, 
       Rcon[[i, 1]] = BitXor[Rcon[[i, 1]], 283]];
      )
     ];
    
    For[i = 2, i <= Nr + 1, i++,
     (
      ExpandedKey[[i, 1]] = RotateLeft[ExpandedKey[[i - 1, 4]], 1]; (*циклический сдвиг влево на 1 байт*)
      (*Блок подстановок*)
      For[j = 1, j <= 4, j++,
       (
        ExpandedKey[[i, 1, j]] = Sbox[[ExpandedKey[[i, 1, j]] + 1]]; 
        )
       ];
      (*Xor с константой*)
      ExpandedKey[[i, 1]] = 
       BitXor[ExpandedKey[[i, 1]], Rcon[[i - 1]], 
        ExpandedKey[[i - 1, 1]]];
      (*Получение оставшихся байтов ключа*)
      For[k = 2, k <= 4, k++,
       (
        ExpandedKey[[i, k]] = 
          BitXor[ExpandedKey[[i, k - 1]], ExpandedKey[[i - 1, k]]];
        )
       ];
      
      )
     ];
    (*обратное приведение к Integer*)
    For[i = 1, i <= Nr + 1, i++,
     (
      ExpandedKey[[i]] = Flatten[ExpandedKey[[i]]];
      ExpandedKey[[i]] = FromDigits[ExpandedKey[[i]], 2^8];
      )
     ];
    
    Return[ExpandedKey]; (*возвращаем массив цикловых ключей*)
    )
   ];


Код прокомментирован, если возникнут вопросы, то задавайте.

RRound[State_, Key_] := Module[{i, tState},
   (
    tState = State;
    tState = ByteSub[tState];
    tState = ShiftRow[tState];
    tState = MixColumn[tState];
    tState = AddRoundKey[tState, Key];
    Return[tState];
    )
   ];

FinalRRound[State_, Key_] := Module[{i, tState},
   (
    tState = State;
    tState = ByteSub[tState];
    tState = ShiftRow[tState];
    tState = AddRoundKey[tState, Key];
    Return[tState];
    )
   ];


Функции цикловой (раундовой) функции и конечного преобразования, представленные в данном коде, думаю, не требуют объяснения — они обозначены точно так же, как и в fips 197.

AddRoundKey[State_, RoundKey_] := Module[{tState},
   (
    tState = BitXor[State, RoundKey];
    Return[tState];
    )
   ];


Функция сложения с ключём очень примитивная: необходимо сложитьпо модулю 2 входное значение и ключ. Для этого используем функцию BitXor, которой на вход подаются Integer.

ByteSub[State_] := Module[{i, tState},
   (
    tState = State;
    tState = IntegerDigits[tState, 2^8, 16];
    For[i = 1, i <= 16, i++,
     (
      tState[[i]] = Sbox[[tState[[i]] + 1]];
      )
     ];
    tState = FromDigits[tState, 2^8];
    Return[tState];
    )
   ];


Функция SubByte состоит из 3 частей:
  • разбиение Integer на 16 байтов;
  • непосредственно замена входных значений на числа из переменной Sbox;
  • объединение байтов обратно в Integer.


ShiftRow[State_] := Module[{tState},
   (
    tState = State;
    tState = IntegerDigits[tState, 2^8, 16];
    tState = Partition[tState, 4];
    tState = Transpose[tState];
    
    tState[[2]] = RotateLeft[tState[[2]], 1];
    tState[[3]] = RotateLeft[tState[[3]], 2];
    tState[[4]] = RotateLeft[tState[[4]], 3];
    
    tState = Transpose[tState];
    tState = Flatten[tState];
    tState = FromDigits[tState, 2^8];
    
    Return[tState];
    )
   ];


Код функции ShiftRow довольно простой. С 1 по 3 строчки — преобразование Integer в матрицу, следующие 3 строки осуществляют сдвиг 1, 2 и 3 байтов соответственно, потом переводим обратно из матрицы в Integer.

И самая интересная, с точки зрения математики, функция MixColumn, которую я прокомментирую непосредственно в коде. Если возникнут вопросы — задавайте.
MixColumn[State_] := Module[{i, j, tState},
   (
    tState = State;
    (*Преобразование Integer в матрицу*)
    tState = IntegerDigits[tState, 2^8, 16];
    tState = Partition[tState, 4];
    tState = Transpose[tState];
    (*Матрица из стандатра fips 197*)
    M = ({
       {2, 3, 1, 1},
       {1, 2, 3, 1},
       {1, 1, 2, 3},
       {3, 1, 1, 2}
      });
    (*Перевод чисел в элементы поля*)
    For[i = 1, i <= 4, i++,
     (
      For[j = 1, j <= 4, j++,
        (
         M[[i, j]] = fld[Reverse[IntegerDigits[M[[i, j]], 2, 8]]]; (*разбиваем Integer на биты и переворачиваем*)
         tState[[i, j]] = 
          fld[Reverse[IntegerDigits[tState[[i, j]], 2, 8]]];
         )
        ];
      )
     ];
    (*Умножение матрицы на столбец*)
    tState = M.tState;
    
    (*Преобразование State к байтам*)
    For[i = 1, i <= 4, i++,
     (
      For[j = 1, j <= 4, j++,
        (
         If[tState[[i, j]] == 0, Continue[]];
         tState[[i, j]] = FromDigits[Reverse[tState[[i, j]][[1]]], 2];
         )
        ];
      )
     ];
    (*Обратное преобразование матрицы к Integer*)
    tState = Transpose[tState];
    tState = Flatten[tState];
    tState = FromDigits[tState, 2^8];
    
    Return[tState];
    )
   ];



Выводы


Таким образом, при помощи Mathematica можно с лёгкостью реализовать алгоритмы шифрования, при условии, что знаешь математику (по большей части теорию чисел).

Послесловие


Последний месяц я программирую, используя продукт sage. Причиной перехода послужила недостаточная производительность Mathematica для криптологических потребностей и дороговизна продукта. Менять Mathematica на sage было сложновато, из-за недостаточно развитой встроенной помощи. Но после нескольких дней привыкаешь и всё становится просто. Легко освоить sage будет людям, знающим python.

Если есть вопросы по Mathematica задавайте! По возможноти постараюсь ответить.

Исходный код всего алгоритма можно взять отсюда.
Tags:wolfram mathematicaAES
Hubs: Programming
+22
5.4k 18
Comments 12