Keccak圆常数

Question

最近，为了解决这个问题，我一直在尝试实现Keccak，SHA-3背后的密码原语。但是，我遇到了一些问题，特别是在计算置换的"Iota“步骤中使用的圆形常量方面。

只是为了让它远离这条路:是的。我知道它们是圆的常数__。我知道我可以把它们硬编码成常量。但这其中的乐趣何在？

我特别提到了SHA-3上的FIPS 202规格文件，以及Keccak团队自己的Keccak参考。然而，尽管我的努力，我似乎不能以正确的常量结束。我以前从来没有处理过比特操作，所以如果我做了完全错误的事情，可以让我知道。

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}。

预期输出(圆整常数)定义如下:0x0000000001、0x00000000000082、0x8000000000000a、0x800000000008000、0x000000000000b、0x0000000000001、0x000000000001、0x8000000000081、0x800000000009、0x0000000000008、0x000000000000008、0x00000000000088、0x0000000000009、0x0000000000a、0x0000000000a、0x000000000080、0x000000000001、0x000000000001、0x000000000081、0x000000000080、0x0000000080、0x0000000080、0x0000000080、0x0000000080、0x0000000080、0x0000000080、0x0000000080、0x0000000080、0x00000000800、0x0000000080、0x0000000080、0x0000000080、0x0000000080、0x000000000001、0x8000000000001、0x8000000000001、0x800000000009、0x000000000000800、0x000000000088、0x00000000000088、0x00000000009、0x0000000000a、0x0000000000a、0x0000000000a、0x000000000001、0x00000000001、0x0000000001、0x80000000081、0x8000000008b、0x800000000008b、0x800000000008b、0x800000000008b、0x800000000008b、0x800000000008b、0x8000000008b、0x80000000000b、0x

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