RSA 演算法的加密原理是什麼？

01-15

參考：密碼學之RSA加密

RSA加密：非對稱密鑰，公開密鑰演算法

RSA加密利用了單向函數正向求解很簡單，反向求解很複雜的特性。

具體是利用了：

1.對兩個質數相乘容易，而將其合數分解很難的這個特點進行的加密演算法。 n=p1*p2，已知p1、p2求n簡單，已知n求p1、p2困難。

2.(m^e) mod n=c，已知m、e、n求c簡單，已知e、n、c求m很難。

RSA加密，實現了公開密鑰，就是A可以給所有人發送鎖，其他人把要加密的信息用這把鎖加密後發送給A，A用自己的鑰匙開鎖就可以獲得加密的信息了。反過來，A要發送加密信息給B，只要知道B的鎖就可以了，而這個鎖是公開的。

公開密鑰n、e的生成：隨機選取兩個質數p1、p2，n=p1*p2，再隨機選取一個整數e，e與φ(n)互質。

加密過程：(m^e) mod n=c，其中m為原信息，c為加密信息，n、e為公開密鑰。

解密過程：(c^d) mod n=m，其中d為解密密鑰。

解密密鑰d的求解：

(c^d) mod n=(((m^e) mod n)^d) mod n=((m^e)^d) mod n=(m^ed) mod n=m ①

根據費馬定理(m^φ(n)) mod n≡1，又1^k≡1，所以(m^k*φ(n)) mod n≡1，兩邊同乘以m得m*((m^k*φ(n)) mod n)≡1*m，化簡(m^(k*φ(n)+1)) mod n≡m ②

由①、②得ed=(k*φ(n)+1)，解得d=(k*φ(n)+1)/e。

費馬定理：若p是素數，a與p互素，則a^(p-1）≡1 （mod p）

過程如下：

A：有一個公鑰n、e。例如：3127、3。

B：有一個信息m。例如：89。

C：偷聽者

A：

第一步：隨機找兩個質數p1、p2，一個奇數e。例如：53、59、3。

第二步：計算n=p1*p2得到n，計算歐拉函數φ(n)=(p1-1)*(p2-1)得到φ(n)，計算鑰匙d=(k*φ(n)+1)/e得到d。例如：53*59=3127、(53-1)*(59-1)=3016、(k*φ(n)+1)/e=(2*3016+1)/3=2011。

第三步：發送n、e給大家知道 //n、e就是公鑰也做鎖，d就是n、e的鑰匙。

C：獲得n、e

B：

第一步：獲得n、e

第二步：加密信息m，(m^e) mod n=c，獲得加密信息c。例如：(89^3) mod 3127=1394。

第三步：發送c給A

C：

第一步：截獲加密信息c

第二步：破解信息c，此時C只有n、e、c，只有把n分解質因數才能破解，而此分解很困難特別是當n很大的時候。

A：

第一步：收到加密信息c

第二步：解密信息c，(c^d) mod n=m，獲得信息m。例如：(1394^2011) mod 3127=89。

完成

Basic RSA:

比如Alice和Bob兩個人

Alice想給Bob一個信息

那B應該

1&>選2個不一樣的很大的質數p與q, 然後B就可以算出n=pq

2&>再選一個e 有一個前提 gcd(e, (p-1)(q-1))=1 (一般很多地方e=65537)

3&>B再需要算出d 使d*e=1(mod (p-1)(q-1)) 你可以通過extended Euclidean algorithm找出來

接下來Alice應該

4&>把她寫的信息轉化為數字m(mod n)

5&>然後算出c=m^e(mod n)然後把她所得的c發回給B

最後

6&>B便可以算出m=c^d(mod n)

在RSA裡面 n,e 都是public key

d是Bob的private key

原理如下

de=1(mod(p-1)(q-1))

de=1+((p-1)(q-1))k for some k

Euler『s rule 可以證明: x^((p-1)(q-1))=1 (mod pq) [if gcd(x, pq)=1]

c^d=(m^e)^d=m^de=m^1*(m^((p-1)(q-1))^k=m*1^k (mod pq)=m(mod pq)

盡量用簡單的方式說出來了

希望可以幫到你如果還有什麼不懂的可以再讓我知道^ ^

RSA公鑰加密演算法是一種非對稱加密技術，也就是加密使用的密鑰（公鑰）和解密用的密鑰（私鑰）不是同一把。

在加密信息數據之前，接收方會把加密用的公鑰對外公開，發送方用公鑰進行加密信息數據成為密文，而解密的密鑰一直都保存在接收方手中。

但是普通的非對稱加密技術很容易被暴力破解，因此為了保證信息數據的安全，需要更安全的公鑰加密技術，RSA公鑰加密演算法在這種情況下應運而生。

RSA公鑰加密演算法是基於一個簡單的數論事實：將兩個大的質數相乘很容易得到乘積，但要把乘積進行因式分解卻非常困難。

RSA公鑰加密演算法也並非牢不可破，1999年就已經破解了512位的密鑰，2009年又破解了768位的密鑰，因此目前的RSA密鑰通常採用的1024位的密鑰，但隨著量子計算機的發展，1024位的密鑰的安全性也受到了挑戰，在未來十年內1024位的RSA密鑰會被逐漸淘汰，進而選擇更長的鑰匙。

以上純手碼，內容來源於以前寫過的一篇關於RSA技術的論文。

中文wiki wikipedia.org 的頁

英語wiki RSA (cryptosystem)

原始論文http://people.csail.mit.edu/rivest/Rsapaper.pdf

將兩個大素數相乘十分容易，但想要對其乘積進行因式分解卻極其困難，這就是RSA的基本原理。

劉英經常對永強講悄悄話。

無奈長貴時常偷聽，於是他們想到了用RSA來對悄悄話。

永強仔細挑選了一個大家都知道的公鑰:(N,e)，仔細挑選了一個只有自己知道的密鑰:d。

當劉英準備給永強發一條明文信息 x 時：

1）劉英使用永強的公鑰(N, e)進行信息加密(x^e mod N)。

2）永強收到加密信息後使用自己的密鑰 d進行信息解密 (x^e)^d mod N得到 x。

RSA WorkFlow (來源：https://www.slideshare.net/daxeshchauhan/rsa-and-diffie-hellman-algorithms-64170629)

也就是說 (x^e)^d 同餘 x mod N ?

是的。

1.永強如何仔細挑選公鑰(N, e)？

先選兩個質數p、q。

N = p*q.

e跟 (p-1)*(q-1)互質，即最大公約數為1。

2.永強如何仔細挑選密鑰 d？

挑選d 使得 d*e 同餘 1 mod (p-1)*(q-1)。

使用傳說中的擴展歐幾里得演算法，可以得d。

3. 根據以上, 如何證明(x^e)^d mod N 同餘 x？

證明 x^(ed) 同餘 x mod N

=&> 證明 x^(ed) - x 可以被 N 整除

根據d的性質： d*e 同餘 1 mod (p-1)*(q-1) =&> d*e = 1 + k(p-1)(q-1) 對於某些整數k.

那麼也就變成了證明 x^(1 + k(p-1)(q-1)) - x，即x(x^(k(p-1)(q-1))-1) 可以被 N 整除。

根據費馬小定理，x^(k(p-1))^(q-1)可以被q整除，x^(k(q-1))^(p-1)可以被p整除.

所以p跟q是 x^(ed) - x 的質數因子

所以N=p*q是x^(ed) - x的因子

x^(ed) - x mod N = 0

x^(ed) 同餘 x mod N。

4. 為啥長貴幾乎不可能猜到明文消息 x?

無論1）枚舉 x滿足 x^e 同餘 y mod N 或者 2）因式分解N找到p跟q，

破解2048位的密鑰可能需要傳統計算機耗費10億年的時間。

歐拉定理的可以從一個已知質數計算到另一個未知質數

RSA加密演算法中的數學原理

可參考。

一言以蔽之，兩個很大的質數p和q的乘積n難以逆向求解，目前似乎只能暴力破解幾百位。

剛剛考完密碼學，作為某985的學生很羞愧的說我也不是很清楚→_→。

其實就是利用大素數，各種操作，然後逆置換等等，這些東西。