※ 引述《sinker (0874)》之銘言：
: ※ 引述《chwang (無聲的所在)》之銘言：
: : 網路上有公開方式啦,我室友的專題也是那個啦..:P
: 自己看太慢了..你教我吧..
以下的話當然不是我說的,不過可以參考看看...:>
基礎理論:費馬小定理(假設a和p互質 ==> a^(p-1) mod p =1)
----------------------------------------------------------
首先, 找出三個數, p, q, r,
其中 p, q 是兩個相異的質數, r 是與 (p-1)(q-1) 互質的數......
p, q, r 這三個數便是 private key
接著, 找出 m, 使得 rm == 1 mod (p-1)(q-1).....(即rm mod (p-1)(q-1)=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, 所以這個過程確實能做到編碼解碼的功能.....
---------------------------------------------------------------------
還有一些事值得探討的
首先是質數的選取........
上一篇提到為了使因數分解發生困難, 所選擇的質數要愈大愈好,
但這也意味著, 質數的選取也同樣的困難......
因為就目前而言, 跟本沒有一個所謂的質數產生公式可用........
解析數論上有一個定理, 當 p 很大時, 質數的分佈密度與 1/log p 成正比,
也就是說一個質數和下一個質數的差平均而言與 log p 成正比.......
還好 log p 的成長並不會很快, 所以就採用一個方法 --- 暴力搜尋法....
一個數接著一個數找...... 直到找到質數為止.........
即使 n 大到 2^512, 所要花的時間也不會大到天文數字,
用 486 的話, 大概在數秒鐘至數十秒之內會找到..... (包括判定的時間)
現在有一個問題了..... 如何去判定一個數是否是質數........
咳....... 大哉問, 因為到目前為止, 並沒有一個很有效的方法來判定.......
當然有人會問, 為什麼不用試除法........
嗯...... 如果用這個方法, 2^512 這麼大的數, 大概要除個大於 10^30 年......
雖然如此, 但還是得去判斷啊........
有一個方法, 是利用費馬小定理去做判定的.......
假設一數 p, 如果 p 是質數, a^p == a mod p,
如果 p 不是質數, 那麼 a^p == a mod p 雖然也有可能成立,
但成立的機率非常小, 而且 p 愈大時機率愈小........
用這種方法, 我們就找一些質數來測定, 比如驗証
2^p == 2 mod p, 3^p == 3 mod p, 5^p == 5 mod p..... 等式是否成立....
如此一來, p 是質數的機率就變得非常非常高了.........
現在來討論 RSA 演算法編碼解碼的速度........
因為我們是對一些很大的數作計算,
所以, 一些加減乘除的運算, 必須自己寫成函式來處理這些事......
就 N-digit key 的資料而言, 加減法需要 O(N) 的時間,
乘除法需要 O(N^2) 的時間........
至於計算 a^b mod c, 則是需要 O(N^3) 的時間,
亦即, 要對 N-digit 的資料用 N-digit key 作編碼解碼,
是需要 O(N^3) 的時間........
一般的實作, N 是介於 512 至 1024 之間, (太小的話很有可能被因數分解開)
所以算算 N^3, 其計算量也是相當驚人的.......
這意味著, 用 RSA 演算法來編碼解碼其速度是非常慢的.......
既然 RSA 的速度很慢, 這就表示它並不適合所有情況.....
比如 ftp, 這就不適合全程使用 RSA 作編碼解碼.......
如何去改善速度? 還記得之前所提到的 DES 吧?
RSA 搭配上 DES 的話, 就可以彌補編碼解碼時速度太慢的問題了 :)
先前提到用 DES 作編碼解碼時, 雙方必須使用同一個 key.......
所以, 我們可以用 RSA 演算法將 DES key 送給對方,
而後接下來的資料, 就全部利用 DES 來做編碼解碼,
如此, 整個過程中, 因使用 RSA 而耗掉的時間就不會太多 :)
再者, 產生 RSA key 所耗掉的時間, 也是相當驚人的..........
先前提到, 以 N-digit key 為例, 兩個相鄰質數平均間隔為 O(N),
對於這些數, 我們要利用費馬小定理去判定是否可能為質數,
而計算 a^b mod c 所花的時間為 O(N^3),
所以算一算, 平均要找到一個 N-digit 質數, 需費時 O(N^4).......
所以在產生 RSA key 時也是一件非常耗時的工作.......
所以, 一般的作法是, 先花一大把時間去找 RSA key,
往後的編碼解碼就使用這一組 key.......
就以 stand-alone telnet daemon 為例好了,
可行的做法是 telnetd 一開始執行時, 先花時間運算出 RSA key,
之後 telnet 連上這個 telnetd 之後, 丟給 telnet 這個 RSA key (public),
然後 telnet 將 DES key 用這個 RSA key 編碼丟後回給 telnetd,
之後的通訊就用這個 DES key 作編碼解碼.........
========================================================================
發信人: tmg.bbs@sob.m7.ntu.edu.tw (海邊漂來的..海嘯), 看板: mapleplan
標 題: 糟了, RSA 演算法將於可預見的將來會被破解
發信站: 陽光沙灘 (Mon Nov 4 09:19:36 1996)
轉信站: sob!news.cs.nthu!sob
突然想起來幾個月前在物理版看到的一篇有關量子電腦的文章..........
從這篇有關量子電腦的文章中, 可以很清楚的知道一點,
就是 RSA 演算法在量子電腦之下, 將會很容易地被破解........
1993年, P. W. Shor 指出, 量子電腦可以做因式分解,
而且, 它所需要的計算時間, 只與該數的對數成多項式關係........
也就是說, 如果 RSA 演算法的 public key 的大小為 n bits 的話,
用量子電腦來做因式分解, 只要 P(n) 的時間就夠了, 其中 P 是一個多項式.
用傳統以圖靈機為架構的電腦來解, 必須花上 2^n 的時間才能分解......
這..... 分解的速度實在太快了, 而且, 量子電腦所使用的演算法,
一定在這幾年內會大大改進.........
所以不久的將來, 多項式 P 的階數一定會降得很可觀,
屆時 RSA 在量子電腦之下將毫無招架之力.........
為什麼量子電腦有辦法做到此一傳統電腦無法完成的工作?
原因是, 傳統電腦的架構本身是一台圖靈機 (turing machine),
而量子電腦已不只是一台圖靈機而已........
由於其利用量子特性, 使得它可以做到圖靈機無法做到的事,
就像用多項式時間去因式分解一個 n bits 的整數........
看來又要掀起一場革命了.........
還好, 現在量子電腦還只是在實驗室階段,
所以, RSA 可能還可以多撐個幾年.........
--
／＼█／＼ Origin:
// █ \ 陽光沙灘
█ (sob.m7.ntu.edu.tw)
--
※ 發信站: 批踢踢實業坊(ptt.twbbs.org)
◆ From: amethyst.Dorm13.NCTU.edu.tw