[發(fā)明專利]基于密碼學(xué)技術(shù)應(yīng)用的大數(shù)快速分解方法

無效

• 申請(qǐng)?zhí)枺?/td>: 201210197737.8
• 申請(qǐng)日: 2012-06-15
• 公開（公告）號(hào): CN102769528A
• 公開（公告）日: 2012-11-07
• 發(fā)明（設(shè)計(jì)）人: 劉詩章;陳豫生;賀漫古
• 申請(qǐng)（專利權(quán)）人: 劉詩章;陳豫生;賀漫古
• 主分類號(hào): H04L9/30
• 分類號(hào): H04L9/30;G06F7/72
• 代理公司: 北京華夏博通專利事務(wù)所(普通合伙) 11264
• 代理人: 劉俊

所屬技術(shù)領(lǐng)域

本發(fā)明涉及信息安全和密碼學(xué)技術(shù)應(yīng)用領(lǐng)域，特別是涉及一種基于密碼學(xué)技術(shù)應(yīng)用的大數(shù)快速分解方法。

背景技術(shù)

在現(xiàn)代密碼學(xué)中，密碼的安全性是第一位的。由于數(shù)學(xué)問題的算法求解的復(fù)雜性可通過計(jì)算復(fù)雜性理論來描述，并可為破譯密碼和計(jì)算復(fù)雜度提供實(shí)際的度量方法。因此，當(dāng)今的大部分密碼系統(tǒng)，常常可歸結(jié)為求解某個(gè)數(shù)學(xué)問題。而計(jì)算復(fù)雜性理論中的一些典型的數(shù)學(xué)問題又給人們提供了設(shè)計(jì)實(shí)用安全的高強(qiáng)度密碼系統(tǒng)的基礎(chǔ)。例如基于NPC類中的背包問題而設(shè)計(jì)的公開鑰密碼系統(tǒng)，基于NP問題的大數(shù)因式分解問題的RSA公開鑰密碼系統(tǒng)等。大數(shù)分解是數(shù)學(xué)領(lǐng)域的一大難題，在密碼學(xué)中，1977年，Rivest，Samir和Adleman聯(lián)合提出一種基于數(shù)論中歐拉定理的公鑰密碼系統(tǒng)，簡(jiǎn)稱RSA公鑰系統(tǒng)，RSA公鑰密碼體制就是基于這種假設(shè)：找到兩個(gè)大的素?cái)?shù)相對(duì)不是很難，但是把一個(gè)大的合數(shù)分解成它的素因子形式卻極為困難。這個(gè)體制運(yùn)行如下：

C＝M^e(mod?N)????M＝C^d(mod?N)

其中，M是明文；C是密文；N＝p·q是模數(shù)，p和q是不同的大素?cái)?shù)；e是公開的加密指數(shù)(密鑰)，d是私有的解密指數(shù)(密鑰)且滿足ed≡1(modφ(N))，(N，e)必須公開，但是d(還有φ(N))需要保密。由于函數(shù)f：M→C是單向陷門函數(shù)，因?yàn)橛煽焖僦笖?shù)算法它是容易計(jì)算的，而它的逆f^-1：C→M是難以計(jì)算的，對(duì)于不知道解密密鑰(陷門信息)d的人而言，為了找到d他們將不得不對(duì)n進(jìn)行因式分解，并計(jì)算φ(n)，然而對(duì)于那些知道d的人而言，則f^-1的計(jì)算如同f的計(jì)算一樣的簡(jiǎn)單，這就是RSA密碼思想。由于RSA的安全性相對(duì)較高，因此在當(dāng)今公鑰系統(tǒng)中得到廣泛應(yīng)用。RSA的安全性是基于難于對(duì)大數(shù)進(jìn)行因子分解，后者是數(shù)學(xué)上的一個(gè)著名難題。由于大數(shù)分解在RSA公鑰系統(tǒng)中的實(shí)際用途，導(dǎo)致了對(duì)它進(jìn)行破譯和對(duì)它安全性進(jìn)行評(píng)估的雙重現(xiàn)實(shí)需求。目前，最有效的因子分解算法，以運(yùn)行時(shí)間特征分類，主要可歸為以下兩大類：1.運(yùn)行時(shí)間主要依賴于待分解整數(shù)N的大小，并不十分依賴于找到的因子p的大小2.運(yùn)行時(shí)間主要依賴于N中p(找到的N的因子)的大小。目前，被采用的因子分解方法有很多，最簡(jiǎn)單的因子分解方法為試除法，它是通過嘗試的所有可能的因子來得到n的完整素因子分解式：n＝p₁·p₂····p_t，p₁≤p₂≤···≤p_t。試除法檢測(cè)對(duì)排除小因子是很有效的，但此方法不能用來進(jìn)行完全分解，除非n是一個(gè)很小的數(shù)，比如說是n＜10⁸；還有費(fèi)馬分解因子方法，該方法是對(duì)于一個(gè)給定的大于1的奇數(shù)n，可用此算法來確定n的不超過的最大因子。而目前被廣泛使用的通用整數(shù)因子分解方法有下述三種，即：連分?jǐn)?shù)方法(簡(jiǎn)稱CFRAC)、二次篩法(簡(jiǎn)稱QS)和數(shù)域篩法(簡(jiǎn)稱NFS)。連分?jǐn)?shù)方法(簡(jiǎn)稱CFRAC)是第一個(gè)現(xiàn)代通用的因子分解方法。二次篩法(QS)由Carl?POmerance于1982年首先提出的，由于運(yùn)算的復(fù)雜性，運(yùn)算的時(shí)間一直是各類算法關(guān)注的首要問題。1983年，Davis，Holdredge和Simmons成功地選用二次篩選法分解了69位十進(jìn)制數(shù)，1989年Lerntra和Manasse又利用這個(gè)方法把計(jì)算分配給數(shù)百臺(tái)離得很遠(yuǎn)的工作站分解了106位的十進(jìn)制數(shù)，1994年4月，Atkins，Graff，Lenstra和Leyland再次利用二次篩選法分解了稱為RSA-129的129位十進(jìn)制的數(shù)，組織了600名專家、1600臺(tái)計(jì)算機(jī)聯(lián)網(wǎng)計(jì)算了9個(gè)月，獲得成功，由此說明RSA的安全性作為密碼系統(tǒng)，n應(yīng)大于200位。上世紀(jì)末和本世紀(jì)初，大數(shù)分解又取得了新的進(jìn)展，1999年，RSA-155(512bits)被成功分解，花了五個(gè)月時(shí)間(約8000MIPS)和224CPU?hours，是在一臺(tái)有3.2G中央內(nèi)存的Cray?C916計(jì)算機(jī)上完成的；2002年，RSA-158也被成功因數(shù)分解。盡管上述分解因子的嘗試工作都取得了成功，但其破解的復(fù)雜性和艱難程度也由此可見一斑。然而，目前還沒有任何一種算法能夠完全解決大數(shù)分解問題，前面提到的幾種算法大都是利用大數(shù)的特定構(gòu)成，對(duì)大數(shù)進(jìn)行的嘗試性分解，很多情況下都不能成功，因此，對(duì)密碼設(shè)計(jì)者而言，只要能夠避開這幾種算法的假定條件，理論上講，他設(shè)計(jì)的密碼就是相對(duì)安全的。對(duì)此，本申請(qǐng)人于2011年提出了專利名稱為：“一種適用于信息加密技術(shù)應(yīng)用的素?cái)?shù)族快速生成方法”，專利申請(qǐng)?zhí)枮椋?01110253413.7的發(fā)明專利，目的就是能夠避開現(xiàn)有技術(shù)幾種算法的假定條件，利用素?cái)?shù)族快速生成方法，設(shè)計(jì)出相對(duì)安全的密碼，本發(fā)明就是在此專利技術(shù)上進(jìn)行的改進(jìn)專利。