rsa演算法2048

『壹』 RSA演算法介紹

RSA演算法是第一個能同時用於加密和數字簽名的演算法，也易於理解和操作。 RSA是被研究得最廣泛的公鑰演算法，從提出到現在已近二十年，經歷了各種攻擊的考驗，逐漸為人們接受，普遍認為是目前最優秀的公鑰方案之一。RSA的安全性依賴於大數的因子分解，但並沒有從理論上證明破譯RSA的難度與大數分解難度等價。即RSA的重大缺陷是無法從理論上把握它的保密性能如何，而且密碼學界多數人士傾向於因子分解不是NPC問題。 RSA的缺點主要有：A)產生密鑰很麻煩，受到素數產生技術的限制，因而難以做到一次一密。B)分組長度太大，為保證安全性，n 至少也要 600 bits以上，使運算代價很高，尤其是速度較慢，較對稱密碼演算法慢幾個數量級；且隨著大數分解技術的發展，這個長度還在增加，不利於數據格式的標准化。目前，SET(Secure Electronic Transaction)協議中要求CA採用2048比特長的密鑰，其他實體使用1024比特的密鑰。 這種演算法1978年就出現了，它是第一個既能用於數據加密也能用於數字簽名的演算法。它易於理解和操作，也很流行。演算法的名字以發明者的名字命名：Ron Rivest, AdiShamir 和Leonard Adleman。 RSA演算法是一種非對稱密碼演算法，所謂非對稱，就是指該演算法需要一對密鑰，使用其中一個加密，則需要用另一個才能解密。 RSA的演算法涉及三個參數，n、e1、e2。 其中，n是兩個大質數p、q的積，n的二進製表示時所佔用的位數，就是所謂的密鑰長度。 e1和e2是一對相關的值，e1可以任意取，但要求e1與(p-1)*(q-1)互質；再選擇e2，要求(e2*e1)mod((p-1)*(q-1))=1。 (n及e1),(n及e2)就是密鑰對。 RSA加解密的演算法完全相同,設A為明文，B為密文，則：A=B^e1 mod n；B=A^e2 mod n； e1和e2可以互換使用，即： A=B^e2 mod n；B=A^e1 mod n;
[編輯本段]一、RSA 的安全性
RSA的安全性依賴於大數分解，但是否等同於大數分解一直未能得到理論上的證明，因為沒有證明破解 RSA就一定需要作大數分解。假設存在一種無須分解大數的演算法，那它肯定可以修改成為大數分解演算法。目前， RSA 的一些變種演算法已被證明等價於大數分解。不管怎樣，分解n是最顯然的攻擊方法。現在，人們已能分解多個十進制位的大素數。因此，模數n 必須選大一些，因具體適用情況而定。
[編輯本段]二、RSA的速度
由於進行的都是大數計算，使得RSA最快的情況也比DES慢上好幾倍，無論是軟體還是硬體實現。速度一直是RSA的缺陷。一般來說只用於少量數據加密。
[編輯本段]三、RSA的選擇密文攻擊
RSA在選擇密文攻擊面前很脆弱。一般攻擊者是將某一信息作一下偽裝( Blind)，讓擁有私鑰的實體簽署。然後，經過計算就可得到它所想要的信息。實際上，攻擊利用的都是同一個弱點，即存在這樣一個事實：乘冪保留了輸入的乘法結構： ( XM )^d = X^d *M^d mod n 前面已經提到，這個固有的問題來自於公鑰密碼系統的最有用的特徵--每個人都能使用公鑰。但從演算法上無法解決這一問題，主要措施有兩條：一條是採用好的公鑰協議，保證工作過程中實體不對其他實體任意產生的信息解密，不對自己一無所知的信息簽名；另一條是決不對陌生人送來的隨機文檔簽名，簽名時首先使用One-Way HashFunction 對文檔作HASH處理，或
[編輯本段]四、RSA的公共模數攻擊
若系統中共有一個模數，只是不同的人擁有不同的e和d，系統將是危險的。最普遍的情況是同一信息用不同的公鑰加密，這些公鑰共模而且互質，那末該信息無需私鑰就可得到恢復。設P為信息明文，兩個加密密鑰為e1和e2，公共模數是n，則： C1 = P^e1 mod n C2 = P^e2 mod n 密碼分析者知道n、e1、e2、C1和C2，就能得到P。 因為e1和e2互質，故用Euclidean演算法能找到r和s，滿足： r * e1 + s * e2 = 1 假設r為負數，需再用Euclidean演算法計算C1^(-1)，則 ( C1^(-1) )^(-r) * C2^s = P mod n 另外，還有其它幾種利用公共模數攻擊的方法。總之，如果知道給定模數的一對e和d，一是有利於攻擊者分解模數，一是有利於攻擊者計算出其它成對的e』和d』，而無需分解模數。解決辦法只有一個，那就是不要共享模數n。 RSA的小指數攻擊。 有一種提高 RSA速度的建議是使公鑰e取較小的值，這樣會使加密變得易於實現，速度有 所提高。但這樣作是不安全的，對付辦法就是e和d都取較大的值。

可以直接hi我
給你一些例子

『貳』 RSA 加密演算法 談到的 1024 2048bit 是什麼意思

bit中文名稱是位，音譯「比特」，是用以描述電腦數據量的最小單位。
二進制數系統中，每個0或1就是一個位(bit)。
單位換算
1Byte=8bit
1KB=1024Byte(位元組)=8*1024bit
1MB=1024KB
1GB=1024MB
1TB=1024GB
二進制數系統中，每個0或1就是一個位(bit)，位是數據存儲的最小單位。其中8bit就稱為一個位元組（Byte）。計算機中的CPU位數指的是CPU一次能處理的最大位數。例如32位計算機的CPU一次最多能處理32位數據。

『叄』 RSA演算法的基本含義

RSA公開密鑰密碼體制。所謂的公開密鑰密碼體制就是使用不同的加密密鑰與解密密鑰，是一種「由已知加密密鑰推導出解密密鑰在計算上是不可行的」密碼體制。
在公開密鑰密碼體制中，加密密鑰（即公開密鑰）PK是公開信息，而解密密鑰（即秘密密鑰）SK是需要保密的。加密演算法E和解密演算法D也都是公開的。雖然解密密鑰SK是由公開密鑰PK決定的，但卻不能根據PK計算出SK。
正是基於這種理論，1978年出現了著名的RSA演算法，它通常是先生成一對RSA 密鑰，其中之一是保密密鑰，由用戶保存；另一個為公開密鑰，可對外公開，甚至可在網路伺服器中注冊。為提高保密強度，RSA密鑰至少為500位長，一般推薦使用1024位。這就使加密的計算量很大。為減少計算量，在傳送信息時，常採用傳統加密方法與公開密鑰加密方法相結合的方式，即信息採用改進的DES或IDEA對話密鑰加密，然後使用RSA密鑰加密對話密鑰和信息摘要。對方收到信息後，用不同的密鑰解密並可核對信息摘要。
RSA演算法是第一個能同時用於加密和數字簽名的演算法，也易於理解和操作。RSA是被研究得最廣泛的公鑰演算法，從提出到現今的三十多年裡，經歷了各種攻擊的考驗，逐漸為人們接受，普遍認為是目前最優秀的公鑰方案之一。
SET(Secure Electronic Transaction)協議中要求CA採用2048bits長的密鑰，其他實體使用1024比特的密鑰。RSA密鑰長度隨著保密級別提高，增加很快。下表列出了對同一安全級別所對應的密鑰長度。 保密級別 對稱密鑰長度（bit） RSA密鑰長度（bit） ECC密鑰長度（bit） 保密年限 80 80 1024 160 2010 112 112 2048 224 2030 128 128 3072 256 2040 192 192 7680 384 2080 256 256 15360 512 2120 這種演算法1978年就出現了，它是第一個既能用於數據加密也能用於數字簽名的演算法。它易於理解和操作，也很流行。演算法的名字以發明者的名字命名：Ron Rivest, Adi Shamir 和 Leonard Adleman。早在1973年，英國國家通信總局的數學家Clifford Cocks就發現了類似的演算法。但是他的發現被列為絕密，直到1998年才公諸於世。
RSA演算法是一種非對稱密碼演算法，所謂非對稱，就是指該演算法需要一對密鑰，使用其中一個加密，則需要用另一個才能解密。
RSA的演算法涉及三個參數，n、e1、e2。
其中，n是兩個大質數p、q的積，n的二進製表示時所佔用的位數，就是所謂的密鑰長度。
e1和e2是一對相關的值，e1可以任意取，但要求e1與(p-1)*(q-1)互質；再選擇e2，要求(e2*e1)mod((p-1)*(q-1))=1。
（n，e1),(n，e2)就是密鑰對。其中(n，e1)為公鑰，(n，e2)為私鑰。
RSA加解密的演算法完全相同，設A為明文，B為密文，則：A=B^e2 mod n；B=A^e1 mod n；（公鑰加密體制中，一般用公鑰加密，私鑰解密）
e1和e2可以互換使用，即：
A=B^e1 mod n；B=A^e2 mod n;

『肆』 什麼是RSA演算法，求簡單解釋。

RSA公鑰加密演算法是1977年由Ron Rivest、Adi Shamirh和LenAdleman在（美國麻省理工學院）開發的。RSA取名來自開發他們三者的名字。RSA是目前最有影響力的公鑰加密演算法，它能夠
抵抗到目前為止已知的所有密碼攻擊，已被ISO推薦為公鑰數據加密標准。RSA演算法基於一個十分簡單的數論事實：將兩個大素數相乘十分容易，但那時想要對其乘積進行因式分解卻極其困難，因此可以將乘積公開作為加密密鑰。由於進行的都是大數計算，使得RSA最快的情況也比DES慢上好幾倍，無論是軟體還是硬體實現。速度一直是RSA的缺陷。一般來說只用於少量數據加密。RSA的速度比對應同樣安全級別的對稱密碼演算法要慢1000倍左右。
基礎
大數分解和素性檢測——將兩個大素數相乘在計算上很容易實現，但將該乘積分解為兩個大素數因子的計算量是相當巨大的，以至於在實際計算中是不能實現的。
1.RSA密碼體制的建立：
(1)選擇兩個不同的大素數p和q；
(2)計算乘積n=pq和Φ(n)=(p-1)(q-1)；
(3)選擇大於1小於Φ(n)的隨機整數e，使得gcd(e,Φ(n))=1；
(4)計算d使得de=1mod Φ(n)；
(5)對每一個密鑰k=(n,p,q,d,e)，定義加密變換為Ek(x)=xemodn，解密變換為Dk(x)=ydmodn，這里x,y∈Zn；
(6)以{e,n}為公開密鑰，{p,q,d}為私有密鑰。
2.RSA演算法實例:
下面用兩個小素數7和17來建立一個簡單的RSA演算法：
(1)選擇兩個素數p=7和q=17；
(2)計算n=pq=7 17=119，計算Φ(n)=(p-1)(q-1)=6 16=96；
(3)選擇一個隨機整數e=5，它小於Φ(n)＝96並且於96互素；
(4)求出d，使得de=1mod96且d<96，此處求出d=77，因為 77 5＝385＝4 96＋1；
(5)輸入明文M＝19，計算19模119的5次冪，Me＝195＝66mod119,傳出密文C＝66；(6)接收密文66，計算66模119的77次冪；Cd=6677≡19mod119得到明文19。

『伍』 RSA演算法詳解

總括： 本文詳細講述了RSA演算法詳解，包括內部使用數學原理以及產生的過程。

相濡以沫。到底需要愛淡如水。

之前寫過一篇文章 SSL協議之數據加密過程 ，裡面詳細講述了數據加密的過程以及需要的演算法。SSL協議很巧妙的利用對稱加密和非對稱加密兩種演算法來對數據進行加密。這篇文章主要是針對一種最常見的非對稱加密演算法——RSA演算法進行講解。其實也就是對私鑰和公鑰產生的一種方式進行描述。首先先來了解下這個演算法的歷史：

RSA是1977年由 羅納德·李維斯特 （Ron Rivest）、 阿迪·薩莫爾 （Adi Shamir）和 倫納德·阿德曼 （Leonard Adleman）一起提出的。當時他們三人都在 麻省理工學院 工作。RSA就是他們三人姓氏開頭字母拼在一起組成的。

但實際上，在1973年，在英國政府通訊總部工作的數學家 克利福德·柯克斯 （Clifford Cocks）在一個內部文件中提出了一個相同的演算法，但他的發現被列入機密，一直到1997年才被發表。

所以誰是RSA演算法的發明人呢？不好說，就好像貝爾並不是第一個發明電話的人但大家都記住的是貝爾一樣，這個地方我們作為旁觀者倒不用較真，重要的是這個演算法的內容：

RSA演算法用到的數學知識特別多，所以在中間介紹這個演算法生成私鑰和公鑰的過程中會穿插一些數學知識。生成步驟如下：

隨意選擇兩個大的質數p和q，p不等於q，計算N=p*q;

什麼是質數?我想可能會有一部分人已經忘記了，定義如下：

比如2，3，5，7這些都是質數，9就不是了，因為3*3=9了

r = φ(N) = φ(p)φ(q) = (p-1)(q-1) 。

這里的數學概念就是什麼是歐拉函數了，什麼是歐拉函數呢？

歐拉函數 的定義：

互質 的定義：

例如： φ(8) = 4 ，因為 1,3,5,7 均和 8 互質。

推導歐拉函數:

（1）如果 n = 1 , φ(1) = 1 ；(小於等於1的正整數中唯一和1互質的數就是1本身)；

（2）如果 n 為質數， φ(n) = n - 1 ；因為質數和每一個比它小的數字都互質。比如5，比它小的正整數1,2,3,4都和他互質；

(3) 如果 n 是 a 的 k 次冪，則 φ(n) = φ(a^k) = a^k - a^(k-1) = (a-1)a^(k-1) ；

(4) 若 m , n 互質，則 φ(mn) = φ(m)φ(n)

證明： 設 A , B , C 是跟 m , n , mn 互質的數的集，據 中國剩餘定理 (經常看數學典故的童鞋應該了解，剩餘定理又叫韓信點兵，也叫孫子定理)， A * B 和 C 可建立雙射一一對應)的關系。（或者也可以從初等代數角度給出 歐拉函數積性的簡單證明 ） 因此的φ(n)值使用 算術基本定理 便知。（來自維基網路）

選擇一個小於r並與r互質的整數e，求得e關於r的模反元素，命名為 d （ ed = 1(mod r) 模反元素存在，當且僅當e與r互質）， e 我們通常取65537。

模反元素：

比如 3 和 5 互質， 3 關於 5 的模反元素就可能是2，因為 3*2-1=5 可以被5整除。所以很明顯模反元素不止一個，2加減5的整數倍都是3關於5的模反元素 {...-3, 2,7,12…} 放在公式里就是 3*2 = 1 (mod 5)

上面所提到的歐拉函數用處實際上在於歐拉定理：

歐拉定理：

歐拉定理就可以用來證明模反元素必然存在。

由模反元素的定義和歐拉定理我們知道， a 的 φ(n) 次方減去1，可以被n整除。比如，3和5互質，而 5 的歐拉函數 φ(5) 等於4，所以 3 的 4 次方 (81) 減去1，可以被 5 整除（ 80/5=16 ）。

小費馬定理：

此時我們的 (N , e) 是公鑰， (N, d) 為私鑰，愛麗絲會把公鑰 (N, e) 傳給鮑勃，然後將 (N, d) 自己藏起來。一對公鑰和私鑰就產生了，然後具體的使用方法呢？請看： SSL協議之數據加密過程詳解

我們知道像RSA這種非對稱加密演算法很安全，那麼到底為啥子安全呢？
我們來看看上面這幾個過程產生的幾個數字：

N 和 e 我們都會公開使用，最為重要的就是私鑰中的 d ， d 一旦泄露，加密也就失去了意義。那麼得到d的過程是如何的呢？如下:

所以得出了在上篇博客說到的結論，非對稱加密的原理：

將a和b相乘得出乘積c很容易，但要是想要通過乘積c推導出a和b極難。即對一個大數進行因式分解極難

目前公開破譯的位數是768位，實際使用一般是1024位或是2048位，所以理論上特別的安全。

RSA演算法的核心就是歐拉定理，根據它我們才能得到私鑰，從而保證整個通信的安全。

『陸』 品味數學之美－RSA原理淺析

在探究RSA演算法的原理之前，我們先來學習一點有趣的數論知識（數學分支之一，主要研究整數的性質）。你會發現一些簡單的數學知識竟然背後有如此神奇的魔力。

說起質數，想必大家不陌生了，一個大於1的整數除了其本身和1之外，不存在因數則被稱為質數或者是素數。比如2、3、5、7等。在小學課堂里，我們可能只是記住了這個概念，但是這里我談下自己的一些思考幫助大家理解，質數就好比是構成數字的基本元素，想想看，氫分子僅由兩個氫原子（組成一個氫分子）構成，那麼一個非質數的6=3*2 即表示為6是由兩個「3」元素或3個「2」元素構成。其中「3」或者「2」是不可以繼續拆分的元素（3，2都是質數）。所以對一個非質數進行因式分解過程就好比對一個物體進行深入解剖，拆分至不可拆分的元素為止。這樣看來，數學家們提出這些數學概念，其實也是一種對數字世界的認識和思考的概括，和我們日常生活理解周邊事物方式也是相似的。

知道了質數，我們再看看互質關系，那麼什麼是互質呢？就是說兩個數沒有相同的因數稱為互質關系。我們對6進行因數分解，拆分到質數的乘積即6＝3* 2而 35=5*7,這兩者沒有相同的因數則稱6與35互質，就好像氫氣分子只是由氫原子構成，而氧氣分子只是由氧原子構成，這二者這間沒有相同的原子就是一種互質的體現。
所以互質只是一個數和數之間有沒有相同的因數關系的體現(公約數也稱公因數)，和兩者是不是質數是沒有關系的。當然質數之間必然是互質關系，因為它們都是構成數字的不同元素。數學上來表示a,b互質一般用gcd(a,b)=1來表示。即a和b的最大公約數是1.

質數和互質的關系是不是很容易理解？但是大數學家歐拉先生可絕不僅僅停步於此，數學家嘛總愛問一下抽象概括性的問題，希望找尋規律比如

如果能找到規律，無論數字如何千變萬化10位數還是100000位數，我們都能根據准則輕易計算數互質關系的數量。你發現了沒有，數字也是一片世界，真是一花一世界一葉一如來啊！好了回歸正傳，對於這個問題歐拉先生給出了他的答案。他是這樣作答的：
首先呢上述問題可以簡化為一個函數來描述即： Phi(n)
這也是數學家老毛病在他們看來任何問題就是對函數的求解。既然這個函數由歐拉提出來的，那麼我們就稱他為 歐拉函數 .還好這個函數簡單只有一個變數，即給定的正整數n。接下來就要分析這個n

n＝1的時候這個問題極其簡單：
Phi(n)＝1
因為1與任何數包含他自身都構成互質關系。1本身也是質數且不作為其他數的因數，因為任何數乘以1都是其本身

大家想想看n是質數，其自身就不存在因數了，而那些與他非互質關系(存在公約數)的數進行因式分解後一定都會有一個因數與n相等。比如n＝3為一個質數，那麼6＝3*2與3是非互質關系，因為存在公約數3。所以我們發現與n非互質關系的數都是n的倍數即(kn)，因為kn>=n所以與n互質的數都小於n即
Phi(n)＝n-1

還記得我們前面提到的質數嗎，他可是構成數字的元素呀，所以如果n不是質數，那麼他一定可以被因式分解拆分成多個質數的乘積。比如24=6*4=3*8=2*2*2*3 比如6=2*3，這些質數因數相互乘積也可以形成如下情況：

我們把相同質數因數進行相乘，很容易將一個非質數分解為兩個互質關系的數的乘積，比如24=6*4=2*2*2*3＝3*8
從簡單的情況來考慮，即n被拆分為兩個互質關系的數的乘積：
即

n=p*q
p與q互質，那麼根據剩餘定理:

Phi left( pq ight) =Phi(p)*Phi(q)

至於如何證明呢？說實話我也不清楚。在我理解看來，與24互質的數都有這樣一個特點：他進行因式分解後其因數不包含有3與2（因為8=2*2*2）。所以與3互質的數定義為集合A，且個數為
Phi left( 3 ight)
與8互質的數定義為集合B，且個數為
Phi left( 8 ight)
這AB兩組的數字可以在組與組間兩兩進行組合乘積，構成與24互質的數。所以兩組數字個數相乘就可以知道乘積的組合個數，也就知道與24互質的個數了。這樣的證明並不嚴謹但姑且可以先記住。
另外還需要記住歐拉函數是一個 積性函數 ,也就是n如果為多個互質的數構成即(n=a*b*c*d.... )，那麼
Phi left( n ight)=Phi left( a ight) *Phi left( b ight)....

也就是n為某一個質數的倍數，比如27=3*3*3=3^3 27就是3的倍數。那麼小於27且存在非互質關系的數一定都是3的倍數也就是：1*3、2*3,3*3...9*3 共計9個， 所以3^3 - 9 ＝3^3 - 3^2 .所以歸納一下也就是說如果p是質數，求與p^n 互質的數的個數，只要將如下的數
(1*p)、(2*p)、(3*p)、....(p^n-1 *p) 進行剔除，剩餘的都將與p^n （切記p是質數）互質所以我們得出：

Phi left( p^{k} ight)=p^{k}-p^{k-1}＝p^{k}(1-dfrac {1}{p} )

當k＝1的時候即
Phi left( p ight)=p-1
又回到了之前n為質數的情況下的表達式。這里我們也看到數學追求簡潔和普適性的思想，再繁雜的規律都可以變成一個簡潔抽象的表達式。

比如24=6*4=3*8=2*2*2*3，因為質數之間就是互質關系而且質數的多次方也是互質關系所以
我們把24演變一下：24=2^3 * 3即把相同的質數進行合並為質數的多次方。這樣2^3 與3是互質關系( 質數的多次方之間也都是互質關系 )，於是當我們求與24互質的數的個數時候，就可以套用之前公式即：

Phi left(24 ight)=Phi left( 2^{3}*3 ight)=Phi left(2^3 ight)*Phi left(3 ight)=(2^{3}-2^{3-1})(3-1) =8

再進一步歸納因為p1、 p2...pm等都是質數且
n = p_{1}^{k_{1}}p_{2}^{k_{2}}p_{3}^{k_{3}}...p_{m}^{k_{m}}

則由於歐拉函數是積性函數，那麼：
Phi left(n ight)=Phi left( p_{1}^{k_{1}}p_{2}^{k_{2}}p_{3}^{k_{3}}...p_{m}^{k_{m}} ight) =Phi left( p_{1}^{k_{1}} ight)* Phi left( p_{2}^{k_{2}} ight)*...Phi left( p_{m}^{k_{m}} ight)
由上一小節n為質數的多次方的結論
Phi left( p^{k} ight)=p^{k}-p^{k-1}＝p^{k}(1-dfrac {1}{p} )
可以得出：
Phi left( p_{1}^{k_{1}} ight)* Phi left( p_{2}^{k_{2}} ight)*...Phi left( p_{m}^{k_{m}} ight)=p_{1}^{k_{1}}p_{2}^{k_{2}}...p_{m}^{k_{m}}*(1-dfrac {1}{p_{1}} )*(1-dfrac {1}{p_{2}})...(1-dfrac {1}{p_{m}} )

則
Phi left(n ight)=n*(1-dfrac {1}{p_{1}} )*(1-dfrac {1}{p_{2}})...(1-dfrac {1}{p_{m}})
此時我們仍然計算24互質個數則
Phi left(24 ight)=Phi left( 2^{3}*3 ight)=Phi left(2^3 ight)*Phi left(3 ight)=24*(1-dfrac {1}{2})(1-dfrac {1}{3})＝8

上面說的那麼多其實歸結起來就是這樣一個道理：當我們去求小於某個數范圍內與其互質的數的個數時候，無非就是把n分為質數還是非質數。

知道了歐拉函數，接下來我們再理解一個同餘概念，簡單來說也就是25除以3的余數為1，而1除以2的余數為1，則我們稱25與1對於模3同餘數，用人話來說就是25和1 除以2得到的余數都一樣。求余數的過程在數學里的黑話叫取模。所以才有上面那麼拗口的說法。但是不要緊，數學喜歡簡單不啰嗦，於是搞出了如下的表達式來表達上述說法：
25equiv 1left( mod 3 ight)
也就是說
25 \% 3 = 1\%3=1
注意到了嗎？上述表達式也可以這樣表述，即25除以3得到的余數為1.圍繞著同餘這個概念，歐拉大師結合他的歐拉函數活脫脫就搞出了個歐拉定理，我們來看看他有什麼發現？

另外根據取模運算的規則：
a^{b}\%p = ((a \% p)^{b}) \% p
我們還可以得出
（a^{Phi left(n ight)})^{k}equiv 1left( mod n ight)
因為
(a^{Phi left(n ight)})^{k} \% n=（a^{Phi left(n ight)}\%n)^{k}\%n=1^k\%n =1
我們舉個例子：比如
{Phi left(10 ight)}＝{Phi left(2*5 ight)}={Phi left(2 ight)}*{Phi left(5 ight)}=(2-1)*(5-1)=4

所以根據歐拉定理：因為9與10互質所以
9^{Phi left(10 ight)}=9^4equiv 1left( mod 10 ight)
於是(9^4 )^k 除以10都餘1。

如果a與n互質，則必然能夠找到一個數使得
abequiv 1left( mod n ight)
則b稱為a的模反元素，我們可以通過歐拉定理來給予證明
a^{Phi left(n ight)}=1left( mod n ight)
a^{Phi left(n ight)}= a*a^{Phi left(n ight)-1}equiv 1left( mod n ight)

模反元素的概念對後續在已知道公鑰情況下，計算合適的私鑰是有很重要的意義的。
掌握了這些數學知識，你可能覺得這些東西似乎很孤立，看不到任何作用和價值，不過接下來我們來看看RSA是怎麼運作的，你就會發現這些看似毫無作用的東西是如何產生價值的。

從加解密的表達式可以看出在，數學原理上公鑰和私鑰其實並沒有什麼差異。你可以用公鑰加密、私鑰解密，也可以用私鑰加密，公鑰進行解密。但是對於密碼學來說，對公鑰和私鑰會有不同的要求。
另外需要注意的是這里 明文數值不能大於等於N ，否則解密的結果並不會等於明文。

因為加密的公式為：
x^e mod n = y
而解密公式為
y^d mod n = x
從上面表達式可以看出在數學原理上公鑰和私鑰其實並沒有什麼差異。你可以用公鑰加密、私鑰解密，也可以用私鑰加密，公鑰進行解密。
所以根據：
y=x^e - kn
且因為Y^D mod N = x 所以
y^D equiv x (mod n)
所以確定能否加解密的過程本質就是證明：
（x^e - kn)^d equiv x (mod n) （1.1）
而根據二項式定理
[圖片上傳失敗...(image-ca75c7-1530364603810)]

（x^e - kn)^d 展開後演變為
x^ed-m_{1}x^{e(d-1)}kn+m_{2}x^{e(d-2)}(kn)^2...m_{n}(kn)^{d}
你會發現二項式展開後，唯有x^ed 沒有包含n，因此結合模運算加法運算規則(a + b) % p = (a % p + b % p) % p ，要想證明1.1的表達式，則必然證明：
x^{ed} equiv x (mod n)
由於
ed equiv 1 (mod {Phi left(n ight)})
所以
ed=h{Phi left(n ight)})+1
則從證明
x^{ed} equiv x (mod n) 演變為證明
x^{h{Phi left(n ight)}}*xequiv x (mod n)
如果x與n 互質則根據歐拉定理
x^{{Phi left(n ight)}}equiv 1 (mod n)
基於在歐拉定理中提及的，根據取模運算規則可以得出
x^{h{Phi left(n ight)}}equiv 1 (mod n)
仍然是基於取模運算乘法規則，我們又可以得出
x^{h{Phi left(n ight)}}xequiv x (mod n)
這樣原式得到證明。
那麼如果x與n不互質的情況下，因為n=p*q且p和q都是質數，所以n的因數只有p和q了，因為x與n不互質，那麼我們可以認為：
x=k_{1}p 0 < u< q
或者
x=k_{2}q 0 < k

請注意k值的取值范圍，這里要牢記一點明文值必須大於0且小於n值。
這里我們先姑且定義
x=kq
0 < k< p

那麼因為p與q都是質數，根據k<p 我們可以認為k與p是互質的，而p本身就是質數，所以根據費爾馬小定理（n
為質數，a與n互質，如果有所遺忘可以回到前面查看相關說明。）
a^{n-1}equiv 1left( mod n ight)
那麼
(kq)^{p-1}equiv 1left( mod p ight)
根據費爾馬定理我們推得出來的表達式
a^{Phi left(n ight)}equiv 1left( mod n ight)
得出
((kq)^{p-1})^{h*(q-1)}equiv 1left( mod p ight)
也就是
(kq)^{h*(q-1)(p-1)}equiv 1left( mod p ight)
根據取模運算的運算定義：

得出

(kq)^{h*(q-1)(p-1)} = 1+u*p
這里的u為任意整數，這時候兩邊都乘以kq
(kq)^{h*(q-1)(p-1)}*kq = 1+u*k*q*p
因為n=pq x=kq那麼
(x)^{Phi left(n ight)+1} = x+u*k*n
還是根據之前取模運算定義得出
(x)^{hPhi left(n ight)+1}equiv xleft( mod n ight)
即原式得到了證明。

之所以RSA是安全的，很大程度取決於n值是否足夠大以至於在已知公鑰e和模數n的情況下仍然難以找出d。根據之前的談及的密鑰對計算方式：
E*D equiv 1(mod M)
要想算出D就必須計算出M 而M = (p-1)(q-1) ，n=p*q則要算出M就需要知道p和q，即從一個龐大的數中分離出兩個也很大的質數。大數的素因數分解被認為是一個困難的問題，即使是現代的計算機也非常難於處理，所以許多加密系統的原理都是建基於此。
目前最安全的做法是選擇使用rsa-2048，隨著2009年12月12日，編號為RSA-768（768 bits, 232 digits）數也被成功分解。這一事件威脅了現通行的1024-bit密鑰的安全性。這里的2048表示的是模數N
的二進制位為2048位。而一般公鑰世面上普遍選擇65535，這是安全性和計算速度之間的綜合考慮下選擇出來的一個比較妥當的數值。因為加解密函數都是在做大數的指數運算，所以在工程方面會盡量考慮公鑰加解密的執行速度，畢竟公鑰是被外部使用的。
此外還記得前面提到rsa加密的明文數值大小不能大於N，或者其位數不能超過N的位數的限制。一旦超過密文解密後和原文數據不相匹配，這時候就需要採用分段加密技術。而另一方面明文的值也不能為0或1，-1因為這樣導緻密文也是0，1或者-1。另外也有一個問題即如果用私鑰解密一段非法數據，那麼得到是解密失敗還是一個毫無意義的解密內容呢？這時候需要採用 rsa padding技術。對這個概念理解可以參考 淺談RSA Padding 這篇文章。

通過學習一些簡單的數論知識即質數、歐拉函數、模反元素等概念後，我們也了解RSA演算法大致過程，總的來說公私密鑰對需要計算如下幾個數據：

RSA的安全性不僅僅建立於大數質因數分解困難這一理論基礎上，在工程上如何對上述這些數值的選取也是很大的學問。通過對rsa學習讓我對工程和理論之間的關系理解上更進一步。理論確定了方向的可行性，而工程實踐則要確保在有限資源下，理論結果是可以應用起來解決特定規模的問題。而在加密演算法領域，一旦工程實踐出現偏差，往往就容易產生安全漏洞，盡管演算法理論證明是安全的。比如rsa中p q值的選擇等。這里我羅列幾個工程問題有興趣的童鞋可以再進一步做探索：

『柒』 rsa演算法原理

RSA演算法是最常用的非對稱加密演算法，它既能用於加密，也能用於數字簽名。RSA的安全基於大數分解的難度。其公鑰和私鑰是一對大素數（100到200位十進制數或更大）的函數。從一個公鑰和密文恢復出明文的難度，等價於分解兩個大素數之積。

我們可以通過一個簡單的例子來理解RSA的工作原理。為了便於計算。在以下實例中只選取小數值的素數p,q,以及e，假設用戶A需要將明文「key」通過RSA加密後傳遞給用戶B，過程如下：設計公私密鑰(e,n)和(d,n)。

令p=3，q=11，得出n=p×q=3×11=33；f(n)=(p-1)(q-1)=2×10=20；取e=3，（3與20互質）則e×d≡1 mod f(n)，即3×d≡1 mod 20。通過試算我們找到，當d=7時，e×d≡1 mod f(n)同餘等式成立。因此，可令d=7。從而我們可以設計出一對公私密鑰，加密密鑰（公鑰）為：KU =(e,n)=(3,33)，解密密鑰（私鑰）為：KR =(d,n)=(7,33)。

英文數字化。將明文信息數字化，並將每塊兩個數字分組。假定明文英文字母編碼表為按字母順序排列數值。則得到分組後的key的明文信息為：11，05，25。

明文加密。用戶加密密鑰(3,33) 將數字化明文分組信息加密成密文。由C≡Me(mod n)得：
C1(密文)≡M1（明文）^e (mod n) == 11≡11^3 mod 33 ;
C2(密文)≡M2（明文）^e (mod n) == 26≡05^3 mod 33;
C3(密文)≡M3（明文）^e (mod n) == 16≡25^3 mod 33;
所以密文為11.26.16。

密文解密。用戶B收到密文，若將其解密，只需要計算，即：
M1(明文)≡C1（密文）^d (mod n) == 11≡11^7 mod 33;
M2(明文)≡C2（密文）^d (mod n) == 05≡26^7 mod 33;
M3(明文)≡C3（密文）^d (mod n) == 25≡16^7 mod 33;
轉成明文11.05.25。根據上面的編碼表將其轉換為英文，我們又得到了恢復後的原文「key」。

當然，實際運用要比這復雜得多，由於RSA演算法的公鑰私鑰的長度（模長度）要到1024位甚至2048位才能保證安全，因此，p、q、e的選取、公鑰私鑰的生成，加密解密模指數運算都有一定的計算程序，需要仰仗計算機高速完成。