第二章 密码学基础NEWppt课件.ppt

第二章密码学基础 目标要求 基本要求 理解密码系统的模型 理解对称密码体制和非对称密码体制的原理 掌握IDEA算法 ECC等公开密码算法的原理与应用 了解常见的加密方式和各自的特点 目标要求 重点 掌握对称密码体制和非对称密码体制的原理 熟悉IDEA算法 ECC公开密码算法的原理与应用 熟悉各种加密方式和各自的特点 难点 非对称密码体制的原理 本章内容 2 1密码技术概述2 2密码算法2 3对称密钥密码加密模式2 4网络加密方式 2 1密码技术概述 2 1 1密码学历史 1000BC 姜子牙阴阳符 500 600BC 天书 100 44BC Caesarcipher Caesarcipher 移位密码 密文表 abcdefghijklmnopqrstuvwxyz密文表 defghijklmnopqrstuvwxyzabcAnexample 明文 Plaintext Howareyou密文 Ciphertext 1790 转轮密码 ThomasJefferson 二战 GermanEnigmamachine 二战 JapanesePurplemachine 1948 香农 ClaudeShannon与信息论ClaudeShannon与密码学 Born 30April1916inGaylord Michigan USADied 24Feb2001inMedford Massachusetts USA 2 1 2密码系统 加密变换 PlainText CipherText CipherText 解密变换 PlainText 发送者 Alice DecryptionKey EncryptionKey 接受者 Alice CipherText 密码分析 窃密者 Eve 密钥信道 1 密码学基本概念 密码学 Cryptology 研究信息系统安全保密的科学 它包含两个分支 密码编码学 Cryptography 对信息进行编码实现隐蔽信息的一门学问 密码分析学 Cryptanalysis 研究分析破译密码的学问 明文 消息 Plaintext 被隐蔽消息 常用M表示 密文 Ciphertext 或密报 Cryptogram 明文经密码变换成的一种隐蔽形式 常用C表示 加密 Encryption 将明文变换为密文的过程 解密 Decryption 加密的逆过程 即由密文恢复出原明文的过程 加密员或密码员 Cryptographer 对明文进行加密操作的人员 加密算法 Encryptionalgorithm 密码员对明文进行加密时所采用的一组规则 常用E 表示 解密算法 接收者对密文进行解密时所采用的一组规则 常用D 表示 密钥 Key 控制加密和解密算法操作的数据处理 分别称作加密密钥和解密密钥 常用k表示 截收者 Eavesdropper 在信息传输和处理系统中的非受权者 通过搭线窃听 电磁窃听 声音窃听等来窃取机密信息 密码分析 Cryptanalysis 截收者试图通过分析从截获的密文推断出原来的明文或密钥 密码分析员 Cryptanalyst 从事密码分析的人 被动攻击 Passiveattack 对一个保密系统采取截获密文进行分析的攻击 2 密码系统组成 明文空间 信息本来的原始空间 密文空间 明文经过加密后得到难以理解和辨认的信息空间 密钥空间 控制算法的实现 由信息通信双方所掌握的专门信息空间 密码算法 规定了明文和密文之间的一个复杂的函数变换方式 包括加密函数与解密函数 加密过程 EK M C 加密过程 DK C M 密码系统应满足 DK EK M M 密码学的Kerchoff准则 一切秘密寓于密钥之中 1883年荷兰密码学家A Kerchoff 1835 1903 就给出了密码学的一个基本原则 密码的安全必须完全寓于密钥之中 尽管密码学家们大都同意这一看法 但直到制定DES时才首次认真地遵循这一原则 2 1 3密码体制 密码体制 一个密码系统采用的基本工作方式密码体制从原理上可以分为两大类 对称密钥密码体制 或单钥密码体制 非对称密钥密码体制 或双钥密码体制 2 1 3 1对称密钥密码体制 加密 E PlainText CipherText CipherText 解密 D PlainText 发送者 Alice K K 接受者 Alice 密钥信道 密钥生成器 加密过程 EK M C 加密过程 DK C M 对称密钥密码根据对明文加密方式的不同分为 序列密码 StreamCipher 或流密码 分组密码 BlockCipher 或块密码 1 序列密码 对明文的单个位 有时对字节 运算的算法 军事和外交场合使用的主要密码技术 工作原理 明文序列 m m0m1m2 密文序列 c ccc1c2 密钥序列 k k0k1k2 序列密码的加密过程 明文序列 m m0m1m2 密文序列 c ccc1c2 密钥序列 k k0k1k2 序列密码的解密过程 加密过程 ci ki mi mod2 加密过程 mi ki ci mod2 2 分组密码 对明文信息分割成块结构 逐块进行加密和解密 工作原理 首先将明文分成相同长度的数据块 然后分别对每个数据块加密产生一串灭为你数据块 解密时 第每个密文数据块进行解密后得到相应的明文数据块 将所有的明文数据块合并起来即得到明文 明文序列 m m0m1m2 密文序列 c ccc1c2 密钥序列 k k0k1k2 分组密码的加密过程 Ek 明文序列 m m0m1m2 密文序列 c ccc1c2 密钥序列 k k0k1k2 分组密码的加密过程 Dk 1 对称密钥密码体制的问题 2 1 3 2非称密钥密码体制 E NetworkorStorage 明文PlainText 密文CipherText D 原明文OriginalPlainText Bob 私钥SecretKey Alice 私钥SecretKey 密文CipherText 若N个人相互保密通信 每人必须拥有 N 1 个私钥 N很大时 需要保存的私钥很多 如何解决 可信中心分发 共需要发N N 1 2个私钥N 1000时 999 1000 2 499500 双方事先约定 用户之间自己秘密会面 第一次远距离通信如何办 加密 E PlainText CipherText CipherText 解密 D PlainText 发送者 Alice K2 K1 接受者 Alice 1976 由Diffie和Hellman提出 被公认为现代密码学诞生的标志 工作原理 每个用户都有一对选定的密钥 公钥 K1 私钥K2 K1是可以公开的 可以像电话号码一样进行注册公布 K2则是秘密的 特点 1 将加密和解密能力分开 2 多个用户加密的消息只能由一个用户解读 秘密通信 3 一个用户加密的消息而使多个用户可以解读 认证 4 不用事先分配秘钥 2 非对称密钥密码体制 2 1 4密码分析 密码分析 试图获得加密体制细节 解密密钥和明文等机密信息的过程 通常包括 分析统计截获的密文材料 假设 推断和证实等步骤 密码分析方法有传统破译方法和物理破译方法两大类 1 基本概念 传统破译方法包括穷举破译法和数学分析法两类 数学分析法又分为确定性分析法的和统计分析法 四种破译类型 唯密文破译 ciphertextonlyattacks 分析者仅知道有限数量的密文 已知明文破译 knownplaintextattacks 分析者除了拥有有限数量的密文外 还有数量限定的一些已知 明文 密文 对 四种破译类型 续 选择明文破译 chosenplaintextattacks 分析者除了拥有有限数量的密文外 还有机会使用注入了未知密钥的加密机 通过自由选择明文来获取所希望的 明文 密文 对 集合 选择密文破译 chosenciphertextattacks 分析者除了拥有有限数量的密文外 还有机会使用注入了未知密钥的解密机 通过自由选择密文来获取所希望的 密文 明文 对 集合 2 防止密码破译的措施 为防止密码被破译 可以采取以下措施 强壮的加密算法 动态会话密钥 保护关键密钥 2 2密码算法 1 IDEA的历史 1990年 瑞士的来学嘉 XuejiaLai 和JamesMassey于1990年公布了IDEA密码算法第一版 称为PES ProposedEncryptionStandard 1991年 为抗击差分密码攻击 他们增强了算法的强度 称IPES ImprovedPES 1992年 改名为IDEA InternationalDataEncryptionAlgorithm 2 2 1IDEA算法 2 IDEA加密过程 IDEA是一个分组长度为64bit的分组密码算法 密钥长度为128bit 抗强力攻击能力比DES强 同一算法既可加密也可解密 IDEA的 混淆 和 扩散 设计原则来自三种运算 它们易于软 硬件实现 加密速度快 在IDEA的模乘运算中 为什么将模数取为216 1 而不是216 2 在其模加运算中 为什么模数取为216而不是216 1 IDEA加密的总体方案图 IDEA加密的单个循环图 IDEA的密钥生成 56个16bit的子密钥从128bit的密钥中生成前8个子密钥直接从密钥中取出 对密钥进行25bit的循环左移 接下来的密钥就从中取出 重复进行直到52个子密钥都产生出来 3 IDEA的解密 加密解密实质相同 但使用不同的密钥 解密密钥以如下方法从加密子密钥中导出 解密循环I的头4个子密钥从加密循环10 I的头4个子密钥中导出 解密密钥第1 4个子密钥对应于1 4加密子密钥的乘法逆元 2 3对应2 3的加法逆元 对前8个循环来说 循环I的最后两个子密钥等于加密循环9 I的最后两个子密钥 使用子分组 16bit的子分组 使用简单操作 易于加法 移位等操作实现 加密解密过程类似 规则的结构 便于VLSI实现 4 实现上的考虑 5 IDEA的安全性 IDEA能抗差分分析和相关分析 IDEA似乎没有DES意义下的弱密钥 IDEA是PGP的一部分 BruceSchneier认为IDEA是DES的最好替代 但问题是IDEA太新 许多问题没解决 2 2 2ECC公钥密码 1 简要历史 椭圆曲线 Ellipticcurve 作为代数几何中的重要问题已有100多年的研究历史 1985年 N Koblitz和V Miller独立将其引入密码学中 成为构造公钥密码体制的一个有力工具 利用有限域GF 2n 上的椭圆曲线上点集所构成的群上定义的离散对数系统 可以构造出基于有限域上离散对数的一些公钥体制 椭圆曲线离散对数密码体制 ECDLC 如Diffie Hellman ElGamal Schnorr DSA等 实数上的椭圆曲线 其中的是满足简单条件的实数一些曲线上的点连同无穷远点O的集合 实数上的椭圆曲线例子 2 运算定义 有限域上的椭圆曲线 模P椭圆群记为群中的元素 x y 是满足以上方程的小于P的非负整数另外加上无穷远点O计算 的加法规则 ECC的加解密 ECC加解密例子 ECC特别适用 无线Modem的实现 对分组交换数据网提供加密 在移动通信器件上运行4MHz的68330CPU ECC可实现快速Diffie Hellman密钥交换 并极小化密钥交换占用的带宽 将计算时间从大于60秒降到2秒以下 Web服务器的实现 在Web服务器上集中进行密码计算会形成瓶颈 Web服务器上的带宽有限使带宽费用高 采用ECC可节省计算时间和带宽 且通过算法的协商较易于处理兼容性 集成电路卡的实现 ECC无需协处理器就可以在标准卡上实现快速 安全的数字签名 这是RSA体制难以做到 ECC可使程序代码 密钥 证书的存储空间极小化 数据帧最短 便于实现 大大降低了IC卡的成本 Menezes Okamoto和Vanstone指出应避免选用超奇异曲线 否则椭圆曲线群上的离散对数问题退化为有限域低次扩域上的离散对数问题 从而能在多项式时间上可解 他们还指出 若所用循环子群的阶数达2160 则可提供足够的安全性 3 ECC的安全性 ECC和RSA对比 在实现相同的安全性下 ECC所需的密钥量比RSA少得多 如下表所示 其中MIPS年表示用每秒完成100万条指令的计算机所需工作的年数 m表示ECC的密钥由2m点构成 以40MHz的钟频实现155bits的ECC 每秒可完成40 000次椭园曲线运算 其速度比1024bits的DSA和RSA快10倍 ECC的密钥长度mRSA的密钥长度MIPS 年1601024101232051201036600210001078120012000010168 2 3 1分组密码的工作模式 2 3网络加密方法 分组密码可以按不同的模式工作 实际应用的环境不同应采用不同的工作模式 电码本 ECB 模式 密码分组链接 CBC 模式 密码反馈 CFB 模式 输出反馈 OFB 模式 计数器 CTR 模式 2 3 2电码本 ECB 模式 最简单的运行模式 一次对一个64bit长的明文分组加密 且每次加密密钥都相同 在用于短数据 如加密密钥 时非常理想 是安全传递DES密钥的最合适的模式 在给定的密钥下同一明文组总产生同样的密文组 这会暴露明文数据的格式和统计特征 明文数据都有固定的格式 需要以协议的形式定义 重要的数据常常在同一位置上出现 使密码分析者可以对其进行统计分析 重传和代换攻击 2 3 3密码分组链接 CBC 模式 一次对一个明文分组加密 每次加密使用同一密钥 加密算法的输入是当前明文分组和前一次密文分组的异或 在产生第1个密文分组时 需要有一个初始向量IV与第一个明文分组异或 解密时 每一个密文分组被解密后 再与前一个密文分组异或 第一个密文分组解密后和初始向量IV异或恢复出第一个明文分组 为使安全性最高 IV应像密钥一样被保护 可使用ECB加密模式来发送IV 保护IV原因是 如果敌手能欺骗接受方使用不同的IV 敌手就能够在明文的第一个分组中插入自己选择的比特值 IV的完整性要比其保密性更为重要 在CBC模式下 最好是每发一个消息 都改变IV 比如将其值加一 由于CBC模式的链接机制 该模式对于加密长于64bit的消息非常合适 CBC模式除能获得保密性外 还能用于认证 2 3 4密码反馈 CFB 模式 加密算法的输入是64bit移位寄存器 其初始值为某个初始向量IV 加密算法输出的最左 最高有效位 jbit与明文的第一个单元进行异或 产生第一个密文单元并传送该单元 然后将移位寄存器的内容左移j位并将送入移位寄存器最右边 最低有效位 j位 这一过程持续到明文的所有单元都被加密为止 解密时 将收到的密文单元与加密函数的输出进行异或 为什么此时仍然使用加密算法而不是解密算法 利用CFB模式或者OFB模式可将DES转换为流密码 流密码不需要对消息进行填充 而且运行是实时的 因此如果传送字母流 可使用流密码对每个字母直接加密进行传送 CFB模式除了获得保密性外 还能用于认证 2 3 5输出反馈 OFB 模式 OFB模式的结构类似于CFB 不同