任何密碼都可以用窮舉推算出來,只是時間問題。如果是這樣的話,那不是很不安全?
一個月以前被邀請回答這個問題,覺得太簡單就沒答,評論了一句「這可能是知乎密碼學話題下最萌的問題吧」。
然而今天我再次刷到了這個問題,下邊的答案卻沒有一個讓我滿意的,大多數答案的概念都是混淆的。所以還是決定簡單說說。
首先要搞清楚概念:什麼是密碼方案?什麼是密碼標準?
一個完整的密碼方案由三個演算法組成:密鑰生成演算法、加密演算法和解密演算法。其中密鑰生成演算法是一個隨機演算法,輸入一個安全參數,它會給出合法的加密密鑰和對應的解密密鑰;加密演算法的輸入是待加密的明文和加密密鑰,輸出是加密後的密文;解密演算法的輸入是密文和解密密鑰,輸出是明文。
一個成熟的密碼方案,以上所說的所有演算法都是公開的,其安全性全部來自於密鑰。那麼這個安全性如何體現呢?這裡要簡單地提兩個概念:圖靈機及其時間複雜度。
圖靈機是一種計算機器:給定輸入,它會按照內置的規則進行計算,最後停機並給出一個輸出(這裡不糾結紙帶等概念)。比如說我可以設計一個圖靈機,它可以計算輸入的二倍。那麼我就列印輸入,並在最後加一個 0 (二進位數乘 2 就在末位添一個 0)。
而時間複雜度是說,對於一個特定的圖靈機,輸入長度為 n 時,停機所需的基本運算的次數 。這裡的基本運算涉及對紙帶的操作,大家理解為對二進位的一位進行一次操作即可。
說清楚了這兩個概念,我們現在就可以談安全性的定義了。在定義中我們引入了「敵手」這個概念。一個敵手可以理解為一個圖靈機,它擁有我們的密文,可能還擁有一些其他的信息或能力。不過一般情況下,我們只允許它擁有多項式時間的能力,也就是說這台「圖靈機」的時間複雜度 必須總小於某一個多項式。我們把這種敵手稱為 P.P.T. (概率多項式時間)的敵手。
此外,我們還需要定義「可忽略函數」。一個可忽略函數是一個正值函數,它下降的速度比任何多項式的倒數都快。也就是說,一個函數 是一個可忽略函數,當且僅當對任意的多項式 , .
這樣,我們就可以定義一個密碼方案的安全性了:
一個密碼方案是安全的,當且僅當對任意的 P.P.T 敵手,攻破方案的概率是一個可忽略函數。
當然,這個定義是很不嚴謹的,因為「攻破」這個詞沒有被很好地定義。在實際的研究中,我們會考慮不同的敵手能力和不同的「攻破程度」。但最基本的考慮仍是:P.P.T. 的敵手能不能以大於可忽略函數的概率搞定。
比如說最著名的公鑰加密方案 RSA ,如果只能窮舉 較小的素因子 ,那麼平均需要枚舉的數量級是 。而輸入 的話,長度是 級別的。也就是說,敵手枚舉的次數至多是 的多項式級別的。而對於任何一個 的多項式,它在 時與 的比值的極限都是 ,因此破解的概率就是一個可忽略的函數,這樣 RSA 加密方案就是安全的。
如果以後有一天,我們可以確定私鑰的每一個比特,那麼破解 RSA 的時間就是輸入長度的線性函數,那麼運行線性時間就可以確定私鑰,自然破解的概率就不是可忽略的。如果那樣,RSA 就不再安全了。
而密碼標準則是根據最新的計算機計算能力和密碼方案的研究制定的實際應用密碼學方案的實現準則。比如說三四十年前,512 比特的 RSA 方案就能抵抗當時世界上最快的計算機(我沒有查,只是舉個例子),那麼密碼標準可能就是密鑰長度為 512 比特。再過 20 年,計算機的計算能力提高了,那就變成 1024 比特。
當然了,密碼標準可不僅僅是密鑰長度,它包括了實現密碼方案每一個細節的要求,每一個要求都是密碼學專家總結出的可能的漏洞。而且密碼標準也會隨著最新的研究成果不斷更新,以保證按照標準進行實現時方案的安全性。
回到題主的問題:我們現實生活中所用到、接觸到的各種密碼系統,都是對安全的密碼方案,按照密碼標準實現出來的(當然也有大意的程序員不按照標準做,它們通常得到了系統被攻破的後果23333),這兩者就是密碼安全性的保障。如果沒有意外情況(比如說你自己在家琢磨出了確定 RSA 每一位私鑰的演算法並且沒有公開),那麼按照標準設計的系統,即使使用最先進的計算機,其破解時間往往都是不可承受的。當計算機的計算能力發展時,密碼標準會相應地進行修正,以保證這個不可承受性成立。
正是在這種情況下,我們才能放心地享受信息技術帶給我們的種種便利。
9.1 補充:評論區注意到了兩個值得一提的問題。
@以琛 提到,密碼的安全性是相對的,只要破解代價遠遠超過密文價值即可。
事實上不是這樣的。我舉個例子:山東三男子投18萬造假幣 僅造出16萬枚1元假硬幣
大家顯然認為,這樣的行為是很蠢的。但是注意到新聞中有這麼一句話:
中央財經大學中國銀行業研究中心主任郭田勇教授分析認為,山東制販假幣的犯罪團伙投入18萬元只造出16萬元假硬幣的主要原因,在於購買模具設備和材料的成本較高。
購買模具和材料的成本高,因此只造出 16 萬。但是模具已經買了,所以再繼續造的話,每造一枚硬幣的成本肯定低於一元了。如果他們持續製造,最後同樣會獲取暴利。
密碼安全和這個問題有類似之處:破解一台價值一元的計算機的漏洞可能需要花費一千元,但破解之後編寫程序,放那跑一天,說不定就攻破了三千台有這個漏洞的計算機。可能你的信息不值錢,不會有人專門盯著你去破解,但是有可能有人隨手寫的爬蟲包含了你的網頁,你又恰好有這個漏洞,你的信息一樣是被非法獲取了的。
@池塘里的魚 提到,我們可以在輸入密碼的時候採取輸錯三次就凍結這樣的手段,防止暴力破解。
事實上,這種情形已經不是所謂的「密碼學」所研究的了。這不是一種加密機制,而是一種在線驗證機制。我們所說的密碼學,說的是我將一個信息用一個密鑰進行處理,得到的密文可以被擁有解密密鑰的人輕易地解密,得到消息;而對沒有這個密鑰的敵手,則很難解密。也就是說,敵手能夠獲取到密文並對其進行離線處理,比如暴力破解等等。而我答案里所說的一切,都是在這個模型下討論的。
人的平均壽命不到3×10^9秒。人類有記載的歷史,只有1.5×10^11秒。地球到現在也只有1.4×10^17秒。宇宙的年齡大約是4.2×10^17秒。很多密碼的窮舉時間遠大於這些數。是的,時間可以算是這個宇宙最稀缺的資源。
反對 @baskice ,不好好搞萌百炒什麼幣(
2015 年全球初級能源產出是 168,519 TWh[1],假設這些能源全部拿去喂 Antminer R4 礦機 [2] 的話,可以帶動 台,換算成算力就是 。
假設用窮舉所有 256 位串的方法去破解某個 hash 的話,所需的時間是多少呢?
對不起,時間真的是宇宙中最稀少的資源。
我們再來反向算一下。
你有 的任務,用同款礦機換算成能量就是 ,差不多是整個可觀測宇宙等效能量的 1% 。
也就是說,整個宇宙,也就夠你破解 100 次密碼……
[1]:https://www.eia.gov/outlooks/ieo/pdf/0484(2017).pdf
[2]:Antminer R4, the most silent yet powerful bitcoin miner
這個答案是對 @王希 答案的一點補充,也是對 @王希 答案下 @錢宇 的問題的回答。閱讀這個答案需要一些CS本科程度的知識背景。
問題 1 是因為二進位輸入,長度是log2 N嗎?
是。同樣也是因為使用了圖靈機(Turing machine)或者random access machine 做為計算模型,而且假設 1)數據都是用二進位表示,2)圖靈機紙帶(tape)上,每個格子(cell)里只寫一位0或者一位1。那麼輸入數據十進位N的總長度所需要的格子數也就是 個了
下面用小寫字母n來表示 ,即
問題 2 敵手枚舉的次數至多是 的多項式級別的,為什麼不能枚舉更多次呢?
這是對安全模型中攻擊者能力的一個限制,我換個角度來回答。
直觀上來說,沒有密鑰的話,必須要求敵手解密的速度比持有密鑰的用戶「慢足夠多」,否則不安全。更確切地說,敵手即使使用的是最好的破解演算法,在沒有密鑰的情況下,也必須嘗試比有密鑰用戶多得多的次數才能攻破加密演算法。
不過,嘗試次數多出多少才算足夠多呢?
得超過用戶演算法所在的複雜度等級(complexity class) 吧
考慮一些常見演算法的複雜度和它們所處的複雜度等級,後者定義參考 http://cs.brown.edu/~jes/book/pdfs/ModelsOfComputation_Chapter8.pdf
二叉樹查找 這個屬於 ,也就是在以 為多項式的時間內、確定性圖靈機上可解的。
樹遍歷 這個屬於 ,也就是在n的多項式時間內、確定性圖靈機上可解的。
pollard"s rho, 用來解決一般域上的離散對數問題 屬於 。
不同複雜度等級對應的時間(即操作步數)的差距是巨大的
所以如果正常解密需要n^2步,而攻擊者沒密鑰得需要2^n步的話,就正好說明加密比較安全。
很有意思的一個觀察是,如果同一個複雜度等級內的函數彼此相乘c次,比如 ,其中c是和n無關的常數,且n足夠大,那麼 仍舊是小於n的,因此仍舊屬於 。類似的有 ,d是另一個與n無關的常數,且n足夠大。
形式上來說,假設 和 都屬於一個複雜度等級 , 那麼 、 以及 都屬於 。(注1)
再回到上面對攻擊者嘗試次數的討論。
假設正常用戶的計算時間是 ,成功的攻擊者的最大嘗試次數是 ,那麼任意攻擊者總的時間複雜度是 。這裡考慮 的情況,即用戶計算的複雜度還是一個多項式。那麼,一個安全的演算法必須使得 能到達比 更上層的複雜度等級,比如到 甚至 。
反過來,為了論證這一點,只需要論證對於所有的攻擊者,只要嘗試次數次數 (即 還是個多項式),都攻不破加密就可以了。套用三體的設定,但凡攻擊者木有做降維打擊(自己擁有有效解決PSPACE-hard問題計算能力,反過來算NP-complete問題),嗯,演算法還是很安全的。
嘗試次數比具體的解密操作多出些無所謂,無論 還是 這種形式,但是不能多出一個數量級。至於 本身就屬於 ,而且我們在討論計算性安全(computational security) 的話,呃,肯定暴力破解了啊,因為可能的密鑰個數也就是這麼多……
注1, 為了可讀性,我在這裡混用了「問題的複雜性」和「演算法的時間複雜度」這兩個概念,都用了描述前者的complexity class
我爹休息時喜歡做保險柜。我給他打下手時,他總愛跟我兜售他的「保險觀」,總結起來就兩條:第一、想清楚要保險的東西對於防範對象值多少錢,然後設計出使得對方要花費更大代價才能攻破的系統;第二、即使是這樣,還是有一定幾率碰上不計成本或者預期太高的賊,所以保險柜的宿命就是被撬開,所以設計的重點應該是讓這個被撬開的過程儘可能漫長、儘可能費事、儘可能受控,進一步增加賊的風險。這兩條適不適用於保險柜,我不知道;說不定適用於密碼吧。
如果用資訊理論安全 (information-theoretic security) 的方法加密,例如one-time pad (OTP),即可保證無論如何窮舉也無法破譯
在目前計算機安全領域
當然也就是俗稱的哇黑客真厲害領域
窮舉破解也叫做暴力破解,代表了沒什麼技術含量就是硬幹,順便說一句在IT行業,什麼東西帶暴力兩字,都是說沒什麼技巧硬幹。
暴力破解其實並非簡單額一個個試出來,還是應用了概率學的,一般來說,暴力破解的時候,有一個叫做字典的東西,這個東西是廣大黑客的心血結晶,是很值錢的,在破解領域,好的字典,是很貴的。
字典就是常見的排列組合,全球有很多人,每天都在黑各種密碼,來充實字典。所以,如果你的密碼在字典上,是很容易被破解軟體直接破解的。
所以你看到,樓下有很多簡單計算組合有多少個,每秒試多少個的,都是初級理解,因為根據概率論,並非每個嘗試的命中概率都一致,這是黑客部分一直在努力的。
而防禦部分,其實簡單的很,增加嘗試的時間。所以目前來說,一般的密碼登陸,當你錯誤幾次以後,起碼會跳一個人機識別出來,這樣,你就不能採取程序快速嘗試了,更高的安全級別下,錯誤次數上升,會直接鎖定賬號。
所以,目前來說,80%的密碼破解,主要還是走phishing,而非窮舉
張靚穎曾經說過:你的時間非常值錢,所以不要浪費在窮舉密碼上!
很有意思的問題。是的,所以的密碼都可以被窮舉法弄出來,只是時間問題,這個一點都沒有錯。
你可能聽過這個段子:
我有500W人民幣存在銀行里,但是忘記密碼了。每次試密碼都要花費2元人民幣。於是,我每個星期都在花2元錢去試。
對,這個就是福利彩票35選7。我們完全可以把這個福利彩票35選7當成一個系統,開獎號碼就是密碼。那麼每次35選7的開獎的結果就是一個排列問題:
我只要買彩票的時候用窮舉法買,一定可以買到中獎的號碼的。但是為什麼沒有人會這樣做呢?
每次買彩票要花2元,那麼他的花費就是:
也就是要花差不多678億元,中獎才給500萬,成本遠遠高於付出。
密碼也是一樣的,如果你破密碼要花費的成本遠高於收益,那麼這個密碼破解是不值得的,也就沒有人願意去做了。
更新,對了,35選7是組合不是排列,要除以5的階乘的,也就是只要花5億多就可以中500萬大獎。另外我還沒有算大獎以外的獎項。我只是想說明一下,絕對安全的密碼是不存在的,只能是用相對安全性來表示。
且不說只要把密碼長度加長就讓理解時間變成天文數字,最簡單一招,密碼輸入錯誤3次就鎖死賬號不讓試探,不就結了,沒啥不安全的。
我可以在計算出來之前改密碼
我可以讓你兩次嘗試間隔不能短於1分鐘我可以讓你三次嘗試失敗後就鎖定一個小時我可以讓你每次嘗試之前都要點擊一張圖片的特定位置你說就算這樣我最終還是可以破解出來看第一條密碼本足夠長且隨機的流密碼不可破解,無限時間都不可以。
任何彩票你都能中獎,只要你把所有號碼全買了,但這樣收益大於虧損。
據說如果沒有理論上的突破,只靠計算機技術和算力的增長,破解一個密碼還是得用國家級體量的資源的投入。
幾萬年那個事情還是理論上的事情,實際上運氣好幾千年可能就出結果了。
以下內容出自:XuanwuLab/XuanwuLab.github.io
"RSA 2016 會議演講: 現代密碼破解的現狀:https://t.co/d5fI2N4Wgj
利用神經網路為密碼可猜測性建模,Paper︰https://t.co/KJsExuOuIW
密碼學大事件!研究人員公布第一例SHA-1哈希碰撞實例: 密碼學大事件!研究人員公布第一例SHA-1哈希碰撞實例
一篇學術 Paper,介紹的是 RSA-1024 的破解,Sliding right into disaster: Left-to-right sliding windows leak:https://eprint.iacr.org/2017/627.pdf
給你推薦本書:詩云
常用漢字大約6000多個;包括各種歷史典籍,總共出現過的漢字大約有8萬多個(其中絕大部分是早已不再使用的「死字」)——咱就按上限10萬算得了。
那麼,所有可能用漢字寫出來的5言絕句,就是從10萬漢字中隨機選擇20個(可重複)的不同排列數——我記得初中數學教過怎麼算這個。
如果你懂編程的話,一個大約百八十行的小程序就可以完成「窮舉所有五言絕句」的任務。
從此以後,再也不需要詩人了。他們能寫出的詩,都在窮舉結果裡面。
類似的,假設一部書最多500萬字,那麼所有可能的書籍的數量就是「10萬種漢字,每種最多取500萬個,排成長度為500萬的長列,求其不同排列數」。
這種程序很容易寫。把前面那個程序的字數限制改成500萬就行了。
嗯,從此以後,再也不需要作家也不需要科研了。任何小說,任何論文,任何教材乃至它們的解釋、深入淺出的科普作品……總之吧,任何可以用漢語表達出來的東西,都在窮舉結果裡面。
進一步推廣,一副4k級的高清圖片,一共4096×2160個像素點;每個像素點有三個分量,每個分量允許256種不同取值——你看,可能表示出的不同圖片也是有上限的。運用排列組合的知識,很容易就能算出這個上限數字。
同樣的,可以很容易的寫出一個小程序,窮舉出所有可能的4K級高清圖片來。
你夢中情人的照片,你夢中情人和你各種秀恩愛的照片,全在其中——哪怕你的夢中情人只存在於你的想像中。
再進一步的,一部電影按每秒50幀、總長按上限五小時算,它至多有「50*3600*5副4K圖片的不同排列數」種。
我們仍然可以很容易的寫成一個小程序,窮舉出所有可能的電影來……
想知道再過2000年,人類最牛X的武器是什麼樣子嗎?整個製造過程都會以視頻形式展現出來,還帶字幕講解的(只要現有語言還能表達出來——如果不能,那就用2000年後的語言解釋;2000年後的語言怎麼翻譯?可以窮舉出來配套的語言教程啊,你想讓哪位巨星給你講解都行)。
所以,我們再也不需要寫作了,也用不著拍照片畫畫拍電影了,更用不著費勁巴拉發射個探測器拍攝木星照片搞什麼勞民傷財的科研了——反正弄一個小程序窮舉出來就完了?
你看,任何東西都毫無難度,只要寫一個簡單的小程序出來,得到宇宙終極真理(只要它可以用現有文字以一套每部不超過500萬字的書表達出來),也不過只是「時間問題」而已。
哦,有個小問題忘了告訴你:雖然理論上可以窮舉;但實際上,燒掉整個宇宙來發電都不夠一台電腦跑完這個小程序;把我們宇宙中的每個原子都變成一個宇宙,都不夠這個小程序存儲窮舉結果的;給我們這個宇宙續命一萬萬萬萬萬億倍,也不夠這個程序運行的。
事實上,這個程序輸出第一篇語法正確有故事情節的小說,所需要的時間就極有可能會耗死我們這個宇宙了……
總之呢,這種小問題交給題主解決就行了;我呢,就先去起點追「霸道總裁愛上我」了——唉,書荒了,人類寫書的效率也太低了。
所以呢,題主如果把這些小問題解決了,千萬要記得喊我一聲 O(∩_∩)O
這種求知慾很好,沒必要嘲諷,我以前也被這個事困擾過。
0x00 簡述
實際應用中,傾盡同時代機器算力達到足夠長的時間不被破解出來,就可以視作不可破,視作安全的密碼體系。
因為算力在不斷提高,所以信息安全專家們需要研究更靠譜的方法。
0x01 一個例子
我嘗試用美國國家安全局NSA設計的SHA演算法家族舉一個盡量淺顯易懂的例子。
SHA演算法家族和更為常見於人們生活中的md5均為雜湊演算法,又叫hash演算法。
這類演算法通俗講上是具有唯一性,即演算法設計者認為這個演算法幾乎不可能有兩個不同的明文擁有一樣的密文,因此可以應用作為數字簽名等。
SHA演算法家族包含5大種加密演算法,SHA-1、SHA-224、SHA-256、SHA-384、SHA-512,5大種中後4種又統稱為SHA-2系列演算法。廣泛應用於SSL、SSH、IPsec等。
從上一自然段我們可以總結出,把SHA家族比作互聯網安全的基石,都毫不過分。同類的md5演算法數年前就被破解,而後正如題主所說,眾多科學家也都意識到,SHA-1演算法不怎麼安全,但是大家依然在用,知道他不安全,甚至知道他為什麼不安全,但是因為目前的技術水平還沒人真正破解了SHA-1,所以大家依然當他可用。
然而就在今年,SHA-1演算法被谷歌徹底攻破,示意圖如下,即利用假文件產生了和正身一樣的SHA1計算結果,術語叫「實現碰撞」。(圖片來源:遍地新聞隨便找了一個,侵刪)
唯一性被打破,SHA-1演算法頃刻之間土崩瓦解,這次破解大大推動了業界廢除他們早已認為不安全但是就是破解不了的SHA-1演算法。
但是注意一點,谷歌給出的結論是,這次碰撞耗費的算力是單CPU 6500年加上單GPU110年,注意,這還是應用了谷歌研究人員優化演算法的結果,而不用優化方法直接暴力破解需要單CPU1200"0000年的算力(數據來源為眾多新聞網站)。
印證了題主所說,時間問題,但是這個暴力破解時間也未免太長了點。
0x02 結論
確實,絕大多數演算法都能被暴力破解,只是時間問題,但是,當時間足夠漫長且沒有人擁有好的方法縮短這個時間的話,就可以被認為是安全的,是可用的。
就算理論上可以被破解,在有人實際在可忍耐的時間內破解過之前依然可以被視為安全的,SHA-1的故事就在告訴我們這個道理。
當然大家大可不必擔心,挑戰破解這些高級加密演算法的人太多了,大家都爭著首發破解呢,如果哪天哪個廣泛應用的演算法不再安全了,一定會有更安全的頂上來的。
0x03 後記
小小本科畢業生一枚,而且研究生也不再學習信息安全,有些知識已經久遠,以上文字可能有理論上或者邏輯上或者表述上的錯誤,歡迎各位大佬火速指正:D
0x04 勘誤致謝
1、感謝鳶一摺紙的指正,0x02第三自然段將「不可能」改為「幾乎不可能」
2、感謝指正,從0x00開始標註序號
之前看了一些RSA,了解到現代加密演算法,用的素數都是10的30次方以上級別的。。。
什麼概念呢,就算你一秒檢驗出十億個數(差不多現在超算一切情況理想的極限,感謝@Reskip指正),大概你需要3乘10的13次方年。。。也就是30萬億年這樣。我們的宇宙才140億年,你解開密碼的時間,夠宇宙從誕生到現在兩千次的。
沒有無窮的壽命,一切都免談。題主一句「只是時間問題」就打算把我們打發了。
說實話,難道你這個問題裡面還有比時間更大的問題?
沒必要嘲諷題主,實際上題主擔心的風險是存在的,隨著計算能力的不斷提升,以及擁有極大計算能力的組織的存在,僅僅依靠數學計算強度是不足以長久保護系統安全的,考慮下同時使用幾千個GPU本地計算明文的情況,大多數密碼會被在幾十天內計算出來。
信息安全策略里有兩個常用的原則:
1.密碼要包含大小寫數字和特殊字元等;2.用戶需要定期(比如三十天)更換密碼(現在越來越多的平台不允許使用以前用過的密碼);這兩原則就是為了對抗密碼先天的窮舉缺陷的,前一個原則可以極大提高被窮舉的時間,後一個則是在被窮舉出來之前就更換新密碼。
信息安全是一個體系工程,任何一個環節缺漏都可能會造成整體崩潰。題目不一定正確噢。
如果給你一段純數字的信息,你怎麼知道解密出來的信息就是真實的信息?因為信息不一定是人可讀可識別的,另外如果獲取到的密文太少,也不可能通過統計學方式去確定解密後的結果是否正確。
即使題目說的情況是正確的,那麼就有「信息值多少計算量」了。比如比特幣很典型,相當於一種解密計算。如果通過計算獲得的比特幣超過了計算消耗,那麼就值,如果少於就不值。
另外,信息的時效性也有關係。比如當前有某種手機生產技術非常值錢,過不了幾年就被淘汰了;比如每年9月前蘋果手機照片泄露就很值錢,過了發布會就一文不值了。
推薦閱讀:
※如何證明Manacher演算法的時間複雜度是O(n)?
※如何看待用中國大陸地區境內的搜索引擎搜索主席樹得到的結果文不對題?
※有哪些演算法是中國人自己創造的?
※有哪些有趣的樹結構的表示方法?
※背包問題是否本質上都是DP?