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

Question

I can't seem to obtain the exact algorithm that would generate all the round constants for SHA-3.

The description can be found here:

crypto.stackexchange.com/questions/6444.

These values can be found at 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)
];

or at github.com/emn178/js-sha3/blob/master/src/sha3.js#L24 (in another form):

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

I visited keccak.noekeon.org to read the Keccak reference. I have read all files from the downloadable "Files for the Keccak reference". But I still cannot understand where all those constants come from. I see them in the precomputed form, but where is the description of the actual algorithm that was used to generate them?

For example, consider the following sources:

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

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

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

I tried to convert the seemingly relevant code from the above sources to 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);

but it obviously does not generate anything (all values are set to zeroes).
Can anyone provide a readable pseudocode or Javascript version of how those constants were generated?

Answer 1

Remember that the shift operator a << b means a << (b & 31) for real in Java and JavaScript. Thus the original .leftShift is flawed. I took @Ryan-s code and fixed it:

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

Answer 2

The reason LFSR is a byte[] in the Java version is to allow LFSR86540 to modify it. You can make the function return the new value instead:

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

and modify keccakInitializeRoundConstants accordingly:

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

and fix l_left:

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

and fix the mistake from LFSR86540 to read the least significant bit before updating:

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

Voilà: matching constants.

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