圓錐曲線加密算法是一種新型的公鑰加密算法，其參數(shù)選擇會(huì)直接影響加密算法的安全性。那么接下來我就給大家簡(jiǎn)單的介紹一下圓錐曲線公鑰加密算法的參數(shù)選擇。

一、有限域Fp上圓錐曲線的參數(shù)選擇

1、有限域Fp上的圓錐曲線

有限域Fp上的圓錐曲線Cp（a，b）是指同余方程：

其中，p是奇素?cái)?shù)。將y ≡ xt （mod p）代入式（1），則圓錐曲線Cp（a，b）的全部點(diǎn)表示為

其中，（a – t 2）–1為（a – t 2）在有限域Fp上的乘法逆元。Cp（a，b）上，定義如下運(yùn)算規(guī)則：

（1）加法運(yùn)算⊕：

1）對(duì)于P = p（t） ∈ Cp（a，b），滿足p（t） ⊕ p（∞） = p（∞） ⊕ p（t） = p（t）。

2）設(shè)P1 = p（t1）， P2 = p（t2）， P3 = p（t3）且t1， t2 ≠ ∞，定義p（t1） ⊕ p（t2） = p（t3）。

其中，

?（2）點(diǎn)P的逆元：

記作–P，當(dāng)P = p（t）時(shí)，則：

（3）標(biāo)量乘運(yùn)算*：

k為整數(shù)且P = p（t） ∈ Cp（a，b），記 ：

目前已有資料證明了圓錐曲線（Cp（a，b）， ⊕）的點(diǎn)和運(yùn)算構(gòu)成群，利用圓錐曲線群（Cp（a，b）， ⊕）可構(gòu)造基于離散對(duì)數(shù)的密鑰交換協(xié)議和公鑰密碼系統(tǒng)的方法，如Diffie-Hellman密鑰交換協(xié)議、ElGamal加密方案、Massey-Omura加密方案等。在加密操作過程中，需要將明文m表示為圓錐曲線Cp（a，b）上點(diǎn)（即明文嵌入），編碼算法為xm = b（m 2 + m + a）–1， ym = bm（m 2 + m + a）–1，在解密操作過程中，譯碼算法為m = ym xm–1。

二、參數(shù)選擇與安全性

在式（1）所定義的圓錐曲線方程Cp（a，b）中包含兩個(gè)參數(shù)，它們的選擇范圍和圓錐曲線加密算法安全性的關(guān)系為 ：

（1）參數(shù)b：

由于該參數(shù)僅在明文嵌入與譯碼中起作用，因此其取值對(duì)于圓錐曲線的安全性不會(huì)產(chǎn)生任何影響。

（2）參數(shù)a：

由于該參數(shù)涉及到圓錐曲線群上的計(jì)算，其取值直接影響到圓錐曲線加密體制的安全性，因此需要進(jìn)行討論。

1）當(dāng)a為有限域Fp上的二次剩余，即當(dāng)Legendre符號(hào)（p/a）=1時(shí)，通過構(gòu)造映射，設(shè)θ1和θ2為模p的二次剩余a的兩個(gè)根（其中θ1 ≠ θ2），在已知θ的情況下可以構(gòu)造從有限域Fp上的圓錐曲線群（Cp（a，b），）⊕到有限域Fp上的普通乘法群（Zp ，*）的映射：

其中，θ12 = θ22 = a。

經(jīng)過式（6）映射后，有限域Fp上的圓錐曲線群的離散對(duì)數(shù)的安全性被降低到有限域Fp上的乘法群上的離散對(duì)數(shù)問題的安全性。特別地，當(dāng)a為有限域Fp上的二次剩余且θ為a的二重根時(shí)，不僅可按照式（6）構(gòu)造從圓錐曲線群（Cp（a，b），）⊕到有限域Fp上的乘法群（Zp ，*）的映射，還可以按照式（7）構(gòu)造從有限域Fp上的圓錐曲線加群（Cp（a，b），）⊕到有限域Fp上的普通加法群（Zp，+）的映射：

其中，θ2 = a。

經(jīng)過式（7）映射后，有限域Fp上的圓錐曲線群的離散對(duì)數(shù)的安全性被降低到有限域Fp上的普通加法群上的離散對(duì)數(shù)問題的安全性。此時(shí)圓錐曲線上的標(biāo)量乘運(yùn)算可以通過域上的乘法運(yùn)算求解，因而可通過域上的除法計(jì)算求解任意點(diǎn)的逆元。從而使得定義在該圓錐曲線上的加群（Cp（a， b）， ）⊕變得毫無安全性可言。

2）當(dāng)a不是有限域Fp上的二次剩余，即在Fp域上不存在a的平方根θ使θ2=a時(shí)，此時(shí)需通過擴(kuò)域才有可能在規(guī)模至少是有限域2pF的域上構(gòu)造與圓錐曲線群（Cp（a， b），）⊕同構(gòu)的普通乘法群。由于有限域2pF上操作數(shù)的長度比有限域Fp上操作數(shù)的長度多了一倍，因此，此時(shí)構(gòu)成的映射并未降低原有限域Fp上的圓錐曲線離散對(duì)數(shù)的安全性。

綜上所述，為了保證圓錐曲線公鑰密碼體制的安全性，需要取適當(dāng)?shù)腶值，從而使，即在有限域Fp上a不是模p的二次剩余，二次剩余的判定可通過Euler判別法計(jì)算。參數(shù)a的取值算法具體描述如下：

算法 有限域Fp上產(chǎn)生圓錐曲線參數(shù)a的算法。

輸入 模p的取值。

輸出 適當(dāng)?shù)腶值。

步驟1 隨機(jī)取適當(dāng)?shù)腶值；

步驟2 計(jì)算；

步驟3 若返回步驟1；

步驟4 得到適當(dāng)?shù)腶值，算法結(jié)束。

2、環(huán)Zn上圓錐曲線的參數(shù)選擇

環(huán)Zn上的圓錐曲線Cn（a，b） 是指同余方程：

其中，p，q為兩個(gè)不等的奇素?cái)?shù)；n= pq。模n下的加、減、乘法運(yùn)算構(gòu)成了環(huán)Zn上的運(yùn)算，根據(jù)式（3）可得到Cn（a， b）上的點(diǎn)，并通過在Cn（a， b）的點(diǎn)上定義加法運(yùn)算⊕，從而得到環(huán)Zn上的圓錐曲線群（Cn（a， b），）⊕。其中，環(huán)Zn中加法運(yùn)算⊕的定義類似于式（2）~式（5）。

對(duì)于環(huán)Zn上的圓錐曲線（Cn（a，b）， ）⊕的應(yīng)用，如利用環(huán)Zn上的圓錐曲線對(duì)RSA公鑰密碼體制進(jìn)行模擬。若按照式（6）構(gòu)造從環(huán)Zn上的圓錐曲線群到環(huán)Zn上的乘法子群的映射，則必須要在環(huán)Zn上計(jì)算參數(shù)a的二次剩余。當(dāng)合數(shù)n為兩相異素?cái)?shù)p， q的乘積時(shí)，對(duì)于模n的二次剩余問題有：

（1）在未知n的分解的情況下，模n的二次剩余判定問題（QRP）是一個(gè)數(shù)學(xué)難題。

（2）分解n的計(jì)算等價(jià)于求模n的平方根。

由此可見，當(dāng)合數(shù)n的分解未知時(shí)，在環(huán)Zn中無論是二次剩余的判斷問題還是平方根的求解問題都是困難的。因此，構(gòu)造從環(huán)Zn上的圓錐曲線群到環(huán)Zn上的乘法子群的映射是困難的。 綜上所述，當(dāng)圓錐曲線建立在環(huán)Zn上時(shí)，為了避免安全上的漏洞，提高運(yùn)算的安全性，對(duì)于參數(shù)a的取值可選擇如下兩種情況，其中的（a/p）或（a/q）可通過Euler判別法計(jì)算：

此時(shí)，Jaccobi符號(hào)。根據(jù)Jaccobi符號(hào)的概念可知，當(dāng)Jaccobi符號(hào)結(jié)果為–1時(shí)，在環(huán)Zn中不存在a的二次剩余。

盡 管 此 時(shí)Jaccobi符 號(hào)，但在環(huán)Zn中并不存在a的二次剩余。

三、擴(kuò)展的圓錐曲線及其參數(shù)選擇

在特征char（F）=2的有限域上，任何元素t與2的標(biāo)量乘2*t=t+t=0，其中，0指char（F）=2的有限域域中的零元。由式（5）可知，當(dāng)t1 = t2 = t ≠ ∞且t1 + t2 ≠ 0時(shí)，p（t3） = 2*p（t） = p（（t2+a）（2t）–1）。特別地，在特征char（F）=2的有限域上p（t3） = 2*p（t） = p（∞），即在特征char（F）=2的有限域上圓錐曲線群僅存在階為2的子群。顯然，該運(yùn)算使得圓錐曲線上的離散對(duì)數(shù)運(yùn)算不能夠加密任何數(shù)據(jù)。 為了使圓錐曲線公鑰密碼體制在特征為2的有限域上實(shí)現(xiàn)，將原圓錐曲線的定義方程擴(kuò)展為式（9）的形式：

根據(jù)圓錐曲線的相關(guān)性質(zhì)，由式（9）推導(dǎo)出特征char（F）=2有限域上的圓錐曲線方程上群的運(yùn)算：

（1）對(duì)于加法運(yùn)算⊕，有p（t1） ⊕ p（t2） = p（t3），其中：

（2）當(dāng)t≠0且t≠∞時(shí)，倍乘運(yùn)算*為：

綜上所述，改進(jìn)后的圓錐曲線中增加了參數(shù)c，通過改變參數(shù)c的取值可以使圓錐曲線公鑰密碼體制建立在任意特征的有限域上。設(shè)t≠0且t≠∞，參數(shù)c的取值按如下方式進(jìn)行產(chǎn)生，

（1）當(dāng)char（F）≠2時(shí)，此時(shí)令參數(shù)c=0，從而倍乘：

（2）當(dāng)char（F）=2時(shí)，此時(shí)令參數(shù)c≠0，從而倍乘：

通過上述分析可知，有限域Fp和環(huán)Zn上圓錐曲線密碼算法安全性主要取決于參數(shù)a的選擇。

admin

收藏 海報(bào)分享