數論密碼

數論密碼，顧名思義，就是基於數論的密碼。密碼是相對於明碼而言的。這是一個矛盾的兩個方面。所謂明碼（plaintext），就是人們可以直接識別或使用的代碼（也就是人們通常所說的信息，如文字、聲像等）；所謂密碼（ciphertext），就是將明碼經過了一定處理，變換成一種外人（與此無關的人員）無法直接識別或使用的信息。

基本介紹

• 中文名：數論密碼
• 外文名：plaintext
• 意義：基於數論的密碼
• 性質：無法直接識別或使用的信息

套用領域

比如在軍事上，上級首腦機關向部下發布軍令時，就往往需要將軍令的原文（明碼）變換成密碼之後再發布（比如通過無線電台或計算機網路等向外發布）。這樣，即使敵方能夠截獲到這些密碼，也無法直接辨別出這些密碼的原意。當然，對於自己的部下而言，由於他們事先已經擁有解開這些密碼的鑰匙，所以能夠正確地將密碼再變換回明碼，從而可以執行軍令。

數論

數論介紹

數論是數學中最古老、最純粹的一個重要數學分支。素有“數學王子”之稱的19世紀德國數學大師高斯就曾說過，數學是科學的皇后，數論是數學的皇后。數論的一個主要任務，就是研究整數（尤其是正整數）的性質（包括代數方程的整數解）。由於在研究這些整數的過程中，人們往往要用到別的數學分支的知識與技巧，這樣就誕生出了解析數論、代數數論、組合數論、機率數論、幾何數論甚至計算數論等分支學科。

純粹學科

由於整數的性質複雜深刻，難以琢磨，因此數論長期以來一直被認為是一門優美漂亮、純之又純的數學學科。美國芝加哥大學著名數學家迪克森（L.E.Dickson）就曾說過：感謝神使得數論沒有被任何套用所玷污。20世紀世界級數學大師、劍橋大學的哈代也曾說過：數論是一門與現實、與戰爭無緣的純數學學科。哈代本人也則因主要從事數論的研究而被尊稱為“純之又純的純粹數學家”。

套用轉變

當然，上述兩位大數學家所說的並不完全符合今天的現實。事實上，在計算機科學與電子技術深入發展的今天，數論已經不僅僅是一門純數學學科，同時也是一門套用性極強的數學學科，比如在今天，數論已經在諸如物理、化學、生物、聲學、電子、通訊，尤其是在密碼學中有著廣泛而深入的套用。

密碼設計

大家知道，密碼設計長期以來一直是困擾軍方的一個問題。要保證軍方的密碼不被敵方破譯，不是件容易的事情。比如在第二次世界大戰期間，德軍設計了一種性能優良的編制密碼的機器，稱之為愛尼格瑪（Enigma）機器。德軍指揮機關向其部隊發布的軍令都是通過愛尼格瑪機器加密之後再往下發布的。當時英軍就想到，要打敗德軍，就必須要破譯德軍的密碼，掌握德軍的軍事動向（即所謂的知彼知己）。因此，英軍迅速在倫敦北邊不到一百公里處徵集了一塊空曠的土地（該地名為布萊克利公園，後也成了該秘密機構的名字），並在那裡集結起一大批傑出的數學家、語言學家和象棋大師等，包括現代計算機科學的開山鼻祖圖靈和後來在愛丁堡大學創辦世界上第一個人工智慧系的米基（D.Michie）。他們專門負責截獲、破譯愛尼格瑪密碼。由於這個組的努力，特別是圖靈出色的工作，他們掌握了破譯該密碼的一整套方法，從而了解德軍的軍事動向，掌握了戰爭的主動權，為英美聯軍擊敗德軍作出了突出的貢獻。有人估算，如果沒有圖靈等人的貢獻，第二次世界大戰至少還要再打十年。

DHM的提出

目前，由於商用計算機網路的廣泛套用，尤其是電子商務的普及與深入，密碼設計在民間也大有用武之地。傳統的密碼體制，稱之為“密鑰密碼體制”，在加密、解密的過程中都採用同一個鑰，簡稱為“密鑰”(secret key)。所謂同一個鑰，就是說知道了其中的一個鑰，另一個鑰就可以很容易地計算出來。具體到軍用通訊，就是軍事指揮機關要事先用密鑰把軍令加密，之後再下達到部隊，與此同時（甚至是事先）還要將密鑰也下達到部隊，否則其部下解不開其軍令。顯然，密鑰的管理與保護是個問題。一般而言，密鑰比密碼本身還重要，因為一旦敵方掌握了密鑰，那么所有用此密鑰加密的密碼就成了人所皆知的明碼。因此，在軍事與外交等部門，都是不惜代價而派專人專管專送密鑰。顯然，這在電子商務方面是行不通的，因為代價太高。

加密公鑰

1976年，美國史丹福大學教授赫爾曼(E.Hellman)和他的研究助理迪菲(W.Diffie)，以及博士生默克勒(R.C.Merkle)（簡稱為DHM）首先創立並發表了所謂的“公鑰密碼體制”（public key cryptography），即加密、解密用兩個不同的鑰，加密用公鑰（public key），即可以公開，不必保密，任何人都可以用；解密用私鑰（private key），此鑰必須嚴加管理，不能泄漏。更為稱絕的是，他們還發明了所謂的數字簽名（digital signatures）技術，即用私鑰簽名，再用公鑰驗證。

密鑰發展

在一般參考文獻中，都認為公鑰密碼體制是迪菲和赫爾曼發明的[1]，可鮮為人知的是，默克勒甚至在他倆之前的1975年就提出了類似的思想，儘管其文章是於1978年發表的[2]，但投稿比較早。因此，公鑰密碼體制的創始人應該是DHM三人，這種觀點目前已得到了國際上的認同，尤其得到了赫爾曼教授本人的認定。當然，英國軍用情報中心也曾宣稱他們早在1970年就發明了公鑰密碼體制，但經仔細分析其資料並與中心有關人員討論後發現，他們只是提及了公鑰密碼體制的某種特殊形式。更為重要的是，DHM的公鑰密碼體制還包含數字簽名，而情報中心的資料則是隻字未提。注意，美國國家安全局也有過類似的宣稱，不過這都是不可信的（至少不可全信）。如要詳細了解公鑰密碼體制的發展史，讀者可參考筆者的一本由赫爾曼教授作序的英文專著[3]。

密鑰問題

當然，DHM只是提出了一種關於公鑰密碼體制與數字簽名的思想，而沒有真正實現。不過，他們確實是實現了一種體現公鑰密碼體制思想、基於離散對數問題的、在不安全的通道上進行密鑰形成與交換的新技術。這裡必須先介紹一下什麼叫離散對數。

離散對數

就是給定正整數x，y，n，求出正整數k（如果存在的話），使y≡xk(mod n)。就目前而言，人們還沒有找到計算離散對數的快速算法（所謂快速算法，是指其計算複雜性在多項式範圍內的算法，即O(logn)k，其中k為常數）。雖然有快速計算離散對數的量子算法，其計算複雜性為O(logn)2+?著，但現在並沒有量子計算機（實用的量子計算機也許根本就建造不出來）。

現在，說明一下DHM的運作過程（假定A和B兩個人要在一個不安全通道如網際網路上形成密鑰以備日後加密解密所用）。

首先，A、B兩人要共同公開約定一個素數q和有限域Fq中的一個生成元g；

A選定一個隨機數a∈{1，2，…，q-1}（a可以認為是A之私鑰），並將g a(modq)傳送給B；

B選定一個隨機數b∈{1，2，…，q-1}（b可以認為是B之私鑰），並將gb(modq)傳送給A；

此時A可以算出(g b)a(modq)，B也可以算出(g a)b(modq)，由於(gb)a(modq) = (g a)b(modq) = g ab(modq)，因此，A和B就形成了一個公共的密鑰g ab(modq)，日後便可以此鑰來進行傳統的加密解密計算，從而達到在不安全的通道上進行保密通訊的目的。

密鑰優點

顯然，敵方可以截獲到g，q，g a(modq)，g b(modq)。因此，如果敵方有快速的求解離散對數的算法，就能從已截獲的上述信息中迅速求出a或b，從而算出g ab(modq)。遺憾的是，目前世界上根本就沒有快速的求解離散對數的算法，因此當所選的有限域Fq很大時，a或b就很難算出。值得注意的是，DHM密鑰交換體制實際上是一座溝通密鑰密碼體制與公鑰密碼體制的橋樑，即用公鑰密碼體制的思想形成密鑰（雖然公鑰密碼體制計算速度慢，但密鑰的長度一般都很短，所以沒有關係），再用密鑰進行傳統的密鑰密碼體制的加密與解密運算（密鑰密碼體制的運算速度一般都很快，所以適合於對容量大的信息進行加密解密計算）。在這裡，這兩種密碼體制交叉使用，揚長避短，充分發揮了各自的優越性。

實例分析

下面給出一個關於具體計算離散對數的實例。

A和B先約定公共的q=2739·（7149-1）/6+1和g=7。

A選隨機數a，並計算7a(modq)，且將其送給B（註：a不能向外泄漏）；

（見擴展閱讀）

此時A和B都能計算出密鑰7ab(modq)，但別人不太容易算出，因為別人不知道a和b。有興趣的讀者不妨將此作為一個練習，試著計算出7ab(modq)的值。

RSA體制

1978年，僅在DHM發明公鑰密碼體制的兩年後，美國MIT的三位科學家裡維斯特(R.L.Rivest)，沙米爾(A.Shamir)和阿德爾曼(L.Adleman)（簡稱RSA）就提出了一種基於整數分解困難性的實用的公鑰密碼體制[4]，現通稱為RSA體制。

整數分解可以認為是給定大於1的正整數n，求出正整數a和b，使之滿足n=ab，其中a和b可以是素數，也可以是合數。根據算術基本定理，只要能夠快速求出a，b，那么就能遞歸地快速求出n的素數分解式n=p1 p2…pk，其中?琢i為正整數，pi為素數，i=1,2,…,k。現在的問題是，人們根本就沒有滿意的快速整數分解算法，目前世界上最快的整數分解算法是波拉德（J.Pollard）首創的數域篩法（NFS）。

波拉德是英國的數學奇才，曾在劍橋大學念數學本科，但因畢業考試不及格而肄業，後來因在計算數論中作出突出貢獻而被劍橋免試授予博士學位。無獨有偶，劍橋出身的另一位著名數學家羅斯（K.Ruth）也是因為在念本科時考試成績不好而勉強畢業，後來卻因在數論研究中取得傑出成就而獲得菲爾茲獎，劍橋則因此而授予其名譽博士學位。

數域篩法的計算複雜性為O(exp(c(logn)1/3(loglogn)2/3 ))，其中c為一實常數，1

現在，具體地談一談RSA的思想。

加密C≡Me(modn)；

解密M≡Cd(modn)；

其中M為明碼，C為密碼，(n，e)為公鑰（加密鑰），d為私鑰（解密鑰），並且要滿足：n=pq，其中p和q為兩個至少100位的素數；ed≡1(mod?準(n))，其中?準為歐拉函式，其計算公式為：如果n的標準分解為

n=p ，

則準(n)=n(1-) 。

(e，n)要公開出去，以便別人能用來對信息進行加密，但p和q（當然包括d）必須保護好，不能泄漏。RSA體制之所以能工作，是因為

Cd≡(Me)d≡Med≡M1+k?準(n)

≡M(M?準(n))k≡M(modn)；

對於合法用戶而言，因為他知道n=pq，故計算出?準(n)=(p-1)(q-1)，從而算出d≡1/e(mod?準(n))，這樣他就可以對信息進行解密計算。上述計算的關鍵是歐拉函式。

顯然，對於非法用戶（即敵方）而言，要算出d，他必須先算出?準(n)；而要算出?準(n)，他必須先分解n。如前所述，整數分解是個很困難的問題，事實上，在現有的計算條件下，當n為一個一般的大於200位的整數時，要分解n往往需要數億年的時間。可以想像，任何一項秘密，過了數億年的時間，其秘密性已不復存在了。因此，用RSA方法來加密信息還是很安全的（當然在具體實現上，其加密解密過程中的參數的選擇還是很有講究的）。

橢圓曲線密碼體制

目前，國際上公認的比較安全實用的公鑰密碼體制是所謂的橢圓曲線密碼體制。其思想是在基於有限域的橢圓曲線上對信息進行加密解密。由於有限域上橢圓曲線的離散對數實際上是一般有限域上的離散對數在橢圓曲線上的一種類比物，因此它至少在實用上比一般有限域上的離散對數的計算要困難些，因此其安全性也要強一些，當然目前人們還不能證明這一點。

橢圓曲線上的離散對數，可以認為是：給定有限域Fq（q=pr為素數冪）上的一條橢圓曲線y2=x3+ax+b，並給定這條曲線上的兩點P和Q，求出正整數k（如果存在的話），使之滿足Q=kP，目前關於橢圓曲線離散對數問題還沒有找到一種甚至是子指數（subexponential）複雜性的算法（對於整數分解與離散對數，已有子指數複雜性的算法）。西爾弗曼（J.H.Silverman）等人於2000年提出了一種稱之為Xedni Calculus的計算橢圓曲線離散對數的算法[5]，但該法過於複雜，並用了很多未被證明的數學結果，因此該法一是沒有實用價值，二是連個複雜性的度量都提不出來。故而尋求快速實用的計算橢圓曲線離散對數的算法（哪怕是子指數複雜性的算法）是當前計算數論中的一項刻不容緩的艱巨任務。

下面介紹基於橢圓曲線的ElGamal公鑰密碼體制（其他的很多公鑰密碼體制都可以很容易地推廣到橢圓曲線上去）。

A和B兩人要事先在公開的通道上選定有限域Fq（其中q=pr，p為素數）上的一條橢圓曲線E，以及隨機點P∈E（該點要能生成一個很大的子群，這個子群最好和橢圓曲線E本身所構成的群一樣大或比較接近）。

A選定一個隨機數a∈{1，2，…，q-1}（a可以認為是A之私鑰），並計算出aP（aP可以認為是A之公鑰），且將其傳輸給B；

B選定一個隨機數b∈{1，2，…，q-1}（b可以認為是B之私鑰），並計算出bP（bP可以認為是B之公鑰），且將其傳輸給A；

現假定A要給B傳輸信息M（明碼）。首先A要選定一個隨機數k，並利用B的公鑰bP計算出密碼C=（kP，M+k(bP )），且將其傳輸給B。

為了能夠將C變換回M，B需要對C進行解密計算，但由於B有b，所以他可以很容易地計算出M=M+k(bP )-b(kP )。

顯然，敵方如能計算橢圓曲線上的離散對數，他就能從公開的信息P和bP中確定出b，從而破譯C。遺憾的是，求解橢圓曲線上的離散對數比求解一般有限域上的離散對數更困難（前面講到，求解一般有限域上的離散對數已經是一件很困難的事情了），所以當所選的有限域Fq很大、所選的橢圓曲線以及這條曲線上的點P又很合適時，a或b是很難算出的，因此基於橢圓曲線離散對數的密碼體制也就要更安全些（至少比基於整數分解或一般有限域上的離散對數的密碼體制要更安全些）。另外，橢圓曲線密碼體制與其他公鑰密碼體制相比，在鑰的長度相同的情況下，它的安全性要更高些。正是基於上述這些原因，目前人們才會對橢圓曲線密碼體制更感興趣。

綜合述評

上面介紹的三種具有代表性的現代公鑰密碼體制，就是基於三種各不相同的數論難題的（即整數分解、離散對數以及橢圓曲線上的離散對數）；目前世界上幾乎所有具有實用價值的公鑰密碼體制，基本上都是基於這三種數論難題的。也就是說，事實上是將密碼的加密、解密、破譯等問題與數論難題的求解聯繫在一塊了。密碼難破譯是因為數論問題難解。因此，在這裡，不僅數論本身的理論與方法有實用價值，就是數論里的難題也為現實生活提供了套用的場所。也許正因為如此，國際數學大師陳省身先生才會主張把數論作為一門套用數學學科[6]。值得特別一提的是，數論密碼是目前密碼學中的主流學科，限於篇幅，這裡不再對其做深入的介紹[3,7]。

參考信息

[1] Diffie W, Hellman E. IEEE Transactions on Information Theory, 1976，22（5）：644

[2] Merkle R C. Communications of the ACM, 1978，21(4):294

[3] Yan S Y. Number Theory for Computing, 2nd Edition. New York: Springer-Verlag， 2002

[4] Rivest R L, Shamir A, Adelman L. Communications of the ACM, 1978，21(2):120

[5] Yan S Y. International Journal of Computer Mathematics, 2003,80（5）：573

[6] 陳省身. 數學進展，1992，21（4）：385

[7] 顏松遠. 數學的實踐與認識, 2002，32(3):486

延伸閱讀

密碼學就是一門研究信息的加密（encryption）與解密（decryption）技術（統稱為cryptography），以及密碼破譯（cryptanalysis）技術的學問。密碼學有兩個顯著特點：一是歷史悠久（事實上，密碼學的歷史幾乎與人類文明史一樣長），二是數學性強（幾乎所有的密碼體制都程度不同地使用了數學的方法，尤其是代數、幾何與數論的方法）。