И вновь в нашем блоге мы решили затронуть тему криптографии, но сделать это на примере двух разных алгоритмов Raiden и RC5. Оба алгоритма разрабатывались разными разработчиками и принадлежат к разным семействам, но мы покажем, что может быть общего между ними и как это можно использовать.
Стоит отметить, что оба алгоритма являются алгоритмами симметричного шифрования, что означает, что для процедур шифрования и дешифрования используется один и тот же ключ. Также, есть еще одно общее свойство у алгоритмов Raiden и RC5 — эти алгоритмы представляют собой блочные шифры, а это означает, что открытый текст они обрабатывают поблочно. Пока не будем останавливаться на различиях и предположим, что открытый текст, а также ключ и шифротекст имеют один и тот же «универсальный» в своем роде формат — поток байтов. Это обстоятельство уже позволяет нам сделать многое, к примеру, создать следующий интерфейс:
/// Блочный шифр interface BlockCipher { /// шифрование одного блока ubyte[] cryptBlock(ubyte[] data); /// дешифрование одного блока ubyte[] decryptBlock(ubyte[] data); /// блок записать как число final ulong block2size(ubyte[] block) { return BitUtils.join8to64(block[0..8]); } /// размер блока в байтах @property ulong blockSize(); /// размер блока записать как блок final ubyte[] size2block(ulong size) { return BitUtils.split64to8(size); } }
Этот интерфейс позволит описать почти любой блочный шифр, от программиста требуется лишь реализовать несколько довольно простых и общих функций: cryptBlock/decryptBlock
— шифрование/дешифрование блока, представленного потоком байтов; block2size
— извлечение из блока данных и представление их в виде числа с типом ulong
, а также дуальная к ней функция size2block
которая необходима для перевода числа с типом ulong
в блок данных (массив байтов). Помимо этого, интерфейс предполагает наличие свойства, которое выдает размер блока данных в байтах. Кажется странным такой выбор, но на самом деле последние два метода и свойство позволят воплотить разные режимы шифрования на самом общем уровне.
Для такой реализации потребуется ряд вспомогательных функций, которе манипулируют битами в байтах, а также целыми наборами байтов — разного рода сдвиги, сборки, а также разбор байтов в разные типы:
module bitutils; class BitUtils { // циклический сдвиг битов влево static T rol(T)(T value, T shift) { return (value << shift) | (value >> (T.sizeof * 8 - shift)); } static T ror(T)(T value, T shift) { return (value >> shift) | (value << (T.sizeof * 8 - shift)); } // собрать uint из массива ubyte static uint join8to32(ubyte[] block) { uint number = block[0]; for (byte j = 1; j < 4; j++) { number = (number << 8) | block[j]; } return number; } static join8to64(ubyte[] block) { ulong number = block[0]; for (byte j = 1; j < 8; j++) { number <<= 8; number |= block[j]; } return number; } // создать одно 64-битное число из 2 32-битных static ulong join32to64(uint L, uint R) { ulong result; result |= L; result <<= 32; result |= R; return result; } // собрать массив ubyte из uint static ubyte[] split32to8(uint size) { ubyte[] block; for (byte i = 24; i > 0; i -= 8) { block ~= cast(ubyte) ((size >> i) & 0xFF); } block ~= size & 0xff; return block; } static ubyte[] split64to8(ulong size) { ubyte[] block; for (byte i = 56; i > 0; i -= 8) { block ~= cast(ubyte) ((size >> i) & 0xFF); } block ~= size & 0xff; return block; } // распределение блока на 2 32 битных значения static void splitLR(ulong LR, out uint L, out uint R) { L = uint((LR >> 32) & 0xffffffff); R = uint(LR & 0xffffffff); } }
Часть из описанных методов уже упоминалась в интерфейсе выше и используется для манипуляции с блоком шифра: join8to64
— для сборки 8 байтов в один ulong
и противоположный по смыслу метод split64to8
— для разделения одного ulong
на 8 байтов. Некоторые из описанных процедур нам также пригодятся в реализации алгоритмов Raiden и RC5 (опять же общая черта), а именно циклические сдвиги влево/вправо, сборки байтов в 32 и 64-разрядные типы, но это вы увидите далее.
Теперь же определим еще ряд полезных интерфейсов и абстрактных классов
/// основной класс криптографических алгоритмов interface CipherAlgorithm { /// шифрование потока байтов ubyte[] crypt(ubyte[] data, ubyte[] iv); /// дешифрование потока байтов ubyte[] decrypt(ubyte[] data, ubyte[] iv); } /// 64-битные шифры abstract class Block64Cipher : BlockCipher { /// размер блока в байтах @property const ulong blockSize() { return 8UL; } } /// 128-битные шифры abstract class Block128Cipher : BlockCipher { /// размер блока в байтах @property const ulong blockSize() { return 16UL; } }
Интерфейс требуется в основном для реализации разного рода фабрик, а также для создания дополнительного ограничения, которое способно о себе напомнить, если вдруг случится забыть пару методов. Абстрактные классы в данном случае берут на себя реализацию конкретной версии свойства, которое определяет размер блока шифровального алгоритма: для Raiden размер блока составляет 64 бита (8 байт) , а для RC5 — 128 битов (16 байт).
Реализация алгоритма Raiden выглядит так:
class Raiden : Block64Cipher { private { uint[4] _key; } void setup(ubyte[] key) { for (int i = 0; i < 4; i++) { _key[i] = BitUtils.join8to32(key[i*4..(i*4)+4]); } } ubyte[] cryptBlock(ubyte[] block) { uint b0 = BitUtils.join8to32(block[0..4]), b1 = BitUtils.join8to32(block[4..8]); uint[4] k = _key; uint sk; uint[2] result; for (uint i = 0; i < 16; i++) { sk = k[i % 4] = ((k[0] + k[1]) + ((k[2] + k[3]) ^ (k[0] << (k[2] & 0x1F)))); b0 += ((sk + b1) << 9) ^ ((sk-b1) ^ ((sk + b1) >> 14)); b1 += ((sk + b0) << 9) ^ ((sk-b0) ^ ((sk + b0) >> 14)); } result[0] = b0; result[1] = b1; return BitUtils.split32to8(b0) ~ BitUtils.split32to8(b1); } ubyte[] decryptBlock(ubyte[] block) { uint b0 = BitUtils.join8to32(block[0..4]), b1 = BitUtils.join8to32(block[4..8]); uint[4] k = _key; uint[16] subkeys; uint[2] result; for (int i = 0; i < 16; i++) { subkeys[i] = k[i % 4] = ((k[0] + k[1]) + ((k[2] + k[3]) ^ (k[0] << (k[2] & 0x1F)))); } for (int i = 15; i >= 0; i--) { b1 -= ((subkeys[i] + b0) << 9) ^ ((subkeys[i] - b0) ^ ((subkeys[i] + b0) >> 14)); b0 -= ((subkeys[i] + b1) << 9) ^ ((subkeys[i] - b1) ^ ((subkeys[i] + b1) >> 14)); } result[0] = b0; result[1] = b1; return BitUtils.split32to8(b0) ~ BitUtils.split32to8(b1); } }
Данный алгоритм очень прост, является своего рода развитием алгоритма TEA и имеет простую структуру, легко запоминается и имеет высокую скорость выполнения. Предполагается, что алгоритм более надежен, чем его предшественник и избавлен от ряда его слабостей, но вместе с тем, Raiden слабо исследован криптоаналитиками. Последнее обстоятельство не в пользу алгоритма, но стоит упомянуть и о том, что Raiden без проблем проходит статические тесты наподобие пакета Diehard.
Теперь рассмотрим реализацию RC5, которая также очень проста и описывается следующим кодом:
class RC5 : Block128Cipher { private { const int W = 64; const ulong PW = 0xB7E151628AED2A6B; const ulong QW = 0x9E3779B97F4A7C15; ulong[] L, S; int t; int b; int u; int c; uint _rounds; } void setup(ubyte[] key, uint rounds = 32) { ulong x, y; int i, j, n; u = W >> 3; b = cast(int) key.length; c = b % u > 0 ? b / u + 1 : b / u; L = new ulong[c]; for (i = b - 1; i >= 0; i--) { L[i / u] = BitUtils.rol(L[i / u], 8) + key[i]; } t = 2 * (_rounds + 1); S = new ulong[t]; S[0] = PW; for (i = 1; i < t; i++) { S[i] = S[i - 1] + QW; } x = y = 0; i = j = 0; n = 3 * max(t, c); for (int k = 0; k < n; k++) { x = S[i] = BitUtils.rol((S[i] + x + y), 3); y = L[j] = BitUtils.rol((L[j] + x + y), cast(int) (x + y)); i = (i + 1) % t; j = (j + 1) % c; } } ubyte[] cryptBlock(ubyte[] block) { ulong a = BitUtils.join8to64(block[0..8]); ulong b = BitUtils.join8to64(block[8..16]); a = a + S[0]; b = b + S[1]; for (int i = 1; i < _rounds + 1; i++) { a = BitUtils.rol((a ^ b), b) + S[2 * i]; b = BitUtils.rol((b ^ a), a) + S[2 * i + 1]; } return BitUtils.split64to8(a) ~ BitUtils.split64to8(b); } ubyte[] decryptBlock(ubyte[] block) { ulong a = BitUtils.join8to64(block[0..8]); ulong b = BitUtils.join8to64(block[8..16]); for (int i = _rounds; i > 0; i--) { b = BitUtils.ror((b - S[2 * i + 1]), a) ^ a; a = BitUtils.ror((a - S[2 * i]), b) ^ b; } b = b - S[1]; a = a - S[0]; return BitUtils.split64to8(a) ~ BitUtils.split64to8(b); } }
Честно сказать, что мы не сами разрабатывали эту реализацию, а слегка адаптировали версию, взятую из C# к реалиям в D. Алгоритм также имеет простую структуру и практически состоит из тех же операций, что и предыдущий, но способ расширения ключа и чередование операций в раундах алгоритма иные. Также алгоритм очень хорошо исследован, имеет удобную структуру при переменном размере ключа (от 0 до 255 бит) и крупный блок в 128 бит.
Оба алгоритма очень хорошие и имееют много общего, однако, можно сделать еще общую реализацию распространенных режимов шифрования, известных еще со времен разработки алгоритма DES.
Вот так можно реализовать уже упоминавшийся нами режим CBC (Cipher Block Chaining — режим сцепления блоков шифротекста) без привязки к конкретному алгоритму:
/// Щифровальные алгоритмы "с набивкой" abstract class PaddedBlockCipher { protected { BlockCipher _bc; } /// метод набивки 2 final ubyte[] padRight(ubyte[] data) { if (_bc !is null) { if (data.length < _bc.blockSize) { data ~= 0x01; } while (data.length < _bc.blockSize) { data ~= 0x00; } } return data; } } /// Режим сцепления блоков шифротекста class CipherBlockChaining : PaddedBlockCipher, CipherAlgorithm { this(BlockCipher bc) { _bc = bc; } ubyte[] crypt(ubyte[] data, ubyte[] iv) { ubyte[] crypted; if (_bc !is null) { auto ci = padRight(iv); ubyte[] block; foreach (ubyte[] b; data.chunks(_bc.blockSize)) { block = padRight(b); block[] ^= ci[]; block = _bc.cryptBlock(block); crypted ~= block; ci = block; } // добавить информацию о размере block = padRight(_bc.size2block(data.length)); block[] ^= ci[]; block = _bc.cryptBlock(block); crypted ~= block; } return crypted; } ubyte[] decrypt(ubyte[] data, ubyte[] iv) { ubyte[] decrypted; if (_bc !is null) { auto block = padRight(iv); foreach (ubyte[] b; data.chunks(_bc.blockSize)) { ubyte[] fb = _bc.decryptBlock(b); fb[] ^= block[]; decrypted ~= fb; block = b; } auto size = _bc.block2size(decrypted[$-_bc.blockSize..$]); decrypted = decrypted[0..size]; } return decrypted; } } /// Режим сцепления блоков шифротекста class CipherBlockChaining : PaddedBlockCipher, CipherAlgorithm { this(BlockCipher bc) { _bc = bc; } ubyte[] crypt(ubyte[] data, ubyte[] iv) { ubyte[] crypted; if (_bc !is null) { auto ci = padRight(iv); ubyte[] block; foreach (ubyte[] b; data.chunks(_bc.blockSize)) { block = padRight(b); block[] ^= ci[]; block = _bc.cryptBlock(block); crypted ~= block; ci = block; } // добавить информацию о размере block = padRight(_bc.size2block(data.length)); block[] ^= ci[]; block = _bc.cryptBlock(block); crypted ~= block; } return crypted; } ubyte[] decrypt(ubyte[] data, ubyte[] iv) { ubyte[] decrypted; if (_bc !is null) { auto block = padRight(iv); foreach (ubyte[] b; data.chunks(_bc.blockSize)) { ubyte[] fb = _bc.decryptBlock(b); fb[] ^= block[]; decrypted ~= fb; block = b; } auto size = _bc.block2size(decrypted[$-_bc.blockSize..$]); decrypted = decrypted[0..size]; } return decrypted; } }
А вот так можно реализовать CFB (CipherFeedback — режим обратной связи по шифротексту):
/// Режим обратной связи по шифротексту class CipherFeedback : PaddedBlockCipher, CipherAlgorithm { this(BlockCipher bc) { _bc = bc; } ubyte[] crypt(ubyte[] data, ubyte[] iv) { ubyte[] crypted; if (_bc !is null) { auto ci = padRight(iv); ubyte[] block; foreach (ubyte[] b; data.chunks(_bc.blockSize)) { block = padRight(b); block[] ^= _bc.cryptBlock(ci)[]; crypted ~= block; ci = block; } block = padRight(_bc.size2block(data.length)); block[] ^= _bc.cryptBlock(ci)[]; crypted ~= block; } return crypted; } ubyte[] decrypt(ubyte[] data, ubyte[] iv) { ubyte[] decrypted; if (_bc !is null) { auto ci = padRight(iv); ubyte[] block; foreach (ubyte[] b; data.chunks(_bc.blockSize)) { block = _bc.cryptBlock(ci); block[] ^= padRight(b)[]; decrypted ~= block; ci = b; } auto size = _bc.block2size(decrypted[$-_bc.blockSize..$]); decrypted = decrypted[0..size]; } return decrypted; } }
И остальные режимы можно реализовывать таким же способом! К примеру, мы еще смогли реализовать режим OFB и CTR, но об этом мы расскажем как-нибудь в другой раз, когда покажем вам еще ряд интересных и простых реализаций. Стоит упомянуть, что все представленные реализации можно отнести в разряд уже готовых криптопримитивов с помощью которых при должном подходе можно реализовать шифрование файлов или другие криптографические операции.
На этом мы заканчиваем наше введение в реализации Raiden и RC5, и ниже прилагаем ряд ссылок для ознакомления с темой шифровальных алгоритмов:
Также напоминаем, что использование представленного кода в реальных решениях довольно рискованная затея и написание криптографии своими руками без должной подготовки — не очень здравая идея. Если хотите использовать надежное и стабильное шифрование в своих продуктах обратитесь лучше к проверенным специалистами и обществом решениям.