Если вбить в яндекс 'aes 128 ecb mode', найдутся хорошие статьи ребят на "хабре": раз и два — толковые и одновременно слишком подробные.


Рассказ об алгоритме в картинках находится здесь (который также можно найти по ссылкам в одной из статей ребят выше).


Кратко об алгоритме: 1) создаем объект с 16-байтным state и массивом 16-байтных ключей; 2) пишем примитивы для объекта (они же трансформации); 3) запускаем n раз (где n — кол-во раундов). Все трансформации делаем симметричными — для зашифровки и расшифровки одновременно. Расшифровка в терминах алгоритма — это зашифровка наоборот.


Структура:


using byte_t = unsigned char;
struct aes128 {
  aes128(const std::string& text, const std::string& cipher, bool decrypt = false)
    : state({begin(text), end(text)}), keys({{begin(cipher), end(cipher)}}), decrypt(decrypt) {}
  aes128() = default;
  aes128(const aes128&) = default;

  std::vector<byte_t> state;
  std::vector<std::vector<byte_t>> keys;
  bool decrypt;
}

Первым делом после создания генерируем ключи (инфа о sbox и RCON будет ниже):


void key_expansion() {
  for (int j = 1; j != 11; j++) { // for 11 rounds
    std::vector<byte_t> key = keys[j-1];
    std::vector<byte_t> column = {key[13], key[14], key[15], key[12]}; // rotation
    for (auto& x: column) x = sbox(x); 
    column[0] ^= RCON[j];

    std::transform(begin(column), end(column), begin(key), begin(key), std::bit_xor<byte_t>());
    std::transform(begin(key)+4, end(key), begin(key), begin(key)+4, std::bit_xor<byte_t>());
    keys.emplace_back(std::move(key));
  }
}

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


void add_round_key(int r) {
  std::transform(begin(keys[r]), end(keys[r]), begin(state), begin(state), std::bit_xor<byte_t>());
}
void substitute_bytes() {
  std::transform(begin(state), end(state), begin(state), [&](byte_t x) { return sbox(x, decrypt); });
}
void shift_rows() {
  int k = decrypt ? 3 : 1; // coef for rotation point
  for (int i = 1; i != 4; ++i)
    shift_row({state[i], state[4+i], state[8+i], state[12+i]}, (k*i) % 4, i);
}
void shift_row(std::array<byte_t, 4>&& row, int k, int j) {
  std::rotate(begin(row), begin(row)+k, end(row));
  for (int i = 0; i != 4; ++i) { state[i*4+j] = row[i]; }
}

Плюс еще одна трансформация (инфу о байтах 0xe, 0x2… берем из статьей ребят выше):


void mix_columns() {
  for (int i = 0; i != 4; i++) {
    const std::array<byte_t, 4> column = {state[i*4], state[i*4+1], state[i*4+2], state[i*4+3]};
    if (!decrypt) {
      state[i*4] = vector_mult(column, { 0x2, 0x3, 0x1, 0x1 });
      state[i*4+1] = vector_mult(column, { 0x1, 0x2, 0x3, 0x1 });
      state[i*4+2] = vector_mult(column, { 0x1, 0x1, 0x2, 0x3 });
      state[i*4+3] = vector_mult(column, { 0x3, 0x1, 0x1, 0x2 });
    } else {
      state[i*4] = vector_mult(column, { 0xe, 0xb, 0xd, 0x9 });
      state[i*4+1] = vector_mult(column, { 0x9, 0xe, 0xb, 0xd });
      state[i*4+2] = vector_mult(column, { 0xd, 0x9, 0xe, 0xb });
      state[i*4+3] = vector_mult(column, { 0xb, 0xd, 0x9, 0xe });
    }
  }
}

Собственно, алгоритмы:


aes128 encrypt(const std::string& text, const std::string& cipher) {
  aes128 aes(text, cipher);
  aes.key_expansion();
  aes.add_round_key(0);
  for (int i = 1; i != 10; i++) {
    aes.substitute_bytes();
    aes.shift_rows();
    aes.mix_columns();
    aes.add_round_key(i);
  }
  aes.substitute_bytes();
  aes.shift_rows();
  aes.add_round_key(10);
  return aes;
}

template <typename I>
aes128 decrypt(I first, I last, const std::string& cipher) {
  aes128 aes({first, last}, cipher, true);
  aes.key_expansion();
  aes.add_round_key(10);
  aes.shift_rows();
  aes.substitute_bytes();
  for (int i = 9; i != 0; --i) {
    aes.add_round_key(i);
    aes.mix_columns();
    aes.shift_rows();
    aes.substitute_bytes();
  }
  aes.add_round_key(0);
  return aes;
}

Утилиты:


byte_t hex(char ch) { return (ch - '0') % 39; }
byte_t sbox(byte_t x, bool decrypt = false) {
  std::string s = (decrypt ? INV_SBOX : SBOX)[x >> 4][x & 15];
  return hex(s[0]) << 4 | hex(s[1]);
}
byte_t mult_by_2(byte_t x) { return (x < 128) ? x << 1 : (x << 1 & 0xff) ^ 0x1b; }
byte_t mult_by_8(byte_t x) { return mult_by_2(mult_by_2(mult_by_2(x))); }

const std::unordered_map<byte_t, std::function<byte_t(byte_t)>> mapper = {
  {0x1, [](byte_t x) { return x; }},
  {0x2, mult_by_2},
  {0x3, [](byte_t x) { return mult_by_2(x) ^ x; }},
  {0x9, [](byte_t x) { return mult_by_8(x) ^ x; }},
  {0xb, [](byte_t x) { return mult_by_8(x) ^ mult_by_2(x) ^ x; }},
  {0xd, [](byte_t x) { return mult_by_8(x) ^ mult_by_2(mult_by_2(x)) ^ x; }},
  {0xe, [](byte_t x) { return mult_by_8(x) ^ mult_by_2(mult_by_2(x)) ^ mult_by_2(x); }},
};
byte_t vector_mult(const std::array<byte_t, 4>& v1, std::array<byte_t, 4>&& v2) {
  std::transform(begin(v1), end(v1), begin(v2), begin(v2),
    [](byte_t x, byte_t y) { return mapper.at(y)(x); });
  return std::accumulate(begin(v2), end(v2), byte_t(0), std::bit_xor<byte_t>());
}

Константы:


const std::vector<std::vector<std::string>> SBOX = {
  { "63", "7c", "77", "7b", "f2", "6b", "6f", "c5", "30", "01", "67", "2b", "fe", "d7", "ab", "76" },
  { "ca", "82", "c9", "7d", "fa", "59", "47", "f0", "ad", "d4", "a2", "af", "9c", "a4", "72", "c0" },
  { "b7", "fd", "93", "26", "36", "3f", "f7", "cc", "34", "a5", "e5", "f1", "71", "d8", "31", "15" },
  { "04", "c7", "23", "c3", "18", "96", "05", "9a", "07", "12", "80", "e2", "eb", "27", "b2", "75" },
  { "09", "83", "2c", "1a", "1b", "6e", "5a", "a0", "52", "3b", "d6", "b3", "29", "e3", "2f", "84" },
  { "53", "d1", "00", "ed", "20", "fc", "b1", "5b", "6a", "cb", "be", "39", "4a", "4c", "58", "cf" },
  { "d0", "ef", "aa", "fb", "43", "4d", "33", "85", "45", "f9", "02", "7f", "50", "3c", "9f", "a8" },
  { "51", "a3", "40", "8f", "92", "9d", "38", "f5", "bc", "b6", "da", "21", "10", "ff", "f3", "d2" },
  { "cd", "0c", "13", "ec", "5f", "97", "44", "17", "c4", "a7", "7e", "3d", "64", "5d", "19", "73" },
  { "60", "81", "4f", "dc", "22", "2a", "90", "88", "46", "ee", "b8", "14", "de", "5e", "0b", "db" },
  { "e0", "32", "3a", "0a", "49", "06", "24", "5c", "c2", "d3", "ac", "62", "91", "95", "e4", "79" },
  { "e7", "c8", "37", "6d", "8d", "d5", "4e", "a9", "6c", "56", "f4", "ea", "65", "7a", "ae", "08" },
  { "ba", "78", "25", "2e", "1c", "a6", "b4", "c6", "e8", "dd", "74", "1f", "4b", "bd", "8b", "8a" },
  { "70", "3e", "b5", "66", "48", "03", "f6", "0e", "61", "35", "57", "b9", "86", "c1", "1d", "9e" },
  { "e1", "f8", "98", "11", "69", "d9", "8e", "94", "9b", "1e", "87", "e9", "ce", "55", "28", "df" },
  { "8c", "a1", "89", "0d", "bf", "e6", "42", "68", "41", "99", "2d", "0f", "b0", "54", "bb", "16" }};

const std::vector<int> RCON = { 0, 1, 2, 4, 8, 16, 32, 64, 128, 27, 54 }; // ten rounds

const std::vector<std::vector<std::string>> INV_SBOX = {
  { "52", "09", "6a", "d5", "30", "36", "a5", "38", "bf", "40", "a3", "9e", "81", "f3", "d7", "fb" },
  { "7c", "e3", "39", "82", "9b", "2f", "ff", "87", "34", "8e", "43", "44", "c4", "de", "e9", "cb" },
  { "54", "7b", "94", "32", "a6", "c2", "23", "3d", "ee", "4c", "95", "0b", "42", "fa", "c3", "4e" },
  { "08", "2e", "a1", "66", "28", "d9", "24", "b2", "76", "5b", "a2", "49", "6d", "8b", "d1", "25" },
  { "72", "f8", "f6", "64", "86", "68", "98", "16", "d4", "a4", "5c", "cc", "5d", "65", "b6", "92" },
  { "6c", "70", "48", "50", "fd", "ed", "b9", "da", "5e", "15", "46", "57", "a7", "8d", "9d", "84" },
  { "90", "d8", "ab", "00", "8c", "bc", "d3", "0a", "f7", "e4", "58", "05", "b8", "b3", "45", "06" },
  { "d0", "2c", "1e", "8f", "ca", "3f", "0f", "02", "c1", "af", "bd", "03", "01", "13", "8a", "6b" },
  { "3a", "91", "11", "41", "4f", "67", "dc", "ea", "97", "f2", "cf", "ce", "f0", "b4", "e6", "73" },
  { "96", "ac", "74", "22", "e7", "ad", "35", "85", "e2", "f9", "37", "e8", "1c", "75", "df", "6e" },
  { "47", "f1", "1a", "71", "1d", "29", "c5", "89", "6f", "b7", "62", "0e", "aa", "18", "be", "1b" },
  { "fc", "56", "3e", "4b", "c6", "d2", "79", "20", "9a", "db", "c0", "fe", "78", "cd", "5a", "f4" },
  { "1f", "dd", "a8", "33", "88", "07", "c7", "31", "b1", "12", "10", "59", "27", "80", "ec", "5f" },
  { "60", "51", "7f", "a9", "19", "b5", "4a", "0d", "2d", "e5", "7a", "9f", "93", "c9", "9c", "ef" },
  { "a0", "e0", "3b", "4d", "ae", "2a", "f5", "b0", "c8", "eb", "bb", "3c", "83", "53", "99", "61" },
  { "17", "2b", "04", "7e", "ba", "77", "d6", "26", "e1", "69", "14", "63", "55", "21", "0c", "7d" }};

Ссылки:


  1. https://en.wikipedia.org/wiki/Advanced_Encryption_Standard
  2. http://www.moserware.com/2009/09/stick-figure-guide-to-advanced.html

Комментарии (7)


  1. Scratch
    14.05.2019 20:45

    Во-первых ECB. Во-вторых, о чем статья? Об умении копипастить непонятные сорцы на хабр?


    1. xyli0o Автор
      14.05.2019 21:09

      Спасибо, поправил. Умение копипастить весьма полезно в профессии; полезнее, правда, разобраться в алгоритме и написать код.


  1. pohjalainen
    15.05.2019 00:33

    Краткость — сестра.


  1. webmascon
    15.05.2019 02:11

    Автору поста: спрячьте код под кат. Вы ломаете rss ленту


    1. xyli0o Автор
      15.05.2019 08:33

      Сорян, идеологически против ката


  1. Brak0del
    15.05.2019 10:24

    А чем эта реализация лучше прочих? Есть ли какая-то инфа по скоростям этой реализации?


    1. xyli0o Автор
      15.05.2019 10:44

      В продакшене точно не нужно использовать данную реализацию. Поинт статьи — показать, что алгоритм (aes 128) весьма прост.