基於演化計算的安全橢圓曲線快速選擇算法的製作方法
2023-08-11 01:22:41
專利名稱：基於演化計算的安全橢圓曲線快速選擇算法的製作方法
技術領域：
本發明屬於信息安全保護技術領域，涉及的是一種基於演化計算的安全橢圓曲線
快速選擇算法。
背景技術：
1985年Neal Koblitz和Victor Mille提出了橢圓曲線密碼體制(ECC)，其安全 性是建立在橢圓曲線離散對數計算困難性的基礎之上，具有安全性高、佔用帶寬小、計算復 雜度高等優點，近二十年來已成為國際密碼學的研究熱點。 ECC算法的標準化，有取代RSA在公鑰密碼霸主地位的趨勢，且ECC已經逐漸被包 含到IEEE、ANSI、ISO和NIST等發布的標準中。特別是美國NIST推薦的15條曲線也成為 目前工程應用中常選用的橢圓曲線。但是選擇安全曲線是一個難題，現有的算法主要有兩 種復乘法(CM)和隨機選擇法。對於CM方法，它是根據給定的階來選取符合此階的ECC曲 線，實現的速度相對較快，但是這種算法的缺陷是產生的曲線具有某種特定的結構特徵，存 在潛在的安全威脅。因此，一般都利用隨機選擇法來選擇曲線。隨機選取的橢圓曲線的安 全性大多數依賴於曲線的階的大小，階越大，計算複雜度就越高，安全性越強， 一般階只要 含有大於2160的素因子即可以認為是安全的，因此，如何求取曲線的階是選擇安全曲線的 一個重要的問題。求階算法有以下幾種Schoof's algorithm、SEA(Schoof-Elkies-Atkin) 算法、Satoh算法、Fouquet算法、SST算法、AGM算法和MSST算法等，但是這些算法的計算 複雜度都比較高，選擇曲線的速度比較慢，不利於快速求解安全曲線。
發明內容
鑑於以上所述現有技術存在的問題和不足，本發明的目的在於提出一種基於演化 計算的安全橢圓曲線快速選擇算法，該算法選擇的安全曲線基域的覆蓋範圍大，能夠抵禦 常見的攻擊威脅，提高安全曲線性。
為達到上述目的，本發明採用如下方案 本發明的基於演化計算的安全橢圓曲線快速選擇算法，其具體步驟如下
(1)、利用Weil定理設計一條Koblitz型橢圓曲線，然後，採用以2為特徵的子域 擴展算法計算Koblitz型橢圓曲線的階#￡(^ )，其計算方程為
當a = 0， b = 1時， 等 )=2"+。=2"+(+ )"} =2" +1-1+擒+(-1-細 =2" +(-1)"(力, 當a = l，b = 1時，令d二V^，那麼 , ):y+i《+《)-y+i一((i+^,)"+(lJ/)")formula see original document page 4
(2)、利用類似於最大最小蟻群(MAS)算法設計出適合安全曲線基域搜索的模
型，採用素數判定算法判定該點對應的階是否為大素數，如果該點對應的階含有大素數因
子，則說明該點所對應的域含有安全橢圓曲線，否則，不含有安全曲線，根據該原則挑選出
安全橢圓曲線，其具體如下 (2-l)、計算若干素數的階，並存儲； (2-2)、參數的初始化，取a = IP = 5，信息素蒸發因子P = 0.02，迭代次數大 於20次能得到比較好的結果，其中每次迭代螞蟻的數量取5 ; (2-3)、每次迭代開始，將5隻螞蟻隨機放在不同點，螞蟻每到達一個點，採用素數 判定算法判定該點對應的階是否為大素數，然後按照蟻群算法模型構建的規則選擇下一個 要到打的點，每隻螞蟻每走一步進行一次信息素局部更新；每次迭代結束後，選擇一個最優 螞蟻對信息素進行一次全局更新，如果該點對應的階含有大素數因子，則說明該點所對應 的域含有安全橢圓曲線，否則，不含有安全曲線，直到找到對應的基點的階是大素數，挑選 出含有大素數階的安全橢圓曲線。 本發明的基於演化計算的安全橢圓曲線快速選擇算法與現有技術相比具體有的 優點在於該算法選擇的安全橢圓曲線與NIST推薦的安全曲線具有相同的安全準則，產生 的曲線能夠抵禦目前常見的攻擊，理論分析及實驗數據表明，安全曲線的最大基域超過美 國NIST公布的15條曲線中基域最高的571bit。
圖1是本發明的基於演化計算的安全橢圓曲線快速選擇算法的流程圖； 圖2是本發明中25個(0-100之間所有素數)素數階的具體數據圖； 圖3是本發明中的蟻群算法模型圖； 圖4是本發明中蟻群算法迭代10次後的結果圖； 圖5是本發明中蟻群算法迭代20次後的結果圖； 圖6是本發明通過實驗得到得m = 163的安全域各個參數、基點以及運算時間圖 圖7是本發明通過實驗得到得m = 233的安全域各個參數、基點以及運算時間圖 圖8是本發明通過實驗得到得m = 283的安全域各個參數、基點以及運算時間圖 圖9是本發明通過實驗得到得m = 409的安全域各個參數、基點以及運算時間圖 圖10是本發明通過實驗得到得m = 571的安全域各個參數、基點以及運算時間 具體實施例方式
下面結合附圖對本發明的實施作進一步詳細的說明。 本發明的基於演化計算的安全橢圓曲線快速選擇算法，如圖1所示，具體實現步 驟如下 (1)、利用Weil定理設計一條Koblitz型橢圓曲線，然後，採用以2為特徵的子域 擴展算法計算Koblitz型橢圓曲線的階能(《 )，其計算方程為
當a = 0， b = 1時， #￡(/p=2" +《)=2" +1—{("^+^!T +(~^—4'〕"} =2"+l- =2" +1-垂((^-1)" +(-l)"dl)T} 當a = l，b = 1時，令^ = 7^，那麼 =2" +i—(< +o=y /)" +(i 4')"} =2"+14((1+勿+(1-細 (2)、利用類似於最大最小蟻群(MMAS)算法設計出適合安全曲線基域搜索的模 型，採用素數判定算法判定該點對應的階是否為大素數，挑選出安全橢圓曲線，其具體如 下 (2-1)、計算0-100之間素數的階，並將其存儲，如圖2所示，第一列為基域大小，第 二列為該域的階； (2-2)、參數的初始化，取a = IP = 5，注重啟發信息在探索中的作用，信息素蒸
發因子P 二0.02，在PC機中的仿真實驗表明P取較小的數避免蟻群算法過快收斂，蟻群
算法模型如圖3所示，每一個點代表一個m值，也對應相應的階。在PC機中的仿真實驗表
明迭代次數大於20次能得到比較好的結果，其中每次迭代螞蟻的數量取5 ; (2-3)、每次迭代開始，將5隻螞蟻隨機放在不同點，螞蟻每到達一個點，採用素數
判定算法判定該點對應的階是否為大素數，如果該點對應的階含有大素數因子，則說明該
點所對應的域含有安全橢圓曲線，否則，不含有安全曲線，然後，如圖3所示，按照蟻群算法
模型構建的規則選擇下一個要到達的點。每隻螞蟻每走一步進行一次信息素局部更新；每
次迭代結束後，選擇一個最優螞蟻對信息素進行一次全局更新。圖4是迭代10次後的結
果，圖5是迭代20次後的結果，其中黑色點表明信息素含量很高，這些點有很大的可能性是
大素數；灰色點表明信息素部分揮發，這些點有較小的可能性是大素數；白色點表明信息
素已經達到最小值，表明這些點幾乎不可能是大素數。從圖4，圖5的結果中可以看出，m =
5， 7， 13， 19， 23， 41， 83時候能夠找到對應的基點的階是素數，挑選出安全橢圓曲線。 本發明的基於演化計算的安全橢圓曲線快速選擇算法在PC機上，其中，硬體平
臺:CPU掘s卿ron 2800+內存256MB硬碟80G，軟體平臺-Microsoft Visual C++2005,
初步完成了 F(22°°°)以內Koblitz安全曲線的產生實驗，其實驗結果表明 ①、該算法選擇的安全曲線基域，最大超過1900bit (PC機耗時5個小時)，超過美
國NIST公布的15條曲線中基域最高的571bit ; ②、已有的163bit以上的安全曲線基域有如下面形式的Koblitz曲線Ei :y2+xy = f+^+l，701bit基域產生結果如下
k表示基域，n為基域為k的階
k = 2'7Q1
同時也覆蓋了美國NIST公布的F(2脫) F(2^)5條Koblitz安全曲線，如圖6、圖 7、圖8、圖9、圖10所示，其中圖6、圖7、圖8、圖9、圖10分別是通過實驗得到的k = 2' 163， k = 2~233， k = 2~283， k = 2~409和k = 2~571安全域的各個參數、基點以及運算時間。
權利要求
一種基於演化計算的安全橢圓曲線快速選擇算法，其特徵在於，該方法具體步驟如下(1)、利用Weil定理設計一條Koblitz型橢圓曲線，然後，採用以2為特徵的子域擴展算法計算Koblitz型橢圓曲線的階其計算方程為當a＝0，b＝1時， #E ( F 2 n )= 2 n+1- ( t1n + t2n )= 2 n+1-{ (- 1 2+ 7 2i) n+ (- 1 2- 7 2i) n} = 2 n+1- 1 2n { (-1+ 7i) n+ (-1- 7i) n} = 2 n+1- 1 2n { ( 7i-1) n+ (-1) n ( 7i+1) n} 當a＝1，b＝1時，令那麼 #E ( F 2 n )= 2 n+1- ( t1n + t2n )= 2 n+1-{ ( 1 2+ 7 2i) n+ ( 1 2- 7 2i) n} = 2 n+1- 1 2n { (1+ 7i) n+ (1- 7i) n} (2)、利用類似於最大最小蟻群(MMAS)算法設計出適合安全曲線基域搜索的模型，採用素數判定算法判定該點對應的階是否為大素數，挑選出安全橢圓曲線，其具體如下(2-1)、計算若干素數的階，並存儲；(2-2)、參數的初始化，取α＝1β＝5，信息素蒸發因子ρ＝0.02，迭代次數大於20次能得到比較好的結果，其中每次迭代螞蟻的數量取5；(2-3)、每次迭代開始，將5隻螞蟻隨機放在不同點，螞蟻每到達一個點，採用素數判定算法判定該點對應的階是否為大素數，然後按照蟻群算法模型，構建的規則選擇下一個要到達的點，每隻螞蟻每走一步進行一次信息素局部更新；每次迭代結束後，選擇一個最優螞蟻對信息素進行一次全局更新，如果該點對應的階含有大素數因子，則說明該點所對應的域含有安全橢圓曲線，否則，不含有安全曲線，直到找到對應的基點的階是大素數，挑選出含有大素數階的安全橢圓曲線。F2009102005047C00011.tif,F2009102005047C00015.tif
全文摘要
本發明的公開了一種基於演化計算的安全橢圓曲線快速選擇算法，該算法包括步驟如下(1)利用Weil定理設計一條Koblitz型橢圓曲線，然後，採用以2為特徵的子域擴展算法計算Montgomery型橢圓曲線的階；(2)利用類似於最大最小蟻群(MMAS)算法設計出適合安全曲線基域搜索的模型，採用素數判定算法判定該點對應的階是否為大素數，挑選出安全橢圓曲線。本發明與現有技術相比具有的優點在於該算法選擇的安全橢圓曲線與NIST推薦的安全曲線具有相同的安全準則，產生的曲線能夠抵禦目前常見的攻擊，理論分析及實驗數據表明，安全曲線的最大基域超過目前NIST公布的15條曲線中基域最高的571bit。
文檔編號G06N3/00GK101714074SQ20091020050
公開日2010年5月26日 申請日期2009年12月22日 優先權日2009年12月22日
發明者劉禮黎, 張煥國, 時向勇, 朱美麗, 王潮 申請人:上海大學