張艷碩 周岐浩 劉 冰 滕樹晨

北京電子科技學院，北京市 100070

1 引言

梅森素數(shù)[1]是數(shù)論研究中的一項重要內(nèi)容，自古希臘時代起人們就開始了對梅森素數(shù)的探索。由于這種素數(shù)具有獨特的性質(zhì)，一直吸引著歐幾里得、費爾馬、歐拉等眾多數(shù)學家和無數(shù)的數(shù)學愛好者對它進行探究。在現(xiàn)代，梅森素數(shù)在計算機科學、密碼學等領域也有重要的應用價值。20世紀90年代中后期，建立了世界上第一個基于互聯(lián)網(wǎng)的分布式計算項目——因特網(wǎng)梅森素數(shù)大搜索[3](GIMPS)。2017年12月26日發(fā)現(xiàn)了第50個梅森素數(shù)，超大素數(shù)有23249425位數(shù)，再次刷新了已知最大素數(shù)紀錄。

偽梅森數(shù)是最近提出的根據(jù)梅森數(shù)變形的具有(2P-c)形式的一類數(shù)，其中p為素數(shù)，c為小奇數(shù)，并用M(p，c)表示。當c＝1時，偽梅森數(shù)即為梅森數(shù)。另外，當一個數(shù)既是偽梅森數(shù)又是素數(shù)時，將其稱為偽梅森素數(shù)[7]。

偽梅森數(shù)的提出大大地拓寬了大素數(shù)的產(chǎn)生渠道。發(fā)現(xiàn)偽梅森素數(shù)需要素數(shù)判別和數(shù)值計算的理論與方法以及高超巧妙的程序設計技術。它促進了分布式計算技術的發(fā)展，在推動計算機功能改進方面發(fā)揮了獨特作用。偽梅森素數(shù)的研究推動了數(shù)論的發(fā)展，促進了計算數(shù)學和程序設計技術的發(fā)展[5]。

本文根據(jù)偽梅森數(shù)的定義推出一些相關性質(zhì)并提出基于遞歸性質(zhì)的偽梅森數(shù)的生成方法以及偽梅森數(shù)在構造RSA[6]密鑰、ElGamal[2]密鑰和Diffie-Hellman[4]密鑰協(xié)商上的應用。

2 偽梅森數(shù)

本文先從梅森數(shù)的定義[1]列出有關偽梅森數(shù)的兩個定義。

定義1將形如2p-c形式的正整數(shù)用M(p，c) 表示，其中p為素數(shù)，c為3、5、7 等小奇數(shù)，稱為偽梅森數(shù)。當M(p，c)為素數(shù)時，我們將其稱為偽梅森素數(shù)

如：M(3，3)＝ 5 為偽梅森素數(shù)，而M(5，5)＝27為偽梅森數(shù)而非偽梅森素數(shù)。

注：針對定義1特殊說明整數(shù)2為唯一的偶素數(shù)，表示為M(2，2)，這個是c唯一為偶數(shù)的情況。本文對M(2，2)作為特殊情況另行討論。當c＝1時，偽梅森數(shù)退化為梅森數(shù)。

定義2約束定義：若整數(shù) k同時滿足M(p1，c1)和M(p2，c2)，且p1＜p2，即

那么將k定義為偽梅森數(shù)M(p1，c1)而非M(p2，c2)。

如：3＝M(2，1)＝M(3，5)，根據(jù)定義2，將3定義為M(2，1) 而非M(3，5)。

這里規(guī)定了整數(shù)k的最簡定義，避免了重復定義造成的資源浪費。

3 偽梅森素數(shù)的性質(zhì)

本文從偽梅森數(shù)與梅森數(shù)關系以及偽梅森數(shù)之間的遞歸關系，推出了偽梅森數(shù)的7個性質(zhì)。

性質(zhì)1對于任意素數(shù)p，奇數(shù)c1，c2，c3有

證明：

性質(zhì)2對于任意素數(shù)p，奇數(shù) c，有M(p，c)與c互素。

證明：

性質(zhì)3對于任意素數(shù)p，奇數(shù)c，若滿足2N-1＜c＜2N，則對于偽梅森數(shù)M(p，c)有：

證明：

假設

利用該定理可以利用兩個小梅森數(shù)構造大的偽梅森數(shù)。

推論1：當N是偶數(shù)且c≡1mod6時，和均為整數(shù)，或當 N是奇數(shù)且 c≡5mod6、時，均為整數(shù)。

證明：

①若N是偶數(shù)，則2N-1≡0mod3

偽梅森數(shù)的定義中c為奇數(shù)，則

所以：

②若N是奇數(shù)，則2N-1≡1mod3。

偽梅森數(shù)的定義中c為奇數(shù)，則

所以：

性質(zhì)4對于任意素數(shù)p1，p2，小奇數(shù)c1，且p1≥p2，有

性質(zhì) 5對于任意素數(shù)p1，p2，奇數(shù)c1，c2，且p1≥p2，有

證明：

性質(zhì)6對于任意素數(shù)p1，p2，小奇數(shù)c1，c2，且p1≥p2，有

證明：

特別的，當c1＝c2＝c時，上式變?yōu)?/p>

注：根據(jù)上述等式判斷M(p1，c)與偽梅森素數(shù)M(p2，c)的互素情況，當?shù)仁接疫厼榉?整數(shù)時，M(p1，c)與M(p2，c)不互素，否則二者互素。由于2p1-p2為整數(shù)，只需判斷的整數(shù)性。

由性質(zhì)2可知M(p2，c)與c互素，故當2M(p1-p2-1，1)＋1與M(p2，c)互素時M(p1，c)與M(p2，c) 互素。由此我們得到性質(zhì)7：

性質(zhì)7對于任意素數(shù)p1，p2，小奇數(shù)c，且p1≥p2，M(p1，c)與偽梅森素數(shù)M(p2，c) 互素的充分必要條件為 2M(p1-p2-1，1)＋1與M(p2，c) 互素。

例1若p1＝7，p2＝3，c＝3，即M(7，3)＝125與M(3，3)＝5，易知二者不互素。p1-p2-1＝3，那么2M(3，1)＋1＝15與M(3，3)＝5也不互素。

若p1＝11，p2＝5，c＝3，即M(11，3)＝2045與M(5，3)＝29，易知二者互素。p1-p2-1＝5，那么2M(5，1)＋1＝63與M(5，3)＝29也互素。

4 偽梅森素數(shù)的產(chǎn)生方法

接下來本文將利用等式(1)得到新的偽梅森數(shù)的生成方法。在等式(1)中，有：

對于任意素數(shù)p1，p2，奇數(shù)c，有

說明：利用等式(1)我們可以通過兩個低次的梅森數(shù)和一個低次的偽梅森數(shù)生成高次偽梅森數(shù)。

由于梅森數(shù)已有公開的數(shù)表，在使用梅森數(shù)時可以直接套用數(shù)表上的數(shù)進行計算。梅森素數(shù)表列舉如表1所示(以偽梅森素數(shù)形式表示)：

表1 前12個梅森素數(shù)[1]

表2 第13至50號梅森素數(shù) [1]

從遞歸性質(zhì)出發(fā)，根據(jù)上述定義可以不斷推出新的偽梅森數(shù)這個思想在生成素數(shù)上具有廣泛應用，具體步驟如下：

步驟1固定c＝t不變，依次選擇素數(shù)p1，p2，其中p1，p2為存在于梅森素數(shù)表中，且M(p1，c) 為素數(shù)。

步驟2利用等式(1)生成新的偽梅森數(shù)。

步驟3對新的偽梅森素數(shù)進行素性檢驗(包括是 Miller-Rabin檢驗[9]，Lucas-Lehmer檢驗[8]等(注：Lucas-Lehmer是針對梅森素數(shù)的素性檢驗，當拓展為偽梅森素數(shù)時，該檢驗并不能通過))，通過則將新偽梅森素數(shù)加入偽梅森素數(shù)表(c＝t)，并回到步驟1。若不通過檢驗，則拋棄該數(shù)，回到步驟1，重新選擇p1，p2。

這樣便得到一個新的偽梅森素數(shù)表族(c＝t)。

我們以偽梅森素數(shù)舉例說明：

5 性能分析

5.1 復雜度

通過直接生成一個新的偽梅森素數(shù)M(p，c)，需要消耗時間復雜度O(2p)，而消耗的空間復雜度為O(1)。 時空分配不合理，當p值較大時很容易造成溢出。

根據(jù)遞歸方法生成素數(shù)方法，通過建立數(shù)表來增加空間復雜度為O(n2)，但時間復雜度降低為O(22p1)，其中2p1＝p-p2。增加了時空分配的合理性，大大提高了性能。

5.2 效率

使用遞歸性質(zhì)尋找偽梅森素數(shù)效率比使用普通方法效率提高很多。其中包括執(zhí)行的時間，執(zhí)行時間需通過依據(jù)編制的程序在計算機上運行時所消耗的時間來度量。由于復雜度的降低，在計算機上的執(zhí)行時間也大幅降低。

6 應用

6.1 基于偽梅森素數(shù)的RSA密鑰對的生成

RSA[6]是第一個安全，實用的公鑰密碼算法，成為了公鑰密碼的國際標準，目前是應用最廣泛的公鑰密碼體制。RSA密碼算法的數(shù)學原理來源于歐拉定理，其安全性取決于大整數(shù)因子分解不易實現(xiàn)。公鑰密碼體制在加密和數(shù)字簽名上應用廣泛，不僅安全、易懂，還容易實現(xiàn)。

RSA密鑰對的生成，通常需要以下幾個步驟：

(1)選取兩個大素數(shù)p、q；

(2)計算乘積n＝p×q，φ(n)＝(p-1)×(q-1)，其中φ(n)是n的歐拉函數(shù)值；

(3)隨機數(shù)e(1＜e＜φ(n))(不用保密)，必須滿足e與φ(n)互素；

(4)通過擴展歐幾里得算法計算d，滿足d×e≡1modφ(n)(保密)，即d-1≡emodφ(n) ；通常把 (e，n)稱為公鑰，(d，φ(n))稱為私鑰，e和d分別稱為加密指數(shù)和解密指數(shù)，在不知道p和q的情況下，很難計算φ(n)，因而就不知道私鑰(d，φ(n))。

例4：我們利用在例2和例3生成的偽梅森素數(shù)運算說明。

設p＝M(17，9)＝131063，q＝M(29，3)＝536870909，求 d。

選擇公鑰 e＝13(素數(shù))，求出d＝924900521。

所以，得到公鑰(e，n)＝(13，70363911946267)，私鑰為(d，φ(n))＝(924900521，70363374944296)。

由于梅森素數(shù)具有2p-1的形式，故容易受到William’sp＋1[10]因式分解攻擊。而偽梅森素數(shù)以2p-c形式作為因子，從而避免受到William攻擊。

6.2 基于偽梅森素數(shù)的EIGamal密鑰對生成

ElGamal[2]算法，是一種較為常見的加密算法，它是基于1985年提出的公鑰密碼體制和橢圓曲線加密體系。既能用于數(shù)據(jù)加密也能用于數(shù)字簽名，其安全性依賴于計算有限域上離散對數(shù)這一難題。在加密過程中，生成的密文長度是明文的兩倍，且每次加密后都會在密文中生成一個隨機數(shù)K，在密碼中主要應用離散對數(shù)問題的幾個性質(zhì)：求解離散對數(shù)(可能)是困難的，而其逆運算指數(shù)運算可以應用平方-乘的方法有效地計算。也就是說，在適當?shù)娜篏中，指數(shù)函數(shù)是單向函數(shù)。

密鑰對產(chǎn)生辦法如下：首先選擇一個素數(shù)p，獲取一個素數(shù)p的一個原根g(若g模p的階等于φ(p)，則稱g為模p的一個原根。(其中φ(p)表示p的歐拉函數(shù)，即所有小于等于p的正整數(shù)中和p互質(zhì)的整數(shù)的個數(shù)))和一個隨機數(shù)x，且g和x均小于p，計算y＝gx(modp)，則其公鑰為y，g和p，私鑰是x可由一組用戶共享。

ElGamal用于數(shù)字簽名。被簽信息為M，首先選擇一個隨機數(shù)k，k與p-1互質(zhì)，計算

再用擴展 Euclidean算法對下面方程求解b：

簽名就是(a，b)。隨機數(shù)k須丟棄。

驗證時要驗證下式：

得到公鑰(y，g，p)＝(410263748，3，536870909)，私鑰為(x)＝(131063)。

6.3 基于偽梅森素數(shù)的ECC密鑰對生成

橢圓曲線密碼學(英語：Elliptic curve cryptography，縮寫為ECC)，一種建立公開密鑰加密的演算法，基于橢圓曲線數(shù)學。橢圓曲線在密碼學中的使用是在1985年由Neal Koblitz和Victor Miller分別獨立提出的。

ECC的主要優(yōu)勢是在某些情況下它比其他的方法使用更小的密鑰——比如RSA加密算法——提供相當?shù)幕蚋叩燃壍陌踩?。ECC的另一個優(yōu)勢是可以定義群之間的雙線性映射，基于Weil對或是Tate對；雙線性映射已經(jīng)在密碼學中發(fā)現(xiàn)了大量的應用，例如基于身份的加密。

同時一定要檢驗是否滿足1≤a＜p。否則簽名容易偽造。

ElGamal用于加密。被加密信息為M，首先選擇一個隨機數(shù)k，k與p-1互質(zhì)，計算

(a，b)為密文，是明文的兩倍長。解密時計算

ElGamal簽名的安全性依賴于乘法群上的離散對數(shù)計算。素數(shù)p必須足夠大，且p-1至少包含一個大素數(shù)。

因子以抵抗Pohlig＆Hellman算法的攻擊。M一般都應采用信息的HASH值(如SHA算法)。ElGamal的安全性主要依賴于p和g，若選取不當則簽名容易偽造，應保證g對于p-1的大素數(shù)因子不可約。

例5：設p＝M(29，3)＝536870909，g＝3是p的一個原根，選擇隨機數(shù)x＝M(17，9)＝131063。不過一個缺點是加密和解密操作的實現(xiàn)比其他機制花費的時間長。

ECC的密鑰對產(chǎn)生方法如下：

定義在Fp上的橢圓曲線：

橢圓曲線E(Fp)定義為：

其中O是無窮遠點。橢圓曲線E(Fp)上的點數(shù)目用＃E(Fp)表示，稱為橢圓曲線E(Fp)的階。

設橢圓曲線參數(shù)(p，a，b，G，n)，其中G是基點，n是G的階。在區(qū)間[1，n-1]中隨機選取一個整數(shù)dB為私鑰。計算點QB＝dBG，取點QB為公鑰。

加密過程：

(1)用戶A將待傳輸?shù)拿魑木幋a到Ep(a，b)上一點M，并產(chǎn)生一個隨機整數(shù)r。

(2)用戶A計算點C1＝M＋rQB；C2＝kG。

(3)用戶A將C1、C2傳給用戶B。

(4)用戶B接到信息后，計算C1-kC2-kC2，結果就是點M，再對點M進行解碼就可以得到明文。

例6：設p＝M(5，9)＝23，a＝1，b＝1，G＝(3，10)，n＝28

隨機數(shù)作為私鑰dB＝M(17，9)＝9

公鑰QB＝(4，21)

6.4 基于偽梅森素數(shù)的密鑰交換協(xié)議

Diffie-Hellman[4]密鑰交換協(xié)議，縮寫為D-H，是一種安全協(xié)議。它可以讓雙方在完全沒有對方任何預先信息的條件下通過不安全信道創(chuàng)建起一個密鑰。這個密鑰可以在后續(xù)的通訊中作為對稱密鑰來加密通訊內(nèi)容。

例8：首先確定p＝M(29，3)＝536870909，g＝3是p的一個原根。

(1)Alice選擇不公開的整數(shù)a＝M(17，9)＝131063，然后傳送給 BobA＝gamodp，即A＝3131063mod536870909＝410263748；

(2)Bob同樣選擇一個不公開整數(shù)b＝17，然后傳送給 AliceB＝gbmodp，即B≡317mod536870909≡387420489；

(3)Alice計算s＝Bamodp，即s＝387420489131063mod536870909＝48621887；

(4)Bob計算s＝Abmodp，即s＝41026374817mod536870909＝48621887；

Alice和Bob就能通過公開信道得到密鑰s＝48621887。

7 結論

隨著現(xiàn)代密碼學的不斷發(fā)展，素數(shù)在信息安全領域以及密碼保密領域起到了越來越大的作用，計算機計算能力不斷增強，許多依賴于計算量的問題迎刃而解，對于大素數(shù)的要求會更高，而偽梅森數(shù)是最近所提出的一類拓寬大素數(shù)生成的渠道。本文對偽梅森素數(shù)進行前瞻性的研究，根據(jù)偽梅森素數(shù)的定義提出一些相關性質(zhì)，并根據(jù)性質(zhì)得出遞歸方法的偽梅森數(shù)的生成方法，再基于該性質(zhì)形成了一系列偽梅森素數(shù)族。

對于檢驗梅森素數(shù)的Lucas-Lehmer檢驗，并不能直接應用于偽梅森素數(shù)。我們希望讀者在閱讀本文后得到啟發(fā)，推出類似素性檢驗方法以檢驗偽梅森素數(shù)。