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

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

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

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

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

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

（1）加法運算⊕：

1）對于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）點P的逆元：

記作–P，當P = p（t）時，則：

（3）標量乘運算*：

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

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

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

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

（1）參數(shù)b：

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

（2）參數(shù)a：

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

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

其中，θ12 = θ22 = a。

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

其中，θ2 = a。

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

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

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

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

輸入 模p的取值。

輸出 適當?shù)腶值。

步驟1 隨機取適當?shù)腶值；

步驟2 計算；

步驟3 若返回步驟1；

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

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

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

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

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

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

（2）分解n的計算等價于求模n的平方根。

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

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

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

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

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

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

（1）對于加法運算⊕，有p（t1） ⊕ p（t2） = p（t3），其中：

（2）當t≠0且t≠∞時，倍乘運算*為：

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

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

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

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

admin

收藏 海報分享