密码学基础.ppt

信息安全InformationSecurity 武汉大学计算机学院武汉大学信息安全研究所 傅建明博士 Jmfu whu 密码学基础知识 密码学概述传统的密码学对称密码公钥密码序列密码 密码学概述 通信保密 COMSEC 60 70年代信息保密计算机安全 COMPUSEC 60年代机密性 访问控制 认证 TCSEC标准信息安全 INFOSEC 80 90年代机密性 完整性 可用性 不可否认性等信息保障 IA 90年代 至今 信息安全发展的四个阶段 年代 通信安全发展时期 从有人类以来 60年代中期 计算机安全发展时期 80年代中期 信息安全发展时期 90年代中期 信息安全保障发展时期 安全保障能力 基本的通讯模型通信的保密模型通信安全 60年代 COMSEC 发方 收方 信源编码信道编码信道传输通信协议 发方 收方 敌人 信源编码信道编码信道传输通信协议密码 信息安全的三个基本方面保密性Confidentiality即保证信息为授权者享用而不泄漏给未经授权者 完整性Integrity数据完整性 未被未授权篡改或者损坏系统完整性 系统未被非授权操纵 按既定的功能运行可用性Availability即保证信息和信息系统随时为授权者提供服务 而不要出现非授权者滥用却对授权者拒绝服务的情况 信息安全的含义 80 90年代 信息安全的其他方面信息的不可否认性Non repudiation 要求无论发送方还是接收方都不能抵赖所进行的传输鉴别Authentication鉴别就是确认实体是它所声明的 适用于用户 进程 系统 信息等审计Accountability确保实体的活动可被跟踪可靠性Reliability特定行为和结果的一致性 安全需求的多样性 保密性一致性可用性可靠性可认证 真实性 责任定位 审计性高性能实用性占有权 如何保证这些需求 美国人提出的概念 InformationAssurance保护 Protect 检测 Detect 反应 React 恢复 Restore 保护Protect 检测Detect 反应React 恢复Restore 信息保障 电子邮件 自动提款机电话卡 IP卡 201电话卡银行取钱信用卡购物 密码 密码从军事走向生活 密码学 Cryptology 是研究信息系统安全保密的科学 密码编码学 Cryptography 主要研究对信息进行编码 实现对信息的隐蔽 密码分析学 Cryptanalytics 主要研究加密消息的破译或消息的伪造 基本概念 量子密码 单量子不可复制定理 DNA密码化学密码 密码新技术 消息被称为明文 Plaintext 用某种方法伪装消息以隐藏它的内容的过程称为加密 Encrtption 被加密的消息称为密文 Ciphertext 而把密文转变为明文的过程称为解密 Decryption 对明文进行加密操作的人员称作加密员或密码员 Cryptographer 密码算法 CryptographyAlgorithm 是用于加密和解密的数学函数 密码员对明文进行加密操作时所采用的一组规则称作加密算法 EncryptionAlgorithm 所传送消息的预定对象称为接收者 Receiver 接收者对密文解密所采用的一组规则称为解密算法 DecryptionAlgorithm 加解密过程示意图加密和解密算法的操作通常都是在一组密钥的控制下进行的 分别称为加密密钥 EncryptionKey 和解密密钥 DecryptionKey 密码学的目的 Alice和Bob两个人在不安全的信道上进行通信 而破译者Oscar不能理解他们通信的内容 加密通信的模型 Alice 加密机 解密机 Bob 安全信道 密钥源 Oscar x y x k 密码体制 它是一个五元组 P C K E D 满足条件 1 P是可能明文的有限集 明文空间 2 C是可能密文的有限集 密文空间 3 K是一切可能密钥构成的有限集 密钥空间 4 任意k K 有一个加密算法和相应的解密算法 使得和分别为加密解密函数 满足dk ek x x 这里x P 密码体制 系统 按照保密的内容分 受限制的 restricted 算法 算法的保密性基于保持算法的秘密 基于密钥 key based 的算法 算法的保密性基于对密钥的保密 现代密码理论 密码算法分类 i 基于密钥的算法 按照密钥的特点分类 对称密码算法 symmetriccipher 又称传统密码算法 conventionalcipher 就是加密密钥和解密密钥相同 或实质上等同 即从一个易于推出另一个 又称秘密密钥算法或单密钥算法 非对称密钥算法 asymmetriccipher 加密密钥和解密密钥不相同 从一个很难推出另一个 又称公开密钥算法 public keycipher 公开密钥算法用一个密钥进行加密 而用另一个进行解密 其中的加密密钥可以公开 又称公开密钥 publickey 简称公钥 解密密钥必须保密 又称私人密钥 privatekey 私钥 简称私钥 密码算法分类 ii 按照明文的处理方法 分组密码 blockcipher 将明文分成固定长度的组 用同一密钥和算法对每一块加密 输出也是固定长度的密文 流密码 streamcipher 又称序列密码 序列密码每次加密一位或一字节的明文 也可以称为流密码 序列密码是手工和机械密码时代的主流 密码算法分类 iii 对称密钥密码又可分为 分组密码每次对一块数据加密多数网络加密应用DES IDEA RC6 Rijndael流密码每次对一位或一字节加密手机One timepadding Vigen re Vernam 密码算法分类 iv 公开密钥密码 大部分是分组密码 只有概率密码体制属于流密码每次对一块数据加密数字签名 身份认证RSA ECC ElGamal加密解密速度慢 密码算法分类 v 三个阶段 1949年之前密码学是一门艺术1949 1975年密码学成为科学1976年以后密码学的新方向 公钥密码学 密码学的起源和发展 i 密码学的起源 隐写术 steganography 通过隐藏消息的存在来保护消息 隐形墨水字符格式的变化图象图像 象形文字的修改 ModifiedHieroglyphics c 1900B C 密码学的第一个例子是对标准书写符号的修改 example i 我去君留十载中爱无南北与西东万株松树青山上洁白孤高生不同 example ii SpartanScytale c 500B C 斯巴达人用于加解密的一种军事设备发送者把一条羊皮螺旋形地缠在一个圆柱形棒上思想 置换 permutation Polybius Checkerboard 205 123B C 明文 POLYBIUS密文 3534315412244543 example iii CaesarCipher c 50B C ABCDEFG XYZDEFGHIJ ABC明文 Caesarcipherisashiftsubstitution密文 FDHVDUFLSKHULVDVKLIWVXEVWLWXWLRQ example iV Nomenclator代码本c 1400字母 符号 单词 短语代码代码字母 符号 单词 短语应用 WorldWarII Example V Example Con t 网格加密法 中国例 密文 王先生 来信收悉 你的盛情难以报答 我已在昨天抵达广州 秋雨连绵 每天需备伞一把 大约本月中旬即可返回 再谈 弟 李明2001年11月7日 网格加密法 中国例 密文 王先生 来信收悉 你的盛情难以报答 我已在昨天抵达广州 秋雨连绵 每天需备伞一把 大约本月中旬即可返回 再谈 弟 李明2001年11月7日 明文 情报在雨伞把中 兽栏法 明文 System密文 密文字母表 古典实例 双轨密码 1861 1865年例 明文 DiscreteandSystem密文 DsrtadytmIceensse加密方法 Dsrtadytmiceensse Beale密码 C 115732481837524917316265722715 M Ihavedeposited 1 When inthecourseofhumanevents itbecomesnecessary 11 Foronepeopletodissolvethepoliticalbandswhichhave 21 Connectedthemwithanother andtoassumeamongthePowers 31 Oftheearththeseparateandequalstationtowhich 41 TheLawsofNatureandofNature sGodentitlethem 51 Adecentrespecttotheopinionsofmankindrequiresthat 61 Theyshoulddeclarethecauseswhichimpelthemtothe 71 separation Weholdthesetruthstobeself evident that 81 Allmenarecreatedequal thattheyareendowedby 91 TheirCreatorwithcertainunalienablerights thatamong 99 TheseareLife Liberty andthepursuitofHappiness 古典密码 古典密码 6 Vigen re密码是一种基于移位字母表的周期代替密码 它的密钥K由一个字母序列来指定 k k1 kd 其中 ki i 1 d 给出了第i个字母表的移动位数 即fi a a ki modn 例如 明文INTELLIGENT用密钥PLAY加密为 M INTELLIGENTK PLAYPLAYPLAEk M XYTCAMIETYT 例设m 6 且密钥字是CIPHER 这相应于密钥 假定明文串是thiscryptosystemisnotsecure首先将明文串转化为数字串 按6个一组分段 然后模26 加 上密钥字得 使用Vigen re表可以方便地进行加密和解密 相应的密文串将是 VPXZGIAXIVWPUBTTMJPWIZITWZT解密过程与加密过程类似 不同的只是进行模26减 而不是模26加 古典密码 7 通过一次加密一组字母来使密码分析更加困难 Playfair密码 Playfair密码是一个双字母组代替密码 用英国科学家LyonPlayfair的名字命名 Playfair密码的密钥是由一个25个字母 J视为I 的5 5矩阵给出 HARPSICODBEFGKLMNQTUVWXYZ 加密规则 对于矩阵中的每一对明文字母m1m2按如下规则加密 m1m2对应的密文为c1c2 若m1和m2在同一行 则c1和c2分别是m1和m2右边的字母 其中第一列认为是第五列的右边 若m1和m2在同一列 则c1和c2分别是m1和m2右边的字母 其中第一行认为是最后一行的下边 若m1和m2在不同的列 则c1和c2是以m1和m2为顶点的矩形的另两个顶点 其中c1和m1在一行 c2和m2在一行 若m1 m2 则在m1和m2之间插入一个无效字符 例如X 后重新分组 若明文有奇数个字符 则在末尾加上一个无效字符 Example Con t 古玩店的商品价格 5321 00EPMO最简单的密码 DNESPLEH倒过来 HELPSEND第一次世界大战期间 德国使用字典编写密码25 3 17电视剧 誓言无声爱情誓言 584 1314 880 1949年之前 古典密码 classicalcryptography 密码学还不是科学 而是艺术出现一些密码算法和加密设备密码算法的基本手段 substitution permutation 出现 针对的是字符简单的密码分析手段出现 密码学的起源和发展 ii 1949 1975年 计算机使得基于复杂计算的密码成为可能1949年Shannon的 TheCommunicationTheoryofSecretSystems 1967年DavidKahn的 TheCodebreakers 1971 73年IBMWatson实验室的HorstFeistel等的几篇技术报告 Smith J L TheDesignofLucifer ACryptographicDeviceforDataCommunication 1971 Smith J L AnExprementalApplicationofCryptogrphytoaremotelyAccessedDataSystem Aug 1972 Feistel H CryptographyandComputerPrivacy May1973数据的安全基于密钥而不是算法的保密 密码学的起源和发展 iii 1976年以后 1976年Diffie Hellman的 NewDirectionsinCryptography 提出了不对称密钥密码1977年Rivest Shamir Adleman提出了RSA公钥算法90年代逐步出现椭圆曲线等其他公钥算法公钥密码使得发送端和接收端无密钥传输的保密通信成为可能 密码学的起源和发展 iv 1976年以后 对称密钥密码算法进一步发展1977年DES正式成为标准80年代出现 过渡性 的 postDES 算法 如IDEA RCx CAST等90年代对称密钥密码进一步成熟Rijndael RC6 MARS Twofish Serpent等出现2001年Rijndael成为DES的替代者 密码学的起源和发展 v 假设破译者Oscar是在已知密码体制的前提下来破译Bob使用的密钥 这个假设称为Kerckhoff原则 最常见的破解类型如下 1 唯密文攻击 Oscar具有密文串y 2 已知明文攻击 Oscar具有明文串x和相应的密文y 3 选择明文攻击 Oscar可获得对加密机的暂时访问 因此他能选择明文串x并构造出相应的密文串y 4 选择密文攻击 Oscar可暂时接近密码机 可选择密文串y 并构造出相应的明文x 这一切的目的在于破译出密钥或密文 密码分析 密码破译的原则 遵循观察与经验方法 采用归纳与演绎步骤 分析 假设 推测和证实三大要素 语言的频率特征 e连接特征 q u Iex 重复特征 th tion tious 密码破译 无条件安全 Unconditionallysecure 无论破译者有多少密文 他也无法解出对应的明文 即使他解出了 他也无法验证结果的正确性 Onetimepad计算上安全 Computationallysecure 破译的代价超出信息本身的价值破译的时间超出了信息的有效期 攻击方法的复杂性 1 数据复杂性 2 处理复杂性 3 存储复杂性 算法的实现 密码模式密码协议 密码学数学基础 熵 事件出现的平均不确定性 一个事件平均所需的信息量中国剩余定理 孙子算经 熵 例 X可能在下周某天去钓鱼 E 星期一 星期二 星期三 星期四 星期五 星期六 星期日 H X 例 任意给定一个1 20的数 猜多少次可以猜到该数 熵 例 甲任意取一个不超过10的整数 由乙来猜 但允许乙提K个问题 甲只回答 是 或者 非 问K多大时可以确定猜到该数 解 若令猜想作为事件V V可能有10种结果 假定这10种结果是等概率的 V的熵为 H V log210 3 32令事件Ak U1U2U3 Uk为提问k个问题 但Ui的熵不超过log22 1 因为只有 是 或者 非 故Ak的熵为不超过k比特 则 log210 k log22 k k 3 32故k 4 熵 例 有25个外表完全相同的硬币 其中24个重量完全一样 有一个较轻的伪币 用无砝码的天平 试问要做多少次的比较 可以找到这枚伪币 解 事件V为找出伪币 可能有25个结论 他们是等概率 故 H V log225 事件U为天平称的结果 可能有3种情况 1 左右平衡 2 左边重 3 右边重 故 H U log23令Ak U1U2U3 Uk为连续用k次天平的事件 k log23 log225k log225 log23 2 93故k最少为3次 熵 问题修改为 如果25个硬币中有一枚假币 用无砝码的天平 试问要做多少次的比较 可以找到这枚假币 且是轻还是重 中国剩余定理 定理 如果n的素数因子分解式为p1 p2 pt 则一组方程 xmodpi ai 其中i 1 2 t 有唯一解x 其中x小于n 其中某些pi可能相等 例 今有物不知其数 三三数之剩二 五五数之剩三 七七数之剩二 问物几何 xmod3 25 7 2 70mod3 1xmod5 33 7 3 63mod5 3xmod7 23 5 2 30mod7 2 中国剩余定理 定理 令d1 d2 dt为两两互素 并令n d1d2 dt 则xmoddi xi i 1 t 在 0 n 1 范围内有公共解x x modn其中 mi n di yi mi 1moddi 数据加密标准算法DES 背景DES是20年来全世界通用的标准算法 20世纪70年代初期 非军事性的密码处于一种无序状态 1972年 美国国家标准局NBS开始一项保护计算机和通信数据的项目 其中一部分是要开发一个单独的标准保密算法 1973年5月15日 NBS公开征集标准加密算法 并公布了设计要求 未果 1974年8月 NBS第二次征集算法 收到一份可选方案 基于IBM在20世纪70年代初开发的LUCIFER算法的算法 1976年 NBS指派两个工作组来评价该标准 DES在1976年11月23日被宣布为联邦标准 允许在非保密的政府通信中使用 标准的官方描述在1977年1月15日颁布 6个月后生效 1984年9美国总统签署145号国家安全决策令 NSDD 命令NSA着手发展新的加密标准 用于政府系统非机密数据和私人企事业单位 NSA宣布每隔5年重新审议DES是否继续作为联邦标准 1988年 FIPS46 1 1993年 FIPS46 2 1998年不再重新批准DES为联邦标准 NBS公开征集标准加密算法的要求 算法必须提供高度的安全性算法必须有详细的说明 并易于理解算法的安全性必须取决于密钥 不依赖于算法本身的保密算法必须必须对所有用户都适用算法必须适用于各种应用算法必须能用电子设备经济地实现算法必须使用效率高算法必须能被证实有效算法必须是可移植的 DES加密算法 高级数据加密标准AES 背景AES加密算法描述算法评价 背景 现代计算机速度的迅速提高 使得只有56bit密钥的DES算法的安全性面临着极大的挑战 1997年 NIST公开征求AES AdvancedEncryptionStandard 作为2001年以后的数据加密标准 1998年8月 AES召开第一次候选会 确定15个算法入围 1999年3月 AES召开第二次候选会 有5个算法入围 MARS RC6 Rijndael Serpent和Twofish 2000年10月 NIST选出由比利时的JoanDaemen和VincentRijmen提交的Rijndael算法作为AES 2001年夏天 NIST颁布新的信息处理标准 FIPS 将Rijndael算法作为AES 加密算法概述 AES算法与以往的基于Feistel网的密码 如DES 不同 算法的每一步都是可逆的 算法的明文块长可以为128bit 192bit或256bit 密钥也可以分别为128bit 192bit或256bit 算法有多圈相同的运算 每一圈包括4个步骤 非线性代替 S 盒 行循环左移 ShiftRow 列混合变换 MixColum 与扩展密钥相异或每一圈的子密钥从扩展密钥中取出密钥扩展过程同时应用了非线性变换和循环左移算法定义的所有运算都是在有限域GF 28 上进行的 AES的演示 演示 RSA算法 由MIT的Rivest Shamir Adleman在1977提出最著名的且被广泛应用的公钥加密体制明文 密文是0到n 1之间的整数 通常n的大小为1024位二进制或309位十进制数可用于数字签名 RSA算法描述 1 取两个素数p和q 保密 如p 5 q 11 2 计算N pq N公开 N p 1 q 1 保密3 随机选取整数e 满足gcd e N 1 即e与 N 互素 4 计算d 使得ed 1mod N 公钥 e N 私钥 d N RSA算法描述 加密 C MemodN wh