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位的。 似興義培 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 幻世萌 線性... 幻想v飛翔 比如說 5 2 3 5 1 排序後可能是 5 5 3 2 1 也可能是5 5 3 2 1，前者是穩定的，後者是不穩定的。冒泡，選擇有穩定性，快拍沒有 資料結構中幾種常見的排序演算法之比較 冒泡。複雜度n平方。適用於陣列 插入排序。複雜度n平方。適用於連結串列 快排。複雜度nlog n 希...在RSA演算法中，已知p 3，q 11，公鑰 加密金鑰 e
資料結構中演算法分析的問題
資料結構中什麼是排序演算法的穩定性