224 刘佳, 等. 基于消息恢复型 Rabin PSS 的无线局域网认证方案. LIUJia,etal.WLANauthenticationschemebasedonmesage recoveryrabin PSS. 图 1 无线局域网系统网络模型 Fig.1 NetworkmodelofWLAN

Size: px

Start display at page:

Download "224 刘佳, 等. 基于消息恢复型 Rabin PSS 的无线局域网认证方案. LIUJia,etal.WLANauthenticationschemebasedonmesage recoveryrabin PSS. 图 1 无线局域网系统网络模型 Fig.1 NetworkmodelofWLAN"

恒材绢方
5 years ago
Views:

1 文章编号 : (2009) 基于消息恢复型 Rabin PSS 的无线局域网认证方案 1,2 刘佳 1,3 韦宝典 1 戴宪华摘要基于无线局域网非对称的结构特点, 设计了一个基于公钥密码技术的身份认证方案, 并在成功认证的同时实现会话密钥的分配. 该方案充分利用 Rabin PSS MR 签名方案和 ElGamal 改进型签名方案中签名与验证计算量的非对称性, 合理地配置认证服务器 AS 与移动终端 STA 的操作, 使网络的整体响应效率得以极大的提高 ; 同时,Rabin PSS MR 签名方案的消息恢复功能减少了公钥证书认证过程的传输量 ( 仅传输公钥证书而不传输公钥 ), 大大节省了通信带宽. 关键词无线局域网 ; 认证 ;Rabin PSS MR; ElGamal 中图分类号 TP 文献标志码 A 收稿日期资助项目国家自然科学基金 ( , ); 综合业务网理论及关键技术国家重点实验室开放基金 (ISN10 11); 重庆市 / 信息产业部计算机网络与通信技术重点实验室开放基金 (CY CNCL ) 作者简介刘佳, 女, 博士生, 主要研究信息安全与密码学.liujia_1116@163.com 1 中山大学信息科学与技术学院, 广州, 仲恺农业工程学院, 广州, 西安电子科技大学综合业务网理论及关键技术国家重点实验室, 西安, 引言 Introduction 无线局域网使用户能够真正实现随时随地随意地接入网络, 然而, 无线局域网的传输介质是开放的无线电波, 这种开放性导致了无线局域网络面临窃听欺骗网络接管和篡改等多种安全威胁. 为此,IEEE 于 1997 年为 WLAN 制定了标准, 采用基于 RC4 算法的有线等效保密机制 WEP(WiredEquivalentPrivacy) [1] 来增强其安全性. 但是, 研究分析发现 WEP 无法有效地保证数据的机密性完整性和对接入用户的身份认证. 要解决无线局域网的安全问题, 需要在网络接入时实施严格的认证, 并在通信过程中实现保密通信. 目前已出现了多种认证方式 [2 3]. 本文针对无线局域网计算资源方面非对称的结构特点, 设计了一个安全的认证方案, 同时实现会话密钥的分配, 为认证服务器 AS 配置计算量少的 Rabin PSS MR 签名的验证操作 [4] Rabin OAEP 加密 [5] 操作和改进型 ElGamal 签名操作 [6], 为移动终端 STA 配置计算量较大的 Rabin OAEP 解密操作和改进型 ElGamal 签名的验证操作, 以此达到降低响应时延提高网络效率的目的. 此外, 为进一步节省通信带宽, 将发送公钥及相应证书的传统公钥认证过程缩短为仅发送公钥证书 ( 而不发送公钥 ) 的精简模式, 方法是采用具有消息恢复功能的 Rabin PSS MR 签名方案. 认证过程结束时, 通信双方将同时得到一个共享的会话密钥以确保随后通信的保密性, 实现认证功能与密钥分配功能的巧妙结合. 1 无线局域网认证结构 AuthenticationstructureofWLAN 无线局域网的拓扑结构可分为两类 : 无中心拓扑结构和有中心拓扑结构 [1], 本文讨论如图 1 有中心拓扑结构的无线局域网. 要实现实体间的安全通信, 要求移动终端 STA 在接入网络之前通过接入设备 AP 与认证服务器 AS 进行双向的认证. 只有通过认证 [7] 才能继续进行保密通信. 在 802 1x 认证框架中, 认证过程主要涉及 3 个功能实体, 即证书中心 CA 认证服务器 AS 和移动终端 STA. 1) 证书中心 CA 负责为 STA 和 AS 颁发公钥证书. 证书是用消息恢复型 Rabin PSS MR 签名方案生成的, 以使证书的验证工作量较小.

2 224 刘佳, 等. 基于消息恢复型 Rabin PSS 的无线局域网认证方案. LIUJia,etal.WLANauthenticationschemebasedonmesage recoveryrabin PSS. 图 1 无线局域网系统网络模型 Fig.1 NetworkmodelofWLANsystem 2) 认证服务器 AS 负责处理所有 STA 在任何时刻的接入认证请求, 验证 STA 公钥证书及身份的合法性, 并向 STA 提供 AS 公钥证书及身份的证明. 3) 移动终端 STA 在接入网络前须向 AS 证明其公钥证书及身份的合法性, 随后还要验证 AS 的公钥证书及身份. STA 通常是桌面计算机或笔记本电脑, 其计算资源相对充足 ; 而 AS 虽然计算能力也不弱, 但需要负责处理所有 STA 在任何时刻的接入认证请求, 其计算任务相对繁重. 为了提高网络的运行效率, 减小响应的时延, 可以由 STA 承担认证过程中计算量较大的工作, 尽量减少 AS 的工作量. 因此本文提出以下设计原则. 1)CA 发放公钥证书给 STA 和 AS, 公钥证书的验证算法应该尽量简单. 2)STA 发送公钥证书给 AS 证明其合法性时, AS 验证工作量应该尽可能小 ; 在验证 STA 身份时, AS 进行随机数加密操作, 验证 STA 的解密能力, 该过程计算量也应该尽可能小. 3)AS 向 STA 证明公钥证书及身份的合法性时,AS 发送公钥证书给 STA 证明其合法性, 并发送签名给 STA 证明其身份, 要求签名过程仅进行尽量少的运算. 2 基础密码算法 Basiccryptographicalgorithms 为了实现认证服务器 AS 和移动终端 STA 的双向认证, 为它们分别配置了不同的签名算法及加密算法, 用以适应无线局域网特殊的非对称结构. 本节介绍认证方案中采用的密码算法 : 改进型 ElGamal 签名算法 Rabin OAEP 加密算法 Rabin PSS MR 签名算法和 SMS4 分组加密算法 [8]. 2.1 改进型 ElGamal 签名算法参数设置取 p 为一个大素数,g 是 Z p 的一个本原元, x R Z p-1 为私钥,y=g x modp 为公钥,m Z p 1 是待签名的消息签名生成 1) 选取一个随机数 r Z p-1 ; 2)V=g r (modp),w=x(m+v)-r(modp-1). (W,V) 作为消息 m 的签名签名验证收到签名 (W,V) 后, 判断 y (m+v) =Vg W modp 是否成立. 若成立, 则确认签名 (W,V) 有效, 否则认定签名无效. 本文采用此改进型 ElGamal 签名算法是因为签名过程中的模幂运算 g r 可预先计算, 实时进行的只 [7] 有模加和模乘运算, 而无原始 ElGamal 签名方案中的模逆运算. 这样, 可以加快 AS 的运算速度, 降低其响应时延. 2.2 Rabin OAEP 加密算法 Rabin 原始算法无法抵抗自适应选择密文攻击. 为此,Belare 和 Rogaway 提出最优非对称加密填充技术 OAEP(OptimalAsymmetric Encryption Pad ding) [5], 采用随机化的消息填充技术, 引入无碰撞的哈希函数, 提供了可证明的安全性 ( 附录 A). Rabin OAEP 加密算法如图 2 所示参数设置图 2 Rabin OAEP 加密方案 Fig.2 Rabin OAEPencryptionscheme 运行密钥产生算法 Gen(1 k ) 得到 (N=pq,p,q, G,H,n,k 0,k 1 ), 其中 :N=pq 是公钥 ;p=q=3(mod4) 是私钥 ; N =k=n+k 0 +k 1 ;2 -k 0 和 2 -k 1 为可忽略

3 学报 : 自然科学版,2009,1(3): JournalofNanjingUniversityofInformationScienceandTechnology:NaturalScienceEdition,2009,1(3): 的量 ;H:{0,1} k-k 0 {0,1} k 0,G:{0,1} k 0 {0,1} k-k 0 是两个哈希函数 ;n 是明文消息 m 的长度加密过程对消息 m {0,1} n 进行加密, 执行下列计算 : 1)r U {0,1} k 0,s (m 0 k 1 ) G(r),t r H(s); 2)c (s t) 2 modn.c 作为消息 m 的密文解密过程收到密文 c 后, 执行下列计算 : 1) 利用私钥 p 和 q 计算 s t q(q -1 modp)c p+1 4 +p(p -1 modq)c q+1 4 (modn), 其中 s =n+k 1 =k-k 0, t =k 0 ; 2)u t H(s),v s G(u); 3) 若 v=m 0 k 1 输出消息 m, 否则认为密文是无效的. Rabin OAEP 加密机制引入了哈希函数 G 和 H, 其计算量相对于模幂和模逆等运算来说几乎可以忽略不计, 但却能以如此小的代价获得如附录 A 所示的可证明安全性. 另外,AS 实施 Rabin OAEP 加密操作时只须进行模平方运算和简单的哈希异或运算, 而将相对复杂的求平方根运算留给计算资源相对充裕的 STA, 符合前述密码算法在认证方案中的配置原则. 2.3 Rabin PSS MR 签名算法 Rabin 原始签名函数属确定性算法, 无法抵抗自适应选择消息攻击.Belare 和 Rogaway 设计了 PSS (ProbabilisticSignatureScheme) 概率签名机制, 并且能够实现消息恢复功能, 形成 PSS MR 方案. 图 3 给出了 Rabin PSS MR 签名方案的原理. 图 3 Rabin PSS MR 签名方案 Fig.3 Rabin PSS MRsignaturescheme 密钥设置运行密钥产生算法 Gen(1 k ) 得到 (N=pq,p,q, G,H,n,k 0,k 1 ), 其中 :N=pq 是公钥 ;p=q=3(mod4) 是私钥 ; N =k=n+k 0 +k 1 +1;2 -k 0 和 2 -k 1 为可忽略的量 ;G:{0,1} k 1 {0,1} k k 1 1,H:{0,1} {0, 1} k 1 是两个哈希函数, 进一步将 G 拆分成 G 1 G 2, 即 G 1 :{0,1} k 1 {0,1} k 0,G 2 :{0,1} k 1 {0,1} n ;n 是签名消息 m 的长度签名生成欲对消息 m {0,1} n 进行签名, 须执行下列计算 : 1)r U {0,1} k 0,w H(m r),r G 1 (w) r, m =G 2 (w) m; 2)y 0 w r m ; 3) 利用私钥 p 和 q 计算 u q(q -1 modp)y p p(p -1 modq)y q+1 4 (modn),u 作为消息 m 的签名签名验证收到签名 u 后, 执行下列计算. 1)y u 2 modn. 将 y 分段解释为 b w r γ, 其中 :b 是 k 比特 y 中的第一个比特 ;w 是后续的 k 1 比特 ;r 是在接下来的 k 0 比特 ;γ 是其余 n 比特. 2)r G 1 (w) r,m G 2 (w) γ. 3) 若 H(m r)=w 且 b=0, 则返回消息 m, 并确认签名 u 有效, 否则认定签名无效. 用 Rabin PSS MR 签名算法产生的公钥证书, 根据文献 [4], 配置 1024 比特的证书和 767 比特的公钥, 可以在公钥认证过程中只发送 1024 比特的证书而无须同时发送 767 比特的公钥接收方仅利用证书 ( 签名 ) 就可以恢复出公钥消息, 大大减少对通信带宽的要求. 而且证书的验证只须做模平方运算, 可进一步减少 AS 的工作量. 此外, 计算量几乎可忽略不计的哈希函数的引入同样能提供可证明的安全性 ( 附录 B). 2.4 SMS4 分组加密算法 2006 年 1 月 6 日, 中国国家密码管理局发布第 7 号公告, 将用于我国无线局域网产品的加密标准确定为 SMS4 算法, 这是国内官方公布的第一个商用密码算法.SMS4 是一个分组长度为 128 比特密钥长度为 128 比特的分组密码算法, 加密算法与密钥扩展算法都采用 32 轮非线性迭代结构, 具体细节可参考文献 [6]. SMS4 分组密码算法主要采用了异或移位查

4 226 刘佳, 等. 基于消息恢复型 Rabin PSS 的无线局域网认证方案. LIUJia,etal.WLANauthenticationschemebasedonmesage recoveryrabin PSS. 表等操作, 运行速度比公钥密码算法快许多, 适用于海量数据的加解密. 这里用它来提供会话的保密性, 关键问题是如何为通信的双方分配共享的会话密钥. 本文设计的认证方案能在成功认证的同时巧妙地实现会话密钥的分配. 3 无线局域网认证方案 WLANauthenticationscheme 根据在第 2 节提出的设计原则, 给出了 3 个认证实体的参数设置及其在认证过程中采用的密码算法, 具体参数设置如表 1 所示. 图 4 给出了设计的无线局域网认证方案的交互过程. STA AS STA 公钥证书中的 hsta s t=oaep(r 1 R 2 H(R 1 R 2 )) A=[s t] 2 modn STA B=En R2 [R 3 ] H(R 1 R 2 )) C=En R2 [h AS W V ] W=x AS (R 1 +R 3 +V)-r(modp AS -1) 图 4 无线局域网认证方案 Fig.4 WLANauthenticationscheme 认证方案主要包括以下步骤. 1)STA 把公钥证书 h STA 发送给 AS. 2)AS 利用 Rabin PSS MR 验证算法验证 STA 公钥证书的合法性 ; 若认证成功,AS 选择两个随机数 R 1 和 R 2, 计算其哈希函数值 H(R 1 R 2 ), 再利用 Rabin OAEP 方案加密 R 1,R 2 和 H(R 1 R 2 ), 将加密结果 A 发送给 STA. 3)STA 利用 Rabin OAEP 方案对 A 进行解密, 恢复出 R 1 和 R 2, 并检验其哈希值 ; 如果解密成功, STA 选择一个随机数 R 3, 以 R 2 为 SMS4 密钥加密 R 3 和 H(R 1 R 2 ), 即 B=En R2 [R 3 H(R 1 R 2 )], 将 B 发送给 AS. 4) 如果 AS 解密得到了正确的 H(R 1 R 2 ), 则可相信 STA 身份的合法性, 并同时得到随机数 R 3 ; AS 利用其私钥 x AS 和预计算值 V=g r modp AS, 计算改进型 ElGamal 签名 W =x AS (R 1 +R 3 +V)- r(modp AS -1); 并以 R 2 为 SMS4 密钥加密其证书 C AS 中的 h AS W 和 V, 即 C=En R2 [h AS W V], 将 C 发送给 STA. 5)STA 收到 AS 的加密消息 C 后, 先用 R 2 解密恢复得到 C AS 中的 h AS W 和 V; 然后, 用 Rabin PSS MR 算法验证证书的合法性. 若证书认证成功,STA 再检验 AS 的改进型 ElGamal 签名是否正确, 即检验 y (R 1 +R 3 +V) AS =Vg W modp AS 是否成立. 如果成立,STA 就接受 AS 为合法服务器, 双向认证结束. 认证结束后,STA 和 AS 可用 R 3 作为会话密钥加密双方后续的通信, 以达到通信保密的目的. 本文的认证方案具有如下几个优势. 1) 由于采用消息可恢复的 Rabin PSS MR 概率签名作为公钥的证书, 在 STA 向 AS 证明其公钥证书合法性时只需要发送公钥证书 ( 签名 ) 即可, 而不需发送公钥 ( 消息 ). 在 AS 向 STA 证明其公钥证书合法性时, 情况类似. 通信过程中通信量减少了 ( ) % ( ), 这在很大程度上降低了对传输带宽的要求. 2) 由于 AS 负责处理所有 STA 在任何时刻的接入认证请求, 其计算任务相对繁重 ; 而 STA 的计算资表 1 认证实体参数设置 Table1 Setupofparametersfortheentitytobecertificated 实体私钥公钥证书密码运算 CA Rabin 私钥 :(p CA,q CA ) p CA =q CA =3mod4 p CA = q CA =l CA Rabin 公钥 :N CA N CA =2l CA Rabin PSS MR 签名 AS ElGamal 私钥 :x AS x AS =l AS ElGamal 公钥 : y AS =g^(x AS )modp y AS =l AS C AS ={AS,y AS,T AS,h AS } h AS =y 1/2 AS modn CA AS =l AS1, T AS =l AS2, h AS =2l CA Rabin PSS MR 签名的验证 Rabin OAEP 加密 SMS4 解密改进型 ElGamal 签名 SMS4 加密 STA Rabin 私钥 :(p STA,q STA ) p STA =q STA =3mod4 p STA = q STA =l STA Rabin 公钥 :N STA N STA =2l STA C STA ={STA,N STA,T STA,h STA } h STA =N 1/2 STA modn CA STA =l STA1, T STA =l STA2, h STA =2l STA Rabin OAEP 解密 SMS4 加密 SMS4 解密 Rabin PSS MR 签名的验证改进型 El Gamal 签名的验证

5 学报 : 自然科学版,2009,1(3): JournalofNanjingUniversityofInformationScienceandTechnology:NaturalScienceEdition,2009,1(3): 源相对充裕, 故将方案中的认证方式设计成适合这种特点的非对称形式 : 由 STA 承担在认证过程中计算量较大的工作, 减少 AS 的工作量, 以提高网络的运行效率, 减小响应的延时. 具体体现在以下 3 个方面 :AS 验证 STA 公钥证书合法性时, 进行的是 Rabin 签名的验证, 只需做模平方这样一个简单的运算 ;AS 向 STA 发送挑战用以验证其是否持有公钥证书对应的私钥时, 采用 Rabin 加密方案, 也是只做一个模平方运算 ; 由 AS 向 STA 实时证明自己身份时, 采用改进型 ElGamal 签名方案, 只需做模加和模乘运算. 3) 本方案没有像文献 [10] 一样直接用 Rabin 方案, 这是因为 Rabin 函数是确定性算法, 即 Rabin 签名算法输出的签名是由密钥 (sk,pk) 和 m 唯一确定的. 这种确定性使得选择消息攻击奏效, 存在很大的安全隐患. 本文采用了具有消息恢复功能的 Rabin PSS MR 概率签名机制, 虽然引入了两个哈希函数, 但相对于公钥密码机制中的模幂和模逆等运算来说, 其计算量几乎可以忽略不计. 然而, 如此小的代价换来的是附录 B 的可证明安全性. 4) 认证协议运行结束时, 通信双方获得了相同的会话密钥 R 3, 即同时实现了密钥分配的功能. 综上所述, 本文提出的基于消息可恢复型 Rabin PSS MR 概率签名机制的安全认证方案非常适合无线局域网的通信要求. 4 结束语 Concludingremarks 本文通过对无线局域网结构的分析, 设计了一种基于公钥密码技术的认证方案. 该方案充分利用了 Rabin PSS MR 签名方案和 ElGamal 改进型签名方案中签名操作与验证操作的非对称性, 实现了认证服务器 AS 与移动终端 STA 双向的高效认证及密钥分配, 提高了网络的认证接入速度. 同时,Rabin PSS MR 签名方案使得公钥认证过程中只须发送证书而无须同时发送公钥, 大大降低了对通信带宽的要求. 参考文献 References [1] TheLAN/MANstandardscommiteeoftheIEEEcomputersocie ty.wireleslanmediumaccescontrolandphysicallayerspeci fication[s].ieeestd [2] ChibaM,DommetyD,EklundM,etal.Dynamicauthorizationex tensionstoremoteauthenticationdialinuserservice(radius) [S].RequestforComments:5176,NetworkWorkingGroup,2008 [3] StermanB,SadolevskyD,SchwartzD,etal.RADIUSextensionfor digestauthentication[s].requestforcomments:5090,network WorkingGroup,2008 [4] BelareM,RogawayP.Theexactsecurityofdigitalsignatures: HowtosignwithRSAandRabin[C] AdvancesinCryptology: ProceedingsofEUROCRYPT 96,LNCS1070,Springer Verlag, 1996: [5] BelareM,RogawayP.Optionalasymmetricencryption[C] Ad vancesin Cryptology:ProceedingsofEUROCRYPT 94,LNCS 950,Springer Verlag,1994: [6] HarnL,XuY.DesignofgeneralisedElGamaltypedigitalsigna tureschemesbasedondiscretelogarithm[j].ieeeelectronics leters,1994,30(24): [7] TheLAN/MANstandardscommiteeoftheIEEEcomputersocie ty.ieeestd802 1X 2001,IEEEstandardforlocalandmetropoli tanareanetworks:prot basednetworkaccescontrol[s].ieee NewYork,2001 [8] 国家密码管理办公室. 无线局域网产品使用的 SMS4 密码算法 [EB/OL].[ ].htp: news_1106.htm,2006 NationalPasword ManagementOfice.SMS4 cipheralgorithm usedbywlanproducts[eb/ol].[ ].htp: www. oscca.gov.cn/doc/6/news 1106.htm,2006 [9] Elgamal.Apublickeycryptosystemandasignatureschemebased ondiscretelogarithms[j].ieeetransinfotheory,1985,31(4): [10] 李志杰. 公钥密码技术在移动通信网络中的应用 [J]. 中国科技信息,2005(8):15,33 LIZhijie.Applicationofpublickeyciphertechnologyinmobile communicationsnetwork[j].chinascienceandtechnologyinfor mation,2005(8):15,33 附录 A:Rabin OAEP 算法安全性证明定理 1 假设分解大整数 N=pq 是困难的 ( 其中 p,q 为两个大素数 ), 则 Rabin OAEP 算法在自适应选择密文攻击下是安全的. 证明等价地证明逆否命题若 Rabin OAEP 算法是不安全的, 则大整数 N 可以分解. Simulator 选择 α, 计算 y=α 2 modn. 若能通过与 Adversary 的如下交互求得 x b ±α, 使 y=x 2 bmodn, 则 Simulator 可分解大整数 N=pq. 为了与 Adversary 进行合理交互,Simulator 需仿真对 H 函数询问 G 函数询问和加密询问的应答, 并分两个阶段进行应答. 1) 参数设置运行密钥产生算法 Gen(1 k ) 得到 (N=pq,p,q,G,H,n,k 0,k 1 ), 其中 N=pq 是公钥,p=q=3(mod4) 是私钥 ; N =k=n+k 0 +k 1 ; 2 -k 0 和 2 -k 1 为可忽略的量 ;H:{0,1} k-k 0 {0,1} k 0,G:{0,1} k 0 {0, 1} k-k 0 是两个哈希函数 ;n 是明文消息 m 的长度. 2) 寻找阶段 a H 函数询问的应答仿真.Adversary 向 Simulator 询问 h i 的 H 函数值,Simulator 随机选择 H hi 发送给 Adversary, 并把 H 函数的输入和输出对应关系存在列表 H_LIST; b 数询问的应答仿真.Adversary 向 Simulator 询问 g i 的 G 函数, Simulator 随机选择 G gi 发送给 Adversary, 并把 G 函数的输入和输出对应关系存在列表 G_LIST; c 密询问的应答仿真.Adversary 发送明文 x 0,x 1 给 Simulator, Simulator 将挑战问题 y 作为 Adversary 的攻击密文提供给他, 让其判断是 x 0 还是 x 1 对应的密文. 在 Simulator 控制 G_oracle 和 H_oracle 的情况下, 任何消息 ( 包括 x 0,x 1 ) 都可能加密成 y, 即只要对消息 x 选择随机数 r, 控制 G(r)=x s 和 H(s)=r t 即可, 既然这样, 就没有理由怀疑 y 不是 x 0 或 x 1 的密文了, 因此问题嵌入是合理的. 3) 猜测阶段 a H 函数询问的应答仿真.Adversary 向 Simulator 询问 h i 的 H 函数值,Simulator 随机选择 H hi 发送给 Adversary, 并把 H 函数的输入

6 228 刘佳, 等. 基于消息恢复型 Rabin PSS 的无线局域网认证方案. LIUJia,etal.WLANauthenticationschemebasedonmesage recoveryrabin PSS. 和输出对应关系存在列表 H_LIST, 同时遍历 G_LIST, 计算 y j =(h i H hi g j ) 2,j=1,2,,Λ, 如果存在 y j 使 y=y j, 则令 w=h i H hi g j, 按照 Rabin OAEP 解密过程, 将 w 分段解释成 s t, s =n+k 1 = k-k 0, t =k 0 ;u t H(s),v s G(u); 若 v=x b 0 k 1, 输出消息 x b, 如果 x b ±α, 算法 Simulator 就可以分解大整数 N=pq: 由 x 2 b= α 2 modn 有 α+x b N 和 α x b N. b G 函数询问的应答仿真.Adversary 向 Simulator 询问 g i 的 G 函数,Simulator 遍历 H_LIST, 计算 y j =(h j H hj g i ) 2,j=1,2,,Λ. 如果存在 y j 使 y=y j, 则令 w=h j H hj g i, 按照 Rabin OAEP 解密过程, 可得消息 x b, 如果 x b ±α, 算法 Simulator 就可以分解大整数 N= pq: 由 x 2 b=α 2 modn 有 α+x b N 和 α x b N. 同时计算 G gi =x b h j,b {0,1}, 并发送 G gi 给 Adversary; 如果不存在 y j 使 y=y j,simulator 随机选择 G gi 发送给 Adversary, 并把 G 函数的输入和输出对应关系存在列表 G_LIST; Adversary 以大于 1/2 的概率发送攻击密文 y 对应的明文 x b,b {0,1} 给 Simulator, 则有理由相信,Adversary 会以某种技巧 ( 概率大于 1/2) 去对 x 0 和 x 1 进行加密尝试, 其中 Adversary 可能用了一些随机数 r, 向控制 G_oracle 和 H_oracle 输出的 Simulator 提出 r 的 G 询问和 s 的 H 询问. 其提问和回答均被 Simulator 记录. 当 Adversary 提供 b 的回答时, 虽然他不知道 Adversary 用了哪时的 (r,s) 取得的成功, 但 Simulator 相信其已经尝试成功, 并且他相信 (r,s) 必被询问并记录过, 因此他只需要逐一尝试其记录即可. 附录 B:Rabin PSS MR 签名算法安全性证明定理 2 假设分解大整数 N=pq 是困难的 ( 其中 p,q 为两个大素数 ), 则 Rabin PSS MR 算法在自适应选择消息攻击下是不可伪造的. 证明等价地证明逆否命题若 Rabin PSS MR 算法是不安全的, 则大整数 N 可以分解. Simulator 选择 α, 计算 y=α 2 modn. 若能通过与 Adversary 的如下交互求得 β ±α, 使 y=β 2 modn, 则 Simulator 可分解大整数 N=pq. 为了与 Adversary 进行合理交互,Simulator 需仿真对签名询问 H 函数询问和 G 函数询问的应答. 1) 密钥设置运行密钥产生算法 Gen(1 k ) 得到 (N=pq,p,q,G,H,n,k 0,k 1 ), 其中 N=pq 是公钥,p=q=3(mod4) 是私钥 ; N =k=n+k 0 +k 1 +1; 2 -k 0 和 2 -k 1 为可忽略的量 ;G:{0,1} k 1 {0,1} k-k 1-1,H:{0,1} {0,1} k 1 是两个哈希函数, 进一步将 G 拆分成 G 1 G 2, 即 G 1 :{0,1} k 1 {0,1} k 0,G 2 :{0,1} k 1 {0,1} n ;n 是签名消息 m 的长度. 2) 签名询问 a Adversary 向 Simulator 询问消息 m i 的签名,Simulator 任选 k 0 比特的随机数 r i ; b 如果存在 j:j<i,r j =r i, 则仿真终止 ; c 随机选择 s i, 计算 y i =s 2 imodn 满足最高比特位为 0. 把 y i 写成 y i =0 w i r i m i, 其中 w i 是 k 1 比特,r i 是 k 0 比特,m i 是最后 k-k 0 -k 1-1 比特. 令 H(m i r i )=w i,g 1 (w i )=r i r i,g 2 (w i )= m i m i,g(w i )=G 1 (w i ) G 2 (w i ), 把 H 函数和 G 函数输入和输出对应关系分别存在列表 H_LIST0,G_LIST0 中 ; d 如果存在 j:j<i, 使 w j =w i, 则仿真终止 ; e 把 s i 当作消息 m i 的签名发送给 Adversary, 同时 Simulator 保存 (m i,r i,s i,y i ); f Adversary 在接收到 m i 的签名 s i 后, 如果要进行验证, 首先求 y i =s 2 i=0 w i r i m i, 验证 w i =H(m i r i ), 其中 r i =G 1 (w i ) r i,m i =G 2 (w i ) m i, 若等式成立, 说明 m i 的签名就是 s i, 其中 H 函数和 G 函数都要去询问 Simulator. 3)H 函数询问的应答仿真 a Adversary 向 Simulator 询问 m i r i 的 H 函数值,Simulator 搜索 H_LIST0 列表, 如果存在 j<i, 使 m j r j =m i r i, 就从列表 H_ LIST0 中查找此 H 函数输入对应的输出发送给 Adversary; b 如果不存在 j<i, 使 m j r j =m i r i, 则随机选择 s i, 计算 y i = s 2 i y=0 w i r i m i, 令 w i =H(m i r i ); c 如果存在 j<i, 使 w j =w i, 则仿真终止. 若不存在 j<i, 使 w j = w i, 则令 G 1 (w i )=r i r i,g 2 (w i )=m i m i,g(w i )=G 1 (w i ) G 2 (w i ), 把 H 函数和 G 函数输入和输出对应关系分别存在列表 H_ LIST1,G_LIST1, 同时在 Simulator 保存 (m i,r i,s i,y i ); d 最后发送 w i =H(m i r i ) 给 Adversary 作为 m i r i 的 H 函数值. e G 函数询问的应答仿真. Adversary 向 Simulator 询问 w i 的 G 函数,Simulator 搜索列表 G_ LIST0 和 G_LIST1, 如果存在 j<i, 使 w j =w i, 直接返回对应的输出. 否则随机选择 k-k 1-1 比特的 α, 使 G(w i )=α, 发送 α 给 Adversary 作为 w i 的 G 函数值. 若 Adversary 能以不可忽略的概率伪造有效 Rabin PSS MR 消息签名对 (m,s), 则它应该能通过验证.Simulator 计算 Y=s 2 =0 w r m,r=r G 1 (w), 以不可忽略的概率在列表中找到 (m,r,w, r,m )=(m i,r i,w i,r i,m i ), 即 Y=s 2 =0 w r m =s 2 i y=0 w i r i m i, 亦即 s 2 =s 2 i y, 则 y= ( ) s s i 2, 设 β= s s i, 如果 β ±α, 算法 Simulator 就可以分解大整数 N=pq: 由 β 2 =α 2 modn 有 α+β N 和 α β N. 证毕. WLANauthenticationschemebasedonmesage recoveryrabin PSS LIUJia 1,2 WEIBaodian 1,3 DAIXianhua 1 1 SchoolofInformationScienceandTechnology,SunYat senuniversity,guangzhou ZhongKaiInstituteofAgriculturalEngineering,Guangzhou StateKeyLabofIntegratedServiceNetworksTheoryandKeyTechnology,XidianUniversity,Xi an Abstract Takingtheasymmetricarchitectureofthewireleslocalareanetworkintoconsideration,weproposean identityauthenticationschemebasedonthepublickeyciphertechnology,wheresecretsesion keysharingisac companiedwiththesuccesfulauthentications.theauthenticationseverasandthemobileterminalsstasareprop erlyconfiguredwithdiferentworkloadsofsignaturegenerationsandsignatureverificationsinrabin PSS MRscheme andtheimprovedelgamalsignaturescheme,aimingtogreatlyenhancethenetwork sresponseeficiency.themesage recoveryfunctionoftherabin PSS MRschemehasreducedthetransmisionworkloadsharplysincethepublickeys arenotnecesarytobetransmitedinthisscheme,whichhassavedagreatdealofcommunicationbandwidth. Keywords WLAN;authentication;Rabin PSS MR;ElGamal

Microsoft Word - 第2部分.doc

Microsoft Word - 第2部分.doc SM9 标识密码算法第 2 部分 : 数字签名算法目次 1 术语和定义... 2 2 符号... 2 3 算法参数与辅助函数... 3 3.1 总则... 3 3.2 系统参数组... 3 3.3 系统签名主密钥和用户签名密钥的产生... 4 3.4 辅助函数... 4 3.4.1 概述... 4 3.4.2 密码杂凑函数... 4 3.4.2.1 密码杂凑函数 Hv( )... 4 3.4.2.2