RSA加密算法原理

栏目: 编程工具 · 发布时间: 5年前

内容简介: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,所以它们互质。 不是质数也可以构成互质关系

只要满足以下几点就可构成互质关系:

  1. 任意两个质数构成互质关系,比如13和61
  2. 1和任意一个自然数是都是互质关系,比如1和99
  3. p是大于1的整数,则p和p-1构成互质关系,比如57和56
  4. p是大于1的奇数,则p和p-2构成互质关系,比如17和15
  5. 如果两个数之中,较大的那个数是质数,则两者构成互质关系,比如97和10
  6. 一个数是质数,另一个数只要不是前者的倍数,两者就构成互质关系,比如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的乘积n
n = 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就是对上面的二元一次方程求解,根据扩展欧几里得算法(辗转相除法)得

RSA加密算法原理

上图我们使用拓展欧几里得求得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个数字:

  1. $p = 61$ 随机数,与$q$互质
  2. $q = 53$ 随机数,与$p$互质
  3. $n = p * q = 3233$
  4. $\psi(n) = 3120$
  5. $e = 17$ 随机数,条件是$1 < e < \psi(n)$,且$e$与$\psi(n)$互质
  6. $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

至此,整个加密过程就演示完了,总结一下:

  1. 小明获取到小红的公钥(n,e) = (3233,17)
  2. 小明选取发送的消息m = 'A' = 65, 注意m要小于n,如果消息大于n,必须分段加密!
  3. 小明通过加密公式:$m^e \equiv c (mod \; n)$ 算出密文c = 2790
  4. 小红获取到小明的密文c = 2790
  5. 小红使用解密公式:$c^d \equiv m (mod \; n)$ 算法明文m = 65 = 'A'

以上所述就是小编给大家介绍的《RSA加密算法原理》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Advanced Web Metrics with Google Analytics, 2nd Edition

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》 这本书的介绍吧!

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具