c - Keccak 中的舍入常量

Question

最近，我一直在尝试实现 Keccak，这是 SHA-3 背后的密码学原语。然而，我遇到了一些问题，特别是在计算排列的“Iota”步骤中使用的轮常数时。

只是为了解决问题:是的。我知道它们是圆的常数。我知道我可以将它们硬编码为常量。但这有什么乐趣呢？

我特别提到了 FIPS 202 specification document关于 SHA-3 以及 Keccak 团队自己的 Keccak reference .然而，尽管我付出了努力，但我似乎无法得到正确的常量。我以前从未处理过位操作，所以如果我以完全错误的方式做某事，请随时告诉我。

rc 是 Keccak 的 FIPS 202 标准中定义的函数，它是一个线性反馈移位寄存器，其反馈多项式为 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，当您将其转换为 int 时，它会被截断为 3。怀疑这种情况是否发生在这种情况下，但为什么要冒险呢，因为在每次通过循环时将变量 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 位，您都可以将结果与 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);
    }
}