數論在密碼上的應用

一、前言
數論，顧名思義，是一門研究數字性質的學問。一般所謂的數論，特指正整數(即自然數)的許多性質，像質數的分佈，方程式的正整數解，韓信點兵，及進位法都包括在數論裏面，我們在小學時候學的分解因數，最大公約數也是數論的一部分，可惜因為數論在日常生活中沒有什麼直接的用處，在中學數學裏很少提到數論，一般被認為是一種「純數學」，深而無用。可是「無用之用，真乃大用」，終於在一九七0年代後期，幾個電機工程師用數論的一些基本定理，製成了一種新的密碼。這種由數論所作成的密碼與以前人們所用的密碼，有著根本性質上的不同，可說是密碼史上一個空前的革新。
密碼通訊在軍事上的用途是大家都知道的，但由於交通的發達，在分秒必爭的工商業社會裏，商業上的情報也已成為商業盈利的主要依靠。譬如說，有人早幾個小時知道什麼公司有了一種新的發明，或某兩個公司計劃合作，或某地區有物價的大波動，就可以在股票上上下其手， 轉瞬之間收進大筆的財富。因此公司本身內部及公司與公司之間的通訊都希望能對外嚴守機密。但由於現在通訊無論是有線或無線都很容易被敵方竊聽，因此公司必須對情報加鎖，即所謂密碼通訊。
以往人們在軍事上所用的密碼其基本的形式在於「代換」與 「置換」。譬如說，我要發出下面一個消息給你，
「我有一個秘密對你說」
我就先把這幾個字換成數字，即一般電碼本上的代碼，假定「我」字的代碼是3314,「有」字的代碼是1432，「一」字代碼是0001，等等，則上面那句話就成了
331414320001 …
代換密碼是把 0,1,2,…,9 十個數字互換，譬如我們可以把 0 換成 2，1 換成 3，等等，若用群論的符號表示，上面的代換可寫成

這個表示法是上行為 0，1，2，…，9，而下行是他們代換成的新數字，即02,13，25,…。因此剛才的電碼若用G法代換，則成了

這時一個不知道這個代換規則的人看到了上面的信號，他就不能從電碼本子裏找出它的原意了。置換法在於把密碼排成一種雙方都知道的形式，如下圖

則發出的信號為755772433216623，同樣的，不知道這種特定圖案的人，很難解開原來的信息。以代換法為例，像G這類的轉換可以有10!=3,628,800種不同的變化，假定我們可以在一分鍾內試一種代換，又假定我們的運氣中等，在試到一半時即10!/2=1,814,400時可以成功，則在不吃、不睡、不錯的情形下，我們要試3年零165天，等迷解出來的時候，仗早已打完了。但這只是最基本的密碼而已，在生死關頭，更難解的密碼必然出籠，例如在代換法中，若兩位兩位的代換(即0079,0185,…)則其變化可達100!=9.32 x 1057種之多， 如果我們再用硬試的方法，則一百萬人同心協力也得用6 x 1048年才能試出謎底，可是地球的年齡不過只有5 x 109年而已。
因此解密碼，都不用硬試的方法去解。一般可用統計的方法根據名字(或字母)出現的頻率及發生的事件加以分析，例如在英語中，各字母出現的頻率按多少排列是

因此一個出現次數最多的符號就很可能代表 e，出現次多的符號就很可能代表a，並以此類推，但道高一尺， 魔高一丈，如果不斷地變化代換的方法，譬如說前一百個字用代換法G1， 第二個一百個字用代換法 G2，則頻率方法亦失去功效。但是魔高一丈， 惡魔又高一丈，重賞之下，天下尚沒有絕對解不開的密碼。二次大戰時， 美國密碼兼統計學家弗立得門(W.F. Friedman)，在一年半的時間完全破獲了日軍的密碼。 在中途島一戰，美國海軍以劣勢的軍力，大勝日本皇家海軍 (讀過參加該戰役的日本軍官淵田美津雄及奧宮正武所著的《中途島》一書嗎?)。另外英國也幾乎在同時解開了德軍的密碼，做到了知己知彼的優勢地位(知己知彼並不一定百戰百勝，但總比不知彼要好得多。)過去這類密碼的特質(也可以說是缺點)在於它們是關閉式的製解法，即收發雙方都必須同時知道這種密碼的構造。因此如果在一通訊系統中有一個聯絡站被間諜滲入或被敵人佔領，則密碼的機密可能全盤暴露。而現在用數論的密碼卻是公開式的 (Public-Key Cryptography)，即是只有收方知道密碼的解法， 發方只需要知道做法而已，而且這種製法可以公開。因此即使發方被捕，敵人仍榨不出解密碼的機密來，其程序是這樣的：
1.收方先告訴發方如何用把情報做成密碼(敵人也聽到了這個做法)
2.發方依法發出情報的密碼(敵人也聽到了這個信號)
3.收方解開此密碼為原信息(但敵人卻解不開此密碼)
當然把收發互換，就可以互通信息了。剛才說過這種方法最大的好處就是只有一方知道解碼的秘訣，比以前收發雙方都知道秘訣的保密性高多了，自從這類的密碼法發表之後，在美國軍事界、教育界、工商業界引起了一個蔚然大波。對大多數的數論而言則是一則以喜，一則以懼。喜的是，皇天不負苦心人，一向不容易找到飯吃的數論家突然成為許多經費充裕的軍工商界所爭取的對象。費馬、尤拉以及那些一生窮困而已作古了的數論家可以含笑九泉了。但懼的是，由於這些理論在軍事通訊上的價值，有關這方面的新發現已被視為國防機密而列為管制了。以往各國數論家無憂無慮發表論文自由交換意見的日子也許是一去不返了，前程固然似錦，往事卻是如煙，純數學最後一塊淨土也終於被實用所「污染」了。然而這次因密碼而推動大家對數論的研究，將在數學史上寫下了有趣的一頁。
這種密碼所用的數論並不深，我們可以全部介紹出來，當然在實際用的時候，數字會大得多，但在大小型電子計算機如此普遍的今日，是不會成問題的。
在我們介紹兩種主要的數論密碼之前，我們先將介紹一點數論。
二、因子、質數、同餘式與費馬、尤拉定理
若 m,n 為兩整數，且 m>0，則以 m 除 n 可得二整數 α 與 r，使得

其中 α 稱為商，r 稱為餘數，且 。若 r=0，則我們說 n 可被 m 所整除，m 為 n 之因子，n 為 m 之倍數，若一數除 1 與本身之外無其他因子，則此數稱為質數，例如 2,3,5,7,11 都是質數，4,6,9,12 卻不是質數。我們定義 n 與 s 對 m 有同餘數：

如果 n 與 s 被 m 除時有相同的餘數。例如

有一個關於同餘式的簡單定理，我們把它們列出來，讀者很容易證出來。
定理2.1
若 ， ， 則 。
若兩正整數 p,q 的最大公因子(約數)是 1，則我們稱 p,q 互質，以
(p,q)=1
表示之。現在我們要證一個有關兩個互質數的一個基本定理。
定理2.2
若兩正整數 p,q 互質，則可以找到二整數(不一定正) a,b，使得
ap+bq=1
證明：
令 A 為含所有 x=ap+bq>0，a,b 為整數之集合，此集合顯然不是空集合，因可取a=b=1,p+g>0。令d為此集合中之最小者，若d=1，則本定理得證，若d>1，令ap+bq=d>1，則任取此集中之另一數。 a'p+b'q，則我們若以d除a'p+b'q，則得

代入
d=ap+bq
則得

此r必為0，否則r為A集中一小於d之數，與假設d為最小數相矛盾，因r=0故d為A集中任何一數之因子。因

故d為p，q之公因子。但p，q之最大公因子為1，故d=1，定理證畢。
這是一個極有用的定理，讀者也許要問，我們如何找到a與b使ap+bq=1呢?一般可用輾轉相除法。
例：
找整數 a,b，使得 5a+9b=1。因

故
1=5-4=5-(9-5)=2 x 5-9 x 1
故

系2.2
若w與m為二互質的正整數且m>w，則可找到一正整數θ使得

證明：
由定理知，有 a、b 二整數使得aw+bm=1，因bm為m之倍數，故

令

則得

因θ不可能為0，故本系得證。
最後我們要用到一個不容易證明的「費馬、尤拉 (Fermat-Euler) 定理」。但因為我們只用到這個定理比較容易證明的特殊形式，我們就只證明簡單的部分。
定理2.3
若m為質數，w為任一與m互質之整數，則

證明：
先把w寫成w個1的和，則由多項式定理知

之展開式中除w個1之外，都含有m之因子，(m為質數m!中之m不可能消去)，故

兩邊乘以系2.2中之a，即

得

本定理證畢。
系2.3
若 m 為二質數 p、q 之積，w 為任一與 m(即同時與 p 與 q 互質之整數，則

證明：先用定理之證明法得

由定理2.1可得

即

即

因wp-1與m互質，由系2.2之證明可知存在一 a 使 ，上式乘以a得

即

本系證畢。
我們還要利用到另一個簡單的定理，我們也在這節裏把它證完。
定理2.4
令 (a1,a2,…,an) 為一含n個正整數的數列，並滿足

又令 (x1,x2,…,xn) 為一由0與1組成的數列，即所有的xi不是0就是1，現設a1，a2，…，an為已知，x1，x2，…，xn為未知，c為一正整數，則方程式

只有一解或無解。
證明：
設此方程式有二解 (x1,x2,…,xn) 及 (x1',x2',…,xn') 則消去 c 之後可得

因

且

故an之係數必為0，即xn=xn'，因此

同理可得

此兩解原為一。本定理得證。
而要解(2.2)是非常容易的事，因為若

則xn必為1，否則必為0，同理若

則xn-1必為1，否則必為0，以此類推，一下子就解出來了。
這幾個定理就足夠瞭解新的密碼法了。
三、狄飛、赫爾曼、麥克兒(Diffie, Hellmon, Merkle)法
此法是由上列三位電機工程師兼數學家（科學本是一家，觸類旁通，稱他們是什麼家並不正確，也不重要）， 在1976及1978年所發表的方法。在此方法中，所有的信號必須寫成二進位的形式， 例如前面的我字代碼3314,若以二進位表示則為

即
110011110010
我們將任何一位信號分成許多段，每段含n個0與1的數，即(x1，x2，…，xn)，以下是本密碼法的收發程序(參看圖1)
1.由收報者秘密的取一組滿足定理2.4的正整數列(a1，a2，…，an)及任一大於 的質數m，及另一數w，令

2.(公開)發出(a10,a20,…,an0)給發報者(敵方可以知道)
3.發報者用a10，a20，…，an0與要發的0，1信號x1，x2，…，xn,求出

並將c0之值告訴發報者(敵方可以知道c0)
4.收報者收到c0之後，可以解出原信號x1,x2，…，xn(而敵方卻不容易用已知的a10，a20，…，an0及c0解出信號，原因馬上會談到)。
圖1 在此種操作中，敵方僅知（a10,…,an0）及 c0，而發方除了自己的信號外並不比敵方多知道什麼密碼的機密；只有發方完全掌握了解碼的方法。
我們先看收方如何解出xi，由定理2.2之系可知存在一且 (mod m)若將收到之信號方程式兩邊乘以θ可使

變成

但

故令

(3.2)即成為

因 ，上式與c=x1a1+x2a2+… +xnan相同，根據定理2.4之說明，一下子就可以解出x1，x2，…,xn可是敵方在整個的過程中知道(3.1)之關係，因ai0並不見得是一個有ai那樣規則的數列，到目前為止只有硬試一途，即

等一個一個的試，對小的n這並不難，但對大的n而言，譬如說n=1000(這並不是一個很長的信號)，則平均要試21000-1=10301次才可以解開，這是一個天文數字，若電腦在一秒鐘內可以做一百萬次檢驗(目前尚辦不到) ，則一年只可以做 3.15 x 1013檢驗，那麼要解開(3.1)需要10288年，前面談過地球的年齡不過5 x 109年而已，我們且舉一個簡單的例子。
例：令n=5,(a1，a2，a3，a4，a5)=(1,3,6,12,25)，w=13，m=51，則收方發出的密碼法(a10，a20,a30，a40，a50)分別為

這即是發報者收到的作密碼的a0，假定發方所要發的情報是10101，則因
c0=13+27+19=59
故收方所收到的密碼是59，要解開此碼，收方先得找到θ使 (mod 51)。用輾轉相除法很快得到θ=4，故收方所要解的是

即
32=x1+3x2+6x3+12x4+25x5=1+6+25
即原信號為10101，至於敵方所要解的是
59=13x1+39x2+27x3+3x4+19x5
這自然不算太難，但我們可以看見 ai0 失去了任何規則，當 n 很大時就不容易解開了。
四、瑞未斯特、希米爾、愛得曼（Rivest, Shamir, Adleman）法
這個方法是上列三位科學家在1978所發表的，其步驟如下（又如圖2）
1.收報者取兩個相異的大質數p、q及另一與(p-1)(q-1)互質的數a，且aw=(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，…），則他將它作成

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

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

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

但因y與x均取小於m之數，故y=x。故本程序之正確性得證。
圖2 （RSA製碼法）在此作業程序中，m,a,c1,…,cn 是公開的。
這種密碼之關鍵在於p、q為兩大質數時，分解m成為p、q為一件極費時的工作，若分解不開m， 則找不到w與d，因此就無法從c解得x，在不久以前，要分解一個數的因子仍停留在近乎硬試的階段，即要從2，3，5，7，…，一直試到附近才停止。若n是50位數而p、q均近25位數，則分解m要除約1025次，若以電子計算機以每秒106次的高速運算，這仍是一個1011年的工作，目前由於大家對這方面的重視，分解一個50位數的時間已可縮短至1010次運算。下面的表中列出了目前(1980年)，分解一個大數大概所需的時間。
m的位數分解m的最少運算次數最快（1980年）電腦所費的時間
501.4 x 10103.9小時
709.0 x 1012104天
801.3 x 1013150天
1002.3 x 101774年
2001.2 x 10233.8 x 109年
若取pq各為40位數在目前已經十分安全了，即使是25位數，在商業上也十分安全，因為3.9小時最快電腦的計算費用也是一筆大的財富。
讀者也許要問這種大質數是否很多，而且容易找到?答案是:大質數既多而又容易找，前面已談到找一個大質數不宜用硬除的辦法，但因找它們所用的定理比我們已證明的幾個要難，我們將在下節中才介紹出來。我們只談一下質數之多，依據質數定理在1與n之間的質數約有 個，因此小於1040(即40位)的質數約有

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


要分解

若不懂數學與計算機，則是談何容易。在本節結束之前，我們也舉一個例子，當然我們不會用上列的大質數，我們且取p、q均為兩位數，令
p=47,q=59
則
m=pq=47 x 59=2773
w=(p-1)(q-1)=2668
取a=157，由輾轉相除可得

故
d=17
故收方發出的密碼法是
m=2773,a=157,k=2
此時發方必須一位一位的發出信號，設第一個要發的信號是3，則他要發出的是

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

因 157=27+24+23+22+1，而

故

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

解碼完成:由上面的運算可知若沒有電子計算機，則解與做這種密碼是何等的辛苦。
五、如何尋找大質數
現在也許你有興趣學一點難一些的數論定理了。
定理5.1
設 a,m 互質，且

則

證明：
因 (mod m)而a不含m之因子，故b-c必為m之倍數即(modm)本定理得證。
定義
設 m 為任何一正整數，定義  為所有小於 m 且與 m 互質的自然數的數目，例如取 m=5，則小於 m 又與m互質的數為 1,2,3,4，故，又如取m=12，則小於 m 而又與 m 互質的數為 1,5,7,1l，故 。 一般稱為尤拉函數，是數論中一個重要的函數。
定理5.2
設m為一自然數表示所有小於m且與m互質的自然數，又以 r1，r2，…，表示這些自然數。 。如果a與m互質，則 ar1，ar2，…  對  而言是 r1,r2,…, 的一個排列。
證明：
令  且 ，則
ari=qm+xi
因 ari 與 m 互質，故 xi 必與 m 互質，因此 xi 是 r1,r2,…, 中的一員，但由定理5.2知  之充要條件為 ，故所有的 xi 皆不相同，本定理得證。
定理5.3（費馬、尤拉定理）
設 w 與 m 為兩互質之自然數， 為尤拉函數，則

證明：
由定理5.2知

即

因 與m互質，故

本定理得證。(此定理為定理2.3之推廣，因m為質數時，)
我們又可以推廣定理2.2，若以 (a,b) 表示 a,b 之最大公約數(公因子)，若d=(a,b)，則存在兩整數 x,y 可使
ax+by=d
這個證法與定理2.2極相似，求法也是用輾轉相除法。
定理5.4
設 a,m 為兩個互質之正整數且 1，則 k 與 不互質。
證明：
設A為所有且

之集合，因，故A非空集合。令d為A中之最小一員，因， 故 ，即d>1。設 ，令 k=qd+r，，顯然由  可得

但因d為此集合中之最小者，故r=0，即k必為d之倍數，且因， 可知(k，)，故k與不互質。
現在我們終於走到了最後一個求證某數是質數的定理。
定理5.5 (魯克斯(Lucas)定理)
若 m 為大於 1 之整數，a 為任一與 m 互質之數， 若 ，且對所有的 (m-1) 因子而言，  則 m 必為一質數。
證明：
設 m 不是質數，則由  之定義可知 ，但由於 a,m 互質，由定理5.3知 ，由已知條件及前定理知

故d為m-1之一因子，由(5.1)知存在二整數 x,y 使得

即

故(m-1)有一因子使得 ，與假設相矛盾，故m必為質數，本定理證畢。
這個定理若用來檢定一已知數m是否是質數並不容易，因為m-1的因子往往不易找到 ，前面已談過要分解一個大數的因子是件極費時的事，但這個定理來找一些大質數卻很容易 ，例如我們令
m=2n+1
則m的因子只有2，22…，2n個，若我們能試一試一個可能與m互質的數a，像3，5，7之類的而且證得

但

則m必為質數。原因是若

則對所有的 k。 （假如  則 。）
對一個固定的a而言，這個整個檢驗過程不過一次驗定a與m互質， 二次  而已，比硬除不知快了多少倍。
例：
若令 m=2n-1，則我們若能試出一與m 互質的數 a 像 3,5,7,… 而也證得

且

及

則m必為一質數(因m-1=2n-2=2(2n-1-1))目前最大的質數多半都是這樣求得的， 在1979年納爾遜與斯羅溫斯基 (H. Nelson & Slowinski) 用電子計算機證明244497-1 是一個 13,395 位的質數。 若以 100 元一千字作稿費，把這個數寫出來就是一千三百元，《數播》一頁大約二千字，所以把這個字寫出來要佔去六頁半的篇幅。
例：
若p為一質數，s，t為兩正整數，m=2spt+1則我們若能試出一個與m互質的數a並證得

且


則m為一質數。
例：
若 p,q 為兩質數，m=2pq+1，則我們若能試出一個與m互質的數d並證得



及

則m為一質數。
如此這般，我們可以由小而大滾雪球式的很容易的找到許多大質數，由於走的路徑千變萬化，所可能找到的大質數也是一個天文數字。當然電子計算機是不可少的工具。在定理5.5中我們只要求任何一個與m互質的a，因此什麼與m互質的a都可以，根據一般的經驗，若m是質數，很快就可以找到一個小的a像3，5，7之類的滿足定理5.5，若不成功，就可以放棄另找了，反正侯選的m多得不得了，最近有一個極巧妙的結果由Lehmer, Soloorary與Shassen同時發現。即若m不是質數，則至少有一半以上的數從2，3，…，到m-1不能滿足 (mod m)，可惜我們沒有辦法在本文中證明此一結果。這個結果在另一個角度看來，即一個不是質數的m只有很小的機會能通過許多小的a。我們最後舉一個數字的例子。
例：
257=28+1是不是質數?
因m-1=28，故我們若能找到一個與m互質的a且


m即為質數。m=275不是3的倍數，我們先取a=3，我們一步一步的求 與 。
k2k 
020=1
121=2
222=4
323=8
416
532
664
7128
8256
故257是一個質數。
六、結尾的話
前面說過，在重賞或生死交關的情形下，至今尚很少不能破獲的密碼，在現今數論密碼一日千里的進展之下， 我們剛才談到兩種密碼也就要（已經？）落伍，但新的方法必然又會出現，並且在尋找新數論密碼的長途上， 數學家一定可以同時在路邊撿到一些前人所未發現的珍珠，有一天人類也許可以坦誠相處到不要用密碼通訊的地步，但這些時來的珍珠將永遠是數學史上的光輝。
1.Rivest, R. L; Shemir, A.; Adleman, L. 《A method for obtaining digital signature and public-key cryptasystem》 Communication of ACM, 1978, pp. 120-126.
2.Simmons, G. 《Cryptology : The mathematics of sewre communication》 The Mathematical Intelligencer, 1978, pp. 233-246.
3.Hellman，M.E. 《The mathematics of public-key cryptography》 Scientific American, August, 1979, pp. 146-157.
4.Pomerance, C. 《The search for prime numbers》 Scientific American, December, 1982, pp. 136-147.