Diffie－Hellman數字籤名的生成和驗證的製作方法
2023-06-06 14:20:46
專利名稱：Diffie－Hellman數字籤名的生成和驗證的製作方法
技術領域：
本申請涉及加密技術的領域，特別涉及一種用來使用基於Diffie-Hellman的算法來生成和/或驗證數字籤名的系統和設備。
背景技術：
檢驗文件是否來自經授權的或者可信的來源的數字籤名技術在本領域內是公知的。例如，利用公/私鑰加密系統，發送者可以通過使用本地可用並且秘密持有的私鑰將相關文件的內容加擾或加密而電子地在文檔上簽名。接收方可以使用發送者的公鑰將所接收的文件解密。接收方正確地將所接收的文件解擾或解密的能力證實該文件是由經授權或可信任的發送者發送的。
圖1圖示了用於產生數字籤名的系統的方框圖100。如圖所示，將文件110提供給生成一值並將該值與文件相關聯的「散列」算法120。例如，SHA-1(安全散列算法)可以為任何文件產生160位的散列值。可以進一步表明產生具有相同散列值的兩個文件在計算上不可行。然後，在塊130處使用例如發送方的RSA私有加密密鑰將散列值加密或加擾。在此情況下，加密或加擾的散列值代表數字籤名。經由網絡150傳送所述文件和籤名。
接收方接收文件160和加密的散列值、即數字籤名，在塊180使用相關聯的RSA公鑰將數字籤名解密或解擾，並在塊170將文件混編(hash)，以生成重新計算的散列值。在塊190進行比較，以確定解密後的散列值是否與所計算的散列值相同。
當使用上述公/私鑰系統提供某種安全措施時，這種系統可能容易受到密集的數學計算攻擊。此外，由於加密技術受到某些出口限制，因此現有的數字籤名技術可能具有相當有限的可用性。希望有替換的驗證技術。
發明內容
公開了一種用於生成和解碼數字籤名以便驗證所接收的信息項(item)的來源的方法和相關設備。接收設備用來確定與第一值和Diffie-Hellman公鑰有關的第一比較器值，所述第一值與經由網絡接收的信息項相關聯；確定與所接收的數字籤名有關的第二比較器值，其中，與第二值相關聯地確定所述數字籤名，所述第二值與經由網絡傳送之前的信息項相關聯；將所述比較器值進行比較，並基於該比較證實所述信息是由所述來源發送的。密鑰生成設備用來從隨機選擇的多個大數生成第一和第二Diffie-Hellman密鑰，其中所述數中的至少一個是質數，並且該設備還將公鑰確定為所生成的Diffie-Hellman密鑰之一的Diffie-Hellman轉置。
圖1圖示了用於傳統的RSA數字籤名處理的過程的方框圖；圖2圖示了根據本發明一個方面的用於驗證用戶身份的過程的方框圖；圖3圖示了根據本發明一個方面的用於生成數字籤名的示例過程的流程圖；圖4圖示了根據本發明一個方面的用於將數字籤名解碼的示例過程的流程圖；以及圖5圖示了用於執行在此示出的處理的設備。
應當理解，這些圖僅用於說明本發明的構思的目的，而不意欲作為對本發明的限制的定義。在圖2-5中示出並在所附詳細描述中描述的實施例應被用作說明性的實施例，而不應被解釋為實踐本發明的唯一方式。此外，在適當的地方可能用參考字符來補充的相同附圖標記被用來標識相同的元件。
具體實施例方式
在加密技術中使用Diffie-Hellman算法已經被擴展為三方，如在「AppliedCryptography 2ndedition」(Bruce Schneier(Ed.)，p.514)中更充分地解釋的那樣。在此加密技術中，每一方傳送由另一方提供的密鑰的元素。每一方基於所提供的信息來為會話確定公共加密密鑰。例如，假設每一方都知道加密變量g和n，其中n是大質數，則可以表明可以使用以下過程來形成三方密鑰交換「A」隨機選擇大整數x，形成X＝gxmod(n)，並將X傳送給「B」；「B」隨機選擇大整數y，形成Y＝gymod(n)，並將Y傳送給「C」；並且「C」隨機選擇大整數z，形成Z＝gzmod(n)，並將Z傳送給「A」；
「A」隨後產生Z的變換為Z』＝Zxmod(n)，並將Z』傳送給「B」；「B」隨後產生X的變換為X』＝Xymod(n)，並將X』傳送給「C」；並且「C」隨後產生Y的變換為Y』＝Yzmod(n)，並將Y』傳送給「A」。
「A」隨後確定密鑰值k為k＝Y』zmod(n)；「B」隨後確定密鑰值k為k＝Z』ymod(n)；並且「C」隨後確定密鑰值k為k＝X』zmod(n)。
「A」、「B」和「C」每一個確定公共密鑰值k的能力可以數學地示出為((gxmod(n))ymod(n))zmod(n)＝gxyzmod(n)＝((gymod(n))zmod(n))xmod(n) [1]圖2圖示了根據本發明一個方面的用於生成數字籤名的示例操作200的方框圖。被表示為塊205的第一方「A」在塊210生成加密值n、g、x和z。加密值n、g、x和z優選地每個都是隨機選擇的大數，並且n是質數。經由網絡202傳送值n和z。值g和x由「A」方秘密保存。在塊220，生成第一密鑰值為X＝gxmod(n)，並且其代表「A」方的私鑰，以供第二方「B」使用。在優選實施例中，將私鑰X通過由虛線222表示的諸如物理交付的安全連結傳送給「B」方。在本發明的另一方面，可以使用「A」方和「B」方之間的網絡202的安全方式(aspect)、經由網絡202來將私鑰X從「A」方傳送給「B」方。例如，這種安全方式包括諸如密碼和共享密鑰的安全通信措施(provision)。
在塊215，生成第二密鑰值為Z＝gzmod(n)，並且在塊225，將第二密鑰值Z變換為公鑰為Z』＝Zxmod(n)。然後，將公鑰Z』分發給第三方「C」。在所示出的示例中，經由網絡202傳送公鑰Z』。儘管未被示出，但是本領域技術人員將認識到，當經由公共網絡傳送公鑰Z』時，包括用來使接收方確信公鑰Z』是傳送自可信來源的措施，例如籤名、證書等。因此，當經由諸如網際網路的公共網絡進行分發時，需要用於驗證公鑰Z』的獨立裝置。在本發明的另一方面，在代表第三方「C」的地點處，公鑰Z』是已知的、預先加載的或預先確定的值。
被表示為塊230的第二方「B」在塊240將信息項或文件235混編，以便產生被稱為「y」的散列值。然後，在塊245，使用散列值y、利用私鑰X和加密變量n來將數字籤名X』確定為X』＝Xymod(n)。然後，經由網絡202傳送文件235和籤名X』。
被表示為塊250的第三方「C」接收被示出為塊260的文件235，並且使用與用於如先前討論的那樣確定散列值的方法相似的方法在塊265計算所接收的文件的散列值。將所計算的散列值稱為「y。然後，使用公鑰Z』和所計算的散列值y』來將第一比較器值用公式表示為Kb=Z』y’mod(n)[2]第三方「C」還在塊275從所接收的數字籤名X』和加密變量z生成第二比較器值(Ka)為Ka＝X』zmod(n) [3]在塊280處進行比較，以便驗證傳送的來源。當傳送前的文件散列值的值(y)等於所接收的文件的散列值(y』)時，所傳送的信息項或文件的來源、即第二方「B」的有效性被確定。在此情況下，比較器值Ka和Kb可以被示出為等於Ka＝X』zmod(n)＝(Xymod(n))zmod(n)＝((gxmod(n))ymod(n))zmod(n)＝gxyzmod(n)；[4]Kb＝Z』y’mod(n)＝(Zxmod(n))y’mod(n)＝((gzmod(n))xmod(n))y’mod(n)＝gxy』zmod(n)；[5]圖3圖示了根據本發明一個方面的用於生成密鑰值的過程300的流程圖。在此說明性的過程中，在塊310處生成密鑰變量g、n、x和z。在塊320，將兩個密鑰生成為X＝gxmod(n)以及Z＝gzmod(n)； [6]在塊330，將所生成的密鑰之一變換為公鑰Z』＝Zxmod(n)。[7]在塊340，經由網絡傳送加密變量中的所選擇的一些，例如n和z。在一個方面，可以經由網絡的安全部分傳送第一密鑰X和公鑰Z』。在另一方面，第一密鑰X和公鑰Z』可被預先加載或預先確定，並因此而被「B」方和「C」知曉。
圖4圖示了根據本發明一個方面的用於驗證數字籤名的過程400的流程圖。在此示例過程中，在塊410獲得密鑰值和加密變量。如先前討論的那樣，可以經由安全網絡電子地或物理地傳送所述密鑰和變量，或者可以預先加載或預先存儲它們。在塊420，為所接收的文件確定散列值。在塊430，基於所確定的散列值來確定第一比較器值。在塊440，確定第二比較器值。在塊450，對所確定的第一和第二比較器值是否相同進行確定。如果答案為肯定的，則在塊460，生成指出第二方「B」發送了所接收的文件的指示。
儘管未示出，但是本領域技術人員將認識到，可以由各方預先確定和知曉加密變量n、g、x和z。因此，不需要經由網絡傳送這些值。在此情況下，在第一方「A」是生產機頂盒的工廠的系統中，可以用所生成的加密密鑰Z』以及變量n和z來預先加載或預先設置每個機頂盒或設備。在此情況下，每個機頂盒將代表「C」方。類似地，第二方「B」可以是被稱為「頭端(head-end)」的傳送設備，例如電纜公司或其它媒體內容服務。在此情況下，第一方A只需向第二方B提供最少量的信息，以供B方產生數字籤名X』。
圖5圖示了用於實現如在圖2-4示出的示例處理中敘述的本發明的原理的系統500。在此示例系統實施例500中，例如經由網絡550從源505接收輸入數據，並根據由處理系統510的處理器520執行的一個或多個程序對其進行處理。然後，可以經由網絡570傳送處理系統510的結果，以便在顯示器580、報告設備590和/或第二處理系統595上查看。
具體地說，處理系統510包括經由網絡550從所圖示的源設備505接收數據的一個或多個輸入/輸出設備540。然後，將所接收的數據施加到與輸入/輸出設備540和存儲器530通信的處理器520。輸入/輸出設備540、處理器520和存儲器530可以經由通信介質525通信。通信介質525可以代表通信網絡，例如ISA、PCI、PCMCIA總線；電路、電路卡或其它設備的一個或多個內部連接；以及這些和其它通信介質的部分和組合。處理系統510或處理器510可以代表手持式計算器、特殊用途或通用處理系統、臺式計算機、膝上型計算機、掌上計算機、或個人數字助理(PDA)設備等、以及可執行所述處理的這些和其它設備的部分或組合。
處理器520可以是用來執行計算機指令代碼或者代碼和邏輯操作的組合的中央處理單元(CPU)或專用硬體/軟體，例如PAL、ASIC、FGPA。在一個實施例中，處理器520可以包括代碼，當執行所述代碼時，其進行在此說明的操作。當需要時，代碼可以被包含在存儲器530中、或者可以從被表示為583的諸如CD-ROM或軟盤的介質中讀取或下載、或者可以由諸如鍵盤或小鍵盤輸入的手動輸入設備585提供、或者可以從可由處理器520訪問的磁或光介質(未示出)讀取。如所示出的那樣，處理器520可以通過輸入/輸出設備540訪問由輸入設備583、585和/或磁介質提供的信息項。此外，由輸入/輸出設備540接收的數據可以立即被處理器520訪問、或者可以被存儲在存儲器530中。處理器520還可以將在此示出的處理的結果通過I/O設備540提供給顯示器580、記錄設備590或第二處理單元595。
如本領域技術人員將認識到的那樣，術語處理器、處理系統、計算機或計算機系統可以代表與一個或多個存儲單元和其它設備例如外設通信的一個或多個處理單元，其中所述一個或多個存儲單元和其它設備電子地連接到所述至少一個處理單元並與其通信。此外，所示設備可以經由例如串行、並行、ISA總線、微通道總線、PCI總線、PCMCIA總線、USB等的內部總線、或者電路、電路卡或其它設備的一個或多個內部連接、以及這些和其它通信介質的部分和組合、或者諸如網際網路和內聯網的外部網絡，來電子地連接到所述一個或多個處理單元。在其它實施例中，可以代替或結合軟體指令而使用硬體電路來實現本發明。例如，在此說明的元件也可以作為分立硬體元件而實現，或者可以被集成到單個單元中。
如將理解的那樣，可以使用不同的處理器來依序或並行執行在圖2-4中示出的操作，以確定特定值。處理器系統510也可以與源505的每一個雙向通信。處理器系統510還可以經由來自一個或多個伺服器的一個或多個網絡連接，例如通過諸如網際網路、內聯網、廣域網(WAN)、城域網(MAN)、區域網(LAN)、陸地廣播系統、電纜網、衛星網、無線網、或電話網(POTS)以及這些和其它類型網絡的部分或組合的全球計算機通信網絡，來接收或傳送數據。如將意識到的那樣，網絡550和570也可以是內部網絡、或者電路、電路卡或其它設備的一個或多個內部連接、以及這些和其它通信介質的部分和組合、或者諸如網際網路和內聯網的外部網絡。如將由本領域技術人員認識到的那樣，處理系統510可以代表適合於作為第二方「B」或第三方「C」操作的設備。
儘管示出、描述和指出了應用於本發明的優選實施例的本發明的基本新穎特徵，但是將理解的是在不脫離本發明的精神的情況下，本領域技術人員可以在所描述的裝置中、在所公開的設備的形式和細節以及其操作方面進行省略和替換以及改變。例如，本領域技術人員將認識到，160位的散列值可能不夠大以提供足夠的安全性。在此情況下，通過對散列值執行擴展功能來進一步擴展所述值的範圍可能是有利的。例如，在一個方面，可以通過將從上述SHA-1算法獲得的160位的散列值升高到已知的冪、即(散列值)α來確定更大的散列值。在優選實施例中，將α選擇為大於7。
顯然，意圖是以基本相同的方式執行基本相同的功能以獲得相同結果的那些元件的所有組合處於本發明的範圍內。從一個所述實施例到另一個實施例的元件的替換也已被充分設計和考慮到。
權利要求
1.一種設備，位於具有多個遠程地點的網絡上的遠程地點處，用於驗證經由所述網絡傳送的信息項的來源，所述設備包括處理器，與存儲器通信，所述處理器用來執行用於以下操作的代碼確定與第一值和Diffie-Hellman公鑰有關的第一比較器值，所述第一值與經由所述網絡接收的所述信息項相關聯；確定與所接收的數字籤名有關的第二比較器值，所述數字籤名被與第二值相關聯地確定，所述第二值與經由所述網絡傳送之前的所述信息項相關聯；以及將所述第一和第二比較器值進行比較，並基於所述比較驗證所述來源。
2.如權利要求1所述的設備，其中，所述處理器還用來執行用於將所述第一值確定為所述所接收的信息項的散列值的代碼。
3.如權利要求1所述的設備，其中，所述公鑰採用以下形式gxzmod(n)其中，g、x、z和n是隨機選擇的大數，並且n是質數。
4.如權利要求3所述的設備，其中，從包含已知、預先加載、預先確定、可確定的組中選擇所述公鑰。
5.如權利要求3所述的設備，其中，所述處理器用來從包含磁帶、光介質、存儲器的外部介質中讀取所述公鑰。
6.如權利要求3所述的設備，其中，所述處理器用來執行用於經由所述網絡接收所述隨機選擇的大數中所選擇的一些的代碼。
7.如權利要求1所述的設備，其中，所述處理器還用來執行用於經由所述網絡接收所述公鑰的代碼。
8.如權利要求3所述的設備，其中，所述處理器還用來從包含磁帶、光介質、存儲器的組中獲得來自預先加載的來源的所述隨機選擇的大數中所選擇的一些。
9.如權利要求1所述的設備，還包括I/O單元，與所述處理器和所述網絡通信。
10.如權利要求9所述的設備，其中，所述I/O單元還與所述存儲器通信。
11.如權利要求1所述的設備，其中，所述代碼存儲在所述存儲器中。
12.如權利要求1所述的設備，其中，所述第二值是散列值。
13.如權利要求1所述的設備，其中，當所述第一和第二比較器值相等時，所述來源被證實。
14.一種用於驗證經由網絡傳送的信息項的來源的方法，所述方法包括以下步驟確定與第一值和Diffie-Hellman公鑰有關的第一比較器值，所述第一值與經由所述網絡傳送的所述信息項相關聯；確定與數字籤名有關的第二比較器值，其中所述數字籤名與經由所述網絡傳送之前的所述信息項相關聯；以及將所述第一和第二比較器值進行比較，並基於所述比較驗證所述來源。
15.如權利要求14所述的方法，還包括以下步驟將所述第一值確定為所述信息項的散列值。
16.如權利要求14所述的方法，其中，所述公鑰採用以下形式gxzmod(n)其中，g、x、z和n是所述隨機選擇的大數，並且n是質數。
17.如權利要求16所述的方法，其中，從包含已知、預先加載、預先確定、可確定的組中選擇所述公鑰。
18.如權利要求16所述的方法，其中，經由所述網絡傳送所述公鑰。
19.如權利要求16所述的方法，其中，從包含已知、預先加載、預先確定的組中選擇所述大數值中的所選擇的一些。
20.如權利要求16所述的方法，其中，從所述網絡接收所述大數值中的所選擇的一些。
21.如權利要求14所述的方法，其中，當所述第一和第二比較器值相等時，所述來源被證實。
22.一種用於生成數字籤名的設備，包括處理器，與存儲器通信，所述處理器用來執行用於以下操作的代碼從隨機選擇的多個大數生成第一和第二Diffie-Hellman公鑰，其中，所述數中的至少一個是質數；以及將公鑰確定為所述Diffie-Hellman公鑰之一的Diffie-Hellman轉置。
23.如權利要求22所述的設備，還包括與所述處理器通信的設備，所述設備用來將所述公鑰和所述Diffie-Hellman公鑰中的剩餘的一個傳送給外部設備。
24.如權利要求23所述的設備，其中，所述外部設備是從包含網絡、磁介質、光介質、人類可讀介質的組中選擇的。
全文摘要
在一個實施例中，公開了一種用於將數字籤名解碼以驗證所接收的信息項的來源的設備。該設備用來確定與第一值和Diffie－Hellman公鑰有關的第一比較器值，所述第一值與經由網絡接收的信息項相關聯；確定與所接收的數字籤名有關的第二比較器值，其中，與第二值相關聯地確定所述數字籤名，所述第二值與經由所述網絡傳送之前的信息項相關聯；以及將第一和第二比較器值進行比較，以基於該比較驗證所述來源。在另一實施例中，密鑰生成設備用來從隨機選擇的多個大數生成第一和第二Diffie－Hellman密鑰，其中所述數中的至少一個是質數，並且該設備還將公鑰確定為所生成的第一和第二Diffie－Hellman密鑰之一的Diffie－Hellman轉置。
文檔編號H04L9/32GK1820450SQ03826855
公開日2006年8月16日 申請日期2003年7月31日 優先權日2003年7月31日
發明者史蒂文·C·羅茲 申請人:湯姆森特許公司