海绵函数
在密码学，海绵函数（sponge function）或者海绵建构（sponge construction）是一种演算法。它使用有限的状态，接收任何长度的输入位元流，然后可以满足任何长度的输出。海绵函数可以在理论上面或者实做上面应用，用来架构或者实做密码学的原始函数，像是加密杂凑函式（cryptographic hash，参考杂凑函数）等等。
结构
[编辑]海绵函数是由三个部份组成：[1]
- 一个内存状态，包含个位元
- 一个能置换或者转换内存状态，固定大小的转换函式
- 一个填充函式（padding function）
内存状态会分成两个区块，（大小为位元）与（大小为位元）。这里的参数又叫做转换率（bitrate），而叫做容量（capacity）。
填充函式会在输入里面增加足够的长度，让输入的位元流长度变成的整数倍。因此填充过后的输入可以被切成长度为的数个分段。
然后，海绵函数运作如下：
- 先初始化为零
- 输入经过填充函式处理
- 填充后输入的前面个位元会与R进行XOR运算
- 经过函式转换成
- 如果填充后输入还有剩馀，下一位元的分段与进行XOR运算
- S转换成
- …
这过程一直重复到所有的输入都用完为止（在海棉的譬喻里面，被函数“吸收”了）。
现在海绵函数可以依照如下的过程输出（“挤出”内容）：
- 此时里面的资料是输出的前面个位元
- 如果需要更多输出，先把转换成
- 此时R里面的资料是输出的下面个位元
- …
这过程会重复到满足输出所需要的长度为止。
这里值得注意的地方是，输入绝对不会与这部份的记忆体作XOR运算，而且这一部份记忆体也不会直接被输出。这一部份的记忆体仅仅只和转换函式相关。在杂凑里面，防止撞击攻击（Collision attack）或者原像攻击（preimage attack）是依靠这段记忆体作到的。一般实做上的大小会是所希望防止等级的两倍。
应用
[编辑]海绵函数可以在理论上面或者实做上面应用。在密码分析理论上，随机海绵函数（random sponge function）是一个转换函式f为随机置换的海绵函数。随机海绵函数比起经常使用的随机预言（有关预言的部份请参考预言机）满足更多加密基元（cryptographic primitives）的限制，像是有限大小的内存状态。[2]
海绵函数也可以用来建造实际的加密基元。例如，Keccak杂凑函数就是以海绵函数的方式建立的。Keccak杂凑函数使用1600位元大的版本被国家标准技术研究所（NIST）在SHA-3竞赛之中选为赢家。Keccak演算法的特点在于作者所开发复杂、多次的置换函数。[3]
参考资料
[编辑]- ^ Guido Bertoni; Joan Daemen; Michaël Peeters; Gilles Van Assche. Sponge Functions. Ecrypt Hash Workshop 2007. [2012-10-09]. （原始内容存档于2016-10-23）.
- ^ Guido Bertoni; Joan Daemen; Michaël Peeters; Gilles Van Assche. On the Indifferentiability of the Sponge Construction. EuroCrypt 2008. [2012-10-09]. （原始内容存档于2016-10-23）.
- ^ NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition. NIST. 2012-10-02 [2012-10-04]. （原始内容存档于2012-10-05）.