李 峰,龔宗躍,2,雷翻翻,顧 申,高 鵬

1.大唐微電子技術(shù)有限公司,北京100094

2.北京航空航天大學(xué),北京100191

3.北華大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院,吉林132013

1 引言

素?cái)?shù)在很多密碼算法和協(xié)議中都有使用,有些算法的安全性完全取決于素?cái)?shù)的保密性[1–4],如RSA[1]中,取素?cái)?shù)p和q,計(jì)算參數(shù)N=pq及私鑰d=e?1modφ(N)(e為選定的公鑰參數(shù)); 算法的理論安全性基于大數(shù)N分解的困難性,實(shí)際的安全性基于素?cái)?shù)p和q的保密性及所使用p,q的安全性.

素?cái)?shù)生成對(duì)很多密碼算法是至關(guān)重要的,而由于大素?cái)?shù)分布的稀疏性,素?cái)?shù)生成是一個(gè)很耗時(shí)的過(guò)程.因此,研究快速高效的素?cái)?shù)生成方法是有必要的.

各種素?cái)?shù)生成方法的算法流程雖然不完全一致,但是整體思路都是一樣的,流程如圖1所示.

圖1中可看到素?cái)?shù)生成分為3 步,分別為選取初值、增量變換、素性檢測(cè),對(duì)于快速素?cái)?shù)生成算法的研究也從這三步著手進(jìn)行.

初值p的選取有兩類(lèi)主要算法,一類(lèi)是直接選取隨機(jī)奇數(shù),另一類(lèi)是選取與小素?cái)?shù)乘積互素的數(shù).文獻(xiàn)[5]提到,確保一個(gè)隨機(jī)奇數(shù)不能被3、5和7 整除,即可在素?cái)?shù)檢測(cè)前排除54% 的奇數(shù); 確保隨機(jī)奇數(shù)與小于100 的素?cái)?shù)均互素即可排除76% 的奇數(shù).

進(jìn)行增量變換時(shí),增量函數(shù)f的選取是一個(gè)關(guān)鍵點(diǎn),不同算法對(duì)f的選取不同,可以每次給初值加2、每次加一個(gè)素?cái)?shù)或經(jīng)過(guò)一個(gè)復(fù)雜的函數(shù)變換.

素性檢測(cè)是所有素?cái)?shù)生成算法必不可少的一個(gè)環(huán)節(jié),有兩大類(lèi)檢測(cè)方法,一類(lèi)是可證明素?cái)?shù)檢測(cè),另一類(lèi)是概率素?cái)?shù)檢測(cè).實(shí)踐中概率素?cái)?shù)檢測(cè)算法使用更為廣泛,經(jīng)概率素?cái)?shù)檢測(cè)算法通過(guò)的素?cái)?shù)有時(shí)也被稱(chēng)為“工業(yè)級(jí)素?cái)?shù)”.

2 生成與小素?cái)?shù)乘積互素?cái)?shù)的算法

本節(jié)主要介紹幾種生成與小素?cái)?shù)乘積互素?cái)?shù)的算法及其相關(guān)理論基礎(chǔ).素?cái)?shù)生成算法中初值的生成常用這類(lèi)算法.

2.1 查表法

定理1(中國(guó)剩余定理[5])若m1,m2,··· ,mn兩兩互素且都大于1,a1,a2,··· ,an是任意整數(shù),則存在一個(gè)解x滿(mǎn)足同余方程組:

其解一定可以寫(xiě)成以下形式:

且θi滿(mǎn)足同余方程組

則由中國(guó)剩余定理可得

故可得到以下等價(jià)條件:

對(duì)于一個(gè)固定的Π,可以計(jì)算得到θi,再選擇k個(gè)隨機(jī)數(shù)xi滿(mǎn)足這樣可以得到一個(gè)與Π的每個(gè)因子都互素的x.因此,可以得到算法1[6].

該算法需要存儲(chǔ)預(yù)計(jì)算得到的θi,因此需要較大的存儲(chǔ)空間.實(shí)際使用中通常對(duì)于選定Π的將θi進(jìn)行預(yù)存,提高算法執(zhí)行效率.

2.2 模搜索法

定義1(Carmichaelλ函數(shù))對(duì)任意整數(shù)為素?cái)?shù).λ(N)的定義如下:

其中p為素?cái)?shù).

算法1 查表法Input:Π=∏ki=1pδii Output:與Π 互素的數(shù)c 1 預(yù)處理:2 計(jì)算θi:3 for i=1 to k do()[()?1]4 θi=ΠΠ pδi mod pδi i i pδi i 5 end 6 計(jì)算其他參數(shù):t=C ·max(pδi)i ,pδi i 表示pδii 的比特?cái)?shù)，C 通常取2.7 主運(yùn)算:8 c=0,i=1 9 while i≤k do 10 取t 比特的隨機(jī)數(shù)x 11 if xδiθi mod Π=0 then 12 Goto Step 9 13 end 14 c=(c+xθi)mod Π 15 i=i+1 16 end 17 返回c

定理2(Carmichael 定理[7])設(shè)a和N都是正整數(shù),且gcd(a,N)=1,則

其中λ(N)是Carmichael 函數(shù).

由定理2易得推論1.

推論1設(shè)a和N都是正整數(shù),若有aλ(N)≡1 modN成立,則有g(shù)cd(a,N)=1,其中λ(N)是Carmichael 函數(shù).

由推論1,可得算法2.該算法不需要任何預(yù)存值,但要多次計(jì)算指數(shù)為λ(Π)的模冪運(yùn)算,算法執(zhí)行效率較低.

算法2 模搜索法Input:Π=∏k i=1pδii Output:與Π 互素的數(shù)c 1 取n 比特隨機(jī)數(shù)c,使其滿(mǎn)足c < Π 2 while cλ(Π) mod Π=1 do 3 c=c+1 4 end 5 返回c

2.3 改進(jìn)的模搜索法

定理3令整數(shù)k,r∈ZΠ,若gcd(k,r,Π)=1,則有

可以利用定理3對(duì)算法2 進(jìn)行優(yōu)化,得算法3[8].

算法3 改進(jìn)的模搜索法Input:Π=∏k i=1pδii ,λ(Π)Output:與Π 互素的數(shù)c 1 取隨機(jī)數(shù)c ∈ZΠ 2 U=(1?cλ(Π))mod Π 3 while U=0 do 4 取隨機(jī)數(shù)r ∈ZΠ 5 c=c+rU 6 U=(1?cλ(Π))mod Π 7 end 8 返回c

該算法運(yùn)算量和算法2基本相當(dāng),但循環(huán)次數(shù)有所減少,從而縮短運(yùn)算時(shí)間.

3 素?cái)?shù)生成主算法

本節(jié)介紹素?cái)?shù)生成中最重要的一個(gè)步驟,增量函數(shù)f的設(shè)計(jì).下文描述中使用T(q)表示對(duì)q進(jìn)行素性檢測(cè),當(dāng)q是素?cái)?shù)時(shí)返回True,否則返回False.

3.1 原生算法

最原始的生成素?cái)?shù)方法就是取一個(gè)隨機(jī)奇數(shù),進(jìn)行素性檢測(cè),如果不是素?cái)?shù)則重新取一個(gè)隨機(jī)數(shù),直到找到一個(gè)素?cái)?shù).

算法4 原生素?cái)?shù)生成算法Input:要生成素?cái)?shù)的比特位數(shù)n Output:素?cái)?shù)q 1 取n 比特隨機(jī)奇數(shù)q 2 while !T(q)do 3 取n 比特隨機(jī)奇數(shù)q 4 end 5 返回q

接下來(lái)討論理論上該算法所需素?cái)?shù)檢測(cè)次數(shù).

定義2(素?cái)?shù)分布函數(shù)[9])素?cái)?shù)分布函數(shù)π(x)表示小于或等于x的素?cái)?shù)個(gè)數(shù),表達(dá)式可以寫(xiě)為且p是素?cái)?shù)1,其中x是大于1 的正實(shí)數(shù).

定理4(素?cái)?shù)定理)π(x)是的漸進(jìn),即

定義3(Li(x)函數(shù))Li(x)[10]是一個(gè)比更好的π(x)的逼近,令x是大于1 的正實(shí)數(shù),則

由于公式(2)需計(jì)算極限,計(jì)算不是很方便,在有限誤差范圍內(nèi),Li(x)可以近似寫(xiě)成

該式與式(1)僅相差一個(gè)常數(shù)Li(2)≈1.05.

定理5π(x)是Li(x)的漸進(jìn),即

根據(jù)定理4和定理5,得到算法4生成滿(mǎn)n比特隨機(jī)數(shù)時(shí)平均素?cái)?shù)檢測(cè)次數(shù)的兩個(gè)近似值,分別為

和

表1 算法4平均素?cái)?shù)檢測(cè)次數(shù)Table 1 Average prime test times of Algorithm 4

由表1可知算法4所需素?cái)?shù)檢測(cè)的次數(shù)較多,生成素?cái)?shù)平均時(shí)間較長(zhǎng).

3.2 增量素?cái)?shù)生成算法

算法4效率較低,算法5對(duì)其進(jìn)行改進(jìn).該算法由Jorgen Brandt 等[11]提出并在文獻(xiàn)[12]中對(duì)其性能進(jìn)行了全面分析.

算法5 增量素?cái)?shù)生成算法Input:要生成素?cái)?shù)的比特位數(shù)n Output:素?cái)?shù)q 1 取n 比特隨機(jī)奇數(shù)q 2 while !T(q)do 3 q=q+2 4 end 5 返回q

由于素?cái)?shù)分布的不均勻性,因此從理論上無(wú)法計(jì)算出該算法平均需要進(jìn)行的素?cái)?shù)檢測(cè)次數(shù),除非已知了指定范圍內(nèi)所有素?cái)?shù)的分布.經(jīng)過(guò)實(shí)驗(yàn)分析,該算法平均素?cái)?shù)檢測(cè)次數(shù)比算法4略有減少,算法5的另一優(yōu)勢(shì)在于能提高素?cái)?shù)檢測(cè)效率,將在4.2節(jié)進(jìn)行討論.

3.3 改進(jìn)的增量素?cái)?shù)生成算法

對(duì)算法5進(jìn)行兩方面改進(jìn),一方面取初值q滿(mǎn)足gcd(q,Π)=1,其中Π是小素?cái)?shù)乘積,通常Π=2×3×5×···×29; 另一方面,迭代過(guò)程由q=q+2 改進(jìn)為q=q+Π,這樣可以保證每個(gè)q均沒(méi)有這些小素因子.

詳細(xì)算法描述見(jiàn)算法6.

算法6 改進(jìn)的增量素?cái)?shù)生成算法Input:要生成素?cái)?shù)的比特位數(shù)n,前k 個(gè)小素?cái)?shù)乘積Π=∏ki=1pi Output:素?cái)?shù)q 1 取n 比特隨機(jī)奇數(shù)q,使之滿(mǎn)足gcd(q,Π)=1 2 while !T(q)do 3 q=q+Π 4 end 5 返回q

與算法5類(lèi)似,由于素?cái)?shù)分布的非均勻性,該算法需要進(jìn)行的素?cái)?shù)檢測(cè)次數(shù)也無(wú)法得到理論上的確定值,但可以確定該算法的素?cái)?shù)檢測(cè)次數(shù)與參數(shù)k直接相關(guān),在一定范圍內(nèi),k取值越大所需素?cái)?shù)檢測(cè)次數(shù)越少.步驟1可使用算法1–3實(shí)現(xiàn).

3.4 M-J 素?cái)?shù)生成算法

M-J 素?cái)?shù)生成算法由Marc Joye 等在文獻(xiàn)[6]中提出.該算法對(duì)算法6進(jìn)行了改進(jìn),減少了所需素?cái)?shù)檢測(cè)的次數(shù).

素?cái)?shù)生成一般指定一個(gè)生成范圍[wmin,wmax],在密碼算法中一般都是生成固定n比特的素?cái)?shù),通常取wmin=2n?1+1,wmax=2n?1.

取參數(shù)Π滿(mǎn)足Π

且使不等式兩端的值盡量接近,即

為下文描述方便,記ψ=εmaxΠ,τ=εminΠ.M-J 算法流程見(jiàn)算法7.

算法7 M-J 素?cái)?shù)生成算法Input:要生成素?cái)?shù)的比特位數(shù)n,ψ和τ Output:素?cái)?shù)q 1 取隨機(jī)數(shù)c,使c ∈Z?ψ 2 計(jì)算q=c+τ 3 while !T(q)do 4 c=fa(c)5 q=c+τ 6 end 7 返回q

Marc Joye 在文獻(xiàn)[6]中給出生成n比特素?cái)?shù)時(shí)算法7的時(shí)間復(fù)雜度為O(n4/lnn),但未給出完整的證明.

考慮算法實(shí)現(xiàn)的效率,可以令步驟4中a=2,即ci=2ci?1modψ,乘2 的運(yùn)算可以通過(guò)左移位快速實(shí)現(xiàn),同時(shí)乘2 后的取模運(yùn)算可以轉(zhuǎn)換為大數(shù)減運(yùn)算,即ci=2ci?1或ci=2ci?1?ψ.由于有限制條件故取a=2時(shí)需要限制gcd(ψ,2)=1,則Π中不能包括因子2,εmax為奇數(shù).因?yàn)棣资瞧鏀?shù),所以步驟5得到的候選值qi可能是偶數(shù).當(dāng)qi為偶數(shù)時(shí),給其加Π保證進(jìn)行素?cái)?shù)檢測(cè)的qi全部為奇數(shù).由此得到算法7的一個(gè)特例,流程見(jiàn)算法7A[6].

算法7A M-J 素?cái)?shù)生成算法的特例Input:要生成素?cái)?shù)的比特位數(shù)n,ψ和τ和Π(不含因子2)Output:素?cái)?shù)q 1 取隨機(jī)奇數(shù)c,使c ∈Z?ψ 2 計(jì)算q=c+τ 3 if q mod 2=0 then 4 q=q+Π 5 if !T(q)then 6 c=2c mod ψ 7 Goto Step 2 8 返回q

實(shí)際中常使用算法7A,可有效縮短生成素?cái)?shù)的時(shí)間,提高效率.

3.5 改進(jìn)的M-J 素?cái)?shù)生成算法

給定目標(biāo)素?cái)?shù)范圍[wmin,wmax],首先生成算法參數(shù).選一個(gè)小數(shù)0 <ε≤1(一般取10?2或者10?3),選擇小素?cái)?shù)的乘積則存在整數(shù)t,u,v滿(mǎn)足以下條件:

(1)1?ε<(uΠ?1)/(wmax?wmin)≤1;

(2)vΠ+t≥wmin;

(3)(u+v)Π+t?1≤wmax;

(4)Π包括盡量多的不同的素因子且Π

根據(jù)參數(shù)(wmin,wmax,ε)得到參數(shù)(Π,t,u,v),即可進(jìn)行素?cái)?shù)生成,見(jiàn)算法8.

令ψ=uΠ,τ=vΠ,取隨機(jī)數(shù)且a=1.

算法8 改進(jìn)的M-J 素?cái)?shù)生成算法Input:t,ψ,τ和a Output:素?cái)?shù)q 1 取隨機(jī)數(shù)k ∈Z?ψ 2 計(jì)算q=[(k?t)mod ψ]+t+τ 3 if !T(q)then 4 k=a·k mod ψ 5 Goto Step 2 6 返回q

算法8生成素?cái)?shù)實(shí)際的分布范圍為[vΠ+t,(u+v)Π+t?1]?[wmin,wmax],是目標(biāo)素?cái)?shù)范圍的一個(gè)子集.該子集與目標(biāo)范圍的接近程度由參數(shù)ε決定.

該算法可以保證進(jìn)行素?cái)?shù)檢測(cè)的每一個(gè)q均滿(mǎn)足gcd(q,Π)=1.該算法通用性較好,輸出素?cái)?shù)的分布也比算法7更好.文獻(xiàn)[8]給出了算法8生成n比特素?cái)?shù)時(shí)所需素?cái)?shù)檢測(cè)次數(shù)為n·ln 2·?(Π)/Π=O(n/lnn).

令u=1,這樣一次取值的區(qū)間長(zhǎng)度就變成了Π?1,為了使取隨機(jī)數(shù)的范圍盡可能接近目標(biāo)范圍,將t的取值由固定值改為Π的隨機(jī)倍數(shù),即t=bΠ,每次取數(shù)時(shí)b在變化.此外,令a=2,步驟4只需要進(jìn)行移位和減運(yùn)算,速度有明顯提升;a=2時(shí)必須使才能保證成立此時(shí),上述的4 個(gè)條件將變成如下形式:

(1)1?ε<((bmax?bmin+1)Π?1)/(wmax?wmin)≤1;

(2)(v+bmin)Π≥wmin;

(3)(v+1+bmax)Π?1≤wmax;

(4)Π包括盡量多的不同的素因子且Π

此時(shí)就得到算法8的一個(gè)特例,算法8A.

算法8A 改進(jìn)的M-J 素?cái)?shù)生成算法的特例Input:Π=∏i pi(pi=2),τ=vΠ,bmin,bmaxOutput:素?cái)?shù)q 1 取隨機(jī)數(shù)k ∈Z?Π 2 取隨機(jī)數(shù)b ∈[bmin,bmax],計(jì)算t=bΠ 3 計(jì)算q=k+t+τ 4 if q%2=0 then 5 q=Π?k+t+τ 6 if !T(q)then 7 k=2·k mod Π 8 Goto Step 2 9 返回q

算法8A中步驟1可以使用第2節(jié)中的3 個(gè)算法進(jìn)行運(yùn)算,步驟7可以通過(guò)移位和減實(shí)現(xiàn),避免使用模乘,保證算法的高效性.應(yīng)用中經(jīng)常使用算法8A.

算法8中一些參數(shù)取特定值時(shí)還可以進(jìn)一步簡(jiǎn)化,令參數(shù)u=1,t=0,a=65537,步驟1中k=65537,則算法可以簡(jiǎn)化為

其中α,v是滿(mǎn)足要求的隨機(jī)數(shù),計(jì)算得到q后進(jìn)行素?cái)?shù)檢測(cè),如果不通過(guò)則重新選擇α和v.根據(jù)文獻(xiàn)[13]該方法是某主流密碼設(shè)備廠商使用的RSALib 中的方法,文獻(xiàn)[16]提出一種針對(duì)該算法的攻擊——RoCA 攻擊,使RSA 的密鑰在較短時(shí)間內(nèi)被恢復(fù).

4 素?cái)?shù)檢測(cè)算法

素?cái)?shù)檢測(cè)算法主要分為可證明素?cái)?shù)檢測(cè)和概率素?cái)?shù)檢測(cè).

可證明素?cái)?shù)檢測(cè)是基于完整的數(shù)學(xué)推導(dǎo),理論上可保證通過(guò)檢測(cè)的肯定是素?cái)?shù),常用的可證明素?cái)?shù)檢測(cè)方法有n?1 分解法、Jacobi和測(cè)試法、基于橢圓曲線的素?cái)?shù)檢測(cè)法等,這些方法運(yùn)算量都較大,耗時(shí)較長(zhǎng),在一般生成用于密碼算法密鑰參數(shù)時(shí)使用較少,本文不詳述這類(lèi)算法,可參考文獻(xiàn)[10]和[13].

概率素?cái)?shù)檢測(cè)算法在實(shí)際中使用更為廣泛,這類(lèi)算法相比于可證明素?cái)?shù)檢測(cè)算法計(jì)算量大大降低,但是其給出的結(jié)果有一定的可能性是錯(cuò)誤的,即輸入一個(gè)素?cái)?shù),這類(lèi)算法給出的結(jié)果肯定是素?cái)?shù); 輸入一個(gè)合數(shù),算法檢測(cè)后可能認(rèn)為該數(shù)是素?cái)?shù).

4.1 概率素?cái)?shù)檢測(cè)算法

常見(jiàn)概率素?cái)?shù)檢測(cè)類(lèi)算法有Fermat 檢測(cè)、Solovay-Strassen 檢測(cè)和Miller-Rabin 檢測(cè)三種算法.

Fermat 檢測(cè)是基于費(fèi)馬小定理,但是該類(lèi)檢測(cè)算法會(huì)將費(fèi)馬偽素?cái)?shù)誤認(rèn)為是素?cái)?shù),而且需要進(jìn)行模冪運(yùn)算,運(yùn)算量較大,實(shí)際中基本已經(jīng)不再使用.

Solovay-Strassen 檢測(cè)的理論基礎(chǔ)是歐拉準(zhǔn)則,但是該檢測(cè)算法會(huì)將歐拉偽素?cái)?shù)誤認(rèn)為是素?cái)?shù),同時(shí)計(jì)算中需要計(jì)算“雅可比記號(hào)”(Jacobi Symbol),計(jì)算較為復(fù)雜.由于歐拉偽素?cái)?shù)比費(fèi)馬偽素?cái)?shù)少很多,因此該檢測(cè)算法的正確率比Fermat 高.但是在Miller-Rabin 算法提出后該算法的使用少了很多.

算法9 Miller-Rabin(n,t)Input:待檢測(cè)奇數(shù)n ≥3,檢測(cè)迭代輪數(shù)t Output:n 是否是概率素?cái)?shù)1 將n?1 寫(xiě)成n?1=2sr,其中r 是奇數(shù)2 for i=1 to t do 3 取隨機(jī)整數(shù)a ∈[2,n?2]4 計(jì)算y=ar mod n 5 if y=1 且y=n?1 then 6 j=1 7 while j≤s?1 且y=n?1 do 8 y=y2 mod n 9 if y=1 then 10 返回“n 是合數(shù)”11 end 12 j ++13 end 14 if y=n?1 then 15 返回“n 是合數(shù)”16 end 17 end 18 end 19 返回“n 可能是素?cái)?shù)”

Miller-Rabin 的理論依據(jù)是定理6.

定理6取素?cái)?shù)n,令n?1=2sr其中r是奇數(shù).對(duì)任意整數(shù)a滿(mǎn)足gcd(a,n)=1,均有ar≡1 modn或者a2/r≡?1 modn對(duì)某些j,0≤j≤s?1.

Miller-Rabin 檢測(cè)算法對(duì)于一些強(qiáng)偽素?cái)?shù)[11]可能給出錯(cuò)誤的判斷.對(duì)于任一合數(shù),經(jīng)過(guò)Miller-Rabin(n,t)檢測(cè),認(rèn)為是素?cái)?shù)的概率不超過(guò)(1/4)t.

Miller-Rabin 檢測(cè)相對(duì)于Fermat 檢測(cè)、Solovay-Strassen 檢測(cè)效率要高很多,但是仍然需要進(jìn)行模冪運(yùn)算,因此實(shí)際使用中還有一些技巧提高素?cái)?shù)檢測(cè)的效率.

4.2 素?cái)?shù)檢測(cè)效率的提高

(1)進(jìn)行小素?cái)?shù)試除

生成的候選值n可能含有小的素因子,因此在進(jìn)行Miller-Rabin 檢測(cè)前可以先進(jìn)行小素?cái)?shù)試除,分別計(jì)算Ri=nmodpi其中pi是選定的小素?cái)?shù),若存在Ri=0 則表明n是合數(shù),通過(guò)小素?cái)?shù)試除的候選值再進(jìn)行Miller-Rabin 檢測(cè).

(2)針對(duì)3.2節(jié)方法的進(jìn)一步優(yōu)化

若素?cái)?shù)生成算法使用算法5,候選值依次加2,則在小素?cái)?shù)試除過(guò)程中,計(jì)算Ri=nmodpi可以進(jìn)一步提速.對(duì)于初始候選值n計(jì)算一次Ri=nmodpi將結(jié)果進(jìn)行保存,則n=n+ 2時(shí)只需計(jì)算Ri=(Ri+2)modpi,可以將大數(shù)取模運(yùn)算變成一次模加運(yùn)算,有效提高效率.

(3)Miller-Rabin 算法步驟4的優(yōu)化

算法9中步驟4需要進(jìn)行底數(shù)為a的模冪運(yùn)算,模冪耗時(shí)較長(zhǎng); 但取a=2時(shí),模冪運(yùn)算可以簡(jiǎn)化,2r可以通過(guò)移位快速實(shí)現(xiàn).使用Miller-Rabin 檢測(cè)時(shí)需要取t個(gè)不同的a,因此在第一輪迭代中固定a=2可以有效提高整體檢測(cè)效率.

5 實(shí)驗(yàn)結(jié)果

本節(jié)對(duì)上述素?cái)?shù)生成算法進(jìn)行實(shí)驗(yàn)測(cè)試,對(duì)比分析了各算法的效率.測(cè)試使用Sage Math 編程,運(yùn)行在Intel Xeon E5-1620@ 3.60 GHz 處理器的工作站.為了比較不同平臺(tái)對(duì)算法性能的影響,將部分算法移植到智能卡進(jìn)行了測(cè)試.

5.1 生成與小素?cái)?shù)乘積互素?cái)?shù)算法性能對(duì)比

該小節(jié)對(duì)算法1–3的性能進(jìn)行對(duì)比,算法生成一個(gè)輸出的耗時(shí)與小素?cái)?shù)個(gè)數(shù)k強(qiáng)相關(guān),實(shí)驗(yàn)結(jié)果如圖2所示.

圖2 生成與小素?cái)?shù)乘積互素?cái)?shù)算法性能對(duì)比Figure 2 Performance comparison of generating a number co-prime with a product of small primes

圖2可看出當(dāng)k< 60時(shí)算法3有著明顯性能優(yōu)勢(shì),當(dāng)k> 60時(shí)算法1的性能更好一些.但考慮到算法1要存儲(chǔ)預(yù)計(jì)算值且一般取k<60,后續(xù)實(shí)驗(yàn)需要用到生成小素?cái)?shù)乘積互素?cái)?shù)時(shí)都選用算法3.

選擇k=60 的情況在智能卡上進(jìn)行實(shí)現(xiàn),所需預(yù)計(jì)算在卡外進(jìn)行.為了準(zhǔn)確分析算法執(zhí)行時(shí)長(zhǎng),采集功耗曲線進(jìn)行分析(采集功耗曲線可以去除數(shù)據(jù)傳輸?shù)臅r(shí)間,7816 接口數(shù)據(jù)傳輸較慢),算法1–3的功耗曲線如圖3所示.

圖3 智能卡上實(shí)現(xiàn)算法1–3的功耗曲線對(duì)比Figure 3 Comparison of power traces of Algorithm 1–3 on smart card

從圖3中可以明顯看出算法1調(diào)用模乘的次數(shù),算法2–3調(diào)用模冪的次數(shù).大量采集各算法執(zhí)行時(shí)的功耗曲線,量取各次執(zhí)行的時(shí)長(zhǎng),得到平均執(zhí)行時(shí)長(zhǎng).算法1的平均時(shí)長(zhǎng)7.5 ms,算法2的平均時(shí)長(zhǎng)10.5 ms,算法3的平均執(zhí)行時(shí)長(zhǎng)6.7 ms,3 個(gè)算法相對(duì)執(zhí)行時(shí)長(zhǎng)與工作站的實(shí)驗(yàn)結(jié)果一致.

5.2 素?cái)?shù)生成主算法性能對(duì)比

本小節(jié)對(duì)比第3節(jié)中介紹的素?cái)?shù)生成主算法的性能,分別比較平均生成一個(gè)素?cái)?shù)所需素?cái)?shù)檢測(cè)次數(shù)和平均時(shí)長(zhǎng).

由于算法6的性能與輸入?yún)?shù)中選擇素?cái)?shù)的個(gè)數(shù)強(qiáng)相關(guān),因此先分析素?cái)?shù)個(gè)數(shù)對(duì)算法6性能的影響,如圖4所示.

圖4 算法6輸入?yún)?shù)k 的不同取值算法性能對(duì)比(生成512 位)Figure 4 Performance comparison of parameter k’s value of Algorithm 6(generate 512 bits prime)

圖4是生成512 bit 素?cái)?shù)時(shí),素?cái)?shù)個(gè)數(shù)k取不同值對(duì)算法6性能(包括平均素?cái)?shù)檢測(cè)次數(shù)和平均耗時(shí)兩方面)的影響,圖中可以看出輸入的素?cái)?shù)個(gè)數(shù)越多,算法性能越好,因此在條件允許時(shí)使用盡量多的小素?cái)?shù).但是選擇越多的素?cái)?shù),意味著需要越多的預(yù)存空間,因此實(shí)際使用時(shí)需要對(duì)時(shí)間和空間進(jìn)行平衡和取舍.本文選擇性能優(yōu)先,在算法6性能盡量好的情況下,對(duì)比算法4–6、7A和8A五個(gè)算法的性能,結(jié)果如表2所示,表中數(shù)據(jù)是10 萬(wàn)次運(yùn)算得到的平均值.

從表2可知算法4和算法5性能較差,平均時(shí)長(zhǎng)和平均素?cái)?shù)檢測(cè)次數(shù)都沒(méi)有優(yōu)勢(shì); 算法7A和算法8A性能基本相當(dāng),文獻(xiàn)[8]中提到原理上算法8A生成素?cái)?shù)的分布均勻性比算法7A好,因此二者中優(yōu)先考慮算法8A.表中算法6的素?cái)?shù)檢測(cè)次數(shù)比算法7A、8A多一些,但是平均執(zhí)行時(shí)長(zhǎng)更短,分析原因是算法6 的gcd()方法使用Sage Math 的系統(tǒng)函數(shù),效率較高,而算法7A、8A中需要調(diào)用算法3,其中模冪使用二進(jìn)制展開(kāi)法實(shí)現(xiàn),比Sage Math 的系統(tǒng)函數(shù)pow()1分析Python 中函數(shù)pow()的底層C 源碼,指數(shù)長(zhǎng)度不同時(shí)算法不同.性能低,此外算法8A中步驟7直接使用的系統(tǒng)模乘函數(shù),未使用移位提速.因此在專(zhuān)用密碼設(shè)備上使用相同的底層算子實(shí)現(xiàn)算法時(shí),算法8A和算法6時(shí)間基本相當(dāng),甚至?xí)煲恍?對(duì)于生成較短的素?cái)?shù)時(shí)算法8A的平均素?cái)?shù)檢測(cè)次數(shù)更少.

表2 素?cái)?shù)生成主要算法性能對(duì)比Table 2 Performance comparison of main step of prime generation

此外需要注意,表中的平均執(zhí)行時(shí)長(zhǎng)與處理器結(jié)構(gòu)有關(guān),甚至算法間的相對(duì)時(shí)長(zhǎng)也有差異.使用Intel Core i5 8250 4 核8 線程處理器執(zhí)行同樣的程序,生成1024 比特的素?cái)?shù)時(shí),算法8A的執(zhí)行時(shí)長(zhǎng)為5.61 ms而算法7A的平均執(zhí)行時(shí)長(zhǎng)為5.80 ms.因此,平均素?cái)?shù)檢測(cè)次數(shù)更值得關(guān)注.

6 應(yīng)用

素?cái)?shù)在密碼學(xué)領(lǐng)域有著大量的應(yīng)用,常見(jiàn)的非對(duì)稱(chēng)密碼算法RSA 中使用了大素?cái)?shù).RSA 算法基本原理如下.

選擇兩個(gè)大素?cái)?shù)p和q,計(jì)算n=pq,隨機(jī)選取加密密鑰e,使p與(p?1)(q?1)互素,然后計(jì)算解密密鑰d=e?1mod((p?1)(q?1)).e和n作為公鑰,d是私鑰,p,q不再需要,通過(guò)安全方式將其丟棄.加密消息m時(shí)計(jì)算c=memodn,解密時(shí)計(jì)算m=cdmodn.可以通過(guò)CRT 方式提高運(yùn)算速度.為了獲得最大程度的安全性,一般取p和q長(zhǎng)度相等,同時(shí)還要保證p和q不是很接近.

應(yīng)用中,通常使用相同的公鑰e(常取3 或65 537),因此生成算法參數(shù)p和q時(shí)就要保證(p?1)(q?1)與e互素.本節(jié)選擇對(duì)算法3和算法8進(jìn)行改進(jìn),使之生成的素?cái)?shù)p能夠滿(mǎn)足gcd(e,p?1)=1.

(1)e是一個(gè)素?cái)?shù).只需在p的素性檢測(cè)后判斷pmode是否等于1,若等于1 則重新生成素?cái)?shù).

(2)e的所有素因子ei均滿(mǎn)足ei|Π.

取整數(shù)α使之滿(mǎn)足gcd(α,Π)=1 且αei?1≡1 modei對(duì)所有ei均成立.記e+=gcd(e,Π).令算法3步驟1的初值c≡αmode+,可以取c=α+re,r為隨機(jī)數(shù).再令算法8步驟4中a=α2,因?yàn)閑+|Π,所以可保證算法8生成p的序列始終滿(mǎn)足p≡α2j+1mode+,其中j為整數(shù).因此對(duì)所有的ei均有p≡1 modei成立,故可保證gcd(e,p?1)=1.

(3)e不是素?cái)?shù)且存在素因子ei?Π.由(2)可知當(dāng)ei|Π時(shí),通過(guò)對(duì)算法3和算法8的部分參數(shù)進(jìn)行特定取值可以保證p≡1 modei,故只需對(duì)ei?Π驗(yàn)證p≡1 modei是否成立.可以使用定理2進(jìn)行判斷,記只需判斷(p?1)λ(e?)≡1 mode?是否成立,若不成立則重新生成素?cái)?shù).

綜上所述,只要算法3步驟1取c=α+re,算法8步驟4中a=α2,再加一步額外的判斷即可使用算法3和算法8直接生成滿(mǎn)足要求的RSA 的參數(shù)p和q.

不同應(yīng)用中對(duì)素?cái)?shù)有不同的要求,可以根據(jù)相應(yīng)的要求對(duì)算法進(jìn)行適當(dāng)?shù)母脑?使算法能夠直接生成滿(mǎn)足要求的素?cái)?shù).文獻(xiàn)[6]和[8]給出了生成安全素?cái)?shù)、應(yīng)用于ANSI X9.31、生成強(qiáng)素?cái)?shù)等多種不同場(chǎng)景下算法的改造.

7 結(jié)論

本文對(duì)近年來(lái)提出的一些快速素?cái)?shù)生成算法進(jìn)行歸納、總結(jié)和對(duì)比.將素?cái)?shù)生成過(guò)程分為初值生成、增量變換和素性檢測(cè)3 個(gè)過(guò)程,分別介紹了每部分的算法,給出了各算法必要的理論基礎(chǔ),分析了算法的演進(jìn)過(guò)程,并給出一些算法實(shí)現(xiàn)中的技巧,提到了部分算法的安全性.

本文通過(guò)實(shí)驗(yàn)驗(yàn)證了各算法的性能,給出了各算法性能的對(duì)比數(shù)據(jù),由實(shí)驗(yàn)結(jié)果可知改進(jìn)的增量素?cái)?shù)生成算法(算法6),改進(jìn)的M-J 素?cái)?shù)生成算法的特例(算法8A)分別結(jié)合改進(jìn)的模搜索法(算法3)這兩種方案整體性能較好.本文還給出了素?cái)?shù)生成算法在RSA 算法中的應(yīng)用.

本文僅給出了各算法的基本形式和性能分析,實(shí)際用于密碼設(shè)備時(shí)還需要考慮算法實(shí)現(xiàn)[17]的安全性,考慮是否有側(cè)信道信息的泄漏[18],考慮結(jié)果分布是否均勻等,用于RSA 算法時(shí)還需要保證使用的素?cái)?shù)是強(qiáng)素?cái)?shù)[19].