计算机算法ppt课件

1 2016年8月4日QQ 516175070 2 内容提要 1算法概述1 1什么是算法1 2算法有什么用1 3算法的特点1 4算法的时间复杂度2加密算法2 1什么是数据加密2 2单向散列算法2 3对称式加密算法2 4非对称式加密算法2 5加密算法的选择 3 什么是算法 算法是按照一定的方法和步骤解决问题的过程算法是一系列解决问题的清晰指令 能够对一定规范的输入 在有限时间内获得所要求的输出 广义地说 算法就是做某一件事的步骤或程序 菜谱是做菜肴的算法 洗衣机的使用说明书是操作洗衣机的算法通俗理解 算法就是解决一个问题的方法 据此而论 编写程序解决的任何一个问题都可以叫做算法 4 算法有什么用 提高计算机运行的效率 节约内存空间 通俗理解没有好算法 计算机完成一件工作可能需要1年 有好算法 计算机完成同样的一件工作可能只要几秒 5 算法的特点 有穷性确切性算法每一条指令必须有确切的含义 不会产生二义性 并且 在任何情况下 算法只有唯一的一条执行路径 相同的输入只能得到相同的输出 可行性算法中描述的操作都是可以通过已经实现的基本算法执行有限次实现 输入输出 6 算法的时间复杂度 同一个问题往往可以用不同的算法解决 不同的算法可能用不同的时间 空间来完成同一个任务 研究分析算法的目的在于 选择合适的算法解决问题 算法的分析评价主要从时间和空间两个维度来考虑 什么是时间复杂度算法需要消耗的时间资源 时间频度算法执行需要的时间和语句执行次数成正比 算法语句执行次数多 耗费时间越长 一个算法语句的执行次数称为时间频度 记为T n 7 时间复杂度 在时间频度T n 中 n称为问题的规模 当n不断变化时 时间频度T n 也会不断变化 但有时我们想知道它变化时呈现什么规律 为此 我们引入时间复杂度概念 一般情况下 算法中基本操作重复执行的次数是问题的规模n的某个函数 用T n 表示 若有某个辅助函数f n 使得当n趋近于无穷大时 T n f n 的极限值为不等于零的常数 则称f n 是T n 的同数量级函数 记作T n O f n 称O f n 为算法的渐进时间复杂度 简称时间复杂度 在各种不同的算法中 若算法中语句执行次数为一个常数 则时间复杂度为O 1 另外 在时间频度不相同时 时间复杂度有可能相同 如T n n2 3n 4与T n 4n2 2n 1它们的频度不同 但是时间复杂度相同 都为O n2 注意 时间复杂度并不是表示一个程序解决问题需要花多少时间 而是当问题规模扩大后 程序需要的时间长度增长得有多快 8 什么是数据加密 对明文的文件或数据按某种算法进行处理 使其成为不可读的一段代码 通常称为 密文 使其只能在输入相应的密钥 yao 之后才能显示出本来内容 这个过程称为数据加密 用到的算法称为加密算法 9 加密算法的分类 单向散列算法 1 MD5算法 2 SHA算法 3 CRC算法非对称加密算法 1 RSA算法 2 ElGamal算法 3 DSA算法对称加密算法BlowFish算法 10 单向散列算法 单项散列函数算法也称Hash 哈希 算法 是一种将任意长度的消息压缩到某一固定长度的函数 该过程不可逆 Hash函数可用于数字签名 消息的完整性检测 消息起源的认证检测等 常见的散列算法有MD5 SHA N Hash RIPE MD HAVAL 11 单向散列算法 MD5算法原理 概述MD5的全称是Message DigestAlgorithm5 信息 摘要算法 经MD4发展而来 MD5算法的使用不需要支付任何版权费用 功能输入任意长度的信息 经过处理 输出为128位的信息 数字指纹 不同的输入得到的不同的结果 唯一性 根据128位的输出结果不可能反推出输入的信息 不可逆 MD5用途网站用户的密码 用户注册的时候 对用户密码进行MD5加密保存到数据库 当用户登录的时 系统把用户输入的密码计算成MD5值 然后再去和保存在数据库中的MD5值进行比较 进而确定输入的密码是否正确 12 单向散列算法 SHA算法 概述安全哈希算法 SecureHashAlgorithm 是美国国家标准技术研究所发布的国家标准FIPSPUB180 最新的标准已经于2008年更新到FIPSPUB180 3 其中规定了SHA 1 SHA 224 SHA 256 SHA 384 和SHA 512这几种单向散列算法 SHA 1 SHA 224和SHA 256适用于长度不超过2 64二进制位的消息 SHA 384和SHA 512适用于长度不超过2 128二进制位的消息功能输入任意长度的信息 经过处理 输出为160位的信息 数字指纹 不同的输入得到的不同的结果 唯一性 SHA与MD5的比较因为二者均由MD4导出 SHA和MD5彼此很相似对强行攻击的安全性 最显著和最重要的区别是SHA摘要比MD5摘要长32位速度 在相同的硬件上 SHA 1的运行速度比MD5慢 13 单向散列算法 CRC算法 概述CyclicRedundancyCheck循环冗余检验 是基于数据计算一组效验码 用于核对数据传输过程中是否被更改或传输错误 特点检错能力极强开销很小易于实现用途ARJ LHA ZIP等压缩软件采用的是CRC 32 GIF TIFF等图像存储格式 所有链路层或网络接口层协议中 例如HDLC DDCMP等众多领域 14 非对称加密算法 概述非对称加密算法需要两个密钥 公开密钥 publickey 和私有密钥 privatekey 公开密钥与私有密钥是一对 如果用公开密钥对数据进行加密 只有用对应的私有密钥才能解密 如果用私有密钥对数据进行加密 那么只有用对应的公开密钥才能解密 因为加密和解密使用的是两个不同的密钥 所以这种算法叫作非对称加密算法 15 非对称加密算法 RSA算法 概述RSA公钥加密算法是1977年由罗纳德 李维斯特 RonRivest 阿迪 萨莫尔 AdiShamir 和伦纳德 阿德曼 LeonardAdleman 一起提出的 1987年首次公布 当时他们三人都在麻省理工学院工作 RSA就是他们三人姓氏开头字母拼在一起组成的 RSA是目前最有影响力的公钥加密算法 它能够抵抗到目前为止已知的绝大多数密码攻击 已被ISO推荐为公钥数据加密标准 特点安全级别非常高RSA的安全性依赖于大素数的因子分解 求两个大素数的乘积是很容易计算的 但要分解两个大素数的乘积 求出它们的素数因子却是非常困难的 它属于NP完全问题速度慢 为保证安全性 大质数至少也要600bit以上 一般1024二进制位 人类已经分解的最大整数 232个十进制位 768个二进制位 应用银行U盾 16 非对称加密算法 ElGamal算法 概述ElGamal算法既能用于数据加密也能用于数字签名 其安全性依赖于计算有限域上离散对数这一难题 用途a 随机生成密钥对b 在软件中判断注册码 17 非对称加密算法 DSA算法 概述DigitalSignatureAlgorithm DSA 是Schnorr和ElGamal签名算法的变种 被美国NIST作为DSfS DigitalSignatureStandard 特点DSA是基于整数有限域离散对数难题的 其安全性与RSA相比差不多用途DSA一般用于数字签名和认证 18 对称加密算法 概述对称加密 也叫私钥加密 指加密和解密使用相同密钥的加密算法 数据发信方将明文 原始数据 和加密密钥 miyao 一起经过特殊加密算法处理后 使其变成复杂的加密密文发送出去 收信方收到密文后 若想解读原文 则需要使用加密用过的密钥及相同算法的逆算法对密文进行解密 才能使其恢复成可读明文开销很小 特点对称加密算法的特点是算法公开 计算量小 加密速度快 加密效率高使用的密钥只有一个用途a 随机生成密钥对b 在软件中判断注册码 19 对称加密算法 DES算法 概述DES算法为密码体制中的对称密码体制 又被称为美国数据加密标准 是1972年美国IBM公司研制的对称密码体制加密算法特点数据加密标准 速度较快 适用于加密大量数据的场合 20 加密算法的选择 由于对称加密算法的密钥管理是一个复杂的过程 密钥的管理直接决定着他的安