1

Recently, just for the heck of it, I've been playing around with an attempt at implementing Keccak, the cryptographic primitive behind SHA-3. I've run into some issues however, specifically with calculating the round constants used in the "Iota" step of the permutation.

Just to get it out of the way: Yes. I know they are round constants. I know I could hard code them as constants. But where's the fun in that?

I've specifically been referencing the FIPS 202 specification document on SHA-3 as well as the Keccak team's own Keccak reference. However, despite my efforts, I can't seem to end up with the correct constants. I've never dealt with bit manipulation before, so if I'm doing something the complete wrong way, feel free to let me know.

rc is a function defined in the FIPS 202 standard of Keccak that is a linear feedback shift register with a feedback polynomial of x^8 + x^6 + x^5 + x^4 + 1.

The values of t (specific to SHA-3) are defined as the set of integers that includes j + 7 * i_r, where i_r = {0, 1, ..., 22, 23} and j = {0, 1, ..., 4, 5}.

The expected outputs (the round constants) are defined as follows: 0x0000000000000001, 0x0000000000008082, 0x800000000000808a, 0x8000000080008000, 0x000000000000808b, 0x0000000080000001, 0x8000000080008081, 0x8000000000008009, 0x000000000000008a, 0x0000000000000088, 0x0000000080008009, 0x000000008000000a, 0x000000008000808b, 0x800000000000008b, 0x8000000000008089, 0x8000000000008003, 0x8000000000008002, 0x8000000000000080, 0x000000000000800a, 0x800000008000000a, 0x8000000080008081, 0x8000000000008080, 0x0000000080000001, and 0x8000000080008008.

rc Function Implementation

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 Function Call

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

Any help on this matter is much appreciated.

4

1 回答 1

3

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

  1. j循环需要从 0 计数到 6。那是因为 2^6-1 = 63。所以如果永远j不是 6，则输出永远不能设置 MSB，即 0x8... 的输出是不可能的。

  2. 对于这种类型的应用程序，使用该pow函数通常不是一个好主意。doublevalues 有一个比期望值略低的坏习惯，例如 4 实际上是 3.99999999999，当您将其转换为int. 在这种情况下发生的情况令人怀疑，但为什么要冒险呢，因为shift每次通过循环时很容易将变量乘以 2。

  3. 的最大值t是 7*23+6 = 167，所以% 255什么都不做（至少在这段代码中i和的值）。t此外，没有必要将t == 0其视为特殊情况。为 0时循环不会运行t，因此默认结果为 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);
    }
}
于 2018-10-22T08:27:41.967 回答