(3.239.56.184) 您好!臺灣時間:2021/05/13 12:40
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

: 
twitterline
研究生:呂易珊
研究生(外文):Yi-shan Lu
論文名稱:WeilPairing的實作改進
論文名稱(外文):Efficient Implementation of the Weil Pairing
指導教授:官大智官大智引用關係
指導教授(外文):D. J. Guan
學位類別:碩士
校院名稱:國立中山大學
系所名稱:資訊工程學系研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:中文
論文頁數:41
中文關鍵詞:橢圓曲線Miller演算法Weil Pairing
外文關鍵詞:Miller''''s algorithmWeil PairingElliptic Curve
相關次數:
  • 被引用被引用:0
  • 點閱點閱:188
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:19
  • 收藏至我的研究室書目清單書目收藏:0
由於現今研究結果顯示, 目前解決橢圓曲線離散對數問題最有效率的演算法只能在指數時間內, 因此這個問題能夠提供許多密碼學上的應用。Weil pairing 擁有非退化性和雙線性兩種特性, 將橢圓曲線上的一對特殊點映射到有限體上乘法群。在pairing 被發現可以將橢圓曲線離散對數問題對應到有限體上的離散對數問題之後, 這方面的相關也逐漸受到重視。1996年由Miller 第一個提出有效計算pairing 的演算法, 爾後有許多學者以此研究為基礎, 將此演算法做改進。2006年,Blake 等學者提出以共軛線的方式減少所需計算的直線數量, Liu 等學者則是將Blake 的想法加以擴充提出兩種改良方式。本文即以此兩篇論文為基礎, 提出同時使用NAF 和分段演算法的方式, 並且實作分析。
The most efficient algorithm for solving the elliptic curve discrete logarithm problem can only be done in exponential time. Hence, we can use it in many cryptographic applications. Weil pairing is a mapping which maps a pair of points on elliptic curves to a multiplicative group of a finite field with nondegeneracy and bilinearity. Pairing was found to reduce the elliptic
curve discrete logarithm problem into the discrete logarithm problem of a finite field, and became an important issue since then. In 1986, Miller proposed an efficient algorithm for computing Weil pairings. Many researchers focus on the improvement of this algorithm. In 2006, Blake et al. proposed the reduction of total number of lines based on the conjugate of a line. Liu
et al. expanded their concept and proposed two improved methods. In this paper, we use both NAF and segmentation algorithm to implement the Weil pairing and analyse its complexity.
1 緒論1
1.1 研究背景. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 研究動機. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 研究目的. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.4 論文架構. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 相關背景知識3
2.1 橢圓曲線. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1.1 定義. . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1.2 群法則. . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Divisors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3 Weil Pairing 及其相關演算法7
3.1 定義與性質. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2 Miller演算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.3 BMX演算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.4 LHC演算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
4 本文提出的改進方法18
4.1 主要想法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
4.1.1 NAF(Non-adjacent form) . . . . . . . . . . . . . . . . . 18
4.1.2 區段演算法. . . . . . . . . . . . . . . . . . . . . . . . . 19
4.2 改進演算法. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.2.1 本文提出之演算法. . . . . . . . . . . . . . . . . . . . . 23
4.2.2 實例. . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.2.3 結果分析. . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.2.4 實驗結果. . . . . . . . . . . . . . . . . . . . . . . . . . 28
5 結論與未來展望30
參考文獻32
[1] S.A. Vanstone A.J. Menezes, T. Okamoto. Reducing elliptic curve logarithms
to logarithms in a finite field. IEEE Transactions on Information
Theory, 1993.
[2] Gwoboa Horng Chao-Liang Liu and Te-Yu Chen. Further refinement of
pairing computation based on miller’s algorithm. Applied Mathematics
and Computation, 2007.
[3] H. Shacham D. Boneh, B. Lynn. Short signature from the weil pairing. In
ASIACRYPT 2001, LNCS 2248, Springer-Verlag, pages 514–532, 2001.
[4] V.K. Murty I.F. Blake and G. Xu. Refinement of miller’s algorithm for
computing the weil/tate pairing. Journal of Algorithms 58, pages 134–
149, 2006.
[5] V. Miller. Short programs for functions on curve. Unpublished
manuscript, 1986.
[6] Xiaoliang Xu Ting Wu, Min Zhang and Rongbo Wang. Improved algorithm
for tate pairing computation. In ISECS, 2008.
[7] Lawrence C. Washington. Elliptic Curves: Number Theory and Cryptography.
CHAPMAN& HALL/CRC, 2003.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔