Day 14：安全杂凑演算法(SHA)

上回提到的杂凑函式，除了杂凑表外，还有不少有趣的应用。

其中一种就是安全杂凑演算法(全名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演算法的结果，我们可以知道两个输入有多相近。实际的应用可以在网路爬虫中侦测重复的内容，或是检查一个档案中是否有抄袭等侵犯版权的行为。