RSA算法的C++实现课程设计报告.doc-资料库

RSA 非对称加密算法 C++实现院（系）：机电信息学院专班学学业：计算机科学与技术级：计科 1001 生：刘静雯号： 1001020107 2012 年 12 月 13 日

1.RSA 算法介绍与应用现状 RSA 公开密钥加密算法自 20 世纪 70 年代提出以来，已经得到了广泛认可和应用。发展至今，电子安全领域的各方面已经形成了较为完备的国际规范。 RSA 作为最重要的公开密钥算法，在各领域的应用数不胜数。RSA 在硬件方面，以技术成熟的 IC 应用于各种消费类电子产品。 RSA 在软件方面的应用，主要集中在 Internet 上。加密连接、数字签名和数字证书的核心算法广泛使用 RSA。日常应用中，有比较著名的工具包 Open SSL(SSL，Security Socket Layer,是一个安全传输协议，在 Internet 上进行数据保护和身份确认。Open SSL 是一个开放源代码的实现了 SSL 及相关加密技术的软件包，由加拿大的 Eric Yang 等发起编写的。Open SSL 应用 RSA 实现签名和密钥交换，已经在各种操作系统得到非常广泛的应用。另外，家喻户晓的 IE 浏览器，自然也实现了 SSL 协议，集成了使用 RSA 技术的加密功能，结合 MD5 和 SHA1，主要用于数字证书和数字签名，对于习惯于使用网上购物和网上银行的用户来说，几乎天天都在使用 RSA 技术。 RSA 更出现在要求高度安全稳定的企业级商务应用中。在当今的企业级商务应用中，不得不提及使用最广泛的平台 j2ee。事实上，在 j2se 的标准库中，就为安全和加密服务提供了两组 API ：JCA 和 JCE 。 JCA (Java Cryptography Architecture)提供基本的加密框架，如证书、数字签名、报文摘要和密钥对产生器； JCA 由几个实现了基本的加密技术功能的类和接口组成，其中最主要的是 java.security 包，此软件包包含的是一组核心的类和接口，Java 中数字签名的方法就集中在此软件包中。JCE(Java Cryptography Extension) 在 JCA 的基础上作了扩展，JCE 也是由几个软件包组成，其中最主要的是 javax.crypto 包，此软件包提供了 JCE 加密技术操作 API。javax.crypto 中的 Cipher 类用于具体的加密和解密。在上述软件包的实现中，集成了应用 RSA 算法的各种数据加密规范(RSA 算法应用规范介绍参见： http://www.rsasecurity.com/rsalabs/node.asp?id=2146 ，这些 API 内部支持的算法不仅仅只有 RSA，但是 RSA 是数字签名和证书中最常用的)，用户程序可以直接使用 java 标准库中提供的 API 进行数字签名和证书的各种操作。单机应用程序使用 RSA 加密尚比较少见，例如使用 RSA 加密任意一个文件。 RSA 算法可以简单叙述如下： <密钥生成> 取素数 p，q，令 n=p×q. 取与(p-1)×(q-1)互素的整数 e，由方程 d×e=1 (mod (p-1)×(q-1))解出 d，二元组(e,n)作为公开密钥，二元组(d,n)作为私有密钥． <加密解密> b=ae mod n，c=bd mod n. 2.算法原理 1．选择两个不同的大素数 p、q(目前两个数的长度都接近 512bit 是安全的）； 2. 计算 n = p*q。 3. 计算 n 的欧拉函数 t=(p-1)(q-1)。

4. 选择整数 e 作为公钥，使 e 与 t 互素，且 1

每一个整数 a，它的模 n 剩余是从 0 到 n-1 之间的某个整数。所谓运算 a mod n 表示求 a 被 n 除的余数，成为模运算。既约剩余系(Reduced Set of Residues)：在模 n 的完全剩余系中，若将所有与 n 互素的剩余类形成一个集合，则称此集合为模 n 的既约剩余系，以 Zn 表示。例如 n=10 时，{0，1，2，3，4，5，6，7，8，9)为模 10 的完全剩余系；而{1， 3，7，9)为模 10 的既约剩余系。 3.3 欧拉函数、欧拉定理和费尔马定理欧拉函数≯(n)：是一个定义在正整数上的函数，其值等于序列 0，1，2，3，…… n-1 中与 n 互素的数的个数。即 fn 为模 n 既约剩余系中所有元素的个数。由定义知，当 P 是素数时，≯ (p)=P-1。定理2．1 欧拉定理：若m，a 为正整数，有g c d(a，m)=l(g c d，Greatest Common Divisor，最大公约数)，则 a≯(m) (mod m)。其中≯m 称为欧拉函数，它是比 m 小但与 m 互素的正整数个数。欧拉定理也有一种等价形式：a≯(m)+1 =a(mod m)。定理 2．2 设 P 和 q 是两个不同的素数，n=p×q，则≯(n)=(p-1)×(q-1)，对任意的 x∈Zn 及任意的非负整数 k，有 x k≯(n)+1≡x (mod n)。定理 3 费尔马定理：如果 P 是素数，且 g c d(m ,p)=l(可表示为(m , p)=1)，则 mp-1≡l(mod p)，费尔马定理还存在另一种等价形式：如果 P 是素数，m 是任意正整数，则 mp≡m(mod p)。对于素数 P 来说，≯ (p)=p-1，所以费尔马定理实际是欧拉定理的一个推论。费尔马定理和欧拉定理及其推论在构成了 RSA 算法的主要理论基础。 3.4 乘法逆元及其求法乘法逆元的定义：若 a b≡l(mod n)，则称 b 为 a 在模 n 的乘法逆元，b 可表利用 Euclid(欧几里德)算法(辗转相除法)求乘法逆元：己知 a 及 n 且(a ,n) =1，示为 a-1。求 a a –l=1(mod n)。欧几里德算法是古希腊数学家欧几里德给出的求两个自然数的最大公约数的方法，如果(a，n)=1，则 b 一定存在。首先介绍利用欧几里德算法求 g c d(a， n)的方法，再介绍求乘法逆元的方法。令 r0=n，r l=a，a≤n，利用辗转相除法可得 r0=r1+g1+r2 r1=r2g2+r3 0≤r2< r l 0≤r3

因为(1001，3837)=l，而 3837=3×1001+834 1001=1×834+1 67 834=4×167+166 167=1 ×166+1 所以 l=167—166=167--(834--4×167)=5×167—834 =5×(1001—834)一 834 =5×1001--6×834 =5×1001--6×(3837—3×1001) =23× 1001--6×3837 因此 23×1001≡l(mod 3837)，故 1001 关于模 3837 的乘法逆元为 23。一般求乘法逆元以欧几里德算法为佳。 4.RSA 算法的各环节 RSA 算法是 1978 年由 R.L.Rivest，A.Shamir 和 L.Adleman 提出的一种用数论构造的、也是迄今为止理论上最为成熟完善的公钥密码体制。RSA 的理论基础是数论中的欧拉定理,它的的安全性依赖于大数的因子分解，但并没有从理论上证明破译 RSA 的难度与大数分解难度等价。 4.1 RSA 公钥加密解密概述 RSA 算法采用下述加密/解密变换。 1．密钥的产生 ①选择两个保密的大素数 P 和 q。 ②计算 N=p q，≯(N) =(p-1)(g-1)，其中≯(N)是 N 的欧拉函数值。 ③选择一个整数 e，满足 l

验证过程：接收方使用发送方的公钥 e 对收到的消息 y 进行数字签名验证变换 x’=ye mod N，并使用发送方的密钥解密恢复消息 x，比较 x’与 x，如果 x’ =x 则证实发送方的身份合法。这样，用户 A 若想用 RSA 签名方案对消息 x 签名，他只需公开他的公钥 N 和 e，由于签名算法是保密的，因此 A 是唯一能产生签名的人，任何要验证用户 A 签名的用户只需查到 A 的公钥即可验证签名。对于实现签名和公钥加密的组合，常用方法是：假定通信双方为 A 和 B。对于明文 x，A 计算他的签名 y=x d mod N，然后利用 B 的公开加密函数 EB 对信息对(x, y)加密得到 Z，将密文 Z 传送给 B，当 B 收到密文 Z 后，他首先用他的解密函数 DB 来解密得到(x，y)=DB (Z)= DB (EB(x，y))，然后利用 A 的验证算法来检查 x’=x=y e mod N 是否成立。 4.3 大数运算处理． RSA 依赖大数运算，目前主流 RSA 算法都建立在 1024 位的大数运算之上。而大多数的编译器只能支持到 64 位的整数运算，即我们在运算中所使用的整数必须小于等于 64 位，即：0xffffffffffffffff 也就是 18446744073709551615，这远远达不到 RSA 的需要，于是需要专门建立大数运算库来解决这一问题。最简单的办法是将大数当作数组进行处理，数组的各元素也就是大数每一位上的数字，通常采用最容易理解的十进制数字 0~9。然后对“数字数组”编写加减乘除函数。但是这样做效率很低，因为二进制为 1024 位的大数在十进制下也有三百多位，对于任何一种运算，都需要在两个有数百个元素的数组空间上多次重循环，还需要许多额外的空间存放计算的进退位标志及中间结果。另外，对于某些特殊的运算而言，采用二进制会使计算过程大大简化，而这种大数表示方法转化成二进制显然非常麻烦，所以在某些实例中则干脆采用了二进制数组的方法来记录大数，当然这样效率就更低了。一个有效的改进方法是将大数表示为一个 n 进制数组，对于目前的 32 位系统而言 n 可以取值为 2 的 32 次方，即 0x100000000，假如将一个二进制为 1024 位的大数转化成 0x10000000 进制，就变成了 32 位，而每一位的取值范围不再是二进制的 0~ 1 或十进制的 0~9，而是 0~0xffffffff 我们正好可以用一个 32 位的 DWORD(如：无符号长整数，unsigned long)类型来表示该值。所以 1024 位的大数就变成一个含有 32 个元素的 DWORD 数组，而针对 DWORD 数组进行各种运算所需的循环规模至多 32 次而已。例如大数 1 8446744073709551 61 5，等于 0Xffffffff ffffffff 其表示方式就相当于十进制的 99：有两位，只是每位上的元素不是 9 而都是 0xffffffff。而 18446744073709551616 等于 0x00000001 00000000 00000000，就相当于十进制的 100：有三位，第一位是 l，其它两位都是 0，如此等等。在实际应用中，“数字数组"的排列顺序采用低位在前高位在后的方式，这样，大数 A 就可以方便地用数学表达式来表示其值： X=ΣXi r i (r=0x100000000，0

根据 RSA 算法的加解密变换，需要产生两个保密的大素数作为基础运算。在 2000 年前欧几里德证明了素数有无穷多个，这自然的就引出一个问题：既然素数有无穷个，那么是否有一个计算素数的通项公式?两千年来，数论学的一个重要任务，就是寻找一个可以表示全体素数的素数普遍公式。为此，人类耗费了巨大的心血。希尔伯特认为，如果有了素数统一的素数普遍公式，那么这些哥德巴赫猜想和孪生素数猜想都可以得到解决。“研究各种各样的素数分布状况，一直是数论中最重要和最有吸引力的中心问题之一。关于素数分布性质的许多著名猜想是通过数值观察计算和初步研究提出的，大多数至今仍未解决”。因此，欲得到素数，必须另寻出路。大素数的产生应是现代密码学应用中最重要的步骤。几乎所有的公开密钥系统均需要用到大的素数，若此素数选用不当，则此公开密钥系统的安全性就岌岌可危。一般而言，素数的产生通常有两种方法，一为确定性素数产生方法，一为概率性素数产生方法，目前后者是当今生成素数的主要方法。所谓概率性素数产生法，是指一种算法，其输入为一奇数，输出为两种状态 YES 或 NO 之一。若输入一奇数 n，输出为 NO，则表示 11 为合数，若输出为 YES，则表示 n 为素数的概率为 1-r，其中 r 为此素数产生法中可控制的任意小数，但不能为 0。此类方法中较著名的有 Solovay-Strassen 算法、Lehmann 算法、Miller-Rabin 算法等。在实际应用中，一般做法是先生成大的随机整数，然后通过素性检测来测试其是否为素数。数论学家利用费尔马定理研究出了多种素数测试方法，目前最快的算法是 Miller-Rabin(拉宾米勒)测试算法(也称为伪素数检测)，其过程如下：首先选择一个待测的随机数 N 计算 r，2r 是能够整除 N-1 的 2 的最大幂数。 1．计算 M，使得 N=2r×M+1。 2．选择随机数 A

地说，RSA 的安全性基于求解其单向函数的逆的困难性。RSA 单向函数求逆的安全性没有真正因式分解模数的安全性高，而且目前人们也无法证明这两者等价。许多研究人员都试图改进 RSA 体制使它的安全性等价于因式分解模数。对 RSA 算法的攻击主要有以下几种： 1．对分解模数 N 的攻击分解模数 N 是最直接也是最显然的攻击目标，同时也是最困难的。攻击者可以合法的获得公开密钥 e 和模数 N；如果 N=p q 被因式分解，则攻击者通过 p、 q 便可计算出≯(N)=(p-1)(q-1)，进而 e d≡l(mod ≯(N))而得到解密密钥 d，大整数分解研究一直是数论与密码理论研究的重要课题。 2．对 RSA 的选择密文攻击选择密文攻击是攻击者对 RSA 等公钥算法最常用的攻击，也是最有效的攻击手段之一。选择密文攻击通常是由 RSA 加密变换的性质诱发的，常见的对 RSA 的选择密文攻击有三种： ①明文破译。攻击者获得某用户 A 使用公钥 e 加密的密文 y=x e (mod n)，并试图恢复出消息 x。随机选取 r

分享到：

赞收藏

资料库

RSA算法的C++实现课程设计报告.doc

相关推荐

安全技术

热门标签

最新资料