今天來算一點有關密碼的數學

我們今天的目標是破解八位數的密碼

每個位數可以有128個字元選擇，因此密碼空間約莫

資料庫中已有 個已雜湊過的用戶密碼
假設這些雜湊值皆不相同，且雜湊位元夠大，無法反向逆推或找到碰撞

Trudy事先儲存 個大家常用的密碼
根據經驗，有四分之一的機率用戶密碼會出現在Trudy的庫存中(找來10000個人看他們的密碼，有大約2500人的密碼出現在Trudy的庫存中)

Trudy今天已駭入資料庫並取得1024個用戶資訊以及其雜湊過的密碼

只有在計算雜湊值需要消耗一單位的成本，進行比較的成本忽略不計

我們以下計算Trudy再不同情境下需要付出的成本

狀況一

Trudy想破解Alice(可能是系統管理員)的密碼；Trudy不使用他的清單

由於不使用他的常見清單，Trudy只能暴力搜尋整個密碼空間

假設想要在母體為n的空間找一個數字，會需要找X次，此X的期望值：

可以發現不管在第幾次該數字被找到的機率是一樣的
因此期望值為n/2

也就是說平均而言得進行 次比較，方能命中Alice的密碼
因此Trudy需付出 的成本

狀況二

Trudy想要破解Alice的密碼；Trudy使用清單

Alice的密碼在Trudy清單中的機率為1/4，因此有1/4的機率，只要在 中尋找即可

理由同上，平均 便可命中

有3/4的機率他得使用暴力解

所花費成本和上面沒有太大區別

狀況三

Trudy 想要破解 任一用戶的密碼；不使用清單

與上面狀況一相同，Trudy至少得進行 次 比較 才能達到命中

不同的是，在計算一個密碼的雜湊值後，他可以跟 個用戶的雜湊值進行比較，也就是單一個密碼猜測可以提供 次比較

因此，他只需付出 成本，便能找到一個密碼與裡面的其中一個用戶命中

狀況四

Trudy 想要破解隨便一個人的密碼；使用清單

我們可以假設資料庫中 一定有人的密碼被收錄於Trudy的清單(不可能的機率太低)

與上面相同，想在此清單空間中找到命中，需進行 次比較
由於每次計算一次雜湊值可以與資料庫裡的所有用戶比較，因此只需花費

因此想要知道任一用戶密碼只是轉瞬間的事

加鹽巴

由於直接儲存密碼雜湊值容易讓Trudy使用狀況四的情形獲取用戶密碼

Trudy甚至可以預先計算他手頭上的清單的雜湊值，如此一來他可以不花成本地直接進行比較

為了預防Trudy進行事先計算，在儲存密碼時，可以額外摻入一個隨機的數字s，稱作鹽巴
新的雜湊值y=h(p, s)，於儲存的時候同時存入(s,y)

各位可以想想

1. 為什麼摻入鹽巴可以預防Trudy提前計算清單
2. 可以重新計算狀況四的情形，看看計算成本有無明顯變化