密码学基础.doc

I 目 录 第一章 密码学基础 1 1 1 密码学的基本概念和专业术语 1 1 1 1 发送者和接收者 1 1 1 2 消息和加密 1 1 1 3 算法和密钥 1 1 1 4 密码分析 2 1 2 密码学的历史 3 第二章 古典密码学 4 2 1 代替密码 4 2 1 1 单表替代密码 4 2 1 2 多表替代密码 4 2 2 置换密码 5 第三章 密码技术 6 3 1 密钥长度 6 3 1 1 对称密钥长度 6 3 1 2 公开密钥长度 7 3 2 密钥管理 8 3 2 1 密钥产生的流程 8 3 2 2 公开密钥的密钥管理 9 3 3 密钥管理技术 9 3 3 1 密钥管理技术的分类 9 3 3 2 数字签名 10 第四章 公开密钥算法 11 4 1 简介 11 4 2 背包算法 11 4 2 1 加法背包 11 4 2 2 乘法背包 12 4 3 RSA 算法 12 4 3 1 RSA 算法的描述 12 4 3 2 RSA 的安全性 13 第五章 总结 14 参考文献 15 II 图表目录 图 1 1 加密与解密 1 表 3 1 穷举攻击的运算量 6 表 3 2 使用通用术语筛选法和特殊数域筛法分解因数时间 7 表 3 3 Bruce Schneier 公开密钥长度建议值 7 表 3 4 Ron Rivest 密钥长度建议值 7 表 4 1 同一安全级别所对应的密钥长度 13 III 摘 要 随着网络技术的飞速发展和 Internet 的快速普及 人们通过网络交流信 息的频率越来越高 人们在网上传递着大量的敏感信息 如银行帐号 信用卡 帐号等 而这些信息对于接收者以外的第三方具有严格的保密需求 所以信息 传输的安全就是个急待解决的问题 密码技术 特别是公钥密码技术的快速发 展给网络信息的交换开拓了众多崭新的领域 各种密码体制和密码算法的成熟 和完善 为信息的安全传输提供了很多有效的解决方案 本文将从密码学基础 古典密码学 密码技术和公钥算法几个方面 对密码学做一个简单的介绍 关键字 密码学基础 古典密码学 密码技术 公钥算法关键字 密码学基础 古典密码学 密码技术 公钥算法 IV Abstract With the rapid development of network technology and the rapid popularization of Internet people exchange information through the network more and more high frequency people in online transfer of sensitive information such as bank account numbers credit card numbers and these information to receive outside third party has strict security demand so the information transmission security is a urgent problems to be solved The password technology especially the rapid development of public key cryptography technology to network information exchange opened up many new fields various cryptographic schemes and algorithms of the mature and perfect in order to secure transmission of information provides many effective solutions This article from the foundations of cryptography a classical cryptography encryption and public key cryptography algorithm aspects to make a simple introduction Keywords Foundations of cryptography classical cryptography encryption technology public key algorithm 1 第一章第一章 密码学基础密码学基础 1 1 密码学的基本概念和专业术语 1 1 1 发送者和接收者 假设发送者想发送消息给接收者 且想安全地发送信息 她想确信偷听者不能阅读发 送的消息 1 1 2 消息和加密 消息被称为明文 用某种方法伪装消息以隐藏它的内容的过程称为加密 加了密的消 息称为密文 而把密文转变为明文的过程称为解密 图 1 1 表明了这个过程 明文 密文 原始明文 图 1 1 加密与解密 1 1 3 算法和密钥 密码算法也叫密码 是用于加密和解密的数学函数 密码算法是密码协议的基础 如果算法的保密性是基于保持算法的秘密 这种算法称为受限制的算法 受限制的 算法具有历史意义 但按现在的标准 它们的保密性已远远不够 大的或经常变换的用 户组织不能使用它们 因为每有一个用户离开这个组织 其它的用户就必须改换另外不 同的算法 如果有人无意暴露了这个秘密 所有人都必须改变他们的算法 更糟的是 受限制的密码算法不可能进行质量控制或标准化 每个用户组织必须有 他们自己的唯一算法 这样的组织不可能采用流行的硬件或软件产品 但窃听者却可以 买到这些流行产品并学习算法 于是用户不得不自己编写算法并予以实现 如果这个组 织中没有好的密码学家 那么他们就无法知道他们是否拥有安全的算法 尽管有这些主要缺陷 受限制的算法对低密级的应用来说还是很流行的 用户或者 没有认识到或者不在乎他们系统中内在的问题 现代密码学用密钥解决了这个问题 密钥用K 表示 K 可以是很多数值里的任意 值 密钥 K 的可能值的范围叫做密钥空间 加密和解密运算都使用这个密钥 即运算 都依赖于密钥 并用 K 作为下标表示 这样 加 解密函数现在变成 加密解密 2 EK M C DK C M 这些函数具有下面的特性 DK EK M M 有些算法使用不同的加密密钥和解密密钥 也就是说加密密钥 K1 与相应的解密密钥 K2 不同 在这种情况下 EK1 M C DK2 C M DK2 EK1 M M 所有这些算法的安全性都基于密钥的安全性 而不是基于算法的细节的安全性 这就 意味着算法可以公开 也可以被分析 可以大量生产使用算法的产品 即使偷听者知道你 的算法也没有关系 如果他不知道你使用的具体密钥 他就不可能阅读你的消息 密码系统由算法 以及所有可能的明文 密文和密钥组成的 1 1 4 密码分析 密码学史密码分析和密码学是共同演化的 这从密码学史中可以看得很明显 总是有 新的密码机被设计出来并取代已经被破解的设计 同时也总是有新的密码分析方法被发明 出来以破解那些改进了的方案 事实上 密码和密码分析是同一枚硬币的正反两面 为了 创建安全的密码 就必须考虑到可能的密码分析 密码分析学实在不知道密钥的情况下 恢复出明文的科学 成功的密码分析能恢复出 消息的明文和密钥 密码分析也可以发现密码体制的弱点 常用的密码分析攻击有四类 当然 每一类都假设密码分析这知道所用的加密算法的 全部知识 1 唯密文攻击 对于这种形式的密码分析 破译者已知的东西只有两样 加密算法 待破译的密文 2 已知明文攻击 在已知明文攻击中 破译者已知的东西包括 加密算法和经密钥加密形成的一个或多 个明文 密文对 即知道一定数量的密文和对应的明文 3 选择明文攻击 选择明文攻击的破译者除了知道加密算法外 他还可以选定明文消息 并可以知道对 3 应的加密得到的密文 即知道选择的明文和对应的密文 例如 公钥密码体制中 攻击者 可以利用公钥加密他任意选定的明文 这种攻击就是选择明文攻击 4 选择密文攻击 与选择明文攻击相对应 破译者除了知道加密算法外 还包括他自己选定的密文和对 应的 已解密的原文 即知道选择的密文和对应的明文 上述四种攻击的强度按序递增 唯密文攻击显然是比较困难的 但对于密码的编制者 来说 设计一个密码能抵御唯密文攻应该是最低的要求了 1 2 密码学的历史 密码是一向有着久远历史的技术 它伴随着战争的出现而出现 公元前 5 世纪 古希腊斯巴达出现原始的密码器 用一条带子缠绕在一根木棍上 沿 木棍纵轴方向写好明文 解下来的带子上就只有杂乱无章的密文字母 解密者只需找到相 同直径的木棍 再把带子缠上去 沿木棍纵轴方向即可读出有意义的明文 这是最早的换 位密码术 第一次世界大战后 情况开始变化 完全处于秘密工作状态的美国陆军和海军的机要 部门开始在密码学方面取得根本性的进展 在 30 年代和 40 年代 有几篇基础性的文章出 现在公开的文献中 有关该领域的几篇论文也发表了 只不过这些论文的内容离当时真正 的技术水平相去甚远 战争结束时 情况急转直下 公开的文献几乎殆尽 到了第二次世界大战时多表密码编制达到了顶点也达到了终点 当年希特勒一上台就 试验并使用了一种命名为 谜 的译码机 一份德国报告称 谜 型机能产生 220 亿种 不同的密钥组合 假如一个人日夜不停地工作 每分钟测试一种密钥的话 需要约 4 2 万 年才能将所有的密钥可能组合试完 希特勒完全相信了这种密码机的安全性 在 1967 年 David Kahn 的 破译者 出现 它没有任何新的技术思想 但却对以往 的密码学历史作了相当完整的记述 包括提及政府仍然认为是秘密的一些事情 破译者 的意义不仅在于它涉及到的相当广泛的领域 而且在于它使成千上万原本不知道密码学的 人了解密码学 新的密码学文章慢慢地开始源源不断地被编写出来了 4 第二章第二章 古典密码学古典密码学 古典密码是密码学的渊源 这些密码大都比较简单 可用手工或机械操作实现加密 现在已经很少采用了 根据密码变幻的规则 可以把古典密码分为代替密码和置换密码两 大类 2 1 代替密码 替代密码是指先建立一个替换表 加密时将需要加密的明文依次通过查表 替换为相 应的字符 明文字符被逐个替换后 生成无任何意义的字符串 即密文 替代密码的密钥 就是其替换表 根据密码算法加解密时使用替换表多少的不同 替代密码又可分为单表替 代密码和多表替代密码 2 1 1 单表替代密码 单表替代密码对明文中的所有字母都使用一个固定的映射 明文字母表到密文字母表 设 A a0 a1 an 1 为包含了 n 个字母的明文字母表 B b0 b1 bn 1 为包含 n 个字母的密文字母表 单表替代密码使用了 A 到 B 的 映射关系 f A B f ai bj 一般情况下 f 是一一映射 以保证加密的可逆性 加密变换过程就是将明文中的每 一个字母替换为密文字母表的一个字母 而单表替代密码的密钥就是映射 f 或密文字母表 经常密文字母表与明文字母表的字符集是相同的 这时的密钥就是映射 f 2 1 2 多表替代密码 多表替代密码使用从明文字母到密文字母的多个映射来隐藏单字母出现的频率分布 每个映射是简单替代密码中的一对一映射多表替代密码将明文字母划分为长度相同的消息 单元 称为明文分组 对明文成组地进行替代 同一个字母有不同的密文 改变了单表替 代密码中密文的唯一性 使密码分析更加困难 多表替代密码的特点是使用了两个或两个以上的替代表 著名的维吉尼亚密码和 Hill 密码等均是多表替代密码 下面简单介绍一下维吉尼亚密码 维吉尼亚密码体制有一个参数 n 在加解密时 同样把英文字母映射为 0 25 的数字 再进行运算 并按 n 个字母一组进行变换 明文空间 密文空间及密钥空间都是长度为 n 5 的英文字母串的集合 因此可表示 加密变换定义如下 设密钥 k k1 k2 kn 明文 m m1 m2 mn 加密变换为 Ek m c1 c2 cn 其中 ci mi ki mod26 i 1 2 n 对密文 c c1 c2 cn 解密变换为 Dk c m1 m2 mn 其中 mi ci ki mod26 i 1 2 n 2 2 置换密码 置换只不过是一个简单的换位 每个置换都可以用一个置换矩阵 Ek 来表示 每个置 换都有一个与之对应的逆置换 Dk 置换密码的特点是仅有一个发送方和接受方知道的加密 置换及对应的逆置换 它是对明文 L 长字母组中的字母位置进行重新排列 而每个字母本 身并不改变 令明文 m m1 m2 mL 令置换矩阵所决定的置换为 pi 则加密置换 c Ek m c1 c2 cL mpi 1 mpi 2 mpi L 解密置换 d Dk c cn 1 1 cn 1 2 1 L 例 置换密码 给定明文为 the simplest possible transposition ciphers 将明文分成长为 L 5 的段 m1 thesi m2 mples m3 tposs m4 iblet m5 ransp m6 ositi m7 oncip m8 her sx 最后一段长不足 5 加添一个字母 x 将隔断的字母序号按下述置换矩阵进行换位 Ek 0 1 2 3 4 1 4 3 0 2 得到密文如下 STIEH EMSLP STSOP EITLB SRPNA TOIIS IOPCN SHXRE 利用下述置换矩阵 Dk 0 1 2 3 4 3 0 4 2 1 可将密文恢复为明文 6 L 5 时可能的置换矩阵总数为 5 120 一般为 L 个 可以证明 在给定 L 下所有 的置换矩阵构成一个 L 对称群 第第三三章章 密密码码技技术术 3 1 密钥长度 密码算法的安全性与采用对称还是非对称体制没有关系 其安全性密钥的长度相关 密钥长度越长 安全性就越高 但同时计算代价也在增加 密钥长度的选择原则是在安全 性和计算代价之间的折中 既保证系统的安全性 又不至于开销太大 3 1 1 对称密钥长度 对称密码体制的安全性是算法强度和密钥长度的函数 前者更加重要而后者则更容易 描述 假设算法具有足够的强度 实际上这点极难做到 不过本例却很容易 这里我所指的 足够是 除了用穷举攻击的方式试探所有的密钥外没有更好的方法破译该密码系统 为了发动对密码系统的攻击 密码分析者需要少量的密文和对应的明文 穷举攻击是 一种已知明文的攻击 对分组密码来说 密码分析者需要密文分组和对应的明文分组 通 常是 64 比特 获得明文和密文比你想象的要容易 密码分析者可通过一些手段获取明文消 息的副本而后去截取相应的密文 他们可能知道有关密文格式的一些信息 而所有这些格 式都有一些予定义字节 密码分析者不需要太多的明文来发起这种攻击 穷举攻击的复杂程度 密钥长度为 n 位 则有种可能的密钥 因此需要次计算 2n2n 表 3 1 给出了不同密钥长度的情况 假如每秒测试 100 万个密钥 穷举攻击所需要的时间 表 3 1 穷举攻击的运算量 密钥位数试验次数时间 年 8 8 2 56 56 2 2285 64 64 2 585000 7 128 128 2 25 10 2048 2048 2 597 10 可见 当密钥长度足够长时 将使穷举攻击的时间太长而无法成功 3 1 2 公开密钥长度 公开密钥密码体制是基于数学难题的 主要是大数因子分解和有限域中寻找离散对数 这类难题 RAS 算法的密钥长度取决于因数分解的时间 表 3 2 给出了使用通用术语筛选法和特 殊数域筛法分解因数时间 单位为 MIPS 年 表 3 2 使用通用术语筛选法和特殊数域筛法分解因数时间 十进制 所需 MIPS 年 分解法法 5127681024128015362048 通用数域筛法300000 2 8 103 11 101 14 103 16 103 20 10 特殊数域筛法 200100000 3 7 103 9 102 11 104 14 10 因此 在选择公开密钥密码算法时 既要看系统需要保证的安全性 又要看密钥的生 存期 还要看因数分解的能力 根据不同情况下的信息的不同价值 并假设计算机的计算 能力每 5 年提高 9 倍 Bruce Schneier 给出的公开密钥长度建议值如表 3 3 所示 Ron Rivest 给出的密钥长度建议值比较乐观 如表 3 4 所示 表 3 3 Bruce Schneier 公开密钥长度建议值 年度对于个人对于公司对于政府 199576812801536 2000102412801536 2005128015362048 2010128015362048 2015153620482048 表 3 4 Ron Rivest 密钥长度建议值 年度较小值平均值较大值 19903985151289 19954055241399 20004225721512 20054396021628 20104556311754 8 20154726611884 20204896772017 密钥应该多长 答案并不固定 它要视情况而定 3 2 密钥管理 密钥管理包括 从密钥的产生到密钥的销毁的各个方面 在现实世界里 密钥管理是 密码学领域最困难的部分 设计安全的密钥算法和协议是不容易的 相对来说 对密钥进 行保密更加困难 3 2 1 密钥产生的流程 1 产生密钥 一般来说 密钥长度越大 对应的密钥空间就越大 攻击者使用穷举猜测密码的难度 就越大 选择好密钥 避免弱密钥 由自动处理设备生成的随机的比特串是好密钥 选择密钥 时 应该避免选择一个弱密钥 对公钥密码体制来说 密钥生成更加困难 因为密钥必须满足某些数学特征 密钥生成可以通过在线或离线的交互协商方式实现 如密码协议等 2 密钥分发 采用对称加密算法进行保密通信 需要共享同一密钥 通常是系统中的一个成员先选 择一个秘密密钥 然后将它传送另一个成员或别的成员 X9 17 标准描述了两种密钥 密 钥加密密钥和数据密钥 密钥加密密钥加密其它需要分发的密钥 而数据密钥只对信息流 进行加密 为增强保密性 也可以将密钥分成许多不同的部分然后用不同的信道发送出去 3 验证密钥 密钥附着一些检错和纠错位来传输 当密钥在传输中发生错误时 能很容易地被检查 出来 并且如果需要 密钥可被重传 接收端也可以验证接收的密钥是否正确 发送方用密钥加密一个常量 然后把密文的 前 2 4 字节与密钥一起发送 在接收端 做同样的工作 如果接收端解密后的常数能与发 端常数匹配 则传输无错 4 更新密钥 9 当密钥需要频繁的改变时 频繁进行新的密钥分发的确是困难的事 一种更容易的解 决办法是从旧的密钥中产生新的密钥 有时称为密钥更新 可以使用单向函数进行更新密 钥 如果双方共享同一密钥 并用同一个单向函数进行操作 就会得到相同的结果 5 备份密钥 密钥的备份可以采用密钥托管 秘密分割 秘密共享等方式 最简单的方法 是使用密钥托管中心 密钥托管要求所有用户将自己的密钥交给密钥 托管中心 由密钥托管中心备份保管密钥 一旦用户的密钥丢失 按照一定的规章制度 可从密钥托管中心索取该用户的密钥 另一个备份方案是用智能卡作为临时密钥托管 秘密分割把秘密分割成许多碎片 每一片本身并不代表什么 但把这些碎片放到一块 秘密就会重现出来 一个更好的方法是采用一种秘密共享协议 将密钥 K 分成 n 块 每部分叫做它的 影 子 知道任意 m 个或更多的块就能够计算出密钥 K 知道任意 m 1 个或更少的块都不能 够计算出密钥 K 这叫做 m n 门限方案 6 密钥有效期 没有哪个加密密钥能无限期使用 有以下有几个原因 密钥使用时间越长 它泄露的 机会就越大 如果密钥已泄露 那么密钥使用越久 损失就越大 密钥使用越久 人们花 费精力破译它的诱惑力就越大枣甚至采用穷举攻击法 对用同一密钥加密的多个密文进行 密码分析一般比较容易 对任何密码应用 必须有一个策略能够检测密钥的有效期 不同密钥应有不同有效期 基于连接的系统 如电话就是把通话时间作为密钥有效期 当再次通话时就启用新的密钥 7 密钥的撤销和销毁 当与密钥有关的系统已经迁移 或者怀疑一个特定的密钥已经受到威胁 密钥的使用 目的已经改变 就必须进行密钥的撤销 密钥的销毁指清除一个密钥的所有踪迹 3 2 2 公开密钥的密钥管理 公开密钥密码使得密钥较易管理 无论网络上有多少人 每个人只有一个公开密钥 使用一个公钥 私钥密钥对是不够的 任何好的公钥密码的实现需要把加密密钥和数字 签名密钥分开 但单独一对加密和签名密钥还是不够的 象身份证一样 私钥证明了一种 10 关系 而人不止有一种关系 3 3 密钥管理技术 3 3 1 密钥管理技术的分类 1 对称密钥管理 对称加密是基于共同保守秘密来实现的 采用对称加密技术的贸易 双方必须要保证采用的是相同的密钥 要保证彼此密钥的交换是安全可靠的 同时还要设 定防止密钥泄密和更改密钥的程序 这样 对称密钥的管理和分发工作将变成一件潜在危 险的和繁琐的过程 通过公开密钥加密技术实现对称密钥的管理使相应的管理变得简单和 更加安全 同时还解决了纯对称密钥模式中存在的可靠性问题和鉴别问题 贸易方可以为 每次交换的信息生成唯一一把对称密钥并用公开密钥对该密钥进行加密 然后再将加密后 的密钥和用该密钥加密的信息一起发送给相应的贸易方 由于对每次信息交换都对应生成 了唯一一把密钥 因此各贸易方就不再需要对密钥进行维护和担心密钥的泄露或过期 这 种方式的另一优点是 即使泄露了一把密钥也只将影响一笔交易 而不会影响到贸易双方 之间所有的交易关系 这种方式还提供了贸易伙伴间发布对称密钥的一种安全途径 2 公开密钥管理 数字证书 贸易伙伴间可以使用数字证书来交换公开密钥 数字证 书通常包含有唯一标识证书所有者的名称 唯一标识证书发布者的名称 证书所有者的公 开密钥 证书发布者的数字签名 证书的有效期及证书的序列号等 证书发布者一般称为 证书管理机构 它是贸易各方都信赖的机构 数字证书能够起到标识贸易方的作用 是目 前电子商务广泛采用的技术之一 3 密钥管理相关的标准规范 目前国际有关的标准化机构都着手制定关于密钥管理的 技术标准规范 ISO 与 IEC 下属的信息技术委员会已起草了关于密钥管理的国际标准规范 该规范主要由三部分组成 一是密钥管理框架 二是采用对称技术的机制 三是采用非对 称技术的机制 该规范现已进入到国际标准草案表决阶段 并将很快成为正式的国际标准 3 3 2 数字签名 数字签名是公开密钥加密技术的另一类应用 它的主要方式是 报文的发送方从报文 文本中生成一个 128 位的散列值 发送方用自己的专用密钥对这个散列值进行加密来形成 发送方的数字签名 然后 这个数字签名将作为报文的附件和报文一起发送给报文的接收 方 报文的接收方首先从接收到的原始报文中计算出 128 位的散列值 接着再用发送方的 11 公开密钥来对报文附加的数字签名进行解密 如果两个散列值相同 那么接收方就能确认 该数字签名是发送方的 通过数字签名能够实现对原始报文的鉴别和不可抵赖性 第第四四章章 公公开开密密钥钥算算法法 4 1 简介 公开密钥密码体制是现代密码学的最重要的发明和进展 一般理解密码学就是保护信 息传递的机密性 1976 年提出公共密钥密码体制 其原理是加密密钥和解密密钥分离 这样 一个具体 用户就可以将自己设计的加密密钥和算法公诸于众 而只保密解密密钥 任何人利用这个 加密密钥和算法向该用户发送的加密信息 该用户均可以将之还原 公共密钥密码的优点 是不需要经安全渠道传递密钥 大大简化了密钥管理 它的算法有时也称为公开密钥算法 或简称为公钥算法 但这仅仅是当今密码学主题的一个方面 对信息发送与接收人的真实身份的验证 对 所发出 接收信息在事后的不可抵赖以及保障数据的完整性是现代密码学主题的另一方面 公开密钥密码体制对这两方面的问题都给出了出色的解答 并正在继续产生许多新的 思想和方案 在公钥体制中 加密密钥不同于解密密钥 人们将加密密钥公之于众 谁都 可以使用 而解密密钥只有解密人自己知道 迄今为止的所有公钥密码体系中 RSA 系统 是最著名 使用最广泛的一种 4 2 背包算法 1977 年 Merkle 与 Hellman 合作设计了使用背包问题实现信息加密的方法 其工作原 理是 假定甲想加密 则先产生一个较易求解的背包问题 并用它的解作为专用密钥 然 后从这个问题出发 生成另一个难解的背包问题 并作为公共密钥 如果乙想向甲发送报 文 乙就可以使用难解的背包问题对报文进行加密 由于这个问题十分难解 所以一般没 有人能够破译密文 甲收到密文后 可以使用易解的专用密钥解密 12 4 2 1 加法背包 我们知道 1 2 1 2 4 1 2 4 8 1 2 4 8 16 那么如果我们选择这样一些数 这 些数从小到大排列 如果前面所有的数加起来的值总小于后面的数 那么这些数就可以构 成一个背包 我们给一个这个背包里面的某些数的和 这个数就是被加密的数 由这个背 包组成这个数只有一种组合方式 这个方式就是秘密了 例如给大家一个封包 2 3 6 12 24 48 由这个背包里的某些数构成的数 86 你知道 86 怎么来的吗 当然 你看着背包里面的内容 可以知道是由 2 12 24 48 得到的 如果你没有这个背包 而是直接得到这个 86 你无法知道 因为加起来等于 86 的数非常多 所以 背包加密非 常难破 4 2 2 乘法背包 乘法背包比加法背包更复杂 不仅是运算量大了很多 更重要的是你得到的一个被加 密了的数据更大 一般都是上亿的 而且在许多机密的机关里面 背包的数据都不是有这 个单位 而是用位 我们知道 1 2 1 2 3 1 2 3 7 1 2 3 7 43 1 2 3 7 42 1683 数字的 增长还是很快的 之所以复杂 就是因为数字很大 背包的特点是 如果背包里面的数据 按小到大排列 那么 前面所有数据的乘积小于后面的任何一个元素 这个就是背包的特 点 是不是很简单 但是要知道乘积的数字的增长是非常快的 4 3 RSA 算法 RSA 公钥加密算法是 1977 年由 Ron Rivest Adi Shamirh 和 LenAdleman 在美国麻省理 工学院开发的 RSA 是目前最有影响力的公钥加密算法 它能够抵抗到目前为止已知的所 有密码攻击 已被 ISO 推荐为公钥数据加密标准 RSA 算法基于一个十分简单的数论事实 将两个大素数相乘十分容易 但那时想要对其乘积进行因式分解却极其困难 因此可以将 乘积公开作为加密密钥 4 3 1 RSA 算法的描述 RSA 算法是第一个能同时用于加密和数字签名的算法 也易于理解和操作 RSA 是被研究得最广泛的公钥算法 从提出到现在已近二十年 经历了各种攻击的考 验 逐渐为人们接受 普遍认为是目前最优秀的公钥方案之一 RSA 的安全性依赖于大数 的因子分解 但并没有从理论上证明破译 RSA 的难度与大数分解难度等价 即 RSA 的重 13 大缺陷是无法从理论上把握它的保密性能如何 而且密码学界多数人士倾向于因子分解不 是 NPC 问题 RSA 的缺点主要有 产生密钥很麻烦 受到素数产生技术的限制 因而难以做到一次 一密 分组长度太大 运算代价很高 RSA 密钥长度随着保密级别提高 增加很快 表 4 1 列出了对同一安全级别所对应的密钥长度 表 4 1 同一安全级别所对应的密钥长度 保密级别对称密钥长 度 bit RSA 密钥长 度 bit ECC 密钥长 度 bit 保密年限 8080102410242010 11211220481602030 12812830722242040 19219276802562080 256256153603842120 RSA 算法是一种非对称密码算法 所谓非对称 就是指该算法需要一对密钥 使用其 中一个加密