用無理數加密,如何破解?

通信雙方約定使用一個大整數的自然對數來加密,

發信方選用一個足夠大的整數,比如2的57,885,161次方? 1,又或者,(為了方便我計算,)1997,通過耳語的方式告訴收信方,

然後通信兩方同時開始計算,

發信方,得出ln(2^57,885,161-1)=40122936.143408504386811297524978......(我可能沒算對)

ln1997=7.5994013334158152158203249294064......

然後將傳輸的第i個char字元+上ln1997的第i位數,變成另外一個char字元,

比如「hello word」+7599401333

h+7=o,e+5=j,l+9=u,o+4=s,空格+0=空格......

然後,密碼學家將如何破解?

再進一步,我設計一個比較複雜的無理數

sin(2.33/(√3.22)+ln(3/7)*1997)=-0.5467864830822379752182897967522......

也就是說加密方法是選定的一個無理數,但是這個無理數得出的方法是秘密的

不是說,我原式始終使用ln X或者sin(x/(√y)+ln(z)*w)這種加密方法,原式有多長,有幾個有理數,幾個無理數,採用什麼計算方法,這都是秘密的。

只要你的解密式子有些微的差別,都會導致尾數完全不等,無法正確解密。

你截取再多的密文和明文,你最多能得到前面的一段數字,比如54678648308223797521828,你不會知道後面的尾數是多少,你無法算出精確的答案出來,比如ln(3/7)我換成ln(30001/70001),對尾數會有影響,或者把2.33換成8/3也一定會有影響的,但是在前面的這些位數是看不出來的。

有人問這個和隨機加密有什麼區別,

每一次加密,往前推一段,短短的一個計算式,得出的加密能力是無限長,加密規律永不循環


先說結論:題主設計的演算法是沒有應用價值的,但思路有可取之處。

現代密碼學中的加密演算法可以分為兩大類,分組加密流加密。分組加密例如DES、AES等等,是用同一個密鑰對數據分塊加密。而流密碼例如RC4、RC5等,是通過一個流密鑰發生器,不斷產生新的密鑰流,然後與原數據做異或運算實現加密。題主設計的這個演算法,其實就是流密碼的思路。這一點目前所有的回答都沒有指出,我感到非常的意外和困惑。

題主的這個演算法不具有實際意義的原因,大家基本都已經說得比較清楚了。那就是你無法有效地計算一個無理數。讓我們來看一則新聞:

Yahoo科技公司的尼古拉斯·蘇使用Yahoo的Hadoop雲計算技術將以前的π值計算的記錄位數整個翻了一番,達到2千萬億位,這次計算在Yahoo公司1000台電腦上運算了23天,相當於單台電腦運算500多年的工作量。

聽起來好厲害,我們看看這個數有多長,2,000,000,000,000,000位,好厲害,假設加密一個位元組用1位,可以加密2000TB的數據,好像又覺得不是很厲害了。一台電腦,算500年,只能加密2000TB的數據,那我要把我的2TB移動硬碟加密一下,要不間斷地算上半年!

=======================================

這個問題至此就回答完了,重新貼一遍結論:

題主的這個演算法沒有應用價值,但思路有可取之處。

=======================================

=======================================

以下內容受到諸多網友質疑,我進一步說明一下

感謝各位知友的提醒,題主這個演算法的主要問題在於試圖使用一個[0, 9]的雜訊去覆蓋[1, 26]的字母甚至是[0, 255]的整個位元組。要想隱藏原始信息,我們需要改變原始信息的分布特性,而一個[0, 9]的隨機數是不足以做到這一點的。通過對圖像像素的變換,我們可以清楚地看到這種不完全的覆蓋,還是會讓原始信息的一些蛛絲馬跡泄漏出來,甚至是嚴重地泄漏出來。

我不認為我的答案是具有誤導性的,我首先指出了題主的演算法在性能上的巨大缺陷,開門見山地指出了其不具有實用價值的事實。第二,我使用了對圖像像素進行『加密』的方法,直觀地演示了用較小的隨機數變換較大的原始數據會導致的安全問題。其中『計算無理數』和『(一個位元組的)原始數據與(一個十進位位的)隨機數做加法』兩個關鍵點都是由題主明確指出的,不是由我惡意曲解的。其中『計算無理數』的主要問題是性能低,『做加法』的主要問題是會導致信息泄露。上面引用的新聞說明了第一點『性能低』,下面的實驗說明了第二點,也就是『信息泄露』。

我說題主的演算法是不安全的,我仍然這樣認為,因為『演算法』這兩個字就表示了從隨機數生成到應用隨機數加密的整個過程。我沒有試圖說明OTP(一次性密碼本)是不安全的,如果說我的回答有問題,那我只不過是沒有指出恰當地應用OTP是安全的,而只是證明了不恰當地應用OTP是不安全的。而對OTP的不恰當應用,是題主的問題,我只不過是編程實現了題主描述的演算法。

========================================

以下是原答案的後半部分,可以探討,不要噴

========================================

然而遺憾的是,題主這個演算法的問題還不僅如此。一個加密演算法,其安全性的保障來自於2個特性。一是「混淆」,二是「擴散」。混淆大家都比較容易做到,然而擴散就不是那麼容易了。為了證明題主的演算法不具備「擴散」特性,我專門編寫了一個程序來進行了實驗。我去網上找到了圓周率100萬位的數表,刪掉了小數點,存在一個叫做pi.txt的文檔里。我們要使用這個數表對512*512像素的Lena圖進行加密。圖片設置為灰度模式,每像素8位(1位元組),每像素使用一個pi的數位來加密。

加密前的Lena女神是這樣的~

加密之後的Lena女神是這樣的:

。。。。。。。。。。。。

加密的核心代碼大概是:

int c = fgetc(fp) - "0";
pImg[0] = (pImg[0] + c) % 256;

加密後跟加密前幾乎沒有區別。如果你仔細觀察,會發現加密後左上角的灰色背景上的一些雜訊好像被增強了一些。這並不是因為我的程序寫錯了,而是因為對一個位元組加密時,一個位元組的取值範圍是0~255,而加上的數字只可能是0~9,加上的數字比本身的數字可能小2個數量級,所以加上跟沒加幾乎沒區別,照片看起來就沒啥變化。

如果就這樣否定了題主,我覺得還是不夠有說服力,我們既然發現了問題,不如就解決一下。我們把一個位元組拆成兩半,也就是4位,然後分別加密,這樣十進位的取值是0~15,跟0~9在一個數量級上了。也就是說每個位元組使用2位pi的數值來加密,代碼大概是這樣的:

int c = fgetc(fp) - "0";
unsigned char low = (pImg[0] 0x0F);
unsigned char high = (pImg[0] &>&> 4);
low = ((low + c) % 0x10);
c = fgetc(fp) - "0";
high = ((high + c) % 0x10);
pImg[0] = ((high &<&< 4) | low);

現在再來看看效果,加密後的圖是這樣的:

哇塞酷!變成一坨了!但是仔細看一下,其實還是能夠看出圖像中人臉的輪廓,這個加密過程其實主要破壞了圖像的低頻部分,而對高頻部分影響較小,使得我們仍能識別出Lena的五官、頭髮、草帽穗等高頻元素。

我們再試試另外一張圖

加密之後變成:

儘管加密後文字變得很難識別,但是用力看,是可以大概識別出文字內容的。如果我們把上面的這張圖扔到Photoshop里調整一下色階:

呵呵。。。一個可以使用Photoshop破解的加密演算法。。。

祝題主好運~

==========分割線===========

下面回答網友們的疑問~!

@笨蛋小明 說,把加法換成異或是不是就看不出來了。答案是否定的~!而且即使你找到了一個猥瑣的運算,使得加密後的圖看不出來原來的東西了,也並不能證明演算法是安全的。一個演算法不具備」擴散「的特性,不管你採用加法還是異或還是什麼奇葩的方法,它都不具備」擴散「特性。我還就真的寫了一個異或的版本,下面上圖~!!

加密的程序核心部分是這樣的:

unsigned char low = (pImg[0] 0x0F);
unsigned char high = (pImg[0] &>&> 4);
low = ((low ^ c) % 0x10);
c = fgetc(fp) - "0";
high = ((high ^ c) % 0x10);
pImg[0] = ((high &<&< 4) | low);

上面那兩張圖加密後的效果是這樣的:

以及

這不還是坑爹嗎!!!

感謝 @劉巍然-學酥 大牛提出的演算法,我又做了一個實驗,每個位元組使用8個數加密,奇數為1,偶數為0,8個小數位對應8個二進位位,形成一個位元組,再與原圖異或,確實取得了非常理想的加密效果,肉眼不能識別,而且直方圖也基本上是均勻分布的。這樣做應該是一個OTP的效果了,所以如果使用正確的話應該是可以安全加密的。

然後再附上加密程序的核心部分

unsigned char mask = 0;
for(int b = 0; b &< 8; b++) { c = fgetc(fp) - "0"; mask &<&<= 1; mask |= (c 1); } pImg[0] ^= mask;


題主其實用的是可計算數,是無理數的一個子集。也就是說,用到的數其實是一個程序的輸出序列。

如果說是可計算數,那麼它其實是一個非常具有一般性的一個演算法:

- 密碼是一個程序P(比如一個小python script)。

- 加密一個N個bit的文本:計算程序P的前N個輸出bit和原文xor得到密文。

- 解密一個N個bit的文本:計算程序P的前N個輸出bit和密文xor得到原文。

這個設計裡面最弱的部分可能是那個xor了……破解的人只要拿到任何兩份同樣密碼程序加密的文本,再互相xor一下,得到的就是兩個原文的xor了!

但如果把其中的作xor運算變成可以做任何運算,那麼其實天下所有加密演算法其實也都不過如此……

算一個可計算數(運行一個程序P)不一定是指數級的,甚至有可能是很輕量的。但加密規律永不循環的加密方法(無理數)一定是需要存儲無限狀態的。也就是說,總存在這樣的原文,它的長度太長,以至於加密的時候你的內存會不夠用了。

(想像一下,你某天去某網站用https下載一個大片兒,每次都是下載到快結束的時候忽然瀏覽器因為佔用內存太多被kill掉……)

而加密規律永不循環(無理數)這個特徵其實並沒有什麼用。為什麼呢?因為定義了加密演算法對抗暴力破解的強度指標是那個計算程序P是否好猜,有多少種可能的P。永不循環並不是沒有規律可循。從ln(3/7)精確到ln(31/71), ln(301/701), ln(3001/7001), ln(30001/70001)... 其實並不需要很多開銷。

這就涉及到了最重要的部分了。即便是用作one time pad,這個演算法也有一個致命的問題:由於題主的可計算函數大部分都是連續函數(可以級數展開,可以迭代逼近),因此其密碼空間具備非常強的連續性,相似的密碼會得出相似的前綴。這使得破解的人在破解時不需要猜出你準確的密碼,只需要猜個大概,就能一點一點通過逼近進行下去。

用連續函數做密碼計算是一個極其糟糕的選擇。這就好像你的銀行密碼雖然有10位,但是提款機會在你輸入了第一位還沒輸入第二位的時候就告訴你你的第一位輸錯了。暴力破解的時間從10^10坍塌到10*10。

總結一下:

- 題主其實說的是無理數中的可計算數。

- 廣義上講,可計算數其實就是一個程序。一切加密演算法其實都是程序。

- 由於仍然是可計算數,單純是無理數對加強密碼其實並沒有什麼大用,只會增大加密解密長文時的性能開銷。

- 密碼演算法中一定不要用連續函數(此處應該說三遍)。


未邀自答。

竟然在知乎上刷出這麼有意思的一個問題,很欣慰啊!但讓我比較失落的是,已有的回答似乎都有些問題。出於討論,也出於對這個問題的興趣,我嘗試回答一下,如有問題或者錯誤,還請各位大牛們指正~

密碼學是一個比較新的學科,但這個學科的奇妙之處在於它既符合計算機領域「腦洞大開」的特點,又符合數學領域「推理嚴謹」的特點。所以,下定結論之前還是要想明白,解釋清楚。所以在回答問題之前,我想把已有答案中的一些問題指出來。我希望能多普及一些相關的知識,儘可能有理有據又比較直白的說明問題。如我指出的問題並不正確或者不嚴謹,還請討論並指正。

================================

1 已有答案的一些問題

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

@Xylitogum的答案:

能公開密鑰么?不能的話就毫無意義。因為你程序的加密運算都在本地進行,很可能被獲取整個程序的代碼,然後直接找到你用的無理數。

這個地方有兩個問題:

  1. 對稱密碼學和非對稱密碼學是不同的概念。對稱密碼學仍然被廣泛使用,並仍具有重要的研究意義。
  2. 解密運算也需要在接收方本地運行,如果說獲取整個程序代碼可以得到密鑰的話,那麼任何密碼學演算法的設計都是無意義的。

密碼學中有兩個主要領域:對稱密碼學(Symmetric Cryptography)和非對稱密碼學(Asymmetric Cryptography)。對稱密碼學中,加密/解密雙方使用一個相同的密鑰進行操作。非對稱密碼學中,加密/解密雙方使用不同的密鑰進行操作。題主所提出的加密演算法屬於對稱密碼學中的對稱加密演算法範疇。為什麼?請看演算法描述中的其中一句話:

通過耳語的方式告訴收信方。

對稱加密演算法中,密鑰不能被公開,所以通信雙方如何共享密鑰是對稱加密演算法從根本上就無法解決的問題。但這並不意味著對稱加密演算法沒有用途。對稱加密演算法加解密速度要比非對稱加密演算法快幾個數量級。同時,對稱加密演算法中,明文空間可以看做{0, 1}^*(對於分組對稱加密演算法,是人為把明文空間分組,如果加上加密模式的話,也可以人為是{0, 1}^*,參見:為什麼說密文鏈接模式已經喪失安全性? - 劉巍然-學酥的回答)。而非對稱加密演算法都有一個明文空間的限制。在實際中,雙方可以使用速度較慢、明文空間有限制的非對稱密碼學進行密鑰協商或者密鑰傳輸,再利用速度較快、明文空間沒有限制的對稱密碼學進行加密等操作。

此外,無論何種加解密演算法,解密方都需要秘密地存儲私鑰。並且在解密時,解密方需要將私鑰作為參數傳入解密演算法中。所以,如果我們認為程序的加密/解密運算在本地執行,可能獲取整個程序的代碼從而得到無理數(私鑰),那麼我們也可以認為對於所有加/解密演算法,攻擊者都可以獲取整個程序的代碼從而得到私鑰。當然,這裡要指出的是,題主的描述有一點瑕疵,使得我們可能會對題主提出的加解密有理解偏差,認為無理數、或者計算無理數的方法是加解密演算法,而不是私鑰。這一點我會在下面的答案中論述。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

匿名用戶的答案:

密鑰空間不是X的空間大小,而是k的空間大小,這就太小了。

這個地方也有兩個問題:

  1. 如果題主可以正確描述演算法,密鑰空間可以為X的空間大小。
  2. 即使密鑰空間是k的空間大小,這並不意味著密鑰空間小。

在題主的描述中,有這麼一句話:

不是說,我原式始終使用ln X或者sin(x/(√y)+ln(z)*w)這種加密方法,原式有多長,有幾個有理數,幾個無理數,採用什麼計算方法,這都是秘密的。

因此,題主的意思是,f(k)整個函數都作為私鑰。

另外,即使密鑰空間是k的空間大小,我們來看一下k的取值範圍。從題主的描述:

比如ln(3/7)我換成ln(30001/70001),對尾數會有影響,或者把2.33換成8/3也一定會有影響的,但是在前面的這些位數是看不出來的。

因此,k的取值範圍可以理解為實數。當然了,由於絕大多數無理數很難用多項式長度的公式來描述,這些無理數如果用做密鑰的話,會導緻密鑰長度無法使用計算機描述,而導致演算法的複雜度超過多項式級。因此,我們可以把k的取值範圍限制為有理數比較科學。然而,這個範圍依然很大,達到可以超過除了one time pad以外的所有加密演算法的密鑰空間長度。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

@Sqd You的答案:

題主既然有方法秘密地傳遞一種加密方法, 就肯定有方法密碼地傳遞一個加密本吧

注意,題主的演算法所涉及到的私鑰長度可能會遠遠小於傳遞加密本的長度。題主演算法的私鑰是一個公式。這個公式的長度是多項式級的,甚至可能是常數級的。而如果使用one time pad的話,密碼本長度要等於明文長度。如果明文長度較長,那麼題主的演算法就有意義了。

================================

2. 精確定義題主的演算法

很多答案之所以有問題,根源在於題主對於演算法的描述並不是很嚴謹,會導致理解上的歧義。所以在給出問題答案前,需要先精確定義題主的演算法。

對於一個對稱加密演算法,只需要定義兩個演算法:加密演算法和解密演算法。還需要定義一個密鑰空間。在此我不打算用數學語言描述,還是使用陳述的方法。

  • 密鑰空間:全體可以計算得到無理數的數學公式。注意,這個密鑰空間非常大,因為數學公式本身的描述的可能就是指數級的,而公式中涉及到的參數又是指數級的。
  • 加密演算法:使用數學公式計算一個無理數,再將無理數用作one time pad的私鑰加密數據。
  • 解密演算法:使用數學公式恢復這個無理數,再將無理數用作one time pad的私鑰解密數據。

================================

3. 題主演算法的安全性

這其實是一個安全的演算法,而且演算法的安全性達到了one time pad。為什麼?首先要明確,很多答案中提到:

重複使用的話會被破解...單純的這種演算法毫無安全性可言...

談到一個演算法的安全性,就必須要談到這個演算法的安全模型。也就是說,攻擊者在具有什麼能力的條件下,認為這個演算法是安全的。舉例來說,如果攻擊者具有指數級複雜度的計算能力,那麼現有演算法都不是安全的。這個例子有些特殊,我想表明的是我們要限制攻擊者的能力。

所謂理論上安全的one time pad演算法,所有的pad只能使用一次,這樣才能保證理論上安全。如果說用了兩次以上就不安全,而斷言題主的演算法不安全,是不嚴謹的。因為我們可以要求題主的演算法中,對於每一個明文,密鑰對應的數學公式都是不同的。如果在這個條件下,題主的演算法可以達到理論上安全。因為無理數本身是無限不循環小數,從概率上說我們可以認為無理數每一位的取值滿足等概率分布,對於攻擊者來說完全隨機。這樣一來,pad所用可以認為是隨機數,這就保證了安全性。

================================

4. 題主演算法的問題

既然題主提出的演算法是安全的,那麼這個演算法有什麼問題呢?題主演算法根本的問題是:演算法加解密速度是指數級的,這使得演算法無法使用多項式計算能力的計算機實現

為什麼?我們考慮演算法中這樣的過程:

使用數學公式計算一個無理數

那麼,計算這個無理數的複雜度是多少?這引出了一個本質問題:計算機如何計算一個無理數?現有計算機計算無理數的通用演算法是牛頓迭代法等類似演算法。這個演算法不是一個確定演算法,無法完全計算無理數,而是有近似範圍。而且,計算的越精確,所需要的迭代次數越多。如果要求計算精確度達到完全精確,那麼迭代次數是指數級的。我們計算根號2的前多少多少位很簡單,再往後算呢?越來越複雜,計算時間指數級增加,最終會導致演算法永遠無法結束運行。

其實,這個問題在題主的描述中已經顯露了:

發信方,得出ln(2^57,885,161-1)=40122936.143408504386811297524978......(我可能沒算對)ln1997=7.5994013334158152158203249294064......

如果已知密鑰,演算法計算結果與正確結果不同的概率是不可忽略的,那麼會認為這個加解密演算法是錯誤的。類似地,如果這個演算法的時間複雜度是指數級,那麼這個演算法無法使用,也是錯誤的。而題主設計這個演算法的根本問題就在這裡。

這其實讓我想起了有關格(Lattice)密碼學上的一個梗。格密碼學的一個大牛在一個分享報告中曾經提到:

I know that someone tested this lattice-based algorithm, and it never stops... It is a polynomial time algorithm, but it needs to be run 1-2 years for a regular PC.

為何格密碼學,以及現在新提出來的全同態加密(Fully Homomorphic Encryption)等密碼學演算法沒法用?根本上也是這個原因。

================================

那麼,討論到此為止。知乎密碼學討論群的各位,求點評啊!如有任何問題,歡迎留言討論,我會隨時修正答案,讓答案更嚴謹。


已經有的答案已經提到的這其實是密鑰空間為圖靈機描述的一種加密方法。

你們似乎都忘了一個「一般的」圖靈機描述空間裡面有「很多」圖靈機是不停機的……換言之,你的密鑰分布可能是一個比較「既定」的樣子的圖靈機,那把「公共部分」抽取出來放在加密演算法裡面是一樣的。

比如說你的密鑰分布是:對於安全參數 k,密鑰是均勻選擇一個 k 位非完全平方數 m,計算 sqrt(m) 的程序。

那相當於加密解密演算法是計算 sqrt(m) 的程序,而密鑰本身是 m。

保證加密解密的效率的同時並不非要犧牲圖靈機的「多樣性」,實際上,樓主說出來的這個加密方法可以涵蓋目前所有的流加密演算法。假設某流加密體系使用的 PRG 是 G,安全參數 k 允許的加密長度是 f(k),我們完全可以定義一個可計算無理數,使得其前 f(k) 位恰好是 G(seed) 的輸出,那麼這就實際上可以看成是一種「無理數加密法」。

參考 Of Kerckhoffs』 principle 提到的理解方式。


你這就相當於隨機字元串加密……單純的這種演算法在現在毫無安全性可言……

這種演算法理論上要保證安全的話除非做成一次一密,然而一次一密的話何必做你這麼多無用功呢……

你仔細想想,你這演算法和大整數有什麼必然關係?

大整數、自然對數,這是一個數學難題嗎?

你這樣做和隨機生成一個數作為key的區別在哪裡?


其實這是常見的對稱加密的思路——stream cipher吧,雙方先在一個安全的信道里商量好一個偽隨機數生成器,然後後面用這個生成器源源不斷地生成one-time pad。在商量偽隨機數的過程安全,隨機數生成器本身安全的情況下,這個加密當然是安全的。

呃,所以應當說,你這個想法沒有你想像得那麼新穎……

首先,其他答主也指出了,你描述的那個辦法是不行的,one-time pad如果有明顯的統計偏差(攻擊者可以區分出one-time pad和真隨機數的區別來),安全性會大大下降。(比如你的文章里所有空格或標點的位置幾乎能被直接猜出來,所有密文里的9都表示原文里的一個數字字元等)所以你那樣拆10進位數肯定是沒戲的。當然可以像其他答主提到的一樣,搞成二進位異或,應該就好了。

然後,計算無理數的效率其實是相對很低的。跟那種能以均勻速度一直吐數的隨機數生成器比,你這個對具體演算法的要求會複雜很多。不信你試試,自己計算自己寫的某個式子的前80億位,你得寫什麼樣的演算法才能高效地計算出來……別忘了80億位只夠給1GB數據加密而已,實在是沒多少。別的演算法算這麼多可都是秒級的速度呢。

接下來就是怎麼攻擊的問題了。最明顯的攻擊方式顯然是你說的截取到無理數開頭的一段,然後暴力枚舉無理數計算公式。直觀上這麼做複雜度肯定是要爆表的,但是有可能存在一些神奇的搜索方法能降不少複雜度下來,所以如果要用的話,請務必選擇相對更複雜的公式。

(附送一個可以虐特別簡單公式的小玩具:RIES (RILYBOT Inverse Equation Solver))

所以我的結論是,你的方法

1. 在修正十進位的問題以後能用;

2. 效率遠遠不如已有的方法;

3. 安全性取決於你具體選取的公式。


難道只有我一個人不明白這個所謂的無理數加密和我們平常用的加密有什麼區別?

第1997位?如果RSA使用1997位密鑰不就行了么?話說1997位密鑰到底是什麼概念?而且你這個還是十進位的1997位?

計算一個無理數,和算好一個無理數放密鑰文件里,本質上有什麼區別?計算過程再慢再複雜,實際投入使用之後這個計算過程為什麼不優化掉?優化掉之後,和密鑰文件的區別在哪?

你總不能告訴我,無理數是無限精度的吧?

也就是說加密方法是選定的一個無理數,但是這個無理數得出的方法是秘密的

不是說,我原式始終使用ln X或者sin(x/(√y)+ln(z)*w)這種加密方法,原式有多長,有幾個有理數,幾個無理數,採用什麼計算方法,這都是秘密的。

只要你的解密式子有些微的差別,都會導致尾數完全不等,無法正確解密。

我是不是可以翻譯成

也就是說加密方法是選定一個超長整數,但是這個整數是秘密的

不是說,我原式始終使用這個整數,原式有多長,每一位是什麼,這都是秘密的。

只要你的整數有些微的差別,都會導致整數完全不等,無法正確解密。


重複使用的話會被破解,兩個密文的差等於兩個原文的差。


第一次通過寫答案反對某一個答案,因為信息比較多,有點小激動。

首先, @劉巍然-學酥的答案我認為是比較正確的。題主設計的cipher如果能證明無理數小數點後的每一位都是隨機生成的,那麼這就是一個One Time Pad。在正確使用OTP加密方法的前提下,這種加密方式是不可破解的。然而,考慮到現有計算機的計算能力,這種加密方法無法被應用。

接下來是本答案的重點,反對 @況琪的答案。

況琪通過對兩張圖片的加密和破解,實際上說明了OTP是不安全的。然而,不安全的原因恰恰是在於他沒有正確使用OTP加密方法。這個錯誤不是使用了加法而沒有使用異或,其錯誤是使用的隨機數的空間大小小於被加密的字的空間大小。即,使用空間大小為10([0, 9])的隨機數加密空間大小為16([0, 15])的字。正確的做法是,使用空間大小為16([0, 15])的隨機數對圖片進行加密。

以下為實驗部分。

使用 @Milo Yip提供的開源16進位pi項目http://hexpi.sourceforge.net/中的數據作為隨機數。首先加密著名的Lena圖。

加密前:

加密後:

發現並不能從加密後的圖中看出我們的模特Lena。

接下來是著名的八點二十發。

加密前:

加密後:

完全看不出要幾點發了!附代碼,歡迎討論。

from PIL import Image

def enc(in_file):
out_file = in_file.split(".")[0] + "_enc.png"
im = Image.open(in_file)
im = im.convert("L")
key = file("pi-hex.1000000.txt", "rb")
(r, c) = im.size
for i in range(r):
for j in range(c):
val = im.getpixel((i, j)) ^ hexstr2int(key.read(2))
im.putpixel((i, j), val)
im.show()
im.save(out_file)
key.close()
im.close()

def hexstr2int(s):
assert(len(s) == 2)
return int(s, 16)


還不如從pi裡面截取位數…


你想法挺好,可以算是流密碼的變形,實用流密碼的最大安全問題是偽隨機,無理數還是有突破的。但是這種做法既然如此簡單,但學界總沒有文章出來,肯定是哪裡有問題。依我所見,流密碼的設計實現在於硬體電路,應用於高速通信環境。現有的多項式方法,很容易設計出高速加解密電路,做ln運算,是否存在這樣的設計方式呢,如果太慢,肯定後面是沒法實用了。至於理論問題,你可以試著發篇論文,讓行內搞理論的人找找麻煩,或者在eprint或者google的crypt討論組上貼出來,很快會有新答案。

知乎不是討論這類專業問題的地方,能科普正確的結論就不錯了。


題主還停留在加密演算法(也就是那個無理數)保密的時代。


你說的這個和普通的隨機字元串加密沒有什麼區別啊


怎麼一股民科的感覺

===========================

我先講講題主的加密演算法,你看我說的對不對?

(手機碼的,請將就著看)

0、約定通信兩方為A,B。

1、A、B先約定一個數k作為密鑰。

2、計算一個「複雜」的式子f(k),得到X。

3、A給B發信息P1,假設有n1位。用X的前n1位與P1相加,得到密文C1。

4、A給B發信息P2,假設有n2位。用X的後面的n2位與P2相加,得到密文C2。

。。。。。。

題主的意思是:就算前面很多密文都被破解了,也不知道X後面的內容,所以無法破解。

題主,你說我說的對不對?

====================================

顯然題主的想法是大錯特錯的!

因為顯然f是確定的,並且是單射的(請題主回憶高一內容),所以密鑰空間不是X的空間大小,而是k的空間大小,這就太小了。

舉個簡單例子:假設f是ln函數(複雜不負責不重要),那麼顯然X?(ln2, ln3),因為不存在這樣的整數k。

所以,破解了前面幾個就可以破解後面的,運氣好的好一個就行。比如假設破解出X的最前面幾位是69314718,那麼多半就是ln2了,後面的位數自然都知道了。

其實本質上就是明文加上一個隨機數而已,題主為了體現「複雜」,「困難」搞一堆式子,反而不隨機了。

=====================================

下面是吐槽:

1、加法是什麼鬼?還要取模。

2、無限長密鑰,A,B怎麼同步?(假設A中間發了一條信息B沒收到,那B不是要日了狗了?)

。。。。。。

======================================

不過這個方式可以用來生成密碼。比如喜歡浪漫的妹紙們可以將銀行密碼設為870905,它是log1314(520)的小數點後六位。


這個答案是對自己在其他人答案下的評論總結。

===================================================

1. 安全性分析

1.1 很明顯,KPA(Known Plain Text Attack Security)安全滿足不了。無論是否公開無理數產生式

注意加密只是加上0-9的數字,那麼我可以選擇兩個明文

m_0= (65,65,65) 這個是用十進位表示的AAA的ASCII碼

m_1=(90,90,90)這個是用十進位表示的ZZZ的ASCII碼

m_0中每個字元被加上0-9後,密文一定還是大寫字母。m_1會出現Z、小寫字母和[ ] ^ _ `。

所以,攻擊者可以高效效區分m_0和m_1所對應的密文。

KPA安全的定義可參考多次使用「一次性密鑰」(one-time pad)為什麼不安全? - 知乎用戶的回答

嚴格安全性定義的關鍵在於「可區分」,不一定是「可完全計算」。

1.2 純密文攻擊,包括針對XOR改進

把分組變小,然後XOR的話,會有不錯的效果,只是這個就不是題主說的用法了。

如果演算法全部公開(固定的無理數公式+小整數隨機量(小於
2^20),或者特定無理數如Pi,
e)
,則攻擊者也可以直接使用對應的無理數序列來進行移位匹配。考慮原文是字母+可見符號序列,則總能在多項式時間內匹配到完整的、有意義的字元串。

具體來說,可以觀察空格和短詞,比如the, is, I之類的位置。而且某些信息,比如html網頁,是有固定格式開頭的,所以類似圖靈破解德軍當天的密碼機設置的方法在這裡就能使用。由於Pi等無理數十進位序列的不重複性(不考慮0.01001000100001……,即每次插入n個零和1個1,這個更好破),一旦開頭固定信息(比如

&

)被匹配上,那麼就能知道密鑰是從無理數的第幾位開始的,而後面的密文必然是用從此開始的數字序列進行加密得到。序列已知、開始位數已知,所以全部解開不是問題。

2. 效率分析

quora上有一個關於為什麼不能使用無理數代替(P)RNG的答案

Why do we need random number generators, if π, e and other irrational numbers are sources of non repeating digits?

簡單翻譯:

效率低 - Pi的展開需要花很多時間;產生器狀態無法保存--總得從第一位開始算起,無法直接取Pi的第幾位;內存消耗大--每次都得存所有的位數(編程演示的幾位知友都是使用的現成的Pi),且隨著繼續加密,這個會不停地吃內存。

通常一個大網站的每秒都有數千的新鏈接產生,考慮SSL/TLS下,用此演算法加密加密視頻流就更恐怖了……

3. 對爭議的討論

糾結的地方就在於 @劉巍然-學酥 答案中提到的:

3.1 無理數逼近/計算公式算不算密鑰的一部分?

3.1.1 如果算,即不公開計算式和固定量,那麼只要考慮這個RF/RNG的安全性和效率。(其實根本保不住這個公式。客戶端總是要分發的,所以反彙編,探針……)

關於Pi的隨機性可參考

http://www.pi314.net/eng/statistique.php

目前沒有任意隨機無理數數位分布的假設,所以最多只能假設安全,無法證明。

另外,此時這個演算法的安全性不依賴於公式,而依賴於seed。即填入公式的3/7之類。

由於是固定公式,則實際上的安全性來自於seed的產生,依舊需要一個安全的產生器(RRG)

題外話:此時,若我有能擴展一位的PRNG,就能有產生任意位的PRNG,那我為什麼要在這裡選擇一個低效的無理數計算公式?

3.1.2 如果公式不算密鑰,破解方法在1中已經提到。

3.2. 加密的方法到底是分組XOR還是分組+[0-9]

在公開公式/固定無理數的情況下不重要。


假如你發送的數據包都是1000位以內的多,那在擁有明文密文對的情況下,我要猜出前1000位的密鑰就變得非常簡單。


1.對演算法保密不可取。

2.在二進位計算機系統中無法表示如0.1這樣的簡單的十進位數字。與其有機會計算sin,ln這樣的數學符號不如使用簡單的整數加減乘法進行加/解密運算。畢竟CPU裡面是有AES,乘法運算指令的。估計科技再發展5年也無法將能夠計算精確到小數點後面32位的sin指令做到CPU裡面去。


網上搜索了一下,發現2002年有人寫了個小軟體"計算加密器",類似樓主的思路,但有區別。

結合使用簡單分析一下,先計算某個數學公式(這是密鑰,可以變的)產生與加密文件一樣長的數,對這個數加密一次(可能將作為數學式子的那個字元串當密鑰)得到真正的密鑰(不光是數字了),

用它對文件加密(異或?),最後再用一次其他塊加密或者上述某些步驟次序倒過來?

以上某些地方只是猜測,畢竟看不到源代碼。

這個小程序的主要動機估計是:

1,數學公式作為密鑰,如sin(2x)-e^0.8y

由於公式和自變數的任意性,讓破解沒辦法窮舉,有人會說泰勒展開、函數逼近之類的,那能有什麼用,

2,密鑰任意長

3,前面的高手提到了可計算性問題,這裡我想是不是可以這樣理解:

這裡重點不是對數學公式的精確計算,而是由非常有限但又有明確含義的數學公式產生固定的任意長的密鑰!這裡的數不需要精確,也不需要一定無理數或者超越數,關鍵是有限產生無限,客服one time pad的弊端。

當然我們會說這個效率太低了吧。

但測試了一下,如果沒有太高時間要求或許可以接受。

我看它跟樓主的想法有些類似,或許有所啟發?

這種方法對於通信有一定弊端,但對加密保存機密文件還是有很強的安全性吧?

本人不是學這方面的,看到前面高手的討論有些興趣剛好發現這個軟體,就發上來大家看看。

軟體下載地址如:

計算加密器下載

計算加密器官方下載

軟體介紹:密鑰產生器,文件加密器。用數學式子代替一般的密碼,以有限字元產生任意多的字元串作為密鑰,對文件進行TEA加密。無須安裝,無須註冊。可加密任何格式的文件。


沒學過密碼學,但我對加密演算法的理解是兩部分,一是密鑰的生成,二是對原始數據進行的替換運算。

替換運算的話,題主寫到的直接加已經被證明不可靠了,不過換成更細緻的運算就能解決。

從這個角度看,題主的創新不在於替換的運算,而在於密鑰的生成。

關於密鑰,我覺得這個創新某些角度看是無意義的。因為選擇pi這個無理數和我手動輸入3.1415926……是無差別的,實際上的區別在於我只需要表達一個pi就能說明我的密鑰。

換句話說,這個創新更像是一種對密鑰的「壓縮」。

當然壓縮本身也是有「加密」的意義的。更何況存儲密鑰短了,暴露的可能性相對就低了。同樣的pi,存儲完整密鑰佔用的空間可大了去了,並且表達這個無理數的方法也可以再做手腳,相當於又一層加密。

所以這一點看還是很有意義的。因為能更方便的表達密鑰,所以能夠使用更長的密鑰(不考慮性能的前提下),從而降低了被破解的可能。

當然僅從密鑰產生和運算兩個方面看一個加密演算法還是不夠的,加密策略,比如多久更換一次密碼,發送新一個數據時是繼續上次的運算還是從頭運算(說到底還是同一段密鑰使用的次數)也是很重要的。

個人理解,有錯誤或者不足請指出。

不過這都多久的題,估計也沒多少人關注了吧。


先說(扯)兩個前提。加密這個東西是特定情況下使用的偽裝策略。分析一套密碼方案可靠不可靠,我們得假設兩點:

前提一,密文是可以被干擾、獲取甚至阻斷的;

前提二,加密方和解密方在約定加密方案後,不能在這套密碼體系之外溝通相關信息。

很好理解,1.如果密文本身安全,那還加密幹嘛。2.如果能夠直接溝通,那還加密幹嘛。

回到正題。

題主的這個方法還是密碼本的思路。好比有一個密碼本,本子里寫的是一大長串隨機數作為密鑰。你有一本,對方有一本。

區別在於密碼本是有限的,題主的無理數密碼理論上是無限的

但是事實上如同 @況琪 所說,無理數加密計算成本很高,沒有大規模應用的價值。所以到這裡為止,題主的演算法就已經掛掉了。

但是還是可以搶救一下。我們把題主的想法提煉一下。題主理想的狀態是,能夠有一套約定的演算法,產生一個無限長度,並且不循環的常量,用這個常量作為加密密鑰。

這不是以前的偽隨機數嗎摔!比無理數靠譜的演算法多了去了啊摔!

好的成功被搶救了回來,使用的是這麼一套密鑰,無限不循環的常量,計算成本科學並且廉價。

現在好了,我們擁有了一個容量無限並且便於檢索的電子密碼本。理論上單次加密已經不可破解了。是不是就可以使用了呢?

懂行的都知道,這樣還是不可靠。 因為如果只是單次加密的話,為什麼不在約定加密方案的時候就把信息傳遞過去呢?何必大費周章還要搞一套加密演算法,然後驗證是否可靠?

因為我們希望這一套密碼可以長期可靠的使用

那麼問題來了,多次收發密碼,總不能每一次都從密碼本的第一位開始加密吧?這樣可是很容易被破解的哦。

當然題主也考慮到了這個問題,並提出了解決方案:

「每一次加密,往前推一段,短短的一個計算式,得出的加密能力是無限長,加密規律永不循環。」

翻譯簡化之後,我們可以理解為這樣的方案:每一次加密之後,前面的密鑰就不用了,開始用後面的。

好像很可靠。

下面就要用到我們的兩個前提了。

前提一,密文是可以被干擾、獲取甚至阻斷的;

前提二,加密方和解密方在約定加密方案後,不能在這套密碼體系之外溝通。

好吧,假設你一個100MB的重要「機密文件.rmvb」被截獲了,而好基友並沒有收到,下次解密的時候你用的是100MB以後的密鑰,而基佬,阿呸,基友還在用老密鑰啊。你們的密碼通道從此以後就掛掉了哦。(當然這裡還是有解決的辦法,比如利用反饋進行匹配修正。)

到這裡為止,基本搶救的只剩下一口氣了。

然而還是有問題。

我們總不能把100MB的數據一個個去人工對照吧。你總得讓計算機幫你去執行。密碼本的時代還有特務來盜取密碼本,現在網路這麼發達,你的演算法只要不是記在腦子裡,也還是不安全。

當然最重要的還是那麼長的密鑰串計算成本+維護成本也相當高。

然而還是可以搶救一下。參見 @劉巍然-學酥 答案中提到的非對稱演算法。

於是,密鑰也可以公開了。密碼本?給你看給你看,看了你也沒轍。


推薦閱讀:

西電只是211,為什麼密碼學排第一?
前男友分開的時候給了我一個密碼,求大神解答是什麼意思?
同態加密的實現原理是什麼?在實際中有何應用?
存在利用魔方性質的加密演算法嗎?
如何在一個月內入門密碼學?

TAG:破解 | 加密 | 計算機科學 | 資訊理論 | 密碼學 |