群论应用举例.doc

组合群论在密码学和电子商务组合群论在密码学和电子商务 的安全性中的应用的安全性中的应用 目录目录 第一章第一章 密码学和电子商务的安全性密码学和电子商务的安全性 1 第一节 密码学概述 1 第二节 电子支付系统的安全性 4 第二章第二章组合群论和密码学组合群论和密码学 4 第一节 基础知识和背景 4 第二节 密码体制和密钥交换协议 7 2 2 1 Wag84 公钥密码体制 7 2 2 2 Anshel93 密码体制 9 2 2 3 Anshel Anshel Goldfeld 密钥交换协议 9 2 2 4 Ko Lee Cheon 密钥交换协议和密码体制 11 第三章第三章组合群论在电子支票的多签名体制中的应用组合群论在电子支票的多签名体制中的应用 14 第一节 三方密钥交换协议 14 第二节 基于辫群的多签名体制方案 15 3 2 1 多签名介绍 16 3 2 2 基于单向环同态的多签名体制 17 3 2 3 基于辫群的多签名体制 18 第一章第一章 密码学和电子商务的安全性密码学和电子商务的安全性 第一节第一节 密码学概述密码学概述 信息安全是密码学的基本要求 为了要达到这一点 密码学始终涉及两 个方面的斗争 其中一方 发送者 是设法对消息进行加密 使得只能是具有 特殊权利的人 接受者 才能够接受和阅读信息 而另一方则是尽力设法截获 信息 破译密文 或者用修改以后的假信息欺骗接收者 在本文中 我们主要讨论的是前一方 即考虑用何种方法能够对消息进行 安全 有效且快捷的加密 保证消息的传送 待加密的消息被称作明文明文 plaintext 用某种方法伪装消息并隐藏它的内 容的方法称作加密加密 encryption 被加密以后的消息称为密文密文 而把密文转变成 明文的过程称为解密解密 加密体制中的加密运算是由一个算法类组成 这些算法 类的不同运算可用不同的参数表示 不同的参数分别代表不同的算法 被称作 密钥密钥 密钥空间密钥空间是所有密钥的集合 密码体制密码体制一般是指密钥空间与相应的加密 运算结构 同时还包括了明文和密文的结构特征 在密码体制的设计和评价中 要考虑到以下一些基本原则 1 不可破原则 指该密码体制在理论上或实际上是不可破解的 2 部分信息丢失不会影响整个系统的安全性 即硬件设备 加密算法 或全部密文与部分明文这些信息的丢失不会危及整个系统的安全 3 与计算机 通信系统匹配原则 要求密码系统不是独立存在的 而 可以在计算机或通信系统中使用 密码体制发展到现在 已经有了很多种不同的类型 但是从密码体制所 使用算法的分类上说 可以分为两种 一种是利用了对称算法 又称作传统密 码算法 另一种则是利用了公开密钥算法 对称算法对称算法是指加密密钥和解密密钥 能够互相推算出来 公开了一个也就相当于公开另一方 因此对称算法的密钥 只能由发送者和接收者两方知道 他们必须事先商定好密钥 这一点就涉及了 密钥交换协议 公开密钥算法公开密钥算法是指公开了加密算法以后不会泄露解密算法 因此 K E K D 和对称算法相比 任何人都可以通过公开渠道 网络或密钥管理中心 已知他 人的加密密钥 把明文加密以后传送给接收者 而只有拥有解密密钥的人才 K D 能够对密文解密 这在密钥管理和消息的传送方面更具有优势 另外 公开密 钥算法还可以运用在数字签名中 在目前应用于实际生活比较广泛的公钥加密算法包含有 RSA 密码体制和 椭圆曲线密码体制 RSA 密码体制 密码体制 1979 年 Shamir Rivest 和 Adelman 提出了第一个也是应用最广的公钥 密码体制 即 RSA 体制 经过 20 多年的密码分析和攻击 迄今为止 RSA 被 证明仍是安全的 设 n pq p 和 q 是两个大素数 a 和 b 是两个整数 定义密 钥空间为 把 n b 作为公开密钥 而 1 mod n p q a bnpq abn p q a 作为秘密密钥 整个加密算法就是 y 而解 n mod b K Exxn 密算法是 由 Euler 定理知道 成立 上述解密的方 mod a K Dyyn K xDy 法正确 由于 RSA 加密算法是指数运算 因此当密钥越大时 计算速度越慢 RSA 算法比通常的 DES 算法慢了 1500 倍 并且 RSA 的计算量很大 为了要达 到较高的安全程度 RSA 的密钥位数比其它的密码体制大的多 现在一般需要 1024 位的密钥 所以一般对速度要求较高的数字签名或智能卡中的身份验证不 太使用 RSA 密码体制 而采用其它较快的算法 椭圆曲线密码系统就是其中的一种 椭圆曲线密码系统 椭圆曲线密码系统 椭圆曲线密码体制和 RSA 体制比较起来 所需要的密钥量小 安全程度 高 比如 RSA 密码体制需要 1024 bit 的密钥才能达到的安全程度 利用椭圆曲 线只需要 160 比特位的密钥就能够保证同样的安全 文献 密钥长度的减少 同时带来了计算速度的提高 即使是在剩余类环运用离散对数而构造的加密 P Z 系统的安全程度也要低于椭圆曲线 因此椭圆曲线系统不愧为一个性质较好的 密码系统 椭圆曲线第一次运用于公钥密码算法是在 1985 年 Neal Koblitz 和 V S Miller 提出来的 他们并没有提出新的算法 只是把椭圆曲线运用到已存在 的公钥密码算法中 比如说 ElGamal 加密算法 利用 ElGamal 思想构造的椭圆 曲线密码体制如下显示 首先是产生密钥阶段 Bob 从中随机选取充分大的整数 随后计算 n Z B k 出椭圆曲线上的点 P 是椭圆曲线上的适当的一点 将保密 作为 B k QQ B k 秘密密钥 并将 P 公开 作为公钥 加密方法如下 如果 Alice 想把消息 M 同样是椭圆曲线上的一点 发 送给 Bob 就从中随机选择整数后 计算出和的值 n Z n lZ 1 SlQ 2 SMlP 加密以后的信息就是椭圆曲线上两点 12 S S 解密 Bob 收到加密信息后 通过密钥就可以计算 M 12 S S B k 2 S B k 得到消息 M 1 S 纵观上面提出的两个公钥密码体制 再加上其它的密码系统 在加密的 时候都采用了单向函数的思想 单向函数单向函数是指函数满足从 x 计算容易 f f x 但从计算 x 有可能不可行 单向函数的构造依赖于计算复杂度理论 即利 f x 用一些困难问题 上述两个系统的安全性都依赖于一些数论中的基本困难问题 比如说 RSA 体制利用了把大整数 n 分解为两个大素数的难度 而椭圆曲线是利 用了求解离散对数问题的困难程度 即根据 P 和 Q 求解中整数 B k Q n Z B k 这些密码体制都是很成功的 在实际中也有了进一步的应用 对于本文来说 我们的主要目的是把组合群论的思想引进到密码学中 所以利用了组合群论中 的一些困难问题 如字问题 共轭问题等等 由此构造出新的密码体制 协议协议 protocol 是指一系列的步骤 它包括两方或者多方 设计它的目 的是要完成一项任务 密钥交换协议密钥交换协议 key exchange protocol 是指两人或多人之 间通过一个协议取得密钥并用于进一步的加密算法中的方法 在实际的密码世 界中密钥交换其实是很重要的一个环节 比如说利用对称加密算法 如果双方 没有约定好密钥 就必须再进行密钥交换 但是如何使得密钥到达接收者和发 送者手里是件很复杂的事情 最早利用公钥密码思想提出的密钥交换协议有 Difffie Hellman 算法 新的密钥交换协议有利用组合群论中的辫群构造的两 n B 个协议 Anshel Anshel Goldfeld 协议和 Ko Lee Cheon 协议 第二节第二节电子支付系统的安全性电子支付系统的安全性 电子商务作为新兴事务 已经随着计算机和网络技术的成熟得到了飞速发 展 而且使得商家的整体经营方式都有了变化 电子商务是以数字化的电子方 式 以网络为媒体进行的商业数据交换或其他商业活动 电子商务的一个重要 组成部分就是电子支付系统 电子支付是指交易的各方是通过电子手段 比如 说银行的电子存款系统和电子清算系统来记录和转移资金的方式 一个安全 可靠的电子支付系统是电子商务的交易活动能够正常进行的保证 目前 INTERNET 上的电子支付系统主要有四种 信用卡 IC 卡 电子现金 e Cash 和电子支票 e Check 一般来说 电子支付系统必须满足以下的安全 性要求 包括有消息的保密性 能够确认双方都具有合法的交易身份的能力 保证交易完毕以后的信息是无法修改的和交易以后各方对业务的不可否认性 作为电子支付系统的不同代表 电子现金和电子支票虽然有一定的共性 但在 安全性要求和性质方面有着各自独特的特点 电子支票和纸张支票转移支付的原理类似 是利用数字传递将钱款从一个 账户转移到另一个账户的电子付款方式 在电子支票实现的过程中 它的安全 性问题是 如何保证银行 用户 商场对电子支票进行签名的有效性 由于转 账在银行 用户和商场三方进行 在每一次交易完成以后都必须对消息签名 用来保证交易信息的真实 完整和不可否认 所以在交易过程中将会涉及到数 字多签名 在本文中 我们最后讨论了一种利用辫群构造的多签名体制 可以 把上述多签名运用到电子支票转账系统中去 电子现金是一种以数据形式流行的货币 因此和支票相比 电子现金更强 调满足隐私性和可分割性 另外 虽然要保证用户的隐私权 电子现金出于安 全性的考虑 还需要满足电子现金的不可伪造性和不可重用性 如果同一份电 子现金被使用两次 使用者的身份就可以被发现 关于电子现金 现在最主要 讨论的是它的可分性的实现 第二章第二章 组合群论和密码学组合群论和密码学 第一节第一节 基础知识和背景基础知识和背景 自从 1984 年 N R Wager 和 M R Magyarik 在 中提出了第一个用组合群论 的理论构造公钥密码体制的方法以来 在密码学家们的共同努力下 利用组合 群论的理论已经提出多个公钥密码体制和密钥交换协议 由于组合群论中的数 学工具和以前数论中的内容截然不同 有必要对组合群论中的一些定义和定理 加以说明 从而可运用到密码学中去 得到不同的加密算法 群 G 称作是有限生成的有限生成的 finitely generated 如果 G 存在有限个生成元 满足 G 中任意一个元素 又称为字 都可以表示成生成元和它们 1 2 g g n g 的逆的有限乘积 群 G 称作是可以有限表示的可以有限表示的 finitely represented 如果在 G 中有有限个 元素 满足在群 G 中 其中 e 是单位元 1 r 2 r k r 1 re 2 re k re 那么 称为 G 的生成元 的一组定义关系 1 r 2 r k r 12 g g n g 换一种角度 如果把群 G 看成是 n 个元素 生成的自由群X 12 a a n a 的商群 即存在的正规子群 使得成立 那么 G 是可以F X F X N F X G N 有限表示的意思是 如果 对应 F X 中的元素 那么 1 r 2 r k r 1 w 2 w k w 是 F X 的正规子群 N 的生成元 12 w w k w 可以有限表示的群 G 可表示为 G 2 1 g g n g 12 r r k r 辫群是一种有限表示的群 的生成元是 它的生 n B n B 1 2 1n 成关系满足 时 当 11 ijij e 2ij 当 111 ijijij e 时 因此 辫群可以表示为 1ij n B n B 121 1 2 ijijij n ijji ij ij 当 当 组合群论中有些基本问题相对于某个特定的群是困难问题 可以作为构造 公钥密码体制的基础 例如第一个公钥密码体制 Wag84 就是根据不可解的字问 题所构造的 而随后的 Anshel93 等主要运用了组合群论中的共轭问题 字问题字问题 word problem 是否存在一个算法来判断群 G 中的元素是不是单位 元 一个问题是算法上可解的算法上可解的 algorithmically solvable 是指存在一组计算机程序 通过计算 对该问题的结果是 是 或 否 做出明确的回答 如果不存在这 样的程序 就称这个问题是算法上不可解的算法上不可解的 algorithmically unsolvable 关于字问题对于某些群是否是算法上不可解的 Novikov Boone 定理 见 对此做出了肯定的回答 定理中利用了有限表示的群 这也是用字问题作 为困难问题构造加密算法的基础 Novikov Boone 定理 定理 存在有限表示的群 G 有着算法上不可解的字问题 并且存在有效的算法 B 如果输入有限表示的一个系统 T 且该系统有着不可 解的字问题 通过算法 B 将会输出有限表示的群 B T 使得 B T 有着算法上不 可解的字问题 第一次提出利用组合群论的思想来构造的 Wag84 密码体制就利用了 Novikov Boone 定理 共轭问题共轭问题 conjugacy problem 是否存在算法来判断群 G 中给定的任意两个 元素是共轭元素 所谓两个元素 x y 共轭是指 存在 G 中元素 w 使得 成立 1 yw xw 关于组合群论中是否存在群有着算法上不可解的共轭问题 同样可由一个 定理加以保证 在该定理中 所涉及的群是剩余有限群 一个群 G 被称为是剩剩 余有限余有限的 residually finite 如果给定了群中任意一个元素 g 都存在gG e G 的正规子群 使得 g 不是中的元素 g NG g N 运用剩余有限的群 Miller 证明了具有算法上不可解共轭问题的群的存在 性 这就是 Miller 定理 Miller 定理定理 存在有限表示且剩余有限的群 其共轭问题是算法上不可解 的 并且存在快速算法 C 使得输入一个有限表示的群 G G 的字问题不可解 后会输出有限表现且剩余有限的群 C G C G 有着不可解的共轭问题 Miller 定理是 1993 年 Iris Lee Anshel 和 Michael Anshel 提出的基于不可解 的共轭问题而构造的公钥加密体制的理论基础 辫群在组合群论应用于密码学中扮演了重要的角色 在 1999 年 n B I Anshel M Anshel 和 D Goldfeld 提出的密钥交换协议和 2000 年 Hyoung Ko Sang Jin Lee 和Jung Hee Cheon 提出的密钥交换协议和加密算 法中 他们都利用了辫群的共轭问题 这是因为辫群的一些重要性质可以很好 的利用到密码体制中去 辫群的定义在前面已经提到过了 但是辫群除了可以用有限生成元表示出 来以外 还有着其独特的几何意义 辫群中每一个元素都对应了两条平行直 n B 线间的 n 股线 每一股线的两个端点开始于上面的平行直线 并中止于下端对 应平行直线 下面的两幅图对应于中的生成元和 如图一对应于 n B i 1 i i 图二对应于 1 i 1ii 1 n 图一 1 1ii 1 n 图二 辫群中的两个元素 a b 相乘在几何上对应了把两个辫群的图像拼接起来 另外 中两个元素相等从几何上来说 是指 a b 两个元素对应的图案能够 n B 在三维空间中从一个图像连续的变动到另一个 根据文献 辫群有一些性质特别适合密码学的要求 用来构造公钥 密码体制 辫群的元素可以通过标准形式 canonical form 来统一表示 即由 p 1 个参量 表示 u 是整数 代表了一个 n 阶置换 该表示是唯 12 u p i 一的 辫群内元素的乘法和求逆都存在快速算法 可以用计算机编程计算 并 且辫群中有很多的困难问题可以作为构造密码体制和密码交换协议的基础 比 如说辫群的共轭问题就是困难问题 第二节 第二节 密码体制和密钥交换协议密码体制和密钥交换协议 2 2 1 Wag84 公钥密码体制公钥密码体制 1984 年 N R Waner 和 M R Magyarik 利用了有限表示群的不可解的字问题 构 造了第一个以组合群论思想为基础的公钥密码体制 由前面的 Novikov Boone 定理可知 存在群满足不可解的字问题 这是 Wag84 公钥密码体制成立的基础 下面是整个加密算法 取 G 是有限表示的群 有着不可解的字问题 G 可以表示为 12 Ga a n a 12 1 1 1 m uuu 利用一个秘密同态函数 A 可以是大的有限群或者是有限表 h GA 示的群 它的字问题有着快速的解法 在群 G 中取两个字和 使得这两个 0 y 1 y 字满足 把群 G 和公开 作为公钥 而把同态函数保密 01 h yh y 0 y 1 yh 作为秘密密钥 加密算法很简单 只要将消息 M 写成二进制数的形式以后 每个 0 bit 位 由随机选择的代替 只要满足 意思是指和是 G 中同一 0 y 00mod yyG 0 y 0 y 个元素的不同表现形式 同理 1 bit 位用代替 这样的话 1 y 11mod yyG 消息 M 中的每个比特位都有 G 中的元素来表示 从密文中任取 G 的一个元素 z 由于 G 有着不可解的字问题 即无法利用算法判断和中哪一个是 1 0 zy 1 1 zy 单位元素 因此 加密是成功的 解密时需要运用解密密钥 h 在密文中取元素 z 只要 h z h 说明 z 代 0 y 表的比特位是 0 反之是 1 因为在 A 中字问题是可解的 上面的结果可以判 断 因此消息被解密 对于以上的利用组合群论所构造加密算法的讨论 首先它需要找一个合适的具有不可解的字问题的群 要使加密算法适合实 用 必须使群里的元素应该在群中有唯一的标准表示 通过计算机很容易进行 存储和计算 即使是这样 原文中一个比特位的 0 或者 1 经过转化成密文以后 需要用群的一个元素来表示 而群中元素在计算机的传输和存储的方面 所需 要的存储量远远大过比特位 并且在密文处理方面有很多的不方便的地方 比 如说如何选择和 Y0或者 Y1等价元素 有没有快速算法等等 这些缺点都降低 了效率 所以总的来说 这只是一个不太成熟 不能实用的方案 但毕竟 它 在把组合群论利用到密码学中开创了新的一步 2 2 2 Anshel93 密码体制密码体制 接下来由文献 在 1993 年 M Anshel 和 I Anshel 继续了利用组合群论 中的问题提出了另一个新的加密算法 与前一个有所不同的是 这次他们所采 用的群是有限生成的群 群中元素具有不可解的共轭问题 并且群是剩余有限 群 在他们所提出的方案中 需要用到前面提到的 Miller 定理作为保障 G 中任意的一个元素 g 存在从 G 到有限群的一个同态 满足 1g 任取 G 中一个元素 存在 G 的正规子群 使得不是中的元素 在w W Nw W N 群 G 中 记 z 为单位元素 由于 G 是剩余有限的 存在一个有限群 可 W G N 考虑同态 H G G 因为不属于 由此 由于 W Nw W N 1H w 1H z 和不是共轭元素 而同态运算保持共轭性质不变 和 z也不是共 H w H zw 轭元素 把同态运算 H 保密 并假设在商群中 求解共轭问题和字问题 W G N 在算法上是多项式内实现的 在加密问题上 Anshel 所采用的方法与前文类似 那就是把 1 用任一与 z 共轭的元素代替 把 0 用与共轭的任一元素代替 用w 这个方法 可随机地把明文中的二进制数字转化成密文中组合群中的元素 而 通过保密的同态加以解密 最终得到原文 wag84 和 Ansh 93 从设计的思想上来说 是基本上类似的 它们都是设法利 用组合论中有特定性质的群 即有着不可解的字问题或是共轭问题 以群中两 类不同的元素分别代表 0 和 1 两个数字 同时均将一个同态映射做密钥保存 只要知道了所选用的群和两个代表 0 和 1 的群元素就可以对消息进行加密 作 为密钥的同态运算所对应的群的字问题和共轭问题则是可解的 它们的差别是 wag84 所选用的群是以字问题做为困难问题 而 Ansh93 是把共轭问题做为困 难问题 两者的区别是群选择的不同 2 2 3 Anshel Anshel Goldfeld 密钥交换协议密钥交换协议 1999 年的时候 不同于以上的几个公钥密码系统 在组合群论的基础上 I Anshel M Anshel 和 D Goldfeld 提出了一个新的密钥交换协议 见 和 该协议中所采用的群是辫群 具有不可解的共轭问题 但是辫群的字问题可以 在多项式时间内解决 在协议中 Anshel99 利用换位子的思想 XYX 1Y 1 其 中 X Y 均为辨群中的元素 其中 XYX 1Y 1可以看成是 Y 的共轭元素和 Y 1 n B 相乘得到 或者可以看成是 X 和 X 1的共轭元素相乘得到的 具体的密钥交换 步骤如下 两方 Alice 和 Bob 分别公布字 a 1 a 2 a n b 1 b 2 b m 这些字均从群 G S D 得到 其中 S 是生成元 D 是定义关系 Alice 和 Bob 之 间的密钥由它的共同的行为产生 Alice 和 Bob 同时执行以下的步骤 一起产生 秘密密钥 1 Alice 首先进行如下运算 Alice 选择一个群 G 中的由 a 1 a 2 a n 生成的秘密的字 X 对每一个 b i 进行共轭运算 产生 m 个新字 c 1 c 2 c m c i X b i X 1 2 Alice 对每一个进行改写 写成 B i 的形式 B i 和 是G 中同一c i c i 个元素的不同表示 i 1 m B i 能够完全掩盖住中有关 X 的秘密信c i 息 由于 B i 和 b i 是关于 X 的共轭元素 但不能从 B i 中推断出 X 是什么 G 有着不可解的共轭问题 X 是不可知的 3 Alice 通过公开的渠道把 B 1 B 2 B m 传送给 Bob 在 Alice 进行计算的同时 Bob 进行类似的计算 1 Bob 从 b 1 b 2 b m 生成的 G 的子群中 选择一个秘密的元素 Y 用每个 a i 进行共轭等 产生d 1 d 2 d n d i Ya i Y 1 2 对每个d i 进行改写 写成 A i 的形式 使得 A i 和d i 表示相同的元素 3 Bob 把 A 1 A 2 A n 传送给 Alice 第三步 Alice 和 Bob 可根据所得的结果分别计算出换位子 X Y XYX 1Y 1 因为 Alice 可以从 V X YXY 1 1 Xx A 1 A n 1中 计算 如果 X x a 1 a n 并且 Bob 也可以计算换位子 W XYX 1 Y 1 y B 1 B 2 B m Y 1 如果 Y y b 1 b n X 由 a 1 a 2 a n 生成 仅为 Alice 所知 而 A 1 A 2 A n 是 a 1 a 2 a n 关于 Y 的共轭元素 通过类似的计算 Alice 可以知道 YXY 1 Bob 也是可以 由秘密的 Y 以及 Alice 传送给它的 B 1 B 2 B m 来得到 XYX 1 但是 对于 Alice 所掌握的字 X 一无所知 当 Alice 和 Bob 经过计算出 V 和 W 以后 V 和 W 是同一个字的不同表现形式 从字 V 和 W 得到 Alice 和 Bob 的共同的 密钥有两个方法 第一个是辫群 G 中的每个元素都有且仅有一种唯一的特殊表 现形式 称作经典形式 那么把 V 和 W 都写成经典形式之后 这时它们的标 准形式是相同的 然后可以定义从辫群的标准形式到二进制数的单向函数 H 从而使密钥 K H V H 第二个方法是把 G 作为群作用在某个集合 S 上 并且满足 E S SG1 G2 S G1G2 S G1 G2属于 G E 是 G 的单位元 且 G 内不同的字作用到 S 上的元素 S 所得的值也是不同的 在 这种条件下 密钥 K V S W S 也同样可以得到 对 Anshel Anshel Goldfeld 密钥交换协议的分析 首先我们不知道 上述的密钥交换协议的安全性是否以辫群共轭问题的难 解程度为基础的 但是 实际上已知 XYX 1和 Y 求解 X 的问题和已知 XB 1 X 1 XB 2 X 1 XB M X 1和 B 1 B 2 B M 的值 来求解 X 的困难程度是不一样的 显然后一个问题比前面的问题要容易的多 后一个问题所面临的困难问题是不同于标准形式的共轭问题 我们可以把它称 之为新的共轭问题 MSCSP 应该说这个也是从算法上来说不可解的 另一 点是 Anshel Anshel Goldfeld 密钥交换协议所利用的辫群中密钥的共轭运算的同 态性质 即 XA 1 X 1XA 2 X 1 XA 1 A 2 X 1 以及 XYX 1 1 XY 1X 1但是在 Alice 和 Bob 对 X Y 进行改写 并使得从 XB 1 X 1 XB M X 1或 YA 1 Y 1 YA N Y 1中不能得出 X Y 的值 的时候 通过改写 即把上述这些辫群里的元素写成标准形式时 并不能够保 证所有的标准形式能完全掩盖住秘密信息 但是只要有一个元素泄露出 X 或者 Y 的值 那么密钥就可以被破解 所以 X B1 X 1 XB M X 1和 YA 1 Y 1 YA N Y 1中的秘密信息必须完全被改写掉 2 2 4 Ko Lee Cheon 密钥交换协议和公钥密码体制密钥交换协议和公钥密码体制 从上述的密钥交换协议可以看出 上述的协议的主要思想是利用组合群论 中的一般理论 关于换位子的思想适用于任何一个群 只是在具体的实现方法 上 才使用了辫群 因为辫群在实现过程中 有一些较好的优点 比如有唯一 的标准形式 并且它的字问题有着快速算法 而共轭问题是困难问题等等 应 该可以看出 任何具有类似性质的群都可以做为构造 Anshel Anshel Goldfeld 密 钥交换协议的群 下面所提到的 Ko Lee Cheon 密钥交换协议则是更立足于辫 群本身的性质 文献 因此在讨论密钥交换协议的时候 对于密钥交换协议 的安全性分析将更加成熟一点 并且能够相对比较实用 韩国学者 Hyoung Ko Sang Jin Lee 和 Jung Hee Cheon 提出 在辫群中有 一些问题属于困难问题 其中能够适用于构造密钥体制的有以下一些 假设是由 生成 由 生成 m n n B 12 1n m B 12 1m 那么 辫群可以看成是的子群 那么有以下几个问题是困难问题 m B n B 1 普通的寻找共轭元素问题 GCSP 元素 X Y 并且 Y BXB 1 其中 B m n nm BB n B 问题 寻找 A 使行 Y AXA 1成立 m B 2 共轭元素分解问题 QCDP X Y 满足 Y BXB 1 B m n nm BB m B 问题 寻找 满足 A A m B YA XA 3 寻找 P 次根问题 X Y 满足 Y XP X nn BB n B 问题 寻找 Z 满足 Y ZP n B 在上述几个问题的基础上 Hyoung Ko 等提出了密钥交换协议 上述协议 所利用的是第一个困难问题 在中取两个群 和 是由 n B l LB r RB l LB 1 生成 而由 生成 由于辫群的生成元满足条件 2 1l r RB 1l 1l r 因此对于任意的 A B 都能满足 ijji 2ij l LB r RB AB BA 所以辫群中的子群和 之间的任意两个元素具有交换性 n B l LB r RB 这是能否满足密钥系统的关键 密钥交换协议的具体实现如下 1 首先选择充分大并且较合适的两个整数 L R 以及辫群 和 n B l LB 在中选择一个比较合适的元素 X 并将 X 公开 r RB n B 2 密钥交换者 Alice 和 Bob 分别执行以下步骤 A Alice 从中任意选择一个秘密元素 A 把 Y1 AXA 1 传送给 l LB Bob B Bob 从中选择一个元素 B 并将 Y2 BXB 1传送给 Alice r RB C Alice 收到 Y 以后 计算 K AY2A 1 D Bob 收到 X 以后 计算 K BY1B 1 由于 AB 是交换的 即 AB BA 所以 A 1B 1 B 1A 1并且 AY2A 1 A BXB 1 A 1 B AXB 1 B 1 BY1B 1 因此 Alice 和 Bob 两人得到的密钥 是相同的 值得注意的是 在密钥交换协议中利用的困难问题和普通的寻找共轭元素 问题 GCSP 不完全是等价的 但是两者之间有紧密的关系 关于这一点 有 点类似于 Diffie Hellman 的密钥交换协议 因为 Diffie Hellman 协议中就是由已 知 GX和 Y 以及 GX X 中分别得到 GXY 但是这个问题可以归结为求解离散对 数的问题 在辫群的协议中 也是类似的 窃听者即使能够知道 AXA 1 B 和 BXB 1和 A 但要计算 ABXA 1B 1 还是会归结为求解共轭元素的问题 虽然 Anshel99 也是利用了辫群的共轭算法 但在这一点上和韩国学者提出是的不一 样的 与密钥交换协议非常相似 Hyoung Ko 等同时利用辫群可以构造一个新 的公钥密码体制 运用到的方法和上面基本一致 只是需要增加一个散列函数 首先定义一个从辫群元素到二进制数字的单向散列函数 H 0 1 K l r B 1 产生公钥及私钥阶段 A 从中选择一个适当的 由 生成的 X l r B 12 1l r B 取中元素 A l LB C 设 Y AXA 1是 X 关于 A 的共轭 把 Y 公开 当做公钥 并且使 A 保 密 当作私钥 2 加密运算 如给定明文 M 0 1 K和 X Y 以后 A 任意从中选择元素 B r RB B 加密以后的密文是 C D C BXB 1和 D H BYB 1 M 3 解密通过计算 M H ACA 1 D 可得 上面这个步骤的原因是因为 ACA 1 ABXB 1A 1 BA XA 1B 1 BYB 1 因此 H ACA 1 D H BYB 1 H BYB 1 M M 代表了异或运算 这个新的加密算法和密钥交换协议的理论基础相同 并且比较实用 第三章第三章 组合群论在电子支票的多签名体制中的应用组合群论在电子支票的多签名体制中的应用 第一节第一节 三方密钥交换协议三方密钥交换协议 考虑将两方的密钥交换协议推广到三方或者更多的人中去 就必须利用 协议本身的性质 关于 Anshel Anshel Goldfeld 密钥交换协议 因为协议中利 用了换位子 很难推广到多方中去 但是 Ko Lee Cheon 协议采用了 11 XYX Y Diffie Hellman 算法的思想 因此可以稍做修改 使参加协议的人增加到三人 或者多人 下面就是具体的三方协议 首先可在辫群中取三个子群 和 由 生 l LB k MB r RB l LB 1 2 1l 成 由 生成 由 生成 其中 k MB 1l 1l k r RB 1l k 1l k r l k r 满足条件 l r k n 利用辫群中生成元的性质可知 任意 a l LBb 都满足 这就是说 群 k MBc r RBabba bccb acca l LB 和中任意元素都是可以交换的 和两方协议类似 Alice Bob 和 k MB r RB Carol 执行以下的步骤 1 Alice Bob 和 Carol 共同选择一个恰当的辫元 x n xB 2 Alice 从中随机选择辨元 把发送给 Bob l LBa 1 1 xaxa 3 Bob 从中任意选择辫元 把发送给 Carol k MB k bMB 1 2 xbxb 4 Carol 从中任意选择 把发送给 Alice r RB r cRB 1 3 xcxc 5 Alice 把发送给 Bob 1 13 yax a 6 Bob 把发送给 Carol 1 21 ybxb 7 Carol 把发送给 Alice 1 32 ycx c 8 Alice 计算密钥 1 3 kay a 9 Bob 计算密钥 1 1 kby b 10 Carol 计算密钥 1 2 kcy c 由于 三个元素有交换性 因此有以下等式成立 abc 111111111 32 ay aa cx caac bxbc aabcxc b a 和 111111111 123 by bb acxc ababcxc b acy cay a 可知为 Alice Bob Carol 三方的共同密钥 因为这个三方协议和 Diffie k Hellman 协议类似 由 Diffie Hellman 协议的安全性可知 上述协议是安全的 它的困难程度基于在辫群中破解共轭问题的难度 另外 出于安全性的考虑 由文献 7 中对满足条件的辫元所加的限制条件可知在上述协议中 不能取xx 成的类型 其中 而 z 是中能够和 123 a a a z 1l aLB 2k aMB 3r aRB n B l LB 和中元素都交换的辫元 因为如果 密钥 k 满足条件 k MB r RBx 123 a a a z k 111 abcxc b a 111 123 aa a ba b ca c z 又因为 通过公开 1 1123 xaa aa a z 1 2123 xa ba ba z 1 3123 xa a ca cz 传输的 和就可以计算得到 从而计算出密 1 x 2 x 3 xx 1 1 aa a 1 2 ba b 1 3 ca c 钥 因此 应该选择适当的 x 满足安全性的要求 不过有一点比较有利的是 同样是在文献 7 中对 x 的讨论中 上述 x 出现的概率非常小 一般不用多做考 虑 第二节第二节 基于辫群的多签名体制方案基于辫群的多签名体制方案 3 2 1 多签名介绍多签名介绍 利用公开密钥算法对一段消息进行数字签名 这是签名方案中最常用的一 种方法 它在理论上发展的已经比较完善 在实际应用中也有成熟的体制 比 如说由 RSA 加密算法转化而成的数字签名 ElGamal 签名方案 Schnorr 签名 算法 经过改进的 Fiat Shamir 签名方案以及 Guillon Quisquater 数字签名方案等 等 这些数字签名的安全性或是建立在大整数分解的难度上 或是建立在计算 离散对数的难度上 或是利用其他数论中的困难问题 不过这些方案都有一个 特点 这些数字签名只是单个人对一份文件的签名 很少有签名方案可以拓展 到多个人对同一份文件的签名上去 即使有 也只是简单的通过单签名加以迭 代而得到的 但是由于实际应用的需要 对签名人数提出了更高的要求 现在 需要一种新的签名方案 可以使多个人对同一份文件进行签名 这就是多签名多签名 多签名有着广泛的应用 比如说一份文件必须有多个人签署才能执行 缺乏了 其中任意一人的同意就不可以 或者是电子支票在银行 客户 商店之间转账 时 银行 客户 商店为了使转账过程得以纪录 在每次交易时对同一份文件 支票进行数字签名 也需要利用多签名的技术 这些应用使得数字多签名 方案的发展成为一种必然 为了满足着一要求 密码学家利用数学理论也构造 了一系列多签名方案 其中比较实用且计算速度较快的是日本学者 Eikoh Chida Tako Nishizeki 等基于单向环同态所构造的多签名方案 在本文中 除 了介绍他们的多签名体制以外 我们还考虑利用辫群中的困难问题对基于单向 环同态而构造的多签名方案进行改进 提出把组合群论思想和多签名方案结合 起来 提出一个新的多签名方案 数字多签名的安全性要求 数字多签名的安全性要求 多签名方案由于签名过程涉及了多个人 并且签名完成以后要求能检验所 有人对同一消息的签名 所以在安全性方面比一般的数字签名有着更高的安全 性要求 首先要求多签名能够抵抗外部攻击 3 2 2 基于单向环同态的多签名体制基于单向环同态的多签名体制 在文献 中 Eikoh Chida Tako Nishzeki 等首先提出了问题 在代数结构 中除了群中存在单向群同态函数 即函数既是单向函数 也满足群中的同态运 算 以外是否还有其它的单向函数同态 比如在环 幺半群中等 实际上 以 前所构造的 RSA 加密算法 离散对数算法都是利用了基于单向群同态的单向陷 门函数 而环同态对于这个问题的肯定回答 他们是构造了一个单向环同态来 实现的 如果 A 是交换环 R A U 是在加法 下的 A 模 对于任意 A 和 U 直和 AU 内的元素和 可定义AU 中的加法 11 a u 22 a u AU AU AU 和乘法 AU AU AU 如下 可以 11 a u 22 a u 1212 aa uu 11 a u 22 a u 121 122 aa aua u 证明所得的 AU 是交换环 利用这个交换环 Eikoh Chida 等有进一步证明了单向环同态的存在性 这 可以表述为下面这个定理 定理 定理 U V 都是有限交换群 n 如果 U 和 V 内二进制运算是多项U 式内可计算的 如果存在单向群同态函数 UV 那么存在单向环同态 F f F 的定义是 F Im nn ZUZf n x n f x 为了构造适当的多签名体制 文献 中利用了上的同态函数 1P Z f g 是的生成元 这个函数是单向的 运用上 1PP ZZ mod x f xgp P Z 面的定理 可以得到单向环同态函数 F 11 PPPP ZZZZ 关于文献中有根据上述函数而构造的多签名体制 在此不再 x F n xn g 详述 3 2 3 基于辫群的多签名体制基于辫群的多签名体制 如果要把辫群应用到构造单向环同态中 就必须考虑辫群的很多基本性质 和上述单向群同态中对群的要求不完全相同 因此 必须对直和 AU 和 AV 的一些定义加以修改 以满足单向函数的要求 不过用辫群 Bn很难满足 单向函数同时又是环同态 所以经修改后的多签名体制和文献 中的有所不同 首先 辫群 Bn是无限群 不是有限的 对于这一点 可以把环 Zn改成环 Z 把直和改成 另外一点限制是 AU 中的 U 是交换群 11pp ZZ n ZB 这是 AU 是交换环的定义中对 U 的基本要求 但是辫群 Bn不是交换群 因 此 利用辫群不一定能够构造出单向环同态 不过根据辫群的性质 辫群还是 可以用来构造多签名体制 注意在文献 中提到了辫群的一个困难问题 寻找满足条件的 x 利用上述困难问题构造单向 n y pBZ p n yxxB 函数 p是固定的正整数 如果中元素 x y 满足条件 nn fBB p f xx n B 根据前文 Eikoh Chida 等证明的定义和定理 则在直和 f xyf x f y 中定义函数 F 为 F 也是单向函数 n ZB nn ZBZB p F n xn x 并且 同时满足加法和乘法运算 n x m y 加法和 F n xm yF n xF m y F n x m yF n x F m y 乘法的同态性质正是构造多签名体制所必须使用的 因为 由 生成的 Bn的子群 LBl ijji 2ij 1 2 1l 和 生成的子 6 群内元素是互相交换的 即任意 1l 1l r r RB abba 所以只要取元素 a b 满足群的同态性质 l aLB r bRB l aLB r bRB 因此直和中的 也满足加法 p f abab pp a bf a f b n ZB n a m b 和乘法的同态性质 利用上述性质 构造多签名体制如下 记 为签名方 对 为的秘密密钥 1 U 2 U r U1ir iii Xn x i U 其中是的子群 每个分别由生成元 生成 ii xLB i LB n B i LB 1 1it 1it 是的公共密钥 并且假设存在散列函数 H p iiii YF Xn x i U 也是的子群 生成元是 因此中 1r ZZLB 1r LB n B 1rt 1 1rt i LB 的任意元素都满足交换性 设待签名的消息为 M 并且 H M 等签名方相继执行一下步骤 n x 1 U 2 U r U