Several Attacks On RSA-Type Cryptosystems Over Elliptic Curves And Conic Curves

In 96Eurocrypt, Coppersmith[11] provides an effective method to solve polynomial problem on module, which leads to the solution of low bits in plain text, that is the low bits m₀ for the polynomial (m + m₀)^e = modiV. This is the first time to use LLL arithmetic to analysis RSA cryptosystem. giving the precedence to analyze RSA by way of searching shortest lattices .According to Coppersmith's marvelous work and brilliant result for analyzing RSA cryptosystem, a lot of academics do some significant research which derived from Coppersmith's approach. In 98, Howgrave-Graham [20] find a new but more easily understandable way, which is proved to be equivalent to Coppersmith method. However, since his approach is limited to the improvement of Coppersmith's way of solving univariant modula polynomial, it can only be utilized to recover the low bits of plain text of RSA cryptosystem.In 99Crypto, Boneh[5] promotes this kind of method into solving bivariate polynomial, which could be utilized to solve the modula polynomial relating to public key and private key. It initiates the methods of analyzing RSA private key using LLL arithmetic. Before he provided this method, Wiener[38] had once used continued fraction to recover private key less than O(N^0.25). So the approach of Boneh using LLL arithmetic to analyze RSA private key is more effective for the reason that it will lead to the solution of low bits secret key d less than N^0.292. Recently, other academics in the field follow the works of Coppersmith and Boneh, and they also give some profound research in solving RSA by means of using LLL to solve polynomial on module, for instance, May, Blomer[3] and Hinek[16] have expended this method to solve partial unknown bits of secret key on the condition that some high or low bits had already been exposed. Hinek and Teske[16] have analyzed the situation that n is composed by r > 2 primes, which have balance character.In CCICS'2007, Fan-yu Kong and other researchers find Public-Key system based on Conic system can also be attacked if the private key is low bits, using the similar methods provided by Boneh. They also give an attack based on LLL reduction under the condition that GCD of p + 1 and q + 1 is 2.In this thesis,we shall talk about how to solve the Public-Key cryptography system on elliptic curves and conic, which is the most common Public-Key system based on ring. We shall talk about our approach of solving trivariant polynomial under a more common condition that GCD of p + 1 and q + 1 is bigger than 2. We get the result that if the private key d is less than O(N^1/4-3/2γ), the low bits private key could be recovered by using LLL arithmetic to solve polynomial on module. (γstands for the index of GCD of p + 1 and q + l,that is d₁ = O(N^γ)). All in all, our methods deals with a more prevalent condition towards Boneh's condition.This dissertation continues to analyze the conditions of partial key exposure attack. This is the expand of Blomer and May's way of analyzing RSA to RSA type cryptosystem over elliptic curves and conic curves, that is we can recover the unknown parts of private key after exposed some high or low bits:If the high bits of private key had been known, that is (?) = O(N^β), whenβ≤1/2, and unknown low bits is in the interval O(N^{4_γ+3/4-β-δ})≤d₀≤O(N^{5/4+β-4_γ-δ}),the private are able to be recovered;If the high bits of private key had been known, that is (?) = O(N^β), whenβ≥1/2, and unknown low bits is in the interval O(N^{4_γ+3/4-δ-β}≤d₀≤O(N^{9/4-β-4_γ-δ},the private are able to be recovered.Similar, if amount of low bits had been exposed, the unknown high bits can also be recovered: if low bits of private key had been known, that is (?) = O(N^β), when the unknown high bits d₀≤O(N^{5/4-2γ-1/4(?)}), the private are able to be recovered.We also expand the methods of-Hinek,Teske analyzing n composed by balance primes into RSA cryptosystem over elliptic and conic curves. When n has r balanceprimes, private key d could be solved if d≤O(N^{-1/2r+3/2-2_γ-(?)}).Meanwhile,even if the private key is big, when we know some unknown high or low bits and unknown bits satisfy some condition, we could also recover the unknown parts:If the high bits of private key had been known, that is (?) = O(N^β), whenβ≤1/r, and unknown low bits is in the interval O(N^{4γ+3/2-3/2r+β-δ})≤d₀≤O(N^{1/2+3/2r+β-4γ-δ}), the private could be able to be recovered.If the high bits of private key had been known, that is (?) = O(N^β), whenβ≥1/r, and unknown low bits is in the interval O(N^{4γ+3/2-3/2r-β-δ}≤d₀≤O(N^{3/2+3/2r-β-4γ-a}),the private could be able to be recovered.If low bits of private key had been known, that is (?) = O(N^β), when the unknown high bits d₀≤O(N^{-1+3r/2r-2γ-1/2r(?)}), the private are able to be recovered.