Круглые константы в Кеччаке - PullRequest
Новая
       49

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

0 голосов
/ 22 октября 2018

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

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

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

rc - это функция, определенная в стандарте FccS 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);
}

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

1 Ответ

0 голосов
/ 22 октября 2018

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

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