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

    Исходный код всего алгоритма можно взять отсюда.
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 12

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

            Only users with full accounts can post comments. Log in, please.