《密码学技术讲义》PPT课件.ppt

密码学讲义 中山大学信息科学与技术学院王常吉副教授2006年11月 2 8 2020 2 目录 密码学基础加密算法消息认证和鉴别数字签名密钥管理加密应用 2 8 2020 3 密码学基础 2 8 2020 4 密码学发展历程 密码学是一门古老的科学 大概自人类社会出现战争便产生了密码 以后逐渐形成一门独立的学科 密码学的发展历史大致可以分为三个阶段 在1949年之前 是密码发展的第一阶段 古典密码体制 古典密码体制是通过某种方式的文字置换进行 这种置换一般是通过某种手工或机械变换方式进行转换 同时简单地使用了数学运算 虽然在古代加密方法中已体现了密码学的若干要素 但它只是一门艺术 而不是一门科学 2 8 2020 5 密码学发展历程 从1949年到1975年 是密码学发展的第二阶段 1949年Shannon发表了题为 保密通信的信息理论 的著名论文 把密码学置于坚实的数学基础之上 标志着密码学作为一门学科的形成 这是密码学的第一次飞跃 然而 在该时期密码学主要用在政治 外交 军事等方面 其研究是在秘密地进行 密码学理论的研究工作进展不大 公开的发表的密码学论文很少 2 8 2020 6 密码学发展历程 1976年 W Diffie和M Hellman在 密码编码学新方向 一文中提出了公开密钥的思想 这是密码学的第二次飞跃 1977年美国数据加密标准 DES 的公布使密码学的研究公开 密码学得到了迅速地发展 1994年美国联邦政府颁布的密钥托管加密标准 EES 和数字签名标准 DSS 以及2001年颁布的高级数据加密标准 AES 都是密码学发展史上一个个重要的里程碑 2 8 2020 7 密码学基本概念 密码学 Cryptology 研究信息系统安全保密的科学 它包含两个分支密码编码学 Cryptography 对信息进行编码实现隐蔽信息的一门学问密码分析学 Cryptanalytics 研究分析破译密码的学问 两者相互对立 而又互相促进地向前发展 2 8 2020 8 密码学基本概念 明文 Plaintext 被隐蔽消息 密文 Ciphertext 或密报 Cryptogram 明文经密码变换成的一种隐蔽形式 加密 Encryption 将明文变换为密文的过程 解密 Decryption 加密的逆过程 即由密文恢复出原明文的过程 加密员或密码员 Cryptographer 对明文进行加密操作的人员 2 8 2020 9 密码学基本概念 加密算法 Encryptionalgorithm 密码员对明文进行加密时所采用的一组规则 接收者 Receiver 传送消息的预定对象 解密算法 接收者对密文进行解密时所采用的一组规则 密钥 Key 控制加密和解密算法操作的数据处理 分别称作加密密钥和解密密钥 截收者 Eavesdropper 在信息传输和处理系统中的非授权者 通过搭线窃听 电磁窃听 声音窃听等来窃取机密信息 2 8 2020 10 密码学基本概念 密码分析 Cryptanalysis 截收者试图通过分析从截获的密文推断出原来的明文或密钥 密码分析员 Cryptanalyst 从事密码分析的人 被动攻击 Passiveattack 对一个保密系统采取截获密文进行分析的攻击 主动攻击 Activeattack 非法入侵者 Tamper 攻击者 Attacker 或黑客 Hacker 主动向系统窜扰 采用删除 增添 重放 伪造等窜改手段向系统注入假消息 达到利已害人的目的 2 8 2020 11 密码学基本概念 搭线信道 搭线信道 非 法 主动攻击 被动攻击 密码分析员 m 接入者 c 窃听者 信 源 m 加密器 c 解密器 m 接 收 M c E k 1 m 信道 m D k2 c 者 k 1 k 2 密钥源 密钥源 k 1 密钥信道 k 2 保密系统模型 2 8 2020 12 密码学基本概念 一个密码系统通常由五个部分组成明文消息空间M 密文消息空间C 密钥空间K 包括加密密钥空间K1和解密密钥空间K2 在单钥体制下 K1 K2 K 此时密钥k K需经安全的密钥信道由发方传给收方 加密变换 解密变换 2 8 2020 13 密码系统应当满足的要求 系统即使达不到理论上是不可破的 即也应当为实际上不可破的 就是说 从截获的密文或某些已知明文密文对 要决定密钥或任意明文在计算上是不可行的 系统的保密性不依赖于对加密体制或算法的保密 而依赖于密钥 这是著名的Kerckhoff原则 加密和解密算法适用于所有密钥空间中的元素 系统便于实现和使用方便 2 8 2020 14 密码体制的分类 按照保密的内容分 受限制的算法 算法的保密性基于保持算法的秘密基于密钥的算法 算法的保密性基于对密钥的保密按照对明文的处理方式分组密码算法 将明文分成固定长度的组 用同一密钥和算法对每一块加密 输出是固定长度的密文 序列密码算法 又称流密码 每次加密一位或一字节明文 2 8 2020 15 密码体制的分类 按照加密密钥和解秘密钥是否相同分 对称密码算法 加密密钥和解密密钥相同 或实质上等同 对称密码体制的优点是安全性高 加解密速度快 缺点是随着网络规模的扩大 密钥的管理成立一个难点 无法解决消息确认问题 缺乏自动检测密钥泄露的能力 非对称密码算法 加密密钥和解密密钥不同 从一个很难推导出另一个 非对称密码体制的优点是可以适用网络的开放性要求 密钥管理相对简单 尤其是可以实现数字签名功能 与对称密码算法相比 非对称密码算法一般比较复杂 加解密速度慢 2 8 2020 16 古典密码 古典密码是密码学的渊源 这些密码大都比较简单 可用手工或机械操作实现加解密 现在已很少采用了 然而 研究这些密码的原理 对于理解 构造和分析现代密码都是十分有益的 2 8 2020 17 代换密码 SubstitutionCipher 明文字母表明文消息是长为字母串 称为明文组 以表示 也称作 报文 它是定义在上的随机变量 是上的维矢量空间 为单字母报 1 gram 为双字母报 Digrams 为三字母报 Trigrams 明文空间 2 8 2020 18 代换密码 密文字母集密文组是定义在维矢量空间上的随机变量 密文空间一般当时有 即明文和密文由同一字母表构成 加密变换 明文空间到密文空间的映射 在1 1的映射下 存在有逆映射 使加密变换通常是在密钥控制下变化的 即 2 8 2020 19 代换密码 为密钥空间 一个密码系统就是在和密钥作用下 由的映射 或以中的元素代换中的元素 在这意义下 称这种密码为代换密码 时 称作单字母或单码代换 也称为流密码 时称作多字母或多码代换 也称为分组密码 2 8 2020 20 代换密码 k 明文源 密钥源 代换网络 代换密码框图 2 8 2020 21 代换密码 一般选择 即明文和密文字母表相同 此时 可以构造成1 1的映射 密码没有数据扩展 则有数据扩展 函数为1 多的映射 明文组可有多个密文组来代换 称为多名或同音 Homophonic 代换密码 则明文数据将被压缩 Compression 函数不是可逆的 保密通信 可用在数据认证系统中 单表代换 在 和时 对所有明文字母 都用一个固定的代换进行加密 多表代换 在 和时 用一个以上的代换表进行加密 2 8 2020 22 代换密码 单表代换密码 明文字母表到密文字母表的固定映射令明文 则相应密文为移位代换密码加密变换 时为恒等变换 解密变换 2 8 2020 23 单表代换密码 Caeser密码是对英文26个字母进行移位代换的密码 有下述代换表 abcdefghijklmnopqrstuvwxyz DEFGHIJKLMNOPQRSTUVWXYZABC明文 Casearcipherisashiftsubstitution密文 FDVHDUFLSKHULVDVKLIWVXEVWLWXWLRQ解密运算为 用密钥的加密表加密就可恢复明文 又称为加法密码 AdditiveCipher 2 8 2020 24 单表代换密码 乘数密码加密变换 又叫采样密码 显然 仅当 即与互素时才是一一对应的 若为素数 则有个可用密钥 否则就只有 个 其中 是是欧拉函数 表示小于且与互素的整数的个数 解密变换 定理 当且仅当时 才是一一映射 乘数密码的密钥个数为 个 对于 除去的恒等变换 还有11种选择 即3 5 7 9 11 15 17 19 21 23和25 2 8 2020 25 单表代换密码 仿射密码的加密变换 其中 以表示密钥 当时就得到乘数密码 当时就得到移位密码 多项式代换密码的加密方程为 其中 前三种密码都可看作是它的特例 2 8 2020 26 单表代换密码 密钥短语密码选一个英文短语 称其为密钥字 KeyWord 或密钥短语 KeyPhrase 如HAPPYNEWYEAR 去掉重复字母得HAPYNEWR 将它依次写在明文字母表之下 而后再将字母表中未在短语中出现过的字母依次写于此短语之后 就可构造出一个字母代换表 如下所示 A abcdefghijklmnopqrstuvwxyzA HAPYNEWRBCDFGIJKLMOQSTUVKZ 2 8 2020 27 多字母代换密码 每次对L 1个字母进行代换优点 隐蔽或均匀化字母的自然频度 利于抗击统计分析 可利用矩阵变换来描述多字母代换密码 因此也称为矩阵变换密码f ZLq ZLqf是线性变换时可用一个Zq上的L L阶矩阵K表示 K kij 为密钥 若K是满秩的 则变换为一一映射 且存在有逆变换K 1 使KK 1 K 1K I L L阶单位方阵 明文向量 m m1 m2 mL 密文向量 c c1 c2 cL mK c解密变换 cK 1 m 2 8 2020 28 Hill密码 明文向量 m m1 m2 mL 密文向量 c c1 c2 cL mK b b b1 b2 bL 是Zq上的L维矢量 K是Zq上的L L阶满秩矩阵 式中 为向量加法解密运算 m c b K 1modq例取b 0 L 2 q 26 明文m m1 m2 密文c c1 c2 若取即密钥 2 8 2020 29 置换密码 置换密码 亦称换位密码 是对明文L长字母组中的字母位置进行重新排列 而每个字母本身并不改变 当矩阵变换密码的变换矩阵为一置换阵时 相应密码就是置换密码 明文 加密变换 置换矩阵所决定置换为 解密变换 2 8 2020 30 栅栏式密码 美国南北战争时期 1861 1865年 军队中曾经使用过的 栅栏 式密码 railfencecipher 算法描述 将明文写成双轨的形式 然后按行的顺序书写得到密文明文 sendhelp加密过程 snhledep密文 snhledep 2 8 2020 31 矩阵置换密码 算法说明 以矩阵形式排列明文 将明文逐行写入矩阵 然后逐列读出 密钥指出各列读出的顺序 例明文为 abcdefghijklmnopqrstuvwxyzab 密钥为 4312567密文为 DKRYCJQXAHOVBIPWELSZFMTAGNUB 2 8 2020 32 安全性评价 无条件安全性若密文中不含明文的任何信息 则认为该密码体制是安全的 否则就认为是不安全的 已经证明 达到这样高等级 完善 的安全性 仅当所用密钥的长度不短于加密的发送消息的总长度才有可能 有条件安全性把搭线者提取明文信息的可能性改为搭线者提取明文信息的可行性 这种安全性称为有条件安全性 即搭线者在一定的计算资源条件下 他不能从密文恢复出明文 2 8 2020 33 安全性评价 攻击复杂性的度量数据复杂性 为攻击所需数据的攻击量 处理复杂性 执行攻击所须的时间 又称工作因子 存储需求 做攻击所须的存储量 加密算法的安全准则破译该密码的成本超过被加密信息的价值 破译该密码的时间超过该信息有用的生命周期 2 8 2020 34 安全性评价 1883年Kerchoffs第一次明确提出了编码的原则 加密算法应建立在算法的公开不影响明文和密钥的安全的基础上 这一原则已得到普遍承认 成为判定密码强度的衡量标准 实际上也成为古典密码和现代密码的分界线 违背Kerchoffs原则 不公开密码算法 兼容性必须信任某个可信方 如密码提供商 一旦泄密 后果严重公开算法经历众人的分析 时间的考验 不会有太严重的缺陷 2 8 2020 35 密码分析 密码分析 截收者在不知道解密密钥及通信者所采用的加密体制的细节条件下 对密文进行分析试图获取机密信息 密码分析在外交 军事 公安 商业等方面都具有重要作用 也是研究历史 考古 古语言学和古乐理论的重要手段之一 密码设计和密码分析是共生的 又是互逆的 两者密切有关但追求的目标相反 两者解决问题的途径有很大差别 2 8 2020 36 密码分析 密码设计是利用数学来构造密码 而密码分析除了依靠数学 工程背景 语言学等知识外 还要靠经验 统计 测试 眼力 直觉判断能力 有时还靠点运气 密码分析过程通常经验 统计 统计截获报文材料 假设 推断和证实等步骤 破译 Break 或攻击 Attack 密码的方法 穷举破译法 又称作蛮力法分析法 有确定性和统计性两类 2 8 2020 37 穷举破译法 是对截收的密报依次用各种可解的密钥试译 直到得到有意义的明文 或在不变密钥下 对所有可能的明文加密直到得到与截获密报一致为止 此法又称为完全试凑法 只要有足够多的计算时间和存储容量 原则上穷举法总是可以成功的 但实际中 任何一种能保障安全要求的实用密码都会设计得使这一方法在实际上是不可行的 为了减少搜索计算量 可以采用较有效的改进试凑法 它将密钥空间划分成几个 例如 q个 等可能的子集 对密钥可能落入哪个子集进行判断 至多需进行q次试验 关键在于如何实现密钥空间的等概子集的划分 2 8 2020 38 蛮力攻击PK密钥长度 2 8 2020 39 分析法 确定性分析法利用一个或几个已知量 比如 已知密文或明文 密文对 用数学关系式表示出所求未知量 如密钥等 已知量和未知量的关系视加密和解密算法而定 寻求这种关系是确定性分析法的关键步骤 例如 以n级线性移存器序列作为密钥流的流密码 就可在已知2nbit密文下 通过求解线性方程组破译 统计分析法利用明文的已知统计规律进行破译的方法 密码破译者对截收的密文进行统计分析 总结出其间的统计规律 并与明文的统计规律进行对照比较 从中提取出明文和密文之间的对应或变换信息 2 8 2020 40 密码分析 密码分析之所以能够破译密码 最根本的是依赖于明文中的多余度 这是Shannon1949年用他开创的信息论理论第一次透彻地阐明的密码分析的基本问题 根据密码分析者可获取的信息量来分类 可将破译密码的类型分为以下四种 下页 2 8 2020 41 密码分析 惟密文破译 分析者从仅知道的截获密文进行分析 试图得出明文或密钥 已知明文破译 分析者除了有截获的密文外 还有一些已知的明文 密文对 通过各种手段得到的 试图从中得出明文或密钥 选择明文破译 分析者可以选定任何明文 密文对来进行攻击 以确定未知的密钥 选择密文攻击 分析者可以利用解密机 按他所选的密文解密出相应的明文 双钥体制下 类似于选择明文攻击 他可以得到任意多的密文对密码进行分析 这几类攻击的强度依次增大 唯密文攻击最弱 2 8 2020 42 密码分析 密码分析的成功除了靠上述的数学演绎和归纳法外 还要利用大胆的猜测和对一些特殊或异常情况的敏感性 一个保密系统是否被 攻破 并无严格的标准 密码史表明 密码分析者的成就似乎远比密码设计者的成就更令人赞叹 许多开始时被设计者吹为 百年或千年难破 的密码 没过多久就被密码分析者巧妙地攻破了 在第二次世界大战中 美军破译了日本的 紫密 使得日本在中途岛战役中大败 一些专家们估计 同盟军在密码破译上的成功至少使第二次世界大战缩短了8年 2 8 2020 43 密码破译实例 图灵等破密恩尼格玛 Enigma 1936年 24岁的图灵提出 图灵机 的设想 二战期间成功地破译了纳粹德国的恩尼格玛密码 希腊语Enigma 意指 不可思议的东西 图灵发明了 炸弹 Bombes 的解密机器 1952年 图灵遭到警方拘捕 原因是同性恋 1954年6月8日 服毒自杀 年仅42岁 图灵去世12年后 美国计算机协会以他的名字命名了计算机领域的最高奖 图灵奖 2 8 2020 44 密码破译实例 Rivest等最初悬赏 100的RSA 129 已由包括五大洲43个国家600多人参加 用1600台机子同时产生820条指令数据 通过Internet网 耗时8个月 于1994 4 2利用二次筛法分解出为64位和65位的两个因子 原来估计要用4亿亿年 所给密文的译文为 这些魔文是容易受惊的鱼鹰 这是有史以来最大规模的数学运算 RSA 130于1996 4 10利用数域筛法分解出来 2 8 2020 45 密码破译实例 1999年8月22日 来自六个不同国家的科学家们在CWI CWI是在荷兰的一个数学和计算机科学的国家研究学会 的Riele的带领下 在对RSA 155的攻击中 利用数域筛法 NFS 成功的分解出了512 bitRSA模的素因子 要分解RSA 155所需的CPU时间大约为8400MIPS年 MIPS 年指以每秒执行1000000条指令的计算机运行一年 这大约为分解RSA 140所需时间的4倍 分解RSA 155总共用了7个月的时间 密码分析者估计在3年内分解RSA 155所用到的算法和计算技术至少在科技界将会得到普及 因此RSA 155将不再安全 并且人们预计 在十年内RSA 232也将被攻破 2 8 2020 46 隐写术 字符标记 印刷或打印的文本字母经选择用铅笔重写 该标记通常不可见 除非该纸以一定的角度对着亮光看 不可见墨水 使用一些物质来书写 但不留下任何可见痕迹 除非加热该纸或在该纸上涂上某种化学药品 扎小孔 在所选的字母上扎小孔 这些小孔通常不可见 除非把该纸放在光的前面 打字机改正带 用于行间与一根黑带一同打印 用改正带打印的结果仅在强光下才可见 格孔密写卡 将它覆盖在一张纸上从格孔中写入密件 然后在纸上余下部分填入其它字句 使它像一般信件 2 8 2020 47 隐写术 王先生 来信收悉 你的盛情真是难以报答 我已在昨天抵达广州 秋雨连绵 每天需备伞一把方能上街 苦诶 大约本月中旬我才能返回 届时再见 弟李明 情报在雨伞中 2 8 2020 48 分组密码 2 8 2020 49 分组密码 单钥分组密码是许多系统安全的一个重要组成部分 分组密码易于构造伪随机数生成器 流密码 消息认证码 MAC 和杂凑函数等 还可进而成为消息认证技术 数据完整性机构 实体认证协议以及单钥数字签字体制的核心组成部分 实际应用中对于分组码可能提出多方面的要求 除了安全性外 还有运行速度 存储量 程序的长度 数据分组长度 高速缓存大小 实现平台 硬 软件 芯片 运行模式等限制条件 这些都需要与安全性要求之间进行适当的折衷选择 2 8 2020 50 分组密码 分组密码加密函数 分组密码框图 明文 密文 明文 密钥 密钥 n为分组长度 通常为64 128 t为密钥长度 通常为64 128 2 8 2020 51 分组密码 分组密码的设计问题在于找到一种算法 能在密钥控制下从一个足够大且足够好的置换子集中 简单而迅速地选出一个置换 用来对当前输入的明文的数字组进行加密变换 设计的算法应满足下述要求 分组长度n要足够大 防止明文穷举攻击法奏效 密钥量要足够大 尽可能消除弱密钥并使所有密钥同等地好 以防止密钥穷举攻击奏效 由密钥确定置换的算法要足够复杂 充分实现明文与密钥的扩散和混淆 没有简单的关系可循 要能抗击各种已知的攻击 2 8 2020 52 分组密码 加密和解密运算简单 易于软件和硬件高速实现 数据扩展 一般无数据扩展 在采用同态置换和随机化加密技术时可引入数据扩展 差错传播尽可能地小 实现上述几点要求并不容易 首先 代换网络的复杂性随分组长度n呈指数增大 常常会使设计变得复杂而难以控制和实现 实际中常常将n分成几个小段 分别设计各段的代换逻辑实现电路 采用并行操作达到总的分组长度n足够大 这将在下面讨论 其次 为了便于实现 实际中常常将较简单易于实现的密码系统进行组合 构成较复杂的 密钥量较大的密码系统 2 8 2020 53 分组密码 安全设计准则混淆 confusion 使得密钥和明文以及密文之间的依赖关系相当复杂以至于这种依赖性对密码分析者来说是无法利用的 目前主要采用代换 Substitution 运算以及非线性运算等扩散 diffusion 密钥的每一位数字影响密文的许多位数字以防止对密钥进行逐段破译 而且明文的每一位数字也应影响密文的许多位数字以便隐蔽明文数字统计特性 最简单的扩散是换位 Permutation 2 8 2020 54 分组密码 实现准则软件实现的要求 使用子块和简单的运算 密码运算在子块上进行 要求子块的长度能自然地适应软件编程 如8 16 32比特等 应尽量避免按比特置换 在子块上所进行的密码运算尽量采用易于软件实现的运算 最好是用标准处理器所具有的一些基本指令 如加法 乘法 移位等 硬件实现的要求 加密和解密的相似性 即加密和解密过程的不同应仅仅在密钥使用方式上 以便采用同样的器件来实现加密和解密 以节省费用和体积 尽量采用标准的组件结构 以便能适应于在超大规模集成电路中实现 2 8 2020 55 分组密码 简单性原则 包括规范的简单性和分析的简单性 必须能抗击所有已知的攻击 特别是差分攻击和线性攻击 可扩展性 要求能提供128 192 256比特的可变分组或密钥长 2 8 2020 56 分组密码的历史 美国于1973年向社会公开征集数据加密算法 最后由IBM公司提出的方案中标 由美国国家标准局在1977年颁布成为数据加密标准 DES DES是分组加密算法 其分组长度为64 使用56比特密钥 即key 56 从DES算法投入使用以来 人们一直在试图分析寻找它的弱点 其中差分分析法和线性分析法最具危胁 但这些方法并没有根本性的突破 1997年 在Internet上采用穷举密钥攻击法仅用了96天 即在一台非常普通的PC上成功破译 用专业解密机用56小时 目前仅为几小时 就可破译 2 8 2020 57 分组密码的历史 DES的设计安全期之后设计新的更好的分组密码算法 如IDEA InternationalDataEncryptionAlgorithm 采用TripleDES1997年1月美国国家标准和技术研究所 NIST 向全世界密码学界发起征集AES AdvancedEncryptionStandard 算法得公告 并成立了AES标准工作研究室确定一个非保密的 公开披露的 全球免费使用的加密算法 用于保护下一世纪政府的敏感信息也希望能够成为保密和非保密部门公用的数据加密标准 DES 2 8 2020 58 分组密码的历史 AES的标准提纲 1 AES是公开的 2 AES为单钥体制分组密码 3 AES的密钥长度可变 可按需要增大 4 AES适于用软件和硬件实现 5 AES可以自由地使用 或按符合美国国家标准策略的条件使用 6 满足以上要求的AES算法 需按下述条件判断优劣 安全性 计算效率 内存要求 使用简便性 灵活性 2 8 2020 59 分组密码的历史 1998年4月15日全面征集AES算法的工作结束 1998年8月20日举行了首届AES讨论会 对涉及14个国家的密码学家所提出的候选AES算法进行了评估和测试 初选并公布了15个被选方案 供大家公开讨论1999年8月9日NIST宣布第二轮筛选出的5个候选算法为 MARS C Burwick等 IBM RC6TM R Rivest等 RSALab RIJNDEAL VincentRijmen JoanDaemen 比利时 SERPENT R Anderson等 英 以 挪威 TWOFISH B Schiener 2 8 2020 60 分组密码的历史 2000年10月2日NIST宣布比利时密码学专家设计的Rijndael 荣代尔 算法作为最终AES的算法 在美国征集AES结束之际 欧洲也进行了称为NESSIE NewEuropeanSchemesforSignature Integrity andEncryption 的密码大计划 是欧洲的信息社会技术 IST 委员会计划出资33亿欧元支持的一项工程 于2000年3月公布了征集公告 2 8 2020 61 DES算法 2 8 2020 62 DES介绍 1973年5月15日 NBS开始公开征集标准加密算法 并公布了它的设计要求 算法必须提供高度的安全性算法必须有详细的说明 并易于理解算法的安全性取决于密钥 不依赖于算法算法适用于所有用户算法适用于不同应用场合算法必须高效 经济算法必须能被证实有效算法必须是可出口的 2 8 2020 63 DES算法介绍 1974年8月27日 NBS开始第二次征集 IBM提交了算法LUCIFER 该算法由IBM的工程师在1971 1972年研制1975年3月17日 NBS公开了全部细节1976年 NBS指派了两个小组进行评价1976年11月23日 采纳为联邦标准 批准用于非军事场合的各种政府机构1977年1月15日 数据加密标准 FIPSPUB46发布 同年7月15日开始生效 2 8 2020 64 DES算法介绍 该标准规定每五年审查一次 计划十年后采用新标准最近的一次评估是在1994年1月 已决定1998年12月以后 DES将不再作为联邦加密标准 FIPSPUB81 DES的工作方式 在1980年公布FIPSPUB74 实现和使用DES的指南 于1981年公布FIPSPUB112规定了DES用作口令加密的标准FIPSPUB113规定了DES如何用作计算机数据鉴别 2 8 2020 65 DES算法步骤 算法分三个阶段实现 给定明文X 通过一个固定的初始置换IP来排列X中的位 得到X0 IP X L0R0 其中L0由X0前32位组成 R0由X0的后32位组成 计算函数F的16次迭代 根据下述规则来计算 LiRi 1 i 16 Li Ri 1 Ri Li 1 F Ri 1 Ki 其中Ki是长为48位的子密钥 子密钥K1 K2 K16是作为密钥K 56位 的函数而计算出的 对比特串R16L16使用逆置换IP 1得到密文Y Y IP 1 R16L16 2 8 2020 66 DES算法步骤 2 8 2020 67 一轮加密简图 2 8 2020 68 子密钥的产生 实际上 K是长度为64的位串 其中56位是密钥 8位是奇偶校验位 为了检错 在密钥编排的计算中 这些校验位可略去 给定64位的密钥K 放弃奇偶校验位 8 16 64 并根据固定置换PC 1来排列K中剩下的位 我们写PC 1 K C0D0 其中C0由PC 1 K 的前28位组成 D0由后28位组成 对1 i 16 计算Ci LSi Ci 1 Di LSi Di 1 LSi表示循环左移2或1个位置 取决于i的的值 i 1 2 9和16时移1个位置 否则移2位置 Ki PC 2 CiDi 2 8 2020 69 子密钥的产生 2 8 2020 70 DES算法争论 弱密钥与半弱密钥DES的破译和对密钥长度的争论DES的轮数S 盒的设计原理未知 2 8 2020 71 DES的弱密钥 初始密钥被分成两部分 每部分都单独做移位 如果每一部分的每一位都是0或都是1 则每一圈的子密钥都相同 这样的密钥被称为弱密钥 DES存在4个弱密钥 2 8 2020 72 DES半弱密钥 有些成对的密钥会将明文加密成相同的密文 即一对密钥中的一个能用来解密由另一个密钥加密的消息 这种密钥称作半弱密钥 这些密钥不是产生16个不同的子密钥 而是产生两种不同的子密钥 每一种出现8次 至少有12个半弱密钥还有些密钥只产生四种子密钥 每种出现四次 这种密钥称为半半弱密钥 共48个 2 8 2020 73 S盒问题 DES的核心是S盒 除此之外的计算是属线性的 S盒作为该密码体制的非线性组件对安全性至关重要 S Box的设计细节 NSA和IBM都未公开过 Hellman在1976年指出 在DES中仔细选择一些S盒 可以使安全性降低 他们以自己设计的S盒代替DES原来的S盒 证明可以做到这一点 且在一定程度上可以隐蔽S盒构造上的弱点 1990年 密码学家EliBiham和AdiShamir首次提出差分分析方法 并找到对DES的选择明文攻击 2 8 2020 74 分组密码运行模式 2 8 2020 75 分组密码运行模式 分组密码每次加密的明文数据量是固定的分组长度n 而实用中待加密消息的数据量是不定的 数据格式可能是多种多样的 因此需要做一些变通 灵活地运用分组密码 另一方面 即使有了安全的分组密码算法 也需要采用适当的工作模式来隐蔽明文的统计特性 数据的格式等 以提高整体的安全性 降低删除 重放 插入和伪造成功的机会 所采用的工作模式应当力求简单 有效和易于实现美国NSB在 FIPSPUB74和81 中规定了DES的四种基本工作模式 电子码本 ECB 密码反馈链接 CBC 密码反馈 CFB 输出反馈 OFB ANSI ISO和ISO IEC也规定了类似的工作模式 2 8 2020 76 ECB模式 电码本 ElectronicCodeBook 相同明文 相同密文同样信息多次出现造成泄漏信息块可被替换信息块可被重排密文块损坏 仅对应明文块损坏适合于传输短信息 2 8 2020 77 ECB模式 ECB模式示意图 2 8 2020 78 CBC模式 密码分组链接 CBC 加密 解密 需要共同的初始化向量相同明文 不同密文初始化向量IV可以用来改变第一块密文块损坏 两明文块损坏安全性好于ECB 2 8 2020 79 CBC模式 CBC模式示意图 2 8 2020 80 CFB模式 CFB CipherFeedback 分组密码 流密码为移位寄存器 为流单元宽度加密 解密 需要共同的移位寄存器初始值一个单元损坏影响多个单元 为分组加密块大小 2 8 2020 81 CFB模式 CFB模式示意图 2 8 2020 82 密码学的数论基础 2 8 2020 83 密码学的数论基础 素数Fermat定理和Euler定理素性测试中国剩余定理离散对数 2 8 2020 84 素数 一个只能被1以及自身整除并且大于1的整数称为素数 也称为质数小于200的素数 2357111317192329313741434753596167717379838997101103107109113127131137139149151157163167173179181191193197199合数 4 6 8 9 10 12 2 8 2020 85 关于素数的一些疑问 素数有多少个 如何寻找素数 如何判断一个数是否为素数 例如2003例如9909408073 2 8 2020 86 欧几里得 EuclidofAlexandria 约公元前330 约公元前275 欧几里得的 几何何原本 是用公理方法建立演绎数学体系的最早典范欧几里德在他的中证明了素数有无穷多 2 8 2020 87 素数有多少 定理 素数有无穷多个证明 假设素数只有有限多个 并记最大的素数为P 定义Q 2 3 5 7 P 1 根据假设 Q是一个合数 同时用Q除以任何素数都余1 所以所有的素数都不是Q的因数 这是不可能的 所以素数有无穷多个 2 8 2020 88 筛法求素数 寻找在给定范围内的素数排列 有埃拉托斯特尼 Eratosthenes 筛法Eratosthenes 公元前276年 公元前194年 希腊数学家 地理学家 天文学家 主要贡献是设计出经纬度系统 计算出地球的直径埃拉托斯特尼筛法是一种简单的列出小于给定数的所有素数的算法 2 8 2020 89 筛法求素数 找指定范围内所有素数首先把2 m内所有数放入筛中 然后找出筛中最小的素数 并将该数在范围之内的所有倍数的数去掉 依次进行 直到筛中的最小的素数已经超出m的范围最小素数去掉所有倍数以后的数中近邻的数即是下次循环的最小素数退出的条件是 最小素数已经等于最大的数 即指定的查找范围 2 8 2020 90 筛法求素数 列出如下这样以2开头的序列2345678910111213141516171819202122232425标出序列中的第一个素数 主序列变成2345678910111213141516171819202122232425将剩下序列中2的倍数划掉 用红色标出 主序列变成2345678910111213141516171819202122232425如果现在这个序列中最大数小于第一个素数的平方 那么剩下的序列中所有的数都是素数 否则返回第二步 2 8 2020 91 筛法求素数 本例中 因为25大于2的平方 我们返回第二步剩下的序列中第一个素数是3 将主序列中3的倍数划出 红色 主序列变成 234567891011121314151617181920212223242525仍然大于3的平方 所以我们还要返回第二步现在序列中第一个素数是5 同样将序列中5的倍数划出 主序列成了 2345678910111213141516171819202122232425因为25等于5的平方 跳出循环 去掉红色的数字 2到25之间的素数是 23571113171923 2 8 2020 92 寻找素数 数学家一直努力找寻产生素数的公式 但截至目前为止 并没有一个函数或是多项式可以正确产生所有的素数 历史上有许多试验的例子 如默森 费马等 2 8 2020 93 寻找素数 默森 Mersenne 1588 1648 法国人 神父默森数 1644 2p 1 2 8 2020 94 默森数 23 1 725 1 3127 1 127211 1 2047 23 89213 1 8191217 1 131071219 1 524287223 1 838607 47 178481229 1 536870911 233 2304167231 1 2147483647 2 8 2020 95 默森数 于是默森提出如下的猜想 当p 2 3 5 7 13 17 19 31 67 127 257时 2p 1会是素数对于其余小于257的44个素数p 2p 1都是合数但后来的数学家发现 当p 67和257时 2p 1不是素数 但当p 61 89 107时 2p 1却是素数 实际上 如果对某正整数n 2n 1是素数 则n一定是素数 2 8 2020 96 当今发现的最大素数第42个一致的默森数225964951 12005年2月26日公布 2 8 2020 97 费马 费马 PierredeFermat 1601 1665 法国人律师 1631年出任图卢兹议院顾问业余研究数学他是几何学 概率论 微积分 数论等领域的先驱 2 8 2020 98 费马数 220 1 3221 1 5222 1 17223 1 257224 1 65537 于是费马猜想所有写成22n 1形式的数都是素数 2 8 2020 99 欧拉 欧拉 LeonhardEuler 1707 1783 瑞士数学家13岁入大学 17岁取得硕士学位证明不是素数 2 8 2020 100 证明F5不是素数 记a 27和b 5 则a b3 3 1 ab b4 1 a b3 b 1 3b 16 24 225 1 232 1 2a 4 1 24a4 1 1 ab b4 a4 1 1 ab a4 1 a4b4 1 ab a4 1 ab 1 a2b2 即232 1可被1 ab 641整除 注 232 1 4294967297 641 6700417 2 8 2020 101 高斯 高斯 CarlFriedrichGauss 1777 1855 德国数学家 近代数学的奠基人之一 人称 数学王子 19岁提出以直尺和圆规绘画正17边形的方法 提出绘画素数多边形形的充分必要条件是该素数必定是费马数 2 8 2020 102 素数分布 素数定理描述素数的大致分布情况其中 n 表示不大于n的素数的数目 例如 10 4 100 25 等若n趋向无穷大 则 n n趋向0 即当n越大时 素数的 密度 会越小 2 8 2020 103 算术基本定理 任一正整数都能表成若干素数的乘积 为素数 并且若不计的排列次序 上述表法唯一素因子标准分解式 任何正整数都可以唯一地表示成 2 8 2020 104 费马小定理 Fermat定理其中为素数 素性判定 Fermat定理的逆定理不成立 满足条件的合数叫Carmichael数 最小的是561 3 11 17 2 8 2020 105 欧拉函数 指小于n并且与n互素的正整数的个数 记 n 对于素数p有 p p 1对于n pq p q均为素数 有 pq p 1 q 1 pq ofnumbersfrom1topqp ofmultiplesofquptopqq ofmultiplesofpuptopq1 ofmultipleofbothpandquptopq pq pq p q 1 p 1 q 1 例如 37 36 21 3 1 7 1 2 6 12 2 8 2020 106 欧拉函数 积性函数 即如果 则如果 有 2 8 2020 107 欧拉定理 Euler定理其中例如 a 3 n 10 10 4 有34 81 1mod10a 2 n 11 11 10 有210 1024 1mod11 2 8 2020 108 素性测试 对于数m 从i 2 3 4 5 到m 1判断m能否被i整除 如果全部不能整除 则m是素数 只要有一个能除尽 则m不是素数 为了压缩循环次数 可将判断范围从2 m 1变为2 int sqr m 2 8 2020 109 素性测试 i 2 j sqr m 初始化DoWhile i0i i 1Loop 根据退出的两种情况来判断是否素数 Ifi jthen是素数else有整除情况endif 2 8 2020 110 Miller Rabin素性测试算法 基于费马小定理算法TEST n 如下 1 Findintegersk q k 0 qodd sothat n 1 2kq2 Selectarandomintegera 1 a n 13 ifaqmodn 1thenreturn maybeprime 4 forj 0tok 1do5 if a2jqmodn n 1 thenreturn maybeprime 6 return composite 2 8 2020 111 Miller Rabin素性测试算法 概率算法Acompositenumberpassthetestwith prob Whenttestsareusedwithindependenta acompositepasseswith tprob henceifrepeattestwithdifferentrandomathenchancenisprimeafterttestsis Pr nprimeafterttests 1 4 teg fort 10thisprobabilityis 0 99999 2 8 2020 112 素性测试 素性测试确定性方法 Lucas Lehmer和ellipticcurveprimalityproving 概率性方法 Fermatprimalitytest Rabin Miller 2 8 2020 113 中国剩余定理 孙子算经 今有物不知其数 三三数之剩二 五五数之剩三 七七数之剩二 问物几何 答曰 二十三 表示为N 2 mod3 3 mod5 2 mod7 其最小正数解是23 孙子算经 中给出了其中关键的步骤是 凡三三数之剩一 则置七十 五五数之剩一 则置二十一 七七数之剩一 则置十五 即N 70 2 21 3 15 2 2 105 23 原题及其解法中的3 5 7后来叫 定母 70 21 15叫 乘数 2 8 2020 114 中国剩余定理 三人同行七十稀 五树梅花廿一枝 七子团圆整半月 除百零五便得知 在 孙子算经 中并没有说明求乘数的方法 直到1247年宋代数学家秦九韶在 数书九章 中才给出具体求法 70是5与7最小公倍的2倍 21 15分别是3与7 3与5最小公倍数的1倍 秦九韶称这2 1 1的倍数为 乘率 求出乘率 就可知乘数 2 8 2020 115 中国剩余定理 同余方程组 算法 计算计算计算 2 8 2020 116 中国剩余定理 用来加速模运算对多个数的乘积求模例如中国剩余定理让我们可以先单独计算模每个 从而加快计算模在RSA中用于加速计算 2 8 2020 117 本原根 由欧拉定理 有考虑一定存在 但可能小于一旦幂达到 出现循环如果最小的 是 则称是一个本原根是素数的一个本原根 则 是1到的排列 2 8 2020 118 本原根的性质 并不是所有的整数都有原根 事实上只有形为2 4 p 和2p 的整数才有原根 这里p为奇素数 为正整数如果a是n的一个原根 则Zn aimodn 0 i n ifaisagenerator b aimodnisalsoageneratoriffgcd i n 1aisageneratoriffa n p 1modnforeachprimedivisorpof n 2 8 2020 119 离散对数问题 theinverseproblemtoexponentiationistofindthediscretelogarithmofanumbermodulopthatistofindxwhereax bmodpwrittenasx logabmodporx inda p b ifaisaprimitiverootthenalwaysexists otherwisemaynotx log34mod13 xst3x 4mod13 hasnoanswerx log23mod13 4bytryingsuccessivepowerswhilstexponentiationisrelativelyeasy findingdiscretelogarithmsisgenerallyahardproblem 2 8 2020 120 离散对数 2 8 2020 121 离散对数问题 已知 计算是容易的已知 计算是非常困难的目前已知最快求模数为素数的离散对数的异步算法的难度为 2 8 2020 122 哥德巴赫猜想 1742 每一个不小于6的偶数 都可表示为两个素数之和例如8 3 5 20 7 13 100 17 83 等等每一个不小于9的奇数 都可表示为三个素数的和 2 8 2020 123 哥德巴赫猜想论证历程 1920挪威布朗9 91948匈牙利瑞尼1 c1958中国王元2 31962中国潘承洞1 51963中国王元 潘承洞1 41965苏联维诺格拉道夫1 31966中国陈景润1 2 2 8 2020 124 陈景润 福建福州人 1933 1996 1957年得到华罗庚提拔 进入北京科学院当研究员1966年首次发表他对 哥德巴赫猜想 的研究成果 2 8 2020 125 双重DES C EK2 EK1 P