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

    В статье 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 задавайте! По возможноти постараюсь ответить.

    Исходный код всего алгоритма можно взять отсюда.

    Комментарии 12

      0
      не ради холивара будет спрошено, но есть ли толковое сравнение матлаба и вольфрама? И как общевычислительных сред, и в отраслевом применении.
        +4
        Имхо, у пакетов разные цели: у математики сильная сторона — символьные вычисления, матлаб — матричные вычисления, матмоделирование. Не то чтобы математика не умеет матричные вычисления, но по-моему в матлабе они куда как удобнее.
          0
          Кстати да, хотя в матлабе есть символьный движок, но судя по примерам кода до математики он не дотягивает. Тем не менее, опять же, судя по примерам кода, в математике набор библиотек и встроенный функционал местами бьет матлаб, а если уж гую можно без геморроя нарисовать, то просто цены ему нет.
            0
            В Матлабе символьный движок не свой, а лицензирован с бородатой версии Mapple.
            Разница, imho, в том, что Матлаб более нацелен на инженерную стезю всех уровней, Математика — на чуть более тонкие материи.
              0
              а более тонкие материи — то есть он заточен под какие то конекретные области?
                0
                Mathematica заточена больше под научные задачи, чем под инженерные.
                  +1
                  немного не догоняю логику. Ведь если мы уже обрабатываем данные или что то моделируем, то это сразу инженерная задача вроде.
        0
        Автор, а с этим вы когда-нибудь работали: eumat.sourceforge.net/index.html?
          0
          С этим чудом не приходилось сталкиваться.
          0
          Как же, как же, помню на парах в универе делали почти то же самое, а потом мне вопросы по аесу на экзамене попались.
            +1
            А будут ли кому-нибудь интересны уроки по Mathematica?
              0
              Я могу помочь, чем смогу. По большей части, правда, программно.

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

            Самое читаемое