密码学基础---2010.ppt

1 密码学基础 主讲人 翟健宏Email zhaijh 办公室 新技术楼509Tel 0451 86402573 2 内容 密码体系概述古典密码对称密钥密码公开密钥密码数字签名与摘要函数 3 数据加密基本概念 密码 是一组含有参数的变换明文 plaintext 作为加密输入的原始信息加密算法 变换函数密文 ciphertext 明文变换结果密钥 key 参与变换的参数 4 加密通信的模型 密码学的目的 Alice和Bob两个人在不安全的信道上进行通信 而破译者Oscar不能理解他们通信的内容 5 密码体制 通常一个完整密码体制要包括如下五个要素M C K E DM是可能明文的有限集称为明文空间C是可能密文的有限集称为密文空间K是一切可能密钥构成的有限集称为密钥空间对于密钥空间的任一密钥 有一个加密算法和相应的解密算法使得ek M C和dk C M 分别为加密解密函数 满足 这里 6 一个密码体制必须满足如下特性 每一个加密函数Ek和每一个解密函数Dk都能有效地计算破译者取得密文y后 将不能在有效的时间内破解出密钥k或明文x一个密码系统是安全的必要条件 穷举密钥搜索将是不可行的 即密钥空间非常大 7 密码分类 按发展进程分 古典密码对称密钥密码公开密钥密码按密钥管理的方式分为秘密密钥算法公开密钥算法按加密模式分 序列密码分组密码 8 密码体系概述古典密码对称密钥密码公开密钥密码数字签名与摘要函数 9 经典密码 代替密码 简单代替 多名或同音代替 多表代替 多字母或多码代替 简单代替密码将明文字母表M中的每个字母用密文字母表C中的相应字母来代替 这一类密码包括移位密码 替换密码 仿射密码 乘数密码等 10 移位密码 移位密码 是最简单的一类代替密码 将字母表的字母右移k个位置 并对字母表长度作模运算 加密变换 ek m k m modq 解密变换 dk c m k modq 11 凯撒Caesar密码 Caesar密码是对英文26个字母进行移位代替的密码 其M C q 26 k 3 使用凯撒密码将明文M meetmeafterthetogaparty加密为C phhwphdiwhowkhwrjdsduwb 12 乘数密码 乘数密码 是一种替换密码 它将每个字母乘以一个密钥k 即Ek m kmmodq 其中k和q为互素的 这样字母表中的字母会产生一个复杂的剩余集合 若k和q不互素 则会有一些明文字母被加密成相同的密文字母 而且 不是所有的字母都会出现在密文字母表中 算法描述设M C Z 26 K a Z 26 gcd a 26 1 x y Z 26 对k a K Ek x ax mod26 Dk y a 1 y mod26 aa 1modq 1a 5 a 1 21a 7 a 1 15 13 例子 a 9 Ek x 9x mod26 ABCDEFGHIJKLMNOPQRSTUVWXYZAJSBKTCLUDMVENWFOXGPYHQZIR明文 密文cipher SUFLKX对于乘数密码 当且仅当a与 互素时 加密变换才是一一映射的 因此a的选择有11种 a 3 5 7 9 11 15 17 19 21 23 25 可能尝试的密钥只有11个 14 仿射密码 仿射密码是替换密码的另一个特例 形式为ek m k1m k2 modq cmodq 其中k1和q是互素的 k1 1 3 5 7 9 11 15 17 19 21 23 25定义 ek x ax b mod26 dk y a 1 y b mod26 x y Z 26 q 26时 可能的密钥是26 12 312个 15 仿射密码 例 例子 设k 7 3 注意到7 1 mod26 15 加密函数是ek x 7x 3 mod26 相应的解密函数是dk y 15 y 3 15y 19 mod26 易见dk ek x dk 7x 3 15 7x 3 19 x 45 19 x mod26 若加密明文 hot 首先转换字母hot成为数字7 14 19 加密 解密 16 单表替换密码的破译 通过字母的使用频率破译 17 多表代替密码 单字母出现频率分布与密文中相同 安全性受到威胁 多表代替密码思想 使用从明文字母到密文字母的多个映射 来隐藏单字母出现的频率分布 每个映射是简单代替密码中的一对一映射 维吉尼亚Vigenere密码 博福特Beaufort密码均是多表代替密码 维吉尼亚Vigenere密码算法如下 设密钥明文加密变换ek m c1c2 cn 其中 Ci mi ki mod26 密钥k可以通过周期性地延长 反复进行以至无穷 18 密码体系概述古典密码对称密钥密码公开密钥密码数字签名与摘要函数 19 对称密钥密码模型 20 数据加密标准 DES的产生1973年5月15日 NBS开始公开征集标准加密算法 并公布了它的设计要求 1 算法必须提供高度的安全性 2 算法必须有详细的说明 并易于理解 3 算法的安全性取决于密钥 不依赖于算法 4 算法适用于所有用户 5 算法适用于不同应用场合 6 算法必须高效 经济 7 算法必须能被证实有效 8 算法必须是可出口的1974年8月27日 NBS开始第二次征集 IBM提交了算法LUCIFER 该算法由IBM的工程师在1971 1972年研制最近的一次评估是在1994年1月 已决定1998年12月以后 DES将不再作为联邦加密标准 21 简化的DES SimplifiedDES方案 简称S DES方案 加密算法涉及五个函数 1 初始置换IP initialpermutation 2 复合函数fk1 它是由密钥K确定的 具有置换和替代的运算 3 转换函数SW 4 复合函数fk2 5 初始置换IP的逆置换IP 1 6 置换函数P8 P10 22 S DES的流程 23 1 S DES的密钥生成 设10bit的密钥为 k1 k2 k3 k4 k5 k6 k7 k8 k9 k10 置换P10是这样定义的P10 k1 k10 k3 k5 k2 k7 k4 k10 k1 k9 k8 k6 相当于P10 35274101986 LS 1为循环左移一次 置换P8 637485109 24 算法如下图若K选为 1010000010 产生的两个子密钥分别为K1 10100100 K2 01000011 25 2 S DES的加密运算 初始置换用IP函数 IP 末端算法的置换为IP的逆置换 IP 1 易见IP 1 IP X X 26 简化的得DES方案加密细节如右图 27 函数fkfk L R L F R SK R 是加密方案中的最重要部分 其中 L R为8位输入的左右各4位 F为从4位集到4位集的一个映射 SK为子密钥 28 对映射F来说 首先输入是一个4位数 n1 n2 n3 n4 第一步运算是扩张 置换 E P 运算 E P 41232341 29 然后 E P的结果与子密钥作异或运算得 8 bit子密钥 K1 k11 k12 k13 k14 k15 k16 k17 k18 30 把它们重记为8位 31 上述第一行的4位输入进S盒S0 产生2 位的输出 第二行的4位输入进S盒S1 产生2 位的输出 两个S盒按如下定义 32 S盒按下述规则运算 将第1和第4的输入比特做为2bit数 指示为S盒的一个行 将第2和第3的输入比特做为S盒的一个列 如此确定为S盒矩阵的 i j 数 例如 P0 0 P0 3 00 并且 P0 1 P0 2 10 确定了S0中的第0行2列 0 2 的系数为3 记为 11 输出 由S0 S1输出4bit经置换P4 2431 即F的输出 33 回顾 34 DES是一种对二元数据进行加密的算法 数据分组长度为64位 密文分组长度也是64位 使用的密钥为64位 有效密钥长度为56位 有8位用于奇偶校验 解密时的过程和加密时相似 但密钥的顺序正好相反 DES的整个体制是公开的 系统的安全性完全靠密钥的保密 35 36 其它分组加密算法 三重DES IDEA RC5 RC6 Blowfish CAST RC2AES算法 为AES开发Rijndael算法的是两位来自比利时的密码专家Joandaemen博士 VincentRijmen 37 密码体系概述古典密码对称密钥密码公开密钥密码数字签名与摘要函数 38 公钥加密模型 39 公钥密码体制 公钥密码又称为双钥密码和非对称密码1976年由Diffie和Hellman在其 密码学新方向 一文中提出的 见划时代的文献W DiffieandM E Hellman NewDirectrionsinCryptography IEEETransactiononInformationTheory V IT 22 No 6 Nov1976 PP 644 654 单向陷门函数是满足下列条件的函数f给定x计算y f x 是容易的 给定y 计算x使y f x 是困难的 所谓计算x f 1 Y 困难是指计算上相当复杂已无实际意义 存在 已知 时 对给定的任何y 若相应的x存在 则计算x使y f x 是容易的 40 基于公开密钥的加密过程 41 基于公开密钥的鉴别过程 42 公钥密码实现保密 鉴别 用户拥有自己的密钥对 KU KR 保密 A B Y EKUb X B DKRb Y DKRb EKUb X X鉴别 条件 两个密钥中任何一个都可以用作加密而另一个用作解密A ALL Y DKRa X ALL EKUa Y EKUa DKRa X X鉴别 保密 A B Z EKUb DKRa X B EKUa DKRb Z X 43 数论问题 离散对数 y gxmodp已知g x p 计算y是容易的 已知y g p 计算x是困难的 表示amodp bmodp 称 模P同余 素数p的原根 primitiveroot 如果a是素数p的原根 则数amodp a2modp ap 1modp是不同的并且包含1到p 1的整数的某种排列 对任意的整数b 我们可以找到唯一的幂I满足b aimodp 0 i p 1 44 Diffie Hellman密钥交换 对Diffie Hellman密钥交换协议描述Alice和Bob协商好一个大素数p 和大的整数g 1 g p g是p的原根 p和g无须保密 可为网络上的所有用户共享 当Alice和Bob要进行保密通信时 他们可以按如下步骤来做 1 Alice送取大的随机数x 并计算Y gx modP 2 Bob选取大的随机数x 并计算Y gx modP 3 Alice将Y传送给Bob Bob将Y 传送给Alice 4 Alice计算K Y x modP 5 Bob计算K Y x modP 易见 K K gxx modP 45 RSA密码体制 欧拉定理若整数g和n互素 则g n 1 modn 其中 n 为比n小 但与n互素的正整数个数 称为 n 为欧拉函数 n pq n p 1 q 1 RSA密码体制明文空间P 密文空间C Zn 密钥的生成选择p q p q为互异素数 计算n p q n p 1 q 1 选择整数e使gcd n e 1 1 e n 计算d 使d e 1 mod n 公钥Pk e n 私钥Sk d p q 46 RSA密码加密和解密函数加密 用e n 明文 M n 密文 C Me modn 解密 用d p q 密文 C 明文 M Cd modn 注意 加密和解密是一对逆运算 47 RSA例子 若Bob选择了p 101和q 113 那么 n 11413 n 100 112 11200 然而11200 26 52 7 一个正整数e能用作加密指数 当且仅当e不能被2 5 7所整除 事实上 Bob不会分解 n 而且用辗转相除法 欧式算法 来求得e 使 e n 1 假设Bob选择了e 3533 那么用辗转相除法将求得 d e 1 6597 mod11200 于是Bob的解密密钥d 6597 48 Bob在一个目录中公开n 11413和e 3533 假设Alice想发送明文9726给Bob 计算 97263533 mod11413 5761 在一个信道上发送密文5761 当Bob接收到密文5761时 他用他的秘密解密指数 私钥 d 6597进行解密 计算57616597 mod11413 9726 49 RSA的计算复杂问题著名的 平方 和 乘法 方法将计算xc modn 的模乘法的数目缩小到至多为2L 这里的L是指数c的二进制表示比特数 RSA的安全性问题若使RSA安全 p与q必为足够大的素数 使分析者没有办法在多项式时间内将n分解出来 建议选择p和q大约是100位的十进制素数 模n的长度要求至少是512比特 50 密码体系概述古典密码对称密钥密码公开密钥密码数字签名与摘要函数 51 认证 网络系统安全要考虑两个方面 一方面用密码保护传送的信息 使其不被破译 另一方面就是防止对手对系统进行主动攻击 如伪造篡改信息等 认证 authentication 则是防止主动攻击的重要技术 它对于开放的网络中的各种信息系统的安全性有重要作用 手段数字签名 内容摘要 散列函数 52 数字签名 要求 签名必须是依赖于被签名信息的一个位串模板 签名必须使用某些对发送者是唯一的信息 以防止双方的伪造与否认 必须相对容易生成该数字签名 必须相对容易识别和验证该数字签名 伪造该数字签名在计算复杂性意义上具有不可行性 既包括对一个已有的数字签名构造新的消息也包括对一个给定消息伪造一个数字签名在存储器中保存一个数字签名副本是现实可行的 签名模式 直接数字签名和仲裁数字签名 53 散列函数 HashFunction 若对相当长的文件通过签名认证怎么办 如一个合法文件有数兆字节长 自然按160比特分划成一块一块 用相同的密钥独立地签每一个块 然而这样太慢 解决办法引入可公开的密码散列函数 Hashfunction 它将取任意长度的消息 做自变量 结果产生规定长度的消息摘要 然后 签名消息摘要 54 散列函数是否减弱认证方案的安全性 伪造方式一 Oscar以一个有效签名 x y 开始 此处y sigk h x 首先他计算Z h x 并企图找到一个x 满足h x h x 若他做到这一点 则 x y 也将为有效签名 为防止这一点 要求函数h具有无碰撞特性 定义1 弱无碰撞 散列函数h称为是弱无碰撞的 是指对给定消息x X 在计算上几乎找不到异于x的x x X 使h x h x 55 伪造方式二 Oscar首先找到两个消息x x 满足h x h x Oscar把x给Bob 且使他对x的摘要h x 签名 从而得到y 那么 x y 是一个有效的伪造 定义2 强无碰撞 散列函数h被称为是强无碰撞的 是指在计算上几乎不可能找到相异的x x 无限制 x 使得h x h x 56 伪造方式三 在某种签名方案中可伪造一个随机消息摘要Z的签名 若h的逆函数h 1是易求的 可算出h 1 Z x 满足x h Z 则 x y 其中y sigk h x 为合法签名 定义3 单向的 散列函数h为单向的 是指计算h的逆函数h 1在计算上不可行 57 对数字签名来说 散列函数h是这样使用的 消息 x任意长消息摘要 Z h x 160bits签名 y sigk Z 320bits 签名一个消息摘要 验证签名 x y 其中 y sigk h x 使用公开的散列函数h 重构作Z h x 然后 检验Verk Z y 来看Z Z 58 生日攻击 摘要的长度是否随意呢 任找23人从中总能选出两人具有相同生日的概率至少为1 2 假设h X Z是一个散列函数 X和Z是有限的 且 X 2 Z 记 X m和 Z n 易见 至少有n个碰撞 那么 如何找到它们 这个过程类似于随机抛k个球进入n个箱子 然后 检查一下是否有一些箱子包含了至少两个球 这k个球对应于k个随机值xi 且n个箱子对应于Z中n个元素 59 若要分析这k个随机元素z1 z2 zk Z两两不同 无碰撞时 的可能性则对应于一个初始问题 无碰撞的概率 考虑一下有序z1 z2 zk中的zi的选择可能第一个选择z1是随机的 无碰撞的概率100 z2 z1的概率为1 1 n z3不同于z1和z2的概率为1 2 n 以此类推 则无碰撞的概率 随机抛k个球进入n个箱子 没有箱子被抛进两个以上的球的概率 60 若设E 可解出k的关于n和E的函数 如下 61 结论 若略去 k项 有k n ln 1 1 E 2 0 5 若取E 0 5 我们估计k 1 17n0 5 n0 5 说明在集合X中 n0 5个随机元素散列的结果产生一个碰撞的概率为50 所谓生日攻击就是 如果X为一些人的集合 Y是一个非闰年的365天集合 h x 表示x的生日 x X 在上述估计式中取n 365 得k 22 3即随机的23人中至少有一个重复生日的概率至少为50 生日攻击给出消息尺寸的下界 一个40bit的消息摘要将是不安全的 因为k 1 17 240 0 5 也就是220 大约100万 即在100万个随机散列值中将找到一个碰撞的概率为1 2 通常建议消息摘要的尺寸为128bits 62 MD4散列算法 或称信息摘要算法 Rivest RSA公司首度科学家 MIT博士 1990年提出MD4 1991年提出增强版MD5 1992年提出SHA公布于1992年1月31日的联帮记录上 并于1993年5月11日采纳作为标准 63 MD4 给定一个消息比特串x 使用如下算法来构造M 设d 447 x mod512 l表示 x mod