iT邦幫忙

2021 iThome 鐵人賽

DAY 20
0
自我挑戰組

一個月的演算法挑戰系列 第 20

Day20:安全性和演算法-雜湊函數(hash function)

安全性與演算法

在電腦科學的領域裡,每一刻都有數以萬計的資料在進行傳輸,在傳輸的過程中,是真的安全嗎?相信每個人都有遇過詐騙電話,或是資料外洩,是怎麼樣的過程造成資料不安全?今天開始來討論安全性演算法的必要性。

「傳送」資料的這個動作,本身就有許多漏洞,很難防著有心人士的攻擊,也是因為如此,才衍生出各式各樣「保護」資料的方式。我們先來看看,資料在「傳送」的過程中會遇到哪些問題:

  1. 竊聽(eavesdrop)
  2. 電子欺騙(spoofing)
  3. 竄改(falsification)
  4. 抵賴(repudiation)

數據傳輸有許多風險,若要進一步了解數據傳輸的原理,可以參考「OSI模型」。接下來幾天,會針對不同的安全性演算法進行探討。

  1. 雜湊函數(hash function)
  2. 共用金鑰密碼系統(shared-key crypto system)
  3. 公開金鑰密碼系統(public-key cryptosystem)
  4. 混成密碼系統(hybrid cryptosystem)
  5. 迪菲-赫爾曼金鑰交換(Diffie-Hellman key exchange)
  6. 訊息鑑別碼(message authentication code)
  7. 數位簽章(digital signature)
  8. 數位憑證(digital certificate)

雜湊函數(Hash Function)

雜湊可用於密碼加密,使用雜湊函數將資料轉換成位址,接著將資料儲存在該位址上,不需要使用比較進行搜尋,可以很快的時間找到資料。

雜湊函數要能夠減少碰撞(Collision),所謂的碰撞,也就是將不同的資料轉換到相同的位址。如果發生碰撞就要啟動碰撞處理機制,若所有資料經過雜湊函數都沒有發生碰撞,則稱為完美雜湊(Perfect Hashing)。

下列是常見的雜湊函式:

  1. 除法(Division method):此方法不僅可以直接對關鍵字mod,還可以在折疊、平方取中後在mod。
  2. 折疊法(Folding method):折疊法是將關鍵字從左到右分割成位數相等的幾個部分,然後將這幾個部分疊加求和,並按雜湊表表長,取後幾位作為雜湊位址。
  3. 平方取中法(Middle-Square method):適合不知道關鍵字分佈,而位數又不是很大的情況
  4. 數字分析法(Digit Analysis):適合處理關鍵字位數較大的情況,如果事先知道關鍵字的分佈且關鍵字的許多位分佈較均勻。

採用不同雜湊函數時,一些參考因素:

  1. 計算雜湊位址所需的時間
  2. 關鍵字的長度
  3. 雜湊表的大小
  4. 關鍵字的分佈情況
  5. 紀錄搜尋的頻率
class Hashtable:
    def __init__(self, size):
        self.data = [None for i in range(size)]
        self.M = size

    def hash(self, key):
        return key % self.M

    def insert(self, key):
        address = self.hash(key)
        if self.data[address] == None:
            self.data[address] = key
        else:
            while self.data[address] != None:
                address = (address + 1) % self.M
            self.data[address] = key
    
    def isExist(self, key):
        address = self.hash(key)
        start = address
        if self.data[address] == key:
            return True
        else:
            while self.data[address] != key:
                address = (address + 1) % self.M
                if address == start or self.data[address] == None:
                    return False
            return True

    def search(self, key):
        address = self.hash(key)
        if self.isExist(key):
            while self.data[address] != key:
                address = (address + 1) % self.M
            return address
        else:
            return None

    def v(self):
        print(self.data)

h = Hashtable(8)
n = int(input())
for i in range(n):
    h.insert(int(input()))
    h.v()
print(h.search(1))    
print(h.search(2))

參考資料:資料結構:使用Python


碰撞處理

兩個不同資料經過雜湊函式轉換到相同位址,稱作碰撞(Collision)。


上一篇
Day19:鏈接串列(Linked List)
下一篇
Day21:安全性和演算法-共用金鑰密碼系統(shared-key crypto system)
系列文
一個月的演算法挑戰30

尚未有邦友留言

立即登入留言