随机背包公钥密码的分析与改进

针对随机背包公钥密码方案,提出一种私钥恢复攻击方法.发现Wang等人所构造的随机背包公钥方案实际上是隐含使用了一个特殊的超递增背包.通过使用普通超递增背包代替该特殊超递增背包,将超递增背包隐藏在随机选择的背包中,对原方案进行了改进,提出一种新的基于中国剩余定理的背包公钥密码方案.改进后的方案消除了原方案存在的设计缺陷,能够抵抗针对原方案提出的格规约攻击、低密度攻击以及shamir攻击.     

对超混沌系统的图像加密算法安全性的改进*

针对Gao等人提出的一种基于超混沌系统的图像加密算法的安全性缺陷,提出了一种改进的图像加密算法,该算法利用超混沌产生的超混沌序列对明文不同的像素点采用不同的方式进行加密。仿真实验结果表明,改进算法加密效果良好,加密效率更高,在保留原算法优点的基础上克服了其不能抵御选择明文攻击和选择密文攻击的缺陷,具有更高的安全性。     

pi序列的似混沌特性及其在图像加密中的应用

提出一新的概念——pi序列,并利用非线性时间序列分析方法揭示pi序列的似混沌特性。然后提出一种基于pi序列的图像加密算法,对数字图像分别进行像素位置和像素值扰乱。最后图像加密算法的安全性分析结果表明此加密算法很强地抵抗统计攻击与差分攻击。     

基于Hash函数和多混沌系统的图像加密算法

为了实现对数字图像的有效保护,提出一种基于Hash函数和多混沌系统的图像加密算法.该算法通过像素置乱、灰度置乱及灰度扩散实现图像加密.在像素置乱过程中,采用Lorenz混沌系统和Hash函数构造置乱序列,而在灰度置乱过程中,基于多表代替密码理论和Logistic混沌系统,提出了一种图像灰度置乱方法,并对灰度进行扩散.理论分析和仿真实验结果表明,该算法具有高的安全性能,在抵抗统计攻击、差分攻击、穷举攻击和选择明文攻击方面都具有良好的性能.     

结合超混沌序列和移位密码的数字图像加密算法

为了实现对数字图像信息的有效保护和提高加密图像的抗噪声攻击等能力,提出基于超混沌序列和移位密码的数字图像加密算法.首先对Chen超混沌序列进行改进,使Chen超混沌序列的随机性能提高;然后用改进的Chen超混沌序列的一个序列加密像素位置,利用移位密码结合另外的序列对像素值进行扩散和混淆,从而实现像素位置和像素值双重加密.理论分析与实验结果表明,该算法具有较好的加密效果和较强的抗剪切攻击能力,并且可以抵御穷举攻击和统计分析攻击;与基于异或XOR操作的加密算法相比,具有更强的抗噪声和抗JPEG压缩攻击能力,可以将加密图像以JPEG格式保存和传输.     

由向量乘积生成的多背包公钥体制密码算法

分析了传统背包密码系统的算法,设计并实现了利用超递增序列与随机向量进行乘积生成普通背包序列的方法.该算法设计了26组背包序列,对加密时系统利用用户口令串生成背包编号的三种方法进行了讨论.结果显示,该算法速度快,可靠性高,可以保证数据的安全性.     

一种新的基于超混沌映射的图像融合加密算法

为了提高图像加密算法的安全性和加密效率,提出一种新的基于超混沌映射的图像融合加密算法。首先,利用Chen超混沌系统产生四条混沌序列,并对这四条混沌序列进行取小数部分、矩阵相乘及取索引值等变形处理;然后分别利用变形后的混沌序列对原始图像和密钥图像进行像素的位置置乱,接着用交换位平面和按位取反操作来扰乱其像素值;最后,执行加运算可得到加密图像。置乱程度和安全性分析表明,该图像融合加密算法具有较好的加密效果,较大的密钥空间和较强的密钥灵敏性,且可抗抵抗穷举攻击和统计攻击。     

一种基于复合离散混沌系统的对称图像加密算法

提出了一种基于复合离散混沌系统的对称图像加密算法。在该算法中，通过复合离散混沌系统隐藏了混沌序列产生时所经历的迭代次数，来避免常用的基于符号动力学的密码分析。理论分析和仿真实验表明，本文提出的算法具有较高的安全枉能，特别是在统计攻击、差分攻击和选择明文攻击能力方面具有很好的抗攻击性能。     

基于复合离散混沌系统的图像加密算法

提出一种基于复合离散混沌系统的图像置乱加密算法,克服普通混沌量化图像置乱算法时间复杂度较高和需要对混沌轨道的概率分布有先验知识等缺陷。该算法利用复合离散混沌系统产生混沌序列,基于排序变换设计一个混沌图像置乱算法。理论分析和仿真实验表明,该算法具有较高的安全保密性能和抗攻击性能。     

一种基于四维超混沌系统的数字图像加密算法

基于低维混沌系统的数字图像加密算法存在密钥空间小、安全性不高等问题。为此,在三维Lorenz系统的基础上,通过增加变量w使其成为四维微分方程组,并引入一个非线性项来增强系统运动的复杂性,由此构造一个四维超混沌系统。基于该系统提出一种新的数字图像加密算法。Lyapunov指数的计算结果和系统运动轨迹的仿真结果验证了系统的超混沌性。安全性分析和测试结果表明,新算法对密钥非常敏感,具有较好的扩散性及安全性,能抵抗蛮力攻击、已知明文攻击和选择明文攻击。     

Approximate algorithms for some generalized knapsack problems

In this paper we construct approximate algorithms for the following problems: integer multiple-choice knapsack problem, binary multiple-choice knapsack problem and multi-dimensional knapsack problem. The main result can be described as follows: for every ε 0 one can construct a polynomial-time algorithm for each of the above problems such that the ratio of the value of the objective function by this algorithm and the optimal value is bounded below by 1 - ε.     

Analysis of integer programming algorithms with L-partition and unimodular transformations

We study algorithms for solving integer linear programming problems, in particular, set packing and knapsack problems. We pay special attention to algorithms of lexicographic enumeration of L-classes and their combinations with other approaches. We study the problems of using unimodular transformations in order to improve the structure of the problems and speed up the algorithms. We construct estimates on the number of iterations for the algorithms that take into account the specific structure of the problems in question. We also show experimental results.     

求解大规模0-1背包问题的主动进化遗传算法

针对遗传算法求解大规模0-1背包问题中存在的不足，将定向变异机制引入到遗传算法中，提出了基于主动进化遗传算法的0-1背包问题求解算法。该算法利用概率编码方案对种子个体进行编码，每代种群中的个体通过对该代种子个体进行测度而产生，用于定向变异的诱变因子将参与种子个体的进化。实验结果表明，该算法具有较好的全局寻优能力和执行效率。     

基于Paillier算法的智能电网数据聚合与激励方案

针对智能电网数据聚合和激励存在的隐私泄露问题,基于Paillier算法设计智能电网数据聚合和激励方案。采用超递增序列构造多维数据,并利用同态Paillier密码技术加密结构化数据。在云计算中心直接对用户与电网管理中心之间的密文数据进行聚合,添加与密钥相关的哈希运算消息认证码防止密文数据被篡改,并由电网管理中心解密后获得原始数据的聚合结果。此外,通过引入区块链和环签名实现高效匿名的光伏发电奖励和电网管理中心与用户之间的双向匿名,利用批验证算法降低计算成本。分析结果表明,在保障数据完整性和用户匿名性前提下,该方案可实现高效安全的智能电网数据聚合和激励。     

收缩背包问题的并行分枝界限算法

收缩背包问题（collapsing knapsack problem,CKP)是0－1背包问题的变体,其中背包的容量为所装物品数量的非增函数,针对并行计算的需求,在对CKP问题分解的基础上,给出了求解每个子问题的权分枝界限算法,提出了基于MIMD－DM的收缩背包问题的并行分枝界限算法;并在曙光1000上设计和实现了该算法,以消息传递方式来解决子算法最优解的播送问题,同时给出了子问题的求解顺序,讨论了问题求解过程中的递归深度和系统的通信开销对加速比曲线的影响。     

重新认识背包公钥密码的安全性

针对背包密码屡被破译的局面,分析了其中原因。指出背包公钥序列是由初始序列变换而来的,初始序列由易解背包形成,存在着冗余度,因此背包公钥序列不可能是完全随机的,利用这些冗余度是破译成功的必要条件,目前大多数被破译的背包密码只使用了模乘运算等混乱技术,这不足以隐藏初始序列的冗余度。为此引入了加法扩散技术,以分散初始序列的冗余度,使攻击者在破译过程中难以利用,举实例说明了项内扩散和项间扩散两种扩散技术。分析表明,运用扩散技术后,能抵御目前已知的攻击方法。     

求解0-1背包问题的二进制狮群算法

针对传统二进制群智能算法求解0-1背包问题易陷入局部最优、收敛速度慢的缺点,提出一种新的解决离散空间问题的二进制狮群算法BLSO。二进制狮群算法对狮王、母狮和幼狮的位置重新定义,引入反置运算、移动算子和学习算子建立全新的位置转移方式和局部搜索规则;加入贪心策略进行解的可行化处理和充分利用,增强局部搜索能力,进一步提高收敛速度。对9个典型的0-1背包算例进行仿真实验,实验结果表明,该算法不仅可以有效求解0-1背包问题,而且还能够以较快的速度搜索到精度较高的次优解甚至全局最优解,具有较好的稳定性;同时,对高维背包问题的求解与参考算法相比,在寻优时间和精度上更具优势。     

改进果蝇优化算法在多目标搜索的应用

在实际工程优化问题中多数问题是多目标优化问题,多目标优化问题一直以来就是智能算法的研究热点。提出一种改进的果蝇优化算法,将其应用在多目标搜索领域,并成功使用该算法解决了一种多目标背包问题。算法在基本果蝇优化算法的基础上采用分群策略和动态半径,在群A中从种群位置开始以动态半径探索新的可行解,在群B中则通过非支配个体之间的交叉操作进行密集搜索。果蝇种群的位置在每一轮迭代产生的非劣解集中进行选取,提高了算法的收敛速度。通过在多个数据集下进行测试,并和粒子群算法、NSGA-2做了对比实验,最终结果显示使用该算法在特定条件下能取得较好的搜索效果,证明了使用果蝇优化算法解决多目标问题的可行性。     

对二元一次不定方程背包方案的格攻击

研究分析背包密度大于0.9408的背包密码方案的安全性非常重要. 针对基于二元一次不定方程的难解函数的新型背包公钥密码算法, 由公钥和密文构造一个格来攻击该方案, 通过采用NTL库验证上述格攻击算法的效率, 从而证明了该攻击方法的有效性. 进而说明此新型背包公钥密码体制是不安全的.     

Reoptimization in Lagrangian methods for the 0-1 quadratic knapsack problem

The 0-1 quadratic knapsack problem consists of maximizing a quadratic objective function subject to a linear capacity constraint. To exactly solve large instances of this problem with a tree search algorithm (e.g., a branch and bound method), the knowledge of good lower and upper bounds is crucial for pruning the tree but also for fixing as many variables as possible in a preprocessing phase. The upper bounds used in the best known exact approaches are based on Lagrangian relaxation and decomposition. It appears that the computation of these Lagrangian dual bounds involves the resolution of numerous 0-1 linear knapsack subproblems. Thus, taking this huge number of resolutions into account, we propose to embed reoptimization techniques for improving the efficiency of the preprocessing phase of the 0-1 quadratic knapsack resolution. Namely, reoptimization is introduced to accelerate each independent sequence of 0-1 linear knapsack problems induced by the Lagrangian relaxation as well as the Lagrangian decomposition. Numerous numerical experiments validate the relevance of our approach.