安全性与演算法

在电脑科学的领域里，每一刻都有数以万计的资料在进行传输，在传输的过程中，是真的安全吗？相信每个人都有遇过诈骗电话，或是资料外泄，是怎麽样的过程造成资料不安全？今天开始来讨论安全性演算法的必要性。

「传送」资料的这个动作，本身就有许多漏洞，很难防着有心人士的攻击，也是因为如此，才衍生出各式各样「保护」资料的方式。我们先来看看，资料在「传送」的过程中会遇到哪些问题：

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