Как именно были сгенерированы все круглые константы для SHA-3?
Я не могу получить точный алгоритм, который бы генерировал все константы для SHA-3.
Описание можно найти здесь:
https://crypto.stackexchange.com/questions/6444/why-are-the-constants-so-simple-in-keccak.
Эти значения можно найти по адресу https://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)
];
или на https://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];
Я посетил http://keccak.noekeon.org/, чтобы прочитать ссылку на Keccak. Я прочитал все файлы из загружаемого "Файлы для справки Keccak". Но я до сих пор не могу понять, откуда все эти константы. Я вижу их в предварительно вычисленной форме, но где описание фактического алгоритма, который использовался для их генерации?
Например, рассмотрим следующие источники:
read.pudn.com/.../KeccakPermutationReference.c__.htm;
Я попытался преобразовать, казалось бы, соответствующий код из вышеупомянутых источников в 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 о том, как были сгенерированы эти константы?
2 ответа
Помните, что оператор сдвига a << b средства a << (b & 31) по-настоящему в Java и JavaScript. Таким образом, оригинал .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));
});Причина 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));
});