|
|
樓主 |
發表於 2017-5-21 08:38:30
|
顯示全部樓層
本文章最後由 kip 於 2017-5-21 08:56 AM 編輯
RSA 加密步驟:
1. 選定兩個大的質數, p, q.
2. n= p*q
3. 計算 φ(n)= φ(p*q)=(p-1)*(q-1)， 這個計算就是找出小於或等於n的正整數中與n互質的數的總個數
4. 選定加密數，滿足 1 < e < φ(n) 且 e 與 φ(n) 互值
5. 找出解密數, 滿足 e*d ≡ 1 mod (n) => 翻成白話， e*d 除 n，其餘數 = 1
6. 加密公鑰 (n, e) 這兩個數字
7. 解密私鑰 (n, d) 這兩個數字
原訊息 m ，加密 c = m^e mod n
解密, m = c^d mod n
實例:
p = 73
q = 127
n = p*q = 9271
φ(n) = (p-1)*(q-1) = 9072
十進位 9072 = 二進位 10 0011 0111 0000 共 14位的二進位數。 所以此例做加密為 RSA-14 bit
選定 e = 6563。驗證 (6563, 9072) 互質
選定 d = 2795。驗證 6563*2795 ≡ 1 mod (9271)
公鑰: (9271, 6563)
私鑰: (9271, 2795)
例如原訊息:
Pigoo is cool.
ASCII code = 80 105 103 111 111 32 105 115 32 99 111 111 108 46
加密
80^6563 mod 9271 = 3264
105^6563 mod 9271 = 659
...
加密過後變成
3264 659 8704 3425 3425 4382 659 7783 4382 3451 3425 3425 5481 7546
解密過程
3264^2795 mod 9271 = 80
659^2795 mod 9271 = 105
...
商業應用時，還會選擇 pudding 方式，讓每次使用相同金鑰加密出來的結果不一樣。
好，問題來了，假如 沒有私鑰，那要怎麼解密?
苦功就是步驟 1 ~ 5 一步一步來。
最耗時的在哪? 在第一步!
當一個很大的正整數 n, 目前電腦沒有一個快速的演算法可以做出質因數分解成 p*q
這就是 RSA 目前很難被破解的原因所在。 |
評分
-
1
查看全部評分
-
|
/1 
發表於 2017-5-20 10:16:39
n_146|