《网络安全加密技术》PPT课件.ppt

9 1对称加密体制 DES 教材5 3密码学基本原理6 3加密技术p134DES简介第一个也是最重要的现代对称加密算法 1977 1美国国家标准局 非国家安全级保密数据 用于银行保护资金转帐安全 5年 3 5使用期分组密码每一分组称为一个消息M C 0 1 64K 0 1 56 9 1 1数据加密标准 DES DES算法总描述 对输入分组进行固定的初始置换IP将下面的运算迭代16轮Li Ri 1Ri Li 1 f Ri 1 Ki 16轮迭代结果输入到IP的逆置换 ki 9 1 1数据加密标准DES DES 2 核心 16轮迭代 一轮迭代过程如下图 9 1 1数据加密标准 DES DES的核心 消息的随机非线性分布第i轮 f Ri 1 Ki 做下面两个子运算Ri 1 32b 扩展置换运算 48b 异或ki 56b 收缩置换运算 48b 8个代换盒 S盒 S盒非线性置换函数8个S盒 8 6b 8 4b 6b地址 16b 行2345b 列 S盒该位置数字数字4b 例第一组011011对应 S盒S1第一行13列的数字S盒4行 16列每行是0 15的一个排列S盒的非线性对DES的安全非常重要 9 1 1数据加密标准DES F函数 1 扩展运算E P28E表 标出比特位的读出顺序 其中16位被读了两次 32 48 F函数 2 与子密钥 Ki48位 的异或运算F函数 3 选择压缩运算 S P298个S盒 4 16 48位被分成8组 每组6位 每组对应一个S盒 1 6位确定在S盒中的行数 2 3 4 5确定列数 根据行列位置在S盒中选取给该位置对应的数字 0 15 得到4位的二元组 例子F函数 4 置换表P E盒扩展运算 S1 S2 S8盒选择函数 S盒运算举例 假设ri 1经过扩展运算 并与Ki异或得到48位二进制数 分为八组 011011110110111000010010000011010101110011110110输入8个S盒 第一组011011对应S盒S11 6位组成二进制数 01 1确定在S1中行数12345位1101 13确定列数13在S1盒1行13列的数字是5 换为二进制4位 0101 注意 所有S盒中的数字都小于等于15 相当于4位二进制数 15 1111 实现6位 位置 行列 向4位内容的转换 9 1 2DES的核心 S盒的非线性对DES的安全非常重要代换密码是非线性的 移位密码仿射密码线性线性密码减小密钥空间 对差分分析的脆弱例差分分析攻击仿射密码DES的安全性密钥长度较短 穷举 强力 测试利用已知明文和密文消息对解决方法 不同密钥加密 解密 加密三重DES方案DES的短密钥弱点90年代变明显 1998 7 15250 000 构造DES解密高手 56个小时成功找到密码 9 2公钥密码体制 公钥密码体制是密码史上一次革命 编码系统基于数学中的单向陷门函数采用了两个不同的密钥 对在公开网络上进行保密通信 密钥分配 数字签名和认证有深远影响 内容公钥密码体制的基本原理RSA算法重点 9 2 1公钥密码体制基本原理 对称密码体制的一个缺点 双双如何建立会密钥话 密钥分配成本高 尤其是对公开网络的电子商务安全应用 1976年 Diffie和Hellman提出 密码学利用NP复杂性理论 陷门单向函数单向函数 一个函数f对定义域上任意一个x f x 容易计算 但对f值域上的任意y f 1 y 都在计算上不可行 陷门单向函数 单向函数f x 如果进一步给定某些辅助信息 如解密密钥 计算f 1 y 又变得容易 9 2 1公钥密码体制基本原理 可信单向函数举例 假设n是两个大素数p和q的乘积 分解n是一个非常困难的问题 NP 完全问题 设b是一个正整数 定义函数f Zn Zn f x xbmodn f是一个单向函数 但知道n的因子是p或q时 计算f 1是容易 因而f是陷门单向函数 秘密的陷门被嵌在单向函数求逆问题中 这个陷门信息就是私人密钥 9 2 2RSA算法 1978年 RivestShamir和Adleman三人最早实现Diffie和Hellman的想法 RSA算法安全 利用陷门单向函数的一种可逆模指数运算 安全性基于大整数分解因子的困难性 9 2 2RSA算法 描述 建立RSA密码体制的过程选择两个大素数p q计算乘积n pq和 n p 1 q 1 选择大于1小于 n 的随机数e 使得gcd e n 1计算d使得de 1mod n 对每一个密钥k n p q d e 定义加密变换为 Ek x xemodn 解密变换为 Dk x ydmodn 这里x y Zn 以 e n 为公开密钥 p q d 为私有密钥 陷门 9 2 2RSA算法 描述 如上建立一个明文空间P和密文空间C为P C Zn 密钥空间为K n p q d e n pq p和q是大素数 1 e d n de 1mod n 的RSA密码体制 9 2 2RSA算法 正确性 RSA算法基础 解密正确性证明 欧拉定理 对任意的e Zn 有e n 1modn 其中Zn x Zn gcd n x 1 函数 是欧拉函数 由于选择的ed 1mod n 所以ed k n 1Cd Med Mk n 1 M n k M Mmodn注 9 2 2RSA算法 实例 RSA算法实例 P 7 q 17 N pq 7 17 119 n p 1 q 1 7 1 17 1 96 选择随机整数5 n 且与96互素 求出d de 1mod96 得到d 77 因为77 5 96 4 1 输入明文M 19 计算C Me 195 66mod119接收密文C 66 解密计算M Cd 6677 19mod119实际计算中p q n e d要大得多 9 2 2RSA算法中的计算技巧 加密和解密运算 模运算性质 基础 ab modn amodn bmodn modn标准的RSA要求pq是128以上 e d也接近这样的数量级 计算Me e化成二进制形式bkbk 1 b0 e bi 02iMe M bi 02i Mbk 2Mbk 1 2 2Mb2 2Mb1 2Mb0 例6677mod11977 1 26 0 25 1 23 1 22 1 20 1 2 0 2 2 16677 661 2 660 2 2 661mod119 9 2 2RSA算法中的计算技巧 构造Memodn的算法d 1Fori kdownto0do d d2modn ifbi 1thend d m modn returnd Me M bi 02i Mbk 2Mbk 1 2 2Mb2 2Mb1 2Mb0 9 2 2RSA算法中的计算技巧 求逆 从e计算d 其中gcd n e 1 求d e 1mod n 计算emod n 的逆元方法 推广的欧几里德算法 注xe y n 1mod n 扩展欧几里德算法不但能计算 a b 的最大公约数 而且能计算a模b及b模a的乘法逆元 intgcd inta intb int if 0 a 有一个数为0 就不存在乘法逆元 x1 1 x2 0 x3 a y1 0 y2 1 y3 b intk for t3 x3 y3 t3 0 t3 x3 y3 k x3 y3 t2 x2 k y2 t1 x1 k y1 x1 y1 x1 y2 x2x3 y3 y1 t1 y2 t2 y3 t3 if y3 1 有乘法逆元ar y2 br x1 return1 else 公约数不为1 无乘法逆元ar 0 br 0 returny3 算法2 Functioneuclid a b longint varx y longint longint Vart longint Beginifb 0thenbegineuclid a x 1 y 0 endElsebegineuclid euclid b amodb x y t x x y y t adivb y end End 例子 157 1mod2668 175 1mod96 19 19 96 77 9 2 3RSA算法的安全性 安全 采用大的密钥 e d的比特数越大越好 但加解密速度慢 二者之间折中 对RSA算法的攻击难度相当于对模数n进行乘积因子分解 目前密钥长度界于1024 2048比特之间 RSA算法是安全的 RSA限制条件 素数pq的长度不能相差太大 p 1 q 1都应该有大的素数因子 gcd p 1 q 1 应该偏小 9 2 4RSA试验 试验目的 掌握有关RSA密码体制编程计算方法掌握使用特定的平台Vb VC Turboc对算法正确编程调试正确运行 实验报告分析编程的约束条件 实验过程及算法1小程序过程 试除法判断大奇数p是否素数循环判断p是否能被一个小于p 的数 2 奇数 整除 如果被整除 p不是素数 否则循环数 1 回到循环开头都不能整除 p是素数2 输入给出大素数p1 p2 e 判断e是否合法 计算d根据1 判断输入的p1 p2是否素数计算n p1 p2 vn p1 1 p2 1 判断e vn是否互素 最大公约数为1 计算dde 1modvn 实验思考问题 实验要求在实验结论分析中回答下列问题 在vb中 程序正确运行的p1 p2的最大值 在实际RSA应用中 p1 p2的取值范围是多少 微机系统可以计算吗 e vn为什么必须互素 举一个反例说明原因 本实验中E取值较小时的好处是什么 结合RSA体制中e的取值说明其缺点 实验报告附件中包括程序源代码 RSA实验运行结果图 VB 9 2 4椭圆曲线密码 ECC 体制 ElGamal密码体制能够在任何离散对数难处理的有限群中实现 我们已经使用了乘法群Zp 其他群 如椭圆曲线群也是合适的侯选者 椭圆曲线在代数学和几何学上已广泛研究了150多年 有丰富深厚的理论积累 ECC 1985年由Koblitz和Miller提出 不如RSA受到重视 但可能是一个潜在重要发展方向