信息安全导论密码基础对称密码.ppt

1 密码基础 对称密码 信息安全导论 模块4 密码基础 2 现代密码学 密码体制的分类 对称 非对称分组 序列 3 分组密码的设计原则 混乱 所设计的密码应使得密钥 明文以及密文之间的依赖关系相当复杂 以至于这种依赖性对密码分析者来说是无法利用的扩散 所设计的密码应使得密钥的每一位数字影响密文的许多位数字 以防止对密钥进行逐段破译 而且明文的每一位数字也应影响密文的许多位数字 以便隐蔽明文数字统计特性 4 典型的分组密码算法 DES DES的历史1971年 IBM 由HorstFeistel领导的密码研究项目组研究出LUCIFER算法 并应用于商业领域1973年美国标准局征求标准 IBM提交结果 之后被选为数据加密标准 5 分组密码的例子 DES DES是1975年被美国联邦政府确定为非敏感信息的加密标准 它利用64比特长度的密钥K来加密长度为64比特的明文 得到64比特长的密文1997年 由于计算机技术迅速发展 DES的密钥长度已经太短 NIST建议停止使用DES算法作为标准 目前 二重DES和三重DES仍然广泛使用 5 6 DES算法的整体结构 Feistel结构DES算法的轮函数DES算法的密钥编排算法DES的解密变换 7 DES算法的整体结构 Feistel结构 7 输入 IP 16轮迭代 IP 1 输出 密钥编排 K1 K16 8 DES算法的整体结构 Feistel结构 1 给定明文 通过一个固定的初始置换IP来重排输入明文块P中的比特 得到比特串P0 IP P L0R0 这里L0和R0分别是P0的前32比特和后32比特 8 初始置换IP 9 DES算法的整体结构 Feistel结构 2 按下述规则进行16次迭代 即1 i 16这里是对应比特的模2加 f是一个函数 称为轮函数 16个长度为48比特的子密钥Ki 1 i 16 是由密钥k经密钥编排函数计算出来的 Li 1 Ri 1 f Li Ri ki 第16轮迭代左右两块不交换 10 DES算法的整体结构 Feistel结构 10 初始置换的逆置换IP 3 对比特串R16L16使用逆置换IP 1得到密文C 即C IP 1 R16L16 11 分组密码的轮函数 函数f以长度为32比特串Ri 1作为第一输入 以长度为48比特串Ki作为第二个输入 产生长度为32比特的输出 11 12 分组密码的轮函数 13 分组密码的轮函数 E扩展 Ri 1根据扩展规则扩展为48比特长度的串 14 E扩展 32bit扩展到48bit 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 9 8 8 4 5 9 9 1 32 32 32 15 分组密码的轮函数 密钥加 计算 并将结果写成8个比特串 每个6比特 B B1B2B3B4B5B6B7B8 16 分组密码的轮函数 S盒代换 6入4出 查表8个S盒S1 S8 每个S盒是一个固定的4 16阶矩阵 其元素取0 15之间的整数 输入6比特b1b2b3b4b5b6 输出如下1 b1b6两个比特确定了S盒的行2 b2b3b4b5四个比特确定了S盒的列3 行 列确定的值即为输出 16 17 17 18 18 例如 输入101100 行 10 2 列 0110 6输出2 即0010例如 输入111001 行 11 3 列 1100 12输出10 即1010 19 分组密码的轮函数 19 P置换 长度为32比特串C C1C2C3C4C5C6C7C8 根据固定置换P 进行置换 得到比特串P C 20 DES算法的密钥编排算法 根据密钥K来获得每轮中所使用的子密钥Ki 20 K PC 1 C0 D0 C1 D1 C16 D16 LS1 LS1 LS2 LS16 LS2 LS16 PC 2 PC 2 K1 K16 64 28 28 56 48 21 DES算法的密钥编排算法 1 给定64比特密钥K 根据固定的置换PC 1来处理K得到C0D0 其中C0和D0分别由最前和最后28比特组成 22 DES算法的密钥编排算法 2 计算Ci LSi Ci 1 和Di LSi Di 1 且Ki PC 2 CiDi LSi表示循环左移两个或一个位置 具体地 如果i 1 2 9 16就移一个位置 否则就移两个位置PC 2是另一个固定的置换 23 DES算法的密钥编排算法 24 DES的解密变换 DES的解密与加密一样使用相同的算法 它以密文y作为输入 但以相反的顺序使用密钥编排K16 K15 K1 输出的是明文x 25 DES加密的例子 设16进制明文X为 0123456789ABCDEF密钥K为 133457799BBCDFF1去掉奇偶校验位后 以二进制表示的K加密后的密文为 26 DES的核心是S盒 除此之外的计算是线性的S盒作为该密码体制的非线性组件对安全性至关重要 S盒的设计准则 S盒不是它输入变量的线性函数改变S盒的一个输入位至少要引起两位的输出改变对任何一个S盒 如果固定一个输入比特 其它输入变化时 输出数字中0和1的总数近于相等 27 分组密码的分析方法 如果密码分析者能够确定正在使用的密钥 则他就可以像合法用户一样阅读所有消息 则称该密码是完全可破译的如果密码分析者仅能从所窃获的密文恢复明文 却不能发现密钥 则称该密码是部分可破译的 28 DES的破解 DES的实际密钥长度为56 bit 就目前计算机的计算能力而言 DES不能抵抗对密钥的穷举搜索攻击 1997年1月28日 RSA数据安全公司在RSA安全年会上悬赏10000美金破解DES 克罗拉多州的程序员Verser在Inrernet上数万名志愿者的协作下用96天的时间找到了密钥长度为40 bit和48 bit的DES密钥 1998年7月电子边境基金会 EFF 使用一台价值25万美元的计算机在56小时之内破译了56 bit的DES 1999年1月电子边境基金会 EFF 通过互联网上的10万台计算机合作 仅用22小时15分就破解了56 bit的 ES 不过这些破译的前提是 破译者能识别出破译的结果确实是明文 也即破译的结果必须容易辩认 如果明文加密之前经过压缩等处理 辩认工作就比较困难 29 DES算法的公开性与脆弱性 DES的两个主要弱点 密钥容量 56位不太可能提供足够的安全性S盒 可能隐含有陷井 Hiddentrapdoors DES的半公开性 S盒的设计原理至今未公布 30 DES小结 充分混乱 密钥 明文以及密文之间的依赖关系相当复杂充分扩散 密钥的每一位数字影响密文的许多位数字 明文的每一位数字也应影响密文的许多位数字 31 密码分析的几种情况 根据攻击者掌握的信息 密码分析分为仅知密文攻击 攻击者除了所截获的密文外 没有其他可以利用的信息已知明文攻击 攻击者仅知道当前密钥下的一些明密文对选择明文攻击 攻击者能获得当前密钥下的一些特定的明文所对应的密文选择密文攻击 攻击者能获得当前密钥下的一些特定的密文所对应的明文 32 分组密码序列密码 流密码 33 流密码 序列密码 分组密码将待加密的明文分为若干个字符一组 逐组进行加密流密码将待加密的明文分成连续的字符或比特 然后用相应的密钥流对其进行加密密钥流由种子密钥通过密钥流生成器产生 34 流密码基本原理 通过随机数发生器产生性能优良的伪随机序列 密钥流 使用该序列加密信息流 逐比特加密 得到密文序列 种子密钥K 随机数发生器 加密变换 密钥流Ki 明文流mi 密文流Ci 35 按照加解密的工作方式 流密码分为同步流密码和自同步流密码 36 同步流密码密钥流的产生完全独立于消息流 明文流或者密文流 特点 无错误扩散 如果传输过程产生一位错误 只影响当前位的解密结果 不影响后续位自同步流密码 37 同步流密码 密钥流生成器的内部状态 F 状态转移函数G 密钥流产生函数 38 同步流密码自同步流密码每一个密钥字符是由前面n个密文字符参与运算得到的特点 有错误扩散 如果传输过程中产生1位错误 则错误会传播n个字符 收到n个正确的密文字符后 密码系统会实现重新同步 39 自同步流密码 密钥流生成器的内部状态 F 状态转移函数G 密钥流产生函数 40 二元加法流密码 目前使用最多的流密码明文m 密文c 密钥k都为0 1序列 运算为模2加 异或 加密 解密 41 二元加法流密码 符号描述与示例加密操作 密钥流 k1 k2 k3 明文流 m1 m2 m3 密文流 c1 c2 c3 解密操作 密钥流 k1 k2 k3 密文流 c1 c2 c3 明文流 m1 m2 m3 例 电报内容 专列下午2点到达 的加密过程如下 密钥流 78 35 02 E4 B2 明文流 D7 A8 C1 D0 CF C2 CE E7 32 B5 E3 B5 BD B4 EF A1 A3 密文流 AF 9D C3 34 7D 42 二元加法流密码算法的安全强度完全取决于密钥流的特性如果密钥流是无限长 无周期的完全随机的序列 则这种密码就是 一次一密 的密码体制 仙农曾证明它是不可破译的但实际应用中 密钥流都是由有限存储和有限复杂的逻辑电路产生的字符序列 因此是有周期性的 不是真正的随机序列要设计周期尽可能长 随机性尽可能好的 近似真正的随机序列 做密钥流 43 Golomb随机性假设 在序列的一个周期内 0与1的个数相差至多为1在序列的一个周期圈内 长为1的游程数占总游程数的1 2 长为2的游程数占总游程数的 长为i的游程数占总游程数的且在等长的游程中 0 1游程各占一半序列的异相自相关函数为一个常数 44 第一个条件说明 01序列中0和1出现的概率 基本 相同第二个条件说明 在已知位置n前若干位置上的值的条件下 0与1在第n位置上出现的概率是相同的第三个条件说明 若将原序列 ai 与序列的移位 ai j 比较 无法得到关于ai的实质性信息 如 周期 45 把满足Golomb随机性假设的序列称为伪随机序列流密码最核心的问题是密钥流生成器的设计密钥流生成器一般由线性反馈移位寄存器 LinearFeedbackShiftRegister LFSR 和一个非线性组合函数构成 46 反馈移位寄存器 由寄存器和反馈函数组成移位寄存器 可用来存储数据 脉冲到来时 移位寄存器所有位右移一位 最右边移出位为输出 最左边输入位由反馈函数的输出填充反馈函数是n元 a1 a2 an 的布尔函数 47 二元加法流密码 续 工作原理移位寄存器中所有位右移一位 最右边移出的位是输出位 最左端的一位由反馈函数的输出填充 反馈函数f a1 an 是n元 a1 an 的布尔函数 移位寄存器根据需要不断地进动m拍 便有m位的输出 形成输出序列o1o2 om 48 二元加法流密码 续 例 图示为一个3 级反馈移位寄存器 反馈函数f x b3 b2 初态为 100 输出序列生成过程 状态输出位100 0110 0011 1101 1110 0011 1101 1110 0因此 对应初态 100 的输出序列为 0011011011 周期为3 b3 b2 b1 t2 t3 a 移位寄存器结构图 110 011 101 初态 100 b 状态转移图 1 1 0 c 序列圈 0 49 二元加法流密码 续 当反馈移位寄存器的反馈函数是异或变换时 这样的反馈移位寄存器叫线性反馈移位寄存器 如图所示 50 二元加法流密码 续 移位寄存器中存储器的个数称为移位寄存器的级数 移位寄存器存储的数据为寄存器的状态 状态的顺序从左到右依次为从最高位到最低位 在所有状态中 叫初态 并且从左到右依次称为第一级 第二级 第n级 亦称为抽头1 抽头2 抽头3 抽头n n级线性反馈移位寄存器的有效状态为个 它主要是用来产生周期大 统计性能好的序列 51 二元加法流密码 续 非线性组合部分主要是增加密钥流的复杂程度 使密钥流能够抵抗各种攻击 对流密码的攻击手段主要是对密钥流进行攻击 以线性反馈移位寄存器产生的序列为基序列 经过不规则采样 函数变换等 即非线性变换 就可以得到实用安全的密钥流 52 几种常见的流密码算法 流密码算法没有公开的国际标准 大多数设计 分析成果都是保密的1 A5算法法国 欧洲数字蜂窝移动电话系统 GSM 中使用的序列密码加密算法用于从手机到基站的连接加密 A5 1 A5 22 Rambutan算法英国的算法 由通信电子安全组织设计3 RC4算法由RonRivest于1987年为RSA数据安全公司设计的可变密钥长度的序列密码 广泛用于商业密码产品中 4 SEAL算法IBM公司的PhilRogaway和DonCoppersmith设计的一种易于用软件实现的序列密码 53 对称密码体制使用中存在的问题 密钥分配问题 通信双方要进行加密通信 需要通过秘密的安全信道协商加密密钥 而这种安全信道可能很难实现密钥管理问题 在有