2016-06-27

確保隨機數真正隨機的演算法

Algorithm ensures that random numbers are truly random
http://phys.org/news/2016-06-algorithm-random.html

By Lisa Zyga
June 24, 2016

(Phys.org) — 產生一個隨機數數列也許比字面上更加困難。雖然數字看起來也許隨機,但你如何確定,它們並沒有遵循某些複雜、潛在的模式?為此,尋找一種方法來證明某個數列是真正的隨機,通常比前面提到的產生隨機數數列更具挑戰性。

在一項新研究中,研究者開發出一種新的演算法,那增加一系列試驗性產生的、看似隨機的數字,通過隨機性驗證的數量。位於波蘭、瑞典與巴西的研究者 Piotr Mironowicz 等人,已將他們的論文發表在最近一期的 New Journal of Physics 期刊上。

如同科學家們的解釋,產生一長串通過驗證的隨機數,對於保障電腦、手機與其他電子裝置的安全至關緊要。

"每種電子裝置都需要隨機性,而且需要很多隨機性," 波蘭 Gdańsk 大學的共同作者 Marcin Pawłowski 表示。"每當你需要安全性時,隨機性就成了必要。每當你想要安全的通訊,就必須產生一個密碼學金鑰。它必須隨機地產生,讓敵手無法輕易猜中。現今每種通訊都是以這種方式加密。每當你用手機打電話、傳簡訊給某人,都必須要產生一串隨機數。如果某人能夠預知這些數字(那不需要完美預測 -- 某人只要能猜中某些數字即已足夠),他們就能夠聆聽你的交談。"

"隨機數不斷地被每一個能夠進行通訊的機器產生。即使沒有通訊產生,每部電腦也都需要隨機性來分配程式在記憶體中的位置。若每次程式被執行,都分配在記憶體中相同的地方時,要駭一部電腦就顯得稀鬆平常。利用隨機數產生器中的後門或惡意功能,是攻擊通訊或電腦系統最常見的方法之一。"


許多數字,沒有模式

雖然要產生並驗證短短的一串隨機數顯得相對容易,不過在密碼學應用中,需要更長的隨機數,而長度正是使這項工作更具挑戰性的原因。

一般來說,研究者使用二種主要方法來產生長隨機數數列。第一種方法是基於物理系統中所固有的隨機性,例如雷射中的光學雜訊與原子中的放射性衰變。這種隨機性可追溯到這些系統的量子特性。第二種方法是使用電腦軟體,那能夠完成複雜的算術程序。技術上來說,只有第一種方法能夠產生真正的隨機數。電腦所產生的隨機數被認為是「偽隨機(pseudorandom)」,因為知道程式開發者如何計算,使得預測這些數字成為可能,那只是看起來隨機。

在這項新研究中,研究者使用第一種方法,透過測量某些物理系統的量子態。然而,這種物理學方法有其自己的問題:你如何能夠確信用來測量此物理系統的測量裝置,不會因為其建構方法,而有某些潛在的可預測性?為了克服此問題,科學家們對於這些裝置發展出嚴格的需求,不過這些「裝置相依(device-independent)」的協定如此嚴格,以至於在產生大量隨機數時非常緩慢。

成為安全性與效率之間的一種妥協,研究者發展出「半裝置相依(semi-device-independent)」協定,那沒有如此嚴格的要求,不過卻會對裝置的容量設限。這些協定能夠產生真正的隨機數字,不過它們仍需要大量的後處理運算能力來證明數列是隨機的。


以更多運算力達到更多隨機性

在這篇新論文中,研究者的主要貢獻是證明半裝置協定存有一種權衡(tradeoff)。當用以分析實驗資料以及驗證其隨機性的運算力愈多,對於產生隨機資料之測量裝置的要求,就可以不需要這麼嚴格。

基於這種權衡,研究者設計了一種新的演算法,那可以從實驗中提取更多資料,接著,使用大量的運算力,就能夠驗證大量的隨機數 -- 比至今所開發出來的任何其他方法都來得多。更重要的是,它能夠更快速的完成,即使那些使用較慢方法無法完成的案子都能夠完成。

"我們的方法讓我們能夠比標準方法驗證更多隨機性," Pawłowski 說。"讓我們假設,你使用後者(標準方法)並達到 1 bit/second,而使用我們的你可達到 2 bits/second。這表示,以相同的方式來驗證,利用我們的方法你只需要一半的時間就能夠產生需要的位元數量。這很不錯。"

"不過這裡有當我們的方法達到 1 bit/sec 時,標準方法仍為 0 的例子。現在,我們的方法變得真的很重要,因為沒有了它,我們就有了一套完全沒用的裝置。我認為這是最大的優勢:使無用的裝置變得有用。"

這種新方法也有這個優勢:它不像其他方法那樣需要改變物理量子系統,然而其成本來自於需要更龐大的運算能力。無論如何,研究者相信這是一種值得的權衡,而且預期這種新方法將會引領未來的隨機數驗證研究。

"我們在一個例子中證明我們方法的有用,但我們有初步的結果與手工編織的參數(hand-weaving arguments),那指出我們的方法應用到不同的實驗設置與情境中(例如,完全裝置相依,或某一部份獲得完全信任)," Pawłowski。"我們現在試圖證明這個,並看看在那種情況下它最有用。我們的第二個目標是試圖減少驗證更多隨機性所需要的運算時間,我們在此也有一些初步結果,指出那能夠辦到。"

※ 相關報導:

* Increased certification of semi-device independent random numbers using many inputs and more post-processing
http://iopscience.iop.org/article/10.1088/1367-2630/18/6/065004
Piotr Mironowicz, Armin Tavakoli, Alley Hameedi,
Breno Marques, Marcin Pawłowski and Mohamed Bourennane
New Journal of Physics.
doi: 10.1088/1367-2630/18/6/065004
產生隨機數的新方法能改善網路安全

沒有留言: