安全生产_代数在网络安全中的应用培训课件

代数在网络安全中的应用 20131989应用数学2班童钞 概述 现有的公钥密码体制大多是建立在交换代数的基础上 例如著名的RSA密码体制 Diffie Hellman密钥交换协议和ELGamal密码体制都基于整数环 而概率公钥算法NTRU则基于多项式环 交换代数结构的优点在于有丰富的理论 容易理解的结构并且易于实现 但是 由于计算能力的持续增强 为保证预期安全水平所需要的密钥长度也不断增长 这就使得基于交换代数的公钥密码遭遇了计算瓶颈 因此有必要寻找基于更加复杂的代数结构的密码技术 近年出现的一种具有强大竞争力的椭圆曲线密码学 ECC 对RSA提出了挑战 在关于公钥密码学的IEEEP1363中 已经考虑了ECC 在公钥密码学中使用椭圆曲线是NealKoblitz和VictorMiller于1985年各自独立地提出的 与RSA相比 ECC的主要诱人之处在于它可以用比RSA短得多的密钥得到相同的安全性 因此可以减少处理负荷 近年来 基于 超奇异 椭圆曲线上双线性对的密码体制的研究十分活跃 解决了构造三方一轮Diffie Hellman密钥协议 短签名方案和基于身份加密算法等长期悬而未决的公开问题 但是 正如Barreto Lynn Scott所指出 超奇异 椭圆曲线上Weil对与Tate对的运算成本经常使它成为基于双线性对密码系统的瓶颈 寻找安全高效的双线性对已成为基于双线性对密码学的首要问题 目前 已经出现了一些使用非交换代数的公钥密码系统 尤其是辫子群密码学吸引了大量的研究 1999年 Anshel Anshel Goldfeld基于辫子群中的共轭问题构建了密钥交换协议 2000年 KoLee等人利用辫子群的子群间的交换关系构建了基于广义共轭问题的Diffie Hellman密钥交换协议 以及一个类似于ELGamal体制的加密算法 但是 由于非交换群中没有像整数环中加法那样与共轭运算相容的运算 这使得基于非交换群的签名方案的设计变得困难 直到2002年 Ko Choi Cho Lee才基于共轭问题的计算形式和判定形式之间的鸿沟 Gap 设计了第一个辫子群签名方案 目录 基于椭圆曲线的密码算法循环矩阵在网络安全中的应用DES算法基于双线性对的密码学基于辫子群的密码体制AES算法RSA算法SHA 1算法离散对数密码体制 椭圆曲线在网络安全中的应用 椭圆曲线的定义及点的加法运算 有限域上的椭圆曲线 椭圆曲线的离散对数问题 椭圆曲线密码体制的概念 椭圆曲线密码体制是属于公钥密码体制中的一种 它主要的数学理论基础是源于数论的相关知识 它是通过有限域中椭圆曲线上的点构成的Aebel加法群 在Aebel群中计算椭圆对数 现在国际上比较流行的密码体制都是以三种难解的理论为依据而设计的 其中一种是基于大整数因子分解问题设计的比如RSA公钥密码体制 还有一种是基于离散对数的难解问题而设计的比如ELGamal公钥密码体制 最后一种就是同样基于离散对数问题设计的椭圆曲线密码体制 构造椭圆曲线 ElGamal算法 ElGamal算法 是一种较为常见的加密算法 它是基于1984年提出的公钥密码体制和椭圆曲线加密体系 既能用于数据加密也能用于数字签名 其安全性依赖于计算有限域上离散对数这一难题 在加密过程中 生成的密文长度是明文的两倍 且每次加密后都会在密文中生成一个随机数K 在密码中主要应用离散对数问题的几个性质 求解离散对数 可能 是困难的 而其逆运算指数运算可以应用平方 乘的方法有效地计算 也就是说 在适当的群G中 指数函数是单向函数 椭圆曲面密码体制的应用背景及优势 我们现在快速的生活节奏和便捷的生活方式都是显而易见的 足不出户的我们就能够通过计算机完成许多的事情 比如工作 购物等 由于需求的增加导致计算机也不断的改进提高 尤其是计算机速度的提高 同时也就需要更好更完善的加密方案 由于现在普遍使用的是经典的公钥密码体制RSA 但在密钥长度为512比特的情况下却逐渐变得不安全 通过加长密钥长度虽然可以提高密码的安全性能 但是加密解密的效率也会变得越来越低 所以最好的方式就是设计一种新的密码体制替代原本使用的 4 椭圆曲线密码体制就是在这样的背景下开始逐渐受到重视的 是一种以椭圆曲线相关数学知识为基础的公钥密码体制 4 在公钥密码体制中与其它算法相比较 椭圆曲线密码体制具有密钥短和计算效率高等典型优点 而其本身的算法及其数学理论都是非常深奥难懂的 椭圆曲线密码体制应用在实际中的主要优势有 安全性能较高 速度快 计算量小 效率高 对于所有的密码体制而言 它的安全性能毫无疑问的成为了核心的问题 对于椭圆曲线密码体制来说它的数学原理是对它安全性能最有利的左证 该体制的核心是有限域上的离散对数问题 4 而这个问题是不能在多项式时间内使用所有的已知算法来求解的 由此可见该体制的抗攻击性能与其它体制相比是占有绝对优势的 下面通过一个表格可以更直观的感受椭圆曲线密码体制的这点优势 由表格可以看出 将160位的ECC算法和1024位的RSA算法作为比较它们的安全强度相差不多 并且在同等的条件下安全强度要求越高的话ECC算法的短密钥优势也就显现的更为明显 所以 ECC算法与RSA算法相比较在每一比特都是拥有更高的安全性能的 也正是由于拥有这样的特点 才能广泛的应用于移动的电子商务以及计算机网络安全和软件注册的相关领域 公开密钥的生成速度主要取决于其中的大数算术运算而它的运算速度自然和它的大小规模息息相关 在一个相同的计算条件下 椭圆曲线密码体制 ECC 的实现可以选择比基于大合数因子分解困难性的公开密钥密码体制 RSA 小很多的大数 这也就保证了实现的速度和效率 同样可以通过下面表格中的数据来说明 通过上表就可以明显的看出ECC在密钥对的生成速度 签名速度和认证方面的速度都快得多 计算量小且计算速度快 尤其是在存储容量不大运算能力比较低的情况下是具有显著优势的 所需存储的空间比较小 带宽要求较低 椭圆曲线密码体制的密钥长度与基于大合数因子分解困难性的公开密钥密码体制相比就要小很多 这一点也可以从表1中看出来 比如RSA需要512位元元而ECC只需要106位即可 这也就表明了ECC对存储空间的需求要较小 在计算上的开销也很小 所以ECC会广泛的应用在类似这些存储空间有限制的设备中 同样也是由于这样的优势决定了ECC可以广泛的使用在移动通信设备和智能卡等存储空间小计算能力相对较差的设备上 带宽即频带宽度是指可以有效通过某信道的信号最大频带宽度 因为椭圆曲线密码体制和其它加密算法相比具有密钥短的特点 所以在传输中要求的带宽也更低 当对一个长的数据信息进行加密时ECC和RSA密码系统有同样的带宽要求 8 但是应用在较短的数据信息中ECC的带宽要求却低很多 这也是ECC能够广泛的应用于无线网络中的重要原因 ECC的使用可以减少一定的带宽开销所以使得通信的效率也大幅提高 并且在Web服务器上使用带宽的费用是十分高昂的 ECC的出现既解决了需要节省计算时间的要求又节约了因带宽需要的花费 在3G网络中针对计算效率低 带宽资源有限的限制 基于椭圆曲线密码体制而涉及安全的支付流程是可以实现端对端的安全数据信息传送 在对系统初始化以及设置系统参数时椭圆曲线密码体制也有不同于其它密码体制的优势 比如与RSA算法相比 RSA需要选取两个素数才能初始化 而ECC则需要选择一个素数并在有限域上选取不同的椭圆曲线 因为选择椭圆曲线时有很多的选择所以初始化的选择空间就很大 基于以上的这些优点 椭圆曲线密码体制在实际中的应用十分广泛 比如虚拟专用网络VPN安全隧道方面由于要考虑到计算机存储和资源方面对嵌入式应用的局限性 依据ECC加密解密速度较快 节省带宽和节省所需要的存储资源的特点可以选择使用椭圆曲线密码体制设计应用于身份鉴别中 在网络的通信中必须要高效率的对数据信息进行加密 而ECC的快速处理速度可以使通信不再受限于存储的容量大小和计算能力的高低 除此之外 椭圆曲线密码体制在数字签名等需要高加密速度的方面也能快速实现安全高效的加密 签名 指纹加密与椭圆曲线 随着近几年科技的发展 尤其是生物特征识别技术的逐步成熟 通过利用生物体本身具有唯一稳定不变性的特征将其运用到确保信息安全的领域 指纹加密技术就是生物识别技术与信息安全融洽结合的最好体现 由于生物特征的唯一性就可以保证使用指纹信息进行身份验证会比其他方案有更高的安全性 准确性 指纹采集端和指纹认证端是分开工作的 它们之间通过网络传输数据信息 这也是指纹识别认证系统中的一个特点 首先是采集指纹信息的过程 用户通过提取指纹的仪器完成该步骤 然后再将指纹信息的数字图像传送给计算机 之后计算机完成指纹特征的采集工作 并将指纹的数字图像转换成即将进行加密操作的特征序列 此时就可以将加密后的信息传送到指纹认证的终端了 在终端完成对应的解密操作 指纹特征的对比操作 最后将对比的结果返回 也就是完成了一次通过网络对指纹身份的识别认证操作 该方案与上文中介绍的EIGamal方案的原理基本相同 具体如下 方案的优缺点 该方案的优点主要体现在指纹的唯一性决定了较高的安全性 也就是说其他的加密方式也能够达到同样安全的效果 换言之 这个方案的安全性并不取决于加密算法的复杂程度 而是取决于加密的数据信息的安全强度 但是 与其他的加密方式相比椭圆曲线使用较少 较小的参数完成过程 尤其与RSA算法相比计算过程更不易出错 所以使用椭圆曲线密码体制进行加密还是比较高效的 椭圆曲线密码体制与RSA密码体制在实际应用中的比较 椭圆曲线密码算法和RSA算法相比最大的优点就是不需要计算椭圆曲线有理点群的离散对数问题的子指数算法 也就是说当在同等安全的条件下 椭圆曲线密码算法可以选择比RSA算法更小的参数进行加密解密操作 同时椭圆曲线密码算法将实数域中乘法的运算和指数的运算映像成了椭圆曲线上加法的运算 综上所述 椭圆曲线密码体制更实用 更容易 更安全 同时成本也更低 将两种算法作比较可以发现 RSA算法的过程不仅复杂还必须严格保密 对于素数的产生和检测的计算过程容易产生错误 而椭圆曲线密码算法虽然生成的参数复杂但是不需要保密甚至还可以对外公布 不过虽然保密的密钥生成复杂但是计算公钥很容易 椭圆曲线密码体制具有椭圆曲线丰富 不易被破解 不需要大量的参数参与计算及不占用大量存储空间的优势 比如在数字签名中完成各部分的效率方面进行比较 RSA算法是几乎不会受到密钥位数变化的影响 一直都可以保持着很快的验证速度 相反地 ECC算法受到的影响很剧烈 与RSA算法受影响程度相比有很大的差距 在使用超过一定的密钥位数的范围中 随着密钥位数逐渐地增大ECC算法就会越优于RSA算法 对于相同使用量的参数 椭圆曲线密码体制在每一比特的加密解密过程中都拥有更大的强度 并且所需要的参数规模也较小 这在实际的应用中是具有很大优势的 椭圆曲线虽然子在一个有限域中只有有限的几个乘法子群 但是却有很高的安全性能 所以成为公钥密码学中应用广泛的新体制 二 循环矩阵在网络安全中的应用 多变量密码学中的循环矩阵 等价的多项式定义了相同密码体制 因此等价的多项式产生的密码体制也有相同的密钥空间和加 解密映射的集合 一个等价类的势 cardinality 相当于选取不同的仿射变换对所产生的加密映射的个数 这就引出了找到产生相同加密映射的仿射变换的个数问题 例如 对于一个给定的多变量公钥密码体制 找到其等价密钥的个数 在一个等价类中的不同多项式方程组的个数代表可以选择的不同密钥的个数 等价密钥的存在可以缩小密钥空间 这对于多变量公钥密码学的密码分析是很有帮助的 多项式同构引出多项式方程组的等价关系 因此多项式方程组的集合可以被划分为不同的等价类 多项式同构的计数问题则包含以下3个方而 1 对不同等价类的计数 2 对每一个等价类的势进行计数 3 确定所有的等价类的代表元 基于循环矩阵的ElGamal密码体制 离散对数问题是公钥密码学中应用最广泛的一个密码原语 其应用之一是最经典的ElGamal密码系统 众所周知 ElGamal密码系统的安全性依赖于有限域上的离散对数问题 为了能够提出更安全的密码系统 人们开始将有限域上的离散对数问题推广到非交换群上的离散对数问题 并在此上提出了MOR密码系统 可以说MOR密码系统是ElGamal密码系统在非交换群上的推广 而这个非交换群是循环矩阵群的自同构群 循环矩阵群提供了一个有限域上的同样大小的安全 且它有一半的计算成本 循环矩阵的另一个有趣的事实是 其能提供一个安全的域的实现大小 循环矩阵的算法是在有限域上进行运算 这与椭圆曲线的情况极为相似 在循环的情况下 该域的大小甚至可以小于一个用于椭圆曲线的大小 总之 循环矩阵的优点是 它使用较小的域而且运算速度更快 在该文献中 所有矩阵是非奇异循环矩阵C d q 和特殊循环矩阵 即循环矩阵的行列式1 记为SC d q ElGamal密码体制在SC d q 的实现 在SC d q 的ElGamal密码系统中 需要进行十二次的逆操作 这是很容易计算的 自公钥密码学概念提出以来 许多优秀的公钥密码体制相继被提出并得到完善 目前 大多数未被攻破的公钥密码体制都是基于交换代数结构的困难问题 如大整数分解问题 有限域上的离散对数问题等 然而 由于量子计算的最新研究成果 许多基于交换代数结构的难题假设不再困难 迄今为止 人们已经提出了许多基于非交换代数结构的公钥密码体制 特别是辫群密码体制吸引了大量的研究 经过本文的探究 我们可以知道 循环矩阵是数学研究中非常重要的一个数学计算手段 它本身具有很多特殊性质 本文针对循环矩阵的特殊性质 研究了其在密码学中的公钥密码加密解密的过程中的应用 随着电子科技的发展 以及电子通信的普及 密码学得到了前所未有的发展机遇 我们从数学工具 数学算法的角度出发 进行创造性思维 使其在密码学中发挥作用 相信对密码学的研究会越来越成熟 DES算法 DES是一种分组密码协议 有两个基本指导思想扩散 Diffusion 和混乱 Confusion 以保证密码算法能满足要求 所以DES的具体实现是依赖于多次迭代进行乘积密码加密变换 这个算法的核心是Feistel密码 由于其设计的巧妙 加密解密都用一个函数 它的算法是对称的 既可用于加密又可用于解密 DES使用一个56位的密钥以及附加的8位奇偶校验位 产生最大64位的分组大小 这是一个迭代的分组密码 使用称为Feistel的技术 其中将加密的文本块分成两半 使用子密钥对其中一半应用循环功能 然后将输出与另一半进行 异或 运算 接着交换这两半 这一过程会继续下去 但最后一个循环不交换 DES使用16个循环 使用异或 置换 代换 移位操作四种基本运算 DES的流程基本是执行16轮下面的运算 1初始变换InitialPermutation2右边32位f函数2 1E置换2 2与轮密钥XOR2 3S盒替换2 4P置换2 5和左边32位XOR3左右交换 最终变换finalpermutation需要特别注意的是 最后一轮是不需要做左右交换这一部的 从具体实现看DES有几个已知的方面存在脆弱性 1 加密协议半公开化2 密钥太短3 软件的实现的性能较低 随着计算机的处理能力的提高 只有56位密钥的DES算法不再被认为是安全性的 故现在一般的方案是三重DES 既3DES AES算法 AES TheAdvancedEncryptionStandard 是一种非Feistel的对称分组密码体制 和DES的基本指导思想一样都是多次混淆 所不同的是非线性层的由16个S盒进行并置混淆 AES具有安全可靠 效率高等优点 AES加密过程是在一个4 4的字节矩阵上运作 这个矩阵又称为 状态 state 其初值就是一个明文区块 矩阵中一个元素大小就是明文区块中的一个Byte Rijndael加密法因支持更大的区块 其矩阵行数可视情况增加 加密时 各轮AES加密循环 除最后一轮外 均包含4个步骤 1 AddRoundKey 矩阵中的每一个字节都与该次轮秘钥 roundkey 做XOR运算 每个子密钥由密钥生成方案产生 2 SubBytes 通过个非线性的替换函数 用查找表的方式把每个字节替换成对应的字节 3 ShiftRows 将矩阵中的每个横列进行循环式移位 4 MixColumns 为了充分混合矩阵中各个直行的操作 这个步骤使用线性转换来混合每列的四个字节 AddRoundKey步骤 在AddRoundKey步骤中 将每个状态中的字节与该回合密钥做异或 AddRoundKey步骤 回合密钥将会与原矩阵合并 在每次的加密循环中 都会由主密钥产生一把回合密钥 通过Rijndael密钥生成方案产生 这把密钥大小会跟原矩阵一样 以与原矩阵中每个对应的字节作异或 加法 SubBytes步骤 在SubBytes步骤中 矩阵中各字节被固定的8位查找表中对应的特定字节所替换 S bij S aij 在SubBytes步骤中 矩阵中的各字节通过一个8位的S box进行转换 这个步骤提供了加密法非线性的变换能力 S box与GF 28 上的乘法反元素有关 已知具有良好的非线性特性 为了避免简单代数性质的攻击 S box结合了乘法反元素及一个可逆的仿射变换矩阵建构而成 此外在建构S box时 刻意避开了固定点与反固定点 即以S box替换字节的结果会相当于错排的结果 ShiftRows步骤 在ShiftRows步骤中 矩阵中每一行的各个字节循环向左方位移 位移量则随着行数递增而递增 ShiftRows描述矩阵的行操作 在此步骤中 每一行都向左循环位移某个偏移量 在AES中 区块大小128位 第一行维持不变 第二行里的每个字节都向左循环移动一格 同理 第三行及第四行向左循环位移的偏移量就分别是2和3 128位和192比特的区块在此步骤的循环位移的模式相同 经过ShiftRows之后 矩阵中每一竖列 都是由输入矩阵中的每个不同列中的元素组成 Rijndael算法的版本中 偏移量和AES有少许不同 对于长度256比特的区块 第一行仍然维持不变 第二行 第三行 第四行的偏移量分别是1字节 3字节 4位组 除此之外 ShiftRows操作步骤在Rijndael和AES中完全相同 MixColumns步骤 在MixColumns步骤中 每个直行都在modulo 之下 和一个固定多项式c x 作乘法 在MixColumns步骤 每一列的四个字节通过线性变换互相结合 每一列的四个元素分别当作的系数 合并即为GF 28 中的一个多项式 接着将此多项式和一个固定的多项式在modulo下相乘 此步骤亦可视为Rijndael有限域之下的矩阵乘法 MixColumns函数接受4个字节的输入 输出4个字节 每一个输入的字节都会对输出的四个字节造成影响 因此ShiftRows和MixColumns两步骤为这个密码系统提供了扩散性 大致说来 AES加密算法的核心有四个操作 AddRoundKey使用从种子密钥值中生成的轮密钥代替4组字节 SubBytes替换用一个代替表替换单个字节 ShiftRows通过旋转4字节行的4组字节进行序列置换 MixColumns用域加和域乘的组合来替换字节 正如你所看到的 AES加密算法使用相当简单明了的技术来代替和置换 除MixColumns例程以外 MixColumns使用特殊的加法和乘法 AES所用的加法和乘法是基于数学的域论 尤其是AES基于有限域GF 28 GF 28 由一组从0 x00到0 xff的256个值组成 加上加法和乘法 因此是 28 GF代表伽罗瓦域 以发明这一理论的数学家的名字命名 GF 28 的一个特性是一个加法或乘法的操作的结果必须是在 0 x00 0 xff 这组数中 虽然域论是相当深奥的 但GF 28 加法的最终结果却很简单 GF 28 加法就是异或 XOR 操作 在GF 28 中用0 x01的乘法是特殊的 它相当于普通算术中用1做乘法并且结果也同样 任何值乘0 x01等于其自身 现在让我们看看用0 x02做乘法 和加法的情况相同 理论是深奥的 但最终结果十分简单 只要被乘的值小于0 x80 这时乘法的结果就是该值左移1比特位 如果被乘的值大于或等于0 x80 这时乘法的结果就是左移1比特位再用值0 x1b异或 它防止了 域溢出 并保持乘法的乘积在范围以内 一旦你在GF 28 中用0 x02建立了加法和乘法 你就可以用任何常量去定义乘法 用0 x03做乘法时 你可以将0 x03分解为2的幂之和 为了用0 x03乘以任意字节b 因为0 x03 0 x02 0 x01 因此 b 0 x03 b 0 x02 0 x01 b 0 x02 b 0 x01 这是可以行得通的 因为你知道如何用0 x02和0 x01相乘和相加 用0 x0d去乘以任意字节b可以这样做 b 0 x0d b 0 x08 0 x04 0 x01 b 0 x08 b 0 x04 b 0 x01 b 0 x02 0 x02 0 x02 b 0 x02 0 x02 b 0 x01 在加解密算法中 AESMixColumns例程的其它乘法遵循大体相同的模式 如下所示 b 0 x09 b 0 x08 0 x01 b 0 x02 0 x02 0 x02 b 0 x01 b 0 x0b b 0 x08 0 x02 0 x01 b 0 x02 0 x02 0 x02 b 0 x02 b 0 x01 b 0 x0e b 0 x08 0 x04 0 x02 b 0 x02 0 x02 0 x02 b 0 x02 0 x02 b 0 x02 总之 在GF 28 中 加法是异或操作 其乘法将分解成加法和用0 x02做的乘法 而用0 x02做的乘法是一个有条件的左移1比特位 AES规范中包括大量有关GF 28 操作的附加信息 有限域GF 28 的加法和乘法 类似DES AES等算法中双方都使用相同的密钥进行加密解密 我们把这种加解密都使用同一个密钥的密码体制称为对称密码体制 使用相同的密钥进行加密解密 密钥的传输是一个重要的问题 所以 在公开的计算机网络上安全地传送和保管密钥是一个严峻的问题 于是 密码学家们构想了一个不一样的的密码体制来解决这一问题 公钥加密算法 公钥加密算法也称非对称密钥算法 用两对密钥 一个公共密钥和一个专用密钥 用户要保障专用密钥的安全 公共密钥则可以发布出去 公共密钥与专用密钥是有紧密关系的 用公共密钥加密的信息只能用专用密钥解密 反之亦然 由于公钥算法不需要联机密钥服务器 密钥分配协议简单 所以极大简化了密钥管理 除加密功能外 公钥系统还可以提供数字签名 RSA是其中的一种有效实现 RSA的基本指导思想是设计有效的单向陷门函数 来使得正向加密计算容易 没有密钥下的反向计算几乎不可能 RSA的安全性是建立在大整数分解的困难性上的 RSA算法 假设Alice想要通过一个不可靠的媒体接收Bob的一条私人讯息 她可以用以下的方式来产生一个公钥和一个私钥 随意选择两个大的质数p和q p不等于q 计算N pq 根据欧拉函数 求得r p 1 q 1 选择一个小于r的整数e 求得e关于模r的模反元素 命名为d 模反元素存在 当且仅当e与r互质 将p和q的记录销毁 N e 是公钥 N d 是私钥 Alice将她的公钥 N e 传给Bob 而将她的私钥 N d 藏起来 公钥与密钥的产生 假设Bob想给Alice送一个消息m 他知道Alice产生的N和e 他使用起先与Alice约好的格式将m转换为一个小于N的整数n 比如他可以将每一个字转换为这个字的Unicode码 然后将这些数字连在一起组成一个数字 假如他的信息非常长的话 他可以将这个信息分为几段 然后将每一段转换为n 用下面这个公式他可以将n加密为c ne c modN 计算c并不复杂 Bob算出c后就可以将它传递给Alice 加密消息 Alice得到Bob的消息c后就可以利用她的密钥d来解码 她可以用以下这个公式来将c转换为n cd n modN 得到n后 她可以将原来的信息m重新复原 解码的原理是 cd ne d modN 以及ed 1 modp 1 和ed 1 modq 1 由费马小定理可证明 因为p和q是质数 ne d n modp 和ne d n modq 这说明 因为p和q是不同的质数 所以p和q互质 ne d n modpq 解密消息 RSA也可以用来为一个消息署名 假如甲想给乙传递一个署名的消息的话 那么她可以为她的消息计算一个散列值 Messagedigest 然后用她的密钥 privatekey 加密这个散列值并将这个 署名 加在消息的后面 这个消息只有用她的公钥才能被解密 乙获得这个消息后可以用甲的公钥解密这个散列值 然后将这个数据与他自己为这个消息计算的散列值相比较 假如两者相符的话 那么他就可以知道发信人持有甲的密钥 以及这个消息在传播路径上没有被篡改过 签名消息 当p和q是一个大素数的时候 从它们的积pq去分解因子p和q 这是一个公认的数学难题 然而 虽然RSA的安全性依赖于大数的因子分解 但并没有从理论上证明破译RSA的难度与大数分解难度等价 1994年彼得 秀尔 PeterShor 证明一台量子计算机可以在多项式时间内进行因数分解 假如量子计算机有朝一日可以成为一种可行的技术的话 那么秀尔的算法可以淘汰RSA和相关的衍生算法 即依赖于分解大整数困难性的加密算法 另外 假如N的长度小于或等于256位 那么用一台个人电脑在几个小时内就可以分解它的因子了 19