Cryptanalysis Of RSA And Knapsack Public Key Cryptosystem

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.