iT邦幫忙

2021 iThome 鐵人賽

DAY 14
0
自我挑戰組

30天不怕演算法:白話文版系列 第 14

Day 14:安全雜湊演算法(SHA)

  • 分享至 

  • xImage
  •  

上回提到的雜湊函式,除了雜湊表外,還有不少有趣的應用。

其中一種就是安全雜湊演算法(全名Secure Hash Algorithm,縮寫SHA),它是一個加密雜湊函式(cryptographic hash function)家族,裡面包含SHA-0, SHA-1, SHA-2, SHA-3等雜湊函式。

上一回的雜湊函式將輸入轉化為一個相對較短的數字,用來作為儲存的索引位址,而SHA家族演算法則是將輸入轉為很長的字串,以達到加密或其他用途。SHA函式(還有所有理想的加密雜湊函式)有這些特性:

  • 低衝突:不同輸入得到相同輸出的機率極低。
  • 單方向:SHA函式會輸出字串,但我們很難以這些輸出的字串回推原本的輸入。
  • 良好雪崩效應:就算輸入只有極微小的改變(例如'cat' 變成 'car'),輸出值也會有巨大差異。

不難想像這些特性運用在加密技術中的效果,如果密碼以SHA函式加密,攻擊者很難透過操作或比較雜湊值,來得到原密碼。除了用在加密外,這樣的技術還可以用在比較大量的資料或檔案。

局部敏感雜湊演算法(locality-sensitive hashing (LSH) algorithms)

通常在設計雜湊函式或尤其是加密雜湊函式時,我們希望雜湊衝突越少越好。但局部敏感雜湊演算法則有完全相反的效果。

雖然這個深奧的名稱可能一時看不太懂,但可簡單想成這種雜湊函式的設計是希望增加衝突,讓相似的輸入可以有相似的輸出。換句話說,透過比較LSH演算法的結果,我們可以知道兩個輸入有多相近。實際的應用可以在網路爬蟲中偵測重複的內容,或是檢查一個檔案中是否有抄襲等侵犯版權的行為。


上一篇
Day 13:雜湊表(hash table)
下一篇
Day 15:樹(tree)
系列文
30天不怕演算法:白話文版30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言