基于椭圆曲线的加密密钥交换协议

张晓敏

陕西省行政学院 陕西 710068

0 前言

为了实现网络安全，网络用户传送加密和可鉴定的消息。此时，用来加密和鉴定的密钥就是由网络中的用户通过密钥交换协议得到的。此外，网络用户在进行会话时，验证其它参与方的身份是非常有必要的，这种认证通常是和密钥交换协议结合在一起的。口令因其容易记忆，易于选取，节省存储空间，适合实际应用等特点成为最简单的认证方法。当然，由于口令是从一个相对较小的字典中均匀选取的，攻击者可能发起穷举字典攻击，进而发动会话进行冒充。为了研究如何安全地利用口令进行密钥协商，并避免穷举字典攻击，研究者们提出了加密密钥交换协议(encrypted key exchange，EKE)的概念，又称为基于口令的密钥交换协议。1992年，Bellovin 和Merritt首次提出了一个两方的EKE协议，通信双方通过预先共享的低熵的口令构造出高熵的会话密钥，并且能够抵抗字典攻击。在三方的EKE中，通信双方分别和可信服务器共享一个容易记忆的口令，并通过服务器进行安全密钥交换，服务器用口令加密信息以实现对用户的认证，只有合法用户能够解密信息从而能够生成正确的会话密钥。

加密密钥交换协议主要分为两类：对称模型和非对称(基于验证元)模型。对称模型中，用户和服务器持有相同的口令。因此，当服务器泄露时，敌手能够直接获得全部用户的真实口令，并且使用口令模仿任何合法用户。基于验证元模型中，用户持有口令，服务器持有的是利用单向函数生成的口令的映像(即验证元)，而非口令本身。基于验证元模型降低了服务器泄露攻击对协议的破坏程度：服务器泄露时，敌手不能直接获得用户的口令，但仍允许敌手在服务器泄露攻击后对获得的口令文件进行离线字典攻击。敌手必须进行一些额外计算才有可能发现用户真正的口令，而进行这些计算给了服务器通知用户受攻击的时间。

1994年，Bellovin 和 Merritt提出了首个基于验证元的加密密钥交换协议，它采用特殊函数来存储用户的口令。自此以后，一些相关研究出现，协议的安全性和效率也得到了提高。基于椭圆曲线上离散对数问题的密码系统近年来广泛应用于实际中，与其他密码系统相比，达到相同的安全性，椭圆曲线密码系统的密钥更短。此外，在椭圆曲线上实现数字签名具有速度快、密钥和签名短等优点。因此，本文利用椭圆曲线密码学的特点，给出了一个基于验证元的三方加密密钥交换协议，服务器通过口令实现对用户的认证，协议能够抵抗字典攻击、服务器泄露攻击和中间人攻击，提供前向安全性，能够保证无密钥控制和已知密钥安全。此外，协议每运行一次各用户可以获得四个安全的会话密钥，而服务器得不到这些密钥的准确信息。

1 预备知识

p是有限域Fp的元素个数，其中p是大素数(长度大于160，或p=2m，m为正整数) 。定义Fp上的椭圆曲线E： y2= x3+ ax+b ，当p＞3；或y2+ xy = x3+ ax2+ b，当p=2。P是 E( Fp)中阶为q的一个基点，q为大素数。

1.1 椭圆曲线上离散对数问题(DLP)

G是由点P生成的循环加群，给定Q，找到正整数n，使得Q=nP。

1.2 椭圆曲线 Diffie-Hellman 密钥交换协议(ECDH)

A选择随机数 a∈Fq并计算PA=aP发送给B；B选择随机数 b∈Fq并计算PB=bP发送给A。A和B分别计算aPB，bPA从而得到共同的会话密钥 K=(a b) P。

1.3 椭圆曲线数字签名算法(ECDSA)

密钥生成：私钥： da∈ [2 ,n - 2]，公钥： Qa=daP。

签名： k∈ [2 ,n - 2]，计算kP和 r =(k P). x mod n ，计算得到签名(r , s)。

如果v=r，则验证者接受签名。

2 协议描述

2.1 公开参数

P是q阶循环加群G的生成元， H:{0 ,1}∗→ {0 ,1}l是杂凑函数；A,B是用户，pwA，pwB是用户相应的口令；S是服务器。

2.2 初始化过程

2.3 协议过程

假设是A需要和B建立会话密钥。

Round 1发起者A广播(A ,B,S)。

Round 3：

（3）A对eA签名：随机选取kA计算最后将发送给S。

（4）B对eB签名：随机选取kB计算最后将发送给S。

密钥计算：

完成。诚实执行协议后，各用户能够计算获得相同的会话密钥。

3 效率和安全性分析

3.1 效率分析

我们分析协议的通信、计算和轮复杂度以及存储开销和实现成本。协议每执行一次，用户和服务器之间需要四轮交互。整个协议过程中，用户要进行2次杂凑函数运算，一次签名运算；服务器需要进行4次杂凑函数运算，2次签名验证。每生成一个会话密钥，每个用户平均需要进行2次点乘运算；服务器平均需要进行2.5次点乘运算。对于每个用户，服务器只需要存储一个与之相应的校验元，与其它同性质的协议比较(见表1)，降低了存储开销和通信开销，更适宜于实际应用。

表1 效率比较

3.2 安全性分析

（1）字典攻击。首先，在离线字典攻击中，攻击者利用其截获的信息验证猜测的口令是否正确。该协议中，以用户A为例，攻击者在各轮中可截获等信息，由于在通信过程中没有传递eA，敌手没有办法验证猜测的口令是否正确。因此，无法进行离线字典攻击。其次，本协议可以抵抗可测在线字典攻击，因为服务器在第四轮里通过验证用户对eA的签名来验证用户是否真正知道口令。一旦验证失败，服务器就会意识到是谁的口令已经作为在线字典攻击的目标了。如果失败的次数超过预定的门限值，服务器就会通知该用户停止使用该口令并启用新的口令。最后，如前所述，敌手不能将S作为口令试验预言机，因此不能进行不可测在线字典攻击。

（2）服务器泄露。如果攻击者获得服务器中存储的口令文件，即可获得用户的验证信息 VA, VB，由于椭圆曲线上离散对数问题的困难性，攻击者仍然得不到 vA, vB，因此在第三轮中不能伪造用户A、B对eA，eB的签名，则在第四轮中无法通过服务器的验证，故而不能冒充合法用户。所以协议抵抗服务器泄露攻击。

（3）前向安全性。由于最终的会话密钥是由随机数构成的，而随机数是由各参与方随机选取的，在协议交互过程中，传递的信息是随机数所对应的离散对数形式。由于离散对数问题的困难性，攻击者即使获得用户与服务器的长期密钥，仍然无法获得随机数，因此不能计算出会话密钥。所以协议提供前向安全性。

（4）无密钥控制。协议使用Diffie-Hellman密钥交换协议协商会话密钥，此外，xAi是由A选取的，xBi是由B选取的，xS是由S选取的。因此，任何一方不能单独控制会话密钥的选择，达到了协议无密钥控制的目的。

（5）已知密钥安全。攻击者攻破一次通信的会话密钥，无助于攻破另一次通信的会话密钥。这是因为通信双方最终得到的会话密钥是由随机数构成，由于两次通信使用的是不同的随机数，这种随机数的不相关性使得攻击者即使攻破了一个会话密钥也无法利用该信息攻破另一次通信的会话密钥，以此实现已知密钥安全。

（6）抗中间人攻击。服务器和用户之间通过验证元 VA, VB实现相互认证来抵抗中间人攻击。攻击者无法获得验证元信息，因此不能伪装为合法用户。此外，由于协议第三轮中的 eA, eB是由用户和服务器各自利用交互信息生成的，而没有进行直接传输，并且用户分别利用 vA,vB对 eA, eB分别进行了签名。因此，协议还能抵抗在线字典攻击和中间人攻击的联合攻击。

[1]S.M. Bellovin, M. Merrit. Encrypted key exchanged: password-based protocols secure against dictionary attacks, Proceeding of IEEE Computer Society Symposium on Research in Security and Privacy.Oakland.California.1992.

[2]IEEE P1363.2/D15, Standard Specifications for Password-Based Public Key Cryptographic Techniques.2004.

[3]Bellovin, S.M.,Merritt,M.,1994.Augmented encrypted key exchange:a password-based protocol secure against dictionary attacks and password file compromise.Technical report, AT&T Bell Laboratories.