Keccak 中的舍入常量

Question

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

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

我特别提到了 FIPS 202 specification document on SHA-3 as well as the Keccak team's own 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

我对代码进行了一些随机更改，现在它可以运行了。以下是要点：

j循环需要从0数到6。那是因为2^6-1 = 63。所以如果j永远不是6，那么输出可以永远不要设置 MSB，即输出 0x8... 是不可能的。
使用 pow 函数对于此类应用程序通常不是一个好主意。 double 值有一个坏习惯，即略低于期望值，例如4 实际上是 3.99999999999，当您将它转换为 int 时，它会得到 t运行cated 为 3。在这种情况下发生的情况令人怀疑，但为什么要冒险，因为在每次循环时将变量 shift 乘以 2 很容易。
t 的最大值是 7*23+6 = 167，所以 % 255 什么都不做（至少对于 i 的值和t 在此代码中）。此外，无需将 t == 0 视为特例。当t为0时，循环不会运行，所以结果默认为0x1。
在 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);
    }
}

Keccak 中的舍入常量

Round Constants in Keccak

c

cryptography

bit-manipulation

sha-3

keccak