本文選題：格　切入點：LLL算法　出處：《北京交通大學(xué)》2017年碩士論文

【摘要】：隨著計算機的普及和發(fā)展,人們對信息安全的關(guān)注度也越來越高。信息安全的基礎(chǔ)正是密碼學(xué)。Diffie和Hellman在1976年發(fā)表的《New directions in cryptography》一文中提出了公鑰密碼學(xué)的概念,揭開了現(xiàn)代密碼學(xué)的序幕。1978年,Rivest、Shamir和Adleman提出了著名的RSA公鑰密碼體制。它是第一個基于整數(shù)分解難題的公鑰密碼算法,也是第一個能夠同時應(yīng)用于數(shù)據(jù)加密和數(shù)字簽名的密碼算法。RSA算法一經(jīng)提出就受到了廣泛關(guān)注,并被迅速應(yīng)用于網(wǎng)絡(luò)和信息安全的各個領(lǐng)域。對RSA公鑰密碼體制的安全性研究一直是密碼學(xué)研究的重點之一。自算法提出以來,RSA經(jīng)歷了各種各樣攻擊的考驗,但至今還沒有算法能夠威脅標(biāo)準(zhǔn)RSA密碼體制的安全性。但是在實際應(yīng)用中,人們?yōu)榱思涌旒咏饷?簽名驗證)的速度,常常會使用特殊的RSA密碼體制,如使用小加(解)密指數(shù),或者是基于中國剩余定理的RSA等,但是這樣也在一定程度上犧牲了 RSA密碼的安全性。格基約化理論是數(shù)學(xué)中的一個重要理論。自1982年,A·K·Lenstra、H·K·Lenstra和L·Lovasz提出了著名的LLL算法成功分解有理系數(shù)多項式后,格基約化理論被廣泛應(yīng)用于密碼學(xué)分析中,成為密碼學(xué)研究的重要工具之一。本文針對使用了小解密指數(shù)的RSA,利用LLL算法,進行了一系列攻擊。本文完成的工作主要包括:(1)回顧并詳細分析Wiener、Ernst等人的攻擊方法及所用技術(shù)。(2)研究LLL算法的實現(xiàn)并分析其效率,提出了使用LLL算法來攻擊小解密指數(shù)RSA的一種快速方法,通過實驗及分析實驗結(jié)果,在小解密指數(shù)條件下,與Wiener的方法相比,本文的攻擊要求d的上界更高,且速度更快。(3)在Coppersmith理論的基礎(chǔ)上,結(jié)合私鑰部分比特泄露的信息,給出了一種提高解密密鑰d的上界的攻擊方法,并給出實驗結(jié)果。
[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.
【學(xué)位授予單位】：北京交通大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TN918.1

【參考文獻】

相關(guān)博士學(xué)位論文 前1條

1 余位馳;格基規(guī)約理論及其在密碼設(shè)計中的應(yīng)用[D];西南交通大學(xué);2005年

，

本文編號：1698643