With the rapid development of computers and internet communication, people begin to pay more attention on protection of personal digital information and a variety 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, publickey 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 introduced the revolutionary concept of publickey cryptography. Rivest, Shamir, and Adleman in MIT discovered the first practical publickey scheme, now referred to as RSA, which is one of the most popular publickey cryptosystems. It can be used to encrypt the plaintext and sign a message. In 1978, Merkle and Hellman designed a knapsack public key cryptosystem based on subset sum problem, called MerkleHellman cryptosystem. After that, there are many publickey schemes brought forward, for example, McEliece publickey encryption algorithm, Rabin publickey encryption algorithm, ElGamal encryption algorithm and signature algorithm, Elliptic curve cryptosystems(ECC), GoldwasserMicali probabilistic encryption algorithm, et al.Nowdays, RSA encryption and signature algorithms and ElGamal signature algorithm 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 security. Therefore, cryptanalysis of the publickey cryptosystems is extremely important for theoretical significance and practical value. Since publickey cryptosystems were invented, cryptographers have been applying oneself to security research of publickey 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 analysis 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):= (p1)(q1), 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 eth 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 p1 method, quadratic sieve method, elliptic curve method, general number field sieve method. Currently, the fastest technique for integer factorization is general number field sieve method, the memory/space complexity of which are subexponential. 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 512bit RSA modulus. Cryptographers suggest that it would be prudent to phase out the use of 1024bit 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 largescale 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 reduction algorithmLLL, 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 technique 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 remaindering 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 CRTcomponents, decryption and signature generation are four times faster than standard decryption and signature. Galbraith, Heneghan, Mckee and Sun, Wu proposed two CRTRSA efficient cryptosystems by choosing small public key exponent and small private CRTexponent 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 CRTRSA equation and construct cleverly a 3dimension lattice. Hence, finding the factors of RSA modulus N can be converted into computing the shortest vector of the 3dimension lattice. The shortest vector in 3dimension 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 CRTRSA 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 pq between two primes p and q of RSA modulus as A, which is called the prime difference of RSA modulus. Denote ipjq 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 bitsize. 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 2qp, 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 samesize, 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 bitsize, 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= ipjq being small and find more new weak keys and make some statement in [72] more accurate.3. Security analysis of two new knapsacktype public key cryptosystemsKnapsack encryption cryptosystem is based on the subset sum problem, which is proven to be NPcomplete, 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 MerkleHellman cryptosystem was devised by Shamir. The attack makes use of H. Lenstra's algorithm for integer programming which runs in polynomial time when the number of variables is fixed, but is inefficient in practice. Adleman points out that cryptanalysis of MerkleHellman knapsack cryptosystem can be converted into the lattice basis reduction problem, so that it is more simple to understand and more efficient to break the MerkleHellman 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 lattice 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 ChorRivest knapsack scheme was proposed by Chor and Rivest in 1988, which resist against Shamir attack and low density attack when the parameters is selected suitably. In ten years, ChorRivest has been thought to be secure. Until 1998, Vaudenay proposed a new attack against the ChorRivest knapsack scheme analyzing the mathematics characteristic of finite field which the ChorRivest 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 knapsacktype public key cryptosystem and highdensity knapsacktype 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 superincreasing 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 highdensity cryptosystem in [121], we analyze the mathematical characteristic between the public key in cryptosystem, and compute the private keymodulus 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.
