[科普中国]-海绵函数

海绵函数，在密码学，海绵函数(sponge function)或者海绵建构(sponge construction)是一种算法。它使用有限的状态，接收任何长度的输入位元流，然后可以满足任何长度的输出。海绵函数可以在理论上面或者实做上面应用，用来架构或者实做密码学的原始函数，像是加密杂凑函式(cryptographic hash，参考杂凑函数)等等。

操作海绵功能操作如下：

1、状态S初始化为零

2、填充输入字符串。这意味着使用填充函数P将输入转换为r位块。

3、对于填充输入的每个r位块B：

a.R被R XOR B替换（使用按位异或）

b.S被f（S）取代

这个过程“吸收”（在海绵比喻中）填充输入字符串的所有块。

海绵功能输出可以生成（“挤出”），如下所示：

1、输出状态存储器的R部分。

2、重复直到输出足够的位：

a.S被f（S）取代。

b.输出状态存储器的R部分

如果剩余少于r位要输出，则R将被截断（仅输出R的一部分）。

另一个比喻将状态记忆描述为“熵池”，输入“涌入”池中，转换函数称为“搅动熵池”。

注意，输入位永远不会异或进入状态存储器的C部分，也不会直接输出任何C位。输入改变C的程度完全取决于变换函数f。在哈希应用中，对碰撞或前像攻击的抵抗力取决于C，并且其大小（“容量”c）通常是所需阻力水平的两倍。

结构海绵函数是由三个部份组成：

1.一个内存状态S，包含b个位元

2.一个能置换或者转换内存状态，固定大小的转换函式f

3.一个填充函式(padding function)P

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

填充函式会在输入里面增加足够的长度，让输入的位元流长度变成r的整数倍。因此填充过后的输入可以被切成长度为r的数个分段。

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

1.S先初始化为零

2.输入经过填充函式处理

3.填充后输入的前面r个位元会与R进行XOR运算

4.S经过函式f转换成f(S)

5.如果填充后输入还有剩余，下一r位元的分段与R进行XOR运算

6.S转换成f(S)

…

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

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

1.此时R里面的资料是输出的前面r个位元

2.如果需要更多输出，先把S转换成f(S)

3.此时R里面的资料是输出的下面r个位元

…

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

这里值得注意的地方是，输入绝对不会与C这部份的内存作XOR运算，而且C这一部份内存也不会直接被输出。C这一部份的内存仅仅只和转换函式f相关。在杂凑里面，防止撞击攻击(Collision attack)或者原像攻击(preimage attack)是依靠C这段内存作到的。一般实做上C的大小会是所希望防止等级的两倍。

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

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

本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所