三大密码体制对称密码公钥密码和量子密码的理论与技术.doc

文章编号 :1001 - 893x(2003) 03 - 0006 - 07三大密码体制 :对称密码 、公钥密码和量子密码的理论与技术林德敬 ,林柏钢(福州大学 计算机科学与技术系 ,福建 福州 350002)摘 要 :随着信息技术的飞速发展 ,信息安全与通信保密日益重要与突出 ,密码技术是信息安全技术的核心 。文中概括介绍了国内外三大密码体制 (对称密码 、公钥密码和量子密码) 的理论与技术及其 现状 ,分析了它们的发展趋势 ,重点探讨了分组密码的主要设计技术和量子密钥的产生与分发 ,最后 对三大体制进行了比较 。关键词 :密码学 ;分组密码 ;序列密码 ;公钥密码 ;量子密码 ; rsa/ des/ aes/ nessie中图分类号 : tn91811文献标识码 :asurvey on the cryptogra phy of symmetry ,public - key and quantuml in de - jing , l in b o - gang(department of computer science and technology ,fuzhou university , fuzhou 350002 ,china)abstract :with the rapid development of it , information and communication security become more and more im2portant . cryptographic technique is the core of information security technology. this paper first introduces sum2marily the three cryptosystem( symmetry , public - key and quantum ciphers) theory & technology and their status quos , and analyzes their developmental trends. second , the thesis approaches emphatically primary de2 sign philosophy of block cipher and generation & distribution of quantum key. finally , the comparison between the three cryptosystems is outlined.key words :cryptography ;block cipher ; stream cipher ; public - key cipher ;quantum cipher ; rsa/ des/ aes/nessie码分析技术 2 个分支组成 。密码编码技术的主要任务是寻求产生安全性高的有效密码算法和协议 ,以 满足对数据和信息进行加密或认证的要求 。密码分析技术的主要任务是破译密码或伪造认证信息 ,实现窃取机密信息或进行诈骗破坏活动 。这两个分支 既相互对立又相互依存 ,正是由于这种对立统一关一 、引言随着信息与通信技术的飞速发展 ,信息安全与通信保密在个人隐私尤其在军事情报和国家机密等 方面显得尤为突出和重要 。而现实中又存在着各种各样的信息安全威胁 ,如伪造 、欺骗 、窃听 、篡改 、抵 赖 、拒绝服务等 ,它们直接针对信息系统的保密性 、 完整性 、可用性 、可控性和不可否认性 。密码技术是 信息安全技术的核心 ,它主要由密码编码技术和密1系 ,才推动了密码学自身的发展。密码 ( 学) 理论与技术目前主要有三大体制 ,即基于数学的对称密 码与公钥密码和基于量子力学的量子密码 。 收稿日期 :2003 - 01 - 23基金项目 :国家自然科学基金资助项目 (6017207) ;福建省自然科学基金资助项目 (a0010011)二 、国内外公钥密码及其研究现状三 、国内外对称密钥密码及其研究现状11 分组密码及其现状(1) 分组密码的抽象描述 1用抽象的观点来看 , 分组密码就是一种满足下11 公钥密码的抽象描述用抽象的观点来看 ,公钥密码体制就是一种陷 门单向函数 。我们说一个函数 f 是单向函数 ,若对 它的定义域中的任意 x 都易于计算 f ( x) ,而对 f 的 值域中的几乎所有的 y , 即 使 当 f 为 已 知 时 要 计 算f - 1 (y) 在计算上也是不可行的 。若当给定某些辅助 信息 (陷门信息) 时易于计算 f - 1 (y) ,就称单向函数 f 是一个陷门单向函数 。公钥密码体制就是基于这一 原理而设计的 ,将辅助信息 ( 陷门信息) 作为秘密密 钥 。这类密码的安全强度取决于它所依据的问题的 计算复度 。21 公钥密码及其现状自从 1976 年公钥密码的思想提出以来 ,国际上 已经提出了许多种公钥密码体制 ,如基于大整数因 子分解问题的 rsa 体制和 rabin 体制 、基于有限域 上离散对数问题的 diffie - hellman 公钥体制和 el2gamal 体 制 、基 于 椭 圆 曲 线 上 的 离 散 对 数 问 题 的 diffie - hellman 公钥体制和 el gamal 体制 、基于背包 问题的 merkle - hellman 体制和 chor - rivest 体制 、 基于代数编码理论的 me eliece 体制 、基于有限自动 机理论的公钥体制等 。目前比较流行的公钥密码体制主要有 2 类 : 一 类是基于大整数因子分解问题的 ,其中最典型的代 表是 rsa 体制 ; 另一类是基于离散对数问题的 , 如 el gamal 公钥密码体制和影响比较大的椭圆曲线公 钥密码体制 。由于分解大整数的能力日益增强 ,因 此为保证 rsa 体制的安全性总是要增加模长 。目 前 768 bit 模长的 rsa 体制已不安全 。一般建议使 用 1 024 bit 模长 ,预计要保证 20 年的安全性就要选择 2 048 bit 的模长 ,增大模长带来了实现上的难度 。 而基于离散对数问题的公钥密码在目前技术下 512bit 模长就能够保证其安全性 。特别是椭圆曲线上的离散对数的计算要比有限域上的离散对数的计算 更困难 ,目前技术下只需要 160 bit 模长即可保证其安全性 ,适合于智能卡的实现 ,因而受到国际上的广泛关注1 。国际上制定了椭圆曲线公钥密码标准 。列条件的映射 e : f2m s f m : 对于每个 k sk ,k 2e ( , k) 是从 f2m 到 f m 的一个置换 。可见 ,设计分2组密码的问题在于找到一种算法 ,能在密钥控制下从一个足够大且足够“好”的置换子集合中 ,简单而 迅速地选出一个置换 。一个好的分组密码应该是既 难破译又容易实现 , 即加密函数 e ( , k) 和解密 函数 d (, k) 都必须容易计算 , 但是至少要从方程 y = e (x , k) 或 x = d (y , k) 中求出密钥 k 应 该是一个困难问题 。(2) 国内外主要的分组密码及其分析随着 des 的出现 ,人们对分组密码展开了深入 的研究和讨论 ,现已有大量的分组密码2 。如 des 的各种变形 、idea 算法 、safer 系列算法 、rc 系列算法 、skipjack 算法 、feal 系列算法 、redoc 系列算法 、loki 系 列 算 法 , cast 系 列 算 法 、khufu 、khafre 、mmb 、3 - way、tea 、mac guffin 、shark、b ear 、l i2on 、ca. 1 . 1 、crab 、blowfish 、gost、square、misty、rijndael 算法 、aes 及 nessie 候 选 算 法 等 。在 分 组密码设计技术发展的同时 ,分组密码分析技术也得 到了空前的发展 。已有很多分组密码分析技术 ,如强力攻击 (穷尽密钥搜索攻击 、字典攻击 、查表攻击 、时间 - 存储权衡攻击) 、差分密码分析及其推广 、线性密码分析及其推广 、差分 - 线性密码分析 、插值攻 击 、密钥相关攻击 、能量分析 、错误攻击 、定时攻击等 。穷尽密钥搜索攻击是一种与计算技术密不可分的朴素密码分析技术 。des 一经公布人们就认为它 的密钥太短 (仅为 56 bit) ,抵抗不住穷尽密钥搜索攻 击 ,事实已证明了这一点 (用该方法终于在 1997 年 6 月 17 日 成 功 地 找 到 了 des 的 密 钥 ) 。可 见 , 寻 找 des 的替代者已刻不容缓 。(3) aes (advanced encryption standard)nist 在 1997 年 1 月 2 日正式宣布了公开征集 aes。它的基本要求是 : 必须 ( 至少) 支持 128 bit 分 组加密 ,支持 128/ 192/ 256 bit 密钥 (密钥空间分别有3 . 4 1038/ 6 . 2 1057/ 1 . 1 1077 个密钥) ,比三重 des快 ,至少与三重 des 一样安全 。nist 的评判规则大体可分为三大部分 : 安全性 ; 代价 ; 算法实现特性 。根据上述评判规则 ,nist 对所有的候选算法进行了 综合评判 :1) 1998 年 8 月第一次 aes 候选会议公布了 15 个官方 aes 候选算法 。表 1 简要概括了这 15 个分 组密码的背景 、整体结构 、设计特点及其有效性 。根 据研究和分析的结果 ,前 9 种算法都有很好的安全 性 ,而后 6 种相对于前 9 种而言存在有一些设计上的缺陷 。2) 1999 年 8 月 ,nist 从中筛选出了 5 个候选算 法 : rijndael 、mars 、rc6 、serpent 、twofish 。3) 2000 年 10 月 2 日 ,nist 宣布获胜者为 rijn2dael 算法 ,其原形是 square 密码算法 。它的设计策略是宽轨迹策略 (wide trail strategy) ,这种策略是针 对差分/ 线性分析提出的 ,它的最大优点是可以给出 算法的最佳差分特征的概率以及最佳线性逼近的偏 差的界 ,由此可以分析算法抗击差分及线性分析的 能力 。rijndael 是一个迭代分组密码 ,其数据分组与 密钥长度都是可变的 。但为满足 aes 的要求 ,分组 长度为 128 bit ,密钥长度为 128/ 192/ 256 bit ,相应的 轮数为 10/ 12/ 14 。4) 2001 年 11 月 26 日 ,nist 正式公布了新标准aes ,其编号为 fips pubs197 。(4) nessie (new european schemes for signatures ,integrity , and encryption)继美国征集 aes 结束之际 ,欧洲也开始进行称为 nessie 的密码大计划 ,其主要目的是为了推出一系列 安全的密码模块 ;另一个目的是保持欧洲在密码研究 领域的领先地位 ,并增强密码在欧洲工业中的作用 。 与 aes 相比 ,nessie 涉及的范围更广 ,不仅征集了分 组密码 ,而且还征集序列密码 、公钥密码 、数字签名 、 mac 以及 hash 函数 。nessie 共收到了 17 个分组密 码 ,按照分组长度分为 4 部分 。表 2 简要概括了这 17 个分 组 密 码 的 背 景 、整 体 结 构 、设 计 特 点 及 其 有 效21 国内外序列密码及其现状序列密码虽然主要用于政府 、军方等国家要害 部门 ,而且用于这些部门的理论和技术都是保密的 , 但由于一些数学工具 (代数 、数论 、概率等) 可用于研究序列密码 , 其理论和技术相对而言比较成熟1 。目前序列密码的现状为 : ( 1) 设计方法方面 : 可归纳为 4 种 ,即系统论方法 、复杂性理论方法 、信息论方 法和随机化方法 ; 将同步流密码的密钥流生成器分 解成驱动部分和非线性组合部分 ,这样做不仅结构简单 ,而且便于从理论上分析这类生成器 ;提出了非线性组合生成器 、非线性滤波生成器和钟控生成器 等多种具体设计方法 。(2) 安全性度量指标方面 :提出了线性 复 杂 度 轮 廓 、跃 复 杂 度 、k - 错 误 复 杂 度(球复杂度) 、球周期 、非线性复杂度等多种度量序列性3 ,4。与 aes 的 15 个候选算法相比 ,nessie 的 17 个候选算法的设计比较单一 ,没有多少新思想 ,受 aes 的影响比较大 ,整体结构主要采用 feistel 变换与 sp 网 络 ,非线性主要靠 s - 盒来实现 。随机性和稳定性的指标 ,并对指标进行了深入研究 。(3) 分析方法方面 : 提出了分别征服攻击方法 、线性攻击方法 、线性伴随式攻击方法 、线性一致性攻击方 法 、快速相关攻击方法 、线性时序逻辑逼近方法 、熵漏分析方法等多种有效的分析方法 。( 4) 在密码布 尔函数的构作与分析方面 : 提出了构造布尔函数的 多种设计准则 ,如相关免疫性 、线性结构 、严格雪崩 特性 、扩散特性 、平衡性 、非线性性 、差分均匀性等 , 构造了一大批满足上述若干准则的布尔函数 ,同时 ,对这些准则之间的关系也进行了深入研究 。( 5) 在非线性资源的生成和分析方面 : 对环上序列的生成和结构进行了深入研究和刻画 ,诱导出的二元序列 具有良好的密码学特性 。(6) 研究方法方面 :将谱技术 、概率统计 、纠错编码技术 、有限域理论等有效地 用于序列密码的研究 。(7) 另外 :虽然没有制定序列 密码标准 ,但在一些系统中广泛使用了序列密码如 rc4 用于存储加密 。事实上 ,欧洲的 nessie 计划中 已经包括了序列密码标准的制定 ,这一举措将导致序列密码研究热 。11 量子密钥产生与分发的物理基础(1) 光子的偏振现象 :每个光子都有一个偏振方 向即电场的振荡方向 。在量子密码学中用到 2 种光 子偏振 ,即线偏振和圆偏振 ,其中线偏振可取 2 个方 向 :水平方向和垂直方向 ; 圆偏振包括左旋和右旋 2 种情况 。在量子力学中 ,光子的线偏振和圆偏振是 一对共轭可观测量 ,也就是说 ,光子的线偏振态与圆 偏振态是不可同时测量的 。值得说明的是 ,在同一 种偏振态下的 2 个不同的方向是可完全区分的 ,例 如在线偏振态中的水平方向和垂直方向是可完全区 分的 ,因而可同时准确测量 。(2) heisenberg 测不准原理 : 光子的一对共轭偏 振态是互补的 , 正是这一 本 质 特 征 为 bb84 协 议 提 供了实现的基础 。实际上 ,在量子力学中任何 2 组四 、量子密码及其研究现状对称与公钥密码都是在合理计算时间内基于某 种数学的假设下 (如单向函数的存在) 提供了计算上 不可破的密码体制 ,即实用安全性 。然而 ,单向函数 的存在性并没有得到证明 ,因此基于数学的密码体 制 只 能 追 求 实 用 上 的 安 全 性 。量 子 密 码 是 以 heisenberg 测不准原理 ( 光子的偏振现象) 和 epr 效 应为物理基础 ,利用光纤异地产生物理噪声 。它可 以真正地实现一次一密密码 ,构成理论上不可破译 的密码体制 。光子不能被克隆的性质使量子密码编 码操作过程不能被完全窃听 ,一旦存在窃听也可以 察觉 ,并可以设法消除 。不可同时测量的物理量都是共轭的 ,都满足互补性 ,在进行测量时 ,对其中一组量的精确测量必然导致 另一组量的完全不确定 ,即遵循量子力学的基本原理 : heisenberg 测不准原理 。(3) epr ( einstein podolsky rosen) 纠缠效应 :一个 球对称原子系统中 ,同时向 2 个相反的方向发射 2个相干光子 ,初始时这 2 个光子都是未被极化的 ,测量其极化态 (偏振态) 时 ,对 2 个光子中的任一个进 行测量可得到测量光子的极化态 ,同时另一个光子 的极化态也被同时确定 ,但 2 个光子的极化态的方 向相反 。(4) 单量子不可克隆定理 :所谓“克隆”是指原来 的量子态不被改变 ,而在另一个系统中产生一个完全相同的量子态 。对于一个未知的单量子态不能被 完全拷贝 。对 2 个 非 正 交 的 量 子 态 不 能 被 完 全 拷 贝 。要从编码在非正交量子态中获得信息 ,不扰动这些态是不可能的 。21 量子密钥产生与分发的实现过程量子密码学还不能像对称 、公钥加密体制那样 能对数据直接进行加密处理 ,目前只能进行安全密 钥分发5 。量子密钥产生与分发的实现过程大致可 分为 5 个过程 :(1) 量子传输 :不同的协议有不同的量子传输方 式 ,但有一个共同点 :它们都利用量子力学原理或量 子现象来实现 。在实际的通信中 ,光子态序列中光 子的极化态将受到噪声和 eve ( 窃听者) 的影响 ,但 按照 heisenberg 测不准原理 , eve 的干扰必将导致光 子极化态的改变 ,这必然会影响 bob 的测量结果 ,由 此可对 eve 的行为进行判定和检测 ;(2) 数据筛选 :在量子传输中由于噪声和 eve 的 作用 ,将使光子态 序 列 中 光 子 的 极 化 态 发 生 改 变 。 另外 ,实际系统中 ,bob 的接收仪器不可能有百分之 百的正确的测量结果 ,所有那些在传送过程中没有 收到或测量失误 ,或由于各种因素的影响而不合要 求的测量结果 ,由 alice 和 bob 经过比较测量基矢后 全部放弃 ,并计算错误率 。若错误率超过一定的阈值 , alice 和 bob 放弃所有的数据并重新开始 ,如果是一个 可以接受的结果 ,则 alice 和 bob 将筛选后的数据保存 下来 ,所获得数据称为筛选数据 (sifted data) ;(3) 数据纠错 :所得到的 n 比特筛选数据并不能 保证 alice 和 bob 各自保存的安全一致性 ,这可以由 各种因素造成 ,解决这一问题的办法是对原数据进 行纠错 ,如采用奇偶校验等 。这样做的目的是为了减少 eve 所获得的密钥信息 ;(4) 保密加强 :保密加强是为了进一步提高所得 密钥的安全性而采取的措施 ( 非量子的方法) ,其具体实现为 :假设 alice 发给 bob 一个 n 比特串 , eve 获 得的比特为 t n 。为了使 eve 所获得的信息无用 , alice 和 bob 采用秘密加强技术 : 公开选取一个压缩函数 g: 0 ,1n 0 ,1r ,其中 r 是被压缩后密钥的长度 ,这样使得 eve 从 w 中获取的信息和她的关于 函数 g 的信息给出她对新密钥 k = g( w) 尽可能少 的信息 。对任意的 s 这样就把第 i 次迭代的输入表示成了输出的函数 ,这些方程证实了图 2 右边部分的安排 。最后 ,我们 看到解密过程的最后一轮的输出是 re0 l e0 。它经过一个 32 bit 的对换就恢复了原来的明文 , 这验 证了 feistel 解密过程的正确性 。注意以上推导并不 要求 f 是一个可逆函数 。为证实这一点对 f 取一个 极端情况 ,即无论 2 个参数取什么值 ,它都产生常数 输出 (即全 1) ,这时可以看到方程仍然成立 。五 、分组密码的主要设计技术11feistel 网络结构及其解密算法feistel 网络是基于 shannon 1945 年的设想提出图 1 feistel 网络结构图 2 feistel 加密和解密线公钥密码的安全性评估问题 ;(4) 目前对于量子密码还有一些问题有待于研究 :如寻找相应的量子效应以便提出更多的量子密钥分配协议 ;如何克服实际量子系统中对量子相干性的干扰破坏以保证系统能够有效工作 ; 有效的量子受控门和量子逻辑网络的设计 ; 经典信息理论在量子理论框架内的重新研究 ,以便建立量子信息理论体系 ;量子密码的实用技术研究等 。2 . 轮函数 f 、s - 盒与密钥编排算法的设计函数 f 是 feistel 密码的核心 ,它主要依赖于 s- 盒子的使用 。对于大部分其它的分组密码也是这 样 。而 s - 盒的设计是分组密码设计过程中一个最 受关注的研究问题 ,因为在分组密码算法中 s - 盒 通常是仅有的一个非线性步骤 ,它们给出了分组密码的安全性 。因此如何设计一个非线性度高的 s - 盒是分组密码的设计关键 。另外 ,它们的设计还应 遵循雪崩准则与比特独立准则以便使它具有很好的 混乱效果 。同时 s - 盒各列的线性组合应该是曲折 的 。一般认为应按如下方式设计 s - 盒2 : (1) 随机选择 :使用某种伪随机数产生 s - 盒的各项 。若 s - 盒是随机的且与密钥相关则 s - 盒将更强 。如 idea 与 blowfish 的 s - 盒 。( 2) 带测试的随机产生 : 随机 选择 s - 盒的各项 ,然后根据需要的特性来测试它 , 丢弃那些没有通过测试的项 。如 mars 的 s - 盒 。(3) 人工构造 :如 des。(4) 数学方法构造 : 根据数学 原理来产生 s - 盒 ,s - 盒可以被设计得具有可以证 明的抗差分攻击和线性攻击的能力 ,同时具有良好 的扩散特性 。如 cast 的 s - 盒 。在任何一个 feistel 分组密码中 ,密钥都被用来产生每个循环使用的子密钥 。我们希望选择子密钥时要使得推测各个子密 钥和由此推出主密钥的难度尽可能的大 。对于这方 面的研究目前还没有公开发表的一般原理 。但是至 少密钥编排应保证密钥/ 密文的雪崩准则 。七 、结束语本文概括介绍了三大密码体制的理论与技术以 及它们的现状与发展趋势 。对称密码体制由于通信 双方在通信之前需要通过一个安全信道交换密钥 , 密钥有可能泄露 、伪造 、被窃取 ,所以对称密码在密 钥管理尤其是密钥分配方面存在较大缺陷 ,但其加 解密速度非常快 ,因此在数据加密领域仍然是以对 称密码为主 。公钥密码体制利用一对“公钥/ 私钥” 来进行保密通信 ,解决了对称密码中的密钥分配问 题 ,但由于其安全性是建立在某一数学难题上的 ,原 则上建立在数学技巧上的密码体制是会被攻破的 , 并且随着计算能力的增强及以 后 量 子 计 算 机 的 出 现 ,公钥密码的安全性将会被严重削弱 。量子密码 利用物理规律原则上是不会被攻破的 ,且它具有实 时分配密钥 ,安全可靠 ,密钥的产生与分发与具体用 户无关等特点 ,它具有对称 、公钥体制中所没有的优 点 ;用量子密钥可以实现对称体制中的密钥共享 ,亦 可实现公钥体制中的秘密密钥功能 。在未来的光通 信时代 ,通过光纤进行量子