隨機性可以節省:短種子能令每對雜湊值具有所需聯合分佈,即使整組值並非相互獨立。運用方差界或分析碰撞時,這個區別很重要。我們使用質數域,因為每個非零元素都有乘法逆元。
兩個隨機係數
固定質數 q,記 Fq=Z/qZ。種子是獨立均勻地從 Fq 選出的一對 (a,b),它選定的雜湊函數為
ha,b(x)=ax+b(modq),x∈Fq.這個族有 q2 個等可能的成員,且包括 a=0 的情況。
下文的輸入 x,y 在隨機選種子之前固定。對固定 x 及任意 u,恰有 q 個 (a,b) 滿足 ax+b=u(每個 a 對應一個 b),所以 h(x) 均勻分佈。更強的陳述同時涉及兩個鍵。
設 x=y 為 Fq 中固定的元素。對每個 u,v∈Fq,
P(h(x)=u, h(y)=v)=q21.因此 h(x) 與 h(y) 相互獨立,並各自在 Fq 上均勻分佈。
方程 ax+b=u 及 ay+b=v 蘊含 a(x−y)=u−v。由於域中 x−y=0,它有逆元,所以 a=(u−v)(x−y)−1 被唯一確定,然後 b=u−ax 也被唯一確定;反過來,這對 (a,b) 滿足兩條方程。因此 q2 個等可能種子中恰有一個產生值對 (u,v),概率為 1/q2。對 v 求和得每個值的概率為 1/q,聯合概率正是乘積 q1⋅q1。
證明透視
解出種子
唯一不尋常的一步,是把「哪些種子給出這兩個值?」看成以 (a,b) 為未知數的線性方程組,而不是以 (x,y) 為未知數。真正起作用的假設只有域中的 x=y:它令係數 x−y 可逆,這正是 q 必須是質數、鍵必須是不同的域元素的原因。種子分佈必須保留 a=0:它把兩個鍵都送到 b,排除它便會改變聯合分佈,下面的常見錯誤會說明這點。論證只數種子的個數,從未用到 u,v 的具體值,所以一次涵蓋全部 q2 個值對。
將 q 個 u=v 的情況相加,得到 P(h(x)=h(y))=1/q。此結論假設輸入是不同的域元素:餘數相同的兩個整數不是此雜湊的不同輸入。它也假設輸入與種子獨立地預先固定;先看種子再選輸入的對手屬於不同模型。
三個鍵與容易誤用的推論
令 q=7,固定鍵 0,1,2。若 (a,b)=(1,2),三個值為 (2,3,4);若 (a,b)=(0,4),則為 (4,4,4)。一般而言,若 a=0,乘以 a 是單射,所以三個不同的鍵都不碰撞;若 a=0,三個全部碰撞。由於 a 均勻分佈,
P(至少一次碰撞)=71,E[碰撞對數]=73.
期望也可由三個兩兩碰撞概率及線性性得到。聯集界給出 P(某次碰撞)≤3/7,有效但在此偏鬆。對 m 個固定且不同的域元素,同樣的聯集界論證至多給出 (2m)/q(任何概率當然至多為一)。對這個特定的仿射族,當 m≥2 時,至少一次碰撞的精確概率是 1/q:要麼所有鍵碰撞,要麼全不碰撞。這個結論不應假定適用於任意兩兩獨立族。
反例模式
雜湊值兩兩獨立,碰撞事件卻相依
對這三個固定鍵,每一對雜湊值相互獨立。但事件 h(0)=h(1) 與 h(1)=h(2) 恰好都等於事件 a=0,它們的聯合概率是 1/7,不是 1/49;把兩個概率相乘是無效的。此外在 F7 中 h(2)=2h(1)−h(0),所以三個雜湊值並非相互獨立。
例題
令 q=5,鍵 x=1、y=3,目標值 u=0、v=3。則 a=(u−v)(x−y)−1;在模 5 下,u−v=−3≡2,x−y=−2≡3,而 3−1=2,因為 3⋅2=6≡1。所以 a=2⋅2=4,b=u−ax=0−4=−4≡1。核對:h(1)=4⋅1+1=5≡0,h(3)=4⋅3+1=13≡3。兩個目標都達到,而計算顯示沒有其他種子可以做到。
例題 1.4.4
(F7 上三個鍵的碰撞數)
取 F7 中的鍵 0,1,2。種子 (a,b)=(3,5) 給出值 5,1,4,沒有碰撞;種子 (0,4) 給出 4,4,4,有三對碰撞。只有 a=0(49 個種子中的七個)會產生碰撞,所以 E[碰撞對數]=71⋅3+76⋅0=73,與三對各為 1/7 一致。
令 q=7,用整數 2 和 9 作為鍵。由於 9≡2(mod7),它們是同一個域元素,對每個種子都有 h(2)=h(9),碰撞概率是 1 而非 1/7。定理不適用,因為在 F7 中 x=y 不成立。把 9 換成不同的餘數 3,碰撞概率便回復為 1/7。
常見錯誤
(為避免平凡雜湊而剔除 a=0)
函數 h0,b 是常數,看起來像可以丟棄的退化情況。若把 a 限制為非零,則對 x=y,h(x) 與 h(y) 永遠不相等,於是 P(h(x)=h(y))=0=1/q,兩個值的聯合分佈也不再在 Fq2 上均勻。兩兩獨立性需要完整的種子空間。
定理針對 Fq 中不同的元素。相差 q 的倍數的鍵以概率 1 碰撞。應先把鍵化為模 q 的餘數,或使用大於最大鍵的質數。
種子帶來甚麼
由兩個域元素索引的函數共有 q2 個且等可能;儲存種子需要兩個域元素。固定 q 時,直接求值每個鍵使用一次域乘法和一次加法;精確的位元成本取決於表示方式及算術實現。兩兩獨立性足以支持某些方差計算,但不能證成任意事件概率的乘積,也不能滿足指數尾界論證所需的完全獨立假設。若鍵是任意長的字串,還需要額外的編碼或雜湊構造,以及它自己的碰撞分析。
習題
快速檢查
(設 q=7、a=3、b=5,計算 h(2)。)
解答 · 答案
h(2)=3⋅2+5=11≡4(mod7)。
快速檢查
(對不同的固定 x,y,P(h(x)=h(y)) 是多少?)
把 P(h(x)=u,h(y)=u) 對 u 求和。
解答 · 答案
u 的 q 個取值各貢獻 1/q2,總和為 q/q2=1/q。
快速檢查
(對三個不同的固定域元素鍵,計算碰撞對數的期望。)
解答 · 答案
共有三對,各以概率 1/q 碰撞,所以期望為 3/q。線性性不需要碰撞事件之間獨立,而這些事件其實是相依的。
快速檢查
(若 x 與 y 是相差 q 的整數,能套用「不同域元素」的結論嗎?)
解答 · 答案
不能。它們的餘數相同,是同一個域元素,在此映射下必然得到相同的雜湊值:碰撞概率是 1,不是 1/q。