密码学03-分组密码体制

本 科 生 学 位 课 ： 现 代 密 码 学第 三 章 分 组 密 码 体 制主 讲 教 师 ： 董 庆 宽研 究 方 向 ： 密 码 学 与 信 息 安 全Email ： 个 人 主 页 ： http:/ 2/155 3.1 分 组 密 码 概 述3.2 数 据 加 密 标 准 DES3.3 差 分 密 码 分 析 和 线 性 密 码 分 析3.4 分 组 密 码 的 运 行 模 式3.5 IDEA 3.6 AES Rijndael本 章 提 要 3/155 3.1 分 组 密 码 概 述 分 组 密 码 (Block Cipher) ：l 将 明 文 消 息 分 组 ， 逐 组 加 密 ； 对 称 密 码 算 法 ， 属 于 代 换 密 码l 将 明 文 消 息 编 码 表 示 后 的 数 字 序 列 x0,x1,xi,划 分 成 长 为 n的 组x=(x0,x1,xn-1)l 各 组 （ 长 为 n的 矢 量 ） 分 别 在 密 钥 k=(k0,k1,kt-1)控 制 下 变 换 成 输 出序 列 y=(y0,y1,ym-1)（ 长 为 m的 矢 量 ） l 其 加 密 函 数 E： Vn KVm， Vn和 Vm分 别 是 n维 和 m维 矢 量 空 间 ， K为 密 钥 空 间 ， 如 图 所 示 。 4/155 与 流 密 码 不 同 之 处 ：l (1)分 组 加 密 。 在 于 输 出 的 每 一 位 数 字 不 是 只 与 相 应 时 刻 输 入 的 明文 数 字 有 关 ， 而 是 与 一 组 长 为 n的 明 文 数 字 有 关 。l (2)无 记 忆 性 。 在 相 同 密 钥 下 ， 分 组 密 码 对 长 为 n的 输 入 明 文 组 所 实施 的 变 换 是 等 同 的 ， 所 以 只 需 研 究 对 任 一 组 明 文 数 字 的 变 换 规 则 。这 种 密 码 实 质 上 是 字 长 为 m的 数 字 序 列 的 代 换 密 码 。 算 法 的 输 入 长 度 和 输 出 长 度l 通 常 取 m=n (用 于 加 密 ) l 若 mn， 则 为 有 数 据 扩 展 的 分 组 密 码 (用 于 认 证 )l 若 m 。l 另 一 方 面 ， 对 每 个 不 同 的 密 钥 ， DES都 定 义 了 一 个 映 射 ， 总 映 射 数 为2 561017N/2， 则 令l Kk1,k2,kc 如 果 T|Tmin N/2 |,将 Tmax对 应 的 候 选 者 Kn(i)作 为 Kn， 并 猜定 Kk1,k2,kc 0(p1/2)或 1 (p6有 所 不 同 。 当 Nk6时 ， 扩 展 算 法 如 下l KeyExpansion (byte Key4*Nk , word WNb*(Nr+1)l l for (i =0; i Nk; i +)l Wi=(Key4* i,Key4* i +1,Key4* i +2,Key4* i +3 );l for (i =Nk; i 6时 ， 扩 展 算 法 如 下l KeyExpansion (byte Key4*Nk , word WNb*(Nr+1)l l for (i=0; i Nk; i +)l Wi=(Key4* i, Key4* i +1, Key4* i +2, Key4* i +3 );l for (i =Nk; i 6与 Nk6的 密 钥 扩 展 算 法 的 区 别 在 于 ： 当 i为 Nk的 4的倍 数 时 ， 须 先 将 前 一 个 字 Wi-1经 过 SubByte变 换 。 以 上 两 个 算 法 中 ， Rconi/Nk 为 轮 常 数 ， 其 值 与Nk无 关 ， 定 义 为 （ 字 节 用 十 六 进 制 表 示 ， 同 时 理解 为 GF(28)上 的 元 素 ） ：l Rcon i=(RCi, 00, 00, 00)l 其 中 RCi 是 GF(28) 中 值 为 xi-1的 元 素 ， 因 此 l RC1 =1(即 01)l RCi = x(即 02)RCi-1= xi-1 147/155 (2) 轮 密 钥 选 取l 轮 密 钥 i（ 即 第 i 个 轮 密 钥 ） 由 轮 密 钥 缓 冲 字 WNb* i到WNb*(i+1)给 出 ， 如 图 3.23所 示 。l Nb=6且 Nk=4时 的 密 钥 扩 展 与 轮 密 钥 选 取W0 W1 W2 W3 W4 W5 W6 W7 W8 W9 W10 W11 W12 W13 W14 轮密钥0轮密钥1 148/155 4 加 密 算 法 加 密 算 法 为 顺 序 完 成 以 下 操 作 ： 初 始 的 密 钥 加 ；(Nr-1)轮 迭 代 ； 一 个 结 尾 轮 。 即l Rijndael (State, CipherKey)l l KeyExpansion (CipherKey, ExpandedKey);l AddRoundKey (State, ExpandedKey); l for (i=1; i Nr; i +) l Round (State, ExpandedKey+Nb* i);l FinalRound (State, ExpandedKey+Nb*Nr)l 149/155 其 中 CipherKey是 种 子 密 钥 ， ExpandedKey是 扩 展密 钥 。 密 钥 扩 展 可 以 事 先 进 行 （ 预 计 算 ） ， 且 Rijndael密码 的 加 密 算 法 可 以 用 这 一 扩 展 密 钥 来 描 述 ， 即l Rijndael (State, ExpandedKey)l l AddRoundKey (State, ExpandedKey);l for (i=1; i N r; i +)l Round (State, ExpandedKey+Nb* i);l FinalRound (State, ExpandedKey+Nb*Nr)l 150/155 5.加 解 密 的 相 近 程 度 及 解 密 算 法 首 先 给 出 几 个 引 理 。 引 理 3.1 设 字 节 代 换 （ ByteSub） 、 行 移 位（ ShiftRow） 的 逆 变 换 分 别 为 InvByteSub、InvShiftRow。l 则 组 合 部 件 “ ByteSubShiftRow”的 逆 变 换 为“ InvByteSubInvShiftRow” l 证 明 ： 组 合 部 件 “ ByteSubShiftRow”的 逆 变 换 原 本为 “ InvShiftRowInvByteSub”。 由 于 字 节 代 换（ ByteSub） 是 对 每 个 字 节 进 行 相 同 的 变 换 ， 故“ InvShiftRow”与 “ InvByteSub”两 个 计 算 部 件 可 以交 换 顺 序 。 （ 证 毕 ） 151/155 引 理 3.2 设 列 混 合 （ MixColumn） 的 逆 变 换 为InvMixColumn 则 列 混 合 部 件 与 密 钥 加 部 件（ AddRoundKey） 的 组 合 部 件“ MixColumnAddRoundKey ( , Key)”的 逆变 换 为“ InvMixColumnAddRoundKey ( , InvKey)”l 其 中 密 钥 InvKey与 Key的 关 系 为 ：InvKey=InvMixColumn (Key) 152/155 证 明 ：l 组 合 部 件 “ MixColumnAddRoundKey ( , Key)” 的 逆变 换 原 本 为 “ AddRoundKey ( , Key)InvMixColumn”，l 由 于 列 混 合 （ MixColumn） 实 际 上 是 线 性 空 间 GF(28)4上的 可 逆 线 性 变 换 ， 因 此 “ AddRoundKey ( ,Key)InvMixColumn”l =“InvMixColumnAddRoundKey ( , InvMixColumn (Key)”（ 证 毕 ） l 由 t(x)=a(x)*c(x)+key(x),知 逆 向 列 混 淆 后 t(x)*c-1(x)= a(x)+key(x)*c-1(x),从 而 a(x) = t(x)*c-1(x) + key(x)*c-1(x),所以 逆 的 列 混 淆 后 应 该 加 上 轮 密 钥 列 混 淆 后 的 结 果 153/155 引 理 3.3 将 某 一 轮 的 后 两 个 计 算 部 件 和 下 一 轮 的 前 两 个 计 算 部 件 组 成组 合 部 件 ， 该 组 合 部 件 的 程 序 为l MixColumn (State)；l AddRoundKey (State, Key(i);l ByteSub (State);l ShiftRow (State) 则 该 组 合 部 件 的 逆 变 换 程 序 为l InvByteSub (State); l InvShiftRow (State);l InvMixColumn (State);l AddRoundKey (State, InvMixColumn (Key(i) 证 明 ： 这 是 引 理 3.1和 引 理 3.2的 直 接 推 论 。l 注 意 到 在 引 理 3.3所 描 述 的 逆 变 换 中 ， 第 2步 到 第 4步 在 形 状 上 很 像 加 密 算法 的 轮 函 数 ， 这 将 是 解 密 算 法 的 轮 函 数 。 注 意 到 结 尾 轮 只 有 3个 计 算 部 件 ，因 此 可 以 得 到 如 下 定 理 。 154/155 定 理 3-2 Rijndael密 码 的 解 密 算 法 为 顺 序 完 成 以 下 操 作 ： 初 始 的 密 钥 加 ； (Nr-1)轮 迭 代 ； 一 个 结 尾 轮 。 其 中 解 密 算 法 的 轮 函 数 为l InvRound (State, RoundKey)l l InvByteSub (State);l InvShiftRow (State);l InvMixColumn (State);l AddRoundKey (State, RoundKey) l 解 密 算 法 的 结 尾 轮 为l InvFinalRound (State, RoundKey)l l InvByteSub (State);l InvShiftRow (State);l AddRoundKey (State, RoundKey) l 155/155 设 加 密 算 法 的 初 始 密 钥 加 、 第 1轮 、 第 2轮 、 、 第Nr轮 的 子 密 钥 依 次 为l k(0), k(1), k(2), , k(Nr-1), k(Nr) 则 解 密 算 法 的 初 始 密 钥 加 、 第 1轮 、 第 2轮 、 、 第Nr轮 的 子 密 钥 依 次 为l k(Nr), InvMixColumn (k(Nr-1), InvMixColumn (k(Nr-2), , InvMixColumn (k(1), k(0)。 证 明 ： 这 是 上 述 3个 引 理 的 直 接 推 论 。 l 综 上 所 述 ， Rijndael密 码 的 解 密 算 法 与 加 密 算 法 的 计 算 网络 相 同 ， 只 是 将 各 计 算 部 件 换 为 对 应 的 逆 部 件 。 156/155 作 业 ： p76,1,2,3,4,5,6 已 知 明 文 为 01234567的 ASCII码 表 示 的 128比 特 密 钥 ： k1是 01011011的 7次 重 复 ， k2是 00001110的 7次 重 复 构 成 的 一 共 112比 特 密 钥 编 写 EDE的 加 解 密 程 序 ， 对 明 文 进 行 加 密 ， 并 进行 解 密 验 证 (1个 月 以 后 交 ),11月 中 旬 l 1.编 写 的 代 码 ； 2.运 行 结 果 截 屏 ； 3。 只 交 电 子 版