内容简介:RSA加密算法是一种其实RSA加密算法最主要的就是两个公式,在理解这两个公式之前需要学习数论中的四个概念:如果两个正整数,除了1以外没有其他公因子,则称这两个数互质,比如6和21的公因子有3和1,所以6和21就不互质;而10和21只有一个公因子1,所以它们互质。
RSA概述
RSA加密算法是一种 非对称加密算法 。在公开密钥加密和电子商业中RSA被广泛使用。RSA是1977年由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的
数论基础
其实RSA加密算法最主要的就是两个公式,在理解这两个公式之前需要学习数论中的四个概念: 互质 、 欧拉函数 、 欧拉定理 、 模反元素
互质
如果两个正整数,除了1以外没有其他公因子,则称这两个数互质,比如6和21的公因子有3和1,所以6和21就不互质;而10和21只有一个公因子1,所以它们互质。 不是质数也可以构成互质关系
只要满足以下几点就可构成互质关系:
- 任意两个质数构成互质关系,比如13和61
- 1和任意一个自然数是都是互质关系,比如1和99
- p是大于1的整数,则p和p-1构成互质关系,比如57和56
- p是大于1的奇数,则p和p-2构成互质关系,比如17和15
- 如果两个数之中,较大的那个数是质数,则两者构成互质关系,比如97和10
- 一个数是质数,另一个数只要不是前者的倍数,两者就构成互质关系,比如3和10
欧拉函数
请问10以内的正整数有哪些与10互质呢?
答案是:{1,3,7,9},10以内用手就可以算的过来,那100呢?1000呢?数字越大越难手算出来,有公式可以计算,就是 欧拉函数
欧拉函数以$\psi(n)$表示。在1到10之中,与10形成互质关系的是{1,3,7,9},所以$\psi(10) = 4$
$\psi(n)$的计算方法并不复杂,推到步骤可以在网上找到,这里只要记住最终结论就行
第一种情况
如果n = 1,则$\psi(1)=1$,因为1与任何数(包括自身)都构成互质关系
第二种情况
如果n是质数,则$\psi(n) = n - 1$。因为质数与小于他的每一个数都构成互质关系。比如5与1、2、3、4都构成互质关系
第三种情况如果n是质数的某一个次方值,即$n = p^k$(p为质数,k为大于等于1的整数),则:
$$
\psi(p^k) = p^k - p^{k-1}
$$
例如,$\psi(8) = \psi(2^3) = 2^3 - 2^2 = 4$
这是因为只有当一个数不包含质数p,才可能与n互质,而包含质数p的数共有$p^{k-1}$个,即$p,2p,3p...p^k$,把他们去除,剩下的就是与n互质的数
上面的式子还可以写成下面的形式:
$$
\psi(p^k) = p^k - p^{k-1} = p^k(1-\frac{1}{p})
$$
可以看出,上面的第二种情况是k=1时的特例
第四种情况
如果n可以分解成两个互质的整数之积$n = p_1 * p_2$,则:
$$
\psi(n) = \psi(p_1p_2) = \psi(p_1)\psi(p_2)
$$
积的欧拉函数等于各个因子的欧拉函数之积。例如,$\psi(56) = \psi(8*7) = \psi(8)*\psi(7)=4*6=24$
第五种情况
因为任意一个大于1的正整数,都可以写成一系列质数的积$n=p^{k_1}_1p^{k_2}_2...p^{k_r}_r$
根据第四条结论,得到:
$$
\psi(n)=\psi(p^{k_1}_1)\psi(p^{k_2}_2)...\psi(p^{k_r}_r)
$$
再根据第三条结论,得到:
$$
\psi(n) = p^{k_1}_{1} p^{k_2}_{2} ... p^{k_r}_{r} (1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_r})
$$
也就等于
$$
\psi(n) = n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_r})
$$
这就是欧拉函数的通用计算公式。比如1323的欧拉函数,计算过程如下
$$
\psi(1323) = \psi(3^3 * 7^2) = 1323(1-\frac{1}{3})(1-\frac{1}{7})=756
$$
欧拉定理
欧拉定理指的是: 如果两个正整数a和n互质,则n的欧拉函数 φ(n) 可以让下面的等式成立:
$$
a^{\psi(n)} \equiv 1(mod\; n)
$$
也就是说,a的$\psi(n)$次方除以n的余数为1。或者说,a的$\psi(n)次方减1可以整除n$。例如,3和7互质,而7的欧拉函数$\psi(7)=6$,所以$(3^6 - 1) / 7 = 728 / 7 = 104$
科普:mod为取模,取模运算与取余运算还是有区别。取余的商靠近0,而取模的商是靠近负无穷的
欧拉定理可以大大简化某些运算。比如,7和10互质,根据欧拉定理,则$7^{\psi(10)} \equiv 1(mod\; 10)$
因此,7的任意次方的个位数(例如7的222次方),心算就可以算出来,因为$7^{222} = (7^4)^{55} * 7^2$,又因为某个整数的个位数,就是这个整数mod 10,所以$(7^{\psi(10)})^{55} * 7^2 \equiv 9 (mod\; 10)$
欧拉定理是RSA算法的核心,只有理解这个定理,才能理解RSA
模反元素
如果两个正整数a和n互质,那么一定可以找到整数b,使得(a*b)-1整除n
$$
a * b \equiv 1(mod\; n)
$$
这时,b就叫a的“模反元素”
比如,3和11互质,找到3的模反元素4,使得(3*4)-1可以整除11。显然,模反元素不止一个,4加减11的非零整数倍都是3的模反元素{...,-18,-7,4,15,...}。即如果b是a的模反元素,则$b+kn$都是a的模反元素
欧拉定理可以用来证明模反元素必然存在
$$
a^{\psi(n)} = a * a^{\psi(n) - 1} \equiv 1 (mod\; n)
$$
可以看到,$a^{\psi(n) - 1}$就是a的模反元素
RSA密钥生成过程
首先假设小红和小明两个人进行通信
因为RSA是非对称加密算法,这也就意味着加密和解密使用的是不同的密钥,生成密钥具体分为六步:
(1)随机选择两个不相等的质数p和q
小红随机选择61和53(实际应用中,两个质数越大,就越难破解)
(2)计算p和q的乘积nn = 61*53 = 3233
(3)计算n的欧拉函数
这里利用欧拉函数求解的第四种情况:
如果n可以分解成两个互质的整数之积,即$n = p_1 * p_2$,则$\psi(n)=\psi(p_1p_2) = \psi(p_1)\psi(p_2)$,所以$\psi(3233)=\psi(61*53)=\psi(61)*\psi(53)$
又因为61和53都是质数,于是可以根据欧拉函数求解的第二种情况:
如果n是质数,则$\psi(n)=n-1$,所以$\psi(65) * \psi(53)=60*52=3120$
所以$\psi(n)=3120$
(4)随机选择一个整数$e$,条件是$1 < e < \psi(n)$,且$e$与$\psi(n)$互质小红在1到3120之间,随机选择了17
(5)计算$e$对于$\psi(n)$的模反元素d
所谓模反元素就是指有一个整数d,可以使得e*d除以$\psi(n)$的余数为1,公式表示为
$e * d = 1(mod \; \psi(n))$
这个公式等价于
$e * d - k * \psi(n) = 1$
将$e=17,\psi(n)=3120$带入得
$17d - 3120k = 1$
令$d = x,-k = y$,则
$17x + 3120y = 1$
所以我们要求的模反元素d就是对上面的二元一次方程求解,根据扩展欧几里得算法(辗转相除法)得
上图我们使用拓展欧几里得求得d=-367,但通常我们习惯取正整数,利用模反元素的特性
3和11互质,那么3的模反元素就是4,因为 (3 × 4)-1 可以被11整除。显然,模反元素不止一个, 4加减11的整数倍都是3的模反元素 {…,-18,-7,4,15,26,…},即如果b是a的模反元素,则 b+kn 都是a的模反元素
所以取$d = d + k\psi(n) = -367+1*3120=2753$
到现在为止,所有的计算都已结束
(6)将n和e封装成公钥,n和d封装成私钥
首先回归一下一共出现的6个数字:
- $p = 61$ 随机数,与$q$互质
- $q = 53$ 随机数,与$p$互质
- $n = p * q = 3233$
- $\psi(n) = 3120$
- $e = 17$ 随机数,条件是$1 < e < \psi(n)$,且$e$与$\psi(n)$互质
- $d = 2753$ $e$对于$\psi(n)$的模反元素$d$
在这个例子中n=3233,e=17,d=2753,所以公钥就是 (n,e)=(3233,17),私钥就是(n,d)=(3233, 2753),这样小红就可以将公钥公布出去,自己保存好私钥就可以了
RSA加解密演示
加密要用公钥(n,e)
假设小明先试探性的给小红发一个字母m = 'A',由于在通信传输中只能传输0和1,所以我们先将'A'转ASCII码为65,所以m = 65 (m必须是整数,且m必须小于n)
所谓加密,就是使用下面的加密公式算出密文c
$m^e = c(mod \; n)$
小明得到的公钥是(n,e) = (3233,17),m = 65,那么得到下面的等式
$65^{17} = c (mod \; 3233)$
小明通过计算得到c = 2790,所以他就把2790发给小红了
(2)揭秘要用私钥(n,d)
小红拿到小明发过来的密文c = 2790,就用下面的公式进行解密出明文m:
$c^d \equiv m (mod \; n)$
而小红的私钥为(n,d) = (3233,2753),所以得到下面的等式:
$2790^{2753} \equiv m (mod \; 3233)$
小红通过计算器以算,得m = 65,然后小红对着ASCII码表得出65对应的字母为A
至此,整个加密过程就演示完了,总结一下:
- 小明获取到小红的公钥(n,e) = (3233,17)
- 小明选取发送的消息m = 'A' = 65, 注意m要小于n,如果消息大于n,必须分段加密!
- 小明通过加密公式:$m^e \equiv c (mod \; n)$ 算出密文c = 2790
- 小红获取到小明的密文c = 2790
- 小红使用解密公式:$c^d \equiv m (mod \; n)$ 算法明文m = 65 = 'A'
以上所述就是小编给大家介绍的《RSA加密算法原理》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Advanced Web Metrics with Google Analytics, 2nd Edition
Brian Clifton / Sybex / 2010-3-15 / USD 39.99
Valuable tips and tricks for using the latest version of Google Analytics Packed with insider tips and tricks, this how-to guide is fully revised to cover the latest version of Google Analytics and sh......一起来看看 《Advanced Web Metrics with Google Analytics, 2nd Edition》 这本书的介绍吧!