【作者】 韩立东；

【导师】 展涛； 王小云；

【作者基本信息】 山东大学 ， 信息安全， 2010， 博士

【摘要】 随着计算机和网络通信的快速发展,人们开始重视个人数字信息保护和各种服务的安全性,如保护个人秘密信息,防止消息篡改,保证通信双方的公平性等。密码学为这些服务的安全性提供了技术,特别是公钥密码学,已成为当今社会信息安全技术的核心。1976年Diffie和Hellman在发表的论文《密码学的新方向》中首次提出公钥加密概念,是密码学方向的一个重要里程碑,开启了密码学的新纪元。麻省理工学院的Rivest, Shamir和Adleman设计出第一个实际的公钥密码体制,称为RSA算法,是迄今为止最著名的公钥密码算法之一,它可以同时用于数据加密和数字签名。1978年,Merkle和Hellman提出了基于子集和问题的背包公钥密码算法-Merkle-Hellman密码体制。此后,又有许多重要的公钥密码算法相继被提出,如McEliece加密算法,Rabin加密算法,ElGamal加密与签名算法,椭圆曲线密码(ECC)算法,Goldwasser-Micali概率加密算法等。目前,RSA加密与签名算法,ElGamal签名算法的变型(DSA)已成为国际上著名的加密签名标准,这些密码算法被广泛应用于网络安全领域和银行系统,为交互双方安全通信提供了保障和技术。因此,对公钥密码算法的安全性进行分析具有重要的理论意义和实际的应用价值。自从公钥密码学提出以来,密码学家一直致力于密码算法的安全性研究。本文针对RSA和背包两种公钥密码体制的安全性做了一些研究。我们的主要工作集中在中国剩余定理表示的RSA密码系统和RSA模特殊素因子的安全性分析,同时针对抵抗Shamir攻击和低密度攻击的两种新背包型密码算法,分别给出有效的破解算法。1.基于中国剩余定理表示(CRT)RSA密码系统小解密指数的攻击分析简单版本的RSA算法描述如下,首先选取比特长度相同的两个大素数p与q,它们的乘积N被称为RSA模。除此之外,另两个重要的参数是加密指数e和解密指数d,其中e与N的欧拉函数φ(N)：=(p-1)(q-1)互素,且满足RSA方程ed=1 mod(?)(N).RSA加密算法加密消息m时,计算C=me mod N,发送密文C给用户。用户收到密文C后,进行解密运算Cd mod N,由欧拉定理知Cd=med=m mod N,从而得到消息m。RSA的安全性基于求解模N的e次根的困难性。破解RSA公钥密码体制直接有效的方法是分解RSA模N。目前分解整数的方法有连分数方法,Pollardp-1方法,二次筛法,椭圆曲线方法,数域筛法等,其中分解RSA模最快的方法是数域筛法,其时间和空间复杂度都是亚指数的。最近,768比特的RSA挑战数宣告被分解,其算法的复杂度相当于分解512比特的RSA挑战数的上千倍。同时密码学家建议1024比特的RSA在三到四年内停止使用,为保证安全可以使用比特数为1536比特,甚至2048比特的RSA模。Shor 1992年在假设量子计算机模型存在的情况下,给出了分解整数的多项式时间算法,然而能否研究出多量子位的量子计算机还是一个未知数。1982年A.Lenstra,H.Lenstra和L.Lovasz提出计算格中近似短向量的多项式时间算法,并用此算法解决了有理系数多项式的分解问题。人们以三人姓氏的首字母命名此算法为LLL算法。LLL算法在RSA密码算法及其他公钥密码体制的安全性分析中有广泛的应用。最著名的是,Coppersmith利用LLL算法在多项式时间内求解单变量的模N方程fN(χ)=0 mod N的小根x0,其中N是分解未知的合数,和计算两个变量的整系数方程f(x,y)=0的小根(x0,y0)。此后,许多RSA的攻击结果都是基于Coppersmith的格构造技术和近似短向量求解算法-LLL算法,如小加密指数攻击,小解密指数攻击,密钥泄露攻击等。对于小解密指数攻击,Wiener在1990年提出当d<N0.25时,通过扩展欧几里得算法求解e/N的渐近连分数,得到解密指数d,从而在多项式时间内分解RSA模。目前最好的结果是Boneh和Durfee提出的。即当d<N0.292时,可以分解RSA模。基本思想是通过RSA方程ed=κ(?)(N)+1,利用Coppersmith的格构造技术构造格,然后使用格归约算法找到格中的较短向量,最后求解短向量所表示的二元方程的根。为了抵抗上述小解密指数攻击,Wiener指出使用中国剩余定理(CRT)表示私钥d来进行解密或签名是一种非常有效的方法,并且可以选取小的CRT解密指数代替小的解密指数使解密过程更加有效快速。这种表示形式最早是由Quisquater和Couvreur提出的。具体地,RSA密码算法的解密指数d由CRT解密指数dp和dq表示,且满足满足下面关系当解密密文c= me mod N时,不是计算m= cd mod N,而是mp= cdp mod p和mq= cdq mod q,然后通过中国剩余定理计算出明文m。可以看出,使用CRT解密指数dp和dq进行解密比标准RSA解密过程一般快四倍。Galbraith, Heneghan, Mckee[110]和Sun, Wu[110]基于素数分布理论分别设计了快速加密和解密的CRT-RSA密码体制,其密钥生成方法是,首先选取小的公钥指数e和私钥指数dp,dq,然后检测所得的p和q是否为素数。Bleichenbacher和May分析了文献[40,110]设计的CRT-RSA密码体制的安全性,指出当CRT解密指数dp和dq满足攻击者可以在多项式时间内有效分解RSA模N。其攻击方法是巧妙地利用CRT-RSA方程得到一个关于四个变元的线性方程,然后构造一个特殊的三维格,把分解RSA模问题转化成求解此三维格中的最短向量问题。LLL算法在三维格中可以找到最短向量,因此利用LLL算法就可以解决上述问题。文献[3]指出,假设所构造三维格中长度小于Minkowski界的短向量是唯一的,从而可以分解此向量所对应的多项式,得到CRT-RSA的私钥指数dp,dq。本文第三章指出此唯一性假设在一般情况下不成立,证明文献[3]中构造的格中长度小于Minkowski界的短向量是不唯一的,也就说明存在多个小于Minkowski界的短向量,并给出了反例。同时讨论能否改进格的构造使得文献[3]的攻击方法还可以有效,我们给出了否定的答案,并指出了原因。同时,我们对上述攻击进行了改进和完善,即在一般情况下可以求解此问题。特别地,对于e<N3/8和dp,dq<(1/3)N(1/4),指出利用连分数方法可以有效地求解此问题。2.特殊素因子的RSA密码系体制的安全性分析记RSA模N的两个素因子p和q的差p-q为∧,称为RSA模N的素因子差。记ip-jq为∧1,其中i,j是小整数,称为N的素因子组合差。de Weger研究分析了∧比较小的这种情况,且要求p和q的比特长度相同,给出了弱密钥解密指数d的界与∧之间的关系。指出当N的素因子差很小时,分别利用连分数方法和格基归约方法可以提高Wiener和Boneh,Durfee的弱密钥解密指数d的界。Blomer和May通过对等式ex+y≡0 mod(?)(N)进行分析,给出了新的弱密钥估计,同时也提出弱密钥的范围随着素因子差∧变小而增大。最近,Maitra和Sarkar考虑了2q-p的情况,本质上是Weger分析结果的补充。如果p和q的比特数不同,上述攻击分析方法是不成立的。因此,本文就此情况展开讨论,即允许p和q是不同比特的素数,分析N的素因子组合差A1=ip-jq与解密指数d之间的联系。首先,利用Fermat的分解方法,证明当Λ1≤(logN)″(|ij|N)(1/4)可以在多项式时间内计算出RSA模N的素因子p和q。其次,当Λ1≥(|ij|N)(1/4)利用连分数攻击方法分析∧1与d之间的关系,并给出当解密指数d满足条件d<N(3/4)-β-τ时,其中Λ1=Nβ，τ>0，RSA密码算法是不安全的。进一步,通过格归约分析方法,讨论RSA模N的素因子组合差∧1与弱密钥解密指数d的关系。以上情况下,当d>N0.292且p,q不同比特时,文献[9,72,116,117]中的攻击方法是不成功的,并给出了实例论证。同时,分析扩展了Blomer,May的攻击结果,得到更多新的弱密钥。3.两种背包型公钥密码算法的安全性分析背包加密算法是基于子集和问题的困难性设计的,该问题已被证明是NP完全问题。也就是说,不存在多项式时间算法求解子集和问题。Merkle和Hellman设计了第一个基于子集和问题的密码算法,具有重要的历史意义。随后人们提出了许多Merkle-Hellman背包算法的变体,其中大多数变体(包括原始方案)已被证明是不安全的。Shamir第一个提出了针对基本的Merkle-Hellman背包方案的多项式时间攻击,这种攻击利用H.Lenstra的整数规划算法,当变量的数目固定时,该算法是多项式时间的,但在实际中效率很低。Adleman指出Merkle-Hellman背包算法的分析也可以看成格基归约问题,利用LLL算法更简洁有效的破解Merkle-Hellman体制。Logarias和Brickell,以及Coster等人利用格基归约方法针对背包密码体制所基于的子集和问题进行了更为深入的研究,假设格基归约方法可以求解格中的最短向量问题(格的维数一般小于200),他们的方法适用于所有低密度的背包算法。1988年,Chor和Rivest基于有限域上的运算设计了一种背包密码算法,当参数选取合适时,可以Shamir攻击和低密度攻击。自该算法提出十年来,人们一直认为Chor-Rivest背包算法是安全的,直至1998年,Vaudenay针对Chor-Rivest背包算法通过分析其所基于的有限域的数学特征提出一种代数攻击。由于不存在多项式量子算法求解子集和问题,许多密码学家认为在后量子时代背包算法对于公钥密码学还是有价值的。2000年,Okamoto等人提出量子计算机模型下的背包密码体制。最近,张等人和王等人分别设计了新背包型密码算法和高密度型背包密码算法,可以抵抗Shamir攻击和低密度攻击,这两种背包体制都是基于易解的背包问题设计的,结构简单易于软硬件实现。首先,通过分析文献[120]中选择参数的要求,我们给出一种有效的攻击方法,其基本运算是欧几里德算法或整数分解,由于所分解的数是私钥很小的倍数,因此可以有效地求解出私钥,从而在多项式时间内破解了整个密码算法。其次,针对文献[121]中的高密度型背包体制,通过分析密码体制的公钥分量之间的数学特征,找到该密码体制的私钥-模M,然后在小空间(U或i比特的奇数)内搜索逐一确定其他的私钥,最终计算出所有的私钥。更多还原

【Abstract】 With the rapid development of computers and internet communication, people begin to pay more attention on protection of personal digital information and a vari-ety of security services, such as protecting the confidentiality of personal information, preventing the message tampered and guaranteeing the fairness between two parties. Cryptography offers a technique to ensure these services secure. Especially, public-key cryptography has been a key technique for information security.The most striking development in the history of cryptography came in 1976 when Diffie and Hellman published " New Directions in Cryptography ". This paper intro-duced the revolutionary concept of public-key cryptography. Rivest, Shamir, and Adle-man in MIT discovered the first practical public-key scheme, now referred to as RSA, which is one of the most popular public-key cryptosystems. It can be used to encrypt the plaintext and sign a message. In 1978, Merkle and Hellman designed a knap-sack public key cryptosystem based on subset sum problem, called Merkle-Hellman cryptosystem. After that, there are many public-key schemes brought forward, for example, McEliece public-key encryption algorithm, Rabin public-key encryption al-gorithm, ElGamal encryption algorithm and signature algorithm, Elliptic curve cryp-tosystems(ECC), Goldwasser-Micali probabilistic encryption algorithm, et al.Nowdays, RSA encryption and signature algorithms and ElGamal signature algo-rithm have been two famous international standards for encryption and signature。They are widely used in network security and bank systems to ensure the fairness between two parties in secure communications. Also, they propose a key technique for secu-rity. Therefore, cryptanalysis of the public-key cryptosystems is extremely important for theoretical significance and practical value. Since public-key cryptosystems were invented, cryptographers have been applying oneself to security research of public-key cryptosystems.In this dissertation, some researches on RSA and Knapsacks Public Key Systems are made. We mainly focus on cryptanalysis of Chinese Remaindering Theorem (CRT) representing RSA cryptosystem with small private CRT exponents, and security analy-sis on RSA with special prime factors of RSA modulus, and also propose two efficient attack methods for two new knapsack public key cryptosystems respectively, which is showed to resist against Shamir attack and low density attack.1. On the RSA public key cryptosystem with small private CRT private exponentsThe textbook version of RSA encryption scheme is depicted as follows:Choose two large prime number p and q with same bit length, denote their product pq as N, and call N the RSA modulus. Besides, another two important parameters are encryption exponent e and decryption exponent d, where e is prime to the Euler function of N, (?)(N):= (p-1)(q-1), and satisfies the RSA equation:ed= 1 mod(?)(N). when encrypting the message m, one computes C=me mod N, and send the cipher C to the user. After receiving C, the user can proceed the decryption operation Cd mod N, and the message m is recovered by Euler theorem.The security of RSA depends on the difficulty of computing the e-th root modulo a composite integer N. Factoring the RSA modulus N is the most direct and efficient method to break RSA cryptosystem. There are many methods of integer factoring such as continued fraction factorization, Pollard p-1 method, quadratic sieve method, elliptic curve method, general number field sieve method. Currently, the fastest tech-nique for integer factorization is general number field sieve method, the memory/space complexity of which are sub-exponential. Recently, it was declared that 768 bits RSA Challenge number had been factored, and the complexity of factoring 768 bits is several thousands times harder than that of factoring a 512-bit RSA modulus. Cryptographers suggest that it would be prudent to phase out the use of 1024-bit RSA within the next three to four years, and one can use 1536 bits RSA modulus, even 2048 bits for much more security. Shor discovered polynomial time quantum algorithm to factor an large composite integer N under the assumption that a large-scale quantum computer exists, but the feasibility of such devices is still open up to now.The lattice basis reduction algorithm in polynomial time is due to A. Lenstra, H. Lenstra, L. Lovasz in 1982, which is initially used to factor polynomials with rational coefficients. The LLL algorithm, named after its inventors A. Lenstra, H. Lenstra, L. Lovasz, is the most widely used tool to analyze the security of RSA and other public key cryptosystems nowadays. The most popular outcome is Coppersmith’s results, i.e., find small rootχ0 of univariate modular equation fN(χ)=0 mod N with the factors of N unknown in polynomial time using LLL algorithm, and find small roots (χ0, y0) of bivariate integer polynomial equation f(x, y)=0. After that, many cryptanalysis results are based on Coppersmith’s lattice construction technique and lattice basis re-duction algorithm-LLL, for example, the attack on small public exponent, the attack on small private exponent, partial private key exposure attack and so on. In 1990, Wiener showed that, when d＜N0.25 the private key d can be efficiently recovered by solving the convergents of (?) using extended Euclidean algorithm, so the RSA modulus N will be factored. Up to now, the best attack on private exponent is Boneh and Durfee’s attack, that is, generating a lattice by utilizing Coppersmith’s lattice construction tech-nique from RSA equation (?), then find small relatively vectors using lattice basis reduction algorithm, and finally solve two bivariate integer polynomial equations represented by small vectors. The result is that, the RSA modulus N can be factored if d＜N0.292.To resist against small private exponent attacks, Wiener suggest that Chinese re-maindering representation of d for decryption or signature is a very efficient method. Choosing even small private CRT exponents can make decryption or signature more fast and more efficient. This representing technique was first devised by Quisquater and Couvreur. To describe concretely, the private exponent d is represented by CRT private exponents dp and dq, which satisfy the following relations When decrypting the ciphertext c, we do not execute m=cd mod N, but compute mp=cdp mod p and mq=cdq mod q. Finally, m can be recovered by the Chinese Remaindering Theorem。Using the secret CRT-components, decryption and signature generation are four times faster than standard decryption and signature. Galbraith, Heneghan, Mckee and Sun, Wu proposed two CRT-RSA efficient cryptosys-tems by choosing small public key exponent and small private CRT-exponent based on distribution theorem of the prime number.Bleichenbacher and May analyzed the schemes in [40,110], and showed that when RSA modulus N can be factored in polynomial time. The basic idea is to generate a linear equation with four variables from CRT-RSA equation and construct cleverly a 3-dimension lattice. Hence, finding the factors of RSA modulus N can be converted into computing the shortest vector of the 3-dimension lattice. The shortest vector in 3-dimension lattice can be always computed by LLL lattice reduction algorithm, so that the above factoring RSA modulus problem will be solved by LLL algorithm.The authors of [3] showed that under the assumption the vector whose length less than Minkowski bound is unique, one could factor the polynomial represented by this short vector, and then compute the CRT-RSA private exponents dp, dq. We point out the argument is not correct in general case in the third chapter of this dissertation, and prove that the vectors in lattice constructed in [3] whose length less than Minkowski bound are not unique generally, that is to say, there exist many vectors shorter than Minkowski bound, and several counterexamples are constructed. Also we discuss whether one can modify the construction of lattice, the method in [3] still work. A negative answer is given, and the reason is analyzed. Also, refinements and more precise statements of the above attack are given, that is, the above problem will be solved in general case. For the special case (?)and dp, (?), the continued fraction approach can be used to solve the problem efficiently, so we improve the Bleichenbacher and May attack.2. Cryptanalysis of RSA system with special prime factors of RSA miodulusDenote the difference p-q between two primes p and q of RSA modulus as A, which is called the prime difference of RSA modulus. Denote ip-jq with small integers i, j as A1, called the prime combination of RSA modulus. de Weger considered the first case that A is small and p and q are same bit-size. A relation between the bound of weak private key d and A was analyzed by de Weger, and he showed that the small prime difference of RSA modulus could improve the bound of weak private key d in Wiener and Boneh, Durfees’papers. Blomer and May presented an equation ex+y≡0 mod (?)(N), and estimated the new weak keys and the range of weak keys will become larger when the prime difference A in the meanwhile. Rencently, Maitra and Sarkar took into account of the case 2q-p, in fact, which is the complementarity of Weger’s result.If the number of bits of p and q are different, the above mentioned attacks are not successful any more. Hence, a general situation will be argued in this paper, allowing that p and q are not same-size, and the relation between weak private key d and prime combination∧1 is also given. First, based on Fermat’s factoring technique, prove that when (?), the primes of RSA modulus can be computed in polynomial time; secondly, when (?), utilizing the continued faction method analyze the relation of∧1 and private key d, and present that when (?), where∧1= Nβandτ＞0, RSA cryptosystem is insecure; furthermore, the relation between weak private key d and prime combination∧1 is also given by lattice reduction method when d＞N0.292 and p, q not same bit-size, the attacks in [9,72,116,117] do not work well, but our methods can succeed and some examples are listed; extend the result of [4] to the case of∧1= ip-jq being small and find more new weak keys and make some statement in [72] more accurate.3. Security analysis of two new knapsack-type public key cryptosystemsKnapsack encryption cryptosystem is based on the subset sum problem, which is proven to be NP-complete, that is to say, there exist no polynomial time algorithm to solve this problem. Merkle and Hellman proposed the first public key scheme based on subset sum problem, which is of important historical significance. After that, many variants have been put forward, but most of them are proven to be insecure. The first polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem was devised by Shamir. The attack makes use of H. Lenstra’s algorithm for integer pro-gramming which runs in polynomial time when the number of variables is fixed, but is inefficient in practice. Adleman points out that cryptanalysis of Merkle-Hellman knap-sack cryptosystem can be converted into the lattice basis reduction problem, so that it is more simple to understand and more efficient to break the Merkle-Hellman knapsack cryptosystem using LLL algorithm. Logarias and Brickell, Odlyzko and Coster et al. go deep into the subset sum problem which is used to design the knapsack using lat-tice reduction problem, assuming that lattice reduction problem may find the shortest vector in the lattice(the number of dimension of lattice is less than 200). Their attack methods are suit for any knapsack algorithm with low density.The Chor-Rivest knapsack scheme was proposed by Chor and Rivest in 1988, which resist against Shamir attack and low density attack when the parameters is se-lected suitably. In ten years, Chor-Rivest has been thought to be secure. Until 1998, Vaudenay proposed a new attack against the Chor-Rivest knapsack scheme analyzing the mathematics characteristic of finite field which the Chor-Rivest scheme bases on. It is called the algebraic attack. Due to no polynomial time quantum algorithm to solve the subset sum problem, many cryptographers suggest the knapsacks are of use for public key cryptosystem after the quantum computer is constructed. Okamoto et.al. presented a new knapsack cryptosystem based on the quantum Turing machine in 2000.In [120,121], a new knapsack-type public key cryptosystem and high-density knapsack-type cryptosystem are respectively designed. The authors in [120,121] presented that these cryptosystems are secure against Shamir attack and low density attack, and based on a new easy knapsack problem. The problem is different from su-perincreasing sequence subset sum problem. The constructions of both cryptosystems are suited for software and hardware implementations. We give an efficient attack by cryptanalysis of parameters selected in [120]. One can find all private keys and break the cryptosystem in [120] in polynomial time using extended Euclidean algorithm or integer factoring algorithm, since the number to be factored is several times greater than private key M. For high-density cryptosystem in [121], we analyze the mathe-matical characteristic between the public key in cryptosystem, and compute the private key-modulus M, and then search all possible values in small range (the range of U or odd number set with i bits) to determine other private keys.更多还原