關於哈希(散列)函數你應該知道的東西 | Linux 中國

2021-03-06 Linux中國

無論安全從業人員用計算機做什麼，有一種工具對他們每個人都很有用：加密哈希（散列）(hash)函數。這聽起來很神秘、很專業，甚至可能有點乏味，但是， 在這裡，關於什麼是哈希函數以及它們為什麼對你很重要，我會作出一個簡潔的解釋。

加密哈希函數，比如 SHA-256 或者 MD5，接受一組二進位數據（通常是字節）作為輸入，並且對每個可能的輸入集給出一個希望唯一(hopefully unique)的輸出。對於任意模式的輸入，給定的哈希函數的輸出（「哈希值」）的長度都是一樣的（對於 SHA-256，是 32 字節或者 256 比特，這從名字中就能看出來）。最重要的是：從輸出的哈希值反推回輸入，這從計算的角度是不可行的(implausible)（密碼學家討厭 「不可能(impossible)」 這個詞）。這就是為什麼它們有時候被稱作單向哈希函數(one-way hash function)。

但是哈希函數是用來做什麼的呢？為什麼「唯一」的屬性如此重要？

唯一的輸出

在描述哈希函數的輸出時，「希望唯一(hopefully unique)」這個短語是至關重要的，因為哈希函數就是用來呈現完全唯一的輸出。比如，哈希函數可以用於驗證 你 下載的文件副本的每一個字節是否和 我 下載的文件一樣。你下載一個 Linux 的 ISO 文件或者從 Linux 的倉庫中下載軟體時，你會看到使用這個驗證過程。沒有了唯一性，這個技術就沒用了，至少就通常的目的而言是這樣的。

如果兩個不同的輸入產生了相同的輸出，那麼這樣的哈希過程就稱作「碰撞(collision)」。事實上，MD5 算法已經被棄用，因為雖然可能性微乎其微，但它現在可以用市面上的硬體和軟體系統找到碰撞。

另外一個重要的特性是，消息中的一個微小變化，甚至只是改變一個比特位，都可能會在輸出中產生一個明顯的變化（這就是「雪崩效應(avalanche effect)」）。

驗證二進位數據

哈希函數的典型用途是當有人給你一段二進位數據，確保這些數據是你所期望的。無論是文本、可執行文件、視頻、圖像或者一個完整的資料庫數據，在計算世界中，所有的數據都可以用二進位的形式進行描述，所以至少可以這麼說，哈希是廣泛適用的。直接比較二進位數據是非常緩慢的且計算量巨大，但是哈希函數在設計上非常快。給定兩個大小為幾 M 或者幾 G 的文件，你可以事先生成它們的哈希值，然後在需要的時候再進行比較。

通常，對哈希值進行籤名比對大型數據集本身進行籤名更容易。這個特性太重要了，以至於密碼學中對哈希值最常見的應用就是生成「數字」籤名。

由於生成數據的哈希值很容易，所以通常不需要有兩套數據。假設你想在你的電腦上運行一個可執行文件。但是在你運行之前，你需要檢查這個文件就是你要的文件，沒有被黑客篡改。你可以方便快捷的對文件生成哈希值，只要你有一個這個哈希值的副本，你就可以相當肯定這就是你想要的文件。

下面是一個簡單的例子：

87227baf4e1e78f6499e4905e8640c1f36720ae5f2bd167de325fd0d4ebc791c  /home/bob/bin/fop

如果我知道 fop 這個可執行文件的 SHA-256 校驗和，這是由供應商（這個例子中是 Apache 基金會）提供的：

87227baf4e1e78f6499e4905e8640c1f36720ae5f2bd167de325fd0d4ebc791c

然後我就可以確信，我驅動器上的這個可執行文件和 Apache 基金會網站上發布的文件是一模一樣的。這就是哈希函數難以發生碰撞（或者至少是 很難通過計算得到碰撞）這個性質的重要之處。如果黑客能將真實文件用哈希值相同的文件輕易的進行替換，那麼這個驗證過程就毫無用處。

事實上，這些性質還有更技術性的名稱，我上面所描述的將三個重要的屬性混在了一起。更準確地說，這些技術名稱是：

1. 抗原像性(pre-image resistance)：給定一個哈希值，即使知道用了什麼哈希函數，也很難得到用於創建它的消息。2. 抗次原像性(second pre-image resistance)：給定一個消息，很難找到另一個消息，使得這個消息可以產生相同的哈希值。3. 抗碰撞性(collision resistance)：很難得到任意兩個可以產生相同哈希值的消息。

抗碰撞性 和 抗次原像性 也許聽上去是同樣的性質，但它們具有細微而顯著的不同。抗次原像性 說的是如果 已經 有了一個消息，你也很難得到另一個與之哈希值相匹配的消息。抗碰撞性 使你很難找到兩個可以生成相同哈希值的消息，並且要在哈希函數中實現這一性質則更加困難。

讓我回到黑客試圖替換文件（可以通過哈希值進行校驗）的場景。現在，要在「外面」使用加密哈希算法（除了使用那些在現實世界中由獨角獸公司開發的完全無 Bug 且安全的實現之外），還有一些重要且困難的附加條件需要滿足。認真的讀者可能已經想到了其中一些，特別需要指出的是：

1. 你必須確保自己所擁有的哈希值副本也沒有被篡改。2. 你必須確保執行哈希算法的實體能夠正確執行並報告了結果。3. 你必須確保對比兩個哈希值的實體確實報告了這個對比的正確結果。

確保你能滿足這些條件絕對不是一件容易的事。這就是可信平臺模塊(Trusted Platform Modules)（TPM）成為許多計算系統一部分的原因之一。它們扮演著信任的硬體基礎，可以為驗證重要二進位數據真實性的加密工具提供保證。TPM 對於現實中的系統來說是有用且重要的工具，我也打算將來寫一篇關於 TPM 的文章。

via: https://opensource.com/article/20/7/hash-functions

作者：Mike Bursell 選題：lujun9972 譯者：Yufei-Yan 校對：wxy

本文由 LCTT 原創編譯，Linux中國 榮譽推出

相關焦點

  • 哈希函數和哈希表
    但是，看完今天的文章，你或許就會覺得原來也不過如此啊！其核心就是哈希函數和哈希表的應用！哈希函數哈希函數又稱為散列函數，就是把任意長度的輸入（又叫做預映射， pre-image），通過散列算法，變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小於輸入的空間，不同的輸入可能會散列成相同的輸出，而不可能從散列值來唯一的確定輸入值。
  • 哈希函數
    如果能預先建立表中關鍵字Key與其存儲位置之間的函數，即元素的存儲位置是其關鍵字的函數f(key)的值，那麼查找過程就可以實現。1、構造哈希函數f2、處理衝突問題構造哈希函數的常用方法￣￣￣￣￣￣￣￣￣￣￣￣￣
  • 是哈希不是嘻哈,你真的了解散列嗎?理解Python中可哈希對象概念
    可哈希對象我們看一下對於hash的解釋：把任意長度的輸入通過散列算法變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小於輸入的空間，不同的輸入可能會散列成相同的輸出，所以不可能從散列值來確定唯一的輸入值。
  • 比特幣中的密碼學:哈希函數五大特性和挖礦原理
    比特幣本身是密碼學發展的產物，利用了密碼學中的很重要的「單向散列函數」以及數字籤名兩大技術來構建，今天我們來集中精力講解單向散列函數的5種重要的特性，以及比特幣挖礦相關的技術原理。 下面我們先講哈希函數的特性： 單向散列函數（one-wayhash function），也就是通俗叫的哈希函數。
  • 和你聊聊哈希算法
    和你聊聊哈希算法1.1 引言哈希算法又稱散列函數算法，是一種查找算法，應該說哈希算法是最快的查找算法，沒有之一。對於查找問題，哈希算法一直是首選算法。那麼，為什麼名字起的這麼「嘻哈」的算法會如此強大，本文將為你揭開謎底。
  • 7000字哈希表總結,圖文講解!
    首先我們可以對哈希函數下手，我們可以精心設計哈希函數，讓其儘可能少的產生衝突，所以我們創建哈希函數時應遵循以下規則（1）必須是一致的，假設你輸入辣子雞丁時得到的是在看，那麼每次輸入辣子雞丁時，得到的也必須為在看。如果不是這樣，散列表將毫無用處。
  • 圖文詳解:7000 字哈希表總結
    首先我們可以對哈希函數下手，我們可以精心設計哈希函數，讓其儘可能少的產生衝突，所以我們創建哈希函數時應遵循以下規則（1）必須是一致的，假設你輸入辣子雞丁時得到的是在看，那麼每次輸入辣子雞丁時，得到的也必須為在看。如果不是這樣，散列表將毫無用處。
  • 小學生也能看懂的哈希函數工作原理
    這是一篇哈希函數/散列函數（hash function）的基礎入門，相信點進這篇教程的朋友都是想對哈希函數的基本概念和它的工作原理有基本了解的人。本文的目的是從一般的意義上去解釋它，因此我將省略到論證與具體的實現，而將重點放在高級原則上。
  • 簡單易懂的哈希表總結
    見下圖這裡的 f 就是我們所說的散列函數（哈希）函數。我們利用散列技術將記錄存儲在一塊連續的存儲空間中，這塊連續存儲空間就是我們本文的主人公-散列(哈希)但是大家有沒有考慮到這種情況，那就是將關鍵字映射到同一個槽中的情況，即 f(k4) = f(k3) 時。這種情況我們將其稱之為衝突，k3 和 k4 則被稱之為散列函數 f 的同義詞，如果產生這種情況，則會讓我們查找錯誤。
  • 優化哈希策略
    內置的散列（又稱哈希）函數都是通用的，在大多數使用情況下都能表現很好。但是我們能不能做的更好呢，特別是當你對某個用例產生了很好的想法時？測試一個散列策略在先前的一篇文章中，我研究了一些測試散列策略的方法，其中特別注意了一種「正交位」優化的散列策略，它僅僅只是改變一個位就能確保每個散列結果儘可能的不同。
  • 數據結構 | 哈希表
    本文為數據結構系列第 11 篇，介紹哈希表的實現。哈希表（也叫散列表）是數據結構課程中都會介紹的概念，一般出現在「散列與查找」相關章節。哈希表的核心思想是構造一個散列函數，鍵值作為散列函數輸入，將元素映射到哈希表某一位置存儲。這樣，在進行查找時就可以根據散列函數快速找到元素所在位置。常見散列函數有：直接定址法、平方取中法、除留餘數法、數字分析法等。
  • 哈希(Hash)和哈希樹(Merkletree)
    哈希函數（英語：Hash function）又稱散列函數，是一種從任何一種數據中創建小的數字「指紋」的方法。散列函數把消息或數據壓縮成摘要，使得數據量變小，將數據的格式固定下來。
  • 10分鐘了解一致性哈希算法,全網(小區區域網)(建議收藏)
    很多同學應該都知道什麼是哈希函數，在後端面試和開發中會遇到「一致性哈希」，那麼什麼是一致性哈希呢？名字聽起來很厲害的樣子，其實原理並不複雜，這篇文章帶你徹底搞懂一致性哈希！進入主題前，先來一場緊張刺激的模擬面試吧。
  • 揭秘| 帶你走進哈希表(Hash Table)的世界
    為什麼會有哈希表這種數據結構呢？讓我們用一個通俗的例子來理解：大家一定都查過字典吧，我們知道，《新華字典》是按照讀音排序的，可以理解為一個以讀音為key，按升序排列的資料庫。對於讀音已知的字，可以通過「二分查找法」，很快地查找到要找的字，其時間複雜度為O(log2n)。
  • 揭秘 | 帶你走進哈希表(Hash Table)的世界
    為什麼會有哈希表這種數據結構呢？讓我們用一個通俗的例子來理解：大家一定都查過字典吧，我們知道，《新華字典》是按照讀音排序的，可以理解為一個以讀音為key，按升序排列的資料庫。對於讀音已知的字，可以通過「二分查找法」，很快地查找到要找的字，其時間複雜度為O(log2n)。但是，對於不知道讀音的字怎麼辦呢？
  • Python 中 MD5 哈希函數的實現
    Python中的MD5哈希與md5相關的功能示例1：在Python中列印等效於MD5哈希的字節示例2：在Python中列印MD5哈希的十六進位等效項示例3：Python MD5文件校驗輸出與說明示例4：使用Python在MD5中編碼字符串輸出與說明示例5：在Python中計算文件的MD5哈希
  • 單向散列函數(HASH函數)基本原理
    Hash函數H(m)也名單向散列函數，它是現代密碼學的核心。散列函數一直在計算機科學中使用，散列函數就是把可變的輸入長度串轉換成固定長度輸出值(叫做散列值)的一種函數。
  • 人們常說的哈希(Hash)到底是什麼?
    Hash一般被翻譯成「散列」，也可直接音譯為「哈希」，就是把任意長度的輸入（又叫做預映射， pre-image），通過散列算法，變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小於輸入的空間，不同的輸入可能會散列成相同的輸出，所以不可能從散列值來唯一的確定輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。
  • Python | Leetcode哈希表系列
    哈希表哈希表（散列表）的思想是將關鍵字 Key 映射到存放記錄的散列表中從而進行快速訪問，其中映射函數 f(key) 稱為哈希函數（散列函數），依據哈希函數建立的查找表稱為哈希表。Hash，音譯為哈希，是把任意長度的輸入（又叫做預映射pre-image）通過散列算法變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小於輸入的空間，不同的輸入可能會散列成相同的輸出，所以不可能從散列值來確定唯一的輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。
  • 【圖學院】區塊鏈與密碼學全民課堂第5-1講:哈希函數簡史
    這裡有知識也有故事，從感興趣到有樂趣，全民課堂等你來學。這個系列中的課程內容首先從比特幣著手進行入門介紹，再延伸至區塊鏈的相關技術原理與發展趨勢，然後深入淺出地依次介紹在區塊鏈中應用的各類密碼學技術。歡迎大家訂閱本公眾號，持續進行學習。