安全体系（二）——RSA算法详解

逃离我推掉我的手 2022-04-22 03:32 265阅读 0赞

**正文**

本文主要讲述RSA算法使用的基本数学知识、秘钥的计算过程以及加密和解密的过程。

[安全体系（零）—— 加解密算法、消息摘要、消息认证技术、数字签名与公钥证书][Link 1]

[安全体系（一）—— DES算法详解][DES]

[安全体系（三）——SHA1算法详解][SHA1]

[回到顶部][Link 2]

# 1.概述 #

RSA公钥加密算法是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。1987年首次公布，当时他们三人都在麻省理工学院工作。RSA算法以他们三人姓氏开头字母命名。

RSA是目前最有影响力的公钥加密算法，到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。只要秘钥长度足够长，用RSA加密的信息实际上是不能被解破的。ISO推荐它为公钥数据加密标准。

RSA算法基于简单的数论事实：将两个大质数相乘十分容易，但是想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。

RSA是"非对称加密算法"，非对称加密算法需要两个密钥：公开密钥（publickey）和私有密钥（privatekey）。公钥与私钥是配对的，用公钥加密的数据只有配对的私钥才能解密，反之亦然。因加解密使用两个不同的密钥，所以这种算法叫作非对称加密算法。

非对称算法的在应用的过程如下，假设发送方向接收方发送消息（明文）：

1.接收方生成公钥和私钥，公钥公开，私钥保留；

2.发送方将要发送的消息采用公钥加密，得到密文，然后将密文发送给接收方；

3.接收方收到密文后，用自己的私钥进行解密，获得明文。

可以看出，非对称加密解决了对称加密密钥传输的问题。

[回到顶部][Link 2]

# 2.数学基础 #

RSA加密算法中，只用到素数、互质数、欧拉函数、模运算等简单的数学知识。

## 2.1 互质关系 ##

**1.素数**

素数又称质数，指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。

**2.互质数**

公因数只有1的两个数，叫做互质数；又称互素，若N个整数的最大公因子是1，则称这N个整数互质。

判断互质的简单法则：

a.任意两个质数是互质的；

b.一个数是质数，另一个数不是它的倍数，两者互质（比如正整数P是质数，则小于P的正整数和P都是互质的）；

c.两个不相等的数，较大的那个数是质数，两者互质；

d.1和任意自然数互质；

e.2和任何奇数是互质；

f.如果P是大于1的整数，则P和P-1互质；

g.如果P是大于1的奇数，则P和P-2互质。

## 2.2 欧拉函数 ##

欧拉函数的推导：

任意给定正整数n，求在小于等于n的正整数中，有多少个与n互质的正整数？

推导步骤如下：

a.当n=1时，φ(1)=1（2.1中的d）；

b.n为质数时，φ(n)=n-1（2.1中的b）；

c.如果n是某一质数的m次方，即n=pm（p为质数，m为整数且大于等于1），则

φ(pm)=pm-pm-1=pm(1-1/p)

这个式子是如何得到的呢？

当m=1时，同情况b。

根据2.1的b，p是质数，则从1到pm的整数中，除去pk(m≥k≥1)，余下的都与pm互质，页就是说，一共n(其中n=pm)个数，其中有pm-1(即p,p2,…pm)个整数与n不是互质关系，则与n互质的整数个数为pm-pm-1。

d.当n=p1\*p2，且p1、p2互质时，有

φ(n)= φ(p1p2)=φ(p1) φ(p2)

即积的欧如果a与p1互质(a<p1)，b与p2互质(b<p2)，c与p1p2互质(c<p1p2)，则c与数对 (a,b) 是一一对应关系。由于a的值有φ(p1)种可能，b的值有φ(p2)种可能，则数对 (a,b) 有φ(p1) φ(p2)种可能，而c的值有φ(p1p2)种可能，所以φ(p1p2)就等于φ(p1) φ(p2)。拉函数等于各个因子的欧拉函数的积。

e.对于任意一个大于1的正整数，都可以写成

n=p1k1p2k2…prkr，其中，p1,p2,…,pk为质数。

由d可知

φ(n)= φ(p1k1)φ(p2k2)…φ(prkr)，

再由c可知

φ(n)= p1k1p2k2…prkr(1-1/p1)(1-1/p2)…(1-1/pr)

即

φ(n)=n(1-1/p1)(1-1/p2)…(1-1/pr)

这就是欧拉函数的通用计算公式。

## 2.3 欧拉定理 ##

欧拉定理：

如果两个正整数a和n互质，则n的欧拉函数φ(n)可使下面等式成立

aφ(n)≡1(mod n)

上式表示，a的φ(n)次方被n除的余数为1，或者叙述为，a的φ(n)次方减去1后可以被n整除。注意，φ(n)是n的欧拉函数。

欧拉定理的特殊情况：如果正整数a与质数p互质，因为质数p的φ(p)等于p-1，则欧拉定理可以写成就是我们所说的费马小定理

ap-1≡1(mod p)

## 2.4 模反元素 ##

模反元素：

如果两个正整数a和n互质，那么一定可以找到整数b，使得ab-1被n整除，或者说ab被n除的余数是1。这时b被称为a的模反元素。公式如下：

ab≡1(mod n)

注意，模反元素并不唯一，如果b是a的模反元素，则b+kn都是a的模反元素。

欧拉定理可以用来证明模反元素的必然存在：

aφ(n)= a×aφ(n)-1≡1(mod n)

## 2.5 扩展欧几里得算法 ##

用来计算秘钥的d和e，这里不详细介绍，可参考[扩展欧几里得算法][Link 3]。

[回到顶部][Link 2]

# 3.秘钥的生成与加解密 #

## 3.1密钥的生成 ##

**密钥生成的步骤如下：**

1.随机选择两个不相等的质数p和q；

2.计算p和q的乘积n（将n转换为二进制后，二进制的长度就是密钥的长度，实际应用中一般选择1024位、2048位）；

3.计算n的欧拉函数φ(n)；

4.随机选择一个整数e，其中φ(n)>e>1，且e与φ(n)互质（实际应用中e一般选为65537）；

5.计算e对于φ(n)的模反元素d；

6.将n和e封装成公钥，n和d封装成私钥。

**举例：**

1.随机选择两个不相等的质数47和59；

2.二者的乘积为43×57=2773，2773转化为二进制为1010,1101,0101，长度为12位，所以密钥的长度为12位；

3.根据欧拉函数公式φ(n)=n(1-1/p)(1-1/q)计算，φ(2773)= 2773×(1-1/47)(1-1/59)=(47-1)(59-1)=2668；

4.随机选择一个整数e=63，2668>63>1，并且63与2668互质；

5.计算63对于2668的模反元素d，根据公式ed≡1(mod φ(n))，有63d-1=2668k，由欧几里得扩展公式计算得d=847。

6.公钥(n,e)=(2773,63)，私钥(n,d)=(2773,847)。

## 3.2加密和解密 ##

**1.加密**

假设发送方向接收方发送信息m，m未加密，我们称之为明文。发送方从接收方获得的公钥为(n,e)，加密公式为

me=c(mod n)

其中，m必须是整数，而且m必须比n小。

m,e,n已知，从上面的公式中计算出c，c就是加密后的信息，我们称之为密文。发送方将密文发送给接收方。

**2.解密**

接收方从发送方接收到密文c，用自己的配对私钥(n,d)进行解密，解密公式为

cd=m(mod n)

已知c,n,d，从上面公式中计算出m，就是发送方发过来的明文。

**举例：**

1.加密

根据上面计算出的公钥(n,e)=(2773,63)，假如m=244，根据公式me=c(mod n)，可计算出密文c=465。

2.解密

根据上面计算出的私钥(n,d)=(2773,847)，已知c=465，根据公式cd=m(mod n)，可计算出明文m=244。

转载地址：[https://www.cnblogs.com/songwenlong/p/6523652.html][https_www.cnblogs.com_songwenlong_p_6523652.html]

[Link 1]: http://www.cnblogs.com/songwenlong/p/6517165.html
[DES]: http://www.cnblogs.com/songwenlong/p/5944139.html
[SHA1]: http://www.cnblogs.com/songwenlong/p/6528025.html
[Link 2]: https://www.cnblogs.com/songwenlong/p/6523652.html#_labelTop
[Link 3]: http://baike.baidu.com/item/%E6%89%A9%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%B7%E7%AE%97%E6%B3%95?fr=aladdin
[https_www.cnblogs.com_songwenlong_p_6523652.html]: https://www.cnblogs.com/songwenlong/p/6523652.html