格理論及格基約減算法在公鑰密碼分析學(xué)中的應(yīng)用研究.pdf

1、近年來，格理論及格基約減算法作為一個(gè)用來高效的分析、攻擊公鑰密碼系統(tǒng)的工具，其角色正在變得越來越重要。格基約減算法在1990年對(duì)基于背包問題的密碼系統(tǒng)的成功攻擊，正式確立了其在密碼分析學(xué)中的地位。而自從1996年Coppersmith提出用LLL算法對(duì)根較小的整系數(shù)單變量模等式及雙變量等式的解法以來，對(duì)其方法的各種應(yīng)用更是成了分析RSA系統(tǒng)及其變種的有力工具。迄今為止，各種分析方法及思路百花齊放、層出不窮，許多成果都是近幾年提出的，比如

2、Boneh和Durfee在2000年提出的對(duì)RSA的低指數(shù)攻擊、B1ǒmer、Ernest等人提出的部分密鑰泄漏攻擊、May等人對(duì)RSA變種體制的攻擊，等等。這些引人注目的成果表明，使用格基約減算法的攻擊(沒有誤會(huì)的情況下后文簡稱“格攻擊”)作為一種高效率的分析方法，在現(xiàn)代密碼分析學(xué)中扮演著極其重要的地位(事實(shí)上，格攻擊是與數(shù)域篩法并列的最有效的分解RSA模的分析工具)。不但如此，而且該方法的應(yīng)用潛力巨大，有許多新的價(jià)值等待人們來挖掘。

3、 　本論文的主要成果是：使用新的方法分析了在RSA體制中已知一部分p求N的分解的問題；此方法在實(shí)踐中也可以作為一種對(duì)RSA公鑰體制的部分泄漏攻擊來使用。該問題的最好結(jié)果是Coppersmith在1996年提出的上界，即已知p的（1/4log2N）高位比特可以在多項(xiàng)式時(shí)間內(nèi)分解N。本文在使用新的方法進(jìn)行分析，證明了在公鑰e≈1(這是RSA體制參數(shù)選擇的通常情況)并且私鑰d<0.483時(shí)用較少的p的高位比特就可以在多項(xiàng)式時(shí)間內(nèi)分解N