Написание C++ iostream, использующего потоковый шифр RC4. Как я могу оптимизировать мою реализацию?

Question

Я реализую собственный iostream (то есть с чтением, записью, поиском и закрытием), который использует потоковый шифр RC4 для шифрования и дешифрования. Один из контрактов этого потока заключается в том, что он является двунаправленным, и вызывающий код должен иметь возможность произвольного поиска любой позиции в потоке перед выполнением любого фактического чтения или записи.

Теперь, поскольку RC4 использует ключ, который опирается на все предыдущие операции подкачки вплоть до заданной позиции "сказать", как я могу включить возможность произвольного поиска любой позиции?

Очевидно, что я мог бы искать до позиции данного смещения поиска (отмеченного ЭТОМ БИТОМ в следующем примере), прежде чем делать фактический процесс преобразования ксинга, что-то вроде:

/**
 * @brief called from a stream's read or write function
 * @param in the input buffer
 * @param out the output buffer
 * @param startPosition the current stream position (obtained via the streams
 * tellg or tellp functions for read and write respectively)
 * @param length the number of bytes to transform
 */
void transform(char *in, char *out,
               std::ios_base::streamoff startPosition,
               long length)
{

    // need to reset sbox from member s_box each time this
    // function is called
    long sbox[256];
    for (int i = 0; i<256; ++i) {
        sbox[i]=m_sbox[i];
    }

    // ***THIS BIT***
    // need to run the swap operation startPosition times
    // to get sbox integer sequence in order
    int i = 0, j = 0, k = 0;
    for (int a=0; a < startPosition; ++a) {
        i = (i + 1) % 256;
        j = (j + sbox[i]) % 256;
        swapints(sbox, i, j);
    }

    // now do the actual xoring process up to the length
    // of how many bytes are being read or written
    for (int a=0; a < length; ++a) {
        i = (i + 1) % 256;
        j = (j + sbox[i]) % 256;
        swapints(sbox, i, j);
        k = sbox[(sbox[i] + sbox[j]) % 256];
        out[a] = in[a] ^ k;
    }

}

и тогда преобразование будет вызвано из чтения или записи реализации потока, что-то вроде:

MyStream&
MyStream::read(char * const buf, std::streamsize const n)
{
    std::ios_base::streamoff start = m_stream.tellg();
    std::vector<char> in;
    in.resize(n);
    (void)m_stream.read(&in.front(), n);
    m_byteTransformer->transform(&in.front(), buf, start, n);
    return *this;
}    

РЕДАКТИРОВАТЬ: поток не должен знать, как работает функция преобразования. Функция преобразования полностью независима, и я должен иметь возможность свободно менять различные реализации преобразования.

РЕДАКТИРОВАТЬ: функция swapints выглядит следующим образом:

void swapints(long *array, long ndx1, long ndx2)
{
    int temp = array[ndx1];
    array[ndx1] = array[ndx2];
    array[ndx2] = temp;
}

Реальная проблема с вышеупомянутой функцией преобразования заключается в ее медлительности, потому что она должна выполнить начальные операции подкачки startPosition, прежде чем будет выполнено собственное преобразование xor. Это очень проблематично, когда выполняется много операций поиска. Теперь я слышал, что RC4 должен быть быстрым, но моя (вероятно, плохая реализация) предлагает иное, учитывая начальный набор операций подкачки.

Поэтому мой реальный вопрос: как можно оптимизировать приведенный выше код, чтобы уменьшить количество необходимых операций? В идеале я хотел бы исключить начальный ("ЭТОТ БИТ") набор операций подкачки

РЕДАКТИРОВАТЬ: оптимизация начальной настройки sbox, вероятно, тривиальна (например, используя memcpy, как предложено egur). Я думаю, что важная оптимизация заключается в том, как оптимизировать цикл, помеченный ЭТОМ БИТОМ. Возможно, все эти переменные можно запрограммировать более кратко, без необходимости в цикле for.

Спасибо,

Бен

Answer 1

После некоторых исследований выясняется, что произвольный доступ к ключевому потоку RC4 невозможен. Смотрите обсуждение по этой ссылке: crypto.stackexchange. Лучшей альтернативой (как указал Россум в своем комментарии) является использование блочного шифра в режиме счетчика.

В режиме счетчика вы выполняете шифрование последовательности чисел. Эта последовательность является инкрементной и является длиной всего потока данных. Итак, скажем, вы хотите зашифровать 8 байтов данных, начиная с позиции "16" исходного потока данных, используя 64-битный (8 байт) блочный шифр.

Необходимо зашифровать 8 байтов, поскольку вы одновременно обрабатываете 8 байтов простого текста. Поскольку позиция, которую мы хотим случайным образом сместить, равна 16, мы по существу зашифровываем "блок 3" этой числовой последовательности (байты от 0 до 7 == блок 1, байты с 8 по 15 == блок 2, байты с 16 по 23 == блок 3 и так далее...)

Например, используя алгоритм XTEA, который шифрует блоки по 8 байт с использованием 128-битного ключа, мы бы сделали что-то вроде:

Блок 3:

// create a plain text number sequence 
uint8_t plainText[8];
plainText[0] = 16;
plainText[1] = 17;
.
.
.
plainText[7] = 23;

// encrypt the number sequence
uint8_t cipherText[8];
applyXTEATransformation(plainText, cipherText, keyOfLength128Bit);

// use the encrypted number sequence as a 
// key stream on the data to be encrypted
transformedData[16] = dataToBeEncrypted[16] ^ cipherText[0];
transformedData[17] = dataToBeEncrypted[17] ^ cipherText[1];
.
. 
.
transformedData[23] = dataToBeEncrypted[23] ^ cipherText[7];

tldr: я хотел сделать произвольный доступ на RC4, но обнаружил, что это невозможно, поэтому вместо этого использовал режим счетчика на блочном шифре XTEA.

Бен

Answer 2

Изменить все % 255 в & 0xff, намного быстрее:

i = (i + 1) % 256;

Для того, чтобы:

i = (i + 1) & 0xFF;

Редактировать:

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

void transform(char *in, char *out,
           long length,
           unsigned char* sbox)

Временный sbox должен быть членом MyStream учебный класс. Функция чтения должна быть:

MyStream&
MyStream::read(char * const buf, std::streamsize const n)
{
    std::ios_base::streamoff start = m_stream.tellg();
    std::vector<char> in;
    in.resize(n);
    (void)m_stream.read(&in.front(), n);

    // init m_TempSbox on first call
    if (m_FirstCall) {
        initTempSbox();
    }

    m_byteTransformer->transform(&in.front(), buf, n, m_TempSbox);
    return *this;
}