2015年9月16日 星期三

Cryptography 1:密碼學裡的隨機

小弟最近消失了好一段時間,都沒在更新文章,其實小弟是掉到陰間去了,在陰間時間變很少,都不寫code(也沒電腦Orz),也不再看相關的東西,例如rust 的文件了,因為我知道一年後出來,rust-lang 搞不好都翻了兩翻,而且看了也不能直接練習,看了等於白看。
最近把時間花在一些比較不會變的東西,像是計算理論、密碼學、數學等等的東西,請我的好友強強林寄列印的書給我,利用放島休的時間聽coursera 上stanford 的cryptography,就算在陰間還是要定期充電,不然出來都變白痴了(雖然說本來就非常弱)。

下面這是聽密碼,關於其中隨機這件事的一些體悟:

密碼學的重點,其實就在「燙」…啊不對,是在「隨機」(random) 兩字,普通的訊息加密變成隨機,讓竊聽者猜不出訊息的內容,才能達成密碼學最重要的目的。
在密碼學裡很常看到xor,就是因為xor 的特性:當你把任何東西X跟隨機的訊息Y xor 起來,出來的東西的機率分佈會跟Y 一樣隨機,因此只要準備一個夠好的Y夠隨機,一個xor 就能把X 給加密好,所以問題就出在Y到底夠不夠隨機上。
當然我們可以用硬體雜訊產生器之類的東西,製造一個真隨機的來源當作密碼,但這在密碼學上不實用,如果是真隨機,表示加、解密雙方無法重現這個密碼,就無法加、解密啦;因此我們需要pseudorandom(偽隨機),用有規則、可重現的方式製造一個很像隨機的東西。

無論是pseudorandom generator/function/permutation,都是設法設計一個夠亂的變法,並讓它們儘可能像random,並讓攻擊者在有限的運算資源限制下,分不出兩者的差異。但總歸來說,兩者還是不同的,以pseudorandom generator 為例,我們會設計很多統計上的測試,像是 0, 1 的數量不能差太多;不能有太長的0序列……讓這些測試無法分出兩者的差異。

千萬不要小看隨機這件事,小小的不隨機,都能讓攻擊者找出一絲絲突破的空間,例如Caesar cipher 隨機性不夠,用頻率攻擊法可以快速破解;enigma 只因為輸入跟輸出不會是同一個字,也能利用這點,配合電子計算機在幾十分鐘內破解;課程中有個例子是DES 有一個問題,可以用線性運算找到一個發生率小於1/2^21 不隨機事件,利用這點,就足以大幅削弱DES 的安全性,也就是說,我們發現這個pseudo-random不是真random,用這個運算預測pseudorandom下一個輸出時,可以比瞎猜好1/2^21。

----

至於random跟pseudorandom是不是一樣呢?

理論上,如果給定無限多組的統計檢定,終究可以驗出真隨機和偽隨機的差異,但同樣的在"有限的運算資源"限制下,能進行的終究只有有限組統計檢定(這個教授倒是有提到,如果P=NP的話,我們就可以……),也就是因為"有限的運算資源"限制,保護了現行的加密系統不被輕易破解。

以真實例子來看,我們可以斷言,pseudorandom不會出現全0這樣罕見的序列,但這樣的序列在random 的狀況是確確實實會發生的,所以pseudorandom 和random 真的有差,但這差異的發生率之小,除非我們能窮盡所有檢查,才能檢出這種差異。
我們在做的事情,就像往霧裡一指,說:來,這是random的產出,然後我們放出另一團pseudorandom 霧,自問:你覺得你這團pseudorandom霧和這random霧像不像?有限的檢查下,我們可能只能驗一下外觀,兩個當然一樣;但給我無限的檢查,會發現random霧裡有幾顆是硫酸、幾顆是氫氧化鈉,他們和你的霧當然不一樣,但把兩團霧混在一起,其實這根本就沒差。

沒有留言:

張貼留言