基于格的RSA小解密指数攻击研究

发布时间：2018-04-02 03:37

本文选题：格　切入点：LLL算法　出处：《北京交通大学》2017年硕士论文

【摘要】：随着计算机的普及和发展,人们对信息安全的关注度也越来越高。信息安全的基础正是密码学。Diffie和Hellman在1976年发表的《New directions in cryptography》一文中提出了公钥密码学的概念,揭开了现代密码学的序幕。1978年,Rivest、Shamir和Adleman提出了著名的RSA公钥密码体制。它是第一个基于整数分解难题的公钥密码算法,也是第一个能够同时应用于数据加密和数字签名的密码算法。RSA算法一经提出就受到了广泛关注,并被迅速应用于网络和信息安全的各个领域。对RSA公钥密码体制的安全性研究一直是密码学研究的重点之一。自算法提出以来,RSA经历了各种各样攻击的考验,但至今还没有算法能够威胁标准RSA密码体制的安全性。但是在实际应用中,人们为了加快加解密(签名验证)的速度,常常会使用特殊的RSA密码体制,如使用小加(解)密指数,或者是基于中国剩余定理的RSA等,但是这样也在一定程度上牺牲了 RSA密码的安全性。格基约化理论是数学中的一个重要理论。自1982年,A·K·Lenstra、H·K·Lenstra和L·Lovasz提出了著名的LLL算法成功分解有理系数多项式后,格基约化理论被广泛应用于密码学分析中,成为密码学研究的重要工具之一。本文针对使用了小解密指数的RSA,利用LLL算法,进行了一系列攻击。本文完成的工作主要包括:(1)回顾并详细分析Wiener、Ernst等人的攻击方法及所用技术。(2)研究LLL算法的实现并分析其效率,提出了使用LLL算法来攻击小解密指数RSA的一种快速方法,通过实验及分析实验结果,在小解密指数条件下,与Wiener的方法相比,本文的攻击要求d的上界更高,且速度更快。(3)在Coppersmith理论的基础上,结合私钥部分比特泄露的信息,给出了一种提高解密密钥d的上界的攻击方法,并给出实验结果。
[Abstract]:With the popularization and development of computer, people pay more and more attention to information security. The foundation of information security is the concept of public key cryptography, which was put forward in the paper "New directions in cryptography" published by .Diffie and Hellman in 1976. In 1978, Rivester Shamir and Adleman put forward the famous RSA public key cryptosystem. It is the first public key cryptosystem based on integer decomposition problem. It is also the first cryptographic algorithm that can be applied to both data encryption and digital signature. The research on the security of RSA public key cryptosystem has been one of the emphases of cryptography. Since the algorithm was put forward, it has been tested by all kinds of attacks. But there is no algorithm to threaten the security of standard RSA cryptosystem. But in practical applications, people often use special RSA cryptosystem to speed up encryption and decryption (signature verification). For example, using a small additive (solution) secret index, or RSA based on the Chinese residue theorem, However, the security of RSA cryptography is also sacrificed to some extent. Lattice reduction theory is an important theory in mathematics. Since 1982, when A K LenstraH K Lenstra and L Lovasz successfully decomposed rational coefficient polynomials, the famous LLL algorithm has been successfully decomposed. Lattice reduction theory has been widely used in cryptographic analysis and has become one of the important tools in cryptography. In this paper, we use LLL algorithm to solve the problem of RSAs which use small decryption index. A series of attacks have been carried out. The work accomplished in this paper mainly includes reviewing and analyzing in detail the attack methods and techniques used by Wienerer Ernst et al.) studying the implementation of LLL algorithm and analyzing its efficiency. This paper presents a fast method to attack small decryption index (RSA) by using LLL algorithm. Through experiment and analysis of experimental results, under the condition of small decryption index, the upper bound of d is higher than that of Wiener. On the basis of Coppersmith theory, a new attack method to improve the upper bound of decryption key d is presented, and the experimental results are given.
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TN918.1

【参考文献】