第6章通信系统的保密.ppt

第6章通信系统的保密 6 1密码系统和密码体制6 2认证技术6 3认证方案6 4数据加密体制6 5模拟信号加密 6 1密码系统和密码体制 6 1 1明文 密文和密钥保密学是研究密码系统或通信系统的安全问题的科学 它包含密码编码学和密码分析学两个分支 密码编码学是研究和设计各种密码体制 使信息得到安全的隐藏体制 密码分析学是在未知密钥情况下研究分析破译密码 以便获取已隐藏的信息 也就是 将窃听者在仅知密文或已知明文以及既知密文又可自选任意数量的明文而获得密文的条件下 分析推导出明文 称它为密码分析学 这是一个矛盾的双方 密码学就是在矛盾双方不断的推动和促进下发展的 密码体制的基本思想是隐藏和伪装需要保密的信息 使非授权者不能获取信息 在深入研究密码学之前 先介绍一些术语 明文 或消息 需要采用某种方法对其进行变换来隐藏载荷着信息的消息或字符串 密文 或称密报 明文经过某种变换后成为一种载荷着不能被非授权者所理解的隐藏信息的消息或字符串 加密 明文变换成密文的操作过程 解密 利用密钥从密文恢复明文的操作过程 即加密的逆过程 接收者 预定接收密文的人员 接收者知道密钥是非常关键的 加密算法 加密者对明文进行加密所采用的一组法则 又称为加密编码 解密算法 利用密钥将密文进行解密所采用的一组法则 又称为解密密码 加密密钥 加密算法通常在一组密钥的控制下进行 这组密钥称加密密钥 解密密钥 解密算法也在一组密钥的控制下进行 这组密钥称为解密密钥 单钥密码体制 在加密和解密过程中 加密密钥和解密密钥相同 或从一个易得出另一个密码体制 单钥密码体制也称私钥密码体制 双钥密码体制 在加密和解密过程中 加密密钥和解密密钥不相同 而且从一个难以得出另一个密码体制 它使加密能力和解密能力分开 一般而言 双钥体制 但不是所有双钥体制 又称公开密钥密码体制 它是现代密码学的核心 特别对认证系统大有作为 截取者 凡截取已加密了的消息的任何人 是非授权的 截取机密的人 一般情况 截取者不知道密钥 密码分析 是在未知密钥的情况下 通过分析从截获的密文中推断出明文的过程 6 1 2密码编码和密码分析1 保密系统的模型保密系统设计的目的是对传送的信息进行加密处理 使除授权者以外的任何截取者在即使准确地收到了接收信号也无法恢复出原来的消息 保密系统的模型如图6 1所示 图6 1保密系统 图中的信源包括信源编码器 它送出的信息流称为明文 信息流可以被分组或不分组 明文送入加密编码器 在密钥控制下被加密成密文序列 密文经信道传输到收端 一般假设信道是无干扰的 对于有扰信道 根据香农第二定理可以在信道输入端和输出端分别加入信道编码和信道译码等构成广义的无干扰信道 由于信道是非安全的 除了各种自然和人为干扰以外 还存在各种非法入侵者的主动攻击和被动攻击 若主要关心整个密码系统的安全性 则信道中的噪声或干扰对被传信号的影响 可以暂时不考虑 认为由信道输出的序列没有错误 密钥源是产生密钥序列的源 通常密钥是离散的 明文和密钥是彼此统计独立的 一般情况下 密钥通过保密信道传送给合法的接收者 信宿 或者发送者与接收者事先商定好 解密译码器被合法接收者 信宿 用于对接收的密文进行解密变换 因为他知道密钥和解密变换 很容易从密文中恢复出明文 截取者接收到密文 即使他知道加密算法 但因不知道特定的密钥 也无法获取信息 可见 所用的特定的密钥很重要 必须要保存好 另外也不能使截取者从密文中获得密钥 2 密码编码事实上加密器是一个把明文M变为密文C的数字 或模拟 变换器 这种变换过程称为加密 因此密文C为 6 1 式中 加密算法 函数 或加密规则 ke 加密密钥 与此相反 收端的解密器是一个由密文到明文的反变换器 这种反变换过程称为解密 因此接收者获得的明文M为 6 2 式中 解密算法或解密规则 kd 解密密钥 可见 一个密码系统的保密性或安全性 完全依赖于加密和解密算法以及加密和解密密钥 一个密码系统的加 解密算法 称为密码算法 在公钥体制中 加密密钥ke可以公开 而解密密钥kd必须保密 而且很难 或实际上不可能 由加密密钥ke和密码算法推出解密密钥kd 也不可能由解密密钥kd和密码算法推出加密密钥ke 在单钥密码体制中 收发两端用户使用同一个密钥 且体制的安全性完全决定于密钥 因此必须对密钥严加保密 在每次通信前 收端用户使用的密钥 必须通过安全信道由发端送到用户手里 因此这种单密钥体制的密钥管理 传输和分配是一个异常复杂的问题 特别是在计算机通信网中 用户数目很多 每对用户之间必须分配不同的密钥 因此密钥的产生 管理 分配更为复杂 但对公钥密码体制来说 由于每个用户的加密密钥是公开的 可以像电话号码一样 刊登在公开的号码本上 或者保存在公用的数据库中 因此密钥的产生 分配 保管就要简单多了 因而公钥密码体制特别适用于通信网系统中 单钥密码体制或对称密码算法分为分组算法和序列算法两类 分组算法是对明文的一组比特同时进行运算 这些比特组为一个分组 相应的算法称为分组算法 相应的密码称为分组密码 序列算法是每次只对明文中单个比特进行运算的算法 相应的密码称为序列密码或流密码 一个好的分组加密算法应满足 分组的明文字长n要足够大 以防止明文穷举攻击法奏效 密钥量要足够大 即置换子集中的元素足够多 以防止密钥穷举攻击法奏效 由密钥确定置换的算法要足够复杂 使破译者除了用穷举法以外 无其他捷径可循 要实现以上3点要求并不很容易 要实现第1项要求 选择n足够大 当n足够大后会使代换网络变得过于复杂而难以控制实现 实际中常常将n分成几个小段 分别设计各段的代换网络 并采用并行操作达到总的分组长度n足够大 要实现第2项要求 以增大密钥量 往往采用多个简单密码系统的组合 香农曾建议采用两种组合 其一是所谓概率加权和的方法 即系统总密钥量等于各个分系统密钥量的概率加权和 另一种是乘积法 即系统总密钥量等于各个分系统密钥量的概率加权积 为了抗击统计分析破译法 实现第3项要求 香农曾建议采用扩散和混淆两种方法 所谓扩散 就是将每一位明文的影响扩散到多个输出的密文中 以便于隐蔽明文的统计特性 所谓混淆 就是掩盖明文和密文之间关系 其目的在于使密文和明文的统计特性间的关系复杂化 直到目前 混淆和扩散是两种最为常用的方法 几乎所有现代加密系统都用到这两种方法 扩散将明文多余度分散到整个密文中 其中 最简单的扩散方法是置换 实际上就是数学上的有限集合的映射变换 或称之为代换 即从明文空间M到密文空间C上的映射 常用的代换有 左循环移位代换 右循环移位代换 模2加1代换 线性变换 坐标变换 仿射变换 可见 分组密码的加 解密运算以分组的数据为单位进行 分组密码设计的主要方法是对分组数据进行替换和转移两种运算 序列密码的加密过程是先把报文 话音 图像和数据等原始明文转换成明文数据序列 然后将它同密钥序列进行逐位加密生成密文序列发送给接收者 接收者用相同的密钥序列对密文序列进行逐位解密来恢复明文序列 序列密码不存在数据扩展和错误传播 实时性好 加 解密实现容易 因而是一种应用广泛的密码系统 序列密码的思想起源于20世纪20年代 最早的二进序列密码系统是Vernam密码 当Vernam密码中的密钥序列是完全随机的二进序列时 它就是一次一密密钥码 一次一密密钥码是完全保密的 但它的密钥产生 分配和管理都极为困难 因而这种系统没有得到广泛的应用 随着微电子技术和数学理论的发展 基于伪随机序列的序列密码就应运而生了 在通常的序列密码中 加 解密用的密钥序列是伪随机序列 它的产生容易且有较成熟的理论研究工具 所以序列密码是当前最通用的密码系统 序列密码的安全保密性主要依赖于密钥序列 因而什么样的伪随机序列是安全可靠的密钥序列以及如何实现这种序列就成了序列密码中研究的一个主要问题 而与此密切相关的伪随机序列理论等课题也成了目前人们研究的一个热点 常用的密钥序列产生器包括基于线性反馈移位寄存器的前馈序列产生器 非线性组合序列产生器 钟控序列产生器和非线性反馈移位寄存器等 但新的方法和新的理论还在不断发展 之中 3 密码分析密码编码学的主要目的是保持明文 或密钥或二者兼而有之 的秘密或隐私性 以防止非法用户或敌人窃取 密码分析学是在不知道密钥的情况下 恢复出明文 或密钥 的科学 在设计一个密码体制的同时 往往必须对该体制进行密码分析 以发现该体制的缺点 估计它的安全性等 另一方面 敌手往往通过密码分析 对密码体制进行攻击 试图发现密码体制的弱点 以此为突破口 最终找到所使用的密钥或由密文恢复出部分或全部明文 试图对密码进行分析称为攻击 攻击时总是假设密码分析者 或敌人 除了加密时使用的特定密钥以外 知道被分析密码体制的一切知识 包括密码算法的全部细节 此假定称为Kerckhoff准则 这是一切密码设计者所必须时刻想到的 当然 在实际情况中并不总是如此 敌手不一定知道所使用的密码算法 也不一定占有密码体制的详细资料 但是 从理论上讲这种假定是非常合理的 也是一个常用的假定 由此可知 一个密码体制的保密性如果依赖于密码算法的保密 那么这种体制的保密性是最低级的 并且也是不实际的 一个好的密码算法 绝不担心被公开并进行讨论 因为只要不知道密钥 甚至算法设计者也不能解密恢复出明文 攻击或破译密码的方法有穷搜索 穷举 法和分析法两类 穷搜索法又称强力攻击 这是对截收到的密文依次用各种可能的密钥试译 直到得到有意义的明文 或者在不变密钥的情况下 对所有可能的明文加密 直到得到与截获到的密文相同为止 原则上讲 只要有足够多的计算时间 存储容量和密文数据 或有足够多的明文 密文对 穷搜索法总是可以成功的 但实际中任何一种能保障安全要求的实用密码体制 都会设计得使这种穷搜索法在实际上是不可行的 在理论上 这种方法也往往作为与其他攻击方法相比较的基础 以此作为标准 判断其他各种攻击方法的有效程度 分析破译法有确定性分析法和统计分析法两类 确定性分析法利用一个或几个已知量 如已知密文或明文 密文对 用数学函数表示出已知量与所要确定的未知量之间的关系 寻求这种数学关系 是确定性分析法的关键步骤 统计分析法利用明文已知的统计规律进行破译 密码破译者对截收到的密文或密文之间的差 进行统计分析 总结出其间的统计规律 并与明文或明文之间的差进行对照比较 从中提取出明 密文之间的变换关系 如分析两个明文之间有特殊差的统计规律 相应的两个密文之间差的统计规律 从而分析出所用密钥的差的统计规律 以及与其类似的相关密钥分析 线性分析和其他利用明 密文和密钥之间相关特性的相关攻击方法等 在遵从Kelrckhoff准则下 密码分析者或破译者的攻击方法有 种 它们分别是唯密文攻击 已知明文攻击 选择性明文攻击 自适应选择明文攻击 选择性密文攻击 选择性密钥攻击 惟密文攻击 密码分析者的任务是利用获得的一些密文恢复出尽可能多的明文或者相应的密钥 已知明文攻击 密码分析者已知一些密文及其对应的明文 分析者的任务是推导出加密消息的密钥 或推导出一个算法 以便对用同一密钥加密的任何新的密文进行解密 选择性明文攻击 分析者不仅可得到一些消息的明文 密文对 而且可以按照他自己的要求 选择被加密的明文及其对应的密文 这相当于密码分析者得到了加密设备 但不知道密钥 因此这种方法比已知密文攻击更有效 分析者的任务是推导出用来加密的密钥 或者推导出一个算法 用此算法可以对用同一密钥加密的任何消息进行解密 自适应选择明文攻击 这是选择性明文攻击的特殊情况 密码分析者不仅能选择被加密的明文 而且还能基于以前加密的结果修正这种选择 因而比选择性明文攻击更为有效 所需的明文 密文对可以更少 选择性密文攻击 密码分析者能够选择不同的待解密密文及相应的明文 这种情况相当于密码分析者得到了解密设备 但不知道密钥 密码分析者的任务是推导出密钥 这种攻击方法适用于公钥体制 当然也适用于私钥体制 但此时在计算复杂性上等价于选择性明文攻击 选择性密钥攻击 这种攻击并不意味着密码分析者能够选择密钥 仅仅说明他有一些不同密钥之间关系的知识 如前面提到的相关密钥分析就属此类 分析者已知消息被一对有一定关系的密钥加密 但不知密钥 及用该对密钥加密的对应的密文 这种攻击当然不一定实际 但它对某些密码体制的攻击可能有效 除了上面的这些方法以外 还可以从其他不同的方法得到密钥 如对密钥保管员采用恐吓 收买等手段取得密钥 或者通过其他手段得到已知密文的明文 或已知明文的密文 当然 这些方法不能作为密码分析人员的常用手段 在上述六种方法中 已知明文攻击和选择性明文攻击是最常用的 并且上述不同攻击方法的排列次序 也代表了攻击或安全性的等级 也就是惟密文攻击是最低级的 而自适应选择明文攻击和选择性密文攻击处于最高层 如果一个密码体制在选择性密文攻击下是安全的 那么它在已知明文攻击和惟密文攻击下也一定是安全的 但反过来就不一定成立 究竟采用何种方法进行破译取决于很多因素 但攻击的复杂性 也就是破译密码体制所花费的代价是首先要考虑的 通常用数据复杂性 时间复杂性和存储量等三种方法度量攻击的复杂性 数据复杂性 即破译一个密码所需的密文量或明文 密文对或明文量等 时间复杂性 即完成破译所需的计算时间或工作因子 存储量 也称空间复杂性 完成破译所需的存取单元 这三者中谁的复杂性最高 谁就作为衡量破译密码体制复杂性的主要标准 一般情况下 后两者的复杂性往往大于第一种情况 因此以后将时间和空间复杂性 作为衡量攻击方法有效性和密码体制安全性的标准 这将在6 1 5节中进一步讨论 6 1 3古典密码体制古典密码是比较简单的 它们大多采用手工或机械方式对明文进行加密 对密文进行解密 现在这些密码的绝大部分已毫无安全可言 已不采用了 但是理解古典密码的基本设计思想和原理 对于掌握和分析现代密码学是有一定意义的 1 单表密码单表密码是一种简单的代换密码 它对所有的明文字符都采用一个固定的明文字符集到密文字符集的映射 设明文M m1m2m3 则相应密文为 6 3 若明文字符集A a1 a2 an 则相应的密文字符集为A f a1 f a2 f an 此时密钥就是一个固定的代换字母表 映射函数f是可逆函数f 1 那么 对密文C c1c2 的解密译码过程为 6 4 例6 1 设明文字符集 为26个英文字母 一个固定的代换字母表为A 它就是密钥 A ABCDEFGHIJKLMNOPQRSTUVWXYZA XGUACDTBPHSRLMVQYWIZEJOKNF若明文为M Thisisabook 则密文 C E m ZBPIPIXGVVS对于有26个英文字母的信源 用这种方式进行加密 解密 代换字母表共有26 种 2 移位代换密码移位代换密码又称加法密码 它是单表密码的一种 设明文字符集A a0 a1 a2 an 1 密钥为ke 其加密变换为 6 5 式中 i j都是A中元素的下标 由式 6 5 的加密变换可知 所得的代换字母表就是明文字符集位移k后所得 这种移位代换密码 密钥k可取1至n共n种 可获n种不同的代换字母表 例6 2 设明文字符集为26个英文字母 n 26 进行移位代换密码 这就是凯撒密码 若选取密钥k 3 则有下述代换对应表 A abcdefghijklmnopqrstuvwxyzA DEFGHIJKLMNOPWRSTUVWXYZABC所得密文字母集为明文字母集向左位移k位 对消息 明文 加密的算法仅仅是用代换表中对应的字母来替代 而解密算法可用代换表对密文进行反向变换替代 若有明文为 M Thisisabook则密文 C WKLVLVDERRN显然 凯撒密码是很容易实现加密编码和解密译码的 因为对于凯撒密码来言 n 26 所以共有26个代换字母表 当k 26时 即位移为零 密文字母与明文字完全一致 当然 这26个代换字母表就是例6 1的26 种代换密码中的一部分 6 1 4保密性与随机性1949年以前的密码研究还称不上是一门科学 许多密码系统的设计仅凭一些直观的技巧和经验 保密通信的一些最本质的东西并没有被揭示 因而密码研究缺乏系统的理论和方法 1949年香农发表了一篇题为 保密系统的通信理论 的著名论文 他首先将信息理论引入到密码 从而把已有数千年历史的密码学推向了科学的轨道 形成了科学的秘密钥密码学学科 香农用概率统计的观点对信息源 密钥源 接收和截获的密文进行了数学描述和定量分析 提出了通用的秘密钥密码系统模型 香农把各种各样的密码系统概括成由一对加密编码器和解密译码器组成 一个是用于传送密文的公开信道 一个是用于传送秘密钥的保密信道 密码系统设计的目的就是要使截收者即使能获得所有的密文也无法恢复出对应的明文或系统使用的密钥 香农用信息论的观点分析消息源 密钥源 接收和截获的密文 引进了不确定性 剩余度和惟一解距离作为度量密码系统安全性的测度 全面地阐述了完全保密 纯密码 理论保密和实际保密等新概念 为密码学研究奠定了重要的理论基础 尽管从20世纪40年代后期起密码学有了理论研究基础 形成了一门新的学科 但在70年代中期以前的密码学研究基本上是秘密进行的 而且主要应用于军事 政府部门 密码学的真正蓬勃发展和广泛的应用是从70年代中期开始的 由于美国颁布了数据加密标准DES 并且Diffie和Hellman提出了公开钥密码系统的新概念 这就给现代密码学的理论与技术的发展带来了划时代的变革 不但现代密码学的研究远远突破了早期秘密钥密码的信息保密的单一目的 信息的认证 密钥的分配 把纠错码与密码结合在一起设计 或用纠错码构造密码系统以及密码系统在商业等民用领域的广泛应用等都成了人们研究密码的内容 当把纠错码与密码结合在一起设计 或用纠错码构造密码系统时 不可避免地要加上多余度 而多余度的增加 无疑减少了保密系统的安全性 另一方面 从密码系统的随机性来看 利用纠错码构造的密码体制不能做到使密码系统完全随机化 而只能做到局部随机化 从本质上讲 纠错密码体制仅仅是一类局部随机化的密码体制 但是 如果这类纠错密码体制的最终安全性乃是计算上安全的话 那么纠错与加密相结合的密码体制 或利用纠错码构造的密码系统乃是实际上安全的 因而也是可行的 总之 为了设计一个实际可行的好的密码系统 正如香农在1949年的论文中指出的 好密码的设计问题 本质上是寻找针对某些其他条件的一种求解难题的问题 1 完全保密性与随机性密码系统的安全性是密码学中研究的主要问题 一个密码系统希望是安全的 就是指截取者无法破译密文而获得发送的信息 若一个保密系统满足明文和密文之间的互信息量等于零 则称此系统为完全的保密系统或称无条件的保密系统 对于完全的保密系统 由于破译者从密文中得不到任何有关明文的信息 所以无法进行破译 显然 这种安全性是对惟密文破译而言的 它不一定能保证已知明文或选择明文破译条件下也是安全的 密码系统设计的基本原则应该是使明文和密文之间的互信息量为零 从概率论观点来看 也就是所有明文与密文应该完全无关 香农早在1948年就已严格证明了 对于许多二进制密码体制 如果要使明文和密文完全无关 则密钥必须是一个真正的随机序列 所以密码设计的焦点集中在密码系统的随机性 也就是密钥的随机性 只有完全随机的密钥序列 才能由明文得到随机化的密文 图6 1已给出了保密系统的数字模型 从截取的密文中提取有关明文的信息量是 I M C H M H M C 6 6 式中 I M C 明文和密文之间的互信息量 H M C 在已知密文的条件下对明文存在的不确定性 H M 明文的熵 H K C 在已知密文的条件下对密钥的不确定性 由式 6 6 和式 6 7 可知 要使破译者从密文中提取的有关明文和密钥的信息量越小 必须使H M C 和H K C 越大 定理6 1对于任何保密系统 有 I M C H M H K 6 8 通常 密钥空间K中密钥是等概分布的 密钥的熵H K 和密钥空间的密钥量有关 密钥量越大 密钥的熵H K 越大 密钥量越小 H K 越小 若密钥量越小 H K 越小 I M C 越大而越接近H M 则使破译者从密文中能获得的关于明文的信息量就越大 越容易破译 因此 从设计密码系统角度来看 必须使密钥空间的密钥量尽可能大 定理6 2完全保密系统存在的必要条件是 H K H M 6 9 根据完全保密系统的定义和定理6 1很容易证明该定理 由定理6 2可知 要构造完全保密系统 必须使密钥空间熵大于明文空间熵 密码分析者即使具有无限的计算资源 时间 存储量等 也不能被破译的密码系统 被称为无条件安全的密码系统 由于一个保密系统的安全性还与破译者所采用的攻击方法有关 在惟密文攻击下是安全的 在选择性明文攻击下就可能是不安全的 显然 这里从概率论 熵和平均互信息量观点讨论的完全保密系统 在惟密文攻击下是无条件安全的 事实上 迄今为止也仅有一次一密系统才是无条件安全的 一个保密系统是计算上安全的 就是实际上安全的 而无条件安全是指理论上的安全性 2 惟一解距离 理论保密性20世纪40年代末 密码学奠基人之一香农引入了一个非常重要的惟一解距离的概念 它是从密码分析学角度考虑的一个重要物理量 当截获者获取的密文长度大于它时 密码成为可破译的 且具有惟一解 反之 当截获者获取的密文长度小于它时 理论上该密文是不可破译的 因为它具有多个解的可能性 要注意的是这个概念指出的仅是可能被破译的必要条件 而并没有给出任何具体的破译方法 即使这样 在理论上无论是对密码分析还是密码设计 它都是一个很重要的概念 理论保密性是探讨惟密文攻击时 密码系统安全性的理论极限 研究惟密文破译的一种密码体制时 窃密者或密码分析人员必须处理的密文量的下限 设C c1c2 cncn 1是密文序列 由条件熵的性质可知 H K c1c2 cncn 1 H K c1c2 cn H K c1 H K 6 10 这就是说随着密文的增加 密钥的不确定性是非增的 随着n的增加 若 K c1c2 cn 0 则从理论上讲可破译该密码体制 由此可知 n越大 疑义度越小 一般情况 随着截获密文的增加 对密钥或明文的疑义度减少 获得有关密钥或明文的信息量就增加 当n充分大时 使H K C 0时 就可惟一地确定密钥空间K 从而实现破译 因而使H K C 0的最小n是密码学中一个有重要意义的量 这个值就是密码系统在惟密文攻击下的惟一解距离n0 n0就是使H K C 近似等于零的最小整数 惟一解距离就是破译者惟一地确定加密所用密钥至少所需要的密文量 当截获者截获的密文量大于n0 原则上就可以惟一地确定密码系统所用的密钥 就可以破译 因此 惟一解距离n0是度量密码系统安全性的一个指标 若一个密码系统 对系统而言 即使截获了许多密文并不能消除关于密钥的不确定性 系统无法破译 这是很理想的保密系统 也就是这系统是具有理论保密性的 定理6 3对于随机密码系统 惟一解距离 6 11 式中 l l位二元信源 或明文 序列的多余度 该定理表明 信源多余度 l越小 则n0越大 保密系统也就越安全 因此在对消息加密前 应先压缩编码以减少多余度 这对提高整个保密系统的安全性是绝对必要的 这也就是信源编码器必须放在加密器以前 纠错编码器放在加密器之后的主要原因之一 除此之外 为了使破译者难以从研究多余度进行统计分析 香农提出了混淆与扩散两种技术 以隐藏消息中的多余度 但是 在实际中 由于 l不可能为零 故惟一解距离总是有限的 因而任何实际保密系统在有限密钥下理论上都是可破译的 但理论上可破译 并不表示实际可破译 这就涉及到保密系统的实际保密性或安全性问题 估计一个保密系统的实际保密性 应主要考虑窃密者的计算能力 资源 以及其采用的破译算法的有效性两个因素 若利用最好的算法 至少需N步运算才能破译一个密码系统 这里N是指定的一个非常大的数 则该保密系统是计算上安全的 事实上 当N大到一个不合理的数时 例如用目前最快的计算机运算N步 需要几千万年或甚至需要宇宙年龄的计算时间 则就认为该系统是计算安全的因而也是实际上安全的 另外一个方法是把证明保密系统是否计算安全的问题 归结到某些著名的数学难题 如 若给定的n pq很难被分解的话 则给定的密码系统是安全的 当然 这种方法仅仅是对保密系统提供了一种相对其他问题的安全性证明 而不能绝对证明系统是否安全 事实上直到目前为止除了以物理定律保证的量子密码体制外 还没有找到这种绝对证明的方法 由于一个保密系统的安全性还与破译者所采用的攻击方法有关 在惟密文攻击下是安全的 在选择性明文攻击下就可能是不安全的 3 实际保密性假定破译者能充分地利用信源的统计知识 并且具备无限的计算能力和时间等资源 则只需使截获的密文量大于n0就可以惟一确定系统所用密钥而破译 实际上 破译者所能利用的资源均受到很多限制 一旦破译一种密码所需付出的代价超过破译该密码所得信息的价值 或者破译成功的时间超出了所得信息的有效期 则这种破译也是徒劳的 所以 研究保密系统实际意义上的保密问题是很重要的 保密系统在破译者的时间 能力 物力等资源受限制的条件下的安全性称为实际保密性 如果一个保密系统的破译所需花费的努力超过破译者具有的条件 则此系统实际上是安全保密的 密码系统的理论安全性通常是在理想的 易于数学分析的假设下关于密码安全性的测度 它忽略了破译者所处的实际情况 在实际条件限制下 一个在理论上不完全保密的系统可能提供实际上的安全保密性 反之 一个理论上是安全保密的系统 在实际上也可能是很脆弱 易于被攻破的 实际情况下 破译者若能获得一些明文 密文对 就有可能破译密码 一次一密钥体制 密钥量很大 H K 很大 所以系统理论上是安全的 但这种情况下密钥量至少和明文一样多 密钥的传送 管理都很困难 这反过来使密钥系统易于攻破 所以 实际保密系统不能单纯追求理论保密性 一般消息的保密都有一个最小保障时间 如果在这时间内破译者不能破译的话 则系统的安全性能满足实际需要 系统具有实际安全性 估计一个保密系统的实际保密性 主要考虑破译者的计算能力和破译者的破译算法的有效性两个因素 破译者的计算能力是指破译者所具备的设备 资金等资源 如果破译者进行破译所需运算的运算量 运算时间和存储量等都受资源的限制 使在系统的保障时间内无法破译 这系统实际是安全的 破译者的破译算法的有效性是指 如果破译者掌握的破译算法很拙劣 就需花费很长的时间和很大的精力来进行破译 这对系统来说 就具有实际的保密性 当然 实际破译者不仅会采用完全试凑法 而且往往会利用信源的统计特性 进行统计分析 这样即使截取到很短的密文也能很快破译 因此 破译者总是不断地寻找新的破译算法 提高他的破译效率 所以 保密系统的设计者要设计一个实际安全的保密系统 就必须研究 分析破译者可能采用哪些破译方法 估计这些破译方法的工作量和有效性 使这些破译方法的运算工作量很大 时间很长 这就相当于设计一个密码系统 使破译密码的难度等价于解某个已知数学难题 这就能使密码系统做到实际上是安全的 公开密钥密码系统的思想就是基于实际安全性提出的 把密码破译归纳为解数学难题 因而一个密码系统的实际安全性的大小就取决于求解这些数学问题的难易程度了 数学问题求解的复杂性可通过计算复杂性理论来描述 因此计算复杂性理论为破译密码的计算复杂度提供了实际的度量方法 而计算复杂性理论中的一些典型数学问题又给人们提供了设计实际安全的密码系统的基础 所以 信息论和计算复杂性理论是现代密码系统设计和分析的重要基础 综上所述 为了保护信息的安全 抗击密码分析 保密系统应当满足以下要求 1 若系统达不到理论上不可破的 也应当成为实际上不可破的 也就是说从截获的密文或某些已知明文 密文对中 要确定出密钥或明文 在实际的计算中是很难办到的 2 系统的保密性与密码算法和密钥密切相关 但是从安全性角度考虑 系统的保密性不能依赖于密码体制和密码算法的保密 而只能依赖于密钥 3 加密和解密算法适用于所有密钥空间中的元素 4 系统要便于实现 且有加 解密速度快 成本低 使用方便等特点 为了防止消息在传输过程中被篡改 删除 重放和伪造 保证被传消息的完整性和真实性 密码系统还应具备使发送的消息具有被验证的能力 使接收者或第三方能够识别和确认消息的真伪和完整 以及确定发送者的身份等 这些内容属于密码系统中的认证范畴 有关认证系统将在6 2节中介绍 6 1 5复杂性理论由前面的讨论可知 人们特别关注一个密码系统的实际安全性或计算安全性 由于密码分析者或破译者所进行的破译工作是按编制的算法在计算机上进行的 因此实现破译所需的计算机资源 运算时间和存储空间 自然可以作为破译者需支付代价的一种定量描述 所以复杂性理论在密码强度或安全性分析中自然非常重要 1 算法复杂性算法是指求解某个问题的一系列具体步骤 也可以理解为求解某个问题的通用计算机程序 求解同一计算问题可能有许多不同的算法 一个算法的计算复杂性包括时间复杂性T n 和空间复杂性S n 两个内容 一个算法所耗费的时间 应该是该算法中每条语句的执行时间之和 而每条语句的执行时间是该语句的执行次数 也称为频度 与该语句执行一次所需时间的乘积 但是 当算法转换为程序之后 每条语句执行一次所需的时间取决于机器的指令性能 速度以及编译所产生的代码质量 这是很难确定的 假设每条语句执行一次所需的时间均是单位时间 一个算法的时间耗费就是该算法中所有语句的频度之和 于是 就可以独立于机器的软 硬件系统来分析算法的时间耗费 一般将算法求解问题的输入量称为问题的规模 并用一个整数表示 那么 算法的时间耗费就是问题规模的函数 例如 矩阵乘积问题的规模是矩阵的阶数 而一个图论问题的规模则是图中的顶点数或边数 一个算法的时间复杂度 TimeComplexity 也称时间复杂性 则是该算法的时间耗费 它是该算法所求解问题规模n的函数 一个算法的空间复杂度 SpaceComplexity 为该算法所耗费的存储空间 它也是问题规模n的函数 n是输入的规模或尺寸 一个算法的计算复杂性是输入规模的函数 当问题的规模n趋向无穷大时 把计算复杂度的数量级 阶 称为算法的渐近复杂度 一般情况下 算法的复杂性主要是指算法的渐近复杂度 例如 一个算法的计算复杂性 T n 2n3 3n2 2n 1 当n趋向无穷大时 显然有 这表明 当n充分大时 T n 和n3之比是一个不等于零的常数 即T n 和n3是同阶的 或者说T n 和n3的数量级相同 可记作T n n3 称T n n3 是算法的渐近复杂度 其中记号 是数学符号 其严格的数学定义是 若T n 和f n 是定义在正整数集合上的两个函数 则T n f n 表示存在正的常数C和n0 使得当n n0时都满足0 T n C f n 评价一个算法的计算复杂性的主要标准是算法复杂性的数量级 即算法的渐近复杂度 2 问题的复杂性问题的种类很多 比较重要的问题有两种形式 一是从可行解的集合中求出最优解的组合优化问题 另一是判定问题或判别问题 它只有两种可能的解 或者回答 yes 或者回答 no 图灵机是一种配有无限读 写纸带的有限状态机 它是一种实际的计算模型 若这种模型每执行一步计算 都有确定的下一步动作 则这种图灵机被称为确定型图灵机 DTM 反之 若每执行一步计算 其下一步动作有几种可能的选择而并不惟一确定 则称这种图灵机为非确定型图灵机 NTM 能够用多项式时间算法解决的问题 称为易处理的 若不能在多项式时间内解决的问题 则称之为难处理的 难处理的问题有时也称为难解的 根据解决问题的算法复杂性 问题被分成以下一些复杂性模型 1 P类 在确定型图灵机上 可在多项式时间内求解的所有问题 在多项式时间内即有求解问题的DTM程序 也就是有实际可用的算法 2 NP类 在非确定型图灵机上 可在多项式时间内求解的所有问题 也就是在多项式时间内有求解问题的NTM程序 P类包括在NP类中 对NP类问题 究竟有没有求解问题的多项式时间的确定型计算程序 即P是否等于NP 这是迄今为止悬而未决的著名难题 在研究问题的复杂性时 还可通过比较将问题按复杂程度分类 详细描述请参阅有关文献 6 2认证技术 6 2 1消息认证系统保密的目的是防止敌手破译系统中的机密信息 信息安全的另一个重要方面是保持信息的完整性 即防止敌手对系统进行主动攻击 如伪造信息 窜改信息等 认证 Authentication 是防止敌手主动攻击的一个重要技术 它对于开放环境中各种信息的安全有重要作用 认证的主要目的有两个 一是验证消息发送者和接收者的真伪 二是验证消息的完整性 即验证消息在传送或存储过程中是否被窜改 重放或延迟等 保密和认证是信息安全的两个重要方面 它们是两个不同属性的问题 一般而言 认证不能自动地提供保密 保密不能自然地提供认证功能 1 无仲裁认证系统在信息通信中 发信者向收信者发送的消息可能会被敌方或窜扰者截获并更改 甚至敌方可能会假冒发信者的身份向收信者发送假情报 收信者要想能判别出收到的消息是否来自真正的发信者而不是敌方 就需要在通信过程中使用消息认证技术 消息认证的过程可由图6 2表示 图6 2消息认证系统模型 在这个系统中 通信双方在通信开始前就要通过安全信道约定一个密钥 并在一段时间以后更换密钥 记S为信源消息的集合 称为信源消息空间 任何s S都是可能被发送的消息 概率大于0 E为所有编码规则的集合 称为密钥空间 任何密钥 或编码规则 e E都以大于0的概率被使用 M为所有可能被认证码字的集合 称为认证码空间 敌方在这个系统中可以任取下面一种方法进行攻击 1 在通信开始之前 敌方从认证码空间中选取一个认证码字m M 并发送给收信者 这种方式称为模仿伪造 Impersonation 如果收信者接受m为合法认证码字 则敌方伪造攻击成功 反之 如果收信者发现m不是合法认证码字并拒绝接受 则敌方伪造攻击失败 2 敌方可以等待通信中传送l个合法认证码字之后再进行攻击 他截获这l个合法认证码字 根据敌方对该系统的知识及这些合法认证码字提供的信息伪造一个认证码字m M 并发送给收信者 这种方式称为l级欺骗 Spoofing 如果收信者接受m为合法认证码字 并译作与这l个认证码字代表的信源消息不同的另外一个信源消息 则称敌方攻击成功 否则称敌方攻击失败 当l 1时 这种攻击方法又称为代换或替换伪造 Substitution 对于一个认证系统 如果敌方的上述两种攻击方法都不比随机从认证码空间中选取一个认证码字的成功概率大 则称该系统为完备的 但与完备保密概念不同的是 完备的认证系统不一定是安全的 比如当信源消息空间与认证码空间大小相同时 认证码空间中的任何码字都代表某一信源消息 因此任取一个认证码字进行欺骗 成功概率都为1 2 有仲裁认证系统在上述认证系统中 发信者与收信者是建立在共同利益基础上的 双方必须绝对相互信任 共同防范的就是敌方的攻击 但在实际应用中的许多方面 发信者与收信者的利益完全可以不一致 如在股票交易中 购买者与抛售者就没有共同的利益 如果使用上述认证系统 虽然敌方的攻击可以得到防护 但通信双方的相互欺骗则是无法防范的 甚至明知自己是受害者也拿不出可靠的证据 这就需要有一个新的认证系统 它要求有一个仲裁人能在通信双方发生争执时进行公正裁决 有仲裁的认证系统如图6 3所示 图6 3有仲裁认证系统模型 3 消息认证理论1987年Simmons给出了消息认证的信息理论 讨论了敌方欺骗时主要考虑模仿伪造和代换伪造两种形式 记pI为模仿伪造的成功概率 pS为代换伪造的成功概率 pd为敌方欺骗成功概率 由于敌方可以任意选择模仿伪造 代换伪造或l级欺骗 因此pd max pI pS 在Simmons的模型中 有pd max pI pS 当敌方使用模仿伪造进行欺骗时 最基本的方法就是从认证码空间中任选一个认证码字传送给收信者 其成功概率满足 6 12 这一不等式说明 要想很好地防止模仿伪造 必须使 M 比 S 大得多 即模仿伪造判决矩阵中有充分多的元素为0 式 6 12 中的等号当且仅当系统是没有分裂时成立 由于信源消息 编码规则或密钥 以及认证码字的取值都是不确定的 可以把它们看作具有一定概率分布的随机变量 记pM m p M m 为m是合法认证码字的概率 pME m e p M m E e 为编码规则是e且合法认证码字取值为m时的概率 定义认证函数 6 13 则对某一特殊的认证码字m 它为合法认证码字的概率可写为 6 14 式中 pE e 选取密钥为e的概率 作为一个密码分析者 在使用模仿伪造手段欺骗时 必定选取使自己成功概率最大的认证码字 因此pI max p m 6 15 对于模仿伪造的成功概率 Simmons证明它满足如下不等式 pI 2 I M E 6 16 式中 I M E M与E的互信息量 不等式右边的这一下限说明了这样的事实 为了使模仿伪造成功概率小 必须在认证码空间中含有关于密钥空间的大量信息 下面简单介绍消息认证系统的安全度量指标 定理6 4如果一个认证系统是L重完全保密的 则密钥数目 6 17 证明设e0是任一密钥 Ml M e0 且 Ml L 设Sl是任意L个信源消息构成的集合 假定不存在密钥el使Sl fel Ml 则p Sl Ml 0 p Sl 故认证系统不是L重完全保密的 因此矛盾 这说明对任意Sl S Sl L 都存在el E 使Sl fel Ml 由于 S k 故至少有个密钥e使Ml M e 因此得 如果一个认证系统是L重完全保密的 并使式 6 17 中的等号成立 则称为最优L重完全保密认证系统 它使L重认证保密系统的密钥量达到最小值 当敌方从信道观察到i个合法认证码字时 就可以试图伪造另外一个不同的认证码字 目的是让收信者当作合法认证码字接收 这种攻击就是i阶欺骗 记pdi为i阶欺骗成功的概率 则有下面的定理 定理6 5在有k个信源消息和v个认证码字的认证系统中 6 18 如果式 6 18 对0 i L都有等号成立 则称该系统对抗欺骗是L阶安全的 定义 LS LA 码为具有LS重完全保密且对抗欺骗是LA阶安全的认证码 希望这样的码具有最高阶的安全性并有一定认证功能 这就要使LS的值接近LA LS LS 1 码就是一种特殊情况 它考虑的是敌方可以在信道中引进新的认证码字 但不能改变信道中的码字的情况 在这种情况下 收信者可以只关心同一密钥作用下的LS个认证码字 如果敌方有能力改变信道中存在的码字 则 LS LS 码也是一类重要的认证码 定理6 6设一个认证码具有LS重完全保密性且对抗欺骗是LS 1阶安全的 则 6 19 6 2 2消息认证码和消息认证1 消息认证码在通信网中 信源若将消息传送给信宿 接收者信宿首先要确定收到的消息是否真正来自信源 其次还要验证来自信源的消息是否被别人修改过 有时信源也需要知道发出的消息是否被正确地送到目的地 这些都需要消息认证技术来解决 一个消息认证系统是由一个明文空间M 密钥空间K 密文空间C 一个认证函数f m k 与认证码集合A m k 共同组成 即S M K C f m k A 6 20 在消息认证系统中采用的密钥是收 发共用的单钥 而认证码a是要与密文一起传送的 若在通信网中 信源要向信宿发送具有认证标记的认证码 首先可按认证函数加密为r位认证码ar 即 ar f m k 6 21 式中 ar A m M k K 同时 明文m亦加密为密文c 并与ar一起传送至信宿 在接收端 信宿在收到认证码a r与密文c 以后 首先将密文c 解密为明文m 再在收端在同一密钥控制下 经认证函数f m k 加工成收端认证码r位a r 即 a r f m k 6 22 2 无条件安全认证码1974年 E N Gilbert M F J MacWilliams和N J A Sloane首先提出了认证码的概念 20世纪80年代 G J Simmions等人系统地发展了认证理论 在这样的系统中 总是假定信源和信宿互相信任 信源将要发送的源状态编码成消息后 经过一个公开信道传给信宿 信宿不仅要收到消息本身 而且要验证消息是否来自合法的发送者及消息是否经过窜改 假定敌手知道认证系统 惟一不知道的是信源和信宿用的哪一个编码规则 敌手不仅能截取和分析信道中传送的消息 而且可以伪造消息进行欺骗 因此 在一个没有仲裁的认证码中 敌手有两种攻击方法 一是模仿攻击 敌手在没有获得一个合法消息的情况下 在信道中传送一个伪造的消息 若信宿将其当作合法消息接收就认为攻击成功 二是替换攻击 敌手在信道中获得一个消息后 进行分析 将其替换成对应于不同源状态的消息 若信宿将其当作合法的消息接收 就认为攻击成功 对于任意取定的编码规则 如果这个编码规则将任意一个源状态编码成惟一一个消息 这样的认证码就叫没有分裂的认证码 否则称为有分裂的认证码 一个没有分裂的认证码是满足下面条件的三元组 S M E 1 S是源状态的有限集 且具有概率分布p s p s 0 2 E是编码规则的有限集 且具有概率分布p e p e 0 3 M是消息的有限集 4 对于任意的一个编码规则e E e是S到M中的一个一对一映射 5 任意一个消息m M m是某一个编码规则的象 由源状态的概率分布和编码规则的概率分布可以确定消息的概率分布p m 易知p m 0 3 消息认证消息认证是使授权的消息接收者检验收到的消息是否真实的一种方法 消息认证码方法是利用带密钥的单向杂凑函数 OnWayHashFunction f k 这里k是密钥 将要传送的消息x变换成一个固定r比特的消息认证码f k x 附在要传送的消息x后送出 以x f k x 表示 其中符号 表示数字的连接 一般而言 单向函数是公开的 密钥k是信源和信宿在一次通信中随机选取的 信宿在收到信源发送来的消息序列后 用它与信源商定的秘密密钥k 按照与信源同样的方法 用杂凑函数f k 将收到的消息前面的部分进行运算 得到相应的r比特 然后与接收的序列的后r比特进行比较 若它们相同 就认为接收到的序列是合法的 否则就认为消息中有错或遭到窜改 当主动攻击者在不知道密钥的情况下 随机的选取r比特碰运气 其成功的概率为2 r 当然 敌手也可以用单向杂凑函数的特点进行攻击 例如 生日问题 攻击等 消息检测码法是利用不带密钥的杂凑函数将要传送的消息变换成固定的r比特长的消息检测码 附在消息后面一起传送 有时也将它们加密后传送 以实现保密认证 消息检测码的功能与纠错码的功能相同 一个系统码就相当于一个消息检测码 4 单向杂凑函数长期以来 单向杂凑函数一直在计算机科学中使用 是现代密码学中一个很重要的概念 无论从数学上或其他的角度看 杂凑函数 HashFunction 就是将输入的消息串转换成输出串的一种函数 单向杂凑函数既是单向函数 又是杂凑函数 从输入串很容易计算其杂凑值 但要产生一个字符串使其杂凑值等于某一个特殊的值却是很困难的 单向杂凑函数主要有两类 带密钥的单向杂凑函数和不带密钥的单向杂凑函数 不带密钥的单向杂凑函数任何人都可以计算 它仅仅是输入字符串的函数 带密钥的单向杂凑函数是输入串和密钥的函数 只有持有密钥的人才能计算单向杂凑函数的值 对于一个杂凑函数h 任意取定一个消息x 若寻找一个消息x 使得h x h x 在多项式时间内是不可行的 就称这个杂凑函数为弱杂凑函数 对于一个杂凑函数h 寻找两个消息x1 x2 使得h x1 h x2 在多项式时间内是不可行的 就