基于SAT求解的密碼分析技術(shù)1

基于SAT求解的密碼分析技術(shù)研究

國防科大計算機學(xué)院姜新文

序列密碼到SAT問題（可滿足性問題）SAT判定到SAT求解

轉(zhuǎn)化合取范式SAT到MSPMSP求解研究及其意義同步流密碼體制模型

加法流密碼體制模型

序列密碼到SAT問題

SAT問題即布爾表達式可滿足性問題（SatisfiabilityProblem）是對一個布爾表達式進行判斷，以找出是否存在一個真值指派，使得表達式的值為真。

例：（（p∧q）∨（～p∧～q））∧r）∨（（（p∧～q）∨（～p∧q））∧～r）

真值表方法理論上可解決SAT。SAT問題是第一個被證明出來的NP完全問題。

序列密碼到SAT問題

布爾方程可以轉(zhuǎn)化為SAT問題

令得到

序列密碼到SAT問題

有解當(dāng)且僅當(dāng)公式是可滿足的SAT判定到SAT求解

設(shè)F(x1,x2,…,xn)是一個公式，A是判定F是否可滿足的一個算法。我們用A指導(dǎo)求解：調(diào)用A判F是否可滿足。若否則中止，若是繼續(xù)。Forallxi,1≤i≤n,do

調(diào)用A判定

F\xi=1可否滿足。若可滿足令F=F\xi=1，否則令F=F\xi=0。

轉(zhuǎn)化合取范式

我們稱布爾變量或布爾變量的非為一個文字，稱若干文字的析取為一個子句，稱若干子句的合取為合取范式。任意公式可以轉(zhuǎn)成合取范式。例如，真值表法。轉(zhuǎn)換的效率有高低，甚至可能招致指數(shù)爆炸。例如，用真值表法。有方法可以將任意公式轉(zhuǎn)換成合取范式，且聯(lián)接詞數(shù)量不超過原公式的若干倍數(shù)。

SAT到MSP

MSP問題SAT到MSP

MSP問題求解研究及其意義

研究進展證明了MSP問題的NP完全性給出了求解MSP問題的多項式時間算法實現(xiàn)了算法完成了大規(guī)模的、不間斷的隨機測試驗證（已經(jīng)5300萬例，從2011.10.07開始）發(fā)表了一系列中文文章，會議文章。進行了一系列交流討論MSP問題能夠決定NP=Pornot

Z-HalgorithmtosolveMSP1.Foralle∈E,weuseoperator2togenerateR(e)directly2.Forl=1toL-12.1Forall<u,v,l>ofstagel,callChange(R(u,v,l))to modifyR(u,v,l)2.2Forallvofstagel,E(v)←Comp(E(v),v,R(E))2.3Forall<a,b,k>∈E，k≤l,executethefollowingtwo steps: R(a,b,k)[k+1:l]←R(a,b,k)∩Comp(E(v),v,R(E)) R(a,b,k)←R(a,b,k)3.Repeatstep2untilnoR(u,v,l)inR(E)={R(e)|e∈E}willaachangeanymore4.IfComp(E(D),D,R(E))≠?,weclaimtheexistenceofaaasimplepathinG.Otherwise,weclaimthatthereisnoaasimplepathinG“P與NP”問題P類問題：驗證容易，求解容易的問題類NP類問題：驗證容易，求解困難的問題類（感覺）兩類問題的關(guān)系（猜想）指數(shù)復(fù)雜性可怕嗎？NPCTrivia:powerofdecimals1080=100000000000000000000000000000000000000000000000000000000000000000000000000000000numberofatomsintheuniverse1080-isasmallnumbertowritedown-isalargenumbertocountto1040=10000000000000000000000000000000000000000

numberofstepsofthefastestcomputerbeforethesundiesTrivia:powerofdecimals1040=10000000000000000000000000000000000000000

numberofstepsofthefastestcomputerbeforethesundies1040/(5000萬億*3600*24*365)>63億億(年)“P與NP”問題NP是否等于P對于信息安全有理論上的至關(guān)重要的意義。由于現(xiàn)代密碼學(xué)基于NP≠P的假定，如果NP=P，現(xiàn)代密碼學(xué)將徹底崩潰。制約了科學(xué)研究的發(fā)展。也有人說到哲學(xué)上的意義。NP=P將挑戰(zhàn)人類的認(rèn)知。甚至，NP=P直接支持唯物主義者關(guān)于世界是可知的理論。背包密碼體制是Diffie和Hellman1976年提出公鑰密碼體制的設(shè)想后的第一個公鑰密碼體制，由Merkle和Hellman1978年提出。

雖然過了兩年該體制即被破譯，后續(xù)的體制繼承了它的思想?！癙與NP”問題whatisin

NP?Mathematician:

Givenastatement,findaproofScientist:Givendataonsomephenomena,

findatheoryexplainingit.Engineer:Givenconstraints(size,weight,energy)

find

adesign(bridge,medicine,phone)If

P=NP,thesehavefast,automaticfinder“P與NP”問題1970年，S.A.Cook發(fā)現(xiàn)NP完全問題類并證明SAT問題的NP完全性以后，該問題開始引起廣泛關(guān)注。一般認(rèn)為該問題有40多年的歷史。2000年美國的ClayMathematicsInstitute命名了“Pvs.NP”問題，并且懸賞1百萬美元應(yīng)征答案。7個問題中列首位。2005年，美國著名的Science雜志公布的當(dāng)前人類有待解決的前25個難題中，PvsNP問題排名第19位。千年計劃人們至今未能解決Pvs.NP問題。在研究Pvs.NP問題過程中，人們甚至還經(jīng)歷了起先看起來很有希望，但多少年后又推翻之前所做的全部工作的痛苦和無賴。至今人們甚至未能找到一個有希望的方向。似乎現(xiàn)有的技術(shù)在證明P≠NP或者P=NP上都變得束手無策。有學(xué)者認(rèn)為解決Pvs.NP問題依賴于新的理論的產(chǎn)生，有學(xué)者認(rèn)為Pvs.NP問題獨立于現(xiàn)有的公理系統(tǒng)，甚至其本身就不能夠證明或者證否。“P與NP”問題“P與NP”問題在2002年對100個研究者的調(diào)查問卷中，有61人相信答案是P≠NP，有9人相信答案是P=NP，有22人不確定，而8人相信該問題可能和現(xiàn)在所接受的公理獨立，所以不可能證明或證否。2010年8月，美國惠普實驗室的數(shù)學(xué)家維奈·迪奧拉里卡宣布證明了NP≠P，引起世界關(guān)注和歡騰。全世界許多媒體都迅速轉(zhuǎn)載了這個消息。但是，人們很快發(fā)現(xiàn)了他的證明中的致命錯誤。2011年8月，另一個NP≠P的文章被否定。關(guān)于NP=P的研究比較多的被采用的一種思路：首先利用一個已知的NP-完全問題，或者自己提出一個新的問題并證明其具有NP完全性質(zhì)。然后試圖給出求解該NP-完全問題的多項式時間算法，最后驗證算法的正確性及分析算法的時間復(fù)雜性。MSP問題求解研究及其意義

研究進展證明了MSP問題的NP完全性給出了求解MSP問題的多項式時間算法實現(xiàn)了算法完成了大規(guī)模的、不間斷的隨機測試驗證（已經(jīng)5300萬例，從2011.10.07開始）發(fā)表了一系列中文文章，會議文章。進行了一系列交流討論MSP問題能