Сегодня речь пойдёт о новом алгоритме блочного шифрования «Кузнечик» из стандарта ГОСТ Р 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
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);
Эти функции преобразовывают входные данные из шестнадцатеричной записи в их байтовое представление, что необходимо для дальнейшей работы программы.
Алгоритм «Кузнечик»
class Kuznyechik {
std::vector<ByteBlock> 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<BYTE> 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<BYTE, BYTE> direct_permutation, inverse_permutation;
const vector<WORD> 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<ByteBlock> iteration_constants;
Именно здесь мы видим те переменные, которые при запуске не хранят необходимые для работы алгоритма значения. Это direct_permutation, inverse_permutation, с помощью которых осуществляется нелинейное преобразование, и iteration_constants, использующиеся для развёртывания ключа. Происходит их заполнение следующим образом:
void init_perms() {
map<BYTE, BYTE> *p_direct, *p_inverse;
p_direct = const_cast< map<BYTE, BYTE> * >(&direct_permutation);
p_inverse = const_cast< map<BYTE, BYTE> * >(&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<ByteBlock> * p = const_cast< vector<ByteBlock> * >(&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<ByteBlock> & 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
template <typename CipherType>
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<ByteBlock> split_blocks(const ByteBlock & src, size_t length);
ByteBlock join_blocks(const std::vector<ByteBlock> & blocks);
void xor_blocks(ByteBlock & to_assign, const ByteBlock & lhs, const ByteBlock & rhs);
template <typename CipherType>
void CFB_Mode<CipherType>::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 <typename CipherType>
void CFB_Mode<CipherType>::decrypt(const ByteBlock & src, ByteBlock & dst) const {
decrypt_with_iv(src, dst, iv);
}
template <typename CipherType>
void CFB_Mode<CipherType>::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 <typename CipherType>
void CFB_Mode<CipherType>::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<ByteBlock> init_vectors(num_threads);
std::vector<ByteBlock> results(num_threads);
std::vector<std::thread> 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<CipherType>::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<Kuznyechik> encryptor(Kuznyechik(key), iv);
encryptor.encrypt(msg, result);
return 0;
}
Репозиторий проекта располагается тут.
Автор: KoSeAn97
