高效散列方法

2023-05-08 23:33:51 2

專利名稱：高效散列方法
技術領域：
本發明涉及數據操作，更具體地，本發明涉及一種高效的把長的數據串表示成短數據串的技術。
散列是一種把長度較長的數據表示成長度較短的數據的技術。該技術在於，二個不同的長度較長的數據代表一個相同的長度較短的數據的概率相對的小。這種特性被稱為碰撞概率。
Pr(h(m1)＝h(m2))≤ε (1)12l]]>碰撞概率由式(1)表示，該式表明在串x1上執行散列函數「h」的結果和在串x2上執行散列函數「h」的結果相等的概率少於或等於
或ε。
未散列的較長串中包含的位數為「n」，並稱為域(domain)。較短的或散列後的串的位數為l，並通常稱為散列函數的距(range)。滿足式(1)的散列函數通常稱為泛ε的。
Pr(h(m1)-h(m2)＝Δ)≤ε (2)12l]]>另一個和散列函數相關的典型特性由式(2)表示，該式指出散列函數「h」在串x1上的輸出和散列函數在串x2上的輸出之間的差等於某預選量Δ的概率小於或等於
或ε。滿足式(2)的散列函數通常稱為泛εΔ散列函數。Pr(h(m1)=c1,h(m2)=c2)2l---(3)]]>12l]]>某些散列函數還具有由式(3)表示的第三特性。式(3)顯示散列函數「h」對輸入串x1的輸出等於預定的數c1並且散列函數「h」對輸入串x2的輸出等於預定的數c2的聯合概率小於
或ε。滿足式(3)的散列函數被稱為強泛ε的。滿足式(3)的散列函數自動滿足式(1)和(2)。
許多應用中使用散列函數，其中之一是簡化對文本串的搜索。在運用於文本串搜索時，散列函數用於縮短被存儲信息的長度，並且接著把同一散列函數用於縮短搜索準則的長度。然後利用縮短的搜索準則搜索縮短的被存儲信息，以便更有效地定位所需的信息條。一旦定位該條所需的信息後，可提供和縮短的文本關聯的未散列處理的或全長度的文本。
在無線通信中還把散列函數用於消息鑑定。通過和消息一起發送標記對消息鑑定，該標記是通過對消息執行加密函數計算出的。為消息產生一個標記是計算密集的。散列函數用來把消息縮短成標記，從而所需進行的加密處理不那麼計算密集。
h(m)＝(ma)modp(4)h(m,,mk)=(i=lkmii)modp---(5)]]>諸如式(4)表達的線性散列和式(5)表達的MMH散列現在被用於把較長的數據或文本的串表示成較短的串，其中二個不同的長串產生相同的短串的概率是相對小的。這些散列函數需要字數為「w」的一個密鑰和字數為「w」的要被散列的消息或文本進行相乘。結果是，為了對某特定的數據或文本串執行散列需要w2次運算。對於具有許多字的大數據或文本串，這造成計算密集型運算。
本發明提供一種高效散列技術，其用
次運算對「w」個字長的串進行散列，無需現有技術的w2次運算。本發明通過對密鑰和被散列的串的之和進行平方以代替該密鑰和該串的相乘達到這種效果。
h(m)＝((m+a)2modp)mod2l(6)在本發明的一種實施例中，如式(6)所示，通過對消息串「m」和密鑰串「a」相加再形成該和的平方對該消息進行散列。在平方運算的結果上執行模為「p」的運算，並且對該模「p」運算的結果執行模為2l的運算。在該情況下，「m」和「a」的長度相同，即「n」位長或「w」字長。請注意「a」可長於「n」位，但最好是「n」位。值「l」代表散列結果後的縮短串的按位數計的長度，並稱之為「距」。把值「p」選為第一個大於「2n」的質數，其中「n」是消息串「m」的位數。請注意，式(6)提供一種滿足式(1)和(2)的散列方法，即，式(6)的散列方法是泛Δ的。
h(m)＝(((m+a)2+b)modp)mod2l(7)在本發明的第二實施例中，提供一種強泛的散列方法。在該情況下，消息串「m」和密鑰「a」相加，接著平方所產生的和。消息串「m」和密鑰「a」都為「w」字長(各含有「n」個位)。請注意，密鑰「a」可含有多於「n」個的位，但「n」為最佳。平方運算的結果和至少為「n」位長的第二密鑰b相加。如前面參照式(6)討論的那樣，對平方項和密鑰「b」的和進行模為「p」的運算。如參照式(6)說明的那樣，對模「p」運算的結果進行模為2l的運算。採用這種散列方法提供了一種滿足式(1)、(2)和(3)的強泛散列方法。
在本發明的再一個實施例中，對「k」個消息或串進行散列以產生單個較短的串。h(m1,,mk)=((i=1kmi-ai)2)modp)mod2l---(8)]]>式(8)說明把各為「w」字長的「k」個消息散列以形成單個較短的串。每個消息mi和一個密鑰ai相加，並平方產生的和。然後對這「k」個消息相加每個消息mi的平方運算的結果。對總和進行模為「p」的運算。並且對模「p」運算的結果進行模為「2l」的運算。值「p」和「l」和前面的定義相同。式(8)表達的散列方法產生滿足式(1)、(2)的泛Δ散列函數。


圖1是平方散列方法的流程圖；圖2是一種強泛平方散列方法的流程圖；以及圖3是第二種泛Δ平方散列方法的流程圖。
圖1說明一種實現式(6)的平方散列方法的方法。在步驟100輸入輸入串或消息「m」。在步驟102輸入某輸入密鑰「a」。消息或串「m」以及密鑰「a」各為由「w」個字組成的「n」位長。密鑰「a」是一個隨機或偽隨機數，可長於「n」位，但最好為「n」位。在步驟104，產生串「m」和密鑰「a」的和「s」。在步驟106平方和「s」。在步驟108，對步驟106的結果進行模為「p」的運算。「p」是比2n大的下一個質數；然而「p」可以是更大的質數，但它可能降低性能。在步驟110，對步驟108的結果進行模為2l的運算。「l」是輸出的短消息或串的位數。在步驟112輸出模2l運算的結果。圖1的處理造成把「n」位的消息或串縮短成「l」位的消息或串。請注意，如圖1相關的處理執行一種滿足式(1)、(2)的特性的泛εΔ散列函數。
圖2說明一種實現式(7)描述的強泛散列方法的方法。在步驟140，輸入消息或串「m」。在步驟142輸入密鑰「a」和「b」。消息「m」、密鑰「a」及「b」各為具有「w」個字的「n」位長。在步驟144，產生消息「m」和密鑰「a」的和並作為和「s」存儲。在步驟146把和「s」的平方存儲成項「SQ」。在步驟148，產生項「SQ」和密鑰「b」的和。在步驟150，對步驟148產生的結果進行模為「p」的運算。再次，「p」等於下一個大於2n的質數；不過「p」可以是更大的質數但可能降低性能。在步驟152，對步驟150的結果進行模2l運算。「l」等於該方法輸出的串或消息的位數。在步驟154，輸出長度為「l」的短消息或串。請注意，圖2的方法把「n」位的串或消息縮短成「l」位的串和消息。還請注意，圖2的處理是一種滿足式(1)、(2)、(3)的特性的強泛ε散列函數。
圖3說明一種用於執行式(8)所描述的泛εΔ散列方法的方法。在步驟170，把下標「i」置為等於1並把變量SUM置為等於0。在步驟172輸入值「k」。「k」等於要輸入的串數或消息數，以生成單個縮短的消息。在步驟174分開消息或串mi，並在步驟176輸入密鑰ai。請注意，消息或串mi和密鑰ai長度相同，各具有由「w」個字組成的「n」個位。密鑰「ai」是一個隨機或偽隨機數並可比「n」位長，但最好為「n」位。ai最好是一個隨機數。可以從許多源如偽隨機發生器產生隨機數。在步驟178，通過生成消息mi和密鑰ai的和形成和si。在步驟180，把si的平方置成等於變量SQi。在步驟182，把變量SUM置成等於變量SUM加SQi。在步驟184，檢查「i」的值，以判定它是否等於值「k」。若不等於值「k」，執行把下標「i」遞增1的步驟186，並接著執行步驟174。若在步驟184中判定「i」的值等於「k」，執行步驟188，其中對變量SUM的當前值進行模為「p」的運算。如上面所述，值「p」是下一個大於值2n的質數，「p」可是更大的質數但這會降低性能。在步驟190，對步驟188產生的結果進行模2l運算。再次，「l」是組成輸出串或消息的位數。在步驟192，輸出縮短的「l」位的消息或串。請注意，圖3的處理把「k」個各為「n」位的消息縮短成一個「l」位的消息。還請注意，圖3的散列方法是一種滿足式(1)和(2)的特性的泛εΔ散列方法。
在參照圖1、2、3下，請注意典型地根據在所需的長度為「l」的短輸出消息和使式(1)和(2)的概率為最小或在強泛ε散列函數情況下，使式(3)的概率為最小之間的折衷選擇值「l」。
下面提供簡略證明以示出所公開的平方散列函數滿足式(1)、(2)和(3)的特性。理論1式(6)描述的散列函數是泛Δ的。證明對於所有「m」≠「n」εZp和ΔεZpPxr[hx(m)-hx(n)＝Δ] (1)＝Pxr[(m+x)2-(n+x)2＝Δ] (2)＝Pxr[(m2-「n」2+2(m-n)x＝Δ] (3)＝1/p (4)其中因為對於任何給定的「m」≠「n」εZp以及δεZp存在唯一的滿足式m2-「n」2+2(m-n)x＝δ的x，而得到最後一個不等式。理論2式(7)描述的散列函數是散列函數的強泛類證明這是下述引理的直接推論，該引理表示如何把泛Δ類的散列函數轉換成強泛類的散列函數。引理1令「h」＝{hxD→R|xεK}是一個泛Δ類的散列函數，其中R是阿貝爾群，「k」是密鑰集。則，由h』x，b(m)≡(hx(m)+b)(其中加法是在群R中的運算)定義的H』＝{h』x，bD→R|xεK，bεR}是強泛類的散列函數。證明對於所有「m」≠「n」εD以及所有α，βεRPrx,b[hx,b'(m)=,hx,b'(n)=]---(5)]]>=Prx,b[hx(m)+b=,hx(n)+b=]---(6)]]>=Prx,b[hx(m)-hx(n)=-,b=-hx(m)]---(7)]]>=Prx,b[hx(m)-hx(n)=-|b=-hx(m)]Prx,b[b=-hx(m)]---(8)]]>＝1/lR2(9)由於hx是泛Δ散列函數並且hx(m)-hx(n)可按等概率取R中的任何值，而得到最後一個等式。
權利要求
1.一種產生位集合的縮短表示的方法，包括步驟輸入該「n」位的集合；把具有至少「n」位的某密鑰和該位集合相加以得到一個和；平方該和以得到和的平方；對和的平方進行模為「p」的運算以產生模「p」結果，其中「p」至少和第一個大於2n的質數一樣大；對該模「p」結果進行模為2l的運算以產生模2l結果，其中「l」小於「n」；以及輸出該模2l結果。
2.一種產生位集合的縮短表示的方法，包括步驟輸入該「n」位的集合；把具有至少「n」位的第一密鑰和該位集合相加以得到第一和；平方第一和以得到和的平方；把該和的平方和具有至少「n」位的第二密鑰相加以得到第二和；對第二和進行模為「p」的運算以產生模「p」結果，其中「p」至少和第一個大於2n的質數一樣大；對該模「p」結果進行模為2l的運算以產生模2l結果，其中「l」小於「n」；以及輸出該模2l結果。
3.一種產生位集合的縮短表示的方法，包括步驟輸入某「n」位的集合；把具有至少「n」位的某密鑰和該位集合相加以得到一個和；平方該和以得到和的平方；至少重複上述三個步驟一次以產生多個和的平方，每次重複這些步驟時採用某個不同的密鑰；把多個和的平方相加以產生總和；對總和進行模為「p」的運算以產生模「p」結果，其中「p」至少和第一個大於2n的質數一樣大；對該模「p」結果進行模為2l的運算以產生模2l結果，其中「l」小於「n」；以及輸出該模2l結果。
全文摘要
一種高效散列技術利用(W
文檔編號G09C1/00GK1251451SQ9912312
公開日2000年4月26日 申請日期1999年10月19日 優先權日1998年10月20日
發明者薩瓦爾·帕特爾, 祖爾非卡·阿明·蘭姆魯 申請人:朗迅科技公司