SHA-3 的所有循环常数究竟是如何生成的？

Question

我似乎无法获得为 SHA-3 生成所有循环常量的确切算法。

可在此处找到说明：

crypto.stackexchange.com/questions/6444。

可以在 github.com/Caligatio/jsSHA/blob/master/src/sha_dev.js#L1450 中找到这些值：

rc_sha3 = [
        new Int_64(0x00000000, 0x00000001), 
        new Int_64(0x00000000, 0x00008082),
        ...,
        new Int_64(0x00000000, 0x80000001), 
        new Int_64(0x80000000, 0x80008008)
];

或 github.com/emn178/js-sha3/blob/master/src/sha3.js#L24（另一种形式）：

var RC = [1, 0, 32898, 0, 32906, 2147483648, 
...,
32896, 2147483648, 2147483649, 0, 2147516424, 2147483648];

我访问了 keccak.noekeon.org 以阅读 Keccak 参考资料。我已经阅读了可下载 "Files for the Keccak reference" 中的所有文件。但我仍然不明白所有这些常量是从哪里来的。我以预先计算的形式看到它们，但是用于生成它们的实际算法的描述在哪里？

例如，考虑以下来源：

android.googlesource.com/.../bouncycastle/crypto/digests/KeccakDigest.java；

read.pudn.com/.../KeccakPermutationReference.c__.htm；

www.grepcode.com/file/.../bouncycastle/crypto/digests/SHA3Digest.java。

我尝试将上述来源中看似相关的代码转换为 JS：

function l(a, b) { this.x = a; this.y = b; };

function l_left(c, d)
{
    var r;
    if (32 >= d)
    {
        r = new l(
                (c.x << d) | ((c.y >>> (32 - d))),
                c.y << d
            );
    }
    else
    {
        r = new l(
                c.y << (d - 32),
                0
            );
    }
    return r;
};

function _xor(a, b)
{
    return new l(
        a.x ^ b.x,
        a.y ^ b.y
    );
}

var keccakRoundConstants = [];

function LFSR86540(LFSR)
{
    if ((LFSR & 0x80) != 0)
    {
        LFSR = ((LFSR << 1) ^ 0x71);
    }
    else
    {
        LFSR <<= 1;
    }
    return ( LFSR & 0x01) != 0;
}

function keccakInitializeRoundConstants()
{
    var L = new l(0,1);
    var LFSRstate = 0x01;
    var i, j, bitPosition;
    for (i = 0; i < 24; i++)
    {
        keccakRoundConstants[i] = new l(0,0);
        for (j = 0; j < 7; j++)
        {
            bitPosition = (1 << j) - 1;
            if (LFSR86540(LFSRstate))
            { 
                keccakRoundConstants[i] = _xor(keccakRoundConstants[i], (l_left(L, bitPosition) ));
            }
        }
    }
    return keccakRoundConstants;
};

keccakInitializeRoundConstants();    
console.log(keccakRoundConstants);

但它显然不会生成任何东西（所有值都设置为零）。
任何人都可以提供可读的伪代码或 Javascript 版本来说明这些常量是如何生成的吗？

Answer 1

之所以LFSR是Java版本中的byte[]，是为了让LFSR86540对其进行修改。您可以使函数 return 成为新值：

function LFSR86540(LFSR) {
    return LFSR & 0x80 ?
        (LFSR << 1) ^ 0x71 :
        LFSR << 1;
}

并相应地修改keccakInitializeRoundConstants：

LFSRstate = LFSR86540(LFSRstate);
if (LFSRstate & 1) {
    keccakRoundConstants[i] = x(keccakRoundConstants[i], l_left(L, bitPosition));
}

并修正 l_left:

- c.y << n
+ c.y << d

并修复 LFSR86540 在更新之前读取最低有效位 的错误：

if (LFSRstate & 1) { keccakRoundConstants[i] = x(keccakRoundConstants[i], l_left(L, bitPosition)); } LFSRstate = LFSR86540(LFSRstate);

瞧：匹配常量。

'use strict'; function hex32(n) { var s = (n >>> 0).toString(16); return "0x" + "0".repeat(8 - s.length) + s; } function Int64(a, b) { this.x = a; this.y = b; } Int64.prototype.shiftLeft = function (d) { return d <= 32 ? new Int64( (this.x << d) | (this.y >>> (32 - d)), this.y << d ) : new Int64( this.y << (d - 32), 0 ); }; Int64.prototype.xor = function (b) { return new Int64( this.x ^ b.x, this.y ^ b.y ); }; Int64.prototype.toString = function () { return "Int64(" + hex32(this.x) + ", " + hex32(this.y) + ")"; }; function LFSR86540(LFSR) { return (LFSR & 0x80) != 0 ? (LFSR << 1) ^ 0x71 : LFSR << 1; } function keccakInitializeRoundConstants() { var keccakRoundConstants = []; var L = new Int64(0, 1); var LFSRstate = 0x01; for (var i = 0; i < 24; i++) { keccakRoundConstants[i] = new Int64(0, 0); for (var j = 0; j < 7; j++) { var bitPosition = (1 << j) - 1; if (LFSRstate & 1) { keccakRoundConstants[i] = keccakRoundConstants[i].xor(L.shiftLeft(bitPosition)); } LFSRstate = LFSR86540(LFSRstate); } } return keccakRoundConstants; }; keccakInitializeRoundConstants().forEach(function (k) { console.log(String(k)); });

Answer 2

请记住，移位运算符 a << b 在 Java 和 Java 脚本中的实际含义是 a << (b & 31)。因此，原来的 .leftShift 是有缺陷的。我使用了@Ryan-s 的代码并修复了它：

'use strict';

function hex32(n) {
    var s = (n >>> 0).toString(16);
    return "0x" + "0".repeat(8 - s.length) + s;
}

function Int64(hi, lo) {
    this.hi = hi;
    this.lo = lo;
}

Int64.of = function(hi, lo) {
  return new Int64(hi, lo);
};

Int64.prototype.shiftLeft = function (d) {
  var hi = this.hi, lo = this.lo;
  if (d < 32) {
    if (d <= 0) return this;
    return Int64.of((hi << d) | (lo >>> (32 - d)), lo << d);
  }
  if (d < 64) {
    if (d <= 32) return Int64.of(lo, 0);
    return Int64.of(lo << (d - 32), 0);
  }
  return Int64.of(0, 0);
};

Int64.prototype.xor = function (b) {
    return new Int64(
        this.hi ^ b.hi,
        this.lo ^ b.lo
    );
};

Int64.prototype.toString = function () {
    return "Int64(" + hex32(this.hi) + ", " + hex32(this.lo) + ")";
};

function LFSR86540(LFSR) {
    return (LFSR & 0x80) != 0 ?
        ((LFSR << 1) & 0xff) ^ 0x71 :
        ((LFSR << 1) & 0xff);
}

function keccakInitializeRoundConstants() {
    var keccakRoundConstants = [];
    var L = new Int64(0, 1);
    var LFSRstate = 0x01;
    for (var i = 0; i < 24; i++) {
        keccakRoundConstants[i] = new Int64(0, 0);
        for (var j = 0; j < 7; j++) {
            var bitPosition = (1 << j) - 1;
            if (LFSRstate & 1) {
                keccakRoundConstants[i] = keccakRoundConstants[i].xor(L.shiftLeft(bitPosition));
            }
            LFSRstate = LFSR86540(LFSRstate);
        }
    }
    return keccakRoundConstants;
};

keccakInitializeRoundConstants().forEach(function (k) {
    console.log(String(k));
});

SHA-3 的所有循环常数究竟是如何生成的？

How exactly were all the round constants for SHA-3 generated?

javascript

algorithm

bit-manipulation

sha-3

lfsr