第３７卷 第１１期 、，ｏ１．３７ ・计算机工程 ２０１１年６月 Ｊｕｎｅ ２０ｌ１ ＮＯ．１１ Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ 安全技术・ 文章编号：１０００－－３４２８（２０１１）１１—＿０１５８—０２ 文献标识码：Ａ 中图分类号：ＴＰ３０９ 辫群上的可转换认证加密方案 裴俐春 ，隗云 ，熊国华 ，张兴凯 （１．防空兵指挥学院信息控制系，郑州４５００５２；２．信息工程大学电子技术学院，郑州４５０００４； ３电子技术研究所，北京１００１９５；４．９６６１０部队，北京１０２２０８） 摘要：量子计算的快速发展给目前的公钥密码体制带来严重威胁，非交换的辫群为构造安全密码协议提供了新平台。基于辫群上共轭搜 索问题和多重共轭搜索问题的难解性，提出一个可转换认证加密方案，只有指定的接收者才能恢复认证的原始消息；当发送者否认签名时， 接收者不需要发送方的参与即可将收到的签名转换为一般签名，并向第三方证明发送者的不诚实。与基于交换代数的方案相比，该方案在 抗量子攻击上更有优势。 关健词：辫群；共轭搜索问题；多重共轭搜索问题；可转换认证加密 Ｃｏｎｖｅｒｔｉｂｌｅ Ａｕｔｈｅｎｔｉｃａｔｅｄ Ｅｎｃｒｙｐｔｉｏｎ Ｓｃｈｅｍｅ ｏｖｅｒ Ｂｒａｉｄ Ｇｒｏｕｐ ＰＥＩ Ｌｉ．ｃｈｕｎ ，ＷＥＩ Ｙｕｎ。Ｇｕｏ．ｈｕａ ，ＺＨＡＮＧ Ｘｉｎｇ．ｋａｉ ，ＸＩＯＮＧ （１．Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｃｏｎｔｒｏｌ，Ａｉｒ Ｄｅ￣ｎｃｅ Ｆｏｒｃｅｓ Ｃｏｍｍａｎｄ Ａｃａｄｅｍｙ，Ｚｈｅｎｇｚｈｏｕ ４５００５２，Ｃｈｉｎａ； ２．Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｅｌｅｃｔｒｏｎｉｃ Ｔｅｃｈｎｏｌｏｇｙ，Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｚｈｅｎｇｚｈｏｕ ４５０００４，Ｃｈｉｎａ； ３．Ｉｎｓｔｉｔｕｔｅ ｏｆＥｌｅｃｔｒｏｎｉｃ Ｔｅｃｈｎｏｌｏｇｙ，Ｂｅｉｊｉｎｇ １００１９５，Ｃｈｉｎａ；４．Ｕｎｉｔ ９６６１０，Ｂｅｉｊｉｎｇ １０２２０８，Ｃｈｉｎａ） ［Ａｂｓｔｒａｃｔ］Ｔｈｅ ｒａｐｉｄ ｄｅｖｅｌｏｐｍｅｎｔ ｏｆ ｑｕａｎｔｕｍ ｃｏｍｐｕｔｉｎｇ ｂｒｉｎｇｓ ｇｒｅａｔ ｃｈａｌｌｅｎｇｅｓ ｔｏ ｐｕｂｌｉｃ ｋｅｙ ｃｒｙｐｔｏｓｙｓｔｅｍｓ．Ｔｈｅ ｂｒａｉｄ ｇｒｏｕｐ，ｗｈｉｃｈ ｉｓ ｎｏｎ—ｃｏｍｍｕｔａｔｉｖｅ，ｐｒｏｖｉｄｅｓ ａ ｎｅｗ ｐｌａｔｆｏｒｍ ｏｆ ｃｏｎｓｔｒｕｃｔｉｎｇ ｃｒｙｐｔｏｇｒａｐｈｉｃ ｐｒｏｔｏｃｏｌｓ．Ａ ｃｏｎｖｅｒｔｉｂｌｅ ａｕｔｈｅｎｔｉｃａｔｅｄ ｅｎｃｒｙｐｔｉｏｎ ｓｃｈｅｍｅ ｏｖｅｒ ｂｒａｉｄ ｇｒｏｕｐ ｉｓ ｐｒｏｐｏｓｅｄ ｏｎ ｔｈｅ ｄｉｆｉｃｕｌｆｔｙ ｏｆ ｃｏｎｊｕｇａｃｙ ｓｅａｒｃｈ ｐｒｏｂｌｅｍ ａｎｄ ｍｕｌｔｉｐｌｅ ｃｏｎｊｕｇａｃｙ ｐｒｏｂｌｅｍ，ｉｎ ｗｈｉｃｈ ｏｎｌｙ ｔｈｅ ｄｅｓｉｇｎａｔｅｄ ｒｅｃｅｉｖｅｒ ｃａｎ ｒｅｃｏｖｅｒ ａｎｄ ａｕｔｈｅｎｔｉｃａｔｅ ｔｈｅ ｍｅｓｓａｇｅ，ｗｈｅｎ ｔｈｅ ｓｅｎｄｅｒ ｒｅｐｕｄｉａｔｅｓ ｔｈｅ ｓｉｇｎａｔｕｒｅ，ｔｈｅ ｒｅｃｅｉｖｅｒ ｃａｎ ｐｒｏｖｅ ｔｈｅ ｄｉｓｈｏｎｅｓｔｙ ｏｆ ｔｈｅ ｓｅｎｄｅｒ ｂｙ ｃｏｎｖｅｒｔｉｎｇ ｔｈｅ ｓｉｇｎａｔｕｒｅ ｔｏ ａｎ ｏｒｄｉｎａｒｙ ｏｎｅ ｗｉｔｈｏｕｔ ｔｈｅ ｃｏｏｐｅｒａｔｉｎｇ ｏｆ ｔｈｅ ｓｅｎｄｅｒ．Ａｓ ｆｏｒ ｔｈｅ ｒｅｓｉｓｔａｎｃｅ ａｇａｉｎｓｔ ｑｕａｎｔｕｍ ａｔｔａｃｋｓ，ｔｈｅ ｐｒｏｐｏｓｅｄ ｓｃｈｅｍｅ ｈａｓ ａｄｖａｎｔａｇｅ ｏｖｅｒ ｔｈｅ ｓｃｈｅｍｅｓ ｂａｓｅｄ ｏｎ ｃｏｍｍｕｔａｔｉｖｅ ａｌｇｅｂｒａｉｃ ｓｔｒｕｃｔｕｒｅｓ． ［Ｋｅｙ ｗｏｒｄｓ］ｂｒａｉｄ ｇｒｏｕｐ；ｃｏｎｊｕｇａｃｙ ｓｅａｒｃｈ ｐｒｏｂｌｅｍ；ｍｕｌｔｉｐｌｅ ｃｏｎｊｕｇａｃｙ ｓｅａｒｃｈ ｐｒｏｂｌｅｍ；ｃｏｎｖｅｒｔｉｂｌｅ ａｕｔｈｅｎｔｉｃａｔｅｄ ｅｎｃｒｙｐｔｉｏｎ ＤＯＩ：１０．３９６９０．ｉｓｓｎ．１０００—３４２８．２０１１．１１．０５４ １概述 量子计算 的快速发展使得基于整数分解或离散对数 问题难解性的公钥密码体制面临严重威胁。为了抵抗已知量 子算法的攻击，大量学者开始设计非基于数论的、基于非交 解性构造了一个可转换认证加密方案，并对其安全性质进行 了详细分析。 ２预备知识 本节介绍辫群及辫群上的难解问题 Ｊ。 换代数的公钥密码体制，如基于一般非交换群的密码 】、基 于有限非交换群的ＭＯＲ密码 等。辫群的概念由Ａｒｔｉｎ Ｅ于 定义１辫群 （ｎ≥２为自然数）是由生成元 ， ，…， 一． 生成的有限表示的无限群。其生成元满足： ＝ １９４７年首次提出 ｌ，由于其结构复杂、运算所需的时间和空 间小的特点，被用于构造公钥密码系统 Ｊ。此后，基于辫群 （Ｊｉ—Ｊｌ≥２） ＋】 （１≤ｉ≤ｎ一２） ＋ｌ ＝ ＋１ 的密钥交换协议 】、认证方案 。…、加密方案… 及签名方 案 相继被提出。 为了在计算机网络环境中实现消息的安全可认证传输， Ｈｏｒｓｔｅｒ Ｐ等 于１９９４年首次提出了认证加密的思想。认证 加密与数字签名的不同之处在于除了指定的接收者外，其他 任何第三方都不能确定这个认证加密签名是发送者所签。为 了防止发送者对签名进行否认，Ａｒａｋｉ Ｓ等 提出了可转换的 因此，辫群 可表示为： ＝（ ，… １， ）． ｆ …，ｃｒ 生成的群 辫群中的元素称为一个 辫或辫元。当ｎ＝２时，Ｂ 为 无限循环群，本文不予考虑。 定义２对于辫群Ｂ ，由生成元 ， ，…，ｑ Ｊ－ｉ生成的群 叫 的左子群，记作Ｌ ；由 叫Ｂ 的右子群，记作ＲＢ 。 基金项目：国家“８６３”计划基金资助项目（２００９ＡＡ【）１ｚ４３８） 认证加密方案，如果发送者事后否认其签名，接收者可以将 收到的签名转换为一般签名，向第三方证明发送方的不诚实。 但是在该方案中，接收者需要发送者的合作才能将收到的签 名转换成一般签名，这一需求显然与设计可转换认证加密方 案的意图相矛盾。２００２年，Ｗｕ Ｔ等 针对这一问题提出新 的可转换认证加密方案，接收者不需要发送者的合作即可完 成签名的转换，这类认证加密方案因此成为了研究热点 。 作者简介：裴俐春（１９８１一），女，助教、硕士，主研方向：网络与信 息安全；隗云，博士研究生；熊国华，高级工程师、博士后、博 士生导师；张兴凯，硕士 本文基于辫群上共轭搜索问题和多重共轭搜索问题的难 收稿日期：２０１０—１１—１３ Ｅ－ｍａｉｌ：ｗｅｉｙｕｎ４５６＠ｓｏｈｕ．ｃｏｍ 第３７卷第１１期 裴俐春，隗云，熊国华，等：辫群上的可转换认证加密方案 １５９ 显然，对任意（ｎ， ）∈ＬＢｎ￣ＲＢ，均有ａｂ＝ｂａ。 定义３对于辫元ｘ，Ｙ∈Ｂｎ，若存在一个辫元ａ∈Ｂｎ使得 Ｙ＝ｎ ｘａ，则称辫元ｘ，Ｙ共轭，记作ｘ～Ｙ。 定义４给定（ ，ｙ）∈Ｂｎ× ，判断ｘ～Ｙ是否成立，称共 轭判断问题（Ｃｏｎｊｕｇａｃｙ Ｄｅｃｉｓｉｏｎ Ｐｒｏｂｌｅｍ，ＣＤＰ）。 定义５给定共轭辫元对（ ，ｙ）∈ＢｎｘＢｎ，找到满足ｙ＝ａ－ ｘａ 的辫元ａ∈ ，称为共轭搜索问题（Ｃｏｎｊｕｇａｃｙ Ｓｅａｒｃｈ Ｐｒｏｂｌｅｍ， ＣＳＰ）。 定义６给定（ ，ａ—ｘｌａ），（ ，ａ ｘｚａ），…，（ＸＮ，ｄ ＸＮａ）Ｅ × ， 求辫元ｂ∈Ｂｎ，满足：ｂ－ｔｘ１ｂ＝ａ １ｘｌａ，口～ｘ２ａ，…，ｂ ＩｘⅣｂ＝ａ－ＩｘⅣａ， 称为多重共轭搜索问题（Ｍｕｌｔｉｐｌｅ Ｃｏｎｊｕｇａｃｙ Ｓｅａｒｃｈ Ｐｒｏｂｌｅｍ， ＭＣＳＰ）。 辫群内元素的乘法和求逆运算都存在快速算法，可以用 计算机编程来实现。对辫群上的共轭判断问题，文献［６】提出 了一种多项式时间算法。但是，尚未有算法能证明可在多项 式时间内求解ＣＳＰ或ＭＳＣＰ。 ３可转换认证加密方案 ３．１系统初始化 假设消息发送者和接收者分别为Ａｌｉｃｅ和Ｂｏｂ。Ａｌｉｃｅ和 Ｂｏｂ共同选择辫群 ，其左、右子群ＬＢｎ、ＲＢｎ，随机元素 ∈ 及抗碰撞的哈希函数Ｈ．：｛０，１｝ ，Ｈ ： ｆｏ，１） 。 Ａｌｉｃｅ随机选择ａ ∈ＬＢ作为自己的私钥，对应公钥为 Ｙ ＝ａＡ ｘａ 。Ｂｏｂ随机选择 ∈ＲＢｎ作为自己的私钥，对应 公钥为Ｙ日＝“ ｘａＢ。 ３．２认证加密 为发送消息ｍ给Ｂｏｂ，Ａｌｉｃｅ执行以下步骤： （１）随机选择ｂ∈ＬＢ，计算 ＝ｂ－１ｘｂ， ＝ｂ－ｉＹ ｂ， ＝ａＡ Ｙ口ａＡ，Ｍ＝Ｈ２（ ）０ｍ，ｈ＝Ｈｌ【Ｍ ｌ】Ｈ２（ ）ＩＩＨ２（ ）。 （２）随机选择ｋ∈ＲＢ ，计算０１＝ｋ－１口： ｈａ ｋ， ＝ｋ １Ｙ ｋ。 （３）将（Ｍ，ｏ， ，Ｏ２）发送给Ｂｏｂ。 ３．３消息认证与恢复 收到（Ｍ， ，０１， ）后，Ｂｏｂ计算： ｈ＝Ｈｌ（Ｍ ｌ ｌＨ２（ ）ＩＩ Ｈ２（“ Ｙ＾口 ）） 通过验证式子 ～ｈ， ～Ｙ 及 ～ 是否成立来对 加密消息Ｍ进行认证。 如果３个式子都成立，Ｂｏｂ通过计算ｍ＝Ｈ：（Ⅱ ｏａ ）０Ｍ 恢复出消息ｍ。 ３．４签名转换 如果Ａｌｉｃｅ事后否认其签名行为，Ｂｏｂ可以通过公开 ＝ Ｙ ｎ 及认证加密消息（Ｍ， ， ，Ｏ２）使得任何第三方都 可以计算ｈ＝Ｈ。（Ｍ ｌｌＨ：（ ）ｌｌＨ （ ），继而通过验证 ～ｈ， Ｏ２～Ｙ 及 ～ｈｘ是否成立来证实签名的有效性。 ４方案分析 ４．１完备性 性质１ Ｂｏｂ可以由认证加密消息（Ｍ， ， ， ）得到认证的 原始消息ｍ。 证明：由口＾∈ＬＢｎ，口 ∈ＲＢｎ可知：ａＡａＢ＝ａｓａ＾， ａ－． ＝ ’，则有： ＝ａＡ Ｙ占ａＡ＝ａａ ａ－， ｘａＢａＡ＝口 ａａ ｘａ＾ａＢ＝口 Ｙ＾ａ口 ｈ＝Ｈ１（Ｍ ｌｌＨ２（ ）ｌ １（ ）＝Ｈ１（Ｍ Ｉ１日２（ ）Ｊ『日（Ⅱ； Ｙ＾ａＢ）） 由 ＝ｋ－ＩａＡ ｈａＡｋ及 ＝ｋ ｉＹＡｋ可知： ０１～ｈ， ～ＹＡ， ＝ｋ １ａｈａ＾ｋｋ～Ｙ＾ｋ＝ ｎ ｈａ＾ａｚ ｘａ＾ｋ＝ｋ－Ｉａａ Ａ ｈｘａ＾ｋ～ Ｂｏｂ由此可以认证加密消息（Ｍ，ｏ， ， ）来源于Ａｌｉｃｅ。 由ａ ∈ＲＢｎ，ｂ∈ＬＢｎ可知： ａｎｂ＝ｂａ ，ｄ ‘ｂ ＝ 一 。 ’ 则有： ＝ｂ－Ｉ Ｙ ｂ＝ｂ－Ｉ口 ｘａ口ｂ＝口； ｂ一’ｘｂａＢ＝ｄ 。ｏａ日 即Ｂｏｂ可通过计算ｍ＝Ｈ：（口； ｏａ ）０ 恢复出消息ｍ。 ４．２安全性 性质２除Ａｌｉｃｅ外，任何第三方无法伪造有效的认证加 密消息（Ｍ， ， ，Ｏ２）使得Ｂｏｂ相信该消息来源于Ａｌｉｃｅ。 证明：由 ＝ａＡ Ｙ ＝Ⅱ Ｙ ａ 可知，任何第三方想产生 有效的认证加密消息，为计算ｈ首先必须求出私钥ａ 或％， 通过对应公钥求解私钥将面临求解共轭搜索问题。如果伪造 发生在Ｂｏｂ公布 ＝ Ｙ ａ 后，第三方为计算０１也必须求出 ，而通过 及Ｙ 求解 将面临求解多重共轭搜索问题。 由共轭搜索问题和多重共轭搜索问题的难解性可知，任何 第三方无法伪造有效的认证加密消息使得Ｂｏｂ相信该消息来 源于Ａｌｉｃｅ。 性质３ Ｂｏｂ无法伪造有效的认证加密消息（ ， ， ， ） 使得第三方相信该消息来源于Ａｌｉｃｅ。 证明：由性质２证明可知，Ｂｏｂ在伪造时须计算 ，即 也必须求ａ 。Ｂｏｂ通过ｙ及Ｙ 求解ａ 也将面临求解多重共 轭搜索问题。因此，Ｂｏｂ也无法伪造认证加密消息。 性质４除Ｂｏｂ外，任何第三方无法获得消息ｍ。 证明：由 ＝ Ｙ ｂ＝ｎ ｏａ 知，任何想恢复消息ｍ的 第三方必须先求出随机元素ｂ或Ｂｏｂ的私钥ａ ，而通过 ＝ｂ １ｘｂ， ＝ｂ １Ｙ ｂ求ｂ将面临求解多重共轭搜索问题， 通过Ｙ 求ａ 将面临求解共轭搜索问题。即使Ｂｏｂ公开 ＝ｎ Ｙ ａ ，第三方通过Ｙ 和 求解ａ 也将面临多重共轭 搜索问题。因此，除Ｂｏｂ外，任何第三方无法获得消息ｍ。 ５结束语 由于满足非交换性，辫群成为构造抗量子攻击密码协议 的新平台。可转换认证加密解决了认证加密中的公开验证问 题，是实现消息安全认证传输的重要手段。本文基于辫群上 共轭搜索问题和多重共轭搜索问题的难解性构造了一个可转 换认证加密方案，为构造基于非交换代数的认证加密方案提 供了思路。 参考文献 ｆ１］Ｓｈｏｒ Ｒ Ｐｏｌｙｎｏｍｉａｌ—ｔｉｍｅ Ａｌｇｏｒｉｔｈｍｓ ｆｏｒ Ｐｒｉｍｅ Ｆａｃｔｏｒｉｚａｔｉｏｎ ａｎｄ Ｄｉｓｃｒｅｔｅ Ｌｏｇａｒｉｔｈｍｓ ｏｎ ａ Ｑｕａｎｔｕｍ Ｃｏｍｐｕｔｅｒ［Ｊ］．ＳＩＡＭ Ｊ． Ｃｏｍｐｕｔｅｒ，１９９７，２６（５）：１４８４—１５０９． ［２１ Ｋｉｔａｅｖ Ａ．Ｑｕａｎｔｕｍ Ｍｅａｓｕｒｅｍｅｎｔｓ ａｎｄ ｔｈｅ Ａｂｅｌｉａｎ Ｓｔａｂｉｌｉｚｅｒ Ｐｒｏｂｌｅｍ［ＥＢ／ＯＬ］．［２０１０—０５・２０］．ｈｔｔｐ：／／ａｒｘｉｖ．ｏｒｇ／ｑｕａｎｔ—ｐｈ／９５１１０２６． ［３１ Ａｎｓｈｅｌ Ｉ，Ａｎｓｈｅｌ Ｍ，Ｇｏｌｄｆｅｌｄ Ｄ．Ａｎ Ａｌｇｅｂｒａｉｃ Ｍｅｔｈｏｄ ｆｏｒ Ｐｕｂｌｉｃ Ｋｅｙ Ｃｒｙｐｔｏｇｒａｐｈｙ［Ｊ］．Ｍａｔｈｅｍａｔｉｃａｌ Ｒｅｓｅａｒｃｈ Ｌｅｔｔｅｒｓ，１９９９，６（３）： ２８７—２９１． ［４］Ｐａｅｎｇ Ｓ Ｈ，Ｋｗｏｎ Ｄ，Ｈａ Ｋ Ｃ，ｅｔ ａ１．Ｉｍｐｒｏｖｅｄ Ｐｕｂｌｉｃ Ｋｅｙ Ｃｒｙｐｔｏｓｙｓｔｅｍ Ｕｓｉｎｇ Ｆｉｎｉｔｅ Ｎｏｎ—ａｂｅｌｉａｎ Ｇｒｏｕｐｓ［ＥＢ／ＯＬ］． ［２０１０－０５—２０１．ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２００１／０６６． （下转第１７５页）