安全性與演算法

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

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

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)。