《用实例给新手讲解RSA加密算法》由会员分享,可在线阅读,更多相关《用实例给新手讲解RSA加密算法(3页珍藏版)》请在金锄头文库上搜索。
1、RSA 加密算法是最常用的非对称加密算法,CFCA 在证书服务中离不了它。但是有不少新来的同事对它不太了解,恰好看到一本书中作者用实例对它进行了简化而生动的描述,使得高深的数学理论能够被容易地理解。我们经过整理和改写特别推荐给大家阅读,希望能够对时间紧张但是又想了解它的同事有所帮助。RSA 是第一个比较完善的公开密钥算法,它既能用于加密,也能用于数字签名。RSA 以它的三个发明者 Ron Rivest, Adi Shamir, Leonard Adleman 的名字首字母命名,这个算法经受住了多年深入的密码分析,虽然密码分析者既不能证明也不能否定 RSA 的安全性,但这恰恰说明该算法有一定的可
2、信性,目前它已经成为最流行的公开密钥算法。RSA 的安全基于大数分解的难度。其公钥和私钥是一对大素数(100 到 200 位十进制数或更大)的函数。从一个公钥和密文恢复出明文的难度,等价于分解两个大素数之积(这是公认的数学难题) 。 RSA 的公钥、私钥的组成,以及加密、解密的公式可见于下表:可能各位同事好久没有接触数学了,看了这些公式不免一头雾水。别急,在没有正式讲解 RSA 加密算法以前,让我们先复习一下数学上的几个基本概念,它们在后面的介绍中要用到:一、 什么是“素数”?素数是这样的整数,它除了能表示为它自己和 1 的乘积以外,不能表示为任何其它两个整数的乘积。例如,1535,所以 15
3、 不是素数;又如,126243,所以 12 也不是素数。另一方面,13 除了等于 131 以外,不能表示为其它任何两个整数的乘积,所以 13 是一个素数。素数也称为“质数” 。二、什么是“互质数” (或“互素数” )?小学数学教材对互质数是这样定义的:“公约数只有 1 的两个数,叫做互质数。 ”这里所说的“两个数”是指自然数。判别方法主要有以下几种(不限于此):(1)两个质数一定是互质数。例如,2 与 7、13 与 19。(2)一个质数如果不能整除另一个合数,这两个数为互质数。例如,3 与 10、5 与 26。(3)1 不是质数也不是合数,它和任何一个自然数在一起都是互质数。如 1 和 990
4、8。(4)相邻的两个自然数是互质数。如 15 与 16。(5)相邻的两个奇数是互质数。如 49 与 51。(6)大数是质数的两个数是互质数。如 97 与 88。(7)小数是质数,大数不是小数的倍数的两个数是互质数。如 7 和 16。(8)两个数都是合数(二数差又较大) ,小数所有的质因数,都不是大数的约数,这两个数是互质数。如357 与 715,357=3 717,而 3、7 和 17 都不是 715 的约数,这两个数为互质数。等等。三、什么是模指数运算? 指数运算谁都懂,不必说了,先说说模运算。模运算是整数运算,有一个整数 m,以 n 为模做模运算,即 m mod n。怎样做呢?让 m 去被
5、 n 整除,只取所得的余数作为结果,就叫做模运算。例如,10 mod 3=1;26 mod 6=2;28 mod 2 =0 等等。 模指数运算就是先做指数运算,取其结果再做模运算。如好,现在开始正式讲解 RSA 加密算法。算法描述:(1)选择一对不同的、足够大的素数 p,q。(2)计算 n=pq。(3)计算 f(n)=(p-1)(q-1),同时对 p, q 严加保密,不让任何人知道。(4)找一个与 f(n)互质的数 e,且 1ef(n)。(5)计算 d,使得 de1 mod f(n) 。这个公式也可以表达为 d e-1 mod f(n)这里要解释一下,是数论中表示同余的符号。公式中,符号的左边
6、必须和符号右边同余,也就是两边模运算结果相同。显而易见,不管 f(n)取什么值,符号右边 1 mod f(n)的结果都等于 1;符号的左边 d 与 e的乘积做模运算后的结果也必须等于 1。这就需要计算出 d 的值,让这个同余等式能够成立。(6)公钥 KU=(e,n),私钥 KR=(d,n)。(7)加密时,先将明文变换成 0 至 n-1 的一个整数 M。若明文较长,可先分割成适当的组,然后再进行交换。设密文为 C,则加密过程为: 。(8)解密过程为: 。 实例描述:在这篇科普小文章里,不可能对 RSA 算法的正确性作严格的数学证明,但我们可以通过一个简单的例子来理解 RSA 的工作原理。为了便于
7、计算。在以下实例中只选取小数值的素数 p,q,以及 e,假设用户 A需要将明文“key”通过 RSA 加密后传递给用户 B,过程如下:(1)设计公私密钥(e,n)和(d,n)。令 p=3,q=11,得出 n=pq=311=33;f(n)=(p-1)(q-1)=210=20;取 e=3, (3 与 20 互质)则 ed1 mod f(n),即 3d1 mod 20。d 怎样取值呢?可以用试算的办法来寻找。试算结果见下表:通过试算我们找到,当 d=7 时, ed1 mod f(n)同余等式成立。因此,可令 d=7。从而我们可以设计出一对公私密钥,加密密钥(公钥)为:KU =(e,n)=(3,33)
8、,解密密钥(私钥)为:KR =(d,n)=(7,33) 。(2)英文数字化。将明文信息数字化,并将每块两个数字分组。假定明文英文字母编码表为按字母顺序排列数值,即:则得到分组后的 key 的明文信息为:11,05,25。(3)明文加密 用户加密密钥(3,33) 将数字化明文分组信息加密成密文。由 CMe(mod n)得:因此,得到相应的密文信息为:11,31,16。(4)密文解密。用户 B 收到密文,若将其解密,只需要计算 ,即:用户 B 得到明文信息为:11, 05,25。根据上面的编码表将其转换为英文,我们又得到了恢复后的原文“key” 。 你看,它的原理就可以这么简单地解释!当然,实际运
9、用要比这复杂得多,由于 RSA 算法的公钥私钥的长度(模长度)要到 1024 位甚至2048 位才能保证安全,因此,p、q、e 的选取、公钥私钥的生成,加密解密模指数运算都有一定的计算程序,需要仰仗计算机高速完成。最后简单谈谈 RSA 的安全性首先,我们来探讨为什么 RSA 密码难于破解? 在 RSA 密码应用中,公钥 KU 是被公开的,即 e 和 n 的数值可以被第三方窃听者得到。破解 RSA 密码的问题就是从已知的 e 和 n 的数值(n 等于 pq) ,想法求出 d 的数值,这样就可以得到私钥来破解密文。从上文中的公式:d e-1 (mod(p-1)(q-1)或 de1 (mod(p-1
10、)(q-1) 我们可以看出。密码破解的实质问题是:从 Pq 的数值,去求出 (p-1)和(q-1)。换句话说,只要求出 p 和 q 的值,我们就能求出 d 的值而得到私钥。当 p 和 q 是一个大素数的时候,从它们的积 pq 去分解因子 p 和 q,这是一个公认的数学难题。比如当 pq 大到 1024 位时,迄今为止还没有人能够利用任何计算工具去完成分解因子的任务。因此,RSA 从提出到现在已近二十年,经历了各种攻击的考验,逐渐为人们接受,普遍认为是目前最优秀的公钥方案之一。然而,虽然 RSA 的安全性依赖于大数的因子分解,但并没有从理论上证明破译 RSA 的难度与大数分解难度等价。即 RSA 的重大缺陷是无法从理论上把握它的保密性能如何。此外,RSA 的缺点还有:A)产生密钥很麻烦,受到素数产生技术的限制,因而难以做到一次一密。B)分组长度太大,为保证安全性,n 至少也要 600 bits 以上,使运算代价很高,尤其是速度较慢,较对称密码算法慢几个数量级;且随着大数分解技术的发展,这个长度还在增加,不利于数据格式的标准化。因此,使用 RSA 只能加密少量数据,大量的数据加密还要靠对称密码算法。