雪崩效應

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

密碼學中,雪崩效應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可免費查閱. 

參見[編輯]