數論在密碼上的應用 (第 4 頁)

　1│2│3│4│5│6　

數論在密碼上的應用（第 4 頁）

楊重駿;楊照崑

首頁 | 搜尋

．原載於數學傳播第七卷第二期、第七卷第三期
．作者當時任教於美國海軍研究實驗所;美國佛羅里達大學統計系
‧對外搜尋關鍵字

四、瑞未斯特、希米爾、愛得曼（Rivest, Shamir, Adleman）法

這個方法是上列三位科學家在1978所發表的，其步驟如下（又如圖2）

1.收報者取兩個相異的大質數p、q及另一與(p-1)(q-1)互質的數a，且a<w令

w=(p-1)(q-1),

m=pq

及p、q之較小者的位數（十進位）為k。

2.（公開）告訴發報者k，m與a。

3.發報者將他的信號分成許多段，每段含k-1位數（十進位）（若k=3（即p、q均為不小於二位的數），則信號

331414320001

則應分成

33,14,14,32,00,01

一個一個的考慮發出），設發報者的信號之一為x（k-1位數，即上例中之33，或14，或32，…），則他將它作成

$\begin{displaymath} c\equiv x^a \pmod{m} \end{displaymath}$

發出。

4.收報者收到c之後，即可把原有的x求出來，因a與w互質，由定理2.2及系知，我們可找到二整數d、e；d>0使得

ad+we=1

令

$\begin{displaymath} y\equiv c^d \pmod{m} \end{displaymath}$

則此y即發報者之x。我們先證明 y=x。

$\begin{displaymath} y\equiv c^d\equiv (x^a)^d\equiv x^{ad}\equiv x^{1-we} \equiv x(x^{-we}) \pmod{m} \eqno{(4.1)} \end{displaymath}$

但因 w、a、d 均為大於 1 之整數，故 e 必為一負數，即 -e 為一正數，又因x小於質數 p、q，故 x 同 m 互質，由定理2.3之系得

$\begin{displaymath} x^w\equiv x^{(p-1)(q-1)}\equiv 1 \pmod{m} \end{displaymath}$

但因y與x均取小於m之數，故y=x。故本程序之正確性得證。

圖2 （RSA製碼法）在此作業程序中，m,a,c₁,…,c_n 是公開的。

這種密碼之關鍵在於p、q為兩大質數時，分解m成為p、q為一件極費時的工作，若分解不開m，則找不到w與d，因此就無法從c解得x，在不久以前，要分解一個數的因子仍停留在近乎硬試的階段，即要從2，3，5，7，…，一直試到 $\sqrt{n}$ 附近才停止。若n是50位數而p、q均近25位數，則分解m要除約10²⁵次，若以電子計算機以每秒10⁶次的高速運算，這仍是一個10¹¹年的工作，目前由於大家對這方面的重視，分解一個50位數的時間已可縮短至10¹⁰次運算。下面的表中列出了目前(1980年)，分解一個大數大概所需的時間。

m的位數	分解m的最少運算次數	最快（1980年）電腦所費的時間
50	1.4 x 10¹⁰	3.9小時
70	9.0 x 10¹²	104天
80	1.3 x 10¹³	150天
100	2.3 x 10¹⁷	74年
200	1.2 x 10²³	3.8 x 10⁹年

若取pq各為40位數在目前已經十分安全了，即使是25位數，在商業上也十分安全，因為3.9小時最快電腦的計算費用也是一筆大的財富。

讀者也許要問這種大質數是否很多，而且容易找到?答案是:大質數既多而又容易找，前面已談到找一個大質數不宜用硬除的辦法，但因找它們所用的定理比我們已證明的幾個要難，我們將在下節中才介紹出來。我們只談一下質數之多，依據質數定理在1與n之間的質數約有 $\frac{n}{\ln n}$ 個，因此小於10⁴⁰(即40位)的質數約有

$\begin{displaymath}\frac{10^{40}}{\ln 10^{40}} =\frac{10^{40}}{92.1}\geq 10^{38}... ...inus0.2pt{\fontfamily{cwM0}\fontseries{m}\selectfont \char 95}}\end{displaymath}$

這又是一個天文數字，因為一個一千頓電子計算機中所含的原子數不過10³¹左右，可見這種密碼之難以捉摸了。現取兩個用來做密碼的十五位質數以饗讀者:

$\begin{displaymath}p=5862031427\, 1421210354\, 0772438083\end{displaymath}$

$\begin{displaymath}q=7976488510\, 8326808223\, 7297393713\end{displaymath}$

要分解

$\begin{displaymath} \begin{array}{rcl} m&=&pq \\ &=&4675842632\, 8739231725\, 4... ...0844 \\ &&8514393251\, 3976539392\, 0565972179 \\ \end{array}\end{displaymath}$

若不懂數學與計算機，則是談何容易。在本節結束之前，我們也舉一個例子，當然我們不會用上列的大質數，我們且取p、q均為兩位數，令

p=47,q=59

則

m=pq=47 x 59=2773

w=(p-1)(q-1)=2668

取a=157，由輾轉相除可得

$\begin{displaymath}17a-1w\equiv 1\end{displaymath}$

故

d=17

故收方發出的密碼法是

m=2773,a=157,k=2

此時發方必須一位一位的發出信號，設第一個要發的信號是3，則他要發出的是

$\begin{displaymath} c\equiv x^a\equiv 3^{157} \pmod{2773} \end{displaymath}$

c之求法主要在將157分成2進位數並用定理2.1即

$\begin{displaymath} x^2 \equiv (x \pmod{m})^2 \pmod{m} \end{displaymath}$

因 157=2⁷+2⁴+2³+2²+1，而

$\begin{displaymath} \begin{eqalign} 3 &\equiv 3 \pmod{2773} \\ 3^2 &\equiv 9 ... ...\ 3^{2^7} &\equiv 2027^2 \equiv 1916 \pmod{2773} \end{eqalign}\end{displaymath}$

故

$\begin{displaymath} \begin{array}{rcl} 3^{157}&\equiv &1916\times 1442 \times 10... ...imes 3 \pmod{2773} \\ &\equiv &441 \pmod{2773} \\ \end{array}\end{displaymath}$

因此 c=441 即發方發出之信號，當收方收到 441 之後，用同樣的運算法可得 c^d 為

$\begin{displaymath} \begin{array}{rcll} 441^{17}&\equiv &441^{2^4+1}& \pmod{2773... ...es 441& \pmod{2773} \\ &\equiv &3& \pmod{2773} \\ \end{array}\end{displaymath}$

解碼完成:由上面的運算可知若沒有電子計算機，則解與做這種密碼是何等的辛苦。

　1│2│3│4│5│6　


	（若有指正、疑問……，可以在此留言或寫信給我們。）

EpisteMath (c) 2000 中央研究院數學所、台大數學系
各網頁文章內容之著作權為原著作人所有

編輯：陳文是 ∕ 繪圖：簡立欣

最後修改日期：6/17/2002