詢問-應答籤名和安全迪菲-海爾曼協議的製作方法

2023-06-13 21:40:21 3

專利名稱：詢問-應答籤名和安全迪菲-海爾曼協議的製作方法
技術領域：
本發明的各方面總體涉及對於信息交換的發送和接收方可證明是安全
的籤名。更具體而言，詢問-應答(challenge-response)籤名方案擁有檢驗 者和籤名者均可以計算出相同或相關的籤名的特性，前者通過知道詢問以 及後者通過知道秘密籤名密鑰(private signature key)來計算，從而在示 例性實施例中準許可證明是安全的、常規密鑰交換協議的變體，包括^^p 的MQV協議的變體。
背景技術：
如最初所建議的，圖1中所示的Diffie-Hellman (迪菲-海爾曼，DH) 密鑰交換協議100 ^L認為對於防禦僅竊聽(eavesdropping-only)的攻擊者 是安全的。對抵抗有效的、中間人攻擊(man-in-他e-middle attacks )的"認 證Diffie-Hellman (authenticated Dtffie-Hellman)"協議的搜尋已經導致 了無數的ad-hoc (特定的)提議，它們中的很多已經損壞或者顯示有缺點。 隨著近幾年用於密鑰交換的嚴密安全模型(rigorous security model)的發 展，本領域的技術人員現在處於好得多的形勢來判斷這些協議的安全性， 以及開發可證明抵抗現實有效攻擊的設計。
如所期望的，添加防禦有效攻擊的防護措施導致複雜性增加，無論是 在附加的通信方面還是在附加的計算方面。後者在利用公鑰技術認證的協 議中尤為重要，其通常要求附加的昂貴的群求冪(group exponentiation)。 除了需要可靠的安全性之外，對密鑰交換的很多實際應用已經促使設計者 改進與認#制關聯的性能代價，尤其是基於公鑰的那些。
由Matsumoto、 Takashima和Imai在1986年; t^的一條調查線(one line ofinvestigation )是對將向協議增加最小的複雜性的公鑰(PK)認證 DH協議的搜索。理論上，直至認證公鑰的交換，協議的通信被期望完全 看作是基本DH交換。在該技術中，必須通過密鑰導出過程獲得協議的認
證各方會對將gx、 gy與各方的公鑰/私鑰相結合的密鑰達成一致，而不是
對基本Diffie-HeUman密鑰g"達成一致。
一部分由於這樣的協議將提供的實際優點，以及一部分由於在這樣的 設計之後的數學詢問，在該方法下已經開發了4艮多協議，常被稱為"可隱 ^iUit的Diffie-Hellman協議"。該方法不僅可以生成作為非常有效的通 信方式(communication-wise)的協議，而且與密鑰導出過程相結合的認 證可以潛在地導致顯著的計算節約。由於這些原因，這些"可隱含認證的" 協議中的幾個協議已經被主要的國家和國際安全標準進行了標準化.
在這些協議中，MQV協議似乎已經被廣泛標準化。很多組織已經將 該協議標準化，並且最近美國國家安全局(NSA)已經宣布該協議是作為 "保護美國il^信息的下一代密碼術"的基礎的密鑰交換機制，其包括"密 級(classified)或緊^^吏命(mission critical)國家安全信息"的保護.
另夕卜，MQV似乎已經被設計以滿足一批安全目標。例如，在Vanstone 等人的第5，761，305號美國專利中解釋了 MQV協議的^版本。
然而，儘管其具有吸引力並且獲得了成功，但是在密鑰交換的良好定 義的模型中MQV迄今為止迴避任何形式上的分析。本發明的動機便在於 希望提供這樣的分析。在進行研究時，發明AJ5l察到實質上沒有一個所陳 述的MQV目標是可以被顯示成立的，如在Canetti和Krawczyk的計算密 鑰交換模型中所實現的，以及如在以上標識的臨時申請中所描述的.
該結果使得本發明人關注於這一常規協議的安全性，因此，基於常規 的MQV協議不可證明是安全的這一分析，在優選地保持其現有性能和通 用性的同時，存在對MQV增加安全性的需要。

發明內容
鑑於常規系統的前述以及其它的示例性問題、缺點以及劣勢，本發明 的示例性特徵在於提供一種用於MQV的新變體(在文中稱為HMQV)的
方法和結構，其以可證明的方式實現了所述MQV協議的安全目標。
本發明的另一示例性特徵在於iHi—種新的數字籤名方案，在文中稱 為"詢問-應M名"。
本發明的另 一示例性特徵在於將該詢問-應答籤名方案論證為包括從 Schnorr識別方案導出的、在文中稱為"指數詢問-應答"(exponential challenge-response, XCR)籤名方案的版本，論證為提供了一種具有詢問 者和籤名者均可以計算出相同或相關籤名的特性的協議機制，前者通過已 經選擇詢問來計算以及後者通過知道秘密籤名密鑰來計算。
因此，本發明的示例性目的在於提供一種用於為認證Diffie-Hellman 協議改進安全性的結構和方法，其中可以通過在其中實現XCR籤名方案 的概念來論證安全性是可證明的，
在本發明的第一示例性方面，為了實現以上特徵和目的，文中描述了 一種在通過設備或網絡互連的雙方之間交換的方法，其包括接受方(檢驗 者)選擇用於計算值X-F/(;c)的秘密值jc,其中包括具有至少一個自變 量的第一預定函數，所述值jc是n的所述至少一個自變量之一。籤名方 (籤名者)選擇用於計算值PKF200的秘密值》其中"包括具有至少一 個自變量的第二預定函數，所述值J是"的所述至少一個自變量之一。 所述籤名者獲得所述值AT，所述籤名者還具有私鑰A和公鑰醜。所述籤名 者計算值FF3(y，辦，A)，其中K 包括具有至少三個自變量的笫三預定函數， 所述值j、所述私鑰6以及所述值X是W的所述至少三個自變量中的三個 自變量。存在第四預定函數/^(jc，r，醜)以計算值s'， /^具有至少三個自變 量，所述值jc、所述值r以及所述公鑰5是的所述至少三個自變量中 的三個自變量，但是所述值s不是的自變量。在所述檢驗者和所述籤名 者之間不存在用作所述函數F7、 F麼和的任何一個中的任何自變 量的基礎的、共享的秘密。如果確定值s'以預定方式與值s相關，則所述 檢驗者可以將所述值s和s'考慮為有效認證符。
在本發明的第二和第三示例性方面，文中還描述了一種實現在前面段 落中所描述的方法的裝置，以及有形地體現可由數字處理裝置執行以實現所述方法的機器可讀指令的程序的信號承載介質。
在本發明的第四示例性方面，文中還描述了 一種用於在通過設備或網
絡互連的雙方之間建立i人證密鑰的方法。第一方具有私鑰fl和^^鑰^，所 述私鑰fl是使得0S"^9-l的整數，《是正整數，g是《階有限群的生成元 (generator)，並且^是由所述值g生成的群中的元素且計算為^=g"。 第二方具有私鑰6和公鑰5=^,所述私鑰6是使得0S6S《-l的整數。所 述第一方選擇用於計算值》f的秘密值a:， jc是使得0S;^《-1的整數，並 且所述值A:被傳達至所述第二方。所述第二方選擇用於計算值的秘密 值》j;是使得OSj^g-l的整數，並且所述值r被傳達至所述第一方.所 述第一方計算值"/i(r，5，m)""'。'"""，其中w、附'包括所述方之間已知或交 換的消息，並且所述第二方計算值^ = /3(義乂附'"°/'6'"°}。所述函數/2和/4 中的至少一個包括具有至少一個自變量的函數H， 一個這樣的自變量是所 述消息w和/w'中的至少一個，其中H包括是單向函數之一的密碼函數、 加密函數以及密碼散列函數。所述第一和第二方分別從值s和s'導出共享 密鑰，


根據下面參照附圖對本發明的優選實施例的詳細描述，可以更好地理 解前述以及其它的目的、方面和優點，其中
圖1示出了基本(未認證)Diffie-Hellman協議100;
圖2示出了通過使用數字籤名認證的兩消息Diffie-Hellman協議200;
圖3示出了常規MQV協議中的會話密鑰K的計算相對於本發明的 HMQV協議的會話密鑰的計算的比較300，在一個示例性實施例中論汪了 HMQV如何利用附加於MQV中所使用的散列的散列；
圖4示出了與圖3中所示出的HMQV協i5C不同的圖示400;
圖5示例性地示出了 XCR的計算500;
圖6示出了非交互式XCR籤名的計算600的例子；
圖7示出了雙方的雙重XCR籤名的計算700;
圖8示出了如在三消息密鑰確認(HMQV-C )協議800中示例性體現 的HMQV;
圖9示出了如在單向(one-pass )密鑰交換卯0中示例性體現的HMQV; 圖10說明了用於在其中併入本發明的示例性硬體/信息處理系統 1000;以及
圖11說明了用於存儲根據本發明的方法的程序的步驟的信號承載介 質IIOO (例如，存儲介質)。
具體實施例方式
現參照附圖，並且更具體地參照圖1-11，其中示出了根據本發明的方
法和結構的示例性實施例。
作為對群和記號的初步註記，文中所討論的所有協議和操作均假設由
生成元《所生成的、《(通常是素數)階的循環群( 。《的比特長度由w (例
如|《|= fto敘n ，意思是底為2的《的對數，上捨入為最接近的整數)表示， 並且該量用作隱含安全^lt。為簡單起見，如實際中常見的，假設M( 、 g和g是固定的並且各方預先已知。可選地，可以將這些值包括在證書等 中。
文中使用群操作的乘法表示，但是該處理同樣可應用於加法群，例如 橢圓曲線或任何其它的代數群或特定群、有限域、複合模，等等。在協議 中，用大寫字母(例如，A、 B)表示的麼嘲是群C7中的元素，以及用相 應的小寫字母(例如，a、 6)表示的私鑰是4中的元素，其中Z《表示整 數0，1，…，《-1的集合。
例如，公鑰^-^對應於私鑰fl。將^作為其公鑰的一方將用^來表示， 按慣例被認為是"Alice"(第二方》按慣例被認為是"Bob")。通常，
"補註記號(hat notation)"用於表示協議中各方的邏輯或"區別"身份， 例如姓名、電子郵件地址、角色等。在一些情況下，可以為這些身份增補 數字證書。對於在臨時申請中所提供的較為完整的數學分析，這裡不再重 復，考慮通過概率多項式時間機來實現協議中包括攻擊者在內的各方。攻
擊者還由Af表示，其中M可以代表"惡意的(malicious)"。
因而，如圖1中所示，對用於基本的未認證Diffie-Hellman協議100 的會活密鑰的計算包括在雙方^、 i之間的交換，其中i方首先向》方發送 其密鑰A^Z，並且S方然後通過將其密鑰F^傳輸回i方來應答，並且其 中jc和y是分別由i和》從集合&隨機選擇的秘密，並且其中將共享M 密鑰計算為g氣
注意到在文中的描述中，符號^有時用於表示隨機選擇。例如，義^Zg 意味著從整數集Z《隨機選擇值;c，通常通過使用隨機或偽隨機數字發生器。
MQV協議
除了身份i、》可以包拾渚如公鑰證書這樣的附加信息，或者可以將 這些身份一起省^W之外，MQV協議中的通信與圖1中所描繪的基本的 未認證DH協議100相同。
在設計兩消息認證密鑰交換協議中的第 一詢問是要基於第 一協議消息 的重放來防止成功的攻擊。由於第一消息不能夠包括由應答者所貢獻的任 何形式的、會話專用(session-specific)的"新鮮度保證(freshness guarantee)"(例如，像nonce或新鮮的DH值)，因此這是有問題的。 該問題的一個解決方案是通過計算會話密鑰來提供新鮮度。
舉例來說，如ISO (國際標準組織)9793協議所採用的，圖2中所示 出的兩消息Diffie-Hellman協議200是使用數字籤名認證的。雖然在》的 籤名下包括/提供了認證的新鮮度，但是在^的消息中並不存在該保護措 施。而會活密鑰f是保證新鮮的(並且與其它會話密鑰無關)，因為其由 新鮮的j;隨機化。然而，如果攻擊者能夠找到^在與》的會話中所4吏用的 單個(A Z)對，則打破了協議的安全性，在這種情況下攻擊者還獲知 SIG"gx，S).這允許攻擊者使用相同的消息及其對jc的知識不定地向》假 冒^，並且不需要曾必須獲知j的長期秘密籤名密鑰。
這是嚴重的弱點，其違犯了這樣的基本原理，即對短暫的(ephemeral) 會話專用信息(例如，(x,f)對)的公開不應當洩漏其它的會話.考慮到很
多應用將脫機計算該(;c，,)對並且將它們保留在較之比方說長期私鑰來說
保護得更少的存儲器中，這就尤為嚴重。
所以如何能夠設計一種即使在洩漏了短暫信息的時候仍可抗重放攻擊 (replay attack)的兩消息協議？通常的回答是將長期私鑰包括到會話密 鑰的計算中。這是Matsumoto、 Takashima和Ima在1986年的工作已提 出的方法，其激發了很多所謂的、Diffie-Hellman的"可隱含認證的"變 體，包括MQV。在該方法中，每一方均具有長期DH公鑰及其相應的秘 密成分，並且通過將會話專用的短暫DH值與各方的公鑰和私鑰相結合而 生成會活。因而，這樣的協議的安全性完全取決於密鑰的這一結合的準確 細節。顯著地，在具有若干缺點的所有先前的協議的情況下，這一表面上 簡單的想法是難以安全實現的。
現在考慮以下對在會話密鑰計算中結合短暫和長期密鑰的問題的通常 的解決方案，當i和》想要交換密鑰時，他們進行基本Diffie-Hellman協 議並且計算會話密鑰為《-g"+。^+W-(yg廣。-(X4)"6。在這種情況下，如果 攻擊者獲知JC而不知道fl，則其不能夠計算iL
然而，該協議仍然是不安全的，如由下面的簡單攻擊所論證的M選
擇值^^A，計算j^-g勺x,並且向》發送:\:*作為對來自2的初始消息 的假冒.》發送r-,並且計算會話密鑰《-(z")一。遺憾的是，M還可 以計算jr為(醜r) .因而，該協議是不安全的。
此外，即使JT的計算變成對於常數rf、 e的A=g(xfrfa)0>+,，那麼攻擊也
仍然是可能的。另一方面，如果允許常數d、 e以攻擊者不能夠分別控制e
和r的方式而隨AT和r變化，則以上的簡單攻擊可能不起作用。該想法將 我們帶回到對MQV的設計，其中d-f並且e-F。
圖3中示出了 MQV中的會活密鑰K的計算301、 302，其中j方擁有 長期私鑰aeZg以及相應的公鑰/4=/。類似地，B的私鑰/公鑰對是(6， 醜=/)，並且短暫的DH值是X-^、 y=/，其中分別由A和B選擇x、 y。 會話密鑰的計算還使用值d-f和e-F，其中對於/叫^/2，X-2'+(Xmod2') 以及F-2'+(ymod2"。
注意到i對會話密鑰的計算涉及用於計算X=f的一個脫機求冪、用於
計算^的一個在線求冪，以及用於CF5yw"的附加在線求冪。然而，還注 意到第二求冪使用長度為l《l/2的指數e，並且因而其計數為"半求冪(half exponentiation)"(例如，相對於g的正常求冪的模數乘法的一半數目)。 操作的相同計數對於5成立。
總之，MQV的性能是真正讓人印象深刻的與基本的未認證DH協 議相同的通信(除了對作為各方身份的一部分的證書的可能傳輸之外)以 及只比基本協議多一半的求冪，其僅僅在計算上增加了 25%以獲得認證交 換。這極大地好於依賴於用於認證的數字籤名或公鑰加密的、已證明的DH 協議中的任何一個，這些協議涉及更昂貴的操作以及增加的帶寬。它還是 最有效率的可隱^S人證的DH協議、最接近於要求三個完整求冪但提供相 當少的安全特徵的"統一模型(Unified Model)"協議.
當選擇認證的DH協議時，這一非凡性能以及對安全性的承諾使得 MQV成為有吸引力的候選者。由於這些原因，該協議已經被採用於很多 標準並且在文獻中得到廣泛討論。然而，由於還未在密鑰交換安全的M 形式模型中成功地進行對MQV協議的任何形式上的分析，因此迄今為止 仍未回答的一個問題是MQV協議真正地有多麼安全。
另一方面，MQV設計者已經明確了在設計後面的安全目標。這些包 括防禦假冒和已知密鑰攻擊(包括抗"未知密鑰共享(UKS)"攻擊)的 M安全性，以及諸如完全正向保密(PFS)和抗KCI (密鑰洩漏假冒) 攻擊的更具體的特徵。抗已知密鑰攻擊表示這樣的原理，即對短暫的M 專用秘密信息的4S開不應當洩漏其它會話的安全性。
PFS和KCI特性涉及在一方的私鑰洩漏給攻擊者M的情況下對安全 損害的P艮制。更具體而言，PFS意味著在兩個^it破壞方之間建立的任何 會活密鑰即使在會活密鑰被從雙方的存儲器中清除之後雙方遭破壞的情況 下也不能夠被M獲知。抗KCI攻擊要求獲知2方的長期密鑰並且因此可 以明顯地向其它方假冒^的攻擊者不能夠向^假冒其它的;^it破壞方。
遺憾地是，如以上引用的臨時申請中所進一步描述的，本發明人的分
析結果表明當在形式上進行研究時，MQV協議並不滿足這些特性中的任 何一個。特別地，在Canetti和Krawczyk的安全模型中論證到，該協議對 一系列攻擊開放，這與聲稱將由MQV滿足的上述安全特性相矛盾。
HMQV協議
HMQV協議(可以認為"H"狄示"散列(Hash)")是MQV的 簡單但有效力的變體，在多個示例性實施例中，除了在步驟302中所示的 用於比較的常規MQV協議之外，其還可以包拾睹如圖3中的步驟303所 示的散列(hashing)。然而，還注意到，作為初始方式，這些示例性實施 例的散列步驟並不是本發明的先決條件，這是因為無需散列以及使用不同 於散列的技術的可選實施例在文中得到了討論，並且還被包括在本發明的 概念中。本發明^&本的概念涉及詢問-應^^名方案，由此引申出多個應 用和實施例，包括MQV協議的示例性散列版本。
本領域所^H^的散列法涉及使用散列函數將字符串轉化成數字、固定 長度的串(例如，散列或消息摘要(digest))等作為輸出。密碼學中散列 函數的基本功能性是具備"單向"或"不可逆"變換，意味著其對於檢索 原始數據應當是不可行的，並且對於構建匹配於給定散列值的數據塊也是 不可行的。散列函數的範圍可以從簡單的"混合"功能到類似純粹隨機置 亂(scrambling)的變換。後者被稱為"強密碼散列函數"並且經常由理 想隨機函數(或"隨機諭示(oracles)")在密碼分析中建模。
幾個散列函數被廣泛用於強密碼散列。例如，MD5將任意大小的數據 塊作為輸入，並且基於處理64位元組的塊中的數據的正弦函數，通過使用逐 位操作、加法以及值的表格來產生128比特(16位元組)的散列。另一主要 的散列函^Sbl提供160比特散列的NIST (國家標準技木研究所)安^Ht列 算法(SHA)。
通常，散列函數不直接用於加密，但是加密函數卻提供單向變換，並 且因此可應用於一些散列用途，包括本發明的一些示例性實施例。散列函 數還很適於數據認證，並且用於結合床密密鑰這樣的目的(在這些i殳置中，
他們常被稱為消息認證代碼MAC或偽隨機函數PRF)或籤名方案(其中 散列值用於"消息摘要")。
本發明的各種示例性實施例使用至少一個散列函數H，該散列函數作 為在以上所引用的臨時申請中較為詳細描述的安全分析中的理想隨機諭示 而祐^提取。在這些示例性實施例中為其使用函數好的兩個任務如下第一， 計算指數麼e;以及第二，導出M密鑰本身。
第一任務示例性地對好使用兩個自變量並且輸出長度為|《|/2的串，而 第二任務將仔應用於單個自變量並且輸出指定長度(例如，128比特)的 密鑰。為了簡化記號，相同的符號醜用於表示散列函數的兩種應用。實際 上，可以使用單個好，比方說，SHA-1，其可以處理可變長度的輸入，並 且可以調整其輸出大小以適應以上兩個任務，在產生散列結果時可能使用 截斷/擴充(truncation/expansion)的某種組合，
然而，還注意到，如果如在第一任務中那樣使用散列，將不必將其限 制於兩個自變量，因為諸如時間戳、nonce等的附加自變量可以作為輸入 被包括到散列函數中，而不是僅散列消息或一方的身份。
當使用散列的時候，用於生成指數d、 e的散列函數(通常具有/=|《|/2 比特的輸出)經常用A4^示，並且應用於具有/t比特輸出的c7值的散列 函數用好表示。實際上，相同的散列函數可以在不同輸出長度的情況下使 用，並且因此有時使用符號好代替A.作為記憶符號，a中的橫杆指示將 函數的輸出用作指數.
如在MQV中，HMQV協議的通信與較早在圖1中所示出的基本DH 交換相同，具有可能附加的證書。如圖3中舉例說明的，在值rf和e的計 算中，會話密鑰K的計算不同於MQV的計算，其涉及對一方自己的DH 值以及對等體身份的散列。該散列的典型輸出是/叫《|/2比特。另外，在一 個示例性實施例中，HMQV將值^-^的散列指定到*比特的密鑰，其 中A是所期望的會話密鑰的長度.在可選的實施例中，沒有散列一個或兩 個cj函數.
根據本說明書，可以看出HMQV保持了 MQV在通信和計算兩方面
的顯著性能。與此同時，在兩消息協議中HMQV以最大可能的程度克服 了以上引用的臨時專利申請中所討論的MQV的所有安全性缺點，如文中 進一步討論和證明的。稍後在本申請中將給出對HMQV的安全特性和優 點及其變體的更為完整的說明。
詢問-應^"名
儘管現在應當清楚HMQV協議如何不同於MQV協議，然而本發明 還有另一方面，其在某種意義上甚至更為重要作為HMQV後面的核心 設計和分析元素的主要技術工具是一種新形式的交互式籤名，被稱為"詢 問-應^^名"，其是使用Fiat-Shamir方法基於Schnorr的識別方案的新 變體來實現的。因此，獲得了本發明的"指數詢問-應答"(XCR)籤名。 下面討論Schnorr和Fiat-Shamir方法與XCR籤名之間的關係。
這些XCR籤名在隨機諭示模型中(在計算性Diffie-Hellman或CDH 假設下一參見以下內容)是安全的，並且示例性地具有檢驗者和籤名者均 可以計算出相同籤名的特性.前者通過知道詢問來實現計算，以及後者可 以通過知道秘密籤名密鑰來實現計算。計算同樣的籤名的變體包括籤名者
和檢驗者的不同^目關的籤名的計算。
例如，由一人計算的籤名值可能是由另一人計算的籤名的散列變體，
或者它們可以通過某種特定的代數特性等而相關。本發明的各種HMQV 協議是使用這些XCR籤名的一種示例性機制，其中它們提供(對DH值 和對等身份的)認證以及會話密鑰計算。
因而，將要簡要討論的XCR籤名及其"雙重版本"(例如，DCR) 提供了從技術和概念上對以HMQV設計和分析為基礎的思想的自然解釋。
另外，注意到還可以在HMQV協議之外的應用中使用XCR籤名。在 XCR籤名的基本形式中，由於其是交互式、詢問專用以及不可轉移的，因 此XCR籤名並沒有提供數字籤名的典型功能性。也就是說，不可以將其 用於不可抵賴(non-repudiation)的目的。
另一方面，XCR籤名提供了對於某些應用(包括密鑰交換)來說重要
的特性一 "可否iU人證(deniable authentication )，，，由此，XCR籤名的 接受者可以確信消息或密鑰的起源和完整性，但是不能夠向任何第三方證 明該起源。特別地，這些籤名以及合成密鑰交換協議理論上適於"不宜報 道的(off-the-record)"通信以及隱私保護。另夕卜，如以下所討論的，XCR 的非交互式版本是存在的，並且在一些情況下，它們提供了可選方案來建 立籤名方案，例如公知的數字籤名算法(DSA)。
如在常規數字籤名方案中那樣，在詢問-應^"名方案中，籤名者具有 分別用於籤名的生成和抬，驗的一對私鑰和zi^鑰，並且^f^設檢驗者獲得籤名 者的可信公鑰。特別地，並不假設各方在啟動籤名協議之前共享秘密，也 不在籤名的計算中涉及這樣的共享秘密。然而，相比於常規籤名，在其基 本形式下，詢問-應M名是交互式的，並且需要籤名的接受者(例如，檢 驗者)在籤名者可以在給定消息上生成籤名之前向該籤名者發布詢問。安 全的詢問-應M名方案需^:證除了合法的籤名者之外任何人都不能夠 生成^^兌服詢問者將籤名接受為有效的籤名.特別地，籤名不僅是消息專 用的而且還是詢問專用的。
另一方面，確保詢問者對籤名的可檢驗性也是所關心的，並且因而沒 有假設或要求關於第三方對籤名的可轉移性或可^r驗性.此外，下面所描 述的具體方案具有這樣的特性，即選擇詢問的一方總是可以在任何消息上 生成籤名，該籤名關於該特定詢問有效。對本申請甚至更重要並且使本方 案區別於其它交互式籤名的是這樣的事實，即檢驗者可以使用詢問來計算 與籤名者相同(或相關)的籤名串。
如前所述，《是《階(通常是素數)的群(7的生成元。此外，i/是輸 出|《|/2比特(l3l= )的散列函數，但是再次使用"素數階"以及jy
的特定輸出長度僅僅是示例性實施例的示例性設計細節，而並不是本發明 所必需的。
XCR籤名方案的定義
圖4中所說明的指數詢問-應答(XCR )籤名方案500定義如下XCR
方案中由i表示的籤名者擁有私鑰6^z^以及7^必=/。由^表示的檢驗 者(或詢問者)提供i計算為(x^ z》的初始詢問a:,其中由i選擇jc 並保密。使用詢問a:將給定消息挑上S的籤名定義為cr，;r+^'一)對，其
中！^/且由》選擇少^Zg，並且以《為模減小指數y + ^(y，m)6。若且唯若 (ra離',"=cr成立時，檢驗者^接受籤名對(r， a)為有效(對於消息/ 和詢
問xf)。
我們4吏用下面的記號對於給定消息附、詢問at以及值r,我們定義 a57c^(n附,y)-義"吋'"06，即zs/g》表示XCR籤名對中的第二元素。作為 一般的附註，值得觀察以上對詞語"消息"的使用表示可以由比特流表示 的、任何形式的數據或信息，包括傳輸數據、文件、介質等，並且其自身 可以是較長消息的散列版本。可以將該消息輸入到各方，如圖5中所示， 或者可以將其從一方傳輸到另一方，或者其可以由第三方(外源)提供， 等等.
如本申請中所述，XCR籤名的優點包括分析健全性(可證明性)、 檢驗者和證明者均可計算性、二元性(單個計算代表雙方或多方籤名的結 合)、"可散列性"(即，作用於散列籤名並且檢JMt列籤名的能力)、 密鑰或公共值的導出、不可轉移性和可否認性、(從可否認籤名到常規的 不可抵賴籤名的)可轉換性、提供了比DSS更穩健的可選方案(尤其是在 交互式環境中)，以及非交互式變體的存在。
通過與從其導出XCR籤名的Schnorr的識別方案的關係，可以說明 設計XCR方案的動機。Schnorr的(交互式)識別方案包括在給定輸入 5-^時對離"fW數6的知識的證明。令》表示該方案中的證明者(其擁有 A)並且i表示檢驗者(其被給予輸入5)。基本的Schnorr的識別包括三 個消息
(i) 》選擇^^Z"並且將^=^發送至^;
(ii) ^利用隨機值e^Zg進行應答；以及
(iii) 》向^發送值5=^+&。若且唯若/= ^成立時，^接受。 該協議對於誠實的檢驗者j (例如，隨機統一選擇e的人)是對(6
的)知識的public-coin零知識證明。因此，通過^^知的Fiat-Shamir方法 可以將其變換成籤名方案，即57<^0) = (1^,;/ + //(7，附)6)，其在隨機諭示模 型中可證明是安全的。
現在，考慮下面的Schnorr協議的四消息變體，其中添加了從^到》的 第一消息。在該第一消息中，i向5發送值；^^。然後，緊接著是來自 Schnorr的方案的三個消息，除了在消息(iii)中，即在修改的協議中的第 四消息中，》發送5=^*，而不是向i發送5^H-e6。若且唯若S-(I^)"時i 接受。可以顯示出該協議是對》在任何值ZeG的情況下計算 Diffie-Hellman值CDH(5， A)的"能力"的證明。此外，該協議對於隨機 選擇e的檢驗者^是零知識的，而X是可以被任意選擇的。
通過將Fiat-Shamir變換應用於該協議，可以獲得本發明的詢問-應答 籤名XCR。這也解釋了為什麼在命名XCR方案時使用術語"指數"其 涉及用協議的最後的消息中的替換Schnorr方案中的s=>H^。
在上述臨時申請中進一步討論了在CDH假設下XCR籤名方案的安全 性的其它方面。
在解釋以上一些術語時，對於G中的兩個元素t/=g"、 K=gv，我們用 CD好(r， F)來表示應用Diffie-Hellman計算1/和K得到的結果(例如， CMT(fZ， D=g"v)。如果算法採用G中的元素對(r， F)作為輸入並且輸出 Diffie-Hellman結果CDH(C7， ^)，則將該算法稱為"G的CDH解算器 (solver)".在所述臨時申請中進一步提供的分析中所使用的主要的難處 理假設是計算性Diffie-Hellman( CDH M^設.如果對G的所有有效的CDH 解算器來說，對於f/，K ^ G ，解算器在(1/， K)對上計算正確值CZ)好(i7， ^ 的概率可忽略(在解算器的隨機硬幣(random coin)以及在G中對l/、 K 的獨立隨M擇上取得的概率)，那麼我們說CDH假設在群(7中成立。 A(7,m)中的比特數
令/是豆(y，/w)的輸出中的比特數。清楚地，較小的/意味著籤名方案 具有較高的效率。另一方面，太小的/意味著差的安全界限，因為一旦指 數^(y,w)可預測，籤名方案就不安全。但是對於安全目的而言需要多大的
/呢？
可以看出(參見以上引用的臨時申請中的討論)，設置/=1/2|《|提供了
良好的安全性能權衡，並且因此在XCR籤名的示例性說明中使用該值(並 且用於其對本發明的HMQV協議的示例性應用)。
改變與B交互的次序
在XCR籤名的一些應用中，特別是如應用於HMQV協議的分析，可 以改變詢問者i與籤名者》之間交互的次序。
在上面對XCR方案的定義中，i在向S提供詢問AT的同時向》呈現消
息附，從而允許》立即利用籤名對(r，^s/c^(:r,w,義))進行應答。在現在考慮
的修改版本中，具有下面的交互次序
(i) ^向》呈現消息w，並且》輸出y，然後，在某個稍後的時刻，
(ii) ^向5提供(y，附，A),並且》輸出^S7C^(r,w,義)。
現在，假設一方F向》查詢以取得該修改後的次序。特別地，F可以 交錯與》的不同交互，即F可以在運行相應的步驟(ii)之前運行步驟(i) 的幾個實例。這要求》在步驟(i)之後保持具有值F， y和w的狀態。當 F稍後在步驟(ii)中呈現(y，m，A)的時候，》核查在其狀態中其具有(Rim) 對，並且如果有的話，則利用A57G^(y，w，JO進行應答並且從其狀態清除(y，
附)(如果》在其狀態中不具有(r，附)對，那麼其不發布籤名)。
注意到對》的動作的該說明確保》對兩個不同的籤名決不會使用相同 的F值。可以易於檢驗，對XCR籤名的安全性的證明對於該修改後的次
序仍然有效，僅僅是因為所模擬的由》選擇r並不要求A:的知識，而僅要 求確定S(r，附)所需要的附值。
散列XCR變體(HCR):
有可能用(r，i/(a》對來替換XCR籤名對(r，(J)，其中H是散列函數， 並且這樣的"散列XCR"籤名縮寫為"HCR"。注意到，因為這樣的XCR 特性，即通過該XCR特性^r驗者對於給定的Y能夠重新計算cr ，然後其 還可以計算d)，並且因此能夠檢驗經修改的HCR籤名。
HCR籤名具有在某些設置中重要的一系列特性。例如，其可以比正常 的XCR籤名短、其可以產生隨機或偽隨機值、其可以預防攻擊者獲知(7 中的任何代數結構，等等。
特別地，在交互式和檢驗者專用認證環境中(例如在密鑰交換協議中)， HCR籤名提供了比DSA籤名更安全的可選方案。實際上，雖然在DSA中， 單個短暫指數(例如，DSA籤名的成分F/中的/0的公開通過洩，密 籤名密鑰而造成籤名方案徹底不安全，但是即使將短暫指數;;洩露給攻擊 者(倘若在這種情況下，籤名者測試詢問X的階次或使用輔助因子求冪迫 使該值具有至少g階)，HCR籤名仍然是不可偽造的。
非交互式XCR變體
XCR (以及HCR)籤名可以通過使X-v4而成為非交互式的，但卻是 檢驗者專用的，其中j是檢驗者的公鑰，如圖6所示。這提供了非常有效 的非交互式檢驗者專用可否認認^制。在變體中，不是使用i方的唯一 公鑰J，後者可以/JS布(例如，張貼在網站上)籤名者所使用的一個或多 個詢問，從而使得這些詢問即^^:在籤名時、在^本身不可用的情況下也 仍然可用。
可轉換的XCR籤名
XCR籤名的突出特性(特別地，該特性4吏得XCR籤名區別於其它的 "可否認"詢問應答機制，包括基於共享秘密和公鑰加密的那些)是將這 些籤名"轉換"成常規的、不可抵賴的籤名的能力，可轉換籤名擁有可否 認i人證的特性，即，它們僅可以由預期的接收者檢驗，並且還允許籤名者 在不洩露其秘密籤名密鑰的情況下最終證明他或她是給定籤名的作者。
舉例來說，對於在多年後必須被轉換成可檢驗的公開記錄的官方不宜 報導的通信來說，可能需要這一從秘密籤名到公開籤名的可轉換性。在 XCR籤名的情況下，在詢問X下，消息w上的籤名(y，fJ)可以通過揭露值 y + ^(y,m)6而由合法籤名者將其轉換成常規的不可抵賴的籤名。
雖然在文獻中已經出現了其它(接受者專用)的可轉換籤名，但是所 有這些都不允許預期的接受者(或詢問者)自己重新計算籤名，並且因此
不享有該重新計算特性提供給XCR籤名的很多優點，如以下雙重XCR籤 名所示例^沈明的。
雙重XCR籤名(DCR):
XCR籤名的重要特性在於已經選擇了詢問的詢問者可以自己計算籤 名。這裡示出了如何利用這一特性，以便導出具有這樣的特性的相關詢問-應M名方案(文中稱為"雙重XCR方案"，或簡稱為DCR),即該特 性在於，任何雙方i、糹均可以利用詢問者和籤名者的雙重角色彼此交互， 並且各自產生任何第三方均不能夠偽造的籤名。此外，所得到的2和B的 籤名具有相同的值，而這也使得該方案對於HMQV協議意義重大。更準 確地說，它們在XCR籤名對中具有相同的ASJG成分。
定義雙重(指數)詢問-應答(DCR)籤名方案，令i、》是分別具 有公鑰爿-g"、 5=^的雙方。令/in、附2是兩個消息。i和》分別在消息im、 w2上的雙重XCR籤名(簡稱DCR)被定義為三元組值AT、 y和 DS/G^—p附2,X，r)Bg"+必)0^)，其中x-^以及r-^是分別由i、》選擇 的詢問，並且符號i/和e分別表示^(X，m》和A(r，m2)。(參見圖7。)
如此，DCR籤名的基本特性在於在交換值AT和r (隨分別由^和》 選擇的；c和y)之後，j和》均可以計算(以及檢驗)相同的籤名 DS/G^(/w,，/^，X，r)。這可以從下面的等效中看出
D57G^》(wp附2，;r，;r) = g("血)("")=(^r廣血=(X4rfy+e6
其中，以《為模減少x+(/"和jH-d
此外，如以上引用的臨時申請中的討論所論汪的，攻擊者不能夠可行 地計算出該籤名。
概略地說，雙重籤名是在詢問！^下^在消息i^上的XCR籤名，並 且與此同時，是在詢問X^下》在消息附2上的XCR籤名。更準確地說， 由於值d和e是在籤名過程期間確定的(通過對消息,、附2的可能對抗的
選擇)，那麼可以論證S的DCR籤名就攻擊者沒有選擇的任何值爿=^來
說都是安全的。
基本HMQV協議在形式上的描述
在其基本的兩消息交換中，HMQV協議包括作為詢問的 Diffie-Hellman值A"-^和y-^在i方和》方之間的交換，雙方通過該詢問 計算雙重XCR籤名Z)57G^("i","》",m-g"+血)c。然後通過散列該值導 出會活密鑰。以這樣的方式，不需M輸籤名本身正是籤名的唯一性確 保了會話密鑰的公共導出值，並且正是計算密鑰(等效於籤名)的獨特能 力提供了對假定的^方和》方所進行的交換的證明.
"上，由於在其上計算籤名的消息im、附2是對等體的身份(即，i、 5)，因此雙方均可保證其所計算的密鑰唯一地必然是正確的身份.在籤 名下(特別地，在值i/和e的計算中)包括各方的身份(不僅僅是短暫的 Diffie-Hellman值)，其本質上是為了避免諸如UKS攻擊的一些認證失敗。
因此,在^和i雙方之間的HMQV協議的M包括具有被計算為好(7T) 的會話密鑰的DH值X-^和的基本Diffie-Hellman交換(圖1)，其
中;r-Z)57Gh(附「泉附2-^^r,:n。也就是說，丌是作為i和》在彼此身份上 的雙重籤名來計算的。以上簽名由簡寫;r(A氛X，:n表示，即
其中，d = ^(Z,》)、e-^(yj)，並且j=gfl、 J5=Z分別是i方和》方的公 鑰。注意到此刻;r(^，》，X，]r)-;r(》,凡;r，Z)。在變體中，好(丌)可以由丌的不 同函數替換，特別地，散列可以包括諸如各方身份等的附加信息，
HMQV協議通常在多方網絡中運行，其中可以調用任何一方來運行該 協議。在一方對協議的每次調用都創建會活(含有與協議的該特定實例相
關的信息的本地狀態)，其可以產生輸出消息以;Mt完成時輸出^密鑰。
在會話期間，可以利用三種類型的激活來如下激活一方(在下面的描述中， i表示被激活方的身份，並且i表示會活所期望的對等體的身份)
1.啟動(凡》)i生成值X-f， c^Z。，創建HMQV協議的本地會話，
她將其標識為(未完成)^(凡反義)，並且輸出值X作為其輸出消息。
該激活的意思是指^已經作為與5的會話的發起方^皮激活了 ，並且X 是作為該會話的一部分希望被傳遞給對等體》的消息。i方將被稱為M 的"持有者"(或"所有者")，》將是會話的"對等體"，並且X是輸 出(DH)值。
2. 應答(i，氛;r): ^檢查1^0。如果是的話，則其生成值X-^， c^4,
輸出x，並且完成具有標識符(麼》，m和會話密鑰^(冗(凡反uo)的會話。 這裡，i被激活作為在與對等體》的會話中以及輸入值y的應答者。在這 種情況下，j立即完成其會活(沒有進一步的輸入消息)。注意到，如果 輸入值r是零，則j忽略該激活。
3. 完成(凡泉m: i檢查i^o並且其有著具有標識符(凡》，;n的開放 會話。如果這些條件中有任何一個不滿足，則i忽略該激活，否則，其完
成具有會話標識符(麼泉y,r)和會話密鑰尺=H(;r(i，i,Z,:n)的會話.這表 示具有輸入值F的協議中第二消息的傳遞，(判定的)來自對等體》的應 答。
三消息HMQV-C協i義
圖8中描繪了三消息HMQV-C (其中C代表"密鑰確認")協議。 該協議享有HMQV的所有安全特性以及本質上相同的計算成本。然而， 其向協議添加了第三消息並且稍微增加了協議消息的長度。
作為回報，HMQV-C提供了^HMQV協議中缺少的一些特性，包 括密鑰確認、PFS以及通用可組合性。
密鑰確認
HMQV協議向^方提供了完成與對等體》的會話以及會活密鑰IT的基 本保證如果力沒有遭到破壞，那麼僅僅S有可能會知道X。該協議沒有 提供的是向i方作出》完成4^或計算出4^密鑰的任何保證.此外， 在執行會話期間，》可能還未"有效(alive)"。
這不僅僅是HMQV的缺點，因為對於基於公鑰的任何兩消息協議來
說，情況是相同的(假設，如在典型的乂iS鑰的情形下，在^與》之間較早
的通信處沒有創建任何在先共享狀態)。另外，如Shoup所指出的，並不 能夠通過任何密鑰交換協議來實現這看似自然的目標，即雙方均已保證在 各方開始使用密鑰之前對等體完成了會話。實際上，攻擊者總是可以通過 停止最後的協議消息來阻止這一相互保證達到其目的。
然而，對於每一方來說這樣的較弱保證是可實現的並且在文獻中被稱 為密鑰確認特性，即對等體能夠計算密鑰(但其不一定向調用應用輸出密 鑰)。雖然對於密鑰交換的基本安全性不是至關重要的(例如，缺少密鑰 確認並不威脅利用密鑰而保護的通信的保密性或可信性)，但是該特性可 以為一些應用提供有用的"操作穩健檢查(operationalsanity check)"。
在這種情況下，協議HMQV-C比HMQV更加合適，因為增加的MAC 值提供了密鑰確認。此外，MAC發汪確認了所標識的對等體對於會話的 有效涉及以及該對等體擁有匹配會話的事實(即，具有相同的對等體以及 相同的會話密鑰)。注意到為了實現這些特性，HMQV-C中的MAC不需 要應用於任何特定的會話信息，而僅僅應用於用來指示消息的"方向"並 防止反射的單個比特。還值得注意的是，僅由HMQV-C中的最初兩個消 息構成的協議已經向JL^fr提供了密鑰確認(其可以向HMQV添加有用 的特徵，而不增加協議消息的數目)，
在密鑰交換的4艮多應用中，缺少密鑰確認可能導致一種形式的"拒絕 服務"(DoS)攻擊，其中J方使用密鑰來開始，比方說向》發送受保護的 信息，而》不能夠處理該信息，因為其還未建立密鑰.如所述，這種情形 不能夠完全避免，因為不可實現相互的"會話完成"確認。
此外，存在針對基於/i^操作的協議的DoS攻擊的更為嚴重的形式， 其中， 一方被iML發現對等體無效之前花費相當大的計算周期(並且創建 會話狀態)。對DoS攻擊的一些有用但範圍有限的對抗措施 (counter-measure)是存在的，在增加協議消息的代價下，其可以應用於 任何的密鑰交換協議(包括HMQV)。
完全正向保密(PFS):
完全正向保密是密鑰交換協議非常需要的特性，由此，對長期私鑰的 洩漏並不危及舊的會話密鑰的安全性。更正式地，如果未遭破壞的^方建 立了與未遭破壞的對等體S的密鑰交換會話，那麼即使當攻擊者在K於^ 處過期之後破壞了^，或者其在^於》處過期之後破壞了S，會話密鑰^
仍保持安全。任何具有隱a證的兩消息協議，包括HMQV，均不能夠針 對有效攻擊者提供完整的完全正向保密。相反，我們可以希望的最好的是 由HMQV所提供的弱形式的PFS。如在臨時申請中進一步解釋的，相對 於基本的兩消息HMQV來說，HMQV-C的主要優點在於其解除了 HMQV 的這一固有限制並且4^供了完整的PFS。
通用可組合安全性
用於密鑰交換的Canetti/Krawczyk的模型(其是用於分析臨時申請中 的MQV和HMQV的基礎)已經被擴;IUU1具挑戰性的模型，其旨在確 保當與其它應用並發地運行時(如在真實世界環境下的情況)密鑰交換協 議的安全性。該模型被稱為密鑰交換的通用可組合(UC)模型。
對於HMQV-C來說，可以示出，當完成會話的第一方輸出其會話密 鑰時，對等體的狀態然後僅含有可以從協議和會活密鑰中的公共信息"模 擬"的信息。Canetti/Krawczyk示出，該特性連同在臨時申請中所示出的 HMQV的其它安全特性一:feA以保證HMQV協i義的通用可組合性.
單向(One-Pass) HMQV:
圖9中所示出的單向密鑰交換協議包括M送者^發送至接受者5的 單個消息，由此，只要雙方以及^"沒有如以下所定義的遭到破壞，雙方 使用其私鑰和公鑰就導出僅j和》有可能會知道的唯一密鑰。
來自所建立的密鑰的要求與常規密鑰交換協議中的相同，除了有可能 由》所接收的消息是對來自^的較舊的消息的重放之外。該重放在單向協 議中是不可避免的，儘管其可能是諸如同步時間或共享狀態的其它手段可 檢測的。
另外，這樣的協議不能夠提供PFS，因為就缺少來自S的會話專用輸
入來說，利用》的私鑰的單獨知識應當可計算密鑰。
在本發明的一個實施例中，在分別具有公鑰J-g"、 5=/的^方與》方
之間的單向HMQV協議包括從i傳輸至S的單個值其中由i選擇 xewZg。由a如下計算會話密鑰f:
(i) 令(凡》)表示包括兩個身份2和》的消息，並且將d設為 ^ = #(%，(凡》))的結果；
(ii) 計算0";=^5/(^(%，(凡》)，5) = ^+氣
(iii )設置《==//(o^),其中好輸出等於所要求的密鑰的長度的比特數。 在檢查Z-0之後，由》計算相同的密鑰《為-好((X4")"。在變體中，
換句話說，在單向HMQV的該實施例中的密鑰是將》的公鑰用作詢問 而從非交互式XCR籤名導出的。
還要指出，可以將單向協議用作認證選擇密文安全(CCA)加密方案。 也就是說，^可以向(由i )加密(針對選擇密文攻擊)及認證的》傳輸 消息附。在一個實施例中，^可以發送三元組(AT，c，0，其中X-^， c是作 為在密鑰&下對消息w的對稱選擇明文安全(CPA)加密而獲得的密文， 並且/是在密鑰X2下在c上計算的MAC值。如在單向HMQV協議中那 樣，密鑰A和A2是根據從AT計算的密鑰J5:而導出的。
該過程的4^P代價是對於^兩次求冪(一個^機的)並且對於》1.5 次求冪.相比於諸如DHIES (Diffie-Hellman集成加密方案)這樣的可選 CCA加密方案，這僅僅是對於》多了 1/2次求冪，但是，作為回報，其提 供了來自^的認證(利用DHIES，該認證將從^返回完整的附加籤名). 這一高效的認證CCA加密對於諸如通用的"頗好隱私(Pretty-Good Privacy, PGP)"應用這樣的"存儲轉發"應用4艮有吸引力，並且比常用 的籤名-加密範例便宜得多，這裡僅有的告誡在於需要清楚地傳輸身份i (以及有可能其證書)，如在解密操作中所需要的那樣。
然而以上協議還值得注意的另 一特性在於，可以將其僅僅用作i在消 息附上的檢驗者專用籤名，而不必增加加密部分。然而，該籤名^1接受者
專用的，並且因此其不具備不可抵賴性。相反，其具備在諸如PGP的很多 應用中m^"價值的特徵可否認性。
注意到已經採用MQV的很多標準也已經採用了其單向變體。對採用 各種形式(一個、兩個和三個消息)的HMQV感興趣的標準來"^兌，定義 在單向協議中的密鑰導出(類似於在HMQV的其它變體中的導出)會是 有意義的。
具體地，通過在定義了 HMQV協議的雙重籤名中用醜替換F，我們 獲得用於單向密鑰的以下值i和》分別計算 =(朋7+<^和 =(X4d:T6, 並且設置密鑰I至這些(相等的)值的散列。注意到在這種情況下，指數 e並不向協議添加任何值，除了使其可與其它變體兼容t外。其實際稍微 有損於協議效率。
然而，附加的差異保留在HMQV的單向版本中的值d = S(Z,(^左))與 兩消息版本中的d = A(X，》)之間。在三種模式之間提供兼容性的方式將是 使它們中都有^ = #(%，》)、e = #(lU),其中在單向的情況下r-醜，並且向 ^"密鑰導出函數添加身份^、》即，尺=//(0%麼》)(在使用某種固定 的準則所定義的^和》的階次的情況下)。這替代了對於在的計算中添 加^的需求。其還具有在洩漏預先計算的DH值的情況下加強HMQV並且 避免可能的未知密鑰共享攻擊的優點。
HMQV的安全方面的總結
相比於常規的MQV協議，HMQV協議提供了多個性能優點，包括以 下內容。HMQV可證明省卻了在協議中所傳輸的DH值上高代價的素數階 測試的需要。如在臨時申請中所論證的，攻擊者可以從選擇欺詐DH值獲 益的唯一方式是通過將其選擇零，並且因而，在HMQV中所要求的全在 於簡單的非零險查。因此，不需要素數階測試或者在MQV協議中並發使 用的輔助因子A。
下面是HMQV協議以數學可證明方式實現的一系列特性 (1) HMQV在Canetti和Krawczyk的強形式化(strong formal)密
鑰交換模型中是安全的；
(2) HMQV抵禦不具有對各方私鑰的訪問的攻擊者的假冒；
(3) HMQV在密鑰與各方的身份之間建立到交換的唯一綁定(通過 將XCR籤名應用於這些身份)，從而避免UKS和其它的認證攻擊；
(4) HMQV在出現部分洩漏會話密鑰以及其它會話信息的情況下也 是安全的；換句話說，HMQV抵抗所謂的"已知密鑰"攻擊。特別地，保 證不同的會話密鑰彼此"在計算上獨立"；
(5) 該協議提供了附加的保護級，稱為抗"密鑰洩漏假冒(KCI)" 攻擊，即其預防獲知A方私鑰的攻擊者能夠向A假冒其它方；
(6) 具有密鑰確認的三消息HMQV協議提供了可證明的完全正向保 密(PFS)，也就是說，即使雙方的長期私鑰最終被公開，在洩露之前由 這雙方所創建的會話密鑰仍保持安全；
(7) 具有密鑰確認的三消息協議享有所謂的"通用可組合"密鑰交換 協議的附加安全優點，即，可以將其與其它協議安全地進行組合；
(8) HMQV的安全性既不取決於靜態公鑰在形式和結構上的專門測 試，也不要求所謂的對相應私鑰的"擁有證明"。HMQV較之類似協議(包 括MQV)的這些優點使得iUit^構(CA)免於對註冊/iH^進行這些專門 檢查的負擔，從而提供更實際和實用的安4^證，特別是由於很多^fcCA 並不能夠或未被配置進行這些檢查。此外，值得注意的是，由CA特別執 行的這樣的測試(例如，證明擁有)使該協議公開了另外的安全弱點；
(9) 兩消息和三消息HMQV協議不需要測試短暫公鑰的階次(即， 值X和Y),從而避免在某些情況下可能高成本的測試。然而，如果該協 議的安全性將要抵禦可能獲知各方的短暫保密密鑰的攻擊者，則需要這些 測試。對於單向HMQV協議的安全性來說也需要該測試。如在MQV的 情況下，可以用協議中a值的"輔助因子求冪"來替換這些測試。可以根 據M代數群要求在群元素(例如預定群中的成員)上的附加測試。
本發明的HMQV協議的一個突出優點在於其是現有可論證的最高效 的認證Diffie-Hellman密鑰交換協議，具有可以以形式數學方式證明成立
的廣範圍的安全特性。實際上，該形式上的可證明性是HMQV與其前身 MQV之間的一個主要區別。
MQV不僅不具有安全性的證據，而且隨時間出現明顯的協議弱點(例 如，Kaliski的工作以及Rogaway等人的報告)，包括在以上引用的臨時 申請中首次描述的一些弱點。這些弱點或攻擊使得由其發明人作出的對 MQV的一些安全主張無效，並且特別地，它們顯示MQV不能夠被證明 是安全的。
XCR籤名與MQV的"隱含籤名(Implicit Signatures)"的比較 作為一種比較方式，值得注意的是，如在專利中以及在學術論文中所 描述的，MQV在協議的設計和描述中也使用籤名的概念。這些在MQV 的情況下被稱為"隱含籤名"，並且它們符合數字籤名的更常規的概念， 即其中簽名值僅可以由秘密籤名密鑰的所有者來產生(具體地，MQV涉 及由秘密籤名密鑰以及短暫保密密鑰和公鑰的線性組合所形成的類 ElGamal籤名)。然而，該協議不善於完4H吏用這些籤名的特性。特別地， MQV協議並不將籤名作為明確認ii^t協議的各方身份的方式來使用，這 導致嚴重的i人證失敗，例如由Kaliski所發現的著名的"未知密鑰共享 (UKS)"攻擊。
相比之下，HMQV在其設計中引入了兩個重要元素。 一個是使用 XCR，其是EIGamal籤名的指WL本。更具體而言，其是Schnorr的籤 名的指liU&本，其又是EIGamal籤名的特定例示.另一個是對等體的身份 的顯式籤名，其確保會活密鑰到會活的對等體的安全綁定，並且特別地， 預防諸如UKS的認證失敗。
XCR籤名的關鍵新穎性在於這樣的特性，即籤名者和檢驗者(或詢問 者)均可以計算出相同的籤名。該特性通常存在於基於共享密鑰密碼的認 證機制中(即，在籤名者和檢驗者均具有先驗共享密鑰的情況下)，M 基於公鑰的籤名中卻是新的。XCR籤名不僅非常適於導出共享密鑰，如在 HMQV中，而且其提供了作為認證工具的各種優點，其中一些優點在上面 進行了描迷。
本領域的普通技術人員應當清楚本發明涵蓋各種實施例。
因而，在一個示例性實施例中，存在雙方，檢驗者K和籤名者S。籤 名者<S具有私鑰6和公鑰5,並且假設檢驗者K擁有或獲得了 S的可信公 鑰J (例如，通過發送自S的數字證書)。對於給定消息附該認證協議包 括
(1) F選,密值JC並且計算值X-^(JC),其中屍7是給定函數，並
且向S發送AT。
(2) &選##密值3;並且計算值^= F2 00，其中&是給定函數，並 且向K傳輸F。
(3) S計算值F/^0，6，AT，w)，其中A是給定函數，並且向F傳輸
(4) K計算值& (jc， y， 5， w)，並錄於值s'及其與所接收的值s 的關係判定/fi的可信性。
該實施例的一些示例性變體包括
(a)&、 R是單向函數。在XCR中這些單向函ltAX-^和y-^.
(b )在xcr籤名中，函數"巧(>^，％,—=;^+維,並且
j'=《(:c，;K， A附)=(K5(^4y 。
(c)若且唯若s'=s時，接受附為認證。這一最後的變體利用了典型 的xcr籤名的特性，由此，檢驗者可以根據知道在詢問x之後的秘密來 重新計算籤名。
U)計算"^o^，x,附)-;^+^',並且測試好("-s，等等。
在將XCR應用於HMQV的至少一個實施例中，在步驟(3)中由S 計算的值s從不被發送至K。相反，F計算值s'，其將等於s(除非S是冒 名頂替者)，並且使用s (在HMQV中其是(J )來從中導出^f密鑰。特 別地，F從不實現顯式;j^驗。在該實施例中，不是用於抬r驗消息ffi的可信 性的方法，而會是這樣一種方法，即通過該方法，雙方計算公共"認證值" (即，有且只有雙方可以計算的值)，並且通過該方法，將該值唯一地綁 定到相應的身份(在HMQV中通過雙重XCR籤名，由各方身份的籤名所
獲得的、在典型的密鑰交換協議中的基本條件)。 在上文中及權利要求中描述了附加的變體。
示例性》更件實現
圖10說明了依照本發明的信息處理/計算機系統的典型硬體配置，並 且其優選地具有至少一個處理器或中央處理器(CPU) 1011。
CPU 1011通過系統總線1012互連於隨機訪問存儲器(RAM) 1014、 只讀存儲器(ROM) 1016、輸AJ輸出(I/O)適配器1018 (用於將諸如磁 盤單元1021和磁帶驅動器1040的外圍設備連接至總線1012)、用戶接口 適配器1022 (用於將鍵盤1024、滑鼠1026、揚聲器1028、擴音器1032 和/或其它用戶接口設備連接至總線1012)、用於將信息處理系統連接至數 據處理網絡、網際網路、內聯網、個人區域網(PAN)等的通信適配器1034, 以及用於將總線1012連接至顯示設備1038和/或印表機1039 (例如，數字 印表機等)的顯示器適配器1036。
除了上述硬體/軟體環境之外，本發明的不同方面包括用於實現以上方 法的計算機實現的方法.舉例來i兌，該方法可以在以上所討論的特定環境 中實現。
舉例來說，這樣的方法可以通過操作計算機(如由數字數據處理裝置 體現)來實現，以便執行機器可讀指令序列。這些指令可以駐留於各種類 型的信號承栽介質中。
因而，本發明的這一方面針對的是一種編程產品，其包括信號承栽介 質，該信號承栽介質有形地體現可由合併了 CPU 1011和以上硬體的數字 數據處理器執行的機器可讀指令的程序，以便實現本發明的方法。
該信號承載介質可以包括，例如，含於CPU 1011內的RAM,如由例 如快速訪問存儲器所表示的。可選地，指令可以含於CPU 1011可直接或 間接訪問的另一信號承栽介質(例如磁數據存儲磁碟1100 (圖11))中。
無論是否含於磁碟1100、計算機/CPU1011或其它地方，指令均可以 存儲在各種機器可讀數據存儲介質中，諸如DASD存儲器(例如，常規的
"硬碟驅動器，，或RAID陣列)、磁帶、電子只讀存儲器(例如，ROM、 EPROM或EEPROM)、光存^i殳備(例如，CD-ROM、 WORM、 DVD、 數字光帶，等等)、紙質"穿孔"卡片或其它合適的信號承栽介質，包括 諸如數字和模擬及通信鏈路和無線的傳輸介質。在本發明的說明性實施例 中，機器可讀指令可以包括軟體對象碼。
權利要求
1.一種在通過設備或網絡互連的雙方之間交換的方法，所述方法包括接受方(檢驗者)選擇用於計算值X＝F1(x)的秘密值x，其中F1包括具有至少一個自變量的第一預定函數，所述值x是F1的所述至少一個自變量之一；籤名方(籤名者)選擇用於計算值Y＝F2(y)的秘密值y，其中F2包括具有至少一個自變量的第二預定函數，所述值y是F2的所述至少一個自變量之一；所述籤名者獲得所述值x，所述籤名者具有私鑰b和公鑰B；以及所述籤名者計算值s＝F3(y，b，X)，其中F3包括具有至少三個自變量的第三預定函數，所述值y、所述私鑰b以及所述值x是F3的所述至少三個自變量中的三個自變量，其中存在第四預定函數F4(x，Y，B)以計算值s′，F4具有至少三個自變量，所述值x、所述值Y以及所述公鑰B是F4的所述至少三個自變量中的三個自變量，但所述值s不是F4的自變量，在所述檢驗者與所述籤名者之間不存在用作所述F1、F2、F3和F4的任何一個中的任何自變量的基礎的共享秘密，以及如果確定值s′以預定方式與值s相關，則所述檢驗者可以將所述值s和s′考慮為有效認證符。
2. 根據權利要求l的方法，其中F7和F2中的至少一個包括單向函數。
3. 根據權利要求l的方法，其中如果fs'，則確定所述值s和s'是有
4. 根據權利要求1的方法，其中，由除了所述檢驗者和所述籤名者之 外的一方執行以下中的至少一個計算,以及確定是否將所述值s和s'確 定為相關。
5. ^L據權利要求1的方法，其中所述值s和所述值s'用於導出雙方之 間共享的秘密。
6. 根據權利要求1的方法，其進一步包括所述檢驗者獲得所述值y，並且使用相同的值來計算所述值s'用於確 定s和s '是否以所述預定方式相關。
7. 根據權利要求1的方法，其中消息附將要被認證並且包括"的自 變量以及的自變量，從而允許所述值s和所述值s'包括所述消息w中 的信息；以及如果確定所述值s和s '以所述預定方式相關，則i人證所述消息。
8. 才艮據權利要求7的方法，其中所述值s和所述值s'用於導出雙方之 間共享的秘密。
9. 根據權利要求8的方法，其中所述消息m包括至少在所述交換中所 述方之一的身份。
10. 根據權利要求7的方法，其進一步包括 所述籤名者向所述^r驗者發送所述值s。
11. 根據權利要求7的方法，其中如果所述fs',則認證所述消息。
12. 根據權利要求l的方法，其中所述>！^ =/，容是《階有P辦的生成元，所述私鑰6是使得0《6 S《-1 的整數；所述值^=/， jc是使得0《;^《-l的整數，並且所述值F=^， j;是使得 0S"《-1的整數J以及所述籤名者計算所述值s-y;(x)力一"氣yi包括第一數學函數，以及/2 包括第二數學函數，並且自變量附包括消息。
13. 根據權利要求12的方法，其中《是素數。
14. 根據權利要求12的方法，其中如果確定所述值s與所述值s'以所 述預定方式相關，則視為認證所述消息w。
15. 根據權利要求14的方法，其中如果確定所述值s等於所述值s'，則視為認證所述消息 m。
16. 根據權利要求12的方法，其中/i包括恆等函數。
17. 根據權利要求12的方法，其中/2包旨列函數，以便散列/2的 所述自變量中的至少一個。
18. 根據權利要求17的方法，其中所述散列自變量之一是非空消息附。
19. 根據權利要求12的方法，其中所述消息附包括在計算機或系統 或網絡中的一方的身份。
20. 根據權利要求17的方法，其中/2(w，;r，_y，6) = >; + //(r,m)6mod《， 其中好包括是單向函數之一的密碼函數、加密函數以及密碼散列函數.
21. 根據權利要求20的方法，其中所述值s'-(yB,4)力w，其中/3(jc) 包括具有至少一個自變量的數學函數，所述值jc是/3(jc)的所述至少一個自變量中的一個自變量。
22. 根據權利要求21的方法，其中/3(;c"a:。
23. 根據權利要求21的方法，其進一步包括 若且唯若fs'時，認證所述消息w。
24. 根據權利要求21的方法，其中所述檢驗者具有私鑰"、公鑰J=gfl 以及消息m'，所述值s包括所述檢驗者在/ '上的籤名，與此同時所述值 s'包括所述籤名者在w上的籤名。
25. 根據權利要求24的方法，其中所述函數/3(" = ;(: + //(%，附')"1110<1《。
26. 根據權利要求l的方法，其中由所，驗者隨M擇jc，並且由 所述籤名者隨機選擇》
27. 根據權利要求l的方法，其中所述第一值X-^包括由所述檢驗 者公布以便可由所述籤名者檢索的值，從而準許所述認證的非交互式版本。
28. 根據權利要求21的方法，其中進一步散列所述值s和s'。
29. —種信號承載介質，其有形地體現可由數字處理裝置執行以便實 現權利要求1中所述方法的步驟中的至少一個的機器可讀指令的程序。
30. —種裝置，其包括計算器，以^更為所述籤名者計算權利要求1中所述的函數和F丄
31. —種用於在通過設備或網絡互連的雙方之間建立認證密鑰的方 法，所述方法包括給定具有私鑰fl和公鑰^的第一方，所述私鑰"是使得0Sa《g-l的 整數，仔是正整數，g是g階有卩l^的生成元，並且爿是由所述值g所生 成的群中的元素且計算為^=gfl，以及給定具有私鑰6和公鑰5=g6的第二方，所述私鑰6是使得O《6《g-1的整數，所述第 一方選擇用於計算值X=f的秘密值jc， jc是使得o " ^ -1的整 數，並且所述值AT被傳達給所述第二方；所述第二方選擇用於計算值的秘密值》，是使得os少s《-1的整數，並且所述值r被傳達給所述第一方；所述第一方計算值"yi(y,B，附)(力"'。'""，其中附、附'包括所述方之間已 知或交換的消息，並且所述第二方計算值,=/3(%乂附'){/4("'"°};所述函數/2和/4中的至少一個包括具有至少一個自變量的函數好，一 個這樣的自變量是所述消息附和附衝的至少一個，其中好包括是單向函數之一的密碼函數、加密函數以及密碼散列函數； 所述第 一和第二方分別從值s和W導出共享密鑰。
32. 根據權利要求31的方法，其中以下中的至少一個(i) 所述值jc和AT的計算包括所述第一方的私鑰以及所述方中一個 或多個的麼"統；以及(ii) 所述值y和y的計算包括所述第二方的私鑰以及所述方中一個 或多個的公鑰。
33. 根據權利要求31的方法，其中所^s和s'導出共享密鑰包括是 單向函數之一的密碼函數、加密函數以及密碼散列函數。
34. 根據權利要求31的方法，其中所述消息附和附衝的至少一個包 括所述第一和第二方之一的身份。
35. 根據權利要求31的方法，其中formula see original document page 6以及好是具有至少兩個自變量的函數，其包括是單向函數之一的密碼函數、 加密函數以及密碼散列函數。
36. 根據權利要求35的方法，其中所述消息附和附'中的至少一個包 括所述第一和第二方中至少一個的身份。
37. 根據權利要求36的方法，其中以下中的至少一個(i) 所述值jc和AT的計算包括所述第一方的私鑰以及所述方中一個 或多個的麼嘲；以及(ii) 所述值y和y的計算包括所述第二方的私鑰以及所述方中一個 或多個的公鑰。
38. 根據權利要求36的方法，其中所ii^s和s'導出共享密鑰包括是 單向函數之一的密碼函數、加密函數以及密碼散列函數.
全文摘要
本申請給出了HMQV，其是MQV認證Diffie-Hellman協議的變體。其提供了與原始協議相同的性能和功能性，但可以在形式上證明其安全目的成立。基於新的「詢問-應答籤名」方案設計了HMQV-MQV的「散列變體」。
文檔編號H04L9/08GK101116281SQ200680004479
公開日2008年1月30日 申請日期2006年2月10日 優先權日2005年2月10日
發明者H·克拉夫奇克 申請人:國際商業機器公司