对一种背包公钥密码改进方案的安全性分析

背包公钥密码算法是比较热门的加密算法之一,目前仍有很多密码研究者在研究背包公钥密码的改进算法。文献[1]提出了两个改进的背包公钥密码方案,本文对这些改进算法进行了安全性分析,并就其中一个方案进行了格规约攻击。通过计算实验说明这种改进之后的背包公钥密码算法仍然是不安全的。     

一种基于多背包的密码算法

本文介绍了背包问题和L3-格基约简算法并加以深刻的分析,在此基础上提出了一种基于多背包的加密算法,该算法大大加强了背包加密算法的安全性,可以有效的对抗L3-格基约简算法。     

对一种RSA改进算法的安全性分析

RSA和背包公钥密码算法都是经典的加密算法,目前仍有很多密码研究者在研究它们的改进算法. 王茜等作者将两者结合起来设计了一个新的密码方案,将RSA用到了背包密码体制中. 对这一新方案进行了安全性分析,从三个角度对这一方案进行了分析说明,并通过格规约攻击计算实验来验证,最终说明这种改进之后的公钥密码算法仍然是不安全的.     

对一种新的背包加强算法的破解

自从Shamir提出攻击RalphMerkle和MartinHellman背包密码系统的算法以来,背包密码系统在算法设计上进行了改进,使其在改进后能抵挡Shamir攻击。但由于自身算法设计上可能存在缺陷,其中有一些改进后的背包密码系统会带来新的安全问题。本文是关于一篇题为《一种新的背包加强算法》(注:发表于《电脑与知识》第2004.29期)一文中提出的背包密码算法的破解算法。     

一种新的背包加强算法

背包问题是著名的NP问题,因此它一度成为密码学界的研究热点。由最初的Merkle-Hellman背包算法到后来的Chor-Rivest背包算法,但很多算法都相继被破译。本文提出了一种加强背包算法,具有操作简易性和较强的安全性,可以运用于网络通信加密系统。     

An incomplete m-exchange algorithm for solving the large-scale multi-scenario knapsack problem

This paper introduces a fast heuristic based algorithm for the max-min multi-scenario knapsack problem. The problem is a variation of the standard 0-1 knapsack problem, in which the profits of the items vary under different scenarios, though the capacity of the knapsack is fixed. The objective of the problem is to find the optimal packing of a set of items so that the minimum total profits of the items in the knapsack over all different scenarios is maximized. For some large-scaled instances, traditional branch-and-bound techniques cannot find an optimal solution within reasonable time, thus we propose a collection of incomplete m-exchange algorithms which are able to produce high quality solutions in just a few minutes of cpu time. Various computational results are also given.     

Determining the K-best solutions of knapsack problems

It is well-known that knapsack problems arise as subproblems of a number of large-scale integer optimization problems. In order to solve these large problems, it is necessary to solve the subproblems efficiently, and for many of them it can be useful to determine the K-best solutions. In this paper, a branch-and-bound method for the unbounded knapsack problem described in the literature is extended to determine the K-best solutions of unbounded and bounded knapsack problems. We show that the proposed extension determines exactly the K-best solutions and we solve important classical instances using high values of K.     

New cryptosystems design based on hybrid-mode problems

Though a lot of public key cryptographic algorithms have been proposed, practically some cryptographic systems’ security will no longer be secure unless the corresponding hard problems are solved in the future. Enhancing security is the major objective for public key cryptosystems on the basis of the hardness of the intractable computational problems. In this paper, we present a new cryptosystem design based on linearly shift knapsack and elliptic curve discrete logarithm problems. Having concatenated Knapsack and ECC hard problems, the presented scheme has solid structure and will hopelessly leave the eavesdropper baffled. The performance analysis has been given to describe the proposed scheme in terms of security level. In addition, the security performance in encryption/decryption complexity is equivalent to related cryptosystems with the nature of security. At the moment, no malicious attacks are capable of “breaking” this scheme in a reasonable amount of time obviously.     

THE NAVY CIPHER BOX MARK II

Recent suggestions in [8] that optimization techniques such as the genetic algorithm can be used to successfully solve knapsack ciphers are somewhat optimistic. The inability to assign an appropriate fitness to an arbitrary solution of the knapsack cipher is the downfall with this method. In this paper a detailed analysis of the proposed fitness function is undertaken and numerical results are presented displaying the futility of using this fitness function in a genetic algorithm for solving knapsack ciphers of any reasonable size.     

背包问题最优解的结构

讨论背包问题的最优解,引入背包问题的阶的概念,并对背包问题的阶作出深入的讨论,在此基础上得到背包问题的最优解的一般形式。     

A dynamic access control scheme based upon the knapsack problem

A new dynamic access control scheme for information protection systems is proposed in this paper. The main idea of it is inspired by the concept of the trapdoor knapsack problem proposed by Merkle and Hellman. Since the knapsack problem is an NP-complete problem, the security of access control is achieved henceforth. Our scheme associates each user with some user keys and each file with some file keys. There is a positive integer set of S′; through a simple formula on keys and S′, the corresponding access privilege can be easily revealed in the protection system. Moreover, by employing our scheme, insertion or deletion of the user/file can be processed effectively with only a few previously defined keys and locks required to be modified.     

Online knapsack with resource augmentation

It is known that online knapsack is not competitive. This negative result remains true even if items are removable. In this paper we consider online removable knapsack with resource augmentation, in which we hold a knapsack of capacity R?1 and aim at maintaining a feasible packing to maximize the total profit of items packed into the knapsack. Both scenarios that removal of accepted items is allowed and is not allowed are investigated. We evaluate an online algorithm by comparing the resulting packing to an optimal packing that uses a knapsack of capacity one. Optimal online algorithms are derived for both the weighted case (items have arbitrary profits) and the unweighted case (the profit of an item is equal to its size).     

Sensitivity analysis of the knapsack sharing problem: Perturbation of the weight of an item

In this paper, we study the sensitivity analysis of the optimum of the knapsack sharing problem (KSP) to the perturbation of the weight of an arbitrary item. We determine the interval limits of the weight of each perturbed item using a heuristic approach which reduces the original problem to a series of single knapsack problems. A perturbed item belongs either to an optimal class or to a non-optimal class. We evaluate the performance of the proposed heuristic on a set of problem instances of the literature. Encouraging results are obtained.     

Fast decryption algorithm for the knapsack cipher

A fast decryption algorithm is described which permits use of the knapsack cipher (a public-key cryptosystem) at data rates in the neighborhood of 10 Mbit/sec. This high-speed capability can be used to incorporate the security and flexibility of public-key cryptosystems into a wide variety of real-time communications applications. Implementation of the algorithm using Very Large Scale Integration appears attractive: The circuit functions required are approximately 56 kilobits of memory and a small amount of arithmetic logic.     

基于Visual C 的0-1背包问题的动态规划算法

0-1背包问题是经典的NP问题.本文对0-1背包问题的动态规划算法进行了分析,用Visual C 实现该算法.     

考虑时间因素的0-1背包调度问题

文中提出考虑时间因素的0-1背包调度问题这一具有NP难度的组合优化问题。给定n个物体(每个物体i的重量为w_i,连续加工时间为t_i),以及一个容量为S的背包,要求给出一个调度方案(物品的放入顺序和放入时间),使得任意时刻放入背包的物品总重量不超过背包容量,每个物体需放入背包连续加工时长t_i后才能取出,该问题是求使所有物体均加工完毕的时间尽可能短的调度方案。提出了3种求解算法:迭代动态规划算法、基于分枝限界的完备算法和遗传进化算法。迭代动态规划算法使用动态规划策略放置尽可能多的未加工物体到背包中,然后每次迭代取出加工完成的物品后再使用动态规划放入尽可能多的剩余未加工物品,直至所有物品被加工完成。基于分枝限界的完备算法通过定义上下界及剪枝操作,有效地降低了算法的计算复杂度。遗传进化算法将一个物品装填序列定义为个体,并定义了相应的适应度、选择、交叉与变异操作。在所设计的3组共计36个算例上的实验结果表明,迭代动态规划算法可以很快求出高质量的解,基于分枝限界的完备算法对小规模算例有很好的效果,遗传算法在处理几百个物体的算例时能在1500s内得到比动态规划算法更好的结果。     

Heuristic and exact algorithms for the max–min optimization of the multi-scenario knapsack problem

We are concerned with a variation of the standard 0–1 knapsack problem, where the values of items differ under possible S scenarios. By applying the ‘pegging test’ the ordinary knapsack problem can be reduced, often significantly, in size; but this is not directly applicable to our problem. We introduce a kind of surrogate relaxation to derive upper and lower bounds quickly, and show that, with this preprocessing, the similar pegging test can be applied to our problem. The reduced problem can be solved to optimality by the branch-and-bound algorithm. Here, we make use of the surrogate variables to evaluate the upper bound at each branch-and-bound node very quickly by solving a continuous knapsack problem. Through numerical experiments we show that the developed method finds upper and lower bounds of very high accuracy in a few seconds, and solves larger instances to optimality faster than the previously published algorithms.     

The two list algorithm for the knapsack problem on a FPS T20

The advent of parallel machines brought about a controverse in the domain of parallel algorithms: is it worth to conceive parallel algorithms for NP-complete problems? In this work we present a parallel implementation of a sequential algorithm from Horowitz and Sahni for the knapsack problem on a FPS T20. Our aim is to establish some experimental results in order to allow comparisons for forthcoming works. The results show that the development of theory and technology yields the computation tractability of very large knapsack problems.     

Shuffled frog leaping algorithm and its application to 0/1 knapsack problem

This paper proposes a modified discrete shuffled frog leaping algorithm (MDSFL) to solve 01 knapsack problems. The proposed algorithm includes two important operations: the local search of the ‘particle swarm optimization’ technique; and the competitiveness mixing of information of the ‘shuffled complex evolution’ technique. Different types of knapsack problem instances are generated to test the convergence property of MDSFLA and the result shows that it is very effective in solving small to medium sized knapsack problems. Further, computational experiments with a set of large-scale instances show that MDSFL can be an efficient alternative for solving tightly constrained 01 knapsack problems.     

解0-1背包问题的蚁群算法

针对经典的0-1背包问题，提出一种基于解的相异度的新的蚁群优化算法，废方法引入信息量的局部更新机制，并根据解的相异程度确定解的交叉概率。数值实验计算表明，该算法加快计算速度的同时保证了解的多样性，具有较好的通用性。