😫 💂🏼 👨🏿‍⚖️ C ++のCFBモードでのGrasshopperブロック暗号の実装 🕧 🐅 ♑️

今日は、2015年GOST R 34.12の新しいGrasshopperブロック暗号アルゴリズムについてお話します。最近、この標準に特化した多くの出版物が公開されました。それらでは、理論的な観点から、説明されたアルゴリズムが説明され、個々の変換の特徴が研究され、アセンブリ言語にコード挿入を含めることによって最適化方法も提案されます。

この記事では、読者に、C ++でのこのブロック暗号の実装に精通することを勧めます。このプログラムを作成するときの目標は、最大の効率を達成することではなく、主なタスクはアルゴリズムの仕組みを示すことでした。公式ドキュメントでアルゴリズムの説明を見ることができます。

プログラム構成

プログラムは3つの部分で構成されています

ヘルパー関数とクラスのセット-mycrypto.cpp mycrypto.hpp
グラスホッパーブロック暗号-Kuznyechik.cpp Kuznyechik.hpp
暗号フィードバック暗号化モード-モード.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関数呼び出しを無視する機能があります。

ByteBlockでの16進文字列の翻訳、およびその逆

 std::string hex_representation(const ByteBlock & bb); ByteBlock hex_to_bytes(const std::string & s);

これらの関数は、入力を16進表記からバイト表現に変換します。これは、プログラムのさらなる作業に必要です。

Grasshopperアルゴリズム

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; };

キーフィールドは、指定されたキーでオブジェクトを初期化するときに一度計算される反復キーです。 is_initフィールドは、Kuznyechikなどのオブジェクトが作成されたことがあるかどうかを示すフラグです。このフラグは、プログラムの起動時に多くの係数とアルゴリズムパラメータが欠落しているという事実のために必要です。最初の初期化で、それらは計算され、プログラムが終了するまでメモリに保存されます。

上記を考慮すると、コピーコンストラクターの存在についてコメントする必要がありますが、このコンストラクターを持たないByteBlockオブジェクトはクラス内にあります。実際には、コピー時に、キー配列からの反復キーの要素ごとのディープコピーが発生します。

グローバル変数とその初期化

使用されるグローバル変数

 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; }

乗算関数について説明するのは興味深いでしょう。その特異性は、線形変換を実行するときに、すべての計算が因子リングGL（2）[x] / p（x）で実行されるという事実にあります。ここで、p（x）= x ^ 8 + x ^ 7 + x ^ 6 + x + 1.最初のサイクルでは、GL（2）の係数で指定された多項式を乗算します。 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ライブラリに精通している人はdeja vuの感覚を持っているかもしれず、それは正当化されるでしょう。実際、このライブラリで使用されたのは、ブロック暗号と暗号化モードの相互作用の実装に対するまさにこのアプローチです。

このテンプレートクラスと連携してブロック暗号を使用できるようにするには、それを実装するクラスが次の要件を満たしている必要があります。

パブリックの暗号化および復号化メソッドは、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); }

復号化機能をコンポーネント部分に分割するという決定は冗長に思えます。これは、暗号文を介したフィードバックを伴う暗号化モードがこの手順の同時実行性をサポートしていない場合に当てはまります。次に、C ++ 11標準のstd ::スレッドを使用した復号化アルゴリズムのバリアントを検討します。

並行性復号化関数

 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; }

プロジェクトリポジトリはここにあります。

C ++のCFBモードでのGrasshopperブロック暗号の実装