Реалізація блочного шифру «Коник» з режимом CFB на С++

Сьогодні мова піде про новий алгоритм блочного шифрування «Коник» з стандарту ГОСТ Р 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 of contsists
// 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 may be cast convenient to use the ByteBlock
// functions in which takes raw pointers as argument
BYTE * byte_ptr();
const BYTE * byte_ptr() const;

// Indexing with operator 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<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

Інтерфейс CFB_Mode
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;
}

Репозиторій проекту розташовується тут.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.