密碼學的骰子——隨機數

2020-12-17 聊聊密碼學

做開發的工程師們應該或多或少都接觸過隨機數,可能認為它就是一個隨機生成的數字嘛,使用時也很簡單,只要調用開發語言提供的函數即可。但實際上隨機數後面還是有著比較複雜但也有趣的知識點的。

根據一般定義,隨機數應該具有以下三個性質:隨機性,不存在統計學偏差,是完全雜亂的數列,即分布均勻性和獨立性;不可預測性,不能從過去的隨機數數列推測出下一個出現的數;不可重現性,不能重現相同的數列。

我們在平時編程開發裡用到的隨機數,一般都只滿足第一個條件,這種只滿足隨機性分布的隨機數,就叫做偽隨機數或弱偽隨機數。這是因為程式語言提供的隨機數生成方法(學名叫偽隨機數生成器)是靠軟體算法實現的,既然是算法,那就必定遵循了一定的規律,也就有被預測的可能。像常用到的C語言的rand庫和Java的java.util.Random類,就是採用了線性同餘算法生成隨機數。雖然名字好像不好聽,但偽隨機數已經滿足大多數應用場景的需求了。

但對於密碼學來講,偽隨機數就遠遠不夠了。除了隨機性,密碼學要求的隨機數還要具備不可預測性。我們把具有這兩個性質的隨機數叫做密碼學安全的偽隨機數或強偽隨機數。在密碼學中隨機數的用途很廣,主要有以下幾個方面:

生成密鑰:無論是對稱密鑰還是公私鑰對,生成過程中都有隨機因子參與其中,以增加密鑰被破解的難度;生成Nonce:Nonce是Number used once或Number once的縮寫,意思是只用一次的數字。通過在數據裡加入Nonce,哪怕是對同樣的明文加密或籤名,都可以保證每一次的加密或籤名結果都不相同,以防止重放攻擊,這一點對於身份驗證系統尤其有意義。所謂重放攻擊就是指攻擊者截獲了你提交的驗證信息,然後將信息原封不動的提交給驗證系統,冒充你進行身份驗證。加鹽:加鹽都是Nonce的拓展應用,基本原理也是在加密時向明文摻入隨機數因子,以增加加密結果的不可預測性。在密碼學裡,有這樣一個基本原則:加密結果儘量不要保留原數據的規律。舉個例子:對稱加密都是採用分組加密模式,也就是將原文數據分成組,對每一組進行加密,最後將得到的多組密文合併起來。下圖中最左邊是原圖,中間就是用對稱分組加密的方式生成的密文。可以看出,雖然作為分組的原圖中每一塊區域的都加密了,但顏色一致的區域加密後的數據也是一樣的,組合成的密文圖像還是帶有原圖的規律,我們依然可以看出原圖的大體內容。針對這個問題,可以在分組數據中加入隨機數,使得即使是同樣的數據,加密後的結果也不一樣。最右邊就是經過上述處理後加密的結果,可以看出加密後圖像已完全沒有任何規律可循了。對稱加解密的初始化向量或非對稱加解密中的Padding都屬於這種加鹽應用。

加一點鹽,味道更好

Blinding:與加鹽的原理類似,只不過是針對密文。話說有一種RSA攻擊方式叫做時序攻擊,基本方法就是攻擊者根據解密所花費的時間確定私鑰,比如這一位私鑰為0時,解密花1ms,私鑰為1時,解密要花10ms,攻擊者通過構造不同密文,統計解密花費的時間,理論上可以推算出私鑰。針對這種攻擊,可以先將密文與隨機數進行合併,再送給私鑰解密,這樣就無法通過時間推算出私鑰了。這種方法叫Blinding。綜上所述,密碼學就是利用了隨機數的隨機性和不可預測性,提高密鑰和加解密過程的複雜性和不可預測性,以增加被攻破的難度。

那麼,密碼學安全的偽隨機數或強偽隨機數如何生成呢?前面分析過了,靠軟體算法生成是不靠譜的。科學已經證明,如果要實現不可預測性的隨機數,需要藉助物理規律、人品或者老天爺,比如擲錢幣、骰子、滑動滑鼠的軌跡、電子元件噪聲、核裂變、量子理論、大氣輻射等等。以它們為隨機源生成的隨機數,是滿足密碼學安全要求的。實際應用中一般是採用基於電子元件的噪聲原理的隨機數發生器晶片。而普通計算機使用的CPU或主板基本是沒有這種隨機數發生器功能的,因此,在密碼學的應用中,隨機數發生器晶片成了USBKey的標配,安全的運算,不能沒有它的參與。你看,又一次回歸到了「私鑰永遠不出KEY」的金科玉律。

所謂「有一利必有一弊」,強隨機數雖然安全,但缺點就是運算速度太慢。我們做過一個實測,在同一臺PC主機和生成程序的情況下,採用USBKey生成1000組,每組128KB的隨機數,共計耗時約12個小時;採用軟體函數庫生成同樣數量的隨機數,只用了不到一分鐘。

最後聊聊真隨機數,真隨機數就是除了隨機性和不可預測性外,還需具有不可重複性,也就是產生的隨機數列,不可能再次出現。但是在給定邊界條件下,是不存在真隨機數的,因為隨機數範圍有邊界,那計算出的隨機數列必然有重複。不過如果邊界條件十分複雜且難以捕捉,我們也可以認為它是真隨機數。很多偽隨機數列從局部看,都展現了完美的隨機性,但如果你把這個隨機數列拉長,就會發現它的分布也是有規律的。而真隨機數,就是把數列拉的無限長,也是沒有任何規律所循。這也就是測試一個隨機數發生器質量時,樣本數據量要足夠大的原因。

其實說到這,不可避免地出現了一個根本問題:世界上到底有沒有真正的隨機數?前面說過,隨機數的產生有賴於物理現象的隨機性,但我們現在認為隨機的物理現象,是不是只是因為人類認識不夠,還沒有發現其真正規律?也就是說,這個世界真的是充滿了不可預知的各種混沌,還是有一隻我們看不見的手在操縱著(愛因斯坦老先生說過:上帝不擲骰子)?幸虧我們討論的是密碼學,不是哲學,這個問題頂多想想就好了。雖然真正的隨機數可能不存在,但是有密碼學能夠用的隨機數就已經很好了。

相關焦點

  • 什麼帳戶隨機數?隨機數的作用是什麼?
    (什麼帳戶隨機數?隨機數的作用是什麼?| 金色百科)  那麼隨機數在比特幣區塊鏈中的作用是什麼呢?  在比特幣區塊鏈中,所有參與節點都在遍歷尋找一個隨機數,節點算力輸出越大就越有可能遍歷到這個隨機數,也就能夠搶到這一輪的記帳權,這個過程通常被稱為「挖礦」。各參與節點在遍歷隨機數的過程中也在不斷地驗證其他節點的交易信息,搶到記帳權的節點會把所有相關的信息廣播出來,全網中所有參與節點在共同驗證了廣播出來的信息之後就會形成一個區塊,緊接在上一個區塊的後面,形成一條區塊數據鏈。
  • 玩轉Python 中的隨機數
    開發中我們經常遇到需要隨機數的場景,比如為了用戶密碼更安全我們有時會加鹽,也就是將用戶原密碼連接上一串隨機字符然後加密保存,又比如我們可能需要隨機展示某張圖片等等。今天,我們就來理一理 Python 中的隨機數的玩法,當然,這裡只涉及標準庫。
  • 密碼學基礎——偽隨機數生成器
    區塊鏈是對密碼學的一次整合運用,理解了密碼學,才能真正理解區塊鏈。獵豹區塊鏈中心在密碼學起源的科普文章中,給大家介紹了經典的加密方法,從凱撒密碼到多表密碼,以及一次一密,在本篇文章中,我們將會和大家分享最早實現一次一密的加密機以及偽隨機數生成器。
  • python安全開發軍規之四:使用安全的隨機數生成器
    背景日常開發中,必然會碰到需要生成隨機數的需求,比如生成圖片驗證碼,簡訊驗證碼……隨機數生成既然是這麼簡單的一個功能,開發必然也很簡單,我們看看怎麼生成一個隨機數,這裡以隨機生成1-100的整數為例。普通程式設計師的寫法import randomrandom.randint(1,100)只用了兩行代碼,程式設計師小Z就寫出了一個隨機數。QA有話說隨機模塊提供的隨機生成器是偽隨機數生成器。所謂偽隨機數,是通過固定的算法生成的,其結果是確定的,可預見的。
  • 女孩用骰子生成安全密碼:一個賣2美刀
    你知道有黑客在以每秒數億次的頻率攻破你的隱私防線嗎?你想過除了生日日期、電話號碼、身份證後六位以外,設置密碼還能有什麼更安全的模式get嗎?這些疑問絕非杞人憂天。網際網路時代下,我們的隱私既被密碼牢牢地鎖在籠子裡,又像是嗷嗷待哺的羔羊隨時被宰。密碼在設定的一瞬間,成了危險與安全的一體兩面。可見,安全已經成為網際網路時代下我們不得不時刻面對的問題。
  • Excel生成隨機數的技巧,隨機數發生器,你用過嗎
    Excel獲取隨機數從概率分布中產生隨機樣本,其基本原理是隨機數的概念。隨機數是均勻分布在0和1之間的數。從技術上講,電腦不能產生真正的隨機數,因為它們必須使用一個可預測的算法。但是,設計用於產生一個數列的算法,似乎是隨機的。在 Excel中,我們可以使用函數RAND()在任何一個單元格之中產生隨機數。
  • 雙線性對在密碼學中的應用(上)
    導 讀如果關心近年的密碼學成果,可以發現雙線性對作為一個基礎的密碼學工具頻頻出現。雙線性對是一種二元映射,它作為密碼學算法的構造工具,在各區塊鏈平臺中廣泛應用,比如零知識證明、聚合籤名等技術方案大多基於雙線性對構造得來。
  • 分享兩種產生隨機數的常用方法
    ,最直接的感受就是讓顯示的數據產生跳動,從而讓用戶感覺真實可靠,同樣在密碼學中隨機數也是非常重要等等,這裡今天小哥就介紹兩種產生隨機數的辦法。「rand()」函數是系統庫文件提供的產生隨機數的函數,它從一個隨機數的序列中按著順序返回一個從0到最大隨機數 RAND_MAX的任意整數,當然最大隨機數的大小通常是固定的一個整數,所以每次程序運行從調用開始的序列都是一樣的 , 這樣也是為了便於程式設計師調試相應的程序。
  • 區塊鏈中隨機數的實現
    當我們談論計算機系統中的隨機性時,我們真正指的是偽隨機性,即儘可能模擬出現實世界應有的隨機性,使之近乎於「真正的隨機性」。以密碼學安全偽隨機數生成器為例,這是一個非常強大的隨機性模擬。隨機數在隱私技術和密碼學中發揮著重要作用。令人驚豔的是,通過生成一個隨機數來對一條消息進行運算(XOR),提供了一種簡單但十分強大的加密方案。
  • 隨機數本質,C語言的隨機數與隨機種子
    引言在實際編程中,我們經常會用到隨機數這個概念,其實也是一個偽隨機數,實際上並不是一個真正的隨機數,但是也足夠我們使用了。在C語言中,編寫一些關於遊戲之類的程序時就需要用到隨機數了。同時C語言也提供了一個標準庫裡面一個函數來產生隨機數,而對於隨機數的產生是根據種子(根據一個數值按照某種公式計算的)來變化的,種子 與隨機數之間符合正態分布(高斯分布)。
  • 逆水寒骰子奇遇怎麼觸發 逆水寒骰子奇遇完成攻略
    逆水寒骰子奇遇,使用骰子可以直接加幸運屬性,那麼逆水寒骰子奇遇怎麼觸發?下面小編為大家帶來逆水寒骰子奇遇完成攻略,一起來看看吧!逆水寒骰子奇遇NPC:追命逆水寒骰子奇遇觸發攻略:與追命好感度隨機觸發,然後會觸發一個任務。先死要喝酒喝過他,然後再搖骰子搖過他,才給這個骰子,另外還有一瓶可以解除所有控制的酒。
  • 在Python中生成隨機數據(指南)
    你猜得沒錯,「真」隨機數可以通過真隨機數生成器(true random number generator,TRNG)產生。舉例來說就是,從地板上反覆撿起一個骰子,扔到空中,然後讓它自己落到地上。假設你的拋擲是無偏的,你真的不知道骰子會落在哪個數字上。扔骰子是一種使用硬體生成非確定性數字的簡單形式。(或者,你可以讓dice-o-matic幫你做這件事。)
  • 骰子與檢定——告訴你什麼叫「1d10」
    在DDO的世界中,幾乎所有動作都存在著一定的隨機性,玩家對任何敵人都不會擁有一個100%的命中率,每一次攻擊也不會有一個固定的傷害值,一切都是由不同面數骰子組合起來模擬的隨機數。
  • 隨機變量是什麼?
    結論:隨機變量是函數;該函數能用來定義另一個函數。起源:在概率空間中,我們有樣本空間,事件空間和概率空間。我們現在關注樣本空間。樣本空間指的是隨機試驗所有可能的結果。我們知道,進行一次隨機試驗,其試驗結果是隨機出現的,所以有了概率這一概念。
  • 手機qq怎麼投骰子 qq在哪使用搖骰子介紹
    qq大家都在使用,最近有不少小夥伴們關心手機QQ怎麼投骰子,想要知道方法的小夥伴們,就讓小編給大家詳細的講講手機qq搖骰子方法。  手機qq怎麼投骰子教程  打開qq,然後在表情界面,點擊左下角的加號qq怎麼投骰子
  • 「你點我查」 長沙市質監局丟骰子隨機抽檢紙尿褲
    「你點我查」 長沙市質監局丟骰子隨機抽檢紙尿褲 2016-09-20 11:15 來源:星辰在線   星辰在線9月20日訊(長沙晚報記者 周輝霞)產品質量抽檢是怎樣進行的?
  • 用骰子DIY真隨機助記詞|火星號精選
    操作手冊徹底踐行了「not your keys, not your bitcoin」的理念,介紹了如何在儘可能不信任任一第三方的情況下,生成你自己的隨機數,助記詞,私鑰,公鑰,助記詞;進而如何進行轉幣等操作。
  • 逆水寒骰子奇遇在哪接?骰子奇遇觸發條件及流程攻略詳解
    逆水寒骰子奇遇在哪接?怎麼觸發?這個是目前遊戲中上線的奇遇任務,很多小夥伴們應該想知道在哪觸發吧?npc是哪個?具體怎麼做?下面是小編帶來的攻略解析,一起來關注下哦! 逆水寒骰子奇遇NPC: 追命 逆水寒骰子奇遇觸發攻略: 與追命好感度隨機觸發,然後會觸發一個任務。
  • 十大骰子驅動桌遊——《骸骨險境》
    作為一款美式遊戲,他完全沒有使用模型這個喜聞樂見的存在,遊戲的主角只有骰子和籌碼。但是這款遊戲的配件質量卻在另一個層面上令人感到震驚。遊戲的幾乎所有配件都沒有使用紙板,所有的卡牌都是塑料質地的,戰鬥場地和玩家版圖則是由氯丁橡膠製成,並有鏤空空間用於放置玩家的骰子。這樣的配件質量,確實對得其遊戲較為昂貴的價格。
  • 韋小寶擲的骰子:被嚴重低估的神仙教具
    本文轉載自【微信公眾號:小土大橙子,ID:buyateng】經微信公眾號授權轉載,如需轉載與原文作者聯繫咱們小時候,很多人家都有麻將,麻將裡就帶著兩個骰子。 現在年輕人打麻將的少了,不過不管是KTV還是很多桌遊中,都能發現骰子的身影。隨機性,意味著帶來趣味性。