Keccak 算法

1. 什么是Keccak

Keccak是一种被选定为SHA-3标准的单向散列函数算法。

Keccak可以生成任意长度的散列值，但为了配合SHA-2的散列值长度，SHA-3标准中规定了SHA3-224、SHA3-256、SHA3-384、SHA3-512这4种版本。在输入数据的长度上限方面，SHA-1为2的64次方-1比特，SHA-2为2的128次方-1比特，而SHA-3则没有长度限制。

此为，FIPS 202还规定了两个可输出任意长度散列值的函数，分别为SHAKE128和SHAKE256。据说SHAKE这个名字取自Secure Hash Algorithm与Keccak这几个单词。

顺便一提，Keccak的设计者之一Billes Van Assche在Github上发布了一款名为KeccakTools的软件。地址如下：https://github.com/KeccakTeam/KeccakTools

2. 海绵结构

Keccak采用了与SHA-1、SHA-2完全不同的海绵结构，如下图：

Keccak的海绵结构中，输入的数据在进行填充之后，要经过吸收阶段和挤出阶段，最终生成输出的散列值。

“海绵结构”这个名字听上去有点奇怪，可以想象以下将一块海绵泡在水里吸水，然后再将里面的水挤出来的情形。同样地，Keccak的海绵结构是先将输入的消息吸收到内部状态，然后再根据内部状态挤出相应的散列值。

2.1 吸收阶段流程

• 将经过填充的输入消息按照每r比特为一组分割成若干个输入分组
• 首先，将“内部状态的r比特”与“输入分组1”进行XOR，将其结果作为“函数f的输入值”
• 然后，将“函数f的输出值r个比特”与“输入分组2”进行XOR，将其结果再次作为“函数f的输入值”
• 反复执行上述步骤，直到达到最后一个输入分组
• 等所有的输入分组处理完成后，结束吸收阶段，进入挤出阶段

函数f的作用是将输入的数据进行复杂的搅拌操作并输出结果（输入和输出的长度均为b=r+c个比特），其操作对象是长度为b=r+c个比特的内部状态，内部状态的初始值为0.也就是说，通过反复将输入分组的内容搅拌进来，整个消息就会被一点一点地“吸收”到海绵结构的内部状态中，就好像水分被一点点吸进海绵内部一样，每次被吸收的输入分组长度为r个比特，因此r被称为比特率。

通过上图可以看出，函数f的输入长度不是r个比特，而是r+c个比特，这意味着内部状态中有c个比特时不受输入分组内容直接影响的（但会通过函数f受到间接影响）。这里的c被称为容量。

2.2 挤出阶段流程

• 首先，将“函数f的输出值中的r个比特”保存为“输出分组1”，并将整个输出值（r+c个比特）再次输入到函数f中
• 然后，将“函数f的树池值中的r个比特”保存为“输出分组2”，并将整个输出值（r+c个比特）再次输入到函数f中
• 反复执行上面的步骤，直到获得所需长度的输出数据

无论是吸收阶段还是挤出阶段，函数f的逻辑本身是完全一样的，每执行一次函数f，海绵结构的内部状态都会被搅拌一次。

挤出阶段中实际上执行的是“对内部状态进行搅拌并产生输出分组（r比特）”的操作，也就是以比特率（r个比特）为单位，将海绵结构内部状态中的数据一点一点挤出来，就像从海绵里面把水挤出来一样。

在挤出阶段，内部状态r+c个比特中的容量（c个比特）部分是不会直接进入输出分组的，这部分数据值会通过函数f间接影响输出内容。因此，容量c的意义在于防止将输入消息中的一些特征泄露出去。

3. 双工结构

作为海绵结构的变形，Keccak中还提出了一种双工结构，如下图：

在海绵结构中，只有将输入的消息全部吸收完毕之后才能开始输出，但在双工结构中，输入和输出是以相同的速率进行的。在双向通信中，发送和接收同时进行的方式称为全双工，Keccak的双工结构也代表同样的含义。

通过采用双工结构，Keccak不仅可用于计算散列值，还可以覆盖密码学家工具箱中的其他多种用途，如伪随机数生成器、流密码、认证加密、消息认证码等。