c - Keccak的圆形常量

最近，我一直在尝试实现Keccak，这是SHA-3背后的加密原语。不过，我遇到了一些问题，特别是在计算排列的“Iota”步骤中使用的圆形常数时。
只是想让它让开：是的。我知道它们是圆形常数。我知道我可以把它们硬编码成常量。但这其中的乐趣在哪里呢？
我特别提到了SHA-3上的FIPS 202 specification document以及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、0x8000000000808A，
0x8000000080008000，0x000000000000808b，0x0000000080000001，
0x8000000080008081、0x80000000008009、0x000000000000008a，
0x0000000000000088、0x0000000080008009、0x000000008000000a，
0x000000008000808b、0x8000000000008b、0x80000000008089，
0x80000000008003、0x80000000008002、0x80000000000080，
0x000000000000800a、0x80000000800000A、0x8000000080008081，
0x80000000008080、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);
}

非常感谢你在这件事上的帮助。

最佳答案

我对代码做了一些随机更改，现在它可以工作了。以下是亮点：
j循环需要从0计数到6。因为2^6-1=63。因此，如果j永远不是6，则输出永远不能设置MSB，即输出为0x8。。。不可能。
对于这种类型的应用程序，使用pow函数通常是个坏主意。double值有一个比期望值稍低的坏习惯，例如4实际上是3.999999999，当您将其转换为int时，它会被截断为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);
    }
}

关于c - Keccak的圆形常量，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/52922526/