信息安全数学基础.ppt

信息安全数学基础 信息科学与工程学院 网络信息的安全威胁网上犯罪形势不容乐观 有害信息污染严重 网络病毒的蔓延和破坏 网上黑客无孔不入 机要信息流失与信息间谍潜入 网络安全产品的自控权 信息战的阴影不可忽视 引言 网络通信的困境 引言 我们要保护什么呢 引言 网络安全体系的五类服务 引言 网络安全体系的五类服务 访问控制服务 根据实体身份决定其访问权限 身份鉴别服务 消息来源确认 防假冒 证明你是否就是你所声明的你 保密性服务 利用加密技术将消息加密 非授权人无法识别信息 数据完整性服务 防止消息被篡改 证明消息与过程的正确性 防抵赖服务 阻止你或其他主体对所作所为的进行否认的服务 可确认 无法抵赖 引言 引言 解决方法 加密 如何实现保密性 密码分析 Alice Bob 加密密钥 解密密钥 Eve 引言 解决方法 数字摘要 如何实现完整性 消息篡改 公共网络 Alice Bob m z m z z hk m y hk m Eve 引言 解决方法 数字签名 如何实现不可否认性 否认 公共网络 Alice Bob Trent 谁是正确的 举报 引言 解决方法 密码技术 身份鉴别 就是确认实体是它所声明的 身份鉴别服务提供关于某个实体身份的保证 以对抗假冒攻击 如何鉴别通信对象的身份 本课程的相关知识点 简单的密码学基础 密码技术是信息安全的核心技术 需要掌握一些密码学基础知识 相关的数学知识 密码技术的实现依赖于数学知识 掌握密码技术涉及的相应数学基础知识点 参考教材 1 密码学导引 机械工业出版社 PaulGarrett著 吴世忠等译 2 信息安全数学基础 武汉大学出版社 李继国等主编 引言 什么是密码技术 窃听 公共网络 Alice Bob Eve 篡改 伪造 加密密钥 解密密钥 密文 密码学是一门古老而深奥的学科 包括密码编码学和密码分析学 通信双方按照某种约定将消息的原形隐藏 密码系统 明文 密文 加解密算法 密钥 引言 密码学的起源与发展三个阶段 1949年之前 密码学是一门艺术 1949 1975年 密码学成为科学 1976年以后 密码学的新方向 公钥密码学 1949年之前 手工阶段的初级形式 隐写术 隐形墨水 字符格式的变化 图像 举例 芦花丛中一扁舟 俊杰俄从此地游 义士若能知此理 反躬难逃可无忧 25871539258314697314697153582486217893 引言 1949 1975年 机械阶段 现代密码出现1949年香农Shannon提出 保密系统信息理论 提出 数据的安全基于密钥而不是密码算法 1976年以后 计算机阶段 公钥密码诞生1976年Diffie Hellman的 NewDirectionsinCryptography 提出了不对称密钥密码 1977年Rivest Shamir Adleman提出了RSA公钥算法 90年代出现椭圆曲线ECC等其他公钥算法 引言 对称密钥密码算法进一步发展1977年DES正式成为标准 80年代出现 过渡性 的 postDES 算法 如IDEA RCx CAST等 90年代对称密钥密码进一步成熟 Rijndael RC6 MARS Twofish Serpent等出现 2001年Rijndael成为DES的替代者AES 2004年6月美国NIST提出最新信息加密技术 量子密码 2004年山东大学王小云教授成功破解处理电子签名的MD5 引言 密码算法的分类按照保密的内容分受限制的算法 保密性基于保持算法的秘密 基于密钥的算法 保密性基于密钥的保密 Kerchoffs原则1883年Kerchoffs第一次明确提出了编码的原则 保密性完全依赖于密钥 算法应该公开 这一原则已得到普遍承认 成为判定密码强度的衡量标准 实际上也成为古典密码和现代密码的分界线 引言 基于密钥的算法 按照密钥的特点分类 对称密码算法 又称秘密密钥算法或单密钥算法 加密密钥和解密密钥相同 或可以容易地从一个推出另一个 特点 加密速度快 密钥管理复杂 主要用于加密信息 非对称密钥算法 又称公开密钥算法 加密密钥和解密密钥不相同 而且很难从一个推出另一个 特点 密钥管理简单 但加密速度慢 用于加密会话密钥和用于数字签名 实际网络应用中 常采用非对称密码来交换对称密码算法的密钥 引言 经典的古典密码算法主要有 代替密码 将明文字符用另外的字符代替 典型的有恺撒密码 仿射密码 维吉尼亚密码等 换位密码 明文的字母保持相同 但顺序打乱 经典的现代密码算法有很多种 最通用的有 DES 数据加密标准 对称密码算法 用于加密 AES 高级加密标准 对称密码算法 用于加密 引言 RSA 最流行的公钥密码算法 加密和数字签名 ECC 椭圆曲线密码 采用ElGamal算法 公钥密码算法 安全性高 密钥量小 灵活性好 DSA 数字签名算法 是数字签名的一部分 公钥密码算法 数字签名 MD5 SHA 1 数字摘要算法 数字签名 保证消息的完整性 引言 理论安全 攻击者无论截获多少密文 都无法得到足够的信息来唯一地决定明文 Shannon用理论证明 欲达理论安全 加密密钥长度必须大于等于明文长度 密钥只用一次 用完即丢 即一次一密密码本 不实用 实际安全 如果攻击者拥有无限资源 任何密码系统都是可以被破译的 但是 在有限的资源范围内 攻击者都不能通过系统地分析方法来破解系统 则称这个系统是计算上安全的或破译这个系统是计算上不可行 引言 密码系统的安全 四种基本攻击类型 唯密文攻击 攻击者只有一些密文 已知明文攻击 攻击者知道一些明文密文对 选择明文攻击 攻击者可以选择明文密文对 针对密钥的攻击 主要是针对公钥密码系统 穷举攻击 攻击者采用尝试方法穷举可能的密钥 当密钥空间较小时很有效 字典攻击是利用一些常用的单词进行组合 基本要求 任何一种加密系统都必须能够对抗唯密文攻击 目前的标准是 一个密码系统应当能够对抗选择明文攻击 引言 密码系统的攻击 第一章简单密码 经典的简单密码 移位密码 一次一密乱码本 仿射密码 1 1移位密码1 Caesar密码 最简单的移位密码 原理 将消息中的每个字母前移3位或者后移3位 举例 allofgaulisdevidedintothreepartsDOORIJDXOLUGLYLGHGLQWRWKUHHSDUWU2 移位密码 改进Caesar密码 发送方和接收方协商一个密钥k 1 k 25 代表移动位数 3 攻击 穷举攻击 25种可能的密钥 密钥空间 4 特点 对称密码 加密密钥和解密密钥相同 单表代替密码 所有的明文字母用同一种方法加密 即子密钥相同 1 2约简 整除算法1 n模m的约简 n除以m的余数r 0 r m 记作 r n m或者r nmodm m称为模数 计算 设a n m 则当n 0时 n m m a 当m 0时 n m n m 第一章简单密码 举例 10 7 10 7 10 7 4 因为 10 7 2 4 3 因为10 7 1 3 4 因为 10 7 2 4 注意 任何整数模m的约简都是非负数 2 乘法逆n模m的乘法逆t满足 n t m 1记作 t n 1 m举例 2 1 5的值为 3 1 100的值为 3 因为3 2 5 1 67 因为67 3 100 1 第一章简单密码 4 乘法逆元的计算 1 穷举法 寻找满足条件的数 技巧 若t n m 1 则n 1 m m t 33 3 100 1 所以3 1 100的值为67 第一章简单密码 3 命题设m 0 1为整数 x与m互素 则x有模m的乘法逆元 特别地 满足表达式ax bm 1的任意整数a就是一个x模m的乘法逆元 假如y是x模m的乘法逆元 对于y 若m y y 那么y 也是x模m的乘法逆元 反之亦然 2 欧几里德算法 举例 23 1 100方法 100 4 23 823 2 8 78 1 7 17 7 1 0 所以 1 3 100 13 231 13 23 10023 1 100 13 871 3 100 23100 1 23 8 1 23 3算法 1 8 1 7 8 1 23 2 8 3 8 1 23 3 100 4 23 1 23 3 100 13 23 1 1 133 13 所以 3 100 13 23 1 第一章简单密码 1 3欧几里得算法用以寻找两个整数m和n的最大公因子d 使用该算法将x和y的最大公因子表示为 ax by gcd x y 的形式 1 举例描述两个整数513和614614 1 513 101513 5 101 8101 12 8 58 1 5 35 1 3 23 1 2 1 2 寻找整数a b1 3 1 2 3 1 5 1 3 1 5 2 3 1 5 2 8 1 5 2 8 3 5 2 8 3 101 12 8 3 101 38 8 3 101 38 513 5 101 38 513 193 101 38 513 193 614 1 513 193 614 231 513 最大公因子为1 第一章简单密码 2 乘法逆元的计算 结论 当x和y互素时 gcd x y 为1 即可得到x 1 y为a y 1 x为b 第一章简单密码 3 举例 所以 21 1 25的结果为6 例2 求1234 1 4321 例1 求21 1 25解 25 1 21 421 5 4 14 1 4 0 第一章简单密码 3 命题 1 给定一非零整数m和任意整数n 存在唯一的整数q和r 使得0 r m 且n q m r 2 设n和N为两个整数 对某个整数k有N kn 则对任意整数x有 x N n x n 1 3一次一密乱码本OTP1 思想 密钥与消息一样长 且只能使用一次 2 工作原理 消息长度为n x x1 x2 xn 随机密钥 k k1 k2 kn 加密 Ek x x1 k1 26 xn kn 26 解密 Dk y y1 k1 26 yn kn 26 第一章简单密码 3 举例 消息 nevermore密钥 excelsior密文 RBXICEWFV R 17 n 13 e 4 26F 5 r 17 o 14 26 4 特点 密钥的产生与分发管理复杂 对称密码 多表代替密码 明文中不同位置的字母采用的加密密钥不同 第一章简单密码 1 4仿射密码1 思想 对移位密码进行改进 扩大密钥空间 2 原理 加密 Ea b x a x b 260 a b 25解密 Da b y 3 特点 1 当a 1时为移位密码 2 加密密钥为 a b 解密密钥为 a 1 a 1b 3 单表代替密码 4 对称密码 由加密密钥可以推导出解密密钥 第一章简单密码 5 密钥空间 由于a 1必须存在 所以可能的密钥数为12 26 1 311个 第一章简单密码 4 攻击方法 穷举攻击 尝试311个可能的密钥 选择明文攻击 Ea b 0 a 0 b 26Ea b 1 a 1 b 26已知明文攻击 Ea b x a x b 26Ea b y a y b 26唯密文攻击 字母频率攻击 a x y 1 Ea b x Ea b y 26b Ea b x ax 26 b Ea b 0 a Ea b 1 b 26 第一章简单密码 举例 已知明文 meetmeatmidnight假设密文 HNNSHNDSHXEQXFOS 1 选择明文攻击攻击者选择 a 0 D 3 d 3 E 4 第一章简单密码 第一章简单密码 第一章简单密码 1 5Vigenere密码1 特点 具有相对较大的密钥空间 对称密码 多表代替密码 有周期性的弱点 若两个字符出现的间隔是密钥长度的倍数 则它们将以同样的方法加密 2 加密和解密的原理 1 密钥是一个字符序列 k k0 k1 km 1 明文x x0 x1 xN 被分成长度为m的段 2 加密函数 Ek x0 x1 xN y0 y1 yN yi xi ki m 26解密函数 Dk y0 y1 yN x0 x1 xN xi yi ki m 26 第一章简单密码 3 多轮加密 若一个明文使用密钥长度为m的维吉尼亚密码加密 得到的密文再用长度为n的密钥加密 其结果与用长度为lcm m n 的维吉尼亚密码加密的结果一样 若m n互素 则lcm m n mxn 密钥长度很大 第一章简单密码 1 6最小公倍数lcm和最大公约数gcd 1 定义对于两个整数d n 若d整除n 或者说d是n的一个因子 记作 d n设m n是两个非0的整数 则最大公约数d为最大的正整数 使得d m和d n 记作d gcd m n 最小公倍数N为最小的正整数 使得m N和n N 记作N lcm m n 2 定理m n的最大公约数gcd m n 具有这样的特性 对于m n的每一个公因子e满足e gcd m n m n的最小公倍数lcm m n 具有这样的特性 对于m n的每一个公倍数N满足lcm m n N 第一章简单密码 3 素数素数p是那些不存在因子d的整数1 d p1 2 定理 每一个正整数都可以分解为素数的乘积 而且这种分解是唯一的 12 22x335 5x7 1 对于每一个素数p 整除gcd m n 的p的方幂 是既整除m又整除n的p的方幂的最小值 2 两个方幂中较大的一个便组成了最小公倍数 举例 3960 23x32x5x11400 24x52则 gcd 3960 400 23x5 40lcm 3960 400 24x32x52x11 39600 第一章简单密码 1 7生日攻击 1 命题在实验x中 不同结果x1 x2 xn的概率分别为p x1 p1 p xn pn 集合A为样本空间 x1 xn 的一个子集 且有p A p 设0 k N 则N次实验中A恰好出现k次的概率为 举例 投币 假设一枚公平的硬币朝上或朝下的几率是相等的 且每次投币是独立的 分析 记录一个n次投掷的过程 2n 任何单个序列出现的概率是1 2n n次投掷恰好有k次正面朝上的概率是 10次投掷中 恰好5次正面朝上的概率为 252 1024 1 46 4或者4 6组合的概率是 420 1024 2 5 2 生日攻击设 1 2 N 为所有原子事件的样本空间 p i 1 N n次实验后至少2次结果相同的概率至少为 1 e n n 1 2N 因此 对于出现两次相同结果的概率至少为1 2 第一章简单密码 证明 先计算出没有两种完全相同结果出现的概率p 则出现两次相同结果的概率p 1 p 1次试验时 p1 1 2次试验时 两次结果相同的概率为1 N 则p2 1 1 N 3次试验时 前两次结果肯定是不相同的 第3次与前两次结果相同的概率为2 N 不同则为1 2 N 根据条件概率有 p3 1 1 N 1 2 N 类推 pn 1 1 N 1 2 N 1 n 1 N 取对数 lnpn ln 1 1 N ln 1 2 N ln 1 n 1 N 根据泰勒级数展开式 ln 1 x x x2 2 x3 3 x 第一章简单密码 所以lnpn ln 1 1 N ln 1 2 N ln 1 n 1 N 1 N 2 N n 1 N 1 2 n 1 N n n 1 2N n2 2N p pn e n n 1 2Np 1 p 1 e n n 1 2Nn次实验后至少2次结果相同的概率p 1 e n n 1 2N另外 要使得p 1 2 则p ln2 第一章简单密码 作业 1 为移位密码加密的消息解密 YRQQEFPBUXJMIBFPIBPPBXPV 2 求 1000模88的约简 3 求29模100的乘法逆 4 已知明文攻击 Ea b 3 5且Ea b 6 7 求解密密钥 5 求gcd 1112 1544 并将其表示成如下形式 1112x 1544y 6 求1001模1234的乘法逆 第一章简单密码 古典密码的两大机制 代替密码 字母表范围内替换 换位密码 在消息内变换字母的位置 2 1代替密码1 描述密钥是字母表的任意组合 有一个明密对应表 密钥空间巨大 26 单表代替密码的两个特例 移位密码和仿射密码 2 举例首先选加密表 为了便于记忆 协商一个密钥 DOYOULIKETHISBOOK去掉重复字母 再进行补充 形成加密表 abcdefghijklmnopqrstuvwxyzDOYULIKETHSBACFGJMNPQRVWXZ 第二章代替与换位 第二章代替与换位 2 2换位密码1 机制 单个字符不变而位置改变 如将文本翻转 明文computersystems密文SMETSYSRETUPMOC2 特点 1 密文长度与明文长度相同 2 唯密文攻击可能得到多种不同的破译结果 如keep peek live evil vile3 分组换位密码针对固定大小的分组进行操作 举例 明文canyouunderstand 1 列换位法设密钥k 4 将明文进行分组排列 密文 CODTAUEANURNYNSD 明文 canyouunderstand 明文 canyouunderstand 1234 1234 第二章代替与换位 按列读出 type 密文 YNSDNURNCODTAUEA 明文 canyouunderstand 明文 canyouunderstand 1234 3421 YNSDNURNCODTAUEA 2 密钥为字符串type 第二章代替与换位 3 矩阵换位法 置换矩阵作为密钥 明文 canyouunderstand canyouunderstand ncyauonurdsentda 密文 NCYAUONURDSENTDA 按置换矩阵的阶4分组 canyouunderstand NCYAUONURDSENTDA 明文 canyouunderstand 解密置换矩阵 说明 第二章代替与换位 第二章代替与换位 2 3频率攻击 1 原理 利用自然语言的频率攻击字母出现的频率有规律 e 11 67t 9 53o 7 81a 7 73 the 4 65to 3 02of 2 61and 1 85 2 应用 对古典密码进行唯密文攻击 3 举例 对仿射密码的攻击密文 JFFGJFDMGFSJHYQHTAGHQGAFDCCFP统计字母出现的次数 F 6G 4H 3J 3 猜测 e 4 F 5 t 19 G 6 则有 Ea b e FEa b t G 第二章代替与换位 Ea b x 7x 3 26 解密函数为 E15 7 x 15x 7 26 解密后的明文为 meetmeaftermidnightinthealley 第二章代替与换位 4 举例 对代替密码的攻击KOSBMKKBSISSYFSJNFKBMESKOS IDYIFPKFJSSMK e ee e e ee t t t tt o o o o n i i i l k b b s s d d b a y 分析 由ESROL得到er s o l或re s o l loser或sorel 那么 由VIERD得到drive或irevd所以比较合理的明文是 loserdrive 5 举例 对换位密码的攻击ESROLVIERD 第二章代替与换位 作业 1 解密由仿射密码加密的密文 VCLLCPBKLCLJKXXCHCP 2 解密用简单换位密码加密的密文 EAGGARDAIREP 3 1群1 二元运算定义 设s为集合 函数f s s s称为s上的二元运算或代数运算 满足 可计算性 s中任何元素都可以进行这种运算 单值性 运算结果唯一 封闭性 s中任何两个元素运算结果都属于s 2 群的定义定义 设是代数系统 为G上的二元运算 如果 运算是可结合的 则称半群 若为半群 并且二元运算 存在单位元e G 则称为幺半群 若为半群 并且二元运算 存在单位元e G G中的任何元素x都有逆元x 1 G 称为群 简记为G 第三章置换 举例 1 是群 其中Z为整数集合 是普通的加法 单位元是0 整数x的逆元是 x 2 是群 Z6 0 1 2 3 4 5 为模6加法 显然 满足结合律 单位元是0 由于1 5 0 2 4 0 3 3 0 所以1和5互为逆元 2和4互为逆元 3和0的逆元仍然是3和0 3 群中元素的阶定义 设是群 a G n Z 则a的n次幂为en 0an an 1 an 0 a 1 mn中 30 0 35 15 3 5 15在群中 20 0 23 0 2 3 0 第三章置换 阶的定义 1 设是群 a G 使得等式ak e成立的最小正整数k称为a的阶 记做 a k a称为k阶元 若不存在这样的整数k 则a称为无限阶元 例如 在中 2和4是3阶元 3是2阶元 1和5是6阶元 0是1阶元 在中 0是1阶元 其他都是无限阶元 2 设为群 a G 且 a r 设k是整数 则ak e当且仅当r k 3 设为群 则群中任何元素a与其逆元a 1具有相同的阶 第三章置换 4 循环群和置换群定义1 设为群 如果存在一个元素a G 使得G ak k Z 则称G为循环群 记做G 称a为生成元 若 a n 则G称为n阶循环群 例如 是循环群 其中Z6 0 1 2 3 4 5 为模6加法 生成元为1或5 是循环群 生成元为1或 1 是循环群 Zn 0 1 n 1 生成元为1 第三章置换 定义3 设s 1 2 n s上的n 个置换构成集合sn 则称sn与置换的复合运算 构成的群为s上的n元对称群 的任意子群称为s上的n元置换群 第三章置换 定义2 设s 1 2 n s上的任何双射映射函数 s s称为s上的n元置换 记为 3 2置换概念1 置换一个集合X的置换f定义为X到自身的一个双射函数f 对应有n个元素的集合X 共有n 个置换 问题 对于集合X 给定某个状态 经过多少次置换返回初始状态 Sn 1 2 3 n 1 n 表示n个元素的置换群置换g为满足g k ik的一个置换 平凡置换e 没有移动任何元素的置换 即对于所有的i 有e i i 置换与集合内容无关 第三章置换 2 置换的合成或乘积设g和h是两个置换 先应用h 再应用g 记为 g h或gh注意 g h h g置换的合成满足结合律 g h k g h k 3 逆置换对于任意置换g 存在一个逆置换g 1 满足 g g 1 g 1 g e4 图表记法用来计算两个置换的乘积 如 第三章置换 5 循环最简单的置换是不同长度的循环 一个k循环满足 f i1 i2 f i2 i3 f ik 1 ik f ik i1 对于任意j i1 i2 ik 有f j j 举例 则 可见 g h h g 具有不可交换性 记作 i1 i2 ik 12 13 第三章置换 6 结论 1 如果g是一个k循环 那么gk e 注意 一个k循环有k种表示法 比较 123 与 132 123 231 312 如 则 即 对某个集合应用g操作k次 不会对集合产生任何影响 第三章置换 2 置换的阶是置换被多次应用后却不产生任何实际影响所需要的重复次数 若置换g是一个k循环 则有gk e g的阶为k 3 不相交的循环若g i1 ik 和h j1 jl 分别为k循环和l循环 且 i1 i2 ik 和 j1 j2 jl 是不相交的列表 则有 gh hg这样的循环g和h称为不相交的循环 第三章置换 一个置换g的阶k 不相交循环分解中各循环长度的最小公倍数 如 思考 如果一副50张的牌洗得好 重复洗8次后所有的牌将返回初始位置 阶为4 4 置换的不相交循环分解任何置换都可以表示为不相交循环的乘积 并且本质上只有这一种表示方法 1457 23 6 第三章置换 3 3切牌最简单的切牌 选择一个随机点把一副牌一分为二 然后交换两部分 n张牌 0 1 n 1i 1 n 1 0 1 i切牌过程为 fi x x n i 1 n如 n 6 i 10 1 2 3 4 52 3 4 5 0 1置换过程为 f1 x x 4 6 第三章置换 若n张牌的位置编号为 1 2 n 1 ni 1 n 1 n 1 i则切牌过程为 fi x x n i 1 n 1 第三章置换 如 n 6 i 21 2 3 4 5 63 4 5 6 1 2置换过程为 f1 x x 3 6 1 2n张牌 1 2 n n 1 2n 1 2n两半交错 n 1 1 n 2 2 2n 1 n 1 2n n1 n 1 2 n 2 n 1 2n 1 n 2n命题 对一副有2n张牌1 2 2n 1 2n的完美快速洗牌过程为 f x 2x 2n 1 推论 若e为2模2n 1的阶 即e是满足2e 1mod2n 1的最小正整数 那么对一副有2n张牌经过e次洗牌后 所有的牌都第一次返回到它们的起始位置 不好的洗牌 完美洗牌 第三章置换 3 4洗牌 然后按列读取这些数 0 n 2n mn n 1 n 1 2n 1 mn n 1 mn 1对于数x 行 x n列 x n 3 5分组交错给定正整数m和n 针对mn个元素 一个m n分组交换的置换定义为 按行将mm个数据写成m n的矩阵的形式 第三章置换 然后按列读取这些数 0 4 8 1 5 9 2 6 10 3 7 11对应的置换过程为 例 12个数据0 1 2 3 4 5 6 7 8 9 10 11 进行3 4分组交错 对应的循环分解为 数据 置换位置 阶为5 按4行3列写出 第三章置换 命题 忽略两个不动点0和mn 1 m n分组交错对集合 1 2 3 mn 2 的作用是 x mx mn 1 举例 3 6分组交错 3x 17 3x 17 分析 快速洗牌 去掉两个不动点完美的快速洗牌 x 2x 2n 1 第三章置换 作业 1 计算乘积 第三章置换 用不相交循环的乘积表示上述的结果 并确定阶 2 S5中任意元素的最大阶是多少 S14呢 3 确定对一副20张牌的完美快速洗牌的循环分解 4 找出3 5的分组交错置换的循环分解 第四章现代对称密码 香农提出的现代密码设计准则 Kerchhoff原则 系统的安全性不依赖于对密文或加密算法的保密 而依赖于密钥 惟一需要保密的是密钥 决定了古典密码学与现代密码学 一个好的密码将融合混淆和扩散混淆 混淆明文的不同部分 扩散 对攻击者隐藏一些语言的局部特征 现代密码将结合换位和代替 代替密码在混淆上是有效的 换位密码扩散性较好 4 1数据加密标准DES DataEncryptionStandard 1976年被采纳作为联邦标准 并授权在非密级的政府通信中使用 应用广泛 DES是一个分组加密算法 对称密码 64位分组 密钥长度为64位 实际长度为56位 第四章现代对称密码 现代密码算法的特点 只要保证密钥安全 就能保证加密信息的安全 对称密码算法 很好地融合了混淆和扩散 DES AES IEDA RC6等非对称密码算法 基于数学难题 RSA ECC ElGamal等 DES的整个算法是公开的 系统的安全性靠密钥保证 算法包括三个步骤 初始置换IP 16轮迭代的乘积变换 逆初始变换IP 1 1 初始置换IP初始置换IP可将64位明文M m1m2 m64的位置进行置换 得到乱序的64位明文组M0 m58m50 m7 2 逆初始置换IP 1逆初始置换IP 1将16轮迭代后的64比特数据的各字节按列写出 将前四列插到后四列中 再对各列进行逆序 然后将元素按行读出即可得到输出的密文组 IP和IP 1的作用主要是打乱输入的ASCII码字划分关系 并将明文校验码变成IP输出的一个字节 第四章现代对称密码 第四章现代对称密码 第四章现代对称密码 第四章现代对称密码 举例 设64位明文M为 0000000011111111010101010001000110001000110011000011001110101010则经过IP置换后的M0为 0010011001001110001001100100111010110010110000101011001011000010转换过程如下 第四章现代对称密码 3 乘积变换乘积变换是DES算法的核心部分 将经过IP置换后的数据分成32位的左右两组 在迭代过程中彼此左右交换位置 每次迭代时只对右边的32位进行一系列的加密变换 然后把左边的32位与右边得到的32位逐位进行异或操作 作为下一轮迭代时左边的段 迭代公式为 Li Ri 1 Ri Li 1 f Ri 1 ki 按位异或操作运算符 即按位作模2相加运算 运算规则为 1 0 1 0 1 1 0 0 0 1 1 0 f的功能是将32比特的数据经过选择扩展运算E 密钥加密运算 选择压缩运算S和置换运算P转换为32比特的输出 第四章现代对称密码 第四章现代对称密码 1 选择扩展运算E选择扩展运算下可将输入的32比特Ri 1扩展成48位的输出 令s表示E原输入数据比特的下标 则E的输出是将原下标s为0或1 模4 的各比特重复一次得到的 实现数据扩展 第四章现代对称密码 2 密钥加密运算密钥加密运算将48比特的子密钥ki与选择扩展运算E输出的48比特数据进行按位异或运算 举例 设32比特数据Ri 1为00000000111111110000000011111111 48比特子密钥ki为000000001111111101010101101010101100110010001000 求Ri 1经过选择扩展运算E后与子密钥ki异或后的结果 第四章现代对称密码 16个子密钥ki的产生 64比特初始密钥k经过换位函数PC 1将位置号为8 16 24 32 40 48 56和64的8位奇偶位去掉并换位 换位后的数据分为2组 经过循环左移位LSi和换位函数PC 2变换后得到每次迭代加密用的子密钥ki 第四章现代对称密码 第四章现代对称密码 LSi表示求子密钥ki时将Ci 1和Di 1进行循环左移 其移位位数为 3 选择压缩运算选择压缩运算可将密钥加密运算后的48比特数据从左至右分成8组 每组为6比特 并行迭入8个S盒后压缩成32比特输出 每个S盒的输入为6比特 输出为4比特 以完成压缩变换 对于某个S盒Si 假设其输入为b1b2b3b4b5b6 在Si表中找到b1b6行 b2b3b4b5列的整数 转换为4位二进制就是输出的4比特数据 第四章现代对称密码 第四章现代对称密码 第四章现代对称密码 举例 设S5的输入为b1b2b3b4b5b6 110110 则 b1b6 2 10 2 2 b2b3b4b5 2 1011 2 11在S5中找到行为2 列为11的数据5转换为4位二进制为0101 所以S5的输出为0101 4 置换运算PS1 S8盒的输出合成32比特数据后 用换位表p进行置换 得到的32比特数据就是f Ri 1 ki 的输出 第四章现代对称密码 DES的解密算法和加密算法相同 只是在解密过程中将子密钥的顺序颠倒 DES的出现在密码史上是个创举 以前任何设计者对于密码体制细节都是严加保密的 自公布以来 它一直活跃在国际保密通信的舞台上 成为商用保密通信和计算机通信的最常用的加密算法 由于DES的安全性完全依赖于密钥 而其64位的密钥太短 因而出现了许多DES的改进算法 如三重DES 分组反馈连接式DES以及密码反馈模式DES等 随着新的攻击手段和改进的加密算法的不断出现 DES也许将完成它的历史使命 高级加密标准AES评选于2000年10月结束 Rijdael算法为AES的唯一算法 第四章现代对称密码 4 DES的安全性 1 差分分析1990年Biham和Shamir提出差分密码分析 是一种比穷举攻击有效的选择明文的攻击方法 差分分析的攻击方法是针对DES和其他类似的有固定S盒的算法 DES的S盒恰好最适宜于抗差分分析 最佳差分分析的总结表明对16轮DES的攻击需选择明文247 分析的复杂性为237 2 线性密码分析MitsuruMatsui提出了线形密码分析 使用线性近似值来逼近分组密码的操作 攻击完整的16轮DES 当已知明文的平均数为243时 可得到密钥 是最有效的攻击DES的方法 第四章现代对称密码 第四章现代对称密码 4 2序列密码1 随机数生成器 1 任意由确定过程生成的随机数序列 从实际意义上讲都不是随机的 2 pRNG pseudo randomnumbergenerators 伪随机数发生器 其典型应用是一次一密乱码本 3 一个pRNG要求 在不知道密钥的情况下 由随机数序列中已知部分推测下一个数是 困难 的 4 伪随机数序列的周期 要求尽可能大对于序列s0 s1 s2 若存在p 使得si p si则称它为周期为p的周期序列 第四章现代对称密码 2 线性同余发生器最为广泛使用的伪随机数产生器 1 产生方式sn 1 a sn b modm Zm其中0 a m 0 b m 初值s0称为种子 2 分析a b m的取值是产生高质量随机数的关键 取a 2 b 7 m 17 则sn 1 2 sn 7 mod17取种子s0 1 生成的伪随机序列为 1 9 8 6 2 11 12 14 1 9 8 6 2 11 12 14 1 9 序列的周期为8 而且Z17中只有8个元素出现 第四章现代对称密码 取a 7 b 1 m 17 则sn 1 7 sn 1 mod17取种子s0 1 生成的伪随机序列为 1 8 6 9 13 7 16 11 10 3 5 2 15 4 12 0 1 8 序列的周期为16 14未出现 取种子s0 14 则序列为 14 14 14 14 3 线性同余发生器的周期定理1 只要种子是模p非零的 则线性同余发生器si 1 a simodp的周期为a在乘法群Z p 中的阶l 而且 l p 1 且当a为模p的本原根时 l p 1 定理2 线性同余发生器si 1 a si bmodp的周期为a在Zp 中的阶 只要种子s0不等于坏种子sbad a 1 1 bmodp举例 求sn 1 7sn 2mod13的坏种子sbad 第四章现代对称密码 4 评价sn 1 asn b modma b m都是可选的 在选择时要保证最大的周期 优点是 简单 速度快 缺点是 可预测 首先被JimReeds破译 一个已被广泛应用的随机数产生器sn 1 a snmodmm 231 1 214783647a 75 16807 231 1保证计算机能有效计算 75是模m的一个原根 保证周期足够长 第四章现代对称密码 4 攻击由于算法是确定的 保密的是参数a b m 而且除了初值s0具有随机性外 算法本身不具备随机性 如果攻击者能获得一部分s1 s2 就可以建立方程组解出a b m 举例 已知序列1 8 6 9 13 7 16 选 8 6 9 13即可解出参数a 7 b 1 m 17 改进 利用系统时钟修改随机数序列 产生n个数后 用当前时间模m后作为新种子 直接将当前的时钟值加到每个随机数上 第四章现代对称密码 3 线性反馈移位寄存器基于移位寄存器的序列密码被广泛应用于军事密码学中 一个反馈移位寄存器由两部分组成 移位寄存器和反馈函数 1 定义固定一个数n 一个模数m 2 选取系数C c0 c1 cn 1 和种子S s0 s1 sn 1 对于i 1 n 递归地定义 si 1 c0si c1si 1 c2si 2 cn 1si n 1modm当n 4时 其关系可用表示为 所以 si 1 c0si c1si 1 c2si 2 c3si 3 第四章现代对称密码 si 1 c0si c1si 1 c2si 2 c3si 3 si si 3 最简单的反馈移位寄存器是线性反馈移位寄存器LFSR 举例 选系数C 1 0 0 1 则输出序列为 4位的LFSR 抽头为第1 4位 初始值为1111 则输出序列为 111101011001000 1111011110110101101011010110 取种子 s0s1s2s3 1100 则输出序列为 1100100011110101100 第四章现代对称密码 n位LFSR能产生2n 1个内部状态中的一个 即在重复之前能产生2n 1位长的伪随机序列 具有特殊抽头序列的LFSR才能具有最大周期2n 1 在该类抽头序列加上常数1形成的多项式必须是模2的本原多项式 举例 32 7 5 3 2 1 0 x32 x7 x5 x3 x2 x 1和x32 x31 x30 x29 x27 x25 1即32位的LFSR 当抽头序列为第32 7 5 3 2 1位时 将使LFSR具有最大周期232 1 第四章现代对称密码 2 代码实现 1 Finonacci配置ShiftRegister ShiftRegister 31 ShiftRegister 6 ShiftRegister 4 ShiftRegister 2 ShiftRegister 1 ShiftRegister 2 Galois配置 第四章现代对称密码 definemask0 x80000057staticunsignedlongShiftRegister 1 voidseed LFSR unsignedlongseed if seed 0 seed 1 elseShiftRegister seed intmodified LFSR void if ShiftRegister 第四章现代对称密码 作业 1 计算线性同余发生器的坏种子 xn 1 6xn 9mod11 2 求LFSRxn 1 xn xn 1 xn 2 xn 3的周期 其初态为 x0 x1 x2 x3 0 1 0 0 5 1整除性1 定义d n d整除n 即存在整数k 使得n kd 真因子d d整除n 但d不是 n 1 素数 一个没有真因子的正整数 2 命题 1 正整数n是素数当且仅当它不能被任何整数d整除 其中 2 互素 如果同时整除m和n的整数只有 1 则称m和n互素 记作gcd m n 1 第五章整除和同余 3 如果a b并且b c 则a c 如果d x并且d y 则对于任意整数a和b有 d ax by 4 n和N是两个整数 且n N 则对任意整数x有 x N n x n 3 定理m和n为不同时为0的整数 则m和n的最大公因子gcd m n 是以xm yn表示的最小正整数 例如 gcd 3 5 2 3 1 5 1gcd 9 15 2 9 1 15 3 第五章整除和同余 4 素数的产生 1 采用素性检测法对随机产生的数进行检测 2 迄今为止没有发现素数的模型或产生素数的有效公式 例如 中国古代数学家提出 若n 2n 2 则n为素数 但是当n 341时不成立 第五章整除和同余 3 一些特殊意义的素数 梅森 Mersenne 素数 形如Mn 2n 1的素数 n为素数 如3 7 127 8191 131071 至今发现27个 n 2 3 5 7 13 17 19 31 61 89 107 127 521 607 1279 2203 2281 3217 4253 4423 9689 9941 11213 21701 23209 44497 M11 2047 23 89不是素数 费马 Fermat 素数 形如Fm 2m 1的素数 m为自然数 至今只发现5个 3 5 17 257 65537F5 4294967297 641 6700417 5 2整数模m1 x ymodmx模m同余y这种关系叫模m的同余 等价的说法有x ymodm当且仅当m x y 2 同余的性质对于固定的整数m 模m同余是一个等价关系 自反性 对于任意的x 总有x xmodm 对称性 x ymodm y xmodm 传递性 x ymodm y zmodm x zmodm 其他性质 1 x ymodm ax aymodm x a y amodm 2 x ymodm ax aymodam a 0 3 a b modm amodm bmodm modm 第五章整除和同余 3 命题两个整数x和x x qm r x q m r 0 r r m 则x x modm当且仅当r r modm 对于固定的模数m 如果x x 那么对于y有x y x ymodmxy x ymodm 推论 同余直接继承了普通算术运算的一些性质 分配律 x y z xy xzmodm加法结合律 x y z x y z modm乘法结合律 xy z x yz modm1的性质 1 x x 1 xmodm0的性质 0 x x 0 xmodm 第五章整除和同余 4 Z m或者Zm整数模m等价类的集合给定整数x和模数m x模m等价类 y Z y xmodm 通常记为x或x 称为x模m的同余类或者剩余类 第五章整除和同余 例 对于模数12 有 模m等价类的集合表示形式 模m等价类的集合 模m约简的集合 Z m中的结论 m 0modmx x 0modmx km xmodm x y m x m y m m xy m x m y m m 5 Z mX或ZmX ZmX y Zm gcd y m 1 即 Zm中与m互素的元素的集合 例如 Z15X 1 2 4 7 8 11 13 14 Z11X 1 2 3 4 5 6 7 8 9 10 第五章整除和同余 6 定理 定理1 设m n是两个互素的正整数 如果x y分别遍历模m n的完全 简化 剩余系 则nx my遍历模mn的完全 简化 剩余系 举例 分别用模4和模5的完全剩余系和简化剩系来表示模20的完全剩余系和简化剩余系 Z4 0 1 2 3 Z4X 1 3 Z5 0 1 2 3 4 Z5X 1 2 3 4 所以 Z20 0 4 8 12 16 5 9 13 17 21 10 14 18 22 26 15 19 23 27 31 Z20X 9 13 17 21 19 23 27 31 第五章整除和同余 定理2 若正整数m n 满足gcd m n 1 则有 mn m n 1modn 第五章整除和同余 5 3两个著名的定理1 欧拉定理 对n 1 如果gcd x n 1 则有 x n 1modn 2 费马小定理对任意的整数x和素数p 有xp 1 1modp 3 欧拉函数 n 的定义对于正整数n 与其互素的小于等于n的正整数的个数表示为 n 称为欧拉函数 也可以理解为ZmX中的元素个数 第五章整除和同余 4 欧拉函数 n 的计算 举例 计算 7 10 35 Z7X 1 2 3 4 5 6 所以 7 6 Z10X 1 3 7 9 所以 10 4 Z35X 1 2 3 4 6 8 9 11 12 13 16 17 18 19 22 23 24 26 27 29 31 32 33 34 所以 35 24 那么 10000 第五章整除和同余 因式惟一分解定理 正整数N可以因子分解为 举例 N 30 2 3 5123456789101112131415161718192021222324252627282930 问题 如何求欧拉函数 其中 p1 p2 pm为素数 所有指数为正整数 那么 证明 第五章整除和同余 那么 10000 10000 24 54 所以 10000 2 1 23 5 1 53 8 4 125 4000 验证 35 24 35 5 7 所以 35 5 1 51 1 7 1 71 1 4 6 24 第五章整除和同余 小结 1 欧拉函数的定义 2 欧拉函数 n 的计算方法 对于正整数n 与其互素的小于等于n的正整数的个数表示为 n 称为欧拉函数 作业 计算 28 1234 第五章整除和同余 传统的指数运算效率低 需改进 1 思想在计算xe时 将e表示为一个二元整数e e0 e1 21 e2 22 en 2n那么 因此 若ek 0 可以忽略项 若ek 1 则包含项 2 实现算法为了计算xe 利用三元组 X E Y 其初始值为 X E Y x e 1 6 1