雪崩效應係數的計算
給定雜湊函式的嚴格雪崩標準矩陣/依賴矩陣，我如何計算它的雪崩係數。我想計算一個參數（值），它代表給定雜湊函式的雪崩效應量。
我曾想過計算整個矩陣的平均值，但不確定這是正確的做法。
以下論文討論了雪崩係數，但他們沒有提到他們計算它的方式。
我相信你能做到這一點的唯一方法是假設你有固定長度的散列函式輸入 $ f $ . 否則，您想對輸入集施加什麼機率分佈是有問題的 $ {0,1}^{\ast} $ 這是所有有限輸入字元串的集合。實際上，雜湊函式確實對輸入字元串有上限，但就測試所有輸入字元串而言，這是天文數字。
所以，讓我們假設散列函式的安全參數為 $ k $ 位。這對應於函式的作用類似於具有長度輸出的隨機函式 $ n=2k $ 位。
您的測試會從均勻分佈中生成大量隨機值 $ {0,1}^{m}, $ 因此將散列函式視為隨機函式 $ f:{0,1}^m\rightarrow {0,1}^n. $ 讓這組隨機輸入表示為 $ X $ . 現在定義
$$ a_{ij}=#{x \in X:[f(x\oplus e_i)]_j \neq [f(x)]j} $$ 為了 $ 1\leq i\leq n,1\leq j\leq m, $ 在哪裡 $ e_i $ 是向量中的一個 $ i^{th} $ 位置和零無處不在 $ [u]j $ 表示 $ j^{th} $ 向量的分量 $ u $ . $ a{ij} $ 計算來自的輸入數量 $ X $ 不同之處在於 $ j^{th} $ 輸出位時 $ i^{th} $ 輸入位被翻轉。 您現在可以定義一定程度的嚴格雪崩標準 $ D{SAC}(f) $ 作為
$$ D_{SAC}(f):=1-\frac{\sum_{i=1}^n \sum_{j=1}^n \left|\frac{2a_{ij}}{#X}-1\right|}{nm}, $$ 期望 $ D_{SAC}(f) $ 應該約為 1，即絕對差值之和$$ \left|\frac{2a_{ij}}{#X}-1\right| $$超過 $ i $ 和 $ j $ 應該很小。表達這一點的一種方式可能是說 $ E[A_{ij}] \approx (#X/2) $ 如果 $ A_{ij} $ 是一個隨機變數，表示 $ a_{ij} $ 和 $ A_{ij} $ 作為二項式變數分佈 $ Bin(#X,1/2). $ 然後，您可以從這里通過對二項式使用高斯近似，根據卡方變數對整個實驗進行建模。所以採取適當的比例 $ nm $ 變數來自卡方分佈 $ nm-1 $ 自由程度。
我已經為 SHA 512 這樣做了：-
- 生成一個 512 位長的隨機數，稱為 O
- 隨機翻轉一位生成數字F
- 計算 X = SHA(O) xor SHA(F)
- 計算沒有。X 中的設置位
- 係數 Ksac = X /512（注）
- 沖洗並重複一百萬次以獲得 Ksac 的平均值
（注）這應該是整數除法嗎？
這是我將 SHA 512 與 100,000 次測試的 DIY 雜湊函式進行比較得到的結果：-
PS 我認為 Gupta 和 Yadav 自己制定了這個指標，但這是一個很好的指標。
PPS 雖然 Ksac 是一個不錯的選擇，但我對他們的結果感到擔憂。他們的 Ksac(SHA-256) 與預期值相差 8%。我進行了數百萬次執行，因為它只需要幾分鐘。也許他們只做了 100 個。或者也許 SHA-256 沒有表現出完整的雪崩效應，他們真的在做大事。無論哪種方式，我都希望討論 8%，因為這與預期的差異接近 1/10。這篇論文看起來很輕，我懷疑這是一篇碩士論文，而不是研究。
