基于SAT求解的密码分析技术1

基于SAT求解的密码分析技术研究

国防科大计算机学院姜新文

序列密码到SAT问题（可满足性问题）SAT判定到SAT求解

转化合取范式SAT到MSPMSP求解研究及其意义同步流密码体制模型

加法流密码体制模型

序列密码到SAT问题

SAT问题即布尔表达式可满足性问题（SatisfiabilityProblem）是对一个布尔表达式进行判断，以找出是否存在一个真值指派，使得表达式的值为真。

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

真值表方法理论上可解决SAT。SAT问题是第一个被证明出来的NP完全问题。

序列密码到SAT问题

布尔方程可以转化为SAT问题

令得到

序列密码到SAT问题

有解当且仅当公式是可满足的SAT判定到SAT求解

设F(x1,x2,…,xn)是一个公式，A是判定F是否可满足的一个算法。我们用A指导求解：调用A判F是否可满足。若否则中止，若是继续。Forallxi,1≤i≤n,do

调用A判定

F\xi=1可否满足。若可满足令F=F\xi=1，否则令F=F\xi=0。

转化合取范式

我们称布尔变量或布尔变量的非为一个文字，称若干文字的析取为一个子句，称若干子句的合取为合取范式。任意公式可以转成合取范式。例如，真值表法。转换的效率有高低，甚至可能招致指数爆炸。例如，用真值表法。有方法可以将任意公式转换成合取范式，且联接词数量不超过原公式的若干倍数。

SAT到MSP

MSP问题SAT到MSP

MSP问题求解研究及其意义

研究进展证明了MSP问题的NP完全性给出了求解MSP问题的多项式时间算法实现了算法完成了大规模的、不间断的随机测试验证（已经5300万例，从2011.10.07开始）发表了一系列中文文章，会议文章。进行了一系列交流讨论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类问题：验证容易，求解困难的问题类（感觉）两类问题的关系（猜想）指数复杂性可怕吗？NPCTrivia:powerofdecimals1080=100000000000000000000000000000000000000000000000000000000000000000000000000000000numberofatomsintheuniverse1080-isasmallnumbertowritedown-isalargenumbertocountto1040=10000000000000000000000000000000000000000

numberofstepsofthefastestcomputerbeforethesundiesTrivia:powerofdecimals1040=10000000000000000000000000000000000000000

numberofstepsofthefastestcomputerbeforethesundies1040/(5000万亿*3600*24*365)>63亿亿(年)“P与NP”问题NP是否等于P对于信息安全有理论上的至关重要的意义。由于现代密码学基于NP≠P的假定，如果NP=P，现代密码学将彻底崩溃。制约了科学研究的发展。也有人说到哲学上的意义。NP=P将挑战人类的认知。甚至，NP=P直接支持唯物主义者关于世界是可知的理论。背包密码体制是Diffie和Hellman1976年提出公钥密码体制的设想后的第一个公钥密码体制，由Merkle和Hellman1978年提出。

虽然过了两年该体制即被破译，后续的体制继承了它的思想。“P与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发现NP完全问题类并证明SAT问题的NP完全性以后，该问题开始引起广泛关注。一般认为该问题有40多年的历史。2000年美国的ClayMathematicsInstitute命名了“Pvs.NP”问题，并且悬赏1百万美元应征答案。7个问题中列首位。2005年，美国著名的Science杂志公布的当前人类有待解决的前25个难题中，PvsNP问题排名第19位。千年计划人们至今未能解决Pvs.NP问题。在研究Pvs.NP问题过程中，人们甚至还经历了起先看起来很有希望，但多少年后又推翻之前所做的全部工作的痛苦和无赖。至今人们甚至未能找到一个有希望的方向。似乎现有的技术在证明P≠NP或者P=NP上都变得束手无策。有学者认为解决Pvs.NP问题依赖于新的理论的产生，有学者认为Pvs.NP问题独立于现有的公理系统，甚至其本身就不能够证明或者证否。“P与NP”问题“P与NP”问题在2002年对100个研究者的调查问卷中，有61人相信答案是P≠NP，有9人相信答案是P=NP，有22人不确定，而8人相信该问题可能和现在所接受的公理独立，所以不可能证明或证否。2010年8月，美国惠普实验室的数学家维奈·迪奥拉里卡宣布证明了NP≠P，引起世界关注和欢腾。全世界许多媒体都迅速转载了这个消息。但是，人们很快发现了他的证明中的致命错误。2011年8月，另一个NP≠P的文章被否定。关于NP=P的研究比较多的被采用的一种思路：首先利用一个已知的NP-完全问题，或者自己提出一个新的问题并证明其具有NP完全性质。然后试图给出求解该NP-完全问题的多项式时间算法，最后验证算法的正确性及分析算法的时间复杂性。MSP问题求解研究及其意义

研究进展证明了MSP问题的NP完全性给出了求解MSP问题的多项式时间算法实现了算法完成了大规模的、不间断的随机测试验证（已经5300万例，从2011.10.07开始）发表了一系列中文文章，会议文章。进行了一系列交流讨论MSP问题能