Rsa-type Public Key Cryptosystem The Decryption Exponent Attack

With the development of economy and the advancement of computer. people are paying more and more attention to the information security. In 1949, Shannon published the Communication The-ory of Secrecy System, opening the mysteries of modern cryptography. In 1976, Diffie and Hellman put forward the concept of public key cryptography in the New Directions in Cryptography for the first time, thus creating the new era in public key cryptography. Later in 1978, Rivest, Shamir and Adleman proposed the first concrete public key cryptography RSA which based on large integer fac-torization problem. From then on, a series of public key cryptographies have come into being. For example, ELGamal raised the public key cryptosystem and a signature scheme on the basis of discrete logarithms in 1985; Miller's elliptic curve cryptography which based on the discrete logarithm prob-lem of elliptic curve in 1986; in 2000, Lenstra and Verheul put forward the XTR public system based on the trace of a subgroup of the finite field multiplicative group (its security is also based on the finite field of discrete logarithm problem); Ajtai-Dworkls, GGH and NTRU are also the basis of the problem of lattice; public key system based on braid Group; and McEliece public key system based on error correcting code, etc.On the other hand, RSA public key system has also been improved by cryptographers. Such as Kayama, Maurer, Okamoto and Vanstone came up with the new public-key scheme based on elliptic curves over the ring Zn (KMOV public key scheme) in 1991; in 2005, SunQi presented RSA-type public key Cryptosystem, which based on the conic curves over the ring Zn;in 2007, SunQi also pre-sented RSA-type public key Cryptosystem, but which based on the generalized conic curves over the ring Zn. In this article, all these improved public key systems are called RSA-type public key cryp-tosystem. In RSA-type public key cryptosystem the encryption exponent e and decryption exponent d satisfy ed≡1 (mod Nn),Nn=1cm{p±1.q±1}.There are many attacks on the RSA public key cryptosystem. This paper mainly extend the two attacking methods-continued fraction attack and lattice attack-to the whole RSA-type public key cryptosystem and get some relevant results as follows:(1) Concerning the expansion of continued fraction attack on RSA-type public key cryptosystem. ed=1 (mod Nn), when Nn is (p+1)(q+1)/2, (p+1)(q-1)/2, (p-1)(q+1)/2 and (p-1)(q-1)/2, respectively, the corresponding boundary of dis 1^1/1/(4 2^1/2+2)N(1/4),²(1/2)2N(1/4) 1/2N(1/4) and (1/4)¹/(1/4)2^1/2N(1/4); When the Nnis lcm{p+1,q+1}, lcm{p+1.q-1}, lcm{p-1,q+1} (?) and lcm{p-1.q-1}. respectively, corresponding to the boundary of 1^1/1/(4 2^1/2+2)gN 1/(2g)⁽1/(2g)N(1/4), 1/(2 g^1/g)N(1/4) and 1^1/1/(4(2g)⁽1/(2g)N(1/4). That is, when d is less than the sector index to decrypt, you can solve for the private key (d.p. q) through public key (N,e) Which is to crack the password for the system at this time.(2) This paper also propose that it is can use Lemma 2 to improve the decryption exponent d of RSA-type public key cryptosystem, and Lemma 2 is as following: Lemma 2.serαbe a real number,a and b is a positive integer prime,and k≥1/2.If|α-a/b|＜k/(b2), then a/b is a continued fraction expansion of the (pm)/(qm),or one of the follwing conditions: (a)a/b=(spm+tpm-1)/(sqm+tqm-1),where sr<2k; (b)a/b=(spm-tpm-1)/(sqm-tqm-1),where st<2k; (c)a/b=(spm-1+tpm-1)/(sqm-1+tqm-1),where st1/(3+12α-12γ)-8γ)(where ged(p-1.q-1)=N(?)e=N(?) soγis a small positive number,andαis a number close to 1),the method of lattice attack can be used to crack the system.The other circumstances of the RSA-type public key cryptosystem can be similar to do and obtain the corresponding results.