分组密码3ppt课件.ppt

第3章分组密码 3 1概述 分组密码加解密速度快 易于标准化和便于软硬件实现 得到许多芯片的支持 通常是信息与网络安全中实现数据加密和认证的核心体制 它在计算机通信和信息系统安全领域有着最广泛的应用 分组密码 Blockcipher 是现代密码学的重要体制 是应用最为广泛 影响最大的一种密码体制 其主要任务是提供数据保密性 分组密码一般是指分组对称密码 第3章分组密码 3 1概述 也称块密码 它是将明文消息经编码表示后的二进制序列M x0 x1 xi 划分成若干长度为m的组块 Mi x0 x1 xm 1 各组分别在密钥k k0 k1 kt 1 的控制下转换成长度为n的密文分组Ci c0 c1 cn 1 其本质是一个从明文空间 m长的比特串的集合 M到密文空间 n长的比特串的集合 C的一一映射 1 一般而言 m n 即为无数据扩展和压缩的分组密码2 mn 有数据压缩的分组密码 第3章分组密码 3 2分组密码的设计原则与评估3 2 1分组密码的设计原则针对安全性的一般设计原则 1 明文分组长度和密钥长度望尽可能大 当分组长度较小时 攻击者通过穷举明文空间 得到密码变换规律 难于抵御选择明文攻击如果密钥量小 攻击者可以有效地通过穷举密钥 对密文进行解密 以得到有意义的明文 难于抵御唯密文攻击 2 混乱原则 指在加解密变换过程中明文 密钥以及密文之间的关系尽可能地复杂化 以防密码破译者采用解析法 建立并求解一些方程 进行破译攻击 混乱原则 具有复杂的非线性因素 3 扩散原则 密钥的每一比特影响密文的许多位 防止对密钥逐段破译 明文的每一位也影响密文的许多位 以隐蔽明文的统计特性 第3章分组密码 3 2分组密码的设计原则与评估3 2 1分组密码的设计原则针对实现的设计原则软件实现的设计原则子块 子块长度适合软件编程 如64位 128位等 简单运算 避免难于实现的按位置换 硬件实现的设计原则规则结构 以适用于用超大规模集成电路实现 第3章分组密码 3 2 2分组密码的评估 1 安全性评估中的最重要因素 包括下述要点 算法抗密码分析的强度 可靠的数学基础 算法输出的随机性 与其他候选算法比较的相对安全性 2 性能在各种平台上的计算效率和对存储空间的需求 3 算法和实现特性灵活性 硬件和软件适应性 算法的简单性等 第3章分组密码 3 3分组密码常见的设计方法乘积密码 以某种方式连续执行两个或多个密码 所得结果的密码强度将强于所有单个密码的强度 乘积密码常伴随一系列置换与替代操作 常见的乘积密码是迭代密码 Feistel和SPN是两种常用的分组密码设计结构 DES等分组密码采用Feistel结构 AES采用SPN结构 第3章分组密码 3 3分组密码常见的设计方法3 3 1Feistel结构Feistel结构是典型的迭代密码 Feistel结构的解密与加密是完全一样的 除了所使用的子密钥的顺序正好相反 第3章分组密码 3 3 2SPN结构 SPN结构也是一种特殊的迭代密码 SPN结构和Feistel结构相比 可以得到更快速的扩散 但是SPN密码的加解密通常不相似 3 4数据加密标准 DES DES是从1975年被美国联邦政府确定为非敏感信息的加密标准 第3章分组密码 DES是一个16轮的Feistel型结构密码 明文分组长度为64比特 密钥长度为64比特 其中 实用56比特 另8位用作奇偶校验 密文分组长度也为64比特 第3章分组密码 1 给定明文 通过一个固定的初始置换IP来重排输入明文块P中的比特 得到比特串P0 IP P L0R0 这里L0和R0分别是P0的前32比特和后32比特 初始置换IP 第3章分组密码 DES算法 DES算法 Feistel结构 2 按下述规则进行16次迭代 即1 i 16这里是异或 f是一个函数 称为轮函数 16个长度为48比特的子密钥Ki 1 i 16 是由密钥k经密钥编排函数计算出来的 Li 1 Ri 1 f Li Ri ki 第16轮迭代左右两块不交换 第3章分组密码 初始置换的逆置换IP 1 3 对比特串R16L16使用逆置换IP 1得到密文C 即C IP 1 R16L16 注意L16和R16的相反顺序 第3章分组密码 DES算法 第3章分组密码 密码函数f Ri 1 32位 Ki 1 32位 E Ri 1 48位 B1 B2 B3 B4 B5 B6 B7 B8 S1 S2 S3 S4 S5 S6 S7 S8 C1 C2 C3 C4 C5 C6 C7 C8 f Ri 1 Ki 32 位 P E E扩展 密钥加 S盒代换 P置换 有两个参数 分别为长度为32比特串Ri 1和长度为48比特串Ki 产生长度为32比特的输出 第3章分组密码 密码函数f E扩展 32比特的Ri 1根据扩展规则扩展为48比特长度的串 第3章分组密码 密码函数f 密钥加 计算并将结果写成8个比特串B B1B2B3B4B5B6B7B8 作为8个S盒 S1 S8 的输入 每个Bi是长度为6的比特串 记为Bi b1b2b3b4b5b6 S盒代换 每个S盒Si是一个固定的4 16阶矩阵 每行是0 15之间整数的一个置换 给Bi计算如下 1 b1b6两个比特确定了Si的行r的二进制表示 0 r 3 2 b2b3b4b5四个比特确定了Si的列c的二进制表示 0 c 15 3 Si Bi 定义成长度为4的比特串的值Si r c 由此可以算出Ci Si Bi 1 i 8 S盒的输出为 C C1C2C3C4C5C6C7C8 共32比特 第3章分组密码 S盒 SubstitutionBox 3 5数据加密标准 DES 48bit块通过S盒压缩成32bit块 48bit寄存器 32bit寄存器 6bit 4bit 共8个S盒 第3章分组密码 3 压缩替代S盒 SubstitutionBox 作用 将6个输入位映射为4个输出位 方法 若定义6个输入位为a1a2a3a4a5a6 a1代表第1位 a6代表第6位 将a1a6组成2位二进制数 对应S盒表中的行号 将a2a3a4a5组成一个4位的2进制数 对应S盒表中的列号 映射到交叉点的数据就是该S盒的输出 输入为101011的输出是 交叉点数据为9转化为二进制为 1001 a1a6 11 3 第3行 a2a3a4a5 0101 5 第5列 3 5数据加密标准 DES P置换 长度为32比特串C C1C2C3C4C5C6C7C8 根据固定置换P 进行置换 得到比特串P C 达到雪崩效应 第3章分组密码 密码函数f 可以看出 DES加密需要四个关键点 1 IP置换表和IP 1逆置换表 2 函数f 3 子密钥Ki 4 S盒的工作原理 DES算法的实现步骤 第3章分组密码 3 5数据加密标准 DES 密钥编排算法 根据密钥K来获得每轮中所使用的子密钥Ki 第3章分组密码 密钥 56bit PC 1 K1 C0 置换选择1 D0 LS1 LS1 C1 D1 LS2 LS2 C2 D2 PC 2 置换选择2 28bit 28bit 56bit K2 PC 2 56bit LS16 LS16 C16 D16 K16 PC 2 56bit 48bit 48bit 48bit 轮数 5749413325179 1585042342618 1025951432527 1911360524436 63554739312315 7625446383022 1466153453729 211352820124 1417112415 3281562110 2319124268 1672720132 415231374755 304051453348 444939563453 464250362932 置换选择PC 1 置换选择PC 2 子密钥生成器 置换选择 第3章分组密码 3 5数据加密标准 DES 第3章分组密码 DES结构 3 5数据加密标准 DES 第3章分组密码 3 4 2DES的安全性分析DES算法正式公开发表以后 引起了一场激烈的争论 1977年Diffie和Hellman提出了制造一个每秒能测试106个密钥的大规模芯片 造价昂贵1997年1月28日 美国的RSA公司在互联网上开展了一项名为 密钥挑战 的竞赛 悬赏一万美元 破解一段用56比特密钥加密的DES密文 1997年6月17日Rocke和志愿者们成功地找到了密钥 在计算机上公布了明文 Strongcryptographymakestheworldasaferplace 第3章分组密码 3 5 3三重DES为了增强DES算法的安全性 人们提出了许多DES的改进方案 其中 称为三重DES的多重加密算法是DES的一个重要的改进算法 第3章分组密码 3 5高级加密标准 AESAES是DES的替代者 1997年9月12日 NIST发布了征集算法的正式公告 要求AES具有128比特的分组长度 并支持128 192和256比特的密钥长度 而且要求AES要能在全世界范围内免费使用 2000年10月2日 Rijndael算法被选择为高级加密标准 AES的候选算法根据以下三条主要原则进行评判安全性代价算法与实现特性 3 5 1AES算法的数学基础AES中的运算是按字节的 并把一个字节看成是系数在有限域GF 2 上的次数小于8的多项式 即把一个字节看成是有限域GF 28 中的一个元素 一 有限域GF 28 可以把出b7b6b5b4b3b2b1b0构成的一个字节看成是系数在 0 1 中取值的多项式 b7x7 b6x6 b5x5 b4x4 b3x3 b2x2 b1x b0如 57 可写成 x6 x4 x2 x 1 第3章分组密码 1 多项式加法 在多项式表示中 两个元素的和是一个多项式 其系数是两个元素的对应系数的模2加 即异或 例如 57 和 83 的和为 57 83 D4 或者采用其多项式记法 57 01010111 x6 x4 x2 x 183 10000011 x7 x 1 x6 x4 x2 x 1 x7 x 1 x7 x6 x4 x2 11010100 D4显然 该加法与简单的以字节为单位的比特异或是一致的 2 多项式乘法 有限域GF 28 中两个元素的乘法为模2元域GF 2 上的一个8次不可约多项式的多项式乘法 对于AES这一8次不可约多项式为例 m x x8 x4 x3 x 1用十六进制表示为 11B 第3章分组密码 例 计算 57 83 x6 x4 x2 x 1 x7 x 1 x13 x11 x9 x8 x7 x7 x5 x3 x2 x x6 x4 x2 x 1 x13 x11 x9 x8 x6 x5 x4 x3 1而 x13 x11 x9 x8 x6 x5 x4 x3 1 modm x x13 x11 x9 x8 x6 x5 x4 x3 1 mod x8 x4 x3 x 1 计算时按降幂排 x7 x6 1所以 x6 x4 x2 x 1 x7 x 1 x7 x6 1 多项式表示 01010111 10000011 11000001 2进制表示 57 83 C1 16进制表示 第3章分组密码 3 x乘法 考虑用x乘以多项式B x b7b6b5b4b3b2b1b0 B x b7x7 b6x6 b5x5 b4x4 b3x3 b2x2 b1x b0 x B x b7x8 b6x7 b5x6 b4x5 b3x4 b2x3 b1x2 b0 x将上面的结果模m x 求余就得到x B x 如果b7 0 则 x B x b6x7 b5x6 b4x5 b3x4 b2x3 b1x2 b0 xmod x8 x4 x3 x 1 即所得结果字节为 b6b5b4b3b2b1b00 如果b7 1 则 x B x x8 b6x7 b5x6 b4x5 b3x4 b2x3 b1x2 b0 xmod x8 x4 x3 x 1 x8 b6x7 b5x6 b4x5 b3x4 b2x3 b1x2 b0 x x8 x4 x3 x 1 1 b6x7 b5x6 b4x5 b3x4 b2x3 b1x2 b0 x x4 x3 x 1 即所得结果字节为 b6b5b4b3b2b1b00 00011011 第3章分组密码 第3章分组密码 例1 f x x6 x4 x2 x 1 g x x7 x 1 m x x8 x4 x3 x 1 求f x g x modm x 求 57 83 现在我们用二进制运算的方法来计算 即 10000011 首先要求出x幂乘的中间结果 01010111 00000010 10101110 01010111 00000100 10101110 00000010 01011100 00011011 01000111 01010111 00001000 10001110 01010111 00010000 00011100 00011011 00000111 01010111 00100000 00001110 01010111 01000000 00011100 01010111 10000000 00111000 所以 01010111 10000011 01010111 00000001 10000000 01010111 10101110 00111000 11000001 等价于x7 x6 1 第3章分组密码 二 GF 28 域上的多项式一个 4字节 字可以看作是GF 28 域上的多项式 每个字对应于一个次数小于4的多项式 1 多项式加法多项式加法通过对应的系数简单相加可以实现 2 多项式乘法GF 28 域上的多项式乘法为模M x x4 1的乘法 3 5 2AES算法总体描述 轮数 密钥长度的关系 AES算法加密的实现 1 明文分组和密钥的组织排列方式 Fig2 1 以明文分组为128bits为例组成的阵列 3 5 2AES算法总体描述 AES加解密流程图 1 给定一个明文M 将轮密钥与M异或 称为轮密钥加 2 对前9轮中的每 轮 用s盒进行一次字节代换操作 对替换的结果做行移位操作 再对结果做列混淆变换 然后进行 轮密钥加操作3 在最后一轮中依次进行字节代换 行移位 列混淆操作 4 得到密文C 3 5 2AES算法总体描述 AES特点 3 5 2AES算法总体描述 每一轮加密的过程 中间态数据有的地方也被记为State 3 5 2AES算法总体描述 AES算法加密的实现 1 明文分组和密钥的组织排列方式 Fig2 1 以明文分组为128bits为例组成的阵列 3 5 2AES算法总体描述 1 字节代换 SubBytes S盒的替换操作 3 5 3算法的基本变换 1 字节代换 SubBytes S盒的替换表 3 5 3算法的基本变换 1 字节代换 SubBytes 设输入字节为A a0a1a2a3a4a5a6a7 1 先将该字节A变换为有限域GF 2 中的乘法逆元素T T A 1modm x m x x8 x4 x3 x 1即A T T A 1modm x 2 对X作GF 2 上的仿射变换 Y M T B 3 5 3算法的基本变换 S盒字节代换举例 3 5 3算法的基本变换 2 行移位变换ShiftRows 在行移位 ShiftRows 变换中 状态矩阵中的每一行将以字节为单位 循环右移不同的位移量 3 列混合变换MixColumns 列混合变换MixColumns 对一个状态逐列进行变换 它将一个状态的每一列视为有限域GF 28 上的一个多项式 在列混合变换中 每一列所表示的多项式将乘以一个固定的多项式C x C x 03 x3 01 x2 01 x 02 对应4字节向量为 03010102 模多项式为 x4 1 列混淆的数学基础 b0c0c3c2c1a0b1 c1c0c3c2a1b2c2c1c0c3a2b3c3c2c1c0a3 列混淆的数学基础 b002030101a0b1 01020301a1b201010203a2b303010102a3 AES中 AddRoundKey 轮密钥加 将轮密钥与中间态数据 State 按比特异或 轮密钥是通过KeySchedule过程从密码密钥中得到的 轮密钥长度等于分组长度 K3 3 K3 3 B3 3 mod2 AES每轮密钥加操作 需要128bit 16字节 4个字 的轮密钥 算法中有11次轮密钥操作 故AES算法共需要44个字长度的密钥 密钥扩展 K4的生成 下页K5 K6 K7的生成 如右 ByteSubstitution ByteRotKte Rcon K4的生成 Wi 4 Wi 3 Wi 2 Wi 1 Wi ByteSubstituion ByteRotKte Rcons KeyexpKnsion 4 i 4 Rnd 1 imod4 0 imod4 0 轮密钥选取 轮密钥0 轮密钥1 轮密钥2 第