簡述RSA演算法中金鑰的產生,資料加密和解密的過程,並簡單說明RSA演算法安全性的原理

時間 2021-09-09 05:21:11

1樓:匿名使用者

rsa演算法的數學原理

rsa演算法的數學原理:

先來找出三個數, p, q, r,其中 p, q 是兩個相異的質數, r 是與 (p-1)(q-1) 互質的數。

p, q, r 這三個數便是 private key。接著, 找出m, 使得 rm == 1 mod (p-1)(q-1)..... 這個 m 一定存在, 因為 r 與 (p-1)(q-1) 互質, 用輾轉相除法就可以得到了.....

再來, 計算 n = pq....... m, n 這兩個數便是 public key。

編碼過程是, 若資料為 a, 將其看成是一個大整數, 假設 a < n.... 如果 a >= n 的話, 就將 a 表成 s 進位 (s <= n, 通常取 s = 2^t), 則每一位數均小於 n, 然後分段編碼...... 接下來, 計算 b == a^m mod n, (0 <= b < n), b 就是編碼後的資料......

解碼的過程是, 計算 c == b^r mod pq (0 <= c < pq), 於是乎, 解碼完畢...... 等會會證明 c 和 a 其實是相等的 :) 如果第三者進行竊聽時, 他會得到幾個數:

m, n(=pq), b...... 他如果要解碼的話, 必須想辦法得到 r...... 所以, 他必須先對 n 作質因數分解.........

要防止他分解, 最有效的方法是找兩個非常的大質數 p, q, 使第三者作因數分解時發生困難......... 《定理》 若 p, q 是相異質數, rm == 1 mod (p-1)(q-1), a 是任意一個正整數, b == a^m mod pq, c == b^r mod pq, 則 c == a mod pq 證明的過程, 會用到費馬小定理, 敘述如下: m 是任一質數, n 是任一整數, 則 n^m == n mod m (換另一句話說, 如果 n 和 m 互質, 則 n^(m-1) == 1 mod m) 運用一些基本的群論的知識, 就可以很容易地證出費馬小定理的........

《證明》 因為 rm == 1 mod (p-1)(q-1), 所以 rm = k(p-1)(q-1) + 1, 其中 k 是整數 因為在 modulo 中是 preserve 乘法的 (x == y mod z and u == v mod z => xu == yv mod z), 所以, c == b^r == (a^m)^r == a^(rm) == a^(k(p-1)(q-1)+1) mod pq 1. 如果 a 不是 p 的倍數, 也不是 q 的倍數時, 則 a^(p-1) == 1 mod p (費馬小定理) => a^(k(p-1)(q-1)) == 1 mod p a^(q-1) == 1 mod q (費馬小定理) => a^(k(p-1)(q-1)) == 1 mod q 所以 p, q 均能整除 a^(k(p-1)(q-1)) - 1 => pq | a^(k(p-1)(q-1)) - 1 即 a^(k(p-1)(q-1)) == 1 mod pq => c == a^(k(p-1)(q-1)+1) == a mod pq 2. 如果 a 是 p 的倍數, 但不是 q 的倍數時, 則 a^(q-1) == 1 mod q (費馬小定理) => a^(k(p-1)(q-1)) == 1 mod q => c == a^(k(p-1)(q-1)+1) == a mod q => q | c - a 因 p | a => c == a^(k(p-1)(q-1)+1) == 0 mod p => p | c - a 所以, pq | c - a => c == a mod pq 3.

如果 a 是 q 的倍數, 但不是 p 的倍數時, 證明同上 4. 如果 a 同時是 p 和 q 的倍數時, 則 pq | a => c == a^(k(p-1)(q-1)+1) == 0 mod pq => pq | c - a => c == a mod pq q.e.

d. 這個定理說明 a 經過編碼為 b 再經過解碼為 c 時, a == c mod n (n = pq).... 但我們在做編碼解碼時, 限制 0 <= a < n, 0 <= c < n, 所以這就是說 a 等於 c, 所以這個過程確實能做到編碼解碼的功能.....

2樓:匿名使用者

rsa方法的工作原理如下:

1) 任意選取兩個不同的大質數p和q,計算乘積r=p*q;

2) 任意選取一個大整數e,e與(p-1)*(q-1)互質,整數e用做加密金鑰。注意:e的選取是很容易的,例如,所有大於p和q的質數都可用。

3) 確定解密金鑰d:

d * e = 1 mod(p - 1)*(q - 1)

根據e、p和q可以容易地計算出d。

4) 公開整數r和e,但是不公開d;

5) 將明文p (假設p是一個小於r的整數)加密為密文c,計算方法為:

c = pe mod r (e為冪次方)

6) 將密文c解密為明文p,計算方法為:

p = cd mod r (d為冪次方)

然而只根據r和e(不是p和q)要計算出d是不可能的。因此,任何人都可對明文進行加密,但只有授權使用者(知道d)才可對密文解密。

例:選取p=3, q=5,試計算出d和e分別是多少?假定明文為整數13,請給出密文數字.

解:如果選取p=3, q=5,則r=15,(p-1)*(q-1)=8。選取e=11(大於p和q的質數),通過d * 11 = 1 mod 8, 計算出d =3。

假定明文為整數13。則密文c為 (e為冪次方)

c = pe mod r = 1792160394037 mod 15 = 7

復原明文p為: (d為冪次方)

p = cd mod r = 343 mod 15 = 13

簡述rsa體制金鑰的生成及其加密、解密演算法。

3樓:匿名使用者

rsa體制金鑰的生成:

1. 選擇兩個大素數,p 和q 。

2. 計算: n = p * q (p,q分別為兩個互異的大素數,p,q 必須保密,一般要求p,q為安全素數,n的長度大於512bit ,這主要是因為rsa演算法的安全性依賴於因子分解大數問題)。

有尤拉函式 (n)=(p-1)(q-1)。

3. 然後隨機選擇加密金鑰e,要求 e 和 ( p - 1 ) * ( q - 1 ) 互質。

4. 最後,利用euclid 演算法計算解密金鑰d, 滿足de≡1(mod φ(n))。其中n和d也要互質。

數e和n是公鑰,d是私鑰。兩個素數p和q不再需要,應該丟棄,不要讓任何人知道。

加密、解密演算法:

1. 加密資訊 m(二進位制表示)時,首先把m分成等長資料塊 m1 ,m2,..., mi ,塊長s,其中 2^s <= n, s 儘可能的大。

2. 對應的密文是:ci ≡mi^e ( mod n ) ( a )

3. 解密時作如下計算:mi ≡ci^d ( mod n ) ( b ) rsa 可用於數字簽名,方案是用 ( a ) 式簽名, ( b )式驗證。

網路安全 簡述rsa演算法的原理和特點

rsa演算法的原理及演算過程?

4樓:我在說謊

rsa演算法非常簡單,概述如下:

找兩素數p和q

取n=p*q

取t=(p-1)*(q-1)

取任何一個數e,要求滿足e

這樣最終得到三個數: n d e

設訊息為數m (m

設c=(m**d)%n就得到了加密後的訊息c設m=(c**e)%n則 m == m,從而完成對c的解密。

注:**表示次方,上面兩式中的d和e可以互換。

在對稱加密中:

n d兩個數構成公鑰,可以告訴別人;

n e兩個數構成私鑰,e自己保留,不讓任何人知道。

給別人傳送的資訊使用e加密,只要別人能用d解開就證明資訊是由你傳送的,構成了簽名機制。

別人給你傳送資訊時使用d加密,這樣只有擁有e的你能夠對其解密。

rsa的安全性在於對於一個大數n,沒有有效的方法能夠將其分解從而在已知n d的情況下無法獲得e;同樣在已知n e的情況下無法求得d。

rsa簡潔幽雅,但計算速度比較慢,通常加密中並不是直接使用rsa 來對所有的資訊進行加密,

最常見的情況是隨機產生一個對稱加密的金鑰,然後使用對稱加密演算法對資訊加密,之後用

rsa對剛才的加密金鑰進行加密。

最後需要說明的是,當前小於1024位的n已經被證明是不安全的自己使用中不要使用小於1024位的rsa,最好使用2048位的。

在RSA演算法中,已知p 3,q 11,公鑰 加密金鑰 e

似興義培 n pq 33 phi n p 1 q 1 2 10 20 ed 1mod phi n 用擴充套件歐幾里德可求出d 3 直接看出來也可以.加密密文c m e n 5 7 20 5 解密明文m c d n 5 3 20 5 經玥源賦 n p q 33 phi p 1 q 1 20 e 7e ...

資料結構中演算法分析的問題

武當單挑王 第一個第二個問題,就相當於你高中學的f x 沒什麼實際意義,也不用糾結 為什麼用t表示呢,代表時間 而一般所說的時間複雜度,都是用大o表示的 你學過函式應該知道,次數最高的那項對函式的增長影響最大,所以這裡可以忽略其他低次項 前面的係數也可以省去,對於這個程式的就是o n2 幻世萌 線性...

簡述汽車故障診斷中資料採集的作用有哪些

作用是驗證對故障初步診斷的正確性 捕捉疑點,針對沒有故障碼的故障 捕捉偶發故障的原因 捕捉故障發生的過程 捕捉多因果的原因點 驗證修理後的結果等。在進行汽車故障診斷時,常用一些診斷參數列徵汽車 總成及機構的技術狀況,如汽車的工作過程引數和伴隨工作過程的狀態引數。利用車載計算機 使隨車故障診斷技術不斷...