密碼學基礎——偽隨機數生成器

買賣虛擬貨幣
如果想要深入瞭解區塊鏈和區塊鏈專案,不可避免的需要了解密碼學。區塊鏈是對密碼學的一次整合運用,理解了密碼學,才能真正理解區塊鏈。我們在密碼學起源的科普文章中,給大家介紹了經典的加密方法,從凱撒密碼到多表密碼,以及一次一密,在本篇文章中,我們將會和大家分享最早實現一次一密的加密機以及偽隨機數生成器。Enigma加密機 第二次大戰初期,法西斯的整體戰爭實力其實是遠遠不如同盟國的,但是,德國、日本採取了大量的的突襲戰術,在二戰初期先發制人,取得了一定的戰爭優勢。要想有效的實施突襲戰術,情報是非常關鍵的,那麼如何保證情報的安全性,就是二戰期間加密學的主要目標。在上一篇文章中我們提到,要想保證資訊都絕對安全,就需要用一次一密都方式對資訊進行加密,也就是對每個字母進行隨機位移的加密,理想的情況是,這個機器將每一個輸入的字母,都對其進行隨機位移,然後輸出加密過的字母。

當時最先進的機器,被稱為轉子加密機,它很好的實現了一次一密。而其中的原理其實和我們熟知的里程錶很像。

(低單位的輪子轉動一週,高單位都輪子轉動一格)
我們都很清楚里程錶的機器,它需要很長時間才會重複一週。想象一下,我們把里程計輪子上的數字打亂,當沒嘀嗒向前一次時,都把轉子上的每一個數字相加,來得到了位移數字,然後把我們要加密的字母進行位移加密,這就是轉子加密機的大致原理。

加密者和接受者可以根據下面的方法生成相同的位移序列:首先,他們需要共享相同的機器,然後就初始狀態達成一致。這被定義為機碼設定,然後他們把各自的機器調整到相同的位置,最後,不斷進行相同的操作,來得到相同的序列。

對於三個轉子、每個轉子有26個數字而言,每個序列經過轉子26的三次方次(17576個數字)的轉動的位移序列才會重複。

而每一個轉子的位置,都等同於序列裡的對應位置,最初的機器狀態被稱為機碼設定,而所有的機碼設定的集合,則被稱為機碼空間,如果最初設定機器的方法增加了的話,機碼空間也就增加了。

當我們選擇一個機碼設定,我們就選擇了這個空間裡的一個起始點,如果把機碼設定給暴露了,就洩露了整個加密序列。

所以,這種轉子加密機的安全性取決於機碼空間的大小,與機碼設定的隨機性這兩方面。

在第二次世界大戰期間,德國納粹使用的最重要的加密技術之一,就是被稱為Enigma(迷)的加密機。

在臨近戰爭結束時,Enigma可以被設定成超過150百萬百萬百萬種方式。這讓德國人相信,盟軍獲得了Enigma機,也無法驗證所有可能的機碼設定。

對於使用Enigma進行通訊的雙方,他們需要首先共享每天的機碼設定,這使他們可以將各自的機器調整到同一位置,這個協議在戰爭期間一再改變,但通常都會在分配金鑰表上分發給所有操作者,每一天,操作者都會剪下當日的設定,而這會告訴他們,機器當天需要的配置,例如,使用哪個轉子,以及轉子的順序,然後在使用之後,機碼設定就會被銷燬。

然而,對於操作者而言,仍剩下一個至關重要的步驟,在通訊之前,他們將要選擇,每一個轉子的初始位置,而一些懶惰的操作者,犯下一個很簡單的錯誤,這和我們鎖腳踏車機械鎖犯下的錯誤一樣,我們傾向於把轉子從初始位置移動很少幾下,或者重複使用一個常見的密碼,這破壞了初始轉子位置的均勻分佈,在重複觀測後,使得盟軍可以完全可以反向還原轉子的線路分佈。

這種人為的低階失誤導致了Enigma機的最終破解,間接影響了戰爭的走勢。

我們可以看到,一次一密最大的問題是,我們不得不提前共享這麼長的金鑰。為了解決這個問題,我們需要引入偽隨機數。

偽隨機數生成器

在理解偽隨機數之前,我們先來看看真正的隨機數,我們的物理世界,其實到處都存在著隨機波動,透過測量被稱為噪音的隨機波動,我們可以生成真正的隨機數,測量噪音的過程被稱為取樣,我們可以透過取樣得到某個隨機數字。但是,相對來說,機器其實是確定的,他們的操作是可預測並且可重複的。

在1946年,馮諾依曼參與了軍方的氫彈的設計,應用了一個名為ENIAC的計算機,他打算重複地計算核聚變過程的模擬,然而這需要隨機生成數進行快速存取,並且保證這些數是可重複的,然而,ENIAC的記憶體相當有限,儲存長的隨機序列是不可能的。

於是,馮諾依曼設計了一個演算法,來機械的模仿隨機性,該演算法如下:首先,選擇一個被成為種子的真正隨機數,這個數可以來自於對噪音的測量,如當前時間的毫秒數,這被稱為種子。然後,把這個種子作為輸入,進行一個簡單的計算——將種子乘以它自身,然後輸出這個結果的中間部分,接下來,使用這個輸出,作為下一個種子,並按照需要多次重複這個過程。

這被稱為評分取中法,這是大量偽隨機數發生器其中的一個。那麼,隨機生成的數列和偽隨機生成的數列之間的差別是什麼呢?

核心區別就在於,偽隨機數如果達到一定數量,序列最終一定會重複,當演算法中出現了之前已經使用過的種子數字時,迴圈就開始了,在偽隨機數序列重複之前的長度,被稱為週期,週期嚴格地由最初種子的長度所限制。

例如,如果我們使用一個兩位的種子,那麼演算法在重複迴圈之前,最多能生成100個數,一個3位的種子在重複迴圈之前,可以生成1000個數,而4位種子在重複之前,可以生成10000個數,然而,如果我們使用一個足夠大的種子,在重複之前,序列中的數字將會到擴大到萬億個。

還有一個關鍵區別非常重要,那就是當你偽隨機地生成數字時,將會有一些無法產生的序列。

例如,如果加密者Alice生成一個含有20個位移的真正隨機序列,這將等價於從所有可能的位移序列的堆疊中,隨機選擇一個序列,這個堆疊中包含了26的20次方種可能,這是一個天文數字。

但如果加密者使用一個4位的隨機種子生成一個20位的偽隨機數序列的話,他只能在10000種可能的結果中,做出等概論的選擇,也就是說她只能生成10000種不同的序列。

當我們從隨機位移轉向偽隨機位移時,相當於把金鑰空間縮小成了一個相對較小的種子空間。

偽隨機數概念的提出使得加密者與接收者不需要再事先共享整個隨機位移序列,而只需要共享相對較短的隨機種子,然後再需要時把它擴充套件成相同的看起來很隨機的序列就可以。

但是如果他們始終無法見面來共享這個種子,該怎麼解決呢?這就是現代加密技術最重要的內容,也是區塊鏈中加密的核心,我們將下一篇文章中重點介紹。

(來源:獵豹區塊鏈安全)
更多區塊鏈資訊:www.qukuaiwang.com.cn/news

免責聲明:

  1. 本文版權歸原作者所有,僅代表作者本人觀點,不代表鏈報觀點或立場。
  2. 如發現文章、圖片等侵權行爲,侵權責任將由作者本人承擔。
  3. 鏈報僅提供相關項目信息,不構成任何投資建議

推荐阅读

;