无证书的普适环境匿名认证方案

Certificate-Less Based Anonymous Authentication Scheme in Pervasive Computing Environments

摘要: 针对普适环境下的匿名认证问题，利用双线性对的相关特性，提出了一种无证书签名算法，算法中的签名矢量相对于签名者身份是一常量。基于该算法设计了一种匿名认证方案，方案中用户利用该算法对时戳签名作为认证信息，在安全认证的同时实现了用户匿名性。分析表明，用户端认证需要116.1 ms，计算量较小，方案在满足双向认证、用户匿名性和无关联性安全要求的同时，解决了现有方案存在的密钥托管问题。

Abstract: Considered the anonymous authentication in pervasive computing environments, a certificateless signature scheme was proposed based on bilinear parings. The verification result of the signature was a constant with respect to the signer’s identifier. Then an anonymous authentication scheme was constructed by combining the proposed signature scheme. During the authentication, a user constructed the signature of timestamp as authentication proof, which realized secure authentication and user anonymity. It is showed that it takes the client 116.1ms to realize authentication and the proposed scheme has less computation on the client side. It can achieve such security requirements as mutual authentication, user anonymity and non-linkability. Moreover, it resolves the problem of key escrow.

1. 引言

普适环境计算是继主机和桌面计算后出现的新计算模式，其目的是使计算机服务融入日常生活空间，形成一个“时时存在、处处存在而又不可见”的计算服务环境 [1] 。在普适环境中当向服务提供方申请服务时，它需要对申请者进行认证，以防止非法用户获取服务。同时申请者也需要对服务提供方进行认证，以防止假冒实体的攻击。为了更好的保护用户隐私，在普适环境下的认证除了提供安全认证和密钥建立服务之外，还要求 [2] [3] [4] ：1) 满足用户匿名，即认证时，不能获得用户的真实身份；2) 满足无关联特性，即不能确定不同的会话来自同一用户。

文献 [5] 采用传统的公钥体制实现匿名认证，用户基于服务器的公钥加密身份实现匿名，用自己的私钥签名作为认证凭证。该方案涉及到较多的公钥操作，公钥证书管理复杂，不适合普适计算中的资源受限的设备。文献 [6] 应用基于身份的密码体制设计匿名认证方案，来避免公钥体制中管理证书问题，但方案中用户和服务器都需要多次的双线性对的运算，带来较大的计算量。文献 [7] 采用基于身份的签名算法对时间戳签名产生认证请求，该签名只有服务器方能够验证，所以对外部用户是匿名的，而且用户端不需要计算双线性对，比较适合普适计算环境。

以上匿名认证方案都有密钥托管方面的问题，密钥生成中心的主密钥如果泄露，攻击者通过计算合法用户的签名私钥，来假冒合法用户。针对该问题，本文基于无证书签名算法来设计匿名认证方案，该方案可满足用户匿名性和用户端计算量小的要求，同时不存在密钥托管问题。

2. 无证书签名算法

2.1. 算法设计

2003年Al-Ryami和K.G. Paterson提出了无证书公钥密码系统 [8] (certificateless public key cryptography, CL-PKC)的概念，通过密钥生成中心(Key Generation Center, KGC)为系统用户生成部分私钥。

(1) 系统建立

KGC输入系统安全参数k；获得满足双线性对要求的、 $G_1$ 、 $G_2$ 、 $q$ ， $G_1$ 的生成元为 $P$ ；随机选取 $s\in Z_q^{*}$ 作为系统私钥；计算系统公钥 $P_0=sP$ ；选取安全哈希函数 $H_1:{\left\{0,1\right\}}_{}^{*}\to G_1$ 和 $H_2:{\left\{0,1\right\}}_{}^{*}\times G_1\to Z_q^{*}$ ；最后KGC公布系统参数 $\left\{G_1,G_2,e,q,P,P_0,H_1,H_2\right\}$ 。

(2) 用户部分私钥产生

$I{D}_A$ 为用户 $A$ 的惟一身份标识，用户 $A$ 向KGC提交 $I{D}_A$ ，KGC验证 $I{D}_A$ 是否合法，若 $I{D}_A$ 合法，KGC为生成 $A$ 的部分私钥 $D_A=s{Q}_A$ ，其中 $Q_A=H_1\left(I{D}_A\right)$ ，并安全地将 $D_A$ 传送给 $A$ 。

(3) 秘密数产生

用户 $A$ 随机选取 $x_A\in Z_q^{*}$ 作为用户秘密数，并安全保存。

(4) 用户私钥产生

用户 $A$ 计算 $S_A=x_A{D}_A$ 作为自己的私钥。

(5) 用户公钥产生

用户 $A$ 计算 $X_A=x_{A}P$ 和 $Y_A=x_A{P}_0$ ，将 $P_A=\langle X_A,Y_A\rangle$ 作为自己的公钥。

(6) 签名

为了对 $m$ 消息进行签名， $A$ 选择随机数 $r\in Z_q^{*}$ ，计算 $R=rP$ 、 $h=H_2\left(m\Vert R\right)$ ， $V=S_A/\left(h+r\right)$ ， $A$ 对 $m$ 的签名为 $\delta =\langle R,V\rangle$ ， $A$ 向验证者发送 $I{D}_A$ 、 $m$ 、 $\delta$ 和 $P_A$ 。

(7) 验证

验证者首先验证 $e\left(X_A,P_0\right)=e\left(Y_A,P\right)$ 是否成立；然后计算 $h=H_2\left(m\Vert R\right)$ ，验证 $e\left(V,hP+R\right)=e\left(Q_A,Y_A\right)$ 是否成立。只有两者验证都通过时才接受签名。

由上述过程可知，对用户 $A$ ， $e\left(Q_A,Y_A\right)$ 是一个确定的常量。对于不同的 ${\delta }_1$ 和 ${\delta }_2$ ，只要是同一个签名人，验证结果必定相同，从而可以确定签名者的身份。即通过预计算 $e\left(Q_A,Y_A\right)$ ，收到 $\delta$ 后计算 $e\left(V,hP+R\right)$ 是否等于 $e\left(Q_A,Y_A\right)$ ，来确认 $\delta$ 是否来自 $A$ 。

2.2. 算法安全性分析

采用文献 [7] 中的方法来分析上述签名算法的安全性。

(1)若 $A$ 对消息 $m$ 的合法签名 $\delta =\langle R,V\rangle$ ，则Adv无法计算出 $A$ 的私钥 $S_A$ 。因为要从 $V$ 中解得 $S_A$ 就需要Adv从 $R=rP$ 求得 $r$ ，这是ECDL问题。

(2)假设Adv可以伪造签名 ${\delta }_{}^{\text{'}}=\langle R_{}^{\text{'}},V_{}^{\text{'}}\rangle$ ，满足 $e\left(V_{}^{\text{'}},H_2\left(m\Vert R_{}^{\text{'}}\right)P+R_{}^{\text{'}}\right)=e\left(Q_A,Y_A\right)$ 。对于循环群 $G_1$ ， $\forall Q\in G_1$ ， $\exists y\in Z_q^{*}$ ，则有 $Q=y{Q}_A$ 。因此任意 ${\delta }_{}^{\text{'}}$ 总有 $y\in Z_q^{*}$ 满足：(a) $V_{}^{\text{'}}=y{Q}_A\wedge H_2\left(m\Vert R_{}^{\text{'}}\right)()P+R_{}^{\text{'}}=y_{}^{-1}{Y}_A$ ；(b) $V_{}^{\text{'}}=y{Y}_A\wedge H_2\left(m\Vert R_{}^{\text{'}}\right)P+R_{}^{\text{'}}=y_{}^{-1}{Q}_A$ 。若(a)成立，Adv需要计算 $R_{}^{\text{'}}$ 使其满足等式： $R_{}^{\text{'}}=y_{}^{-1}{Y}_A-H_2\left(m\Vert R_{}^{\text{'}}\right)P$ ，但是对于单向函数 $H_2$ ，Adv无法获取符合条件的 $R_{}^{\text{'}}$ ，故(a)条件不成立；同理可证(b)条件不成立。

3. 匿名认证方案设计

3.1. 方案描述

KGC负责为合法用户生成部分私钥，服务器是普适环境中可以向用户提供某种服务的实体，合法用户在获得服务时必须首先通过服务器的认证。

(1) 系统建立

KGC依照2.1节中描述过程生成系统参数，选定公私钥对 $\left(s,P_0\right)$ ，并对外发布系统参数 $\left\{G_1,G_2,e,q,P,P_0,H_1,H_2\right\}$ 。

(2) 用户公私钥生成

用户公私钥的生成方法同2.1节中描述方法相同。 $I{D}_U$ 为用户U的身份标识，KGC生成用户部分私钥 $D_U=s{Q}_U$ ， $Q_U=H_1\left(I{D}_U\right)$ ，用户选取随机数 $x_U\in Z_q^{*}$ ，计算出完整私钥 $S_U=x_U{D}_U$ ，用户公钥为 $P_U=\langle X_U,Y_U\rangle$ ，其中 $X_U=x_U{P}_{}$ ， $Y_U=x_U{P}_0$ 。

(3) 用户注册

在使用服务器的服务之前，用户U须先向服务器注册并成为服务器的合法用户。服务器S具有长期私钥 $S{K}_S\in Z_q^{*}$ ，相对应的公钥为 $P{K}_S=S{K}_{S}P$ 。在注册时，用户向服务器提供 $I{D}_U$ 和公钥 $P_U=\langle X_U,Y_U\rangle$ 。服务器首先审核用户身份，审核通过后，通过验证 $e\left(X_U,P_0\right)=e\left(Y_U,P\right)$ 来确定用户的公钥是否合法。验证通过后，服务器为用户建立帐户 $\langle in{d}_U,I{D}_U\rangle$ ，其中 $in{d}_U=e\left(Q_U,Y_U\right)$ 是用户帐户索引。注册过程中，用户会获得服务器公钥 $P{K}_S$ 、一个哈希函数 $H_3:G_1\times G_1\to {\left\{0,1\right\}}_{}^{*}$ 和消息认证算法 $MAC$ 。

(4) 认证

当用户需要使用服务器提供的服务时，通过以下步骤进行双方向认证。

用户选择随机数 $r\in Z_q^{*}$ ，获得当前时间戳 $T$ ，计算 $R=rP$ ， $R_{}^{\text{'}}=rP{K}_S$ ， $h=H_2\left(T\Vert R\right)$ ，计算临时身份 $Ti{d}_U=S_U/\left(h+r\right)$ ，用户将 $\langle T,R_{}^{\text{'}},Ti{d}_U\rangle$ 发送给 $S$ ，然后计算会话密钥 $K=H_3\left(R\Vert R_{}^{\text{'}}\right)$ 并保存 $K$ 。

服务器收到消息后，需验证时戳 $T$ 的新鲜性。若 $T$ 是新鲜的，Ｓ计算 $R=S{K}_S^{-1}{R}_{}^{\text{'}}$ ， $h=H_2\left(T\Vert R\right)$ ， $in{d}_U=e\left(Ti{d}_U,hP+R\right)$ 。S以 $in{d}_U$ 来索引用户列表，若用户存在，则认证通过。计算 $K=H_3\left(R\Vert R_{}^{\text{'}}\right)$ 、 $MA{C}_K\left(I{D}_U,S\right)$ ，并向用户发送认证应答 $MA{C}_K\left(I{D}_U,S\right)$ 。用户U收到 $MA{C}_K\left(I{D}_U,S\right)$ 后，利用 $K$ 验证认证应答的完整性。若验证通过，则通对服务器的认证，并在以后的通信中使用 $K$ 作为会话密钥。

3.2. 方案安全性分析

(1) 双向认证

本方案可以实现用户和服务器之间的双向认证以及相互之间会话密钥协商。下面利用采用BAN逻辑对方案的认证安全性进行分析证明，由于双向认证在认证阶段实现，所以只需分析认证阶段协议。

为了便于BAN逻辑证明，需对原协议进行转化。按照BAN逻辑的描述规则，U和S之间的共享密钥 $K$ 用 $K_{US}$ 表示，U和S的公私钥分别为 $K_U^{}$ 、 $K_U^{-1}$ 、 $K_S^{}$ 和 $K_S^{-1}$ 。

消息转化：

消息1 $U\to S$ ： $T,R_{}^{\text{'}},Ti{d}_U$ 可转化为 $U\to S$ ： $T,{\left\{K_{US},{\left\{K_{US},T\right\}}_{K_U^{-1}}\right\}}_{K_S^{}}$

消息1中虽然没有密钥 $K_{US}$ ，由于S可以利用私钥由 $R_{}^{\text{'}}$ 计算出 $R$ 进而计算出 $K_{US}$ ，并且 $K_{US}$ 只能由S计算得到，所以 $K_{US}$ 可以看作由S的公钥加密传送。由于 $Ti{d}_U$ 是U对 $R$ 和 $T$ 的签名，而 $K_{US}$ 由 $R$ 计算得到，所以 $Ti{d}_U$ 可以看作是对 $K_{US}$ 和 $T$ 的签名 ${\left\{K_{US},T\right\}}_{K_U^{-1}}$ 。由于签名 $Ti{d}_U$ 只有S可以验证，所以 ${\left\{K_{US},T\right\}}_{K_U^{-1}}$ 可以看作由S的公钥加密。因此，上述转化是合理的。

消息2 $S\to U$ ： $MA{C}_K\left(I{D}_U,S\right)$ 可转化为 $S\to U$ ： ${\left\{U,S\right\}}_{K_{US}}$

消息2的转化中，将消息码认证算法 $MAC$ 用对称加密算法代替，因为两者都由对称密钥控制，所以转化是合理的。

协议理想化：

消息1 $U\to S$ ： ${\left\{U\stackrel{K_{US}}{\leftrightarrow }S,{\left\{U\stackrel{K_{US}}{\leftrightarrow }S,T\right\}}_{K_U^{-1}}\right\}}_{K_S^{}}$

消息2 $S\to U$ ： ${\left\{U\stackrel{K_{US}}{\leftrightarrow }S\right\}}_{K_{US}}$

初始化假设：

(1) $U|\equiv U\stackrel{K_{US}}{\leftrightarrow }S$ ；(2) $U|\equiv \#\left(U\stackrel{K_{US}}{\leftrightarrow }S\right)$ (3) $S|\equiv \stackrel{K_S}{\to }S$ ；

(4) $S|\equiv \stackrel{K_U}{\to }U$ ；(5) $S|\equiv \#\left(T\right)$ ；(6) $S|\equiv U\Rightarrow U\stackrel{K_{US}}{\leftrightarrow }S$

由于 $K_{US}$ 由 $R$ 和 $R_{}^{\text{'}}$ 计算得出， $R$ 和 $R_{}^{\text{'}}$ 都是由U产生的参数，所以 $K_{US}$ 是由U产生的，进而可得出假设(1)、(2)、(6)。由于S可以对U的签名 $Ti{d}_U$ (临时身份)进行验证，可得假设(4)。由于S可以判断时戳 $T$ 的新鲜性，可得假设(5)。假设(3)显然成立。

证明过程为：

由消息1得

$S⊲{\left\{U\stackrel{K_{US}}{\leftrightarrow }S,{\left\{U\stackrel{K_{US}}{\leftrightarrow }S,T\right\}}_{K_U^{-1}}\right\}}_{K_S^{}}$ (7)

由公式(7)、假设(3)和接收规则得

$S⊲\left\{U\stackrel{K_{US}}{\leftrightarrow }S,{\left\{U\stackrel{K_{US}}{\leftrightarrow }S,T\right\}}_{K_U^{-1}}\right\}$ (8)

由公式(8)和接收规则可得

$S⊲{\left\{U\stackrel{K_{US}}{\leftrightarrow }S,T\right\}}_{K_U^{-1}}$ (9)

由公式(9)、假设(4)和消息含义规则得

$S|\equiv U~\left\{U\stackrel{K_{US}}{\leftrightarrow }S,T\right\}$ (10)

由假设(5)和新鲜性规则得

$S|\equiv \#\left(U\stackrel{K_{US}}{\leftrightarrow }S,T\right)$ (11)

由公式(10)、(11)和临时值验证规则得

$S|\equiv U|\equiv \left\{U\stackrel{K_{US}}{\leftrightarrow }S,T\right\}$ (12)

由公式(12)和信仰规则得

$S|\equiv U|\equiv U\stackrel{K_{US}}{\leftrightarrow }S$ (13)

由假设(6)、公式(13)和仲裁规则得

$S|\equiv U\stackrel{K_{US}}{\leftrightarrow }S$ (14)

由消息2得

$U⊲{\left\{U\stackrel{K_{US}}{\leftrightarrow }S\right\}}_{K_{US}}$ (15)

由公式(15)、假设(1)和消息含义规则得

$U|\equiv S~\left\{U\stackrel{K_{US}}{\leftrightarrow }S\right\}$ (16)

由公式(16)、假设(2)和临值验证规则得

$U|\equiv S|\equiv U\stackrel{K_{US}}{\leftrightarrow }S$ (17)

结论：由上述证明过程可知，认证阶段协议满足一级信仰：假设(1)和公式(14)，二级信仰：公式(13)和公式(17)，所以该方案可以实现安全的双向认证和密钥协商。

(2) 用户匿名性

在认证的过程中，除了服务器外其它用户均不能获取用户的真识身份。这是因为在整个认证过程中用户只是提供了签名矢量£ = $\langle T,R_{}^{\text{'}},Ti{d}_U\rangle$ ，而£中不含有用户的身份信息，并且£只能由服务器才能计算出用户帐户的索引，其它用户无法由签名矢量获取该用户身份。

(3) 非关联性

在认证过程中，用户每次对不同的时间戳签名作为认证信息，认证信息具有随机性，其它用户无法将不同的认证信息联系起来。

(4) 无密钥托管

在本方案中KGC只是为用户生成了部分私钥，要生成签名私钥还需获取用户选择的秘密参数。因此，当KGC被攻破导致主密钥泄露后，因没有用户秘密参数而无法生成用户的签名私钥，从而无法假冒合法用户获得服务。

同文献 [6] 和文献 [7] 中方案相比，本方案不存在密钥托管问题，具有更强的安全特性。

3.3. 方案效率分析

分析方案的计算开销，并同双线性对基础上实现方案的文献 [6] 和文献 [7] 中进行分析比较。由于注册协议只在新用户加入系统时运行，并且可以离线进行，所以在分析方案计算开销时只考虑认证阶段。在分析比较方案的计算开销时，忽略对称密钥操作和普通哈希操作，仅考虑双线性对运算(P)、映射到 $G_1$ 上点的Map-to-Point杂凑函数运算(MtP)、 $G_1$ 上点的数乘运算(gM)。方案的计算开销如表1所示。

Table 1. Comparison of computational overhead

表1. 计算开销比较

采用文献 [9] [10] [11] [12] 中方法可分别计算出用户端密码操作运行时间，若给定密码操作在服务器端运行时间为 $t_S$ ，则用户端的运行时间为 $t_U=t_S\times 2100/206$ ，密码操作的运行时间如表2所示。

Table 2. Cipher operation runtime

表2. 密码操作运行时间

表3为根据上述假设来计算出的各方案运行时间。

Table 3. Performance comparisons

表3. 性能比较

由表3可以得出，本文所设计方案中用户端的计算开销较小，能够满足普适环境下用户计算量要求较小的需求。与文献 [6] 方案相比，本文所设计的方案中用户和服务器的计算开销大大减小。这是由于本文方案中用户不需要进行双线性对运算，并减少了服务器方双线性对的运算次数。本文方案同文献 [7] 方案具有相同的计算开销，但是本方案不存在密钥托管问题，具有更好的安全特性，因此本方案优于文献 [7] 方案。

4. 总结

利用无证书公钥设计了一种匿名认证方案，方案既能很好地满足了双向认证，又能实现用户匿名性，而且用户端计算量小，并且解决了现有方案中的密钥托管问题。通过分析，方案能够满足普适计算环境的高安全性要求。

基金项目

河南省科技攻关课题(No.222102210223)，河南省科技研发计划联合基金项目(No.222103810044)。