Эффективное (исключающее ИЛИ (b + 1)) известное (исключающее ИЛИ b) в C для алгоритма ChaCha

В настоящее время я пытаюсь улучшить реализацию алгоритма ChaCha. Вот мой код (написанный на C):

#include <string.h> // memcpy
#include <stddef.h> // size_t
#include <stdint.h> // uint32_t

typedef uint32_t ChaChaSigma [4];
typedef uint32_t ChaChaKey [8];
typedef uint32_t ChaChaNonce [4];
typedef enum ChaChaStandard {
    kOriginal,
    kIetf
} ChaChaStandard;
typedef short ChaChaRounds;
typedef uint32_t ChaChaBlock [16];

typedef struct ChaChaMatrix {
    union {
        struct {
            ChaChaSigma sigma; // The costant used. Usually "expand 32-byte k".
            ChaChaKey key;     // The key used. Has to be hashed or padded by the user manually.
            ChaChaNonce nonce; // The nonce used. It's formed by a block counter and an iv.
        };
        uint32_t words [16];   // The words of the matrix. Used for raw access.
    };
    ChaChaStandard standard;
    ChaChaRounds rounds;
} ChaChaMatrix;

// trick to have default values
#define INIT_CHACHAMATRIX(...) ((ChaChaMatrix){ 
    .sigma = {0x61707865UL, 0x3320646eUL, 0x79622d32UL, 0x6b206574UL}, 
    .key = {0, 0, 0, 0, 0, 0, 0, 0}, 
    .nonce = {0, 0, 0, 0}, 
    .standard = kOriginal, 
    .rounds = 20, 
    __VA_ARGS__ 
})

uint32_t rotl32 (uint32_t n, short r) {
    return (n << r) | (n >> (32 - r));
}

void ChaChaStep (uint32_t x[16], size_t a, size_t b, size_t c, short r) {
    x[a] += x[b];
    x[c] = rotl32(x[c] ^ x[a], r);
}

void ChaChaQuarterRound (uint32_t x[16], size_t a, size_t b, size_t c, size_t d) {
    ChaChaStep(x, a, b, d, 16);
    ChaChaStep(x, c, d, b, 12);
    ChaChaStep(x, a, b, d,  8);
    ChaChaStep(x, c, d, b,  7);
}

void ChaChaVerticalRound (uint32_t x[16]) {
    ChaChaQuarterRound(x, 0, 4,  8, 12);
    ChaChaQuarterRound(x, 1, 5,  9, 13);
    ChaChaQuarterRound(x, 2, 6, 10, 14);
    ChaChaQuarterRound(x, 3, 7, 11, 15);
}

void ChaChaDiagonalRound (uint32_t x[16]) {
    ChaChaQuarterRound(x, 0, 5, 10, 15);
    ChaChaQuarterRound(x, 1, 6, 11, 12);
    ChaChaQuarterRound(x, 2, 7,  8, 13);
    ChaChaQuarterRound(x, 3, 4,  9, 14);
}

void ChaChaComputeBlock (ChaChaMatrix * matrix, ChaChaBlock * block) {
    memcpy(block, matrix, sizeof(uint32_t)*16);
    short i;
    for (i = 0; i < matrix->rounds; i+=2) {
        ChaChaVerticalRound(*block);
        ChaChaDiagonalRound(*block);
    }
    for (i = 0; i < 16; i++) {
        (*block)[i] += matrix->words[i];
    }
}

Я все еще планирую реализацию для увеличения счетчика без необходимости иметь дело с приведением типов и стандартами IETF / Original.

Второе действие, выполняемое с матрицей, использует переменную часть (счетчик блоков внутри одноразового номера). Потому что это (обычно) увеличивается только на 1 единицу каждый раз, когда мне интересно, есть ли способ повысить эффективность XOR.

Я открыл Excel и построил график BITXOR(314, i), i – переменная от 0 до 999. На графике виден красивый узор. Каждый 0x100*n (другими словами: каждые 4 “больших шага вниз” на 0x40 ед.) прыгает. Шаблон похож на XOR(0, ..., n) один (?)

график

Мой вопрос:

  • Есть ли эффективные способы расчета a XOR (b+1) известный a XOR b? Шаблон, на мой взгляд, предполагает, что это возможно, но я недостаточно умен, чтобы найти решение …
  • Есть ли смысл в реализации этого крошечного улучшения?

PS: если программный стековый обмен лучше соответствует формату вопроса, я могу переместить его туда 🙂

1 ответ
1

Небольшой обзор

пытаюсь улучшить мою реализацию алгоритма ChaCha

static функция

rotl32() не является четко определенной функцией для вращения, когда счетчик равен 0 (или 32). Здесь это не имеет значения, поскольку rotl32(n, 0) не используется. Поскольку функция подходит только для локального использования, сделайте ее static чтобы избежать использования этой ограниченной целевой функции другими модулями.

// uint32_t rotl32 (uint32_t n, short r) {
static uint32_t rotl32 (uint32_t n, short r) {

Избегайте магических чисел

Почему 16 ниже? Почему uint32_t? Можно было посмотреть код и в конечном итоге увидеть, что memcpy() делает, а как насчет прямых альтернатив ?:

void ChaChaComputeBlock (ChaChaMatrix * matrix, ChaChaBlock * block) {
  // memcpy(block, matrix, sizeof(uint32_t)*16);
  memcpy(block, matrix, sizeof *block);
  // or 
  *block = (ChaChaBlock){0};

Есть ли эффективные способы вычисления XOR (b + 1), известного как XOR b? Шаблон, на мой взгляд, предполагает, что это возможно, но я недостаточно умен, чтобы найти решение …

Возможно, сейчас я его не вижу.
Еще несколько небольших идей:

int против. short

Небольшая неэффективность заключается в использовании суб-int параметры / объекты. int обычно лучший размер для четкого кода.

// uint32_t rotl32 (uint32_t n, short r) {
uint32_t rotl32 (uint32_t n, int r) {

 // short i;
 int i;

const, restrict

Сообщите компилятору, что matrix и block не перекрываются.

Использовать const чтобы обеспечить более широкое функциональное использование и, возможно, некоторые оптимизации.

// void ChaChaComputeBlock (ChaChaMatrix * matrix, ChaChaBlock * block) {
void ChaChaComputeBlock (const ChaChaMatrix * restrict matrix, 
    ChaChaBlock * restrict block) {

Есть ли смысл в реализации этого крошечного улучшения?

Возможно да. Иметь ввиду Действительно ли преждевременная оптимизация – корень всех зол?
.

  • Большое спасибо за подробный ответ! Я должен использовать static ключевое слово, даже если я использую chahca.c для объявления и определения rotl32 и определения всех других функций?

    – ДадиБит

  • @DadiBit Если функция используется только в chahca.c, подумай о том, чтобы сделать это static. Другие функции также должны быть объявлены в chahca.h.

    – chux – Восстановить Монику

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *