【作者】 王保仓；

【导师】 胡予濮；

【作者基本信息】 西安电子科技大学 ， 密码学， 2006， 博士

【摘要】 传统的公钥密码算法速度比较慢，这制约了公钥密码的广泛应用。国内外密码学界都在加强快速密码算法的研制与开发，以便使公钥密码能够应用到更广泛的环境中。在快速公钥密码这一研究领域，本文取得了如下成果： (1)找到了一类新的易解背包问题，并用此问题构造了一个背包型加密算法。该算法是第一个基于背包问题的概率加密方案。证明了该算法能够抵抗低密度攻击和联立丢番图逼近攻击等。而且该算法的加解密计算复杂度是二次的。 (2)找到了RSA公钥密码算法的一类弱密钥，指出如果RSA数的两个素因子的比值能够被一个小分数有效逼近的话，则RSA数是容易分解的。 (3)使用中国剩余定理构造了一个快速公钥加密算法，证明了攻击者重构陷门信息等价于求解两个数论困难问题，即整数分解和联立丢番图逼近问题。 (4)对RSA问题进行了推广，提出了广义RSA问题，给出了广义RSA问题与RSA问题之间的联系。并用此问题构造了一个具有双重陷门解密机制的公钥密码算法GRSA。证明了GRSA是单向的当且仅当广义RSA计算问题是困难的，GRSA是选择明文攻击下语义安全的当且仅当广义RSA判定问题是困难的。 (5)构造了一个安全性基于两个数学困难问题的公钥密码算法，该算法的安全性同时基于整数分解和联立丢番图逼近困难问题，而且该密码算法的加解密计算复杂度是二次的。 (6)使用矩阵环上的一个特殊的组合问题构造了一个公钥加密算法，其安全性与整数分解问题有关，但并不直接依赖于整数分解问题，而是依赖于一类特殊的矩阵组合问题。 (7)从辫群上求根问题的困难性出发构造了一个数字签名方案，证明了攻击者能够成功地伪造一个签名当且仅当他能够求解辫群上的求根问题。而且从该数字签名方案出发构造了一个基于身份的数字签名方案。 (8)对公钥密码算法Naccache-Stern进行了安全性分析，指出该算法的解密可以看作一个群分解问题，并说明了该攻击算法攻击成功的概率依赖于把一个随机的自然数转化成一个光滑数的概率。 (9)对2000年ACISP会议上的一个快速公钥密码算法进行了安全性分析，给出了该算法的安全性与联立丢番图逼近问题以及格上的最小向量问题之间的关系。更多还原

【Abstract】 The traditional public-key ciphers suffer from a drawback that their speed is relatively low, which hampers the further applications of public key cryptography and also motivates the cryptographic community to design fast public-key cryptosystems. In the area of fast public-key cryptography, the author obtains the following main results.(1) A new kind of easy knapsack-type problems is found. A knapsack-type public-key encryption scheme is constructed based on the problem. This is the first probabilistic knapsack-type encryption scheme. It is shown that the cryptosystem is secure against low-density attacks and the simultaneous Diophantine approximation attacks. Furthermore, the computational complexities of the encryption and the decryption algorithms of the cryptosystem are quadratic.(2) A weak key of the RSA cryptosystem is found. It turns out that the modulus of the RSA cryptosystem is easy to factor if the the ratio of the two prime factors of the modulus can be well approximated by a small fraction.(3) A fast public-key encryption scheme is developed by using the Chinese remainder theorem. It is pointed out that the attacker must solve two number-theoretic intractable problems, namely the integer factorization and simultaneous Diophantine approximation problems, to recover the trapdoor information.(4) The RSA problem is generalized by introducing the generalized-RSA problem. The relations between the RSA problem and the G-RSA related problems are given. A public-key cryptosystem GRSA is proposed, which is based on the G-RSA problem and features double trapdoor decryption mechanism. It is proven that the GRSA is one-way if and only if the computational G-RSA problem is intractable, and the semantic security of the GRSA cryptosystem under the chosen-plaintext attack model is correct if and only the decisional G-RSA problem is infeasible.(5) A public-key cryptosystem based on two cryptographic intractable assumptions is proposed. The security of the proposed cryptosystem is based on the integer factorization and the simultaneous Diophantine approximation problems. It only takes quadratic bit complexity for the cryptosystem to perform an encryption/decryption operation.(6) A public-key cryptosystem is proposed by using a special combinatorial problem defined over the matrix ring. The security of the scheme is related to but not directly dependent upon the integer factorization problem.(7) This dissertation considers the root extraction problem defined over braid groups, and constructs a digital signature scheme. It is shown that the attacker can forge a signature if and if he can solve the root extraction problem defined over braid groups. Furthermore, the signature scheme is modified as an identity-based signature scheme.(8) The Naccache-Stern cryptosystem is cryptanalyzed. It is pointed out that the decryption of the cryptosystem can be viewed as a group factorization problem. The success probability of the attack relies on with what probability it can successfully transform a random integer into a smooth number.(9) The security of the cryptosystem proposed at ACISP 2000 is analyzed. The relation of the security of the cryptosystem with the simultaneous Diophantine approximation problem and the shortest vector problem over lattices is clarified.更多还原