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

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

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

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

New public-key cryptosystem

The development of a new public-key cryptosystem is discussed. This system is a hybrid combination of the RSA (Rivest-Shamir-Adleman) and knapsack crypto-systems. The message is encrypted in two stages using the knapsack algorithm followed by the RSA algorithm, and then decrypted in reverse order. The mathematics of the knapsack and RSA algorithms, a security analysis of the hybrid system, and a small computer simulation example are all included. The major advantages of this system, when compared with the knapsack and RSA crypto-systems, are higher speed and greater security.     

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.     

背包问题无存储冲突的并行三表算法

背包问题属于经典的NP难问题，在信息密码学和数论等研究中具有极重要的应用，将求解背包问题著名的二表算法的设计思想应用于三表搜索中，利用分治策略和无存储冲突的最优归并算法，提出一种基于EREW-SIMD共享存储模型的并行三表算法，算法使用O（2^n/4）个处理机单元和O（2^3n/8）的共享存储空间，在O（2^3n/8）时间内求解n维背包问题．将提出的算法与已有文献结论进行的对比分析表明：文中算法明显改进了现有文献的研究结果，是一种可在小于O（2^n/2）的硬件资源上，以小于O（2n/2）的计算时问求解背包问题的无存储冲突并行算法。     

Quadratic compact knapsack public-key cryptosystem

Knapsack-type cryptosystems were among the first public-key cryptographic schemes to be invented. Their NP-completeness nature and the high speed in encryption/decryption made them very attractive. However, these cryptosystems were shown to be vulnerable to the low-density subset-sum attacks or some key-recovery attacks. In this paper, additive knapsack-type public-key cryptography is reconsidered. We propose a knapsack-type public-key cryptosystem by introducing an easy quadratic compact knapsack problem. The system uses the Chinese remainder theorem to disguise the easy knapsack sequence. The encryption function of the system is nonlinear about the message vector. Under the relinearization attack model, the system enjoys a high density. We show that the knapsack cryptosystem is secure against the low-density subset-sum attacks by observing that the underlying compact knapsack problem has exponentially many solutions. It is shown that the proposed cryptosystem is also secure against some brute-force attacks and some known key-recovery attacks including the simultaneous Diophantine approximation attack and the orthogonal lattice attack.     

Optimal Parallel Algorithm for the Knapsack Problem Without Memory Conflicts

Abstract The knapsack problem is well known to be NP-complete. Due to its importance in cryptosystem and in number theory, in the past two decades, much effort has been made in order to find techniques that could lead to practical algorithms with reasonable running time. This paper proposes a new parallel algorithm for the knapsack problem where the optimal merging algorithm is adopted. The proposed algorithm is based on an EREW-SIMD machine with shared memory. It is proved that the proposed algorithm is both optimal and the first without memory conflicts algorithm for the knapsack problem. The comparisons of algorithm performance show that it is an improvement over the past researches.     

Optimal parallel algorithms for the knapsack problem without memory conflicts

The knapsack problem is well known to be NP-complete. Due to its importance in cryptosystem and in number theory, in the past two decades, much effort has been made in order to find techniques that could lead to practical algorithms with reasonable running time. This paper proposes a new parallel algorithm for the knapsack problem where the optimal merging algorithm is adopted. The proposed algorithm is based on anEREW-SIMD machine with shared memory. It is proved that the proposed algorithm is both optimal and the first without memory conflicts algorithm for the knapsack problem. The comparisons of algorithm performance show that it is an improvement over the past researches.     

安全背包公钥密码的要点和设计

为提高背包密码的安全性,文章依据背包密码以往失败的原因,提出了一个背包密码的可证明安全性的启发性方法,据此设计了一个新型背包密码。该密码由模乘运算实现混乱,由基于二元一次不定方程的难解函数实现扩散,充分隐藏初始序列及其冗余度,攻击者破译该背包密码的难度规约为求解此难解函数,同时能达到较高的背包密度,常规的破译方法无效。     

FAPKC签名和加密混合使用的安全性分析

在实际的应用密码系统中有一个重要的原则:密钥只能有单一的用途,它仅用于加密或仅用于签名·但是Haber和Pinkas指出,在许多情况下,在两个不同的密码系统中(比如一个公钥加密系统和一个公钥签名系统)同时使用有关联关系的密钥实际上并不会损害系统的安全性·有限自动机公开钥密码体制既可用来加密,也可用来签名,因而是一个混合密码系统·对FAPKC加密和签名混合使用的安全性进行了分析,证明了混合使用FAPKC不损害密码体制的安全性·     

对一个背包公钥密码的格攻击*

对一个新的基于Merkle-Hellman背包密码和Rabin公钥密码的背包公钥密码算法进行了安全性分析。使用格规约算法求解一个联立丢番图逼近问题和一个二元整数线性规划问题就恢复出了该密码算法的部分密钥。重构的部分密钥可以解密任意密文。因此,该背包公钥密码算法是不安全的。     

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

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

基于证书的抗泄露的安全加密方案

近期实践表明密码系统容易受到各种攻击而泄漏密钥等相关秘密信息, 泄漏的秘密信息破坏了以前的已证明安全的方案, 因此设计抗泄漏的密码学方案是当前密码研究领域的一个热点研究方向。设计一个基于证书的加密方案, 总的设计思想是使用一个基于证书的哈希证明系统, 这个证明系统包含一个密钥封装算法, 用这个密钥封装算法结合一个提取器去加密一个对称加密所用的密钥, 那么得到的加密方案就是可以抵抗熵泄漏并且是安全的。对方案的安全性分析和抗泄漏性能分析, 表明本方案在抵抗一定量的密钥泄漏和熵泄漏时可以保持安全性。     

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

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

多变量分支混沌签名体制

针对量子计算机对现有密码算法的威胁,结合多变量公钥体制和混沌系统,提出一种能抵抗量子算法的分支密码体制。体制的中心映射有两个分支,分支一使用传统多变量公钥密码体制,分支二使用混沌密码体制,将两分支的输出结果相加,最后通过仿射变换将中心映射进行隐藏。利用分支结构提高计算效率,利用混沌系统克服传统多变量公钥密码体制的缺点以增强安全性,适用于各类设备进行签名运算。     

0-1背包问题的两种扩展形式及其解法

0-1背包问题是经典的NP-HARD组合优化问题之一,由于其难解性,该问题在信息密码学和数论研究中具有极其重要的应用。首先对01背包问题及其解法进行了分析,然后提出01背包问题的两种扩展形式,并给出了基于动态规划和贪心算法的两种有效算法来解决这两类问题。实验结果验证了所提出方法的有效性。     

一个新的高效无证书签名方案

为了消除传统公钥密码系统中公钥证书的管理和传递,同时避免基于身份密码系统中的密钥托管问题,出现了无证书密码系统。基于双线性对提出了一个新的无证书签名方案。方案的签名算法只需要一个指数运算,验证算法仅需要两个对运算。方案的安全性依赖于CDH困难问题和Inv-CDH困难问题,并在随机预言机模型下,证明能够抵抗适应性选择消息攻击下的存在性伪造。     

Security enhancement for AES encrypted speech in communications

This paper introduces a secure speech communication approach, which is based on encryption and authentication. This system is based on Advanced Encryption Standard (AES) for encryption and private image database for enhancement of encryption and for authentication. The idea of this cryptosystem is based on XOR of one image from image database with the clear speech before encryption and embedding the index number of this image in the database as a least significant bit watermark into speech. A comparison study is held between the AES block cipher algorithm and the proposed algorithm. This proposed cryptosystem used to enhance the security of AES algorithm and increase its immunity to brute force attacks. It used also to provide authentication and enhance security by addition of extra key which don’t need to be exchanged between parts depending on the embedded image. The extra proposed step remove residual intelligibility from clear speech and fill the silent periods within speech conversation and help in destroy format and pitch information. Security analyses are presented for the proposed cryptosystem from a strict cryptographic viewpoint. Experimental results verify and prove that the proposed cryptosystem is highly secure from the cryptographic viewpoint.     

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.     

椭圆曲线密码体制在电子公文中的应用与研究

椭圆曲线密码体制是基于代数曲线的一种公开密钥密码系统,它的安全性基于有限域上椭圆曲线离散对数问题。文中利用椭圆曲线密码体制对电子公文进行数字签名,以解决身份认证问题。而对于电子公文的加密则采用两种加密机制:利用典型的对称密码体制DES算法对电子公文的内容进行加密,而利用接收方和发送方的基于椭圆曲线密码体制的公开密钥和私有密钥,进行一定的计算得到DES算法进行加密/解密所需要的密钥。将公钥算法和私钥算法的有机结合,解决了密码体制中速度和安全性不能兼顾的问题。