查看“︁雪崩效应”︁的源代码

{{TA
|G1=IT
|G2=Math
}}
{{About|[[密碼學]]中的雪崩效應|半導體的雪崩效應|突崩潰}}

在[[密码学]]中，'''雪崩效应'''（'''avalanche effect'''）指加密[[算法]]（尤其是[[块密码]]和[[加密散列函数]]）的一种理想属性。雪崩效应是指当输入发生最微小的改变（例如，反转一个二进制位）时，也会导致输出的不可区分性改变（输出中每个二进制位有50%的概率发生反转）。合格块密码中，无论[[密钥]]或[[明文]]的任何细微变化都必须引起[[密文]]的不可区分性改变。该术语最早由[[Horst Feistel]]使用，<ref name="feistel1973">{{Cite journal|first=Horst|last=Feistel|title=Cryptography and Computer Privacy|journal=[[Scientific American]]|volume=228|issue=5|year=1973|url=http://www.apprendre-en-ligne.net/crypto/bibliotheque/feistel/index.html|access-date=2014-01-27|archive-date=2019-06-06|archive-url=https://web.archive.org/web/20190606231507/http://www.apprendre-en-ligne.net/crypto/bibliotheque/feistel/index.html}}</ref>尽管其概念最早可以追溯到[[克劳德·香农]]提出的[[混淆与扩散|扩散（diffusion）]]。

[[File:Avalanche effect.svg|thumb|300px|right|[[SHA-1]]散列函数展示了良好的雪崩效应。当一个二进制位发生变化时，散列校验和将随之而截然不同。]]

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

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

== 严格雪崩准则 ==
'''严格雪崩准则'''（'''Strict Avalanche Criterion'''，'''SAC'''）是雪崩效应的形式化。它指出，当任何一个输入位被[[取反|反转]]时，输出中的每一位均有50%的概率发生变化。严格雪崩准则建立于密码学的完全性概念上，由Webster和Tavares在1985年提出。<ref name="webster_tavares_1985">{{cite book |first1=A. F.|last1= Webster |first2=Stafford E. |last2=Tavares|chapter=On the design of S-boxes|title=Advances in Cryptology - Crypto '85 |series=Lecture Notes in Computer Science|volume=218|pages= 523–534|year=1985|isbn=0-387-16463-4|publisher=Springer-Verlag New York, Inc. |location= New York, NY,}}</ref>

高阶的一般化严格雪崩准则涉及到多个输入位。满足高阶严格雪崩准则的布尔函数总是[[Bent函数]]，也被称作最大非线性度函数，或“完全非线性”函数。<ref>{{cite report |last1=Adams |first1=C. M. |author-link1=Carlisle Adams |last2=Tavares |first2=S. E. |author-link2=Stafford Tavares |date=January 1990 |title=The Use of Bent Sequences to Achieve Higher-Order Strict Avalanche Criterion in S-box Design |version=Technical Report TR 90-013 |publisher=[[Queen's University at Kingston|Queen's University]] |citeseerx=10.1.1.41.8374}}</ref>

== 位独立准则 ==
'''位独立准则'''（英文：'''Bit Independence Criterion'''，簡稱：'''BIC'''）指出，对于任意输入位 <math>i</math> 和输出位 <math>j</math> 、<math>k</math>，当输入位 <math>i</math> 被反转时，输出位 <math>j</math> 和 <math>k</math> 应当互不影响地独立变化。

== 参考文献 ==
{{Reflist}}

== 参见 ==
* [[混淆与扩散]]

{{-}}
{{分组密码}}
{{密碼學|hash}}

[[Category:密码学]]