检索结果-南通市图书馆

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

基于minisat的多项式方程组求解实现

重庆理工大学学报（自然科学） 2015年第6期29卷 75-81页

作者：邹湘景彭伟国防科技大学计算机学院长沙410073

在许多分析验证研究中,经常要对问题中的多项式组进行求解。当多项式方程组规模较大时,求解比较困难,大大限制了分析研究的效率。针对该问题设计了一种算法,将具有一定格式的多项式转化为合取范式形式,使多项式求解问题转化为SAT求解问... 详细信息

在许多分析验证研究中,经常要对问题中的多项式组进行求解。当多项式方程组规模较大时,求解比较困难,大大限制了分析研究的效率。针对该问题设计了一种算法,将具有一定格式的多项式转化为合取范式形式,使多项式求解问题转化为SAT求解问题。利用SAT求解器Mini Sat对二元域上的多项式组进行求解,使得密码分析过程更加高效。实验结果表明:该算法能正确地将多项式进行转化,并能快速利用Mini Sat求出结果。

关键词：可满足性问题 minisat 多项式合取范式

System Design and Implementation of Intelligent Fire Engine Path Planning based on SAT Algorithm

在线全文

学校读者我要写书评

暂无评论

International Journal of Technology Management 2016年第5期 67-69页

作者： CAI Li-sha ZENG Wei-peng HAN Bao-ru Hainan Software Profession Institute Qionghai Hainan 571400China

In this paper, in order to make intelligent fi re car complete autonomy path planning in simulation map. Proposed system design of intelligent fi re car path planning based on SAT. The system includes a planning module, a communication module, a control module. Control module via the communication module upload the initial state and the goal state to planning module. Planning module solve this planning solution,and then download planning solution to control module, control the movement of the car fi re. Experiments show this the system is tracking short time, higher planning effi ciency.

关键词： Intelligent fi re engine SAT algorithm Path planning system minisat solver

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

基于子句文字长度动态约束的变量消除算法

计算机科学与探索 2014年第11期8卷 1314-1323页

作者：邓晓瑶冯志勇饶国政王鑫天津大学计算机科学与技术学院天津300072 天津市认知计算与应用重点实验室天津300072

变量消除算法作为一种重要的预处理算法已经应用于多种预处理器中。对比研究了在不同约束条件下,变量消除算法对简化性能和求解性能的影响,提出了基于子句文字长度动态约束的变量消除算法。该算法只允许当变量分解后的子句文字长度比原... 详细信息

变量消除算法作为一种重要的预处理算法已经应用于多种预处理器中。对比研究了在不同约束条件下,变量消除算法对简化性能和求解性能的影响,提出了基于子句文字长度动态约束的变量消除算法。该算法只允许当变量分解后的子句文字长度比原有子句文字少时,执行变量消除替换操作。在此基础上实现了一个基于Mini Sat开源代码的可满足性问题预处理器Mini Sat BFS。实验结果表明,与现有的基于子句数目约束的算法相比,新算法不仅降低了子句、变量和文字的数目,而且缩短了预处理过程和求解过程的时间消耗。更重要的是,改进后的算法在限定时间内可以求解更多的可满足性问题。

关键词：可满足性问题变量分解消除 minisat

在线全文

学校读者我要写书评

暂无评论

可满足性问题的预处理策略研究与分析

可满足性问题的预处理策略研究与分析

作者：邓晓瑶天津大学

学位级别：硕士

可满足性问题（即SAT问题）是第一个被证明的经典NP问题。人们一直致力于如何在有限的时间求解可满足性问题。随着现实世界中可满足性问题的规模逐渐增长,预处理技术已经逐渐受到重视。由于其良好的简化效果,变量消除算法已经应用于多... 详细信息

可满足性问题（即SAT问题）是第一个被证明的经典NP问题。人们一直致力于如何在有限的时间求解可满足性问题。随着现实世界中可满足性问题的规模逐渐增长,预处理技术已经逐渐受到重视。由于其良好的简化效果,变量消除算法已经应用于多种预处理器中。作为一种轻量级预处理技术,变量消除算法的简化效果与其消除过程中的约束条件有着直接联系。为了进一步提高和优化变量消除算法的预处理性能,本文对比研究了在不同的约束条件下变量消除算法的简化性能以及简化后的CNF实例的求解效果,同时设计了一种基于子句文字长度动态约束的变量消除算法。与分解前的子句文字长度相比,只有当分解后的子句集合的文字长度减少时,该算法完成变量消除替换过程。为了减少变量消除算法中无价值计算,该算法引入了动态约束机制,大大缩短了预处理时间,进一步提高简化性能。本文在该算法的基础上,基于Mini Sat的开源代码实现了一个可满足性问题的预处理器minisat BFS。除了通过常规的性能指标来对比分析两种不同约束条件下变量消除算法的预处理性能。本文利用复杂网络的统计分析方法,将CNF实例转化为复杂网络表示,从复杂网络的整体和局部两个维度来分析简化前后的CNF实例,评估现有预处理算法的简化性能。最终的实验结果表明,与现有的基于子句数目约束的算法相比,新的算法不仅降低了CNF实例的规模,而且缩短了预处理过程和求解过程的时间消耗。更重要的是,改进后的算法在限定的时间内可以求解更多的可满足性问题,具备显著的性能优势。

关键词：可满足性问题变量消除算法 minisat

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

代数分析及其对若干轻量级分组密码的应用

代数分析及其对若干轻量级分组密码的应用

作者：葛十景上海交通大学

学位级别：硕士

密码分析学与密码编码学作为密码学的两个分支,有着矛和盾一样的关系,它们一直在相互促进对方的发展。代数分析是近年来密码分析学的研究热点之一,代数分析方法的研究对于密码分析学和密码编码学都有重要意义。本文首先归纳总结了针对... 详细信息

密码分析学与密码编码学作为密码学的两个分支,有着矛和盾一样的关系,它们一直在相互促进对方的发展。代数分析是近年来密码分析学的研究热点之一,代数分析方法的研究对于密码分析学和密码编码学都有重要意义。本文首先归纳总结了针对分组密码算法的代数分析过程和方法。代数分析过程包括构建描述加密过程的代数方程组和求解代数方程组以恢复密钥。构建方程组的过程是通过将S盒的代数描述扩展成为整个加密过程的代数描述。本文针对典型的SPN型分组密码算法给出了一种中间相遇式方程构造方法。该方法可以在不提高方程次数的前提下,有效地减少中间变量的使用。求解代数方程组的方法主要有基于Gr?bner基的求解方法、基于可满足问题求解的方法等。在代数攻击中引入差分技术,可以构造出新的攻击形式,有效地提高攻击效率。本文介绍了差分在代数攻击中的各种应用形式,并且通过引入差分S盒将代数攻击扩展到不同的攻击场景中。PRINTCipher算法是2010年提出的一种针对印刷电路的新的轻量级分组密码算法。本文对PRINTCipher中的代数方程做了详细分析,使用minisat攻击工具对低轮PRINTCipher加密算法进行了攻击实验,结果表明完整的PRINTCipher由于轮数较多可以有效地抵御代数分析。本文还介绍了针对PRESENT分组密码算法的代数攻击。采用S盒的表达式形式,通过使用相遇式构建方法,构建出多轮PRESENT加密中的代数方程组。文中还对简化的PRESENT算法进行了攻击实验。采用minisat作为攻击过程中的求解工具,对4轮、6轮PRESENT加密进行实际攻击。可以在一分钟之内恢复4轮加密的所有密钥,数小时内恢复6轮加密的密钥。并且,通过引入差分思想,将有效攻击轮数提高到8轮。

关键词：分组密码代数分析 S盒 Gr?bner基可满足问题差分技术 PRINTCipher算法 PRESENT算法 minisat

SAT全解算法的研究及其在Trivium和Lex分析中的应用

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

SAT全解算法的研究及其在Trivium和Lex分析中的应用

作者：戴江海解放军信息工程大学

学位级别：硕士

近二十余年来，高效实用的SAT算法一直是人工智能集成电路图论等诸多领域中研究的热点自2007年SAT算法被用于多元非线性方程组的求解之后，它在密码分析领域中的应用也开始被人关注，并在对于一些密码算法如分组密码DES Keeloq，序列密... 详细信息

近二十余年来，高效实用的SAT算法一直是人工智能集成电路图论等诸多领域中研究的热点自2007年SAT算法被用于多元非线性方程组的求解之后，它在密码分析领域中的应用也开始被人关注，并在对于一些密码算法如分组密码DES Keeloq，序列密码Crypto-1HiTag2和Trivium的简化变种Bivium等的直接或间接的代数攻击中，都得到了非常好的结果然而，一般的SAT求解器只能得出方程组的一个解，无法应对方程组有多个解的情况目前SAT全解算法的研究主要应用于电子设计自动化领域，在国内外的成果都不多，并且大多是基于电路表示，无法直接应用于密码分析本文中给出了一种针对于求解多元非线性方程组的SAT全解算法，并说明了其正确性和完备性在方程组的解个数较多的情况下，该算法平均求出每个解的时间将远低于使用经典SAT求解器求出一个解的时间 2008年Alex Biryukov等人使用Gr bner基方法计算出了序列密码Trivium初始化过程中111拍和112拍的可滑动对，并估计找出115拍的可滑动对需要64天使用本文中的SAT全解算法来计算Trivium的可滑动对，在90分钟内即可找出120拍的所有可滑动对 Vesselin Velichkov等人于2010年对基于SR(10,2,2,4)的Lex(2,2,4)进行了可以恢复密钥的直接代数攻击而在此攻击中，Lex的密钥流生成过程只用到了两组子密钥利用SAT全解算法对使用完整的10组子密钥的Lex(10,2,2,4)进行代数攻击，可以在15分钟左右恢复密钥 Jianyong Huang等人在2010年提出一种对Lex的差分fault分析，要求在内部状态中嵌入40个fault，恢复密钥所需的时间复杂度为将此方法进行进一步推进之后，只需20个fault便可以直接恢复密钥结合代数攻击的思想，在嵌入16个fault之后，利用SAT全解算法在6秒左右便可以恢复密钥

关键词： ALL-SAT minisat 代数攻击 Trivium Lex 可滑动对差分fault分析

Trivium算法的Fault Cube攻击与可滑动对研究

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

Trivium算法的Fault Cube攻击与可滑动对研究

作者：曾文解放军信息工程大学

学位级别：硕士

Trivium是eSTREAM计划最终推荐的首选算法,作为序列密码设计领域一种划时代设计方式的杰出代表, Trivium引起了密码学界的高度关注,近几年来一直是密码领域,特别是密码分析领域的研究热点. Trivium的设计将循环更新内部状态和非线性反... 详细信息

Trivium是eSTREAM计划最终推荐的首选算法,作为序列密码设计领域一种划时代设计方式的杰出代表, Trivium引起了密码学界的高度关注,近几年来一直是密码领域,特别是密码分析领域的研究热点. Trivium的设计将循环更新内部状态和非线性反馈进行了巧妙的结合,使得其表面上看来结构简单,而事实上安全性却非常高.这种崭新的序列密码设计方式充分认识到了早期线性密码设计的不足,吸收了分组密码的一些优秀的设计思想,同时还充分考虑到了算法抗现有攻击方法的能力,特别是抗代数攻击、相关攻击和差分分析的能力.从2005年Trivium算法提出至今,虽然一些Trivium的变种算法得到了有效的攻击,但是完整Trivium算法的安全性依然不减.本文主要在前人工作的基础上继续对Trivium算法进行了如下三个方面的研究: 1.基于cube攻击和fault分析的方法,本文创新性地提出了fault cube攻击的方法,利用在合适的位置嵌入fault的方式将一些初始化拍数退化的Trivium变种算法截成初始化拍数相对较少的两部分,然后充分利用cube攻击对两个部分分别进行攻击,最后通过fault位置将两个部分的cube攻击合并为对整体的一个攻击.该方法利用fault分析对cube攻击进行了有效的改进,可以对1056拍以下初始化的Trivium变种算法进行有效攻击,攻击的计算复杂度不超过O(253). 2.在Trivium的设计中存在一种有趣且很有意义的现象,某些不同的key/IV对可以产生仅相差若干比特移位的密钥流,从这个意义上来说,这些不同的key/IV对其实是平移等价的,本文将其称为可滑动key/IV对.基于SAT方法有效求解描述可滑动key/IV对的非线性方程,本文找到了相差195比特移位以内的多个可滑动key/IV对.与已有结果相比,本文找到的可滑动key/IV对的数量和寻找效率均有很大提高. ***的选择IV统计分析一直是早期Trivium分析中研究的热点之一,经过众多密码学者的拓展和完善,目前已形成了一种典型的选择IV统计分析框架,但是在该框架中考虑的仅仅是单个密钥流比特代数正规型的相关密码学性质.本文在此框架的基础上考虑一串相对较长的密钥流比特的代数正规型的密码学性质,提出了一种选择IV统计分析的新框架,对目前的Trivium选择IV统计分析结果进行了有效的改进.

关键词： Trivium cube攻击 fault嵌入 minisat SAT 可滑动对密码分析

利用一种SAT问题全解算法求Trivium可滑动对

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

信息工程大学学报 2012年第1期13卷 1-7页

作者：戴江海戚文峰信息工程大学信息工程学院河南郑州450002

Trivium是进入到eSTREAM计划最终方案的一个序列密码体制,而在其初始化过程中存在可滑动对。SAT求解器可以有效地求解非线性方程组,然而一般的SAT求解器在求出一个解之后便会结束。对minisat求解器中的算法进行改进,使之可以得出方程所... 详细信息

Trivium是进入到eSTREAM计划最终方案的一个序列密码体制,而在其初始化过程中存在可滑动对。SAT求解器可以有效地求解非线性方程组,然而一般的SAT求解器在求出一个解之后便会结束。对minisat求解器中的算法进行改进,使之可以得出方程所有解。将改进的算法应用于Trivium中可滑动对的求解,得到了初始化拍数从111到120的所有可滑动对。相比于使用Grbner基方法,求解效率有了极大的提高。

关键词： SAT问题 minisat 序列密码 Trivium 可滑动对

基于Python的电路故障诊断系统通信模块的实现

在线全文

学校读者我要写书评

暂无评论

电子制作 2014年第1X期22卷 132-133页

作者：蔡莉莎林尔敏曾维鹏海南软件职业技术学院电子工程系海南软件职业技术学院软件工程系海南琼海571400

本文以与门电路为例,介绍电路故障诊断系统通信模块的实现方法。利用下位机将与门电路系统所构建CNF形式描述的系统行为描述,组件正常行为描述以及51单片机获取观测值以此建立的观测值描述文件上传到上位机。上位机采用Python语言实现... 详细信息

本文以与门电路为例,介绍电路故障诊断系统通信模块的实现方法。利用下位机将与门电路系统所构建CNF形式描述的系统行为描述,组件正常行为描述以及51单片机获取观测值以此建立的观测值描述文件上传到上位机。上位机采用Python语言实现上下位机之间的串口通信,将所接收数据输入运行在Liunx操作系统下的minisat求解器求解三元组,并将诊断结果反馈下位机。实验结果表明基于Python的通信模块可以很好的实现51单片机与PC机之间的串口通信。

关键词：电路故障诊断系统 minisat Python 串口通信