通信原理教程13.ppt

1 第十三章通信安全 13 1概述通信安全的基础 密码学密码编码学密码分析学通信不安全因素被破译被攻击 被伪造和篡改认证 防止被攻击的手段认证的目的 验证信息发送者真伪验证接收信息的完整性 是否被篡改了 是否被重复接收了 是否被拖延了 认证技术 包括消息认证 身份验证和数字签字 2 密码编码学内容 将消息加密的方法将已加密的消息解密的方法密码分析学内容 如何破译密文和伪造密文 密码学的基本术语明文 待加密的消息密文 加密后的消息密码 用于加密的数据变换集合密钥 用于表示加密变换的参数密码种类 单密钥密码公共密钥密码 也称为双密钥密码 3 13 2单密钥加密通信系统例 密钥Z m序列加密算法 模2加法解密算法 仍是模2加法一般算法 令F为产生密文Y的可逆变换 即有Y F X Z FZ X 在接收端 密文Y用逆变换F 1恢复成原来的明文X 即X F 1 Y Z FZ 1 Y FZ 1 FZ X 4 13 3分组密码和流密码分组密码加密过程原理连续的分组用相同的密钥加密 若有一个特定的分组明文和以前的一个分组相同 则加密后两者的密文也相同 目标是使明文的任1比特都不会直接出现在密文中 5 流密码原理 对明文的逐个比特进行不同的变换 例 二进制加性流密码令xn yn和zn分别表示在n时刻明文比特 密文比特和密钥流比特 则有式中 N是密钥流的长度 因为在模2运算中加法和减法是一样的 所以上式也可以写为因此 同样的装置既可以用于加密 也可以用于解密 6 密钥流应当尽可能地近似于一个完全随机的序列 若密钥流是一个m序列 则图中的密钥流产生器就是一个m序列产生器 密钥则是控制此m序列的生成多项式和同步信息等 二进制加性流密码没有错误传播 在密文中一个错误比特解密后只影响输出中的相应比特 分组密码可能有错误传播 使明文分组中很少几个比特的改变在密文输出中产生很多比特的变化 分组密码的这种错误传播性质在认证中很有价值 因为它使敌方的破译人员不可能修改加密后的数据 除非知道密钥 流密码通常较适用于通过易出错的通信信道传输数据 用于要求高数据率的应用中 例如视频保密通信 或者用于要求传输延迟很小的场合 7 对通信安全的基本要求假设 敌方破译人员知道所用加密法的全部机理 只是不知道密钥 密码分析性攻击的形式 仅对密文的攻击对已知明文的攻击对选定的明文的攻击对选定的密文的攻击实际中常发生的是仅对密文的攻击 例 使用语言的统计结构知识 例如 英文字母e的出现概率是13 以及字母q的后面总跟随着u 和关于某些可能的字的知识 例如 一封信的开头中可能有 先生 或 女士 两字 仅对密文的攻击是一个密码系统受到的最轻的威胁 因此 任何系统若不能战胜这种攻击 则被认为是完全不安全的系统 8 13 4用信息论研究密码的方法香农模型的假定 敌方破译人员具有无限的时间和无限的计算能力 敌方仅限于对密文攻击 香农的密码分析定义 给定密文以及各种明文和密钥的先验概率 搜寻密钥的过程 当敌方破译人员获得密文的唯一解时 就成功地解密了 香农对安全性的基本度量 互信息量I X Y 令X X1 X2 XN 表示一个N比特的明文消息 Y Y1 Y2 YN 表示相应的N比特密文 假定 密钥Z服从某种概率分布H X X的不确定性H X Y 给定Y后X的不确定性I X Y H X H X Y X和Y之间的互信息量 9 13 4 1完善安全性完善安全性定义假定 破译人员只能够看到密文Y 则一个保密系统的完善安全性定义为 明文X和密文Y之间是统计独立的 即有I X Y 0于是 由I X Y H X H X Y 可以求出H X Y H X 上式表明 敌方破译人员最多只能 按照所有可能消息的概率分布 从给定的密文Y 去猜测明文消息X 10 香农基本界给定密钥Z后 有H X Y H X Z Y H Z Y H X Y Z 当且仅当Y和Z共同唯一地决定X时 H X Y Z 0 当使用已知密钥Z解密时 这是一个很有价值的假定 因此 我们可以将式H X Y H X Z Y H Z Y H X Y Z 简化如下 H X Y H Z Y H Z 将上式代入式H X Y H X 得知 为使一个保密系统给出完善的安全性 必须满足条件H Z H X 它表明为了达到完善安全性 密钥Z的不确定性必须不小于被此密钥所隐蔽的明文X的不确定性 11 一次一密密码原理方框图 一种流密码 其密钥和密钥流相同 并且密钥只使用一次 密文yn xn zn n 1 2 式中 xn 消息比特序列 zn 统计独立和均匀分布的密钥比特序列 一次一密密码是完善安全的 因为消息和密文之间的互信息量为0 所以它是完全不可解密的 12 13 4 2唯一解距离对于一个用非完善密码加密的密文 可以预期 当截获的文件量随时间增大到某一点时 破译人员用无限的时间和无限的计算能力 将能够找到密钥并从而破译了密文 在香农的模型中 破译人员能破译此密文的临界点称为唯一解距离 唯一解距离的定义 使条件熵H Z Y1 Y2 YN 近似为0的最小N 对于一类特殊的 随机密文 唯一解距离近似由下式给出 式中 H Z 密钥Z的熵 Ly 密文字符集的大小 r N比特密文中所含信息的冗余度百分比 即式中 H X 为明文X的熵 13 在大多数保密系统中 密文字符集的大小Ly和明文字符集的大小Lx一样 在这种情况下 r就是明文本身的冗余度百分比 求H Z 令K 密钥Z中的数字数目 这些数字是从大小为Lz的字符集中选用的 则可以将密钥Z的熵表示如下 当且仅当密钥是完全随机的时 上式等号成立 令Lz Ly 并完全随机地选择密钥以使唯一解距离最大 然后 将H Z Klog2Lz代入得到 N0 K r 14 N0 K r例 考察一个Lx Ly Lz保密系统 它用于对英文文本加密典型英文文本的r大约等于75 因此 按照上式 一个破译人员在仅截获约1 333K比特的密文数据后 就能破译此密码 其中K是密钥长度 值得注意 非完善密码仍然有实用价值 15 13 4 3数据压缩在密码编码中的作用数据压缩能除去冗余度 因此增大了唯一解距离 13 4 4扩散与混淆扩散 将明文中一个比特的影响扩散到密文中很多比特 从而将明文的统计结构隐藏起来 混淆 采用数据变换 使密文的统计特性与明文的统计特性之间的关系更为复杂 乘积密码 由一些简单的密码分量相继加密构成 这些较简单的密码分量分别能使最终的密码有适度的扩散和混淆 例 乘积密码用 替代密码 和 置换密码 作为基本分量 16 替代密码 明文的每个字符用一种固定的替代所代替 代替的字符仍为同一字符表中的字符 特定的替代规则由密钥决定 若明文为X x1 x2 x3 x4 式中 x1 x2 x3 x4 为相继的字符 则变换后的密文为Y y1 y2 y3 y4 f x1 f x2 f x3 f x4 式中 f 是一个可逆函数 例 密文的字符表从此表中可以看到 第一个字符U替代A 第二个字符H替代B 等等 使用替代密码可以得到混淆 17 置换密码 明文被分为具有固定周期d的组 对每组作同样的交换 特定的交换规则是由密钥决定的 若周期d 4 交换规则为则明文中的字符x将从位置1移至密文中的位置4 一般而言 明文X x1 x2 x3 x4 x5 x6 x7 x8 将变换成密文Y x3 x4 x2 x1 x7 x8 x6 x5 虽然密文Y中单个字符的统计特性和明文X中的一样 但是高阶统计特性却改变了 使用置换密码可以得到扩散 18 将替代和置换作交织 并将交织过程重复多次 就能得到具有良好扩散和混淆性能的保密性极强的密码 例 设明文消息为THEAPPLESAREGOOD使用交换字符表作为替代密码 则此明文将变换为如下密文 IYCUWWKCZUOCVRRA下一步我们将交换规则用于置换密码 则从替代密码得到的密文将进一步变换成UCIYCKWWCOZUARVR这样 上面的密文和原来的明文相比 毫无共同之处 19 13 5数据加密标准 美国政府标准算法DESDES采用扩散和混淆算法 是一种保密性很强的密码 它对64b长的明文数据分组运算 所用的密钥长度为56b DES算法中 总变换 P 1 F P X 其中X 明文 P 某种交换 F 包括替代和置换 由某些函数f的级连构成 20 DES算法流程图第1次初始交换后 64b的明文分为左半部L0和右半部R0 每半部长32b 完成16轮交换 其中第i轮交换 Li Ri 1 i 1 2 16Ri Li 1 f Ri 1 Zi i 1 2 16式中 Zi 在第i轮中使用的密钥 此密钥的长度为48b 第16轮运算的结果 经过颠倒后 得到R16L16 再经过最后一次交换P 1 就产生出64b的密文 为了解密 函数f 不必须是可逆的 因为 Li 1 Ri 1 能够从 Li Ri 直接恢复 Ri 1 Lii 1 2 16Li 1 Ri f Li Zi i 1 2 16 21 计算f 的流程图扩展 R 32b R 48b 方法 重复每个相继的4比特字的两端比特 若R r1r2r3r4r5r6r7r8 r29r30r31r32则扩展后R r32r1r2r3r4r5r4r5r6r7r8r9 r28r29r30r31r32r1R 和Zi模2相加 再将相加结果分成8个6b的字 B1B2 B8 R Zi 22 每个6b的字Bi输入到一个替代方框Si 后者用查表的方法产生出一个4b的输出Si Bi Si Bi 是6b字Bi的布尔函数 8个输出Si输入到交换方框P 交换所得就是所要求的32b的函数f R Zi f R Zi P S1 B1 S2 B2 S8 B8 23 密钥进程计算 决定每个Zi所用的过程流程图各Zi使用密钥Z0的不同子集 密钥Z0在位置8 16 64上有8个监督比特 用于在对应的8b字节中进行错误检测 交换选择1 丢掉Z0的监督比特 然后存入两个28b的移存器中 24 作16次迭代运算 每次迭代包括一次或两次循环左移 然后进行 交换选择2 输出就是第1次至第16次迭代用的不同的48b密钥分组Z1 Z2 Z16 25 13 6公共密钥密码编码方法13 6 1基本原理公共密钥系统中 用两种算法去计算两个不可逆函数 变换 令这两种算法用 Ez 和 Dz 表示 Ez fz x y 公共密钥 公钥 Dz fz 1 y x 秘密密钥 私钥 式中 x 在某个函数fz的域中的一个输入消息 y 在fz取值范围内相应的密文 基本要求 函数fz必须是一个单向函数 公钥和私钥的两个基本性质 消息被这对密钥之一加密后 能够用另一个密钥解密 知道公钥后 不可能计算出私钥 将此系统的用户姓名 地址和公钥列于一本 电话簿 中 当一个用户需要向另一个用户发送保密消息时 查此 电话簿 用对方的公钥对消息加密 加密的消息只能由持有对应私钥的用户阅读 26 13 6 2Diffie Hellman公共密钥分配系统基本原理 令离散指数函数为Y Xmodp1 X p 1式中 一个整数 并且是一个本原元 因此 X是Y的以 为底的模p离散对数 X log Ymodp1 Y p 1使用 平方的乘积 法 很容易从X计算Y 例如 对于X 16 有Y 16 2 2 2 2另一方面 从Y计算X则难得多 应用方法 假定所有用户都知道 和p 若有一用户i 从一组整数 1 2 p 中 均匀地选择一个独立随机数Xi 作为私钥 并将离散指数Yi Ximodp和用户姓名及地址一起放在 公共电话簿 中 其他用户也如此做 27 假设用户i和j希望进行保密通信 为此 用户i从 公共电话簿 中取出Yj 并用私钥Xi计算用户j用同样方法计算Kij 因为Kji Kij所以 用户i和j可将Kji看作是普通保密系统中的密钥 敌方若想得到Kji 必须用从 公共电话簿 中得到的Yi和Yj 按照下列公式去计算Kji 上式因为包含离散对数故难于计算 28 13 7RSA算法13 7 1RSA公共密钥密码系统基本原理 RSA算法是一种分组密码 其理论基础是 求出一个随机的大素数不难 但是将两个这种数的乘积分解因子目前认为是不可能的 算法 随机选择两个很大的素数p和q p q 将p和q相乘 得到乘积pq n使用下式求出欧拉函数 n n p 1 q 1 从欧拉函数 n 的定义可知 上式给出小于n的正整数i的数目 且i和n的最大公因子等于1 即i和n互为素数 例 设p 3 q 5 则n 15 n 3 1 5 1 8 它表示小于15且和15互素的正整数i共有8个 它们是 1 2 4 7 8 11 13 14 29 令e是一个小于 n 的正整数 它使e和 n 的最大公因子等于1 这样 求出一个小于 n 的正整数d 它使de 1mod n RSA的单向函数由计算下式中的离散指数定义 fz x xe ymodn将n和e值组成公共密钥 公布计算函数fz的算法Ez 它很容易找到 就相当于公布n和e的值 素数p和q组成秘密密钥 知道素数p和q后 就容易求出逆函数fz 1 fz 1的定义是fz 1 y ydmodn使用式de 1mod n 能求出解密指数d 即de n Q 1式中 Q是某个整数 y xe 利用欧拉的一个著名定理 即对于任何正整数x和n x n 有 将其代入de n Q 1 得到yd x它表明 知道素数p和q后 就容易求出逆函数fz 1 30 RSA密码算法的安全性依赖于如下前提 求fz的逆函数的任何方法等效于求分解n pq的方法 这样就产生了一个问题 用分解n的方法进行攻击可能吗 答案是不可能的 若素数p和q分别由100位以上十进制数字组