雪崩效应

(重定向自雪崩效应 (密码学)

密码学中,雪崩效应avalanche effect)指加密算法(尤其是块密码加密散列函数)的一种理想属性。雪崩效应是指当输入发生最微小的改变(例如,反转一个二进制位)时,也会导致输出的不可区分性改变(输出中每个二进制位有50%的概率发生反转)。合格块密码中,无论密钥明文的任何细微变化都必须引起密文的不可区分性改变。该术语最早由Horst Feistel使用,[1]尽管其概念最早可以追溯到克劳德·香农提出的扩散(diffusion)

SHA-1散列函数展示了良好的雪崩效应。当一个二进制位发生变化时,散列校验和将随之而截然不同。

若某种块密码或加密散列函数没有显示出一定程度的雪崩特性,那么它被认为具有较差的随机化特性,从而密码分析者得以仅仅从输出推测输入。这可能导致该算法部分乃至全部被破解。因此,从加密算法或加密设备的设计者角度来说,满足雪崩效应乃是必不可缺的圭臬。

构造一个具备良好雪崩效应的密码或散列是至关重要的设计目标之一。这正是绝大多数块密码采用了乘积密码的原因,也是大多数散列函数使用大数据块的原因。这些特性均使得微小的变化得以通过算法的迭代迅速增殖,造成输出的每一个二进制位在算法终止前均受到输入的每一个二进制位的影响。

严格雪崩准则

严格雪崩准则Strict Avalanche CriterionSAC)是雪崩效应的形式化。它指出,当任何一个输入位被反转时,输出中的每一位均有50%的概率发生变化。严格雪崩准则建立于密码学的完全性概念上,由Webster和Tavares在1985年提出。[2]

高阶的一般化严格雪崩准则涉及到多个输入位。满足高阶严格雪崩准则的布尔函数总是Bent函数,也被称作最大非线性度函数,或“完全非线性”函数。[3]

位独立准则

位独立准则Bit Independence CriterionBIC)指出,对于任意输入位i和输出位jk,当输入位i被反转时,输出位jk应当互不影响地独立变化。

参考文献

  1. ^ Feistel, Horst. Cryptography and Computer Privacy. Scientific American. 1973, 228 (5) [2014-01-27]. (原始内容存档于2019-06-06). 
  2. ^ Webster, A. F.; Tavares, Stafford E. On the design of S-boxes. Advances in Cryptology - Crypto '85. Lecture Notes in Computer Science 218. New York, NY,: Springer-Verlag New York, Inc. 1985: 523–534. ISBN 0-387-16463-4. 
  3. ^ C. Adams; S. Tavares. The Use of Bent Sequences to Achieve Higher-Order Strict Avalanche Criterion in S-Box Design. Technical Report TR 90-013. Queen's University. January 1990. CiteSeerX: 10.1.1.41.8374 . 

参见