CN101116281A - 询问-应答签名和安全迪菲-海尔曼协议 - Google Patents

Abstract

本申请给出了HMQV，其是MQV认证Diffie－Hellman协议的变体。其提供了与原始协议相同的性能和功能性，但可以在形式上证明其安全目的成立。基于新的“询问－应答签名”方案设计了HMQV－MQV的“散列变体”。

Description

询问-应答签名和安全迪菲-海尔曼协议

技术领域

本发明的各方面总体涉及对于信息交换的发送和接收方可证明是安全的签名。更具体而言，询问-应答(challenge-response)签名方案拥有检验者和签名者均可以计算出相同或相关的签名的特性，前者通过知道询问以及后者通过知道秘密签名密钥(private signature key)来计算，从而在示例性实施例中准许可证明是安全的、常规密钥交换协议的变体，包括公知的MQV协议的变体。

背景技术

如最初所建议的，图1中所示的Diffie-Hellman(迪菲-海尔曼，DH)密钥交换协议100被认为对于防御仅窃听(eavesdropping-only)的攻击者是安全的。对抵抗有效的、中间人攻击(man-in-the-middle attacks)的“认证Diffie-Hellman(authenticated Diffie-Hellman)”协议的搜寻已经导致了无数的ad-hoc(特定的)提议，它们中的很多已经损坏或者显示有缺点。随着近几年用于密钥交换的严密安全模型(rigorous security model)的发展，本领域的技术人员现在处于好得多的形势来判断这些协议的安全性，以及开发可证明抵抗现实有效攻击的设计。

如所期望的，添加防御有效攻击的防护措施导致复杂性增加，无论是在附加的通信方面还是在附加的计算方面。后者在利用公钥技术认证的协议中尤为重要，其通常要求附加的昂贵的群求幂(group exponentiation)。除了需要可靠的安全性之外，对密钥交换的很多实际应用已经促使设计者改进与认证机制关联的性能代价，尤其是基于公钥的那些。

由Matsumoto、Takashima和Imai在1986年发起的一条调查线(oneline of investigation)是对将向协议增加最小的复杂性的公钥(PK)认证DH协议的搜索。理论上，直至认证公钥的交换，协议的通信被期望完全看作是基本DH交换。在该技术中，必须通过密钥导出过程获得协议的认证：各方会对将g^x、g^y与各方的公钥/私钥相结合的密钥达成一致，而不是对基本Diffie-Hellman密钥g^xy达成一致。

一部分由于这样的协议将提供的实际优点，以及一部分由于在这样的设计之后的数学询问，在该方法下已经开发了很多协议，常被称为“可隐含认证的Diffie-Hellman协议”。该方法不仅可以生成作为非常有效的通信方式(communication-wise)的协议，而且与密钥导出过程相结合的认证可以潜在地导致显著的计算节约。由于这些原因，这些“可隐含认证的”协议中的几个协议已经被主要的国家和国际安全标准进行了标准化。

在这些协议中，MQV协议似乎已经被广泛标准化。很多组织已经将该协议标准化，并且最近美国国家安全局(NSA)已经宣布该协议是作为“保护美国政府信息的下一代密码术”的基础的密钥交换机制，其包括“密级(classified)或紧要使命(mission critical)国家安全信息”的保护。

另外，MQV似乎已经被设计以满足一批安全目标。例如，在Vanstone等人的第5,761,305号美国专利中解释了MQV协议的基本版本。

然而，尽管其具有吸引力并且获得了成功，但是在密钥交换的良好定义的模型中MQV迄今为止回避任何形式上的分析。本发明的动机便在于希望提供这样的分析。在进行研究时，发明人观察到实质上没有一个所陈述的MQV目标是可以被显示成立的，如在Canetti和Krawczyk的计算密钥交换模型中所实现的，以及如在以上标识的临时申请中所描述的。

该结果使得本发明人关注于这一常规协议的安全性。因此，基于常规的MQV协议不可证明是安全的这一分析，在优选地保持其现有性能和通用性的同时，存在对MQV增加安全性的需要。

发明内容

鉴于常规系统的前述以及其它的示例性问题、缺点以及劣势，本发明的示例性特征在于提供一种用于MQV的新变体(在文中称为HMQV)的方法和结构，其以可证明的方式实现了所述MQV协议的安全目标。

本发明的另一示例性特征在于论证一种新的数字签名方案，在文中称为“询问-应答签名”。

本发明的另一示例性特征在于将该询问-应答签名方案论证为包括从Schnorr识别方案导出的、在文中称为“指数询问-应答”(exponentialchallenge-response，XCR)签名方案的版本，论证为提供了一种具有询问者和签名者均可以计算出相同或相关签名的特性的协议机制，前者通过已经选择询问来计算以及后者通过知道秘密签名密钥来计算。

因此，本发明的示例性目的在于提供一种用于为认证Diffie-Hellman协议改进安全性的结构和方法，其中可以通过在其中实现XCR签名方案的概念来论证安全性是可证明的。

在本发明的第一示例性方面，为了实现以上特征和目的，文中描述了一种在通过设备或网络互连的双方之间交换的方法，其包括接受方(检验者)选择用于计算值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′考虑为有效认证符。

在本发明的第二和第三示例性方面，文中还描述了一种实现在前面段落中所描述的方法的装置，以及有形地体现可由数字处理装置执行以实现所述方法的机器可读指令的程序的信号承载介质。

在本发明的第四示例性方面，文中还描述了一种用于在通过设备或网络互连的双方之间建立认证密钥的方法。第一方具有私钥a和公钥A，所述私钥a是使得0≤a≤q-1的整数，q是正整数，g是q阶有限群的生成元(generator)，并且A是由所述值g生成的群中的元素且计算为A＝g^a。第二方具有私钥b和公钥B＝g^b，所述私钥b是使得0≤b≤q-1的整数。所述第一方选择用于计算值X＝g^x的秘密值x，x是使得0≤x≤q-1的整数，并且所述值X被传达至所述第二方。所述第二方选择用于计算值Y＝g^y的秘密值y，y是使得0≤y≤q-1的整数，并且所述值Y被传达至所述第一方。所述第一方计算值 $s=f_1(Y,B,m{)}^{\left\{f_2(x,a,m^{\′})\right\}},$ 其中m、m′包括所述方之间已知或交换的消息，并且所述第二方计算值 $s^{\′}=f_3{(X,A,m^{\′})}^{\left\{f_4(y,b,m)\right\}}.$ 所述函数f₂和f₄中的至少一个包括具有至少一个自变量的函数H，一个这样的自变量是所述消息m和m′中的至少一个，其中H包括是单向函数之一的密码函数、加密函数以及密码散列函数。所述第一和第二方分别从值s和s′导出共享密钥。

附图说明

根据下面参照附图对本发明的优选实施例的详细描述，可以更好地理解前述以及其它的目的、方面和优点，其中：

图1示出了基本(未认证)Diffie-Hellman协议100；

图2示出了通过使用数字签名认证的两消息Diffie-Hellman协议200；

图3示出了常规MQV协议中的会话密钥K的计算相对于本发明的HMQV协议的会话密钥的计算的比较300，在一个示例性实施例中论证了HMQV如何利用附加于MQV中所使用的散列的散列；

图4示出了与图3中所示出的HMQV协议不同的图示400；

图5示例性地示出了XCR的计算500；

图6示出了非交互式XCR签名的计算600的例子；

图7示出了双方的双重XCR签名的计算700；

图8示出了如在三消息密钥确认(HMQV-C)协议800中示例性体现的HMQV；

图9示出了如在单向(one-pass)密钥交换900中示例性体现的HMQV；

图10说明了用于在其中并入本发明的示例性硬件/信息处理系统1000；以及

图11说明了用于存储根据本发明的方法的程序的步骤的信号承载介质1100(例如，存储介质)。

具体实施方式

现参照附图，并且更具体地参照图1-11，其中示出了根据本发明的方法和结构的示例性实施例。

作为对群和记号的初步注记，文中所讨论的所有协议和操作均假设由生成元g所生成的、q(通常是素数)阶的循环群G。q的比特长度由|q|(例如意思是底为2的q的对数，上舍入为最接近的整数)表示，并且该量用作隐含安全参数。为简单起见，如实际中常见的，假设参数G、g和q是固定的并且各方预先已知。可选地，可以将这些值包括在证书等中。

文中使用群操作的乘法表示，但是该处理同样可应用于加法群，例如椭圆曲线或任何其它的代数群或特定群、有限域、复合模，等等。在协议中，用大写字母(例如，A、B)表示的公钥是群G中的元素，以及用相应的小写字母(例如，a、b)表示的私钥是Z_q中的元素，其中Z_q表示整数0，1，...，q-1的集合。

例如，公钥A＝g^a对应于私钥a。将A作为其公钥的一方将用

来表示，按惯例被认为是“Alice”(第二方

按惯例被认为是“Bob”)。通常，“补注记号(hat notation)”用于表示协议中各方的逻辑或“区别”身份，例如姓名、电子邮件地址、角色等。在一些情况下，可以为这些身份增补数字证书。对于在临时申请中所提供的较为完整的数学分析，这里不再重复，考虑通过概率多项式时间机来实现协议中包括攻击者在内的各方。攻击者还由M表示，其中M可以代表“恶意的(malicious)”。

因而，如图1中所示，对用于基本的未认证Diffie-Hellman协议100的会话密钥的计算包括在双方

之间的交换，其中

方首先向

方发送其密钥X＝g^x，并且

方然后通过将其密钥Y＝g^y传输回

方来应答，并且其中x和y是分别由

和

从集合Z_q随机选择的秘密，并且其中将共享会话密钥计算为g^xy。

注意到在文中的描述中，符号∈_R有时用于表示随机选择。例如，x∈_RZ_q意味着从整数集Z_q随机选择值x，通常通过使用随机或伪随机数字发生器。

MQV协议：

除了身份

可以包括诸如公钥证书这样的附加信息，或者可以将这些身份一起省略掉之外，MQV协议中的通信与图1中所描绘的基本的未认证DH协议100相同。

在设计两消息认证密钥交换协议中的第一询问是要基于第一协议消息的重放来防止成功的攻击。由于第一消息不能够包括由应答者所贡献的任何形式的、会话专用(session-specific)的“新鲜度保证(freshnessguarantee)”(例如，像nonce或新鲜的DH值)，因此这是有问题的。该问题的一个解决方案是通过计算会话密钥来提供新鲜度。

举例来说，如ISO(国际标准组织)9793协议所采用的，图2中所示出的两消息Diffie-Hellman协议200是使用数字签名认证的。虽然在的签名下包括g^x提供了认证的新鲜度，但是在

的消息中并不存在该保护措施。而会话密钥g^xy是保证新鲜的(并且与其它会话密钥无关)，因为其由新鲜的y随机化。然而，如果攻击者能够找到

在与

的会话中所使用的单个(x，g^x)对，则打破了协议的安全性，在这种情况下攻击者还获知这允许攻击者使用相同的消息及其对x的知识不定地向

假冒并且不需要曾必须获知的长期秘密签名密钥。

这是严重的弱点，其违犯了这样的基本原理，即对短暂的(ephemeral)会话专用信息(例如，(x，g^x)对)的公开不应当泄漏其它的会话。考虑到很多应用将脱机计算该(x，g^x)对并且将它们保留在较之比方说长期私钥来说保护得更少的存储器中，这就尤为严重。

所以如何能够设计一种即使在泄漏了短暂信息的时候仍可抗重放攻击(replay attack)的两消息协议？通常的回答是将长期私钥包括到会话密钥的计算中。这是Matsumoto、Takashima和Ima在1986年的工作已提出的方法，其激发了很多所谓的、Diffie-Hellman的“可隐含认证的”变体，包括MQV。在该方法中，每一方均具有长期DH公钥及其相应的秘密成分，并且通过将会话专用的短暂DH值与各方的公钥和私钥相结合而生成会话。因而，这样的协议的安全性完全取决于密钥的这一结合的准确细节。显著地，在具有若干缺点的所有先前的协议的情况下，这一表面上简单的想法是难以安全实现的。

现在考虑以下对在会话密钥计算中结合短暂和长期密钥的问题的通常的解决方案，当

和

想要交换密钥时，他们进行基本Diffie-Hellman协议并且计算会话密钥为K＝g^(x+a)(y+b)＝(YB)^x+a＝(XA)^y+b。在这种情况下，如果攻击者获知x而不知道a，则其不能够计算K。

然而，该协议仍然是不安全的，如由下面的简单攻击所论证的：M选择值x^*∈_RZ_q，计算 $X^{*}=g^{x^{*}}/A,$ 并且向

发送X＊作为对来自

的初始消息的假冒。

发送Y＝g^y并且计算会话密钥K＝(X*A)^y+b。遗憾的是，M还可以计算K为(BY)^x*。因而，该协议是不安全的。

此外，即使K的计算变成对于常数d、e的K＝g^(x+da)(y+eb)，那么攻击也仍然是可能的。另一方面，如果允许常数d、e以攻击者不能够分别控制e和Y的方式而随X和Y变化，则以上的简单攻击可能不起作用。该想法将我们带回到对MQV的设计，其中 $d=\stackrel{\‾}{X}$ 并且 $e=\stackrel{\‾}{Y}.$

图3中示出了MQV中的会话密钥K的计算301、302，其中

方拥有长期私钥a∈Z_q以及相应的公钥A＝g^a。类似地，B的私钥/公钥对是(b，B＝g^b)，并且短暂的DH值是X＝g^x、Y＝g^y，其中分别由A和B选择x、y。会话密钥的计算还使用值 $d=\stackrel{\‾}{X}$ 和 $e=\stackrel{\‾}{Y},$ 其中对于l＝|q|/2， $\stackrel{\‾}{X}=2^l+\left(X\mathrm{mod}{2}^l\right)$ 以及 $\stackrel{\‾}{Y}=2^l+\left(Y\mathrm{mod}{2}^l\right).$

注意到

对会话密钥的计算涉及用于计算X＝g^x的一个脱机求幂、用于计算B^e的一个在线求幂，以及用于(YB^e)^x+da的附加在线求幂。然而，还注意到第二求幂使用长度为|q|/2的指数e，并且因而其计数为“半求幂(halfexponentiation)”(例如，相对于g的正常求幂的模数乘法的一半数目)。操作的相同计数对于

成立。

总之，MQV的性能是真正让人印象深刻的：与基本的未认证DH协议相同的通信(除了对作为各方身份的一部分的证书的可能传输之外)以及只比基本协议多一半的求幂，其仅仅在计算上增加了25％以获得认证交换。这极大地好于依赖于用于认证的数字签名或公钥加密的、已证明的DH协议中的任何一个，这些协议涉及更昂贵的操作以及增加的带宽。它还是最有效率的可隐含认证的DH协议、最接近于要求三个完整求幂但提供相当少的安全特征的“统一模型(Unified Model)”协议。

当选择认证的DH协议时，这一非凡性能以及对安全性的承诺使得MQV成为有吸引力的候选者。由于这些原因，该协议已经被采用于很多标准并且在文献中得到广泛讨论。然而，由于还未在密钥交换安全的任何形式模型中成功地进行对MQV协议的任何形式上的分析，因此迄今为止仍未回答的一个问题是MQV协议真正地有多么安全。

另一方面，MQV设计者已经明确了在设计后面的安全目标。这些包括防御假冒和已知密钥攻击(包括抗“未知密钥共享(UKS)”攻击)的基本安全性，以及诸如完全正向保密(PFS)和抗KCI(密钥泄漏假冒)攻击的更具体的特征。抗已知密钥攻击表示这样的原理，即对短暂的会话专用秘密信息的公开不应当泄漏其它会话的安全性。

PFS和KCI特性涉及在一方的私钥泄漏给攻击者M的情况下对安全损害的限制。更具体而言，PFS意味着在两个未遭破坏方之间建立的任何会话密钥即使在会话密钥被从双方的存储器中清除之后双方遭破坏的情况下也不能够被M获知。抗KCI攻击要求获知

方的长期密钥并且因此可以明显地向其它方假冒

的攻击者不能够向

假冒其它的未遭破坏方。

遗憾地是，如以上引用的临时申请中所进一步描述的，本发明人的分析结果表明当在形式上进行研究时，MQV协议并不满足这些特性中的任何一个。特别地，在Canetti和Krawczyk的安全模型中论证到，该协议对一系列攻击开放，这与声称将由MQV满足的上述安全特性相矛盾。

HMQV协议：

HMQV协议(可以认为“H”是表示“散列(Hash)”)是MQV的简单但有效力的变体，在多个示例性实施例中，除了在步骤302中所示的用于比较的常规MQV协议之外，其还可以包括诸如图3中的步骤303所示的散列(hashing)。然而，还注意到，作为初始方式，这些示例性实施例的散列步骤并不是本发明的先决条件，这是因为无需散列以及使用不同于散列的技术的可选实施例在文中得到了讨论，并且还被包括在本发明的概念中。本发明更基本的概念涉及询问-应答签名方案，由此引申出多个应用和实施例，包括MQV协议的示例性散列版本。

本领域所公知的散列法涉及使用散列函数将字符串转化成数字、固定长度的串(例如，散列或消息摘要(digest))等作为输出。密码学中散列函数的基本功能性是具备“单向”或“不可逆”变换，意味着其对于检索原始数据应当是不可行的，并且对于构建匹配于给定散列值的数据块也是不可行的。散列函数的范围可以从简单的“混合”功能到类似纯粹随机置乱(scrambling)的变换。后者被称为“强密码散列函数”并且经常由理想随机函数(或“随机谕示(oracles)”)在密码分析中建模。

几个散列函数被广泛用于强密码散列。例如，MD5将任意大小的数据块作为输入，并且基于处理64字节的块中的数据的正弦函数，通过使用逐位操作、加法以及值的表格来产生128比特(16字节)的散列。另一主要的散列函数是提供160比特散列的NIST(国家标准技术研究所)安全散列算法(SHA)。

通常，散列函数不直接用于加密，但是加密函数却提供单向变换，并且因此可应用于一些散列用途，包括本发明的一些示例性实施例。散列函数还很适于数据认证，并且用于结合保密密钥这样的目的(在这些设置中，他们常被称为消息认证代码MAC或伪随机函数PRF)或签名方案(其中散列值用于“消息摘要”)。

本发明的各种示例性实施例使用至少一个散列函数H，该散列函数作为在以上所引用的临时申请中较为详细描述的安全分析中的理想随机谕示而被提取。在这些示例性实施例中为其使用函数H的两个任务如下：第一，计算指数d、e；以及第二，导出会话密钥本身。

第一任务示例性地对H使用两个自变量并且输出长度为|q|/2的串，而第二任务将H应用于单个自变量并且输出指定长度(例如，128比特)的密钥。为了简化记号，相同的符号H用于表示散列函数的两种应用。实际上，可以使用单个H，比方说，SHA-1，其可以处理可变长度的输入，并且可以调整其输出大小以适应以上两个任务，在产生散列结果时可能使用截断/扩充(truncation/expansion)的某种组合。

然而，还注意到，如果如在第一任务中那样使用散列，将不必将其限制于两个自变量，因为诸如时间戳、nonce等的附加自变量可以作为输入被包括到散列函数中，而不是仅散列消息或一方的身份。

当使用散列的时候，用于生成指数d、e的散列函数(通常具有l＝|q|/2比特的输出)经常用

来表示，并且应用于具有k比特输出的σ值的散列函数用H表示。实际上，相同的散列函数可以在不同输出长度的情况下使用，并且因此有时使用符号H代替

作为记忆符号，

中的横杆指示将函数的输出用作指数。

如在MQV中，HMQV协议的通信与较早在图1中所示出的基本DH交换相同，具有可能附加的证书。如图3中举例说明的，在值d和e的计算中，会话密钥K的计算不同于MQV的计算，其涉及对一方自己的DH值以及对等体身份的散列。该散列的典型输出是l＝|q|/2比特。另外，在一个示例性实施例中，HMQV将值 ${\mathrm{\σ}}_{\hat{A}}={\mathrm{\σ}}_{\hat{B}}$ 的散列指定到k比特的密钥，其中k是所期望的会话密钥的长度。在可选的实施例中，没有散列一个或两个σ函数。

根据本说明书，可以看出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签名提供了对于某些应用(包括密钥交换)来说重要的特性-“可否认认证(deniable authentication)”，由此，XCR签名的接受者可以确信消息或密钥的起源和完整性，但是不能够向任何第三方证明该起源。特别地，这些签名以及合成密钥交换协议理论上适于“不宜报道的(off-the-record)”通信以及隐私保护。另外，如以下所讨论的，XCR的非交互式版本是存在的，并且在一些情况下，它们提供了可选方案来建立签名方案，例如公知的数字签名算法(DSA)。

如在常规数字签名方案中那样，在询问-应答签名方案中，签名者具有分别用于签名的生成和检验的一对私钥和公钥，并且假设检验者获得签名者的可信公钥。特别地，并不假设各方在启动签名协议之前共享秘密，也不在签名的计算中涉及这样的共享秘密。然而，相比于常规签名，在其基本形式下，询问-应答签名是交互式的，并且需要签名的接受者(例如，检验者)在签名者可以在给定消息上生成签名之前向该签名者发布询问。安全的询问-应答签名方案需要保证：除了合法的签名者之外任何人都不能够生成会说服询问者将签名接受为有效的签名。特别地，签名不仅是消息专用的而且还是询问专用的。

另一方面，确保询问者对签名的可检验性也是所关心的，并且因而没有假设或要求关于第三方对签名的可转移性或可检验性。此外，下面所描述的具体方案具有这样的特性，即选择询问的一方总是可以在任何消息上生成签名，该签名关于该特定询问有效。对本申请甚至更重要并且使本方案区别于其它交互式签名的是这样的事实，即检验者可以使用询问来计算与签名者相同(或相关)的签名串。

如前所述，g是q阶(通常是素数)的群G的生成元。此外，H是输出|q|/2比特

的散列函数，但是再次使用“素数阶”以及H的特定输出长度仅仅是示例性实施例的示例性设计细节，而并不是本发明所必需的。

XCR签名方案的定义：

图4中所说明的指数询问-应答(XCR)签名方案500定义如下：XCR方案中由表示的签名者拥有私钥b∈_RZ_q以及公钥B＝g^b。由

表示的检验者(或询问者)提供计算为X＝g^x(x∈_RZ_q)的初始询问X，其中由

选择x并保密。使用询问X将给定消息m上

的签名定义为

对，其中Y＝g^y且由

选择y∈_RZ_q，并且以q为模减小指数

当且仅当 ${\left({\mathrm{YB}}^{\stackrel{\‾}{H}(Y,m)}\right)}^x=\mathrm{\σ}$ 成立时，检验者

接受签名对(Y，σ)为有效(对于消息m和询问X＝g^x)。

我们使用下面的记号：对于给定消息m、询问X以及值Y，我们定义 ${\mathrm{XSIG}}_B(Y,m,X)=X^{y+\stackrel{\‾}{H}(Y,m)b},$ 即

表示XCR签名对中的第二元素。作为一般的附注，值得观察以上对词语“消息”的使用表示可以由比特流表示的、任何形式的数据或信息，包括传输数据、文件、介质等，并且其自身可以是较长消息的散列版本。可以将该消息输入到各方，如图5中所示，或者可以将其从一方传输到另一方，或者其可以由第三方(外源)提供，等等。

如本申请中所述，XCR签名的优点包括：分析健全性(可证明性)、检验者和证明者均可计算性、二元性(单个计算代表双方或多方签名的结合)、“可散列性”(即，作用于散列签名并且检验散列签名的能力)、密钥或公共值的导出、不可转移性和可否认性、(从可否认签名到常规的不可抵赖签名的)可转换性、提供了比DSS更稳健的可选方案(尤其是在交互式环境中)，以及非交互式变体的存在。

通过与从其导出XCR签名的Schnorr的识别方案的关系，可以说明设计XCR方案的动机。Schnorr的(交互式)识别方案包括在给定输入B＝g^b时对离散对数b的知识的证明。令

表示该方案中的证明者(其拥有b)并且表示检验者(其被给予输入B)。基本的Schnorr的识别包括三个消息：

(i)选择y∈_RZ_q，并且将Y＝g^y发送至

(ii)

利用随机值e∈_RZ_q进行应答；以及

(iii)

向

发送值s＝y+eb。当且仅当g^s＝YB^e成立时，

接受。该协议对于诚实的检验者

(例如，随机统一选择e的人)是对(b的)知识的public-coin零知识证明。因此，通过公知的Fiat-Shamir方法可以将其变换成签名方案，即 ${\mathrm{SIG}}_{\hat{B}}\left(m\right)=(Y,y+H(Y,m)b),$ 其在随机谕示模型中可证明是安全的。

现在，考虑下面的Schnorr协议的四消息变体，其中添加了从

到的第一消息。在该第一消息中，向

发送值X＝g^x。然后，紧接着是来自Schnorr的方案的三个消息，除了在消息(iii)中，即在修改的协议中的第四消息中，

发送S＝X^s，而不是向

发送s＝y+eb。当且仅当S＝(YB^e)^x时

接受。可以显示出该协议是对

在任何值X∈G的情况下计算Diffie-Hellman值CDH(B，X)的“能力”的证明。此外，该协议对于随机选择e的检验者是零知识的，而X是可以被任意选择的。

通过将Fiat-Shamir变换应用于该协议，可以获得本发明的询问-应答签名XCR。这也解释了为什么在命名XCR方案时使用术语“指数”：其涉及用协议的最后的消息中的X^s替换Schnorr方案中的s＝y+eb。

在上述临时申请中进一步讨论了在CDH假设下XCR签名方案的安全性的其它方面。

在解释以上一些术语时，对于G中的两个元素U＝g^u、V＝g^v，我们用CDH(U，V)来表示应用Diffie-Hellman计算U和V得到的结果(例如，CDH(U，V)＝g^uv)。如果算法采用G中的元素对(U，V)作为输入并且输出Diffie-Hellman结果CDH(U，V)，则将该算法称为“G的CDH解算器(solver)”。在所述临时申请中进一步提供的分析中所使用的主要的难处理假设是计算性Diffie-Hellman(CDH服设。如果对G的所有有效的CDH解算器来说，对于U，V∈_RG，解算器在(U，V)对上计算正确值CDH(U，V)的概率可忽略(在解算器的随机硬币(random coin)以及在G中对U、V的独立随机选择上取得的概率)，那么我们说CDH假设在群G中成立。

中的比特数：

令l是

的输出中的比特数。清楚地，较小的l意味着签名方案具有较高的效率。另一方面，太小的l意味着差的安全界限，因为一旦指数

可预测，签名方案就不安全。但是对于安全目的而言需要多大的l呢？

可以看出(参见以上引用的临时申请中的讨论)，设置l＝1/2|q|提供了良好的安全性能权衡，并且因此在XCR签名的示例性说明中使用该值(并且用于其对本发明的HMQV协议的示例性应用)。

改变与B交互的次序：

在XCR签名的一些应用中，特别是如应用于HMQV协议的分析，可以改变询问者

与签名者之间交互的次序。

在上面对XCR方案的定义中，

在向

提供询问X的同时向

呈现消息m，从而允许

立即利用签名对

进行应答。在现在考虑的修改版本中，具有下面的交互次序：

(i)

向

呈现消息m，并且

输出Y，然后，在某个稍后的时刻，

(ii)

向

提供(Y，m，X)，并且

输出

现在，假设一方F向

查询以取得该修改后的次序。特别地，F可以交错与

的不同交互，即F可以在运行相应的步骤(ii)之前运行步骤(i)的几个实例。这要求

在步骤(i)之后保持具有值Y，y和m的状态。当F稍后在步骤(ii)中呈现(Y，m，X)的时候，核查在其状态中其具有(Y，m)对，并且如果有的话，则利用

进行应答并且从其状态清除(Y，m)(如果

在其状态中不具有(Y，m)对，那么其不发布签名)。

注意到对

的动作的该说明确保

对两个不同的签名决不会使用相同的Y值。可以易于检验，对XCR签名的安全性的证明对于该修改后的次序仍然有效，仅仅是因为所模拟的由

选择Y并不要求X的知识，而仅要求确定

所需要的m值。

散列XCR变体(HCR)：

有可能用(Y，H(σ))对来替换XCR签名对(Y，σ)，其中H是散列函数，并且这样的“散列XCR”签名缩写为“HCR”。注意到，因为这样的XCR特性，即通过该XCR特性检验者对于给定的Y能够重新计算σ，然后其还可以计算H(σ)，并且因此能够检验经修改的HCR签名。

HCR签名具有在某些设置中重要的一系列特性。例如，其可以比正常的XCR签名短、其可以产生随机或伪随机值、其可以预防攻击者获知σ中的任何代数结构，等等。

特别地，在交互式和检验者专用认证环境中(例如在密钥交换协议中)，HCR签名提供了比DSA签名更安全的可选方案。实际上，虽然在DSA中，单个短暂指数(例如，DSA签名的成分r＝g^k中的k)的公开通过泄露秘密签名密钥而造成签名方案彻底不安全，但是即使将短暂指数y泄露给攻击者(倘若在这种情况下，签名者测试询问X的阶次或使用辅助因子求幂迫使该值具有至少q阶)，HCR签名仍然是不可伪造的。

非交互式XCR变体：

XCR(以及HCR)签名可以通过使X＝A而成为非交互式的，但却是检验者专用的，其中A是检验者的公钥，如图6所示。这提供了非常有效的非交互式检验者专用可否认认证机制。在变体中，不是使用

方的唯一公钥A，后者可以公布(例如，张贴在网站上)签名者所使用的一个或多个询问，从而使得这些询问即使是在签名时、在

本身不可用的情况下也仍然可用。

可转换的XCR签名：

XCR签名的突出特性(特别地，该特性使得XCR签名区别于其它的“可否认”询问应答机制，包括基于共享秘密和公钥加密的那些)是将这些签名“转换”成常规的、不可抵赖的签名的能力。可转换签名拥有可否认认证的特性，即，它们仅可以由预期的接收者检验，并且还允许签名者在不泄露其秘密签名密钥的情况下最终证明他或她是给定签名的作者。

举例来说，对于在多年后必须被转换成可检验的公开记录的官方不宜报道的通信来说，可能需要这一从秘密签名到公开签名的可转换性。在XCR签名的情况下，在询问X下，消息m上的签名(Y，σ)可以通过揭露值

而由合法签名者将其转换成常规的不可抵赖的签名。

虽然在文献中已经出现了其它(接受者专用)的可转换签名，但是所有这些都不允许预期的接受者(或询问者)自己重新计算签名，并且因此不享有该重新计算特性提供给XCR签名的很多优点，如以下双重XCR签名所示例说明的。

双重XCR签名(DCR)：

XCR签名的重要特性在于已经选择了询问的询问者可以自己计算签名。这里示出了如何利用这一特性，以便导出具有这样的特性的相关询问-应答签名方案(文中称为“双重XCR方案”，或简称为DCR)，即该特性在于，任何双方

均可以利用询问者和签名者的双重角色彼此交互，并且各自产生任何第三方均不能够伪造的签名。此外，所得到的

和

的签名具有相同的值，而这也使得该方案对于HMQV协议意义重大。更准确地说，它们在XCR签名对中具有相同的XSIG成分。

定义：双重(指数)询问-应答(DCR)签名方案。令

是分别具有公钥A＝g^a、B＝g^b的双方。令m₁、m₂是两个消息。

和

分别在消息m₁、m₂上的双重XCR签名(简称DCR)被定义为三元组值：X、Y和

其中X＝g^x以及Y＝g^y是分别由

选择的询问，并且符号d和e分别表示

和

(参见图7。)

如此，DCR签名的基本特性在于：在交换值X和Y(随分别由

和

选择的x和y)之后，

和

均可以计算(以及检验)相同的签名

这可以从下面的等效中看出：

${\mathrm{DSIG}}_{\hat{A},\hat{B}}(m_1,m_2,X,Y)=g^{(x+\mathrm{da})(y+\mathrm{eb})}={\left({\mathrm{YB}}^e\right)}^{x+\mathrm{da}}={\left({\mathrm{XA}}^d\right)}^{y+\mathrm{eb}}$

其中，以q为模减少x+da和y+eb。

此外，如以上引用的临时申请中的讨论所论证的，攻击者不能够可行地计算出该签名。

概略地说，双重签名是在询问YB^e下

在消息m₁上的XCR签名，并且与此同时，是在询问XA^d下

在消息m₂上的XCR签名。更准确地说，由于值d和e是在签名过程期间确定的(通过对消息m₁、m₂的可能对抗的选择)，那么可以论证

的DCR签名就攻击者没有选择的任何值A＝g^a来说都是安全的。

基本HMQV协议在形式上的描述：

在其基本的两消息交换中，HMQV协议包括作为询问的Diffie-Hellman值X＝g^x和Y＝g^y在方和

方之间的交换，双方通过该询问计算双重XCR签名 ${\mathrm{DSIG}}_{\hat{A},\hat{B}}({}^{\′\′}\hat{A}^{\′\′},{}^{\′\′}\hat{B}^{\′\′},X,Y)=g^{(x+\mathrm{da})(y+\mathrm{eb})}.$ 然后通过散列该值导出会话密钥。以这样的方式，不需要传输签名本身：正是签名的唯一性确保了会话密钥的公共导出值，并且正是计算密钥(等效于签名)的独特能力提供了对假定的

方和

方所进行的交换的证明。

基本上，由于在其上计算签名的消息m₁、m₂是对等体的身份(即，

因此双方均可保证其所计算的密钥唯一地必然是正确的身份。在签名下(特别地，在值d和e的计算中)包括各方的身份(不仅仅是短暂的Diffie-Hellman值)，其本质上是为了避免诸如UKS攻击的一些认证失败。

因此，在

和

双方之间的HMQV协议的会话包括具有被计算为H(π)的会话密钥的DH值X＝g^x和Y＝g^y的基本Diffie-Hellman交换(图1)，其中 $\mathrm{\π}={\mathrm{DSIG}}_{\hat{A},\hat{B}}(m_1=\hat{B},m_2=\hat{A},X,Y).$ 也就是说，π是作为

和

在彼此身份上的双重签名来计算的。以上签名由简写

表示，即：

$\mathrm{\π}(\hat{A},\hat{B},X,Y)B{\mathrm{DSIG}}_{\hat{A},\hat{B}}(m_1=\hat{B},m_2=\hat{A},X,Y)=g^{(x+\mathrm{da})(y+\mathrm{eb})}$

其中， $d=\stackrel{\‾}{H}(X,\hat{B}),$ $e=\stackrel{\‾}{H}(Y,\hat{A}),$ 并且A＝g^a、B＝g^y分别是

方和

方的公钥。注意到此刻 $\mathrm{\π}(\hat{A},\hat{B},X,Y)=\mathrm{\π}(\hat{B},\hat{A},Y,X).$ 在变体中，H(π)可以由π的不同函数替换，特别地，散列可以包括诸如各方身份等的附加信息。

HMQV协议通常在多方网络中运行，其中可以调用任何一方来运行该协议。在一方对协议的每次调用都创建会话(含有与协议的该特定实例相关的信息的本地状态)，其可以产生输出消息以及在完成时输出会话密钥。在会话期间，可以利用三种类型的激活来如下激活一方(在下面的描述中，

表示被激活方的身份，并且

表示会话所期望的对等体的身份)：

1.启动

生成值X＝g^x，x∈_RZ_q，创建HMQV协议的本地会话，她将其标识为(未完成)会话

并且输出值X作为其输出消息。

该激活的意思是指

已经作为与

的会话的发起方被激活了，并且X是作为该会话的一部分希望被传递给对等体

的消息。

方将被称为会话的“持有者”(或“所有者”)，

将是会话的“对等体”，并且X是输出(DH)值。

2.应答

检查Y≠0。如果是的话，则其生成值X＝g^x，x∈_RZ_q，输出X，并且完成具有标识符

和会话密钥

的会话。这里，被激活作为在与对等体

的会话中以及输入值Y的应答者。在这种情况下，立即完成其会话(没有进一步的输入消息)。注意到，如果输入值Y是零，则忽略该激活。

3.完成

检查Y≠0并且其有着具有标识符

的开放会话。如果这些条件中有任何一个不满足，则

忽略该激活，否则，其完成具有会话标识符

和会话密钥 $K=H\left(\mathrm{\π}(\hat{A},\hat{B},X,Y)\right)$ 的会话。这表示具有输入值Y的协议中第二消息的传递，(判定的)来自对等体

的应答。

三消息HMQV-C协议：

图8中描绘了三消息HMQV-C(其中C代表“密钥确认”)协议。该协议享有HMQV的所有安全特性以及本质上相同的计算成本。然而，其向协议添加了第三消息并且稍微增加了协议消息的长度。

作为回报，HMQV-C提供了基本HMQV协议中缺少的一些特性，包括密钥确认、PFS以及通用可组合性。

密钥确认：

HMQV协议向

方提供了完成与对等体

的会话以及会话密钥K的基本保证：如果

没有遭到破坏，那么仅仅

有可能会知道K。该协议没有提供的是：向方作出

完成会话或计算出会话密钥的任何保证。此外，在执行会话期间，可能还未“有效(alive)”。

这不仅仅是HMQV的缺点，因为对于基于公钥的任何两消息协议来说，情况是相同的(假设，如在典型的公钥的情形下，在与

之间较早的通信处没有创建任何在先共享状态)。另外，如Shoup所指出的，并不能够通过任何密钥交换协议来实现这看似自然的目标，即双方均已保证在各方开始使用密钥之前对等体完成了会话。实际上，攻击者总是可以通过停止最后的协议消息来阻止这一相互保证达到其目的。

然而，对于每一方来说这样的较弱保证是可实现的并且在文献中被称为密钥确认特性，即对等体能够计算密钥(但其不一定向调用应用输出密钥)。虽然对于密钥交换的基本安全性不是至关重要的(例如，缺少密钥确认并不威胁利用密钥而保护的通信的保密性或可信性)，但是该特性可以为一些应用提供有用的“操作稳健检查(operational sanity check)”。

在这种情况下，协议HMQV-C比HMQV更加合适，因为增加的MAC值提供了密钥确认。此外，MAC验证确认了所标识的对等体对于会话的有效涉及以及该对等体拥有匹配会话的事实(即，具有相同的对等体以及相同的会话密钥)。注意到为了实现这些特性，HMQV-C中的MAC不需要应用于任何特定的会话信息，而仅仅应用于用来指示消息的“方向”并防止反射的单个比特。还值得注意的是，仅由HMQV-C中的最初两个消息构成的协议已经向发起者提供了密钥确认(其可以向HMQV添加有用的特征，而不增加协议消息的数目)。

在密钥交换的很多应用中，缺少密钥确认可能导致一种形式的“拒绝服务”(DoS)攻击，其中

方使用密钥来开始，比方说向

发送受保护的信息，而不能够处理该信息，因为其还未建立密钥。如所述，这种情形不能够完全避免，因为不可实现相互的“会话完成”确认。

此外，存在针对基于公钥操作的协议的DoS攻击的更为严重的形式，其中，一方被迫在发现对等体无效之前花费相当大的计算周期(并且创建会话状态)。对DoS攻击的一些有用但范围有限的对抗措施(counter-measure)是存在的，在增加协议消息的代价下，其可以应用于任何的密钥交换协议(包括HMQV)。

完全正向保密(PFS)：

完全正向保密是密钥交换协议非常需要的特性，由此，对长期私钥的泄漏并不危及旧的会话密钥的安全性。更正式地，如果未遭破坏的

方建立了与来遭破坏的对等体

的密钥交换会话，那么即使当攻击者在K于

处过期之后破坏了

或者其在K于处过期之后破坏了

会话密钥K仍保持安全。任何具有隐含认证的两消息协议，包括HMQV，均不能够针对有效攻击者提供完整的完全正向保密。相反，我们可以希望的最好的是由HMQV所提供的弱形式的PFS。如在临时申请中进一步解释的，相对于基本的两消息HMQV来说，HMQV-C的主要优点在于其解除了HMQV的这一固有限制并且提供了完整的PFS。

通用可组合安全性：

用于密钥交换的Canetti/Krawczyk的模型(其是用于分析临时申请中的MQV和HMQV的基础)已经被扩展成更具挑战性的模型，其旨在确保当与其它应用并发地运行时(如在真实世界环境下的情况)密钥交换协议的安全性。该模型被称为密钥交换的通用可组合(UC)模型。

对于HMQV-C来说，可以示出，当完成会话的第一方输出其会话密钥时，对等体的状态然后仅含有可以从协议和会话密钥中的公共信息“模拟”的信息。Canetti/Krawczyk示出，该特性连同在临时申请中所示出的HMQV的其它安全特性一起足以保证HMQV协议的通用可组合性。

单向(One-Pass)HMQV：

图9中所示出的单向密钥交换协议包括从发送者

发送至接受者

的单个消息，由此，只要双方以及会话没有如以下所定义的遭到破坏，双方使用其私钥和公钥就导出仅

和

有可能会知道的唯一密钥。

来自所建立的密钥的要求与常规密钥交换协议中的相同，除了有可能由

所接收的消息是对来自

的较旧的消息的重放之外。该重放在单向协议中是不可避免的，尽管其可能是诸如同步时间或共享状态的其它手段可检测的。

另外，这样的协议不能够提供PFS，因为就缺少来自

的会话专用输入来说，利用

的私钥的单独知识应当可计算密钥。

在本发明的一个实施例中，在分别具有公钥A＝g^a、B＝g^b的

方与方之间的单向HMQV协议包括从

传输至的单个值X＝g^x，其中由

选择x∈_RZ_q。由

如下计算会话密钥K：

(i)令

表示包括两个身份

和

的消息，并且将d设为 $d=\stackrel{\‾}{H}(X,(\hat{A},\hat{B}))$ 的结果；

(ii)计算 ${\mathrm{\σ}}_{\hat{A}}=\mathrm{XSI}{G}_{\hat{A}}(X,(\hat{A},\hat{B}),B)=B^{x+\mathrm{da}};$

(iii)设置 $K=H\left({\mathrm{\σ}}_{\hat{A}}\right),$ 其中H输出等于所要求的密钥的长度的比特数。在检查X≠0之后，由

计算相同的密钥K为K＝H((XA^d)^b)。在变体中， $K=H(\mathrm{\σ},\hat{A},\hat{B}).$

换句话说，在单向HMQV的该实施例中的密钥是将

的公钥用作询问而从非交互式XCR签名导出的。

还要指出，可以将单向协议用作认证选择密文安全(CCA)加密方案。也就是说，

可以向(由

)加密(针对选择密文攻击)及认证的

传输消息m。在一个实施例中，

可以发送三元组(X，c，t)，其中X＝g^x，c是作为在密钥K₁下对消息m的对称选择明文安全(CPA)加密而获得的密文，并且t是在密钥K₂下在c上计算的MAC值。如在单向HMQV协议中那样，密钥K₁和K₂是根据从X计算的密钥K而导出的。

该过程的全部代价是对于

两次求幂(一个是脱机的)并且对于

1.5次求幂。相比于诸如DHIES(Diffie-Hellman集成加密方案)这样的可选CCA加密方案，这仅仅是对于

多了1/2次求幂，但是，作为回报，其提供了来自

的认证(利用DHIES，该认证将从

返回完整的附加签名)。这一高效的认证CCA加密对于诸如通用的“颇好隐私(Pretty-GoodPrivacy，PGP)”应用这样的“存储转发”应用很有吸引力，并且比常用的签名-加密范例便宜得多。这里仅有的告诫在于需要清楚地传输身份

(以及有可能其证书)，如在解密操作中所需要的那样。

然而以上协议还值得注意的另一特性在于，可以将其仅仅用作

在消息m上的检验者专用签名，而不必增加加密部分。然而，该签名是接受者专用的，并且因此其不具备不可抵赖性。相反，其具备在诸如PGP的很多应用中很有价值的特征：可否认性。

注意到已经采用MQV的很多标准也已经采用了其单向变体。对采用各种形式(一个、两个和三个消息)的HMQV感兴趣的标准来说，定义在单向协议中的密钥导出(类似于在HMQV的其它变体中的导出)会是有意义的。

具体地，通过在定义了HMQV协议的双重签名中用B替换Y，我们获得用于单向密钥的以下值：

和

分别计算 ${\mathrm{\σ}}_{\hat{A}}={\left({\mathrm{BB}}^e\right)}^{x+\mathrm{da}}$ 和 ${\mathrm{\σ}}_{\hat{B}}={\left({\mathrm{XA}}^d\right)}^{b+\mathrm{eb}},$ 并且设置密钥K至这些(相等的)值的散列。注意到在这种情况下，指数e并不向协议添加任何值，除了使其可与其它变体兼容之外。其实际稍微有损于协议效率。

然而，附加的差异保留在HMQV的单向版本中的值 $d=\stackrel{\‾}{H}(X,(\hat{A},\hat{B}))$ 与两消息版本中的 $d=\stackrel{\‾}{H}(X,\hat{B})$ 之间。在三种模式之间提供兼容性的方式将是使它们中都有 $d=\stackrel{\‾}{H}(X,\hat{B})$ 、 $e=\stackrel{\‾}{H}(Y,\hat{A}),$ 其中在单向的情况下Y＝B，并且向会话密钥导出函数添加身份

即， $K=H(\mathrm{\σ},\hat{A},\hat{B})$ (在使用某种固定的准则所定义的

和

的阶次的情况下)。这替代了对于在d的计算中添加

的需求。其还具有在泄漏预先计算的DH值的情况下加强HMQV并且避免可能的未知密钥共享攻击的优点。

HMQV的安全方面的总结：

相比于常规的MQV协议，HMQV协议提供了多个性能优点，包括以下内容。HMQV可证明省却了在协议中所传输的DH值上高代价的素数阶测试的需要。如在临时申请中所论证的，攻击者可以从选择欺诈DH值获益的唯一方式是通过将其选择零，并且因而，在HMQV中所要求的全在于简单的非零检查。因此，不需要素数阶测试或者在MQV协议中并发使用的辅助因子h。

下面是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)的这些优点使得认证机构(CA)免于对注册公钥进行这些专门检查的负担，从而提供更实际和实用的安全保证，特别是由于很多本地CA并不能够或未被配置进行这些检查。此外，值得注意的是，由CA特别执行的这样的测试(例如，证明拥有)使该协议公开了另外的安全弱点；

(9)两消息和三消息HMQV协议不需要测试短暂公钥的阶次(即，值X和Y)，从而避免在某些情况下可能高成本的测试。然而，如果该协议的安全性将要抵御可能获知各方的短暂保密密钥的攻击者，则需要这些测试。对于单向HMQV协议的安全性来说也需要该测试。如在MQV的情况下，可以用协议中σ值的“辅助因子求幂”来替换这些测试。可以根据基础代数群要求在群元素(例如预定群中的成员)上的附加测试。

本发明的HMQV协议的一个突出优点在于其是现有可论证的最高效的认证Diffie-Hellman密钥交换协议，具有可以以形式数学方式证明成立的广范围的安全特性。实际上，该形式上的可证明性是HMQV与其前身MQV之间的一个主要区别。

MQV不仅不具有安全性的证据，而且随时间出现明显的协议弱点(例如，Kaliski的工作以及Rogaway等人的报告)，包括在以上引用的临时申请中首次描述的一些弱点。这些弱点或攻击使得由其发明人作出的对MQV的一些安全主张无效，并且特别地，它们显示MQV不能够被证明是安全的。

XCR签名与MQV的“隐含签名(Implicit Signatures)”的比较：

作为一种比较方式，值得注意的是，如在专利中以及在学术论文中所描述的，MQV在协议的设计和描述中也使用签名的概念。这些在MQV的情况下被称为“隐含签名”，并且它们符合数字签名的更常规的概念，即其中签名值仅可以由秘密签名密钥的所有者来产生(具体地，MQV涉及由秘密签名密钥以及短暂保密密钥和公钥的线性组合所形成的类ElGamal签名)。然而，该协议不善于完全使用这些签名的特性。特别地，MQV协议并不将签名作为明确认证对协议的各方身份的方式来使用，这导致严重的认证失败，例如由Kaliski所发现的著名的“未知密钥共享(UKS)”攻击。

相比之下，HMQV在其设计中引入了两个重要元素。一个是使用XCR，其是EIGamal签名的指数版本。更具体而言，其是Schnorr的签名的指数版本，其又是EIGamal签名的特定例示。另一个是对等体的身份的显式签名，其确保会话密钥到会话的对等体的安全绑定，并且特别地，预防诸如UKS的认证失败。

XCR签名的关键新颖性在于这样的特性，即签名者和检验者(或询问者)均可以计算出相同的签名。该特性通常存在于基于共享密钥密码的认证机制中(即，在签名者和检验者均具有先验共享密钥的情况下)，但在基于公钥的签名中却是新的。XCR签名不仅非常适于导出共享密钥，如在HMQV中，而且其提供了作为认证工具的各种优点，其中一些优点在上面进行了描述。

本领域的普通技术人员应当清楚本发明涵盖各种实施例。

因而，在一个示例性实施例中，存在双方，检验者V和签名者S。签名者S具有私钥b和公钥B，并且假设检验者V拥有或获得了S的可信公钥B(例如，通过发送自S的数字证书)。对于给定消息m该认证协议包括：

(1)V选择秘密值x并且计算值X＝F₁(x)，其中F₁是给定函数，并且向S发送X。

(2)S选择秘密值y并且计算值Y＝F₂(y)，其中F₂是给定函数，并且向V传输Y。

(3)S计算值s＝F₃(y，b，X，m)，其中F₃是给定函数，并且向V传输S。

(4)V计算值s′＝F₄(x，Y，B，m)，并且基于值s′及其与所接收的值s的关系判定m的可信性。

该实施例的一些示例性变体包括：

(a)F₁、F₂是单向函数。在XCR中这些单向函数是X＝g^x和Y＝g^y。

(b)在XCR签名中，函数 $s=F_3(y,b,X,m)=X^{\{y+\stackrel{\‾}{H}(Y,m)b\}}$ 并且 $s^{\′}=F_4(x,Y,B,m)={\left({\mathrm{YB}}^{\left\{\stackrel{\‾}{H}(Y,m)\right\}}\right)}^x.$

(c)当且仅当s′＝s时，接受m为认证。这一最后的变体利用了典型的XCR签名的特性，由此，检验者可以根据知道在询问X之后的秘密来重新计算签名。

(d)计算 $s=F_3(y,b,X,m)=X^{\{y+\stackrel{\‾}{H}(Y,m)b\}}$ 并且测试H(s′)＝s，等等。

在将XCR应用于HMQV的至少一个实施例中，在步骤(3)中由S计算的值s从不被发送至V。相反，V计算值s′，其将等于s(除非S是冒名顶替者)，并且使用s(在HMQV中其是σ)来从中导出会话密钥。特别地，V从不实现显式检验。在该实施例中，不是用于检验消息m的可信性的方法，而会是这样一种方法，即通过该方法，双方计算公共“认证值”(即，有且只有双方可以计算的值)，并且通过该方法，将该值唯一地绑定到相应的身份(在HMQV中通过双重XCR签名，由各方身份的签名所获得的、在典型的密钥交换协议中的基本条件)。

在上文中及权利要求中描述了附加的变体。

示例性硬件实现：

图10说明了依照本发明的信息处理/计算机系统的典型硬件配置，并且其优选地具有至少一个处理器或中央处理器(CPU)1011。

CPU 1011通过系统总线1012互连于随机访问存储器(RAM)1014、只读存储器(ROM)1016、输入/输出(I/O)适配器1018(用于将诸如磁盘单元1021和磁带驱动器1040的外围设备连接至总线1012)、用户接口适配器1022(用于将键盘1024、鼠标1026、扬声器1028、扩音器1032和/或其它用户接口设备连接至总线1012)、用于将信息处理系统连接至数据处理网络、因特网、内联网、个人区域网(PAN)等的通信适配器1034，以及用于将总线1012连接至显示设备1038和/或打印机1039(例如，数字打印机等)的显示器适配器1036。

除了上述硬件/软件环境之外，本发明的不同方面包括用于实现以上方法的计算机实现的方法。举例来说，该方法可以在以上所讨论的特定环境中实现。

举例来说，这样的方法可以通过操作计算机(如由数字数据处理装置体现)来实现，以便执行机器可读指令序列。这些指令可以驻留于各种类型的信号承载介质中。

因而，本发明的这一方面针对的是一种编程产品，其包括信号承载介质，该信号承载介质有形地体现可由合并了CPU 1011和以上硬件的数字数据处理器执行的机器可读指令的程序，以便实现本发明的方法。

该信号承载介质可以包括，例如，含于CPU 1011内的RAM，如由例如快速访问存储器所表示的。可选地，指令可以含于CPU 1011可直接或间接访问的另一信号承载介质(例如磁数据存储磁盘1100(图11))中。

无论是否含于磁盘1100、计算机/CPU 1011或其它地方，指令均可以存储在各种机器可读数据存储介质中，诸如DASD存储器(例如，常规的“硬盘驱动器”或RAID阵列)、磁带、电子只读存储器(例如，ROM、EPROM或EEPROM)、光存储设备(例如，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.根据权利要求1的方法，其中F1和F2中的至少一个包括单向函数。

3.根据权利要求1的方法，其中如果s＝s′，则确定所述值s和s′是有效认证符。

4.根据权利要求1的方法，其中，由除了所述检验者和所述签名者之外的一方执行以下中的至少一个：计算s′以及确定是否将所述值s和s′确定为相关。

5.根据权利要求1的方法，其中所述值s和所述值s′用于导出双方之间共享的秘密。

6.根据权利要求1的方法，其进一步包括：

所述检验者获得所述值Y，并且使用相同的值来计算所述值s′用于确定s和s′是否以所述预定方式相关。

7.根据权利要求1的方法，其中消息m将要被认证并且包括F3的自变量以及F4的自变量，从而允许所述值s和所述值s′包括所述消息m中的信息；以及

如果确定所述值s和s′以所述预定方式相关，则认证所述消息。

8.根据权利要求7的方法，其中所述值s和所述值s′用于导出双方之间共享的秘密。

9.根据权利要求8的方法，其中所述消息m包括至少在所述交换中所述方之一的身份。

10.根据权利要求7的方法，其进一步包括：

所述签名者向所述检验者发送所述值s。

11.根据权利要求7的方法，其中如果所述s＝s′，则认证所述消息。

12.根据权利要求1的方法，其中：

所述公钥B＝g^b，g是q阶有限群的生成元，所述私钥b是使得0≤b≤q-1的整数；

所述值X＝g^x，x是使得0≤x≤q-1的整数，并且所述值Y＝g^y，y是使得0≤y≤q-1的整数；以及

所述签名者计算所述值 $s=f_1{\left(X\right)}^{f_2(m,Y,y,b)},$ f₁包括第一数学函数，以及f₂包括第二数学函数，并且自变量m包括消息。

13.根据权利要求12的方法，其中q是素数。

14.根据权利要求12的方法，其中如果确定所述值s与所述值s′以所述预定方式相关，则视为认证所述消息m。

15.根据权利要求14的方法，其中如果确定所述值s等于所述值s′，则视为认证所述消息m。

16.根据权利要求12的方法，其中f₁包括恒等函数。

17.根据权利要求12的方法，其中f₂包括散列函数，以便散列f₂的所述自变量中的至少一个。

18.根据权利要求17的方法，其中所述散列自变量之一是非空消息m。

19.根据权利要求12的方法，其中所述消息m包括在计算机或系统或网络中的一方的身份。

20.根据权利要求17的方法，其中f₂(m，Y，y，b)＝y+H(Y，m)bmod q，其中H包括是单向函数之一的密码函数、加密函数以及密码散列函数。

21.根据权利要求20的方法，其中所述值 $s^{\′}={\left({\mathrm{YB}}^{\left\{H(Y,m)\right\}}\right)}^{f_3\left(x\right)},$ 其中f₃(x)包括具有至少一个自变量的数学函数，所述值x是f₃(x)的所述至少一个自变量中的一个自变量。

22.根据权利要求21的方法，其中f₃(x)＝x。

23.根据权利要求21的方法，其进一步包括：

当且仅当s＝s时，认证所述消息m。

24.根据权利要求21的方法，其中所述检验者具有私钥a、公钥A＝g^a以及消息m′，所述值s包括所述检验者在m′上的签名，与此同时所述值s′包括所述签名者在m上的签名。

25.根据权利要求24的方法，其中所述函数f₃(x)＝x+H(X，m′)amodq。

26.根据权利要求1的方法，其中由所述检验者随机选择x，并且由所述签名者随机选择y。

27.根据权利要求1的方法，其中所述第一值X＝g^x包括由所述检验者公布以便可由所述签名者检索的值，从而准许所述认证的非交互式版本。

28.根据权利要求21的方法，其中进一步散列所述值s和s′。

29.一种信号承载介质，其有形地体现可由数字处理装置执行以便实现权利要求1中所述方法的步骤的机器可读指令的程序。

30.一种装置，其包括：

计算器，以便为所述签名者计算权利要求1中所述的函数F2和F3。

31.一种用于在通过设备或网络互连的双方之间建立认证密钥的方法，所述方法包括：

给定具有私钥a和公钥A的第一方，所述私钥a是使得0≤a≤q-1的整数，q是正整数，g是q阶有限群的生成元，并且A是由所述值g所生成的群中的元素且计算为A＝g^a，以及

给定具有私钥b和公钥B＝g^b的第二方，所述私钥b是使得0≤b≤q-1的整数，

所述第一方选择用于计算值X＝g^x的秘密值x，x是使得0≤x≤q-1的整数，并且所述值X被传达给所述第二方；

所述第二方选择用于计算值Y＝g^y的秘密值y，y是使得0≤y≤q-1的整数，并且所述值Y被传达给所述第一方；

所述第一方计算值 $s=f_1{(Y,B,m)}^{\left\{f_2(x,a,m^{\′})\right\}},$ 其中m、m′包括所述方之间已知或交换的消息，并且所述第二方计算值 $s^{\′}=f_3{(X,A,m^{\′})}^{\left\{f_4(y,b,m)\right\}};$

所述函数f₂和f₄中的至少一个包括具有至少一个自变量的函数H，一个这样的自变量是所述消息m和m′中的至少一个，其中H包括是单向函数之一的密码函数、加密函数以及密码散列函数；

所述第一和第二方分别从值s和s′导出共享密钥。

32.根据权利要求31的方法，其中以下中的至少一个：

(i)所述值x和X的计算包括所述第一方的私钥以及所述方中一个或多个的公钥；以及

(ii)所述值y和Y的计算包括所述第二方的私钥以及所述方中一个或多个的公钥。

33.根据权利要求31的方法，其中所述从s和s′导出共享密钥包括是单向函数之一的密码函数、加密函数以及密码散列函数。

34.根据权利要求31的方法，其中所述消息m和m′中的至少一个包括所述第一和第二方之一的身份。

35.根据权利要求31的方法，其中：

f₁(Y，B，m)＝YB^H(Y，m)，

f₂(x，a，m′)＝(x+H(X，m′)a)mod q，

f₃(X，A，m′)＝XA^H(X，m′)，

f₄(y，b，m)＝(y+H(Y，m)b)mod q，以及

H是具有至少两个自变量的函数，其包括是单向函数之一的密码函数、加密函数以及密码散列函数。

36.根据权利要求35的方法，其中所述消息m和m′中的至少一个包括所述第一和第二方中至少一个的身份。

37.根据权利要求36的方法，其中以下中的至少一个：

(i)所述值x和X的计算包括所述第一方的私钥以及所述方中一个或多个的公钥；以及

(ii)所述值y和Y的计算包括所述第二方的私钥以及所述方中一个或多个的公钥。

38.根据权利要求36的方法，其中所述从s和s′导出共享密钥包括是单向函数之一的密码函数、加密函数以及密码散列函数。

Claims (38)

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.根据权利要求1的方法，其中F1和F2中的至少一个包括单向函数。

3.根据权利要求1的方法，其中如果s＝s′，则确定所述值s和s′是有效认证符。

4.根据权利要求1的方法，其中，由除了所述检验者和所述签名者之外的一方执行以下中的至少一个：计算s′以及确定是否将所述值s和s′确定为相关。

5.根据权利要求1的方法，其中所述值s和所述值s′用于导出双方之间共享的秘密。

6.根据权利要求1的方法，其进一步包括：

所述检验者获得所述值Y，并且使用相同的值来计算所述值s′用于确定s和s′是否以所述预定方式相关。

7.根据权利要求1的方法，其中消息m将要被认证并且包括F3的自变量以及F4的自变量，从而允许所述值s和所述值s′包括所述消息m中的信息；以及

如果确定所述值s和s′以所述预定方式相关，则认证所述消息。

8.根据权利要求7的方法，其中所述值s和所述值s′用于导出双方之间共享的秘密。

9.根据权利要求8的方法，其中所述消息m包括至少在所述交换中所述方之一的身份。

10.根据权利要求7的方法，其进一步包括：

所述签名者向所述检验者发送所述值s。

11.根据权利要求7的方法，其中如果所述s＝s′，则认证所述消息。

12.根据权利要求1的方法，其中：

所述公钥B＝g^b，g是q阶有限群的生成元，所述私钥b是使得0≤b≤q-1的整数；

所述值X＝g^x，x是使得0≤x≤q-1的整数，并且所述值Y＝g^y，y是使得0≤y≤q-1的整数；以及

所述签名者计算所述值 $s=f_1{\left(X\right)}^{f_2(m,Y,y,b)},$ f₁包括第一数学函数，以及f₂包括第二数学函数，并且自变量m包括消息。

13.根据权利要求12的方法，其中q是素数。

14.根据权利要求12的方法，其中如果确定所述值s与所述值s′以所述预定方式相关，则视为认证所述消息m。

15.根据权利要求14的方法，其中如果确定所述值s等于所述值s′，则视为认证所述消息m。

16.根据权利要求12的方法，其中f₁包括恒等函数。

17.根据权利要求12的方法，其中f₂包括散列函数，以便散列f₂的所述自变量中的至少一个。

18.根据权利要求17的方法，其中所述散列自变量之一是非空消息m。

19.根据权利要求12的方法，其中所述消息m包括在计算机或系统或网络中的一方的身份。

20.根据权利要求17的方法，其中f₂(m，Y，y，b)＝y+H(Y，m)bmod q，其中H包括是单向函数之一的密码函数、加密函数以及密码散列函数。

21.根据权利要求20的方法，其中所述值 $s^{\′}={\left({\mathrm{YB}}^{\left\{H(Y,m)\right\}}\right)}^{f_3\left(x\right)},$ 其中f₃(x)包括具有至少一个自变量的数学函数，所述值x是f₃(x)的所述至少一个自变量中的一个自变量。

22.根据权利要求21的方法，其中f₃(x)＝x。

23.根据权利要求21的方法，其进一步包括：

当且仅当s＝s′时，认证所述消息m。

24.根据权利要求21的方法，其中所述检验者具有私钥a、公钥A＝g^a以及消息m′，所述值s包括所述检验者在m′上的签名，与此同时所述值s′包括所述签名者在m上的签名。

25.根据权利要求24的方法，其中所述函数f₃(x)＝x+H(X，m′)amodq。

26.根据权利要求1的方法，其中由所述检验者随机选择x，并且由所述签名者随机选择y。

27.根据权利要求1的方法，其中所述第一值X＝g^x包括由所述检验者公布以便可由所述签名者检索的值，从而准许所述认证的非交互式版本。

28.根据权利要求21的方法，其中进一步散列所述值s和s′。

29.一种信号承载介质，其有形地体现可由数字处理装置执行以便实现权利要求1中所述方法的步骤中的至少一个的机器可读指令的程序。

30.一种装置，其包括：

计算器，以便为所述签名者计算权利要求1中所述的函数F2和F3。

31.一种用于在通过设备或网络互连的双方之间建立认证密钥的方法，所述方法包括：

给定具有私钥a和公钥A的第一方，所述私钥a是使得0≤a≤q-1的整数，q是正整数，g是q阶有限群的生成元，并且A是由所述值g所生成的群中的元素且计算为A＝g^a，以及

给定具有私钥b和公钥B＝g^b的第二方，所述私钥b是使得0≤b≤q-1的整数，

所述第一方选择用于计算值X＝g^x的秘密值x，x是使得0≤x≤q-1的整数，并且所述值x被传达给所述第二方；

所述第二方选择用于计算值Y＝g^y的秘密值y，y是使得0≤y≤q-1的整数，并且所述值Y被传达给所述第一方；

所述第一方计算值 $s=f_1{(Y,B,m)}^{\left\{f_2(x,a,m^{\′})\right\}},$ 其中m、m′包括所述方之间已知或交换的消息，并且所述第二方计算值 $s^{\′}=f_3{(X,A,m^{\′})}^{\left\{f_4(y,b,m)\right\}};$

所述函数f₂和f₄中的至少一个包括具有至少一个自变量的函数H，一个这样的自变量是所述消息m和m′中的至少一个，其中H包括是单向函数之一的密码函数、加密函数以及密码散列函数；

所述第一和第二方分别从值s和s′导出共享密钥。

32.根据权利要求31的方法，其中以下中的至少一个：

(i)所述值x和X的计算包括所述第一方的私钥以及所述方中一个或多个的公钥；以及

(ii)所述值y和Y的计算包括所述第二方的私钥以及所述方中一个或多个的公钥。

33.根据权利要求31的方法，其中所述从s和s′导出共享密钥包括是单向函数之一的密码函数、加密函数以及密码散列函数。

34.根据权利要求31的方法，其中所述消息m和m′中的至少一个包括所述第一和第二方之一的身份。

35.根据权利要求31的方法，其中：

f₁(Y，B，m)＝YB^H(Y，m)，

f₂(x，a，m′)＝(x+H(X，m′)a)modq，

f₃(X，A，m′)＝XAH^(X，m′)，

f₄(y，b，m)＝(y+H(Y，m)b)modq，以及

H是具有至少两个自变量的函数，其包括是单向函数之一的密码函数、加密函数以及密码散列函数。

36.根据权利要求35的方法，其中所述消息m和m′中的至少一个包括所述第一和第二方中至少一个的身份。

37.根据权利要求36的方法，其中以下中的至少一个：

(i)所述值x和X的计算包括所述第一方的私钥以及所述方中一个或多个的公钥；以及

(ii)所述值y和Y的计算包括所述第二方的私钥以及所述方中一个或多个的公钥。

38.根据权利要求36的方法，其中所述从s和s′导出共享密钥包括是单向函数之一的密码函数、加密函数以及密码散列函数。

Images