【★】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。