在正式的Keccak实施概况中,有一节讨论了组织内部Keccak状态的不同方法--即第1.2节,位和字节编号约定--在https://keccak.team/software.html中,您可以找到一个参考软件实现以及一个第三方实现列表。然而,至少有两个第三方C实现引用了一个由24个整数常量组成的数组,该数组显然是在Keccak置换的π步骤中使用的,但它们在规范中没有提到。例如,在David实现的keccak-tiny-unrolled.c文件中,数组定义如下:
static const uint8_t pi[24] = \
{10, 7, 11, 17, 18, 3,
5, 16, 8, 21, 24, 4,
15, 23, 19, 13, 12, 2,
20, 14, 22, 9, 6, 1};在π步骤中,包含内部Keccak状态的所有25条车道中的24条被移动到不同的位置。这是一个简单的“双射”映射,但由David的程序处理车道的顺序并不明显,因为状态数组被平坦为一维,π步骤与“按时间顺序优先”的ρ映射相结合,在这种映射中,每条车道按位旋转的位置是固定的。下文第1.1节所界定的所有轮调抵消(注意指数)如下:

上面提到的文件中对应的rho数组看起来如下(0跳过为幂等,rho和pi数组的大小相同):
static const uint8_t rho[24] = \
{ 1, 3, 6, 10, 15, 21,
28, 36, 45, 55, 2, 14,
27, 41, 56, 8, 25, 43,
62, 18, 39, 61, 20, 44};我不想说一些明目张胆的错误,但现在,考虑到这个数组,对行中的主要方案(从零开始)中的状态线进行编号,并且知道在实际代码中(参见keccakf()函数),它的元素按照在同一个数组中定义的顺序,我们可以得出结论: pi数组的第一个元素只是一维状态数组元素(一个单车道)的索引,应该用rho位置旋转的车道替换。然后,keccakf()函数中的a数组中的车道顺序变成如下(i - lane存储在a中):
0 - 12 7 - 9 14 - 1 21 - 18
1 - 13 8 - 5 15 - 22 22 - 19
2 - 14 9 - 6 16 - 23 23 - 15
3 - 10 10 - 2 17 - 24 24 - 16
4 - 11 11 - 3 18 - 20
5 - 7 12 - 4 19 - 21
6 - 8 13 - 0 20 - 17例如,左转第13车道应取代第2车道,因此a[pi=10] =2。同样,由rho =3位置旋转的第2车道应取代第9车道,因此[pi=7]必须是第9车道。
我想知道这些常量是从哪里来的,为什么国家是这样组织起来的。我已经简要地阅读了链接概述,但是它没有提到π常量的任何显式公式,而且我在其他地方也没有发现任何真正有用的东西。你能帮帮我吗?
发布于 2018-05-12 12:35:19
从我的实现代码中,pi数组的索引计算如下:
For x = 0 To 4
For y = 0 To 4
State[(0 * x) + (1 * y), (2 * x) + (3 * y)] = tempState[x, y]
Next y
Next x来自Keccak规范:
映射$π$是一种以长期扩散为目标提供分散的车道的换位.如果没有它,Keccak-f会表现出低重量的周期性轨迹.对于$π$,我们选择了一个矩阵,该矩阵定义了轴在一个长度为6的循环中的排列。映射$ρ$由用于提供片间色散的车道内的平移组成。没有它,切片之间的扩散将非常缓慢。它在z方向上是平移不变的。
对于rho偏移量计算:
x = 1
y = 0
For t = 0 To KECCAK_LANES - 2
RhoOffsets[(5 * y) + x] = ((t + 1) * (t + 2) / 2) Mod KECCAK_LANELENGTH
newX = ((0 * x) + (1 * y)) Mod 5
newY = ((2 * x) + (3 * y)) Mod 5
x = newX
y = newY
Next t您可能会注意到,x和y的乘法常数与pi相同,实际计算的常数是简单的几何序列模64,或者对于较小的Keccak实例而言,无论车道长度是多少。
凯卡克之所以对rho偏移使用完全不同的顺序,是因为pi和rho都是线性的,只要偏移顺序发生变化,就可以以相反的顺序完成,而这正是它们所做的。因为rho的顺序基本上是π的逆,所以他们切换这个顺序使他们的rho偏移顺序与几何序列相同。
那么,我们如何看待rho偏移顺序和π阶之间的关系呢?在rho值的x,y表中,第0元素(0)位于第0位(0,0),第1元素(1)位于第5位置(1,0),第2元素(3)位于第2位置(0,2),第3元素(6)位于第11位(2,1),最后元素(44)位于第6位(1,1)。
根据这些元素在状态内pi值序列中的位置(x+5y),第0 pi值为0,第5 pi值为10,第2值为7,第11值为11,以此类推,最后值为1,与pi序列表匹配。您可以从rho表中序列元素的x,y位置计算pi值,$π_{x,y}$ = $5*((2x+3y) \mod 5 )+y$
由于pi通过重新定位车道来混合整个状态,并且rho在每个车道内旋转比特,因此它们在硬件上合并为一个单一的门空闲操作。州内车道的最后位置仅为π。
https://crypto.stackexchange.com/questions/59162
复制相似问题