海绵函数

海绵函数是由三个部分组成：^[1]

• 一个内存状态${\displaystyle S}$ ，包含${\displaystyle b}$ 个比特
• 一个能置换或者转换内存状态，固定大小的转换函数${\displaystyle f}$ 
• 一个填充函数（padding function）${\displaystyle P}$ 

内存状态会分成两个区块，${\displaystyle R}$ （大小为${\displaystyle r}$ 比特）与${\displaystyle C}$ （大小为${\displaystyle b-r}$ 比特）。这里的参数${\displaystyle r}$ 又叫做转换率（bitrate），而${\displaystyle c}$ 叫做容量（capacity）。

填充函数会在输入里面增加足够的长度，让输入的比特流长度变成${\displaystyle r}$ 的整数倍。因此填充过后的输入可以被切成长度为${\displaystyle r}$ 的数个分段。

然后，海绵函数运作如下：

• ${\displaystyle S}$ 先初始化为零
• 输入经过填充函数处理
• 填充后输入的前面${\displaystyle r}$ 个比特会与R进行XOR运算
• ${\displaystyle S}$ 经过函数${\displaystyle f}$ 转换成${\displaystyle f(S)}$ 
• 如果填充后输入还有剩余，下一${\displaystyle r}$ 比特的分段与${\displaystyle R}$ 进行XOR运算
• ${\displaystyle }$S转换成${\displaystyle f(S)}$ 
• …

这过程一直重复到所有的输入都用完为止（在海棉的譬喻里面，被函数“吸收”了）。

现在海绵函数可以依照如下的过程输出（“挤出”内容）：

• 此时${\displaystyle R}$ 里面的资料是输出的前面${\displaystyle r}$ 个比特
• 如果需要更多输出，先把${\displaystyle S}$ 转换成${\displaystyle f(S)}$ 
• 此时R里面的资料是输出的下面${\displaystyle r}$ 个比特
• …

这过程会重复到满足输出所需要的长度为止。

这里值得注意的地方是，输入绝对不会与${\displaystyle C}$ 这部分的存储器作XOR运算，而且${\displaystyle C}$ 这一部分存储器也不会直接被输出。${\displaystyle C}$ 这一部分的存储器仅仅只和转换函数${\displaystyle f}$ 相关。在散列里面，防止撞击攻击（Collision attack）或者原像攻击（preimage attack）是依靠${\displaystyle C}$ 这段存储器作到的。一般实做上${\displaystyle C}$ 的大小会是所希望防止等级的两倍。

海绵函数可以在理论上面或者实做上面应用。在密码分析理论上，随机海绵函数（random sponge function）是一个转换函数f为随机置换的海绵函数。随机海绵函数比起经常使用的随机预言（有关预言的部分请参考预言机）满足更多加密基元（cryptographic primitives）的限制，像是有限大小的内存状态。^[2]

海绵函数也可以用来建造实际的加密基元。例如，Keccak散列函数就是以海绵函数的方式创建的。Keccak散列函数使用1600比特大的版本被国家标准技术研究所（NIST）在SHA-3竞赛之中选为赢家。Keccak算法的特点在于作者所开发复杂、多次的置换函数。^[3]