一種減少rsa密鑰變量存儲空間的方法
2023-07-01 10:57:16 1
專利名稱：一種減少rsa密鑰變量存儲空間的方法
技術領域：
本發明涉及一種減少RSA密鑰變量存儲空間的方法，屬信息安全和網絡安全的技術領域。
背景技術：
隨著全球性信息化浪潮的出現，信息安全和網絡安全日益受到人們的關注。信息安全和網絡安全技術的應用已深入到大型、關鍵性業務系統如EFT和POS機系統(electronic fund transfer and point of salessystems)等。然而對於用小容量存儲設備的系統而言，由於計算能力的限制和存貯設備介質不能存儲大數據的物理特性，這些技術的應用受到了限制。
公鑰密碼算法是Difte和Hellman在1976年提出的。他們利用一種特別的數學變換，冪運算，提出基於離散對數難題的密鑰分配協議。用戶進行兩次模冪運算，就可以得到與其相關的一方的相同的密鑰。由於這個變換是單向的，所以無法用於加密和解密。
在美國專利US 4,218,582的中，Hellman和Merkle利用Difte和Hellman的結果提出一種消除安全信息通道的方法。1978年，Rivest，Shanir和Adleman提出公鑰加密算法RSA，同時還提出數字籤名，即電子籤名的概念。他們為該算法申請了美國專利，並獲得授權，專利號為US 4,405,829。該算法是利用兩個大素數相乘，得出一個模數N，取一個公鑰e，然後通過這兩個大素數計算出私鑰d，公開公鑰e和模數N。這樣，如果用戶A要給公鑰為e和模數為N的用戶B發送消息M的話，則只需用模數N和公鑰e對消息M進行模冪運算，得到密文C。用戶B接到密文C後，用私鑰d進行解密。上述過程的逆向運算正好可以用來做電子籤名，以證實消息M的完整性、可認證性和不可否認性，因為私鑰d只有用戶B一人知道。
由於公鑰密碼的密鑰量巨大，在卡上認證系統裡公鑰密碼一直未被看好。在美國專利US 4,438,824中，Mueller-Schloer用附加數據卡的辦法提出了一個身份驗證系統。在該系統裡，多個終端與安全服務站相連，每個終端都有一個CPU、內存、讀卡器和合數模。CPU通過合數模控制數據的加密和解密。而安全服務站的工作也類似，以此來進行驗證，這個系統同時兼容了美國數據加密標準算法DES和公鑰加密算法RSA。
但在商業上，這個系統至今仍未被EFT和POS機系統所接受。因為這些系統採用容量很小的磁條卡作存儲介質，來存儲私人鑑別號碼(PIN)，以認證用戶身份的合法性。在80年代末和90年代初，人們開始尋求解決將密鑰變量存儲在小容量存儲介質上的辦法。
在美國專利US 4,408,203中，Canpbell用對稱密碼(私鑰密碼)的算法，提出了一個解決法方案。此外，在美國專利US 4,423,287中，Zeidler用一次密鑰的方法解決EFT和POS機系統的用戶身份認證問題。由於受到磁條卡的容量限制，人們(包括Canpbell和Zeidler)始終沒能將更安全的RSA應用到EFT和POS機系統上去。
目前安全的RSA合數模是1024比特的整數，而銀行等機構的磁條卡上的3個磁軌只能存放316，160和432比特的信息，這對於長度為1024比特的合數模、公鑰、私鑰都是遠遠不夠的。美國專利US4,736,423雖公開了一個400比特的算法，但由於該算法本身的局限性，該算法無法推廣到長度為1024比特的RSA上，而且當時小指數攻擊方面的技術沒有出現，在今天看來，這個方法可能是完全不安全的。
所以對公鑰密碼系統在銀行或金融系統的應用，主要取決於兩個因素的發展，即要麼大容量的存儲技術出現，要麼找到一種減少密鑰存儲空間的技術。由於存儲技術的局限性，主要的出路便是發展減少密鑰存儲空間的技術。從實用和安全的角度來看，這又是一對矛盾。因此既安全又密鑰存儲空間小的密鑰生成技術更是重中之重了。
發明內容
本發明要解決的技術問題是提出一種減少RSA密鑰變量存儲空間的方法，即減少RSA密鑰變量存儲空間的算法。該方法是一項生成既安全、密鑰存儲空間又小的密鑰的技術，有以下優點能為用小容量存儲器，磁條卡的金融電子系統，如EFT和POS機系統等生成用於身份認證、鑑別和消息認證所需的高強度密碼。
本發明採用以下技術方案使上述的技術問題得到解決。根據目前EFT和POS機系統用磁條卡進行身份認證的特點，為滿足RSA安全性的要求RSA密鑰變量的長度應為3072比特，其中，公鑰PK、私鑰SK和模數N各佔1024比特；密鑰公鑰PK和私鑰SK應能抵抗小指數攻擊。本發明的技術方案先將存儲在磁條卡上的106比特的身份認證信息分成9個變量，其中兩個變量的長度分別為16和20比特，其餘變量的長度均為10比特；接著利用本發明的技術方案提供的算法生成所述的9個變量和求出兩個大素數P和Q；用兩個大素數P和Q的乘積可得到模數N＝P*Q和兩個能抵抗小指數攻擊的密鑰KP公鑰PK和私鑰SK。綜上，本發明的技術方案利用模數N、公鑰PK和私鑰SK，兩個大素數P和Q，以及9個變量三者之間的關係，生成長度總和為106比特的9個變量。本發明的技術方案把RSA密碼系統密鑰變量的存儲空間減少到使其能用在以存儲容量為106比特的磁條卡作為用戶身份認證的EFT和POS機等系統中的程度。
關於EFT和POS機系統的認證，用公鑰密碼算法RSA來實現，需要用到減少密鑰變量的存儲空間的技術，而這個技術的三個主體分別是用戶卡(CARD)，終端(EFT)和主機處理中心(HPC)。
假定用戶在銀行或其它金融機構已經註冊，則他擁有一個基本帳號(PAN)。而用戶插入終端的卡上信息被讀入時，用戶只需輸入個人的身份證號(PIN)來證實自己的基本帳號(PAN)。如果PIN和PAN核對正確，則系統將啟動業務服務。
但是用戶的身份認證實際上是利用卡上的用戶個人身份信息個人密鑰KP，通過密碼算法如RSA等來保護的。
圖1解釋了RSA系統在EFT和POS機系統中的應用。磁條卡的容量不能存儲足夠安全的RSA密鑰變量，成為了一個急需解決的問題。在詳細解釋減少RSA密鑰變量存儲空間的方法之前，先來看看整個系統的結構。
首先，設用戶的身份IDi，個人密鑰KPi和模數Ni都被讀入終端EFT，且個人的身份證號PINi也已讀入終端EFT，這時用戶的身份信息IDi和終端的身份信息TIDj被送到主機處理中心HPC。
然後，主機處理中心HPC通過隨機數發生器(GEN RN)產生隨機數T1，並發送至終端EFT，接著終端EFT將隨機數T1和業務要求消息TRM做連接運算，同時也把個人的身份證號PINi和個人密鑰KPi做模2加運算，產生私鑰SKi。用私鑰SKi和模數Ni對業務要求消息TRM‖隨機數T1做解密運算，得到dSKi(TRM，T1)。終端EFT通過自己的隨機數發生器產生隨機數T2，將它與dSKi(TRM，T1)一起發送給主機處理中心HPC。
在主機處理中心HPC中，通過終端EFT發送的用戶身份信息IDi，終端身份信息TIDj，找到用戶的個人的身份證號PANi，模數Ni和公鑰PKi，用公鑰PKi和模數Ni對dSKi(TRM，T1)進行加密處理，恢復出業務要求消息TRM和隨機數T1′。若隨機數T1′＝隨機數T1，則通過驗證，繼續，否則拒絕業務要求。假設上面的驗證通過，則主機處理中心HPC用銀行的模數Nb和私鑰SKb對隨機數T2進行解密處理，將dSKb(T2)發回至終端EFT。圖2和圖3分別是解密和加密過程。
最後，終端EFT將接收到的dSKb(T2)用銀行公開的模數Nb和公鑰PKb進行加密處理。如果加密結果是T2′，正好與原來的T2一致，則認證用戶為合法用戶，並按業務要求消息TRM辦理業務。
上述系統的運行是以卡(CARD)的容量足夠能存儲Ni和KPi為前提的。由於磁條卡的的容量小，沒有辦法將他們直接存儲到磁條卡上，因此本發明利用一定的預計算將Ni和KPi壓縮存儲在容量為106比特的磁條卡上，使磁條卡能與上述的系統聯用。
以下是利用存儲在磁條卡上的106比特的信息產生足夠安全的RSA密鑰變量模數Ni和個人密鑰KPi。
圖4所示的106比特被分為9組變量D1，…，D9，所有變量都是以二進位形式存儲的。其中，D2和D9的長度分別為20和16比特，其餘變量的長度均為10比特。
現結合圖5a和圖5b具體說明本發明的技術方案。
一種減少RSA密鑰變量存儲空間的方法，其特徵在於，具體操作步驟第一步 選取變量D1，使Z＝2488-2D1+1是一個長度為488比特的素數，下面將利用Z產生其它的參數，所用的運算及其符號羅列如下OR二進位數的『或』運算，mod數的模運算，[K]不超過K的最大整數，a*b表示a和b的相乘，L(Q)取Q的二進表示的左邊373比特，即前373比特構成一個新數，以上未羅列的其它運算均為普通整數運算；(注變量D1生成，其長度為10比特。)第二步 選取D2，D3，得X1=D2(D3+1)modZ,]]>使P″＝(X1)OR(2487+1)是一個長度為488比特的素數；(注變量D2和D3生成，變量D2和D3的長度分別為20和10比特。)第三步 選取D4，使P′＝2(D4+210)P″+1是一個長度為500比特的素數；(注變量D4生成，其長度為10比特。)第四步 選取D5，使P＝2(D5+210)P′+1是一個長度為512比特的素數；(注變量D5生成，其長度為10比特。)
第五步 計算X2＝[21024/P]，將X2的二進位表示的最後一位強制改為1，得X3；第六步 選取D6，使Q″＝2(D6+210)X3+1是一個長度為488比特的素數；(注變量D6生成，其長度為10比特。)第七步 選取D7，使Q′＝2(D7+210)Q″+1是一個長度為500比特的素數；(注變量D7生成，其長度為10比特。)第八步 選取D8，使Q＝2(D8+210)Q′+1是一個長度為512比特的素數；(注變量D8生成，其長度為10比特。)第九步 計算模數N＝P*Q，此時N的長度為1024比特；第十步 選取D9，計算d＝2374+2(D9+L(Q))+1，使e*d≡1 mod(P-1)(Q-1)中的e≥217+1；(注變量D9生成，其長度為16比特。e和d分別稱為加密指數和解密指數。在現今攻擊RSA密碼系統的方法中，若解密指數d＜N0.365，RSA密碼系統是容易被攻破的。N0.365＜2374，所以這裡選取的d大於2374是安全的。與此同時，關於較小的加密指數e也是不安全的，所以選取的e必須≥217+1。)第十一步令公鑰PK＝e，私鑰SK＝d，此時公鑰PK和私鑰SK的長度均為1024比特；第十二步至此，變量D1，D2，D3，D4，D5，D6，D7，D8和D9均已生成，其中，變量D2和D9的長度分別為20和16比特，其餘的長度均為10比特。
將變量D1，D2，D3，D4，D5，D6，D7，D8和D9存儲在磁條卡上的長度為106比特的存儲空間上。
用本發明的方法錄製的磁條卡特別適於與EFT和POS機等系統聯用，為EFT和POS機等系統提供既安全又能抵抗小指數攻擊的用戶身份認證或信息認證。
本發明的方法的優點1、由於本發明的方法生成的用於身份認證或數據認證的數據長度為106比特，所以該方法適合於用在目前用磁條卡進行身份認證的EFT和POS機系統中。
2、本發明的方法生成的長度為106比特的身份認證或數據認證的數據讀入EFT和POS機系統後，EFT和POS機系統能產生長度均為1024比特的模數N、公鑰PK和私鑰SK，並且公鑰PK和私鑰SK能抵抗小指數攻擊，換句話說，該方法能產生既能抵抗小指數攻擊，又能不被分解的模數N、公鑰PK和私鑰SK。
上述性能大幅度提高了目前EFT和POS機系統的身份認證安全性和應用的廣泛性。
本發明的主要結構，算法和技術步驟主要由附圖1，圖2，圖3，圖4和圖5組成。
圖1是RSA密碼算法在EFT和POS機系統上的應用結構和算法，及認證用戶合法性和銀行合法性的示意圖。
圖2，圖3分別為圖1中的解密算法和加密算法。
圖4為存儲在磁條卡上106比特的RSA壓縮密鑰。
圖5(a)和圖5(b)為將106比特的9組變量生成安全有效的RSA密鑰變量的預計算過程。該算法是本發明的方法的技術核心，既能滿足RSA最新防止攻擊的技術要求，又能產生安全性很高的密鑰。
具體實施例方式
在上面的發明內容中詳加說明的減少RSA密鑰變量存儲空間的方法就是實施例。
工作原理。
上述過程中都可以通過預計算來實現。目前，已有很多檢測整數素性的算法，所以上述的操作步驟都是可實現的。
通過事先預計算的106比特的數據和上述操作步驟的逆過程可以非常容易地恢復出模數N，密鑰KP公鑰PK和私鑰SK。已知用戶身份認證數據，其長度為106比特，及其9組變量D1，D2，D3，D4，D5，D6，D7，D8和D9。以下是恢復出模數N，密鑰KP公鑰PK和私鑰SK的過程1、Z＝2488-2D1+1將D1代入上式，得Z。
2、X1=D2(D3+1)modZ]]>將D2，D3和Z代入上式，得X1。
3、P″＝(X1)OR(2487+1)將X1代入上式，得P″。
4、P′＝2(D4+210)P″+1將D4和P″代入上式，得P′。
5、P＝2(D5+210)P′+1將D5和P′代入上式，得P。
6、X2＝[21024/P]7、 8、Q″＝2(D6+210)X3+1將D6和X3代入上式，得Q″。
9、Q′＝2(D7+210)Q″+1將D7和Q″代入上式，得Q′。
10、Q＝2(D8+210)Q′+1將D8和Q′代入上式，得Q。
11、N＝P*Q將P和Q代入上式，得N。
12、d＝2374+2(D9+L(Q))+1將D9和L(Q)代入上式，得d。
13、e*d≡1 mod(P-1)(Q-1)將d，P和Q代入上式，得e。
14、PK＝e，SK＝d至此，恢復出的模數，公鑰和私鑰分別為N，PK和SK，模數N，公鑰PK和私鑰SK的長度均為1024比特。
權利要求
1.一種減少RSA密鑰變量存儲空間的方法，其特徵在於，具體操作步驟第一步 選取變量D1，使Z＝2488－2D1+1是一個長度為488比特的素數，下面將利用Z產生其它的參數，所用的運算及其符號羅列如下OR二進位數的『或』運算，mod數的模運算，[K]不超過K的最大整數，a*b表示a和b的相乘，L(Q)取Q的二進表示的左邊373比特，即前373比特構成一個新數，以上未羅列的其它運算均為普通整數運算；第二步 選取D2，D3，得X1=D2(D3+1)modZ,]]>使P″＝(X1)OR(2487+1)是一個長度為488比特的素數；第三步 選取D4，使P′＝2(D4+210)P″ +1是一個長度為500比特的素數；第四步 選取D5，使P＝2(D5+210)P′+1是一個長度為512比特的素數；第五步 計算X2＝[21024/P]，將X2的二進位表示的最後一位強制改為1，得X3；第六步 選取D6，使Q″＝2(D6+210)X3+1是一個長度為488比特的素數；第七步 選取D7，使Q′＝2(D7+210)Q″+1是一個長度為500比特的素數；第八步 選取D8，使Q＝2(D8+210)Q′+1是一個長度為512比特的素數；第九步 計算模數N＝P*Q，此時N的長度為1024比特；第十步 選取D9，計算d＝2374+2(D9+L(Q))+1，使e*d≡1 mod(P-1)(Q-1)中的e≥217+1；第十一步 令公鑰PK＝e，私鑰SK＝d，此時公鑰PK和私鑰SK的長度均為1024比特；第十二步 至此，變量D1，D2，D3，D4，D5，D6，D7，D8和D9均已生成，其中，變量D2和D9的長度分別為20和16比特，其餘的長度均為10比特。
2.根據權利要求1所述的方法，其特徵在於，將該方法生成的9個變量D1，D2，D3，D4，D5，D6，D7，D8和D9存儲在磁條卡上的長度為106比特的存儲空間上，製得適於與EFT和POS機等系統聯用的、既安全又能抵抗小指數攻擊的用戶身份認證卡或信息認證卡。
3.權利要求2所述的用戶身份認證卡或信息認證卡用於EFT和POS機等系統作用戶身份認證的方法，其特徵在於，通過事先預計算的106比特的數據和上述操作步驟的逆過程可以非常容易地恢復出模數N，密鑰KP公鑰PK和私鑰SK。已知用戶身份認證數據，其長度為106比特，及其9組變量D1，D2，D3，D4，D5，D6，D7，D8和D9，以下是恢復出模數N，密鑰KP公鑰PK和私鑰SK的過程1、Z＝2488-2D1+1將D1代入上式，得Z；2、X1=D2(D3+1)modZ]]>將D2，D3和Z代入上式，得X1；3、P″＝(X1)OR(2487+1)將X1代入上式，得P″；4、P′＝2(D4+210)P″+1將D4和P″代入上式，得P′；5、P＝2(D5+210)P′+1將D5和P′代入上式，得P；6、X2＝[21024/P] 8、Q″＝2(D6+210)X3+1將D6和X3代入上式，得Q″；9、Q′＝2(D7+210)Q″+1將D7和Q″代入上式，得Q′；10、Q＝2(D8+210)Q′+1將D8和Q′代入上式，得Q；11、N＝P*Q將P和Q代入上式，得N；12、d＝2374+2(D9+L(Q))+1將D9和L(Q)代入上式，得d；13、e*d≡1mod(P-1)(Q-1)將d，P和Q代入上式，得e；14、PK＝e，SK＝d至此，恢復出的模數，公鑰和私鑰分別為N，PK和SK，模數N，公鑰PK和私鑰SK的長度均為1024比特。
全文摘要
一種減少RSA密鑰變量存儲空間的方法，屬信息安全和網絡安全的技術領域。本發明的技術方案利用模數N、公鑰PK和私鑰SK，兩個大素數P和Q，以及9個變量三者之間的關係，生成長度總和為106比特的9個變量，把RSA密碼系統密鑰變量的存儲空間減少到使其能用在以存儲容量為106比特的磁條卡作為用戶身份認證的EFT和POS機等系統中的程度。該方法有以下優點將生成的9個變量存儲在磁條卡上的長度為106比特的磁條卡上，可製得適於與EFT和POS機等系統聯用的、既安全又能抵抗小指數攻擊的用戶身份認證卡或信息認證卡。
文檔編號G07F7/10GK1777100SQ20051011135
公開日2006年5月24日 申請日期2005年12月9日 優先權日2005年12月9日
發明者錢海峰, 汪振華, 陳志傑, 時儉益, 陸洪文, 葉家琛, 李志斌, 王澤成 申請人:上海燕託計算機有限公司