Круглые константы в Кеччаке

Question

Недавно, просто ради этого, я пытался реализовать Keccak, криптографический примитив SHA-3. Однако я столкнулся с некоторыми проблемами, в частности с вычислением округлых констант, используемых на шаге "Йота" перестановки.

Просто чтобы убрать это с дороги: Да. Я знаю, что они круглые константы. Я знаю, что могу жестко закодировать их как константы. Но где в этом веселье?

Я специально ссылался на документ спецификации FIPS 202 на SHA-3, а также на собственный справочник Keccak команды Keccak. Однако, несмотря на мои усилия, я не могу получить правильные константы. Я никогда раньше не сталкивался с битовыми манипуляциями, поэтому, если я делаю что-то совершенно неправильно, не стесняйтесь, дайте мне знать.

rc является функцией, определенной в стандарте FIPS 202 Keccak, который является регистром сдвига с линейной обратной связью с полиномом обратной связи x^8 + x^6 + x^5 + x^4 + 1,

Значения t (специфичные для SHA-3) определяются как набор целых чисел, который включает j + 7 * i_r где i_r = {0, 1, ..., 22, 23} и j = {0, 1, ..., 4, 5}.

Ожидаемые результаты (круглые константы), определяются следующим образом: 0x0000000000000001, 0x0000000000008082, 0x800000000000808a, 0x8000000080008000, 0x000000000000808b, 0x0000000080000001, 0x8000000080008081, 0x8000000000008009, 0x000000000000008a, 0x0000000000000088, 0x0000000080008009, 0x000000008000000a, 0x000000008000808b, 0x800000000000008b, 0x8000000000008089, 0x8000000000008003, 0x8000000000008002, 0x8000000000000080, 0x000000000000800a, 0x800000008000000a, 0x8000000080008081, 0x8000000000008080, 0x0000000080000001 и 0x8000000080008008.

Реализация функции rc

uint64_t rc(int t)
{
    if(t % 255 == 0)
    {
        return 0x1;
    }

    uint64_t R = 0x1;

    for(int i = 1; i <= t % 255; i++)
    {
        R = R << 0x1;
        R |= (((R >> 0x0) & 0x1) ^ ((R >> 0x8) & 0x1)) << 0x0;
        R |= (((R >> 0x4) & 0x1) ^ ((R >> 0x8) & 0x1)) << 0x4;
        R |= (((R >> 0x5) & 0x1) ^ ((R >> 0x8) & 0x1)) << 0x5;
        R |= (((R >> 0x6) & 0x1) ^ ((R >> 0x8) & 0x1)) << 0x6;
        R &= 0xFF;
    }

    return R & 0x1;
}

вызов функции rc

for(int i_r = 0; i_r < 24; i_r++)
{

    uint64_t RC = 0x0;

    // TODO: Fix so the limit is not constant
    for(int j = 0; j < 6; j++)
    {
        RC ^= (rc(j + 7 * i_r) << ((int) pow(2, j) - 1));
    }

    printf("%llu\n", RC);
}

Любая помощь по этому вопросу высоко ценится.

Answer 1

Я сделал несколько случайных изменений в коде, и теперь он работает. Вот основные моменты:

1. j цикл должен считать от 0 до 6. Это потому, что 2^6-1 = 63. Так что если j никогда не равен 6, то на выходе никогда не может быть установлен MSB, т. е. на выходе 0x8... невозможно.

2. С использованием pow Функция, как правило, плохая идея для этого типа приложения. double значения имеют неприятную привычку быть немного ниже, чем хотелось бы, например, 4 на самом деле 3.99999999999, который усекается до 3, когда вы конвертируете его в int, Сомнительно, что происходило в этом случае, но зачем рисковать, так как легко просто умножить переменную shift по 2 на каждый проход через петлю.

3. Максимальное значение для t 7*23+6 = 167, поэтому % 255 ничего не делает (по крайней мере, со значением i а также t в этом коде). Кроме того, нет необходимости лечить t == 0 как особый случай. Цикл не будет работать, когда t 0, поэтому по умолчанию результат 0x1.

4. Реализация регистра сдвига с линейной обратной связью довольно проста в C. Каждый член полинома соответствует одному биту. x^8 просто 2^8, что 0x100 а также x^6 + x^5 + x^4 + 1 является 0x71, Так что всякий раз, когда немного 0x100 установлен, вы XOR результат 0x71,

Вот обновленный код:

#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>

uint64_t rc(int t)
{
    uint64_t result = 0x1;

    for (int i = 1; i <= t; i++)
    {
        result <<= 1;
        if (result & 0x100)
            result ^= 0x71;
    }

    return result & 0x1;
}

int main(void)
{
    for (int i = 0; i < 24; i++)
    {
        uint64_t result = 0x0;
        uint64_t shift = 1;
        for (int j = 0; j < 7; j++)
        {
            uint64_t value = rc(7*i + j);
            result |=  value << (shift - 1);
            shift *= 2;
        }            
        printf("0x%016" PRIx64 "\n", result);
    }
}