毕业设计（论文）-非对称密码学加密算法的研究与设计――RSA算法的程序设计、 .doc

目目 录录 设计总说明.3 introduction 5 前 言.8 1 密码学的概述.9 1.1 密码学的基本术语9 1.1.1 密码学.9 1.1.2 密钥.9 1.1.3 加密与解密.10 1.1.4 密码体制.10 1.1.5 鉴别、完整性和抗抵赖.10 1.2 密码学的应用.11 1.3 密码算法的概念及其分类.11 1.3.1 对称密码算法.11 1.3.2 公开密钥算法.12 1.3.3 hash 算法12 1.4 密码编码学的基本概念.13 1.5 密码分析学的基本概念.13 1.6 密码学的信息论基础.14 1.7 密码学的起源和发展.14 1.8 密码算法的安全性.15 2 公钥密码体制基础.16 2.1 整数算法16 2.1.1 二进制运算.16 2.1.2 整数除法.16 2.1.3 整除性.16 2.2 模运算.18 非对称密码学加密算法的研究与设计rsa 算法的程序设计 第2页共63页 2.2.1 模算符.18 2.2.2 余集：zn18 2.2.3 同余.19 2.2.4 在集合 zn 当中的运算19 2.2.5 逆.20 2.2.6 加法集和乘法集的不同.21 2.2.7 另外两个集合.21 2.3 素数.22 2.3.1 定义22 2.3.2 素数的基数22 2.3.3 素性检验22 2.3.4 euler phi-(欧拉(n)函数.23 2.3.5 fermat(费尔马)小定理23 2.3.6 生成素数25 2.4 素性测试.25 2.4.1 确定性算法.25 2.4.2 概率算法.26 2.4.3 推荐的素性检验.28 2.5 因数分解.29 2.5.1 算术基本定理.29 2.5.2 因数分解方法.29 2.5.3 fermat 方法.30 2.6 中国剩余定理.30 2.7 指数与对数.30 2.7.1 指数31 2.7.2 对数.31 2.8 分治法基本思想31 3 rsa 密码系统33 3.1 rsa 简介 33 华北科技学院毕业论文 第3页共63页 3.2 单向函数.33 3.3 rsa 的加解密过程及算法分析 34 3.4 rsa 的安全性分析 37 3.4.1 针对 rsa 的攻击.37 3.4.2 因数分解攻击.37 3.4.3 选择密文攻击.38 3.4.4 对加密指数的攻击.38 3.4.5 对解密指数的攻击.39 3.4.6 明文攻击.39 3.4.7 对模的攻击.40 3.4.8 执行攻击.41 3.5 使用 rsa 的意义.42 4 rsa 的 c 程序实现.43 4.1 rsa 编程设计 43 4.2rsa 源程序.49 4.3 结束语.59 参考文献.60 致谢.61 非对称密码学加密算法的研究与设计rsa 算法的程序设计 第4页共63页 设计总说明设计总说明 密码学是信息安全的重要技术，是用于保护国家机密及决策的一个重要工具， 也是保护个人信息以及其他重要资料的重要方法。可以有效保障信息的机密性、完 整性和鉴别。密码学的研究涉及到很多技术的学习，主要包括怎样把数据加密，怎 样传送加密数据，怎样解密加密的数据，使需要数据的合法者得到自己要的数据。 密码学是研究编制密码和破译密码的技术科学。密码学一般包括两个对立统一的 分支学科：密码编码学和密码分析学。密码编码学与密码分析学相辅相成，共处于密 码学的统一体中。现代密码学除了包括密码编码学和密码分析学两个主要的学科外， 还包括一个新产生的分支密码密钥学。它是以密码体系最核心部分的密钥作为研 究对象的学科。密钥管理是一种规程，它包括密钥的产生、分配、存储、保护、销毁 等环节。上述三个分支学科构成了现代密码学的主要科学体系。 公开密钥密码体制是现代密码学的最重要的发明和进展。对信息发送与接收人 的真实身份的验证、对所发出 /接收信息在事后的不可抵赖以及保障数据的完整性 是现代密码学主题的另一方面。 公钥密码算法最主要的特点是加密和解密使用不同 的密钥（公钥和私钥） ，且加密密钥能公开，而仅需保守解密密钥的机密的密码算法。 公开密钥与私有密钥是一对，如果用公开密钥对数据进行加密，只有用对应的私有 密钥才能解密；如 果用私有密钥对数据进行加密，那么只有用对应的公开密钥才能 解密。在这种加密算法中，从公开的加密密钥无法推导出保密的解密密钥，也无法从 加密密钥和密文恢复出相应的明文。最有影响的公钥密码算法是 rsa，它能抵抗到目 前为止己知的所有密码攻击。在公钥体制中，加密密钥不同于解密密钥。人们将加 密密钥公之于众，谁都可以使用；而解密密钥只有解密人自己知道。迄今为止的所 有公钥密码体系中， rsa 系统是最著名、使用最广泛的一种。 非对称密码体制的特点：算法强度复杂、安全性依赖于算法与密钥但是由于其 算法复杂，而使得加密解密速度没有对称加密解密的速度快。对称密码体制中只有 一种密钥，并且是非公开的，如果要解密就得让对方知道密钥。所以保证其安全性 就是保证密钥的安全，而非对称密钥体制有两种密钥，其中一个是公开的，这样就 可以不需要像对称密码那样传输对方的密钥了。这样安全性就大了很多。 本课题主要研究加密算法中的非对称密码加密算法 rsa。对密码学做了简单的介 绍，着重介绍了公钥密码体制的基本知识：如二进制运算、整数除法、模运算、欧拉 华北科技学院毕业论文 第5页共63页 函数、费尔马小定理、欧几里德算法、概率算法、推荐的素性检验；算术基本定理、 中国剩余定理、分治法基本思想。并分析 rsa 加解密过程及算法实现；针对 rsa 的 攻击做简要分析，如因数分解攻击、选择密文攻击、对加密指数的攻击、对解密指数 的攻击、明文攻击、对模的攻击、执行攻击；rsa 加密算法的优缺点分析。根据理论 基础设计 rsa 算法的程序，并在 vc6.0 软件平台下实现 rsa 算法的加密解密。 rsa 算法是第一个既能用于数据加密也能用于数字签名的算法，算法的名字以发 明者的名字命名。算法中使用的公钥和私钥都是两个大素数（大于 100 个十进制位） 的函数。据猜测，从一个密钥和密文推断出明文的难度等同于分解两个大素数的积。 先选择两个大素数 p 和 q（） ，且。计算：n=p*q 然后随机 16 2265536pq、pq 选择加密密钥 e，要求 e 和(p-1)*(q-1)互质。最后，利用 euclid 算法计算解密密钥 d,满 足 e*d=1(mod(p-1)*(q-1)其中 n 和 d 也要互质。数 e 和 n 是公钥，d 是私钥。两个素数 p 和 q 不再需要，应该丢弃，不要让任何人知道。加密信息 m 时，首先把 m 分成等长 数据块 m1，m2，mi，块长 s，其中 2s(a/b)*y； return n； (5)对每一个密钥 k=(n，p，q，d，e)，定义加密变换为 y=ek(x)=xemodn，解密变 换为 dk(x)=ydmod n，这里 x，yzn。这里我们要用到模取幂运算。 事实上，可以直接计算，没有必要先算 me，那样肯定不行，计算量将mod e mn 很大。叫做模取幂运算，根据简单的数论知识，可以设计一个分治算法。具mod e mn 体如下： 设是整数 b 的二进制表示（即 b 的二进制有 k+1 位， bk是最高位） ，下列过程随着 c 的值从 0 到 b 成倍增加，最终计算出。mod c an modular-exponentiation(a, b, n) 1. c 0 2. d 1 3. 设 是 b 的二进制表示 4. for ik downto 0 5. do c 2c 6. d (d*d) mod n 7. if bi = 1 8. then c c + 1 9. d (d*a) mod n 10. return d 非对称密码学加密算法的研究与设计rsa 算法的程序设计 第38页共63页 首先说明一下，上述伪代码中用缩紧表示语句之间的层次关系，例如第 59 行都 是 for 循环体内的语句，第 89 行都是 then 里面的语句。这是我比较喜欢的一种表示 方法。上述伪代码依次计算出的每个幂或者是前一个幂的两倍，或者比前一个幂大 1。 过程依次从右到左逐个读入 b 的二进制表示已控制执行哪一种操作。循环中的每次迭 代都用到了下面的两个恒等式中的一个： 。 22 mod(mod ) cc anan 。 212 mod(mod ) cc ana an 用哪一个恒等式取决于 bi=0 还是 1。由于平方在每次迭代中起着关键作用，所以 这种方法叫做“反复平方法” 。在读入 bi位并进行相应处理后，c 的值与 b 的二进制 表示的前缀的值相同。事实上，算法中并不真正需要变量 c，只是为 了说明算法才设置了变量 c：当 c 成倍增加时，算法保持条件不变，直至mod c dan c=b。 (6)将e，n作为公开密钥，d，n作为私有密钥。 3.4 rsa 的安全性分析的安全性分析 3.4.1 针对针对 rsa 的攻击的攻击 还没有发现针对 rsa 的破坏性攻击。已经预言了几种基于弱明文、弱参数选择或 不当执行的攻击。图就是这些潜在攻击的分类。 华北科技学院毕业论文 第39页共63页 针对 rsa 的 潜在攻击 因数分解 选择密文 加密指数 解密指数 明文 模 执行 针对 rsa 潜在攻击的分类 3.4.2 因数分解攻击因数分解攻击 rsa 的安全性基于这么一种想法，那就是模要足够大以至于在适当的时间内把它 分解是不可能的。收信者选择 p 和 q，并且计算出 n=pq。虽然 n 是公开的，但 p 和 q 是保密的。如果攻击者能分解 n 并获得 p 和 q，她就可以计算出 f(n)=(pq。然 后，因为 e 是公开的，攻击者还可以计算出。私密指数 d 是攻击者可以 1 mod ( )den 用来对任何加密信息进行解密的暗门。 有许多种因数分解算法，但是没有一种可以分解带有多项式时间复杂度的大整数。 为了安全，目前的 rsa 要求 n 必须大于 300 个十进制数位，这就是说模必须最小是 1024 比特【5】。即使运用现在最大最快的计算机，分解这么大的整数所要花费的时间也 是不可想象的。这就表明只要还没有发现更有效的因数分解算法，rsa 就是安全的。 3.4.3 选择密文攻击选择密文攻击 针对 rsa 的潜在攻击都基于 rsa 的乘法特性，我们假定发信者创建了密文： 并且把 c 发送给收信者。我们也假定收信者要对攻击者的任意密文解密，mod e cmn 而不是只解密 c。攻击者拦截 c 并运用下列步骤求出 m： (1) 攻击者选择 zn*中的一个随机整数 x。 (2) 攻击者计算出。mod e ycxn 非对称密码学加密算法的研究与设计rsa 算法的程序设计 第40页共63页 (3) 为了解密攻击者把 y 发送给收信者并得到；这个步骤就是选择密mod d zyn 文攻击的一个例子。 (4) 攻击者能够很容易地得到 m，因为 mod() mod()mod()mod()mod deddedd zyncxncxncxnmxn 1 ()modmodzmxnmzxn 攻击者运用扩展的欧几里得算法求 x 的乘法逆，并最终求得 m。 3.4.4 对加密指数的攻击对加密指数的攻击 为了缩短加密时间，使用小的加密指数 e 是非常诱人的。普通的 e 值是 e=3。不过 有几种针对低加密指数的潜在攻击，在这里我们只作简单的讨论。这些攻击一般不会 造成系统的崩溃，不过还是得进行预防。为了阻止这些类型的攻击，我们推荐使用 e=216+1=65537(或者一个接近这个值的素数)。 主低加密指数攻击称为 coppersmith 定理攻击。该项定理表明在一个 e 阶的 mod n 多项式 f(x)中，如果有一个根小于 n1/e，就可以运用一个复杂度 log n 的算法求出这些 根【5】。这个定理可以应用于的 rsa 密码系统。如果 e=3 并且在明( )mod e cf mmn 文当中只有三分之二的比特是已知的，这种算法可以求出明文中所有的比特。 如果一个实体使用相同的低加密指数给一个接收者的群发送相同的信息，就会发 动广播攻击。例如，假设有如下的情节：发信者要使用相同的公共指数 e=3 和模 n1、n2 和 n3 给三个接收者发送相同的信息。 3 111 modcmn 3 222 modcmn 3 333 modcmn 对这些等式运用中国剩余定理，攻击者就可以求出形式的等式。 3 123 modcmn n n 这就表明 m3n1n2n3。也表明 c=m3是在规则算法中(不是模算法)。攻击者可以求出 的值。 1/3 cm 相关信息攻击是由 franklin reiter 提出来的，下面我们就简单描述一下这种攻击。 发信者用 e=3 加密两个明文 m1和 m2，然后再把 c1和 c2发送给收信者。如果通过一个 线性函数把 m1和 m2联系起来，那么攻击者就可以在一个可行的计算时间内恢复 m1 和 m2。 华北科技学院毕业论文 第41页共63页 短填充攻击是由 coppersmith 提出来的，下面我们就简单描述一下这种攻击。发信 者有一条信息 m 要发送给收信者。她先用 r1对信息填充，加密的结果是得到了 c1，并 把 c1发送给收信者。攻击者拦截 c1并把它丢掉。收信者通知发信者他还没有收到信息， 所以发信者就再次使用 r2对信息填充，加密后发送给收信者。攻击者又拦截了这一信 息。攻击者现在有 c1和 c2，并且她知道 c1和 c2都是属于相同明文的密文。coppersmith 证明如果 r1和 r2都是短的，攻击者也许就能恢复原信息 m【5】。 3.4.5 对解密指数的攻击对解密指数的攻击 可以对解密指数发动攻击的两种攻击方式就是：暴露解密指数攻击和低解密指数 攻击。我们简单讨论一下这两种攻击。 如果攻击者可以求出解密指数 d，她就可以对当前加密的信息进行解密。不过，到 这里攻击并还没有停止。如果攻击者知道 d 的值，她就可以运用概率算法(这里不讨论) 来对 n 进行因数分解，并求出 p 和 q 值。因此，如果收信者只改变了泄露解密指数但 保持模 n 相同，因为攻击者有 n 的因数分解，所以她就可以对未来的信息进行解密。 这就是说，如果收信者发现解密指数已经泄露，他就要有新的 p 和 q 的值还要计算出 n，并创建所有新的公钥和私钥。因此在 rsa 中，如果 d 已经泄露，那么 p、q、n、e 和 d 就必须要重新生成。 低解密指数攻击，收信者也许会想到，运用一个小的私钥 d 就会加快解密的过程。 wiener 表示如果，一种基于连分数(一个数论当中的问题)的特殊攻击类型就可 1/4 dn 以危害 rsa 的安全【5】。要发生这样的事情，必须要有 q是整数 b 的二进制表示（即 b 的二进制有 k+1 位，bk是最高位） 0;1cd 开始 0ik 2 ;modcc dddn 是 1?b i 是 1cc modddan mod e mnd 结束 否 4.2rsa 源程序源程序 #include #include 华北科技学院毕业论文 第51页共63页 using namespace std; /rsa 算法所需参数 typedef struct rsa_param_tag unsigned _int64 p, q; /两个素数，不参与加密解密运算 unsigned _int64 f; /f=(p-1)*(q-1)，不参与加密解密运算 unsigned _int64 n, e; /公匙，n=p*q，gcd(e,f)=1 unsigned _int64 d; /私匙，e*d=1 (mod f)，gcd(n,d)=1 unsigned _int64 s; /块长，满足 2s=1; /a=a * a % n; /函数看起来可以处理 64 位的整数，但由于 这里 a*a 在 a=232 时已经造成了溢出，因此实际处理范围没有 64 位 a=mulmod(a, a, n); b-; /c=a * c % n; /这里也会溢出，若把 64 位整数拆为两 个 32 位整数不知是否可以解决这个问题。 c=mulmod(a, c, n); return c; /*rabin-miller 素数测试，通过测试返回 1，否则返回 0。n 是待测素数。注意：通 过测试并不一定就是素数，非素数通过测试的概率是 1/4*/ long rabinmillerknl(unsigned _int64 m = n - 1; j = 0; /0、先计算出 m、j，使得 n-1=m*2j，其中 m 是正奇数，j 是非负整数 while(!(m m = 1; /m 除以 2 /1、随机取一个 b，2 q ? p : q;/选择大的 unsigned _int64 b = p = 1; b = 1; if(!(a /如果 a 为偶数，交换 a，b a = b; b = t; do while(!(b /b 为偶数，a 为奇数时，(b,a)=(b/2,a) if(b 1; /b、a 都是奇数，(b,a)=(b-a)/2,a) while(b); 华北科技学院毕业论文 第57页共63页 return r * a; /*欧几里得算法已知 a、b，求 x，满足 a*x =1 (mod b)相当于求解 a*x-b*y=1 的最 小整数解*/ unsigned _int64 euclid(unsigned _int64 long xx, yy; m = b; e = a; x = 0; y = 1; xx = 1; yy = 1; while(e) i = m / e; j = m % e; m = e; e = j; j = y; y *= i; if(xx = yy) if(x y) y = x - y; else 非对称密码学加密算法的研究与设计rsa 算法的程序设计 第58页共63页 y -= x; yy = 0; else y += x; xx =1 - xx; yy =1 - yy; x = j; if(xx = 0) x = b - x; return x; /*随机产生一个 rsa 加密参数*/ rsa_param rsagetparam(void) rsa_param rsa= 0 ; unsigned _int64 t; rsa.p=randomprime(16); /随机生成两个素数 p rsa.q=randomprime(16); /生成随机素数 q rsa.n=rsa.p * rsa.q; /计算 n rsa.f=(rsa.p - 1) * (rsa.q - 1); /计算 f do 华北科技学院毕业论文 第59页共63页 rsa.e = g_rnd.random(65536); /随机生成 e /小于 216，65536=216 rsa.e |= 1;/保证最低位是 1，即保证是奇数， while(steingcd(rsa.e, rsa.f) != 1); /测试 e rsa.d=euclid(rsa.e, rsa.f); /欧几里得法生成 d rsa.s=0; t=rsa.n 1; while(t) rsa.s+; /s=log2(n) t=1; return rsa; /*rsa 加密解密*/ void testrsa(void) rsa_param r; char psrc=“刘永海的毕业论文程序！tanks everone“; /待加密的数据 const unsigned long n=sizeof(psrc); unsigned char *q, pdecn; unsigned _int64 pencn; unsigned long i; int j = 0; r=rsagetparam(); /获得参数 p,q,f,n,d,e,s printf(“p=%dn“,r.p); printf(“q=%dn“,r.q); printf(“f=(p-1)*(q-1)=%dn“,r.f); printf(“n=p*q=%dn“,r.n); printf(“e=%dn“,r.e); printf(“d=%dn“,r.d); 非对称密码学加密算法的研究与设计rsa 算法的程序设计 第60页共63页 printf(“s=%dn“,r.s); printf(“原始数据:%sn“,psrc); q= (unsigned char *)psrc; printf(“加密:n“); for(i=0; i n; i+) penci=powmod(unsigned _int64)qi, r.e, r.n); /公钥 e 加密 printf(“ %d “, penci); if (j % 5 = 0) printf(“n“); j+; printf(“n“); printf(“解密:n“); for(i=0; i n; i+) pdeci=(unsigned char)powmod(penci, r.d, r.n); /私钥 d 解密 printf(“ %c “, pdeci); printf(“n“); printf(“%sn“,pdec); int main() testrsa(); return 0; 华北科技学院毕业论文 第61页共63页 运行结果说明：从以上分析可以看出，对加密的密文能正确解密。 4.3 结束语结束语 随着互联网络的迅速发展,网络通信和网络传输对安全性的要求越来越高,这就促 使密码学不断地发展。大批的密码算法的设计者和分析者不断的努力推动着密码学的 进步,涌现了不少优秀的算法。同时这些算法的实现和应用更是一个重要的课题。好的 算法不能仅仅停留在数学逻辑的层面上,投入应用才是更有意义的。 rsa存在一些密码学方面的缺陷，随着数论的发展，一些研究人员正试图找出一 种耗时以多项式方式增长的分解算法。不过目前这还只是展望,，甚至连发展的方向都 还没有找到。有三种事物的发展会威胁到rsa的安全性：分解技术、计算机能力的提 高和计算机造价的降低。特别是第一条对rsa的威胁最大。因为只要大数分解的问题 不解决，做乘法总是比分解因数快得多。专家学者不断在大数分解基础等方面取得了 一些成果，提高了rsa的安全性能。但这些研究成果随着计算机能力的强大，不断受 到威胁。从而使电子商务中的密钥安全问题在一定程度上转化为大数的分解问题，也 成为密码学领域研究的热点之一。 rsa除了用于加解密以外，还有一个很重要的用途就是用于数字签名。这里就简单 非对称密码学加密算法的研究与设计rsa 算法的程序设计 第62页共63页 介绍下就是了。rsa可用于数字签名时，是用私钥计算消息的签名m：，mod d smn 任何人都可以用公钥检验，用检验签名。具体操作时考虑到安全性和m信mod e msn 息量较大等因素，一般是先作hash运算（简单介绍见1.3.3） 。 参考文献参考文献 1 cet in kaya koc. h igh2speed rsa imp lementat ionr.rsa l abo rato ries technique repo rt,1994:rsalabs 2 a selby c, m itchell. a lgo rithm s fo r softw are imp le2mentat ions of rsa c.iee proceed in g,1989 3 【+ 程序设计基础:第 3 版】 周霭如，林伟健编著 电子工业出版社 2010 1 4 【易学 c+】 潘嘉杰编著 人民邮电出版社 2008 5 【密码学与网络安全】 (美) behrouz a. forouaan 著 清华大学出版社 2009 6 【应用密码学:协议、算法与 c 源程序】 (美)b.施奈尔bruce schneier 著 机械工 业出版社 2000 7 【应用密码学手册】 (加)a