Application Of Lattice Theory In Analysis Of Variant RSA Algorithms

The research on the application of the RSA algorithm has a profound impact on the exploration of the public key cryptosystem,and the research on the RSA attack method has always been a popular direction in the field of cryptography.In addition to the standard RSA algorithm in the conventional sense,there are also some other types of variant RSA algorithms.Some of these variant RSA algorithms are to improve the encryption and decryption efficiency of the original RSA algorithm;some are to share the cost loss of encryption and decryption.;others are for defense against known attacks,etc.This paper uses lattice analysis technology to study the security of the variant RSA algorithm that satisfies the key equation ed-k（p²-1）（q²-1）=1 for public and private key pairs.The modulus N of the variant RSA algorithm is calculated.The N=p·q decomposition problem is transformed into a problem of solving modular equations or small roots of integer equations in polynomial time.The research contents mainly include:（1）Given the public and private key pairs（e,d）are known,a deterministic algorithm for modulo decomposition of this variant RSA algorithm is given,which can decompose N=P·q in polynomial time.When the public-private key pair （e,d） satisfies N²<ed<N³,the candidate value is continuously tested by the enumeration method to find the appropriate k value to calculate the key equation,so as to decompose the modulus N,the time complexity is O（2log²N）.When the public-private key pair （e,d） satisfies N³<ed<N⁴,the modular equation solving problem is transformed into the solving problem of short vectors on the lattice by using lattice theory analysis skills to complete the decomposition of the RSA modulus N,The time complexity is O(2log¹²N).（2）Under the condition of e<N,a small encryption exponential attack on the variant RSA algorithm is proposed,that is,the public-private key pair satisfies e<d.We refine the equations satisfied by e and d,and use the LLL lattice reduction algorithm to find Linear combination of integers,and then solve the three-variable modular equation through linearization techniques to obtain the decomposition result of the small encrypted exponential attack -（p+q）²,set the public and private key pairs e,d,when ed-k（p²-1）（q²-1）=1 Under the condition of,the modulus N can be effectively decomposed,and the time complexity is O（log e·2（log²N））.（3）Under the known condition of d₀=dmod 2^n/4,a partial private key leakage attack method for this variant RSA cryptographic algorithm is proposed.Let the public-private key pair e,d,under the condition of ed-k（p²-1）（q²-1）=1,when the attacker has obtained some low-order bits of the decryption indexd,then You can use this part of the acquired bit information to restore the entire private key,which can effectively decompose the modulus N,and the time complexity is O（2^V Klog K·T（n））.