【★】RSA-什么是不对称加密算法？

<b>不对称加密算法RSA浅析</b>

本文主要介绍不对称加密算法中最精炼的RSA算法。我们先说结论，也就是RSA算法怎么算，然后再讲为什么。

  随便选取两个不同的大素数p和q，N=p*q，r=（p-1）*（q-1）。

    算出一组（e，d）满足e*d≡1（mod

r）。

    设明文x，密文y，x和y都小于N：

    加密：xe ≡

y (mod N)；解密：yd ≡

x (mod N)。

以前也接触过RSA加密算法，感觉这个东西太神秘了，是数学家的事，和我无关。但是，看了很多关于RSA加密算法原理的资料之后，我发现其实原理并不是我们想象中那么复杂，弄懂之后发现原来就只是这样而已..

    RSA算法的主要用途如下：

1.数据加密

    2.不对称秘钥解密

    3.保证数据完整性

    4.验证发送者

　　学过算法的朋友都知道，计算机中的算法其实就是数学运算。所以，在讲解RSA加密算法之前，有必要了解一下一些必备的数学知识。我们就从离散数学开始讲解，有一定基础的同学直接跳到下一节甚至直接看代码部分就行了。

　　RSA加密算法中，只用到素数、互质数、指数运算、模运算等几个简单的数学知识。所以，我们也需要了解这几个概念即可。

素数

互质数

　　常见的互质数判断方法主要有以下几种：

1

较小数是质数，较大数不为它的倍数。如3与10。

2 相邻的两个自然数是互质数。如 15与

16。

3 相邻的两个奇数是互质数。如 49与 51。

4

较大数是质数的两个数是互质数。如97与88。

5 辗转相除法判断。

指数运算

模运算！！非常重要，不懂请自学！

　　两个整数<b>a，b</b>，若它们除以正整数<b>m</b>所得的余数相等，则称<b>a，b</b>对于模<b>m</b>同余，记作: a

≡ b (mod

m)；读作：<b>a</b>同余于<b>b</b>模<b>m</b>，或者，<b>a</b>与<b>b</b>关于模<b>m</b>同余。例如：26

≡ 14 (mod 12)。

对称与非对称秘钥的区别

传统的加密算法都使用对称秘钥，即加密和解密都使用同一把秘钥，有的人还会混淆其与文件夹加密或者锁屏密码，这里不妨说一下，电脑上的文件夹加密和手机上的屏幕解锁密码都是应用在用户界面上的一层密码防护，并没有将文件内容重新排列组合，即使忘记密码也能通过操作系统的API接口访问内部数据，就好比把机密文件藏在保险箱里，盗贼只要敲开箱子就能看到文件信息，说白了就是防外行人的。而算法加密就是将机密文件信息翻译成火星文（内定的语言），即使卧底发现了它也看不懂。

    对称加密算法具体表现成：y=f（x）；x=f

-1（y）。举个栗子，将明文中的每个字符都替换成它在Unicode或Ascall码中的下一个字符，这是一种很简单的加密算法，接收者收到密文还真的很难想到是如此“幼稚”的排列组合。但是一旦这个算法f泄露了，第三方很容易就能推算出它的逆变换f

-1，所以对称加密算法某种程度上不安全。

那么什么是不对称加密算法呢？就是：就算告诉你了加密规则，你一时半会也想不出它对应了解密规则。我刚接触这个理论觉得很神奇，甚至不相信数学世界中会存在这种“不可逆”的算法，但是一个简单的例子就让我信服了：

一个33以下的整数x，将它变成另一个数y=x3(mod

33）即x3除以33取得的余数，我当时无论如何也想不到y怎样再变回x。这就是RSA算法的神奇之处，想知道它的解法吗？

RSA加密算法简史

　　RSA是1977年由罗纳德·李维斯特（Ron

Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard

Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的。

公钥与密钥的产生

(p-1)(q-1)，证略。

3 选择一个小于 r

r）。此时e和d关于等式对称，关于模r互逆互质。

将 p 和 q 的记录销毁。

5 

(N,e)是公钥，(N,d)是私钥。Alice将她的公钥(N,e)传给Bob，而 

    将自己的私钥(N,d)藏起来。

加密消息

　　xe ≡

y (mod N)

计算y并不复杂。Bob算出y后就可以将它传递给Alice。

解密消息

Alice得到Bob的消息y后就可以利用她的密钥d来解码。她可以用以下这个公式来将y转换为x：

　　yd ≡

x (mod N)

这样就得到的余数x就是原来的明文x，她可以将原来的信息X重新复原。

解码的原理

（证明解密等式成立即可）

　　由加密算法推得yd ≡

x e·d(mod

N)

以及ed ≡ 1

(mod p-1)和ed ≡ 1

　　xe·d ≡

x (mod

p) 　　和 　x e·d ≡

x (mod q)

    xe·d ≡

x (mod pq)

不过说实话，算法的证明需要引用欧拉、费马老人家的定理比较繁琐，即使看懂了也没有太多的成就感所以读者可以选择直接记住它的结论。

签名消息

digest)，然后用她的密钥(private

key)加密这个散列值并将这个“署名”加在消息的后面。这个消息只有用她的公钥才能被解密，此处可以看出公钥e和私钥d是可以互换使用的，即公式上的”对称“。乙获得这个消息后可以用甲的公钥解密这个散列值，然后将这个数据与他自己为这个消息计算的散列值相比较。假如两者相符的话，那么他就可以知道发信人持有甲的密钥，反之如果不符那么这个消息既可能被篡改也可能来自第三方的“坏人”。

编程实践

　　下面，开始我们的重点环节：编程实践。在开始编程前，我们通过计算，来确定公钥和密钥。

计算公钥和密钥

1 假设p = 3、q = 11（解决之前的伏笔~），则N = pq

= 33；

2 r = (p-1)(q-1) = (3-1)(11-1) =

20；

3 根据模反元素的计算公式，我们可以得出，e·d ≡ 1 (mod

20),即e·d = 20n+1 (n为正整数)；我们假设n=1，则e·d = 21。e、d为正整数，并且e与r互质，则e = 3，d

= 7。（两个数交换一下也可以。）

　　到这里，公钥和密钥已经确定。公钥为(N, e) = (33,

3)，密钥为(N, d) = (33, 7)。

编程实现

　　下面我们使用Java来实现一下加密和解密的过程。具体代码如下：

"font-size:14px;"&gt;<b>package</b> security.rsa;  

2

<b>3</b> <b>publicclass</b> RSA {  

5

<b>11</b>

<b>publicstaticlong</b> rsa(<b>int</b> baseNum, <b>int</b> key, <b>long</b> message){  

<b>12</b>

<b>if</b>(baseNum &lt; 1 || key &lt; 1){  

<b>13</b> <b>return</b> 0L;  

14         }  

15 //加密或者解密之后的数据

<b>16</b>

<b>long</b> rsaMessage = 0L;  

17

18 //加密核心算法

19         rsaMessage = Math.round(Math.pow(message, key)) % baseNum;  

<b>20</b>

<b>return</b> rsaMessage;  

21     }  

22

23

24

<b>25</b>

<b>publicstaticvoid</b> main(String[] args){  

26

//基数

<b>27</b>

<b>int</b> baseNum = 3 * 11;  

28

//公钥

<b>29</b>

<b>int</b> keyE = 3;  

30

//密钥

<b>31</b>

<b>int</b> keyD = 7;  

32 //未加密的数据

<b>33</b>

<b>long</b> msg = 24L;  

34 //加密后的数据

<b>35</b>

<b>long</b> encodeMsg = rsa(baseNum, keyE, msg);  

36 //解密后的数据

<b>37</b>

<b>long</b> decodeMsg = rsa(baseNum, keyD, encodeMsg);  

38

39         System.out.println("加密前：" + msg);  

40         System.out.println("加密后：" + encodeMsg);  

41         System.out.println("解密后：" + decodeMsg);  

42

43     }  

44       

45

46

}  

RSA算法结果：

加密前：24

加密后：30

解密后：24

（看程序最清楚了，对于要加密的数字x,

xe%N=y,

y就是加密之后的密文。yd%N=x,

就能解密得到x）

RSA加密算法的安全性

　　当p和q是一个大素数的时候，从它们的积pq去分解因子p和q，这是一个公认的数学难题。然而，虽然RSA的安全性依赖于大数的因子分解，但并没有从理论上证明破译RSA的难度与大数分解难度等价。

RSA加密算法的缺点

　　虽然RSA加密算法作为目前最优秀的公钥方案之一，在发表三十多年的时间里，经历了各种攻击的考验，逐渐为人们接受。但是，也不是说RSA没有任何缺点。由于没有从理论上证明破译RSA的难度与大数分解难度的等价性。所以，RSA的重大缺陷是无法从理论上把握它的保密性能如何。在实践上，RSA也有一些缺点：

产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密；

2 分组长度太大，为保证安全性，n 至少也要 600 bits

以上，使运算代价很高，尤其是速度较慢（比对称加密算法慢1000倍以上）。

以上就是RSA算法的全部内容以及尽可能多的个人理解，若有偏差请自行改正，疑问请留言qq2195868682。