產生壓縮rsa模數的方法和設備的製作方法

2023-04-23 21:58:26

專利名稱：：產生壓縮rsa模數的方法和設備的製作方法
技術領域：
：本發明總體涉及公共密鑰加密算法，具體涉及Rivest-Shamir-Adleman(RSA)模數的壓縮表示。
背景技術：
：本部分旨在向讀者介紹現有技術中與以下將描述和/或要求權利的本發明各方面有關的各個方面。相信該論述有助於為讀者提供背景信息，以便於更好地理解本發明的各方面。相應地，應理解，要就此而論來閱讀這些陳述，而不應作為對現有技術的認可。令#=/^是兩個大質數的乘積。令e和t/表示一對公共和私有指數，滿足W三1(mod,),其中gcd(e，X(iV))-l並且人是Carmichael函數。由於iV-j^，所以人(7V)-lcm(p—1)。在給定;c〈7V的情況下，公共操作(例如，消息加密或籤名驗證)在於將;c的e次冪對N取模，艮P，計算y:ZmodiV。然後，在給定少的情況下，相應的私有操作(例如，對密文或籤名產生的加密)在於計算/mod^V。根據e和d的定義，顯然可以得到/三x(modAO。通過中國剩餘(CRT模型)，可以以更高的速度來執行私有操作。獨立地計算模數p和q並然後將它們重新組合。在這種情況下，私有參數是(p,《，4,^W，其中4^dmod(p-1)，《=c/mod(《-1)，並且K'mod;。然後，因為CRT(Xp，=xg+《K(;cp—modp]，所以得到/mod7V，其中j^=/pmod/and=/9modg。總之，(二因素)RSA模數iV^;^是兩個大質數p和？的乘積，滿足gcd(MAO,e)=1。如果n表示N的比特大小，則對於某個l<<"來說，p必須在[2"—"°_1/2，2"-"°—l]的範圍內，g在[2"°—1/2，2"°-l]的範圍內，使得2"—1<iV=/^zC函pM&r5We"ce，pages1—10.Springer,1998)提出了產生方法，但是Lenstra的方法不適於受約束的設備，如智慧卡，這是因為第二質數《是遞增地構造的，這可能導致無法接受的過長運行時間。本發明通過以指定的區間產生兩個質數來實施壓縮RSA模數，從而克服了現有技術中問題。因此，壓縮RSA模數得益於高效的質數產生算法，女口，由MarcJoye、PascalPaillier禾口SergeVaudenay(Efficientgenerationofprimenumbers.Ojpfogrop/z/c//aniwareawe/五w6e(i(ie(i—C//EiS2000，volume1965ofiVoto/"Cow/7"^Sc/e證，pages340-354.Springer,2000)提出，並由MarcJoye禾口PascalPaillier(Fastgenerationofprimenumbersonportabledevices:Anupdate.Oj//ogra//z/c//6ec/c/e2》中產生g'，使得gcd(g-l,e)=1，定義以及輸出々={%，^^,^^。在第三優選實施例中，A^是通過對第一質數/的至少一部分進行加密而獲得的。第二方面，本發明針對一種用於產生具有預定部分A^的RSA模數iV的因子的設備，所述RSA模數包括至少兩個因子。該設備包括處理器，所述處理器用於產生第一質數p;獲得形成模數W的一部分的值以及在依賴於p和的區間中產生第二質數《，使得;^是共享的RSA模數。該設備還包括接口，用於至少輸出模數W的無損壓縮表示，所述無損壓縮表示使得能夠對模數iV的無歧義恢復。在第一優選實施例中，所述設備是智慧卡。"共享"被解釋為對於所共享的部分具有相同的值，例如，十六進位的1234567890abcdef和123456789abcdefD共享數字首部中的123456789。現在將參考附圖來描述本發明以及其優選實施例的各特徵和優點，附圖旨在示意而並非限制本發明的範圍，在附圖中，圖1示出了根據本發明優選實施例的用於RSA模數產生的設備。具體實施例方式總體思想總體發明思想在於，固定RSA模數N的大部分(例如，在優選實施例中達到RSA模數N的前一半)，使得可以從區間中任意地得到(而不是如先前提議中建議的遞增地嘗試)形成N的質數。可以使用(公共的)偽隨機數發生器根據隨機短種子來評價RSA模數的大部分，或在用戶之間共享該RSA模數的大部分。這得到了更快的(並且更易於實現的)RSA模數壓縮技術。此外，這樣產生的RSA模數無法與常規的RSA模數相區分(即，在輸出分布方面沒有差別)。最後，這樣產生的RSA模數可以與現有的質數產生技術相兼容(在這種情況下沒有額外的成本)。優選實施例令K/cSw。iV比特RSA模數;V(是兩個大質數/和《的乘積)是可以通過如下方式來產生的。1.使用偽隨機數發生器，根據隨機種子&生成k比特整數A^乂=『1vPRNG(s。))e1^，-1J注意，與2^的或操作確保了的最高有效位是1。本領域技術人員將理解，當然還可以選擇A^的值。2.產生隨機質數pe[2"-n。-"2，2n-n。-1]，使得gcd(p-l,e)-1。3.產生隨機質數^P'P—使得§^(《-1，。=1。如果沒有發現這樣的質數，則重複該過程。4.定義7V,=(^jmod2""並輸出》=(A^.[k,"]}。在給定表示W的情況下，現在容易公共地對相應的"比特RSA模數7V進行恢復，即，A^A^P/，其中^是根據^=2^vPRNG")而獲得的k比特整數。應注意，如果2"《^p，則選擇《的範圍可能是空的。這解釋了為什麼/c應當至多是"o。因此，先前的方法最好將"比特RSA模數壓縮到W比特。最差的情況是關於平衡RSA模數(即，n=2"Q)的，這獲得(最佳地)l+2的壓縮比。第一備選實施例在備選實施例中，模數N的結尾比特是固定的。1.根據種子s。產生WrdvPRNG("))e[1,2^-4。自然，也可以選擇A^。2.產生第一質數Pe[2"言'"，2"—""-lj並且gcd(p-l，e"l。3.令mod211(jf=C+q'2'存在的話)。A/,=4.定義射產生第二質數《。2n—1+1-Cp2"-Cp2》'2>」並且gcd(《-l，e)-l(如果壓並輸出々={^,[;c，"]}。將理解，由於M的最高有效位應當為1，不一定要將M的最高有效位包括在W中。更普遍地，還可以固定iV的一些前導比特和一些尾比特。第二備選實施例所提出的方法可以適於調整由多於2個因子構成的RSA模數，例如，3質數RSA模數或A^/《形式的RSA模數。對於這一點的其他描述，可以有利地參考TsuyoshiTakagi的論文(FastRSA-typecryptosystemmodulo;V^va"cesC，to/ogy-CTKPrO，,volume1462ofiVotoCo，她r5Wewce,pages318-326.Springer,1998)。第三備選實施例在RSA模數W的公共部分(也可以說是A^)在用戶間共享或者對於給定的應用而言對所有用戶都共用時，也可以應用所提出的方法。在這種情況下，不需要傳輸隨機種子W(以及/c和"的值)。設備圖1示出了根據本發明優選實施例的用於產生RSA模數的設備。該產生設備100包括至少一個處理器110、至少一個存儲器120、可以包括單獨的輸入單元和輸出單元在內的通信裝置130、以及可能的用戶接口140。處理裝置適於執行前述方法當中的任一方法。密鑰託管將理解，本發明可以有利地用於密鑰託管用途。在RSA模數7V二j^的情況下，知道大約^(或《)比特的一半就足以使用例如格基規約技術來恢復私有密鑰。因此，如果使用加密密鑰K對^比特的大約一半進行加密，並將其嵌入到公共RSA模數;V的表示中，則知道K的"權限"將能夠根據W重構P，並因此計算出相應的私有RSA密鑰。加密後的p比特可以包含在RSA模數的預定部分中。還將理解，根據本發明的方法還尤其有利地用於智慧卡和其他資源受限的設備中，因為該方法使用相對少的資源。說明書和權利要求(合適的地方)以及附圖中公開的每個特徵是可以獨立地提供或以任何組合的方式提供的。在合適的情況下可以採用硬體、軟體、或兩者結合的形式來實現這些特徵。這裡對"一個實施例"或"實施例"的引用意味著結合實施例所描述的具體特徵、結構、或特性可以包括在本發明的至少一個實現方式中。在說明書中不同地方的出現的短語"在一個實施例中"不一定指的是同一個實施例，也不是必須與其他實施例相排斥的單獨的或備選的實施例。權利要求中出現的參考數字僅僅是說明性的，不應對權利要求的範圍造成限制性的影響。權利要求1、一種產生具有預定部分Nh的RSA模數N的因子的方法，所述RSA模數包括至少兩個因子，所述方法包括以下步驟-產生第一質數p；-獲得形成模數N的一部分的值Nh；-產生第二質數q；以及-至少輸出模數N的無損壓縮表示，所述無損壓縮表示使得能夠實現對模數N的無歧義恢復；所述方法的特徵在於，在依賴於p和Nh的區間中產生第二質數q，使得pq是共享Nh的RSA模數。2、根據權利要求l所述的方法，其中，所述預定部分AV(立於RSA模數的首部。3、根據權利要求2所述的方法，其中，所述RSA模數是n比特模數，所述預定部分W包括/c個比特，並且在區間pe[2"-"2'2一-1]中產生第一質數^使得gcd(p-l，e)-1;在區間p中產生第二質數？，使得gcd(^l,e)=l;以及iV=Ag|iV,，其中M=mod2"-K。4、根據權利要求l所述的方法，其中，所述預定部分AVf立於RSA模數的尾部。5、根據權利要求4所述的方法，其中，在區間"12"—"°—1/2,2"—"°-"中產生第一質數P，使得gcd(^-l，e一l;第二質數《是通過計算q-c+q'^產生的，其中P，並且《'是在區間《2n-1十1-Cp2n-Cp~~^^'2》中產生的，使得gcd(《-l,ehl，輸出々=/^，&/^""。6、根據前述任一權利要求所述的方法，其中，是通過對第一質數P的至少一部分進行加密而獲得的。7、一種用於產生具有預定部分A^的RSA模數7V的因子的設備000)，所述RSA模數包括至少兩個因子，所述設備包括處理器(110)，用於-產生第一質數p;-獲得形成模數W的一部分的值A^以及-在依賴於P和A^的區間中產生第二質數《，使得/^是共享A^的RSA模數；以及接口(130)，用於至少輸出模數iV的無損壓縮表示，所述無損壓縮表示得能夠實現對模數W的無歧義恢復。8、根據權利要求7所述的設備，其中，所述設備是智慧卡。全文摘要本發明提供了一種產生具有預定部分Nh的RSA模數N的因子的方法和設備，所述RSA模數包括至少兩個因子。產生第一質數p；獲得形成模數N的一部分的值Nh；在依賴於p和Nh的區間中產生第二質數q，使得pq是共享Nh的RSA模數；以及輸出使得能夠計算出模數N的信息。文檔編號H04L9/30GK101622817SQ200880006099公開日2010年1月6日申請日期2008年2月19日優先權日2007年2月27日發明者馬克·喬伊申請人:湯姆森許可貿易公司