首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >Keccak圆函数π步骤的实现细节

问Keccak圆函数π步骤的实现细节
EN

Cryptography用户
提问于 2018-05-11 16:20:20
回答 1查看 755关注 0票数 2

在正式的Keccak实施概况中,有一节讨论了组织内部Keccak状态的不同方法--即第1.2节,位和字节编号约定--在https://keccak.team/software.html中,您可以找到一个参考软件实现以及一个第三方实现列表。然而,至少有两个第三方C实现引用了一个由24个整数常量组成的数组,该数组显然是在Keccak置换的π步骤中使用的,但它们在规范中没有提到。例如,在David实现的keccak-tiny-unrolled.c文件中,数组定义如下:

代码语言:javascript
复制
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数组的大小相同):

代码语言:javascript
复制
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中):

代码语言:javascript
复制
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车道。

我想知道这些常量是从哪里来的,为什么国家是这样组织起来的。我已经简要地阅读了链接概述,但是它没有提到π常量的任何显式公式,而且我在其他地方也没有发现任何真正有用的东西。你能帮帮我吗?

EN

回答 1

Cryptography用户

回答已采纳

发布于 2018-05-12 12:35:19

从我的实现代码中,pi数组的索引计算如下:

代码语言:javascript
复制
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偏移量计算:

代码语言:javascript
复制
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在每个车道内旋转比特,因此它们在硬件上合并为一个单一的门空闲操作。州内车道的最后位置仅为π。

票数 3
EN
页面原文内容由Cryptography提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://crypto.stackexchange.com/questions/59162

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档