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

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

國(guó)防科大計(jì)算機(jī)學(xué)院姜新文

序列密碼到SAT問(wèn)題（可滿(mǎn)足性問(wèn)題）SAT判定到SAT求解

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

加法流密碼體制模型

序列密碼到SAT問(wèn)題

SAT問(wèn)題即布爾表達(dá)式可滿(mǎn)足性問(wèn)題（SatisfiabilityProblem）是對(duì)一個(gè)布爾表達(dá)式進(jìn)行判斷，以找出是否存在一個(gè)真值指派，使得表達(dá)式的值為真。

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

真值表方法理論上可解決SAT。SAT問(wèn)題是第一個(gè)被證明出來(lái)的NP完全問(wèn)題。

序列密碼到SAT問(wèn)題

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

令得到

序列密碼到SAT問(wèn)題

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

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

調(diào)用A判定

F\xi=1可否滿(mǎn)足。若可滿(mǎn)足令F=F\xi=1，否則令F=F\xi=0。

轉(zhuǎn)化合取范式

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

SAT到MSP

MSP問(wèn)題SAT到MSP

MSP問(wèn)題求解研究及其意義

研究進(jìn)展證明了MSP問(wèn)題的NP完全性給出了求解MSP問(wèn)題的多項(xiàng)式時(shí)間算法實(shí)現(xiàn)了算法完成了大規(guī)模的、不間斷的隨機(jī)測(cè)試驗(yàn)證（已經(jīng)5300萬(wàn)例，從2011.10.07開(kāi)始）發(fā)表了一系列中文文章，會(huì)議文章。進(jìn)行了一系列交流討論MSP問(wèn)題能夠決定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”問(wèn)題P類(lèi)問(wèn)題：驗(yàn)證容易，求解容易的問(wèn)題類(lèi)NP類(lèi)問(wèn)題：驗(yàn)證容易，求解困難的問(wèn)題類(lèi)（感覺(jué)）兩類(lèi)問(wèn)題的關(guān)系（猜想）指數(shù)復(fù)雜性可怕嗎？NPCTrivia:powerofdecimals1080=100000000000000000000000000000000000000000000000000000000000000000000000000000000numberofatomsintheuniverse1080-isasmallnumbertowritedown-isalargenumbertocountto1040=10000000000000000000000000000000000000000

numberofstepsofthefastestcomputerbeforethesundiesTrivia:powerofdecimals1040=10000000000000000000000000000000000000000

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

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

NP?Mathematician:

Givenastatement,findaproofScientist:Givendataonsomephenomena,

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

find

adesign(bridge,medicine,phone)If

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

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