2

我似乎无法获得可以为 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 参考资料。我已阅读可下载的“Keccak 参考文件”中的所有文件。但我仍然无法理解所有这些常量的来源。我以预先计算的形式看到它们，但是用于生成它们的实际算法的描述在哪里？

例如，考虑以下来源：

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 版本吗？

4

2 回答 2

2

请记住，移位运算符在 Java 和 JavaScript 中是真实的a << b。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));
});

于 2017-06-03T09:09:11.600 回答
2

原因LFSR是byte[]在Java 版本中是允许LFSR86540修改它。您可以使函数返回新值：

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

于 2017-05-26T16:57:29.050 回答