[Из песочницы] Реализация блочного шифра «Кузнечик» с режимом CFB на С++30.10.2016 14:18

Сегодня речь пойдёт о новом алгоритме блочного шифрования «Кузнечик» из стандарта ГОСТ Р 34.12 2015. В последнее время выходит множество публикаций, посвященных этому стандарту. В них с теоретической точки зрения описываются приведённый алгоритм, изучаются особенности отельных преобразований, а так же предлагаются способы оптимизации, путём включения вставок кода на языке ассемблера.

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

Структура программы


Программа состоит из трех частей
  • набор вспомогательных функций и классов — mycrypto.cpp mycrypto.hpp
  • блочный шифр «Кузнечик» — Kuznyechik.cpp Kuznyechik.hpp
  • режим шифрования Cipher Feed Back — modes.hpp

Использованные обозначения
#define BLOCK_LENGTH 16

typedef unsigned char BYTE;
typedef unsigned short WORD;

Вспомогательные средства


Класс ByteBlock
Интерфейс ByteBlock
class ByteBlock {
    BYTE * pBlocks;
    size_t amount_of_bytes;
public:
    // Construct block of bytes which contsists of
    // size_ blocks each of them with init_value in it
    ByteBlock(size_t size_ = 0, BYTE init_value = 0);

    // Construct block with size_ first bytes of pBlocks_
    // The value will be copied, source stays untouchable
    ByteBlock(BYTE * pBlocks_, size_t size_);

    // Move constructor
    // Copy constructor thus implicitly deleted
    // Object to move turn to null
    ByteBlock(ByteBlock && rhs);

    // Destructor, yeah
    ~ByteBlock();

    // Move assigment operator
    // Object to move turn to null
    void operator = (ByteBlock && rhs);

    // This cast may be convenient to use the ByteBlock
    // in functions which takes raw pointers as argument
    BYTE * byte_ptr();
    const BYTE * byte_ptr() const;

    // Indexing operator with evident functionality
    BYTE & operator [] (size_t index);
    BYTE operator [] (size_t index) const;

    bool operator == (const ByteBlock & lhs) const;
    bool operator != (const ByteBlock & lhs) const;

    // Replace body of the current block with pBlocks_
    // Old value will be zerod, and then, deleted
    // New value copied into the block,
    // source stays untouchable
    void reset(const BYTE * pBlocks_, size_t size_);

    // Return amount of bytes in block
    size_t size() const;

    // It'll return deep copy of the block, which
    // points to different place in memory
    ByteBlock deep_copy() const;

    // It'll return slice of current ByteBlock
    ByteBlock operator () (size_t begin, size_t length) const;

    // Changes values between two ByteBlock-s
    friend void swap(ByteBlock & lhs, ByteBlock & rhs);
};

Объекты данного класса (далее «сообщения») повсеместно используются в программе для хранения информации в двоичном виде. Интерфейс продумал таким образом, чтобы эффективно решались следующие задачи:
  • Хранение байтовых строк произвольной длины
  • Обеспечение «единственности» сообщений в памяти
  • Обнуление участка памяти перед освобождением памяти
  • Обеспечение своевременного удаление сообщений
  • Предоставление удобного доступа к отельным байтам, и последовательностей байтов в сообщении

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

Объекты класса ByteBlock всегда владеют памятью, на которую указывают. Даже когда объект инициализируется с некоторым участком памяти, конструктор копирует его на новое место, и объект работает с копией исходной информации. В некотором смысле данный класс похож на умный указатель из STL — std: unique_ptr.
Обнуление памяти обеспечивается функцией memset. Стоит заметить, что при сборке данной программы не стоит указывать опции оптимизации, так как некоторые компиляторы имеют свойство игнорировать вызов функции memset, зная, что далее память не будет использована, а вскоре будет удалена.

Перевод hex-строк в ByteBlock и обратно
std::string hex_representation(const ByteBlock & bb);
ByteBlock hex_to_bytes(std::string s);

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

Алгоритм «Кузнечик»


Интерфейс Kuznyechik
class Kuznyechik {
    std::vector keys;
    static bool is_init;
public:
    static const int block_lenght { BLOCK_LENGTH };

    Kuznyechik(const ByteBlock & key);
    Kuznyechik(const Kuznyechik & rhs);
    ~Kuznyechik();
    void encrypt(const ByteBlock & src, ByteBlock & dst) const;
    void decrypt(const ByteBlock & src, ByteBlock & dst) const;
};

Поле keys — итерационные ключи, которые вычисляются один раз, во время инициализации объекта по заданному ключу. Поле is_init — флаг, который указывает, создавались ли когда либо объекты типа Kuznyechik. Данный флаг необходим в связи с тем, что на момент запуска программы многие коэффициенты и параметры алгоритма отсутствуют. При первой инициализации они высчитываются и хранятся в памяти до завершения программы.

С учётом вышесказанного, необходимо прокомментировать наличие конструктора копирования, тогда как внутри класса располагаются объекты ByteBlock, у которых этот конструктор отсутствует. Дело в том, что при копировании происходит поэлементное глубокое копирования итерационных ключей из массива keys.

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

const vector linear_transform_coeff = {
	148, 32, 133, 16, 194, 192, 1, 251, 1, 192,
	194, 16, 133, 32, 148, 1
};
const WORD linear_transform_modulus = 0x1C3;

const vector iteration_constants;

Именно здесь мы видим те переменные, которые при запуске не хранят необходимые для работы алгоритма значения. Это direct_permutation, inverse_permutation, с помощью которых осуществляется нелинейное преобразование, и iteration_constants, использующиеся для развёртывания ключа. Происходит их заполнение следующим образом:
Инициализация глобальных переменных
void init_perms() {
    map *p_direct, *p_inverse;
    p_direct = const_cast< map * >(&direct_permutation);
    p_inverse = const_cast< map * >(&inverse_permutation);
    for(int i = 0; i < nonlinear_transform_perm.size(); i++) {
        (*p_direct)[i] = nonlinear_transform_perm[i];
        (*p_inverse)[nonlinear_transform_perm[i]] = i;
    }
}

void init_consts() {
    vector * p = const_cast< vector * >(&iteration_constants);
    ByteBlock v128;
    for(BYTE i = 1; i <= 32; i++) {
        v128 = ByteBlock(BLOCK_LENGTH, 0);
	v128[BLOCK_LENGTH - 1] = i;
        iteration_linear_transform_direct128(v128.byte_ptr());
	p->push_back(std::move(v128));
    }
}

Реализация использующихся в алгоритме преобразований
Все преобразования работают с обычными указателями: преобразование из ByteBlock в BYTE * не требует дополнительных затрат, а проверка на то, что размер выделенной памяти соответствует параметрам шифра, была выполнена на более верхнем уровне.
Нелинейное прямое преобразование
void nonlinear_transform_direct128(BYTE * target) {
    BYTE * p_end = target + BLOCK_LENGTH;
    while(target != p_end) {
        *target = direct_permutation.at(*target);
        target++;
    }
}

Нелинейное преобразование есть ни что иное, как обычная перестановка.
Линейное прямое преобразование
void iteration_linear_transform_direct128(BYTE * target) {
    for(int i = 0; i < 16; i++)
        linear_transform_direct128(target);
}

void linear_transform_direct128(BYTE * target) {
    BYTE buffer = linear_transform_core128(target);
    for(int i = BLOCK_LENGTH - 1; i > 0; i--)
        target[i] = target[i-1];
    *target = buffer;
}

BYTE linear_transform_core128(const BYTE * target) {
    WORD result = 0;
    for(int i = 0; i < BLOCK_LENGTH; i++)
        result ^= multiply(target[i], linear_transform_coeff[i]);

    return result;
}

WORD multiply(WORD lhs, WORD rhs) {
    WORD result = 0, modulus = linear_transform_modulus << 7;
    for(WORD detecter = 0x1; detecter != 0x100; detecter <<= 1, lhs <<= 1)
        if(rhs & detecter) result ^= lhs;
    for(WORD detecter = 0x8000; detecter != 0x80; detecter >>= 1, modulus >>= 1)
        if(result & detecter) result ^= modulus;
    return result;
}

Интересно будет остановиться на функции multiply. Особенность её заключается в том, что при выполнения линейного преобразования все вычисления ведутся в фактор-кольце GL (2)[x]/p (x), где p (x) = x^8 + x^7 + x^6 + x + 1. В первом цикле производится перемножение многочленов, заданных своими коэффициентами из GL (2). Во втором же цикле пошагово вычисляется значение по модулю p (x).Развёртывание итерационных ключей
Функции формирования итерационных ключей
void keys_transform128(BYTE * k1, BYTE * k2, int iconst) {
    BYTE buffer[BLOCK_LENGTH];
    memcpy(buffer, k1, BLOCK_LENGTH);
    xor128(k1, k1, iteration_constants[iconst].byte_ptr());
    nonlinear_transform_direct128(k1);
    iteration_linear_transform_direct128(k1);
    xor128(k1, k2, k1);
    memcpy(k2, buffer, BLOCK_LENGTH);
}

void key_derivation128(BYTE * k1, BYTE * k2, BYTE * k3, BYTE * k4, int ipair) {
    if(k1 != k3) memcpy(k3, k1, BLOCK_LENGTH);
    if(k2 != k4) memcpy(k4, k2, BLOCK_LENGTH);
    for(int i = 0; i < 8; i++)
        keys_transform128(k3, k4, ipair * 8 + i);
}

И, наконец, алгоритм шифрования в наших обозначениях будет выглядеть следующим образом: 
void encrypt128(BYTE * target, const vector & keys) {
    xor128(target, target, keys[0].byte_ptr());
    for(int i = 1; i < 10; i++) {
        nonlinear_transform_direct128(target);
        iteration_linear_transform_direct128(target);
        xor128(target, target, keys[i].byte_ptr());
    }
}

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

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


Интерфейс CFB_Mode
template 
class CFB_Mode {
    const CipherType algorithm;
    const ByteBlock iv;

    void decrypt_with_iv(const ByteBlock & src, ByteBlock & dst, const ByteBlock & iv_) const;
public:
    CFB_Mode(const CipherType & alg, const ByteBlock & init_vec);
    void encrypt(const ByteBlock & src, ByteBlock & dst) const;
    void decrypt(const ByteBlock & src, ByteBlock & dst) const;

    void parallel_decrypt(const ByteBlock & src, ByteBlock & dst) const;
};

Выбор режима блочного шифрования был случаен. По аналогии легко пишутся и другие режимы. У тех, кто знаком с библиотекой CryptoPP может возникнуть чувство дежавю, и это будет оправданно. Ведь именно такой подход к осуществлению взаимодействия блочного шифра и режима шифрования использован в этой библиотеке.

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

  • Описаны открытые методы encrypt и decrypt с тем же прототипом, что и в классе CFB_Mode
  • Существует открытое поле block_length, хранящее число байтов, соответствующее длине блока шифра

Очевидно, наш класс Kuznyechik удовлетворяет этим требованиям.Функция шифрования и дешифрования
В этих алгоритмах используются вспомогательные функции, которые разбивают всё сообщений на блоки, кратные длине, на которой работает конкретный блочный шифр, объединяют их обратно, а так же поэлементный xor.
std::vector split_blocks(const ByteBlock & src, size_t length);
ByteBlock join_blocks(const std::vector & blocks);
void xor_blocks(ByteBlock & to_assign, const ByteBlock & lhs, const ByteBlock & rhs);

Функция шифрования
template 
void CFB_Mode::encrypt(const ByteBlock & src, ByteBlock & dst) const {
    auto blocks = split_blocks(src, CipherType::block_lenght);
    ByteBlock tmp;

    algorithm.encrypt(iv, tmp);
    xor_blocks(tmp, tmp, blocks[0]);
    blocks[0] = std::move(tmp);
    for(int i = 1; i < blocks.size(); i++) {
        algorithm.encrypt(blocks[i-1], tmp);
        xor_blocks(tmp, tmp, blocks[i]);
        blocks[i] = std::move(tmp);
    }
    dst = join_blocks(blocks);
}

Функция дешифрования
template 
void CFB_Mode::decrypt(const ByteBlock & src, ByteBlock & dst) const {
    decrypt_with_iv(src, dst, iv);
}

template 
void CFB_Mode::decrypt_with_iv(const ByteBlock & src, ByteBlock & dst, const ByteBlock & iv_) const {
    auto blocks = split_blocks(src, CipherType::block_lenght);
    ByteBlock tmp;

    algorithm.encrypt(iv_, tmp);
    xor_blocks(tmp, blocks[0], tmp);
    swap(tmp, blocks[0]);
    for(int i = 1; i < blocks.size(); i++) {
        algorithm.encrypt(tmp, tmp);
        xor_blocks(tmp, blocks[i], tmp);
        swap(tmp, blocks[i]);
    }
    dst = join_blocks(blocks);
}

Решение разбить функцию дешифрования на составные компоненты кажется излишним. Это было бы так, если бы режим шифрования с обратной связью по шифротексту не поддерживал параллелизм для данной процедуры. Далее будет рассмотрен вариант алгоритма дешифрования с использованием потоков std: threads из стандарта C++11.
Функция дешифрования с использованием параллелизма
template 
void CFB_Mode::parallel_decrypt(const ByteBlock & src, ByteBlock & dst) const {
    // length in blocks of CipherType::block_lenght
    unsigned long const length =
        src.size() / CipherType::block_lenght + (src.size() % CipherType::block_lenght ? 1 : 0);

    // amount of threads which can perform really simultaniously
    unsigned long const hardware_threads = std::thread::hardware_concurrency();

    // blocks of size CipherType::block_lenght to perform on by one thread
    unsigned long const min_per_thread = 1;

    // amount of threads to satisfy current condition
    unsigned long const max_threads = (length + min_per_thread - 1) / min_per_thread;

    // amount of threads to create
    unsigned long const num_threads = std::min(
        hardware_threads != 0 ? hardware_threads : 2,
        max_threads
    );

    // if we aren't able to use multiple threads call common decryptor
    if(num_threads <= 1) {
        decrypt(src, dst);
        return;
    }

    std::cerr << "Running " << num_threads << " threads." << endl;

    unsigned long const block_size = (length / num_threads) * CipherType::block_lenght;
    std::vector init_vectors(num_threads);
    std::vector results(num_threads);
    std::vector threads(num_threads - 1);

    init_vectors[0] = iv.deep_copy();
    for(int i = 1; i < num_threads; i++)
        init_vectors[i] = src(i * block_size - CipherType::block_lenght, CipherType::block_lenght);

    unsigned long start_pos = 0;
    for(unsigned long i = 0; i < num_threads - 1; i++) {
        threads[i] = std::thread(
            &CFB_Mode::decrypt_with_iv,
            this,
            src(start_pos, block_size),
            std::ref( results[i] ),
            std::ref( init_vectors[i] )
        );
        start_pos += block_size;
    }

    decrypt_with_iv(
        src(start_pos, src.size() - start_pos),
        results[num_threads - 1],
        init_vectors[num_threads - 1]
    );

    for(auto & t : threads) t.join();

    dst = join_blocks(results);
}


Пример программы, шифрующей некоторое сообщение


#include "mycrypto.hpp"
#include "Kuznyechik.hpp"

int main() {
    ByteBlock key = hex_representation(
        "8899aabbccddeeff0011223344556677fedcba98765432100123456789abcdef"
    );
    ByteBlock iv = hex_representation("abcdef12345600dacdef94756eeabefa");
    ByteBlock msg = hex_representation("1122334455667700ffeeddccbbaa9988");
    ByteBlock result;

    CFB_Mode encryptor(Kuznyechik(key), iv);
    encryptor.encrypt(msg, result);

    return 0;
}

Репозиторий проекта располагается тут.

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

  • 30 октября 2016 в 13:28

    +2

    ↑

    ↓

    Странные какие-то названия у российских изобретателей. Шизофреничные. Вот некоторые примеры: «Буратино» — огнеметная система. Каким боком добрый детский герой связан с оружием массового уничтожения? «Береза» — система предупреждения об радарном облучении и ракетной атаки. Причем вообще тут береза? Каким боком? Логичней бы тогда звучала «Паутина». Тут тоже шифр «Кузнечик», что за бред с Кащенко? Другого названия что ли не нашлось? Да у нас полно названий которые могли бы подчеркнуть что это шифр и он сделан в России. Фантазии у них там в военных КБ совсем нет. Вот и льют свою шизофазию в массы. Проводили бы тогда общественные конкурсы, если у самих литературного таланта нет.

    • 30 октября 2016 в 13:38

      0

      ↑

      ↓

      «Объект «Буратино», ну какой шпион подумает что речь идет о системе залпового огня? Только давно привыкший к псевдо-шизофреничным названиям.

      • 30 октября 2016 в 14:13 (комментарий был изменён)

        0

        ↑

        ↓

        Частично согласен, что это может обеспечить секретность. Но американцы например не стесняются давать своим поделкам красивые и звучные названия, которые в тоже время говорят, что вещь сделана в США и связана с американской историей. Причем призвана и уточнять характер изделия. Вот например вертолет «Апач», известно что индейцы племени апачи отличались крайней жестокостью и уж точно не были друзьями детей из детской сказки. Причем апачи это чисто американское явление уникальное для США. Ракета «Минитмен», минитмены как известно это тоже американское явление времен гражданской войны, ополченцы призванные защитить независимость США. Даже американские (натовские) аналоги даваемые нашим изделиям зачастую звучат более броско и эффективно. «Блек-джек » и сразу скидывай карты. «Сатана» и начинай молиться Иисусу нашему Христу во спасение своей тушки.

    • 30 октября 2016 в 13:56

      0

      ↑

      ↓

      А еще к этим названиям добавляют всякие индексы и модификации, получается совсем клинично типа
      ПТРК «Малютка-П» или «Хризантема-С»

© Habrahabr.ru