跳到主要內容

臺灣博碩士論文加值系統

(3.236.50.201) 您好!臺灣時間:2021/08/05 20:41
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:王聖宏
研究生(外文):Sheng-HongWang
論文名稱:適用於公開金鑰密碼學系統之以4為基底的低延遲可擴充性蒙哥馬利乘法器
論文名稱(外文):Low-Latency Scalable Radix-4 Montgomery Multiplier for Public Key Cryptosystem
指導教授:謝明得謝明得引用關係
指導教授(外文):Ming-Der Shieh
學位類別:碩士
校院名稱:國立成功大學
系所名稱:電機工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:中文
論文頁數:56
中文關鍵詞:蒙哥馬利乘法器RSA 公開金鑰密碼處理器支援雙領域計算蒙哥馬利乘法器
外文關鍵詞:Montgomery multiplierRSA cryptography processorDual-field Montgomery multiplier
相關次數:
  • 被引用被引用:0
  • 點閱點閱:157
  • 評分評分:
  • 下載下載:19
  • 收藏至我的研究室書目清單書目收藏:0
模乘法運算 (Modular Multiply)近年來被大量應用在公開金鑰密碼學系統,像是RSA(Rivest-Sharmir-Adleman) 密碼學系統或是ECC(Elliptic Curve Cryptography)密碼學系統。而模乘法運算在公開金鑰密碼學系統中一直是相當重要且嚴苛的運算。在目前被提出的模乘法運算演算法之中,蒙哥馬利模乘法演算法是一個非常有效率的方法。在論文中,我們提出了一個以字元為基準,具可擴充性,並搭載低延遲技術之以4 為基底的布斯編碼(Booth encoding)蒙哥馬利乘法器架構。
在傳統以4 為基底的蒙哥馬利模乘法運算中,由於迴圈的暫時運算結果都必須向右位移而造成資料相依性關係問題,使得相鄰處理單元之間的時間延遲必須等兩個時間週期。而在我們論文中所提出來的架構中,提出了低延遲時間的方法,無論我們選用哪一種字元大小,相鄰處理單元之間的時間延遲都會縮減為一個時間週期,資料相依性關係問題得到舒解,而此方法不需要增加運算元個數。
此新技術的實作成果顯示,和其他以4 為基底的蒙哥馬利模乘法器相比較,我們所提出的設計可以節省完成一次1024 位元蒙哥馬利乘法26.5%的運算時間。

Modular multiplication is widely applied to public key cryptosystems like Rivest-Sharmir-Adleman (RSA) and elliptic curve cryptography (ECC).Modular multiplication is always an important and crucial operation in public key cryptosystems. Among existing modular multiplication algorithms, Montgomery’s modular multiplication algorithm is known as a very efficient method for carrying out modular multiplication. This work presents a word-based Booth encoded radix-4 Montgomery modular multiplication algorithm for low-latency scalable architecture.
The data dependency resulting from the inherent right shifting of the intermediate results in the conventional radix-4 Montgomery modular multiplication algorithm is alleviated; thus the latency between neighboring process elements (PEs) is exactly one cycle regardless of the chosen word size. Moreover, the number of the equivalent operands in the accumulation is not increased with operand reduction scheme.
Implementation results show that compared to other Booth encoded radix-4 Montgomery modular multipliers, the proposed design can achieve at least 26.5% time reduction for accomplishing one 1024-bit Montgomery modular multiplication.
目 錄
第一章緒論 ............................................... 1
1.1 研究動機 ................................................................................................................ 1
1.2 論文架構 ................................................................................................................ 2
第二章背景知識介紹 .......................................... 4
2.1 公開金鑰密碼學系統模型 ..................................................................................... 4
2.1.1 RSA 公開金鑰密碼學系統 ......................................................................... 5
2.1.2 ECC 公開金鑰密碼學系統 ......................................................................... 7
2.2 蒙哥馬利演算法性質簡介 ................................................................................... 10
2.2.1 模運算的數學性質 ................................................................................... 10
2.2.2 以2 為基底的蒙哥馬利演算法 ............................................................... 10
2.2.3 蒙哥馬利領域與實數領域的相互轉換 .................................................... 11
2.3 高基底蒙哥馬利演算法 ....................................................................................... 12
2.3.1 傳統高基底蒙哥馬利模乘法演算法 ....................................................... 13
2.3.2 商數決定運算之乘法省略 ....................................................................... 14
2.3.3 商數決定運算之加法省略 ....................................................................... 14
2.3.4 商數管線化之蒙哥馬利模乘法演算法 ................................................... 15
2.4 具可擴充性之蒙哥馬利乘法演算法 .................................................................. 16
2.4.1 以字元為基準具可擴充性之蒙哥馬利乘法演算法 ............................... 16
2.4.2 運算元向左位移之蒙哥馬利乘法演算法 ............................................... 17
2.4.3 應用低延遲技術之以2 為基底的蒙哥馬利模乘法演算法 ................... 17
第三章以 4 為基底的低延遲可擴充性蒙哥馬利乘法器 .................. 19
3.1 應用布斯編碼之設計 .......................................................................................... 19
3.1.1 應用布斯編碼之運算元重新編碼 ........................................................... 19
3.1.2 布斯編碼之硬體設計 ............................................................................... 20
3.2 商數管線化之設計 .............................................................................................. 21
3.2.1 商數管線化之硬體設計 ........................................................................... 22
3.2.2 應用布斯編碼之商數重新編碼 ............................................................... 23
3.3 基於進位儲存形式之以4 為基底的低延遲技術 .............................................. 24
3.3.1 應用低延遲技術之蒙哥馬利乘法器 ....................................................... 24
3.3.2 運算元之重新編列技巧 ........................................................................... 28
3.3.3 二級商數管線化 ....................................................................................... 31
3.3.4 所提出之以4 為基底的低延遲蒙哥馬利模乘法演算法 ....................... 32
3.4 比較與分析 .......................................................................................................... 38
3.4.1 演算法收斂性範圍分析 ........................................................................... 38
3.4.2 演算法之效能分析比較 ........................................................................... 40
第四章硬體架構之設計與實現 ................................... 43
4.1 硬體架構 ............................................................................................................... 43
4.1.1 蒙哥馬利模乘法器整體架構 ................................................................... 43
4.1.2 資料處理單元硬體設計 ........................................................................... 45
4.1.3 支援雙領域運算之蒙哥馬利乘法器設計 ............................................... 47
4.2 驗證方法 .............................................................................................................. 50
4.3 實現結果與比較 .................................................................................................. 51
第五章結論與未來展望 ...................................... 54
5.1 結論 ...................................................................................................................... 54
5.2 未來展望 .............................................................................................................. 54
參考文獻 ................................................. 55

表目 錄
表 3.1 輸入運算元之布斯編碼整理表 ...................................................................... 20
表3.2 商數之布斯編碼整理表 .................................................................................. 23
表4.1 運算域GF(p),運算元為1024 位元之蒙哥馬利乘法速度面積比較表 ..... 52
表4.2 雙領域計算之蒙哥馬利乘法速度面積比較表 .............................................. 52
表4.3 RSA 處理器比較表 ......................................................................................... 53

圖目 錄
圖 2.1 密碼學系統模型 ............................................................................................. 4
圖2.1 RSA 公開金鑰密碼系統之資料加解密圖 .................................................... 6
圖2.3 RSA 公開金鑰密碼系統之參數選取 ............................................................ 6
圖2.4 橢圓曲線上的點加法運算 ............................................................................. 8
圖2.5 橢圓曲線上的點倍數運算 ............................................................................. 8
圖2.6 以2 為基底蒙哥馬利演算法 ........................................................................ 11
圖2.7 傳統高基底蒙哥馬利演算法 ....................................................................... 13
圖2.8 商數決定運算之乘法省略 ........................................................................... 14
圖2.9 商數決定運算之加法省略 ........................................................................... 14
圖2.10 商數管線化之高基底蒙哥馬利演算法 ....................................................... 16
圖3.1 文獻[16]使用之4 對2 加法器 .................................................................... 20
圖3.2 使用布斯編碼之最低有效位元運算處理單元 ........................................... 21
圖3.3 商數決定(quotient determination)之運算示意圖 ........................................ 23
圖3.4 基底四蒙哥馬利演算法資料相依性示意圖 ............................................... 24
圖3.5 傳統架構之第一時間週期示意圖 ............................................................... 25
圖3.6 傳統架構之第二時間週期示意圖 ............................................................... 25
圖3.7 傳統架構之第三時間週期示意圖 ............................................................... 25
圖3.8 延遲暫時運算結果加法之第一時間週期示意圖 ....................................... 26
圖3.9 延遲暫時運算結果加法之第二時間週期示意圖 ....................................... 26
圖3.10 延遲暫時運算結果加法之第三時間週期示意圖 ....................................... 27
圖3.11 傳統架構字元處理單元之4 對2 進位儲存型式加法器示意圖 ............... 28
圖3.12 第i 個字元處理單元之4 對2 進位儲存型式加法器示意圖 .................... 29
圖3.13 第i + 1 個字元處理單元之4 對2 進位儲存型式加法器示意圖 ............. 30
圖3.14 二級商數管線化之資料相依性關係圖 ....................................................... 31
圖3.15 應用低延遲技術之運算元個數示意圖 ..................................................... 37
圖3.16 X 任務與Y 任務中之運算元重新編列示意圖 ........................................ 37
圖3.17 傳統基底四具可擴充性之蒙哥馬利演算法資料相依性關係圖 ............. 40
圖3.18 所提出之低延遲技巧基底四蒙哥馬利演算法資料相依性關係圖 ......... 41
圖4.1 蒙哥馬利乘法器硬體架構圖 ..................................................................... 44
圖4.2 字元資料處理單元示意圖 ......................................................................... 45
圖4.3 資料路徑設計圖 ......................................................................................... 46
圖4.4 進行布斯編碼後之進位儲存加法器輸入運算元示意圖 ......................... 48
圖4.5 適用於雙領域計算之進位儲存加法器輸入運算元示意圖 ..................... 48
圖4.6 適用於雙領域計算之資料路徑設計圖 ..................................................... 49

[1]R. L. Rivest, A. Shamir, and L. Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Comn. ACM, vol. 21, pp. 120-126, Feb. 1978.
[2]N. Koblitz, Elliptic Curve Cryptosystems, Math. Computation, vol. 48, pp. 203-209, 1987.
[3]V .S. Miller, Use of Elliptic Curve in Cryptography, Proc. Adv. Cryptography(Crypto), pp. 417-426, 1986.
[4]P .L. Montgomery, Modular Multiplication without Trial Division, Math. Computation, vol. 44, pp. 519-521, Apr. 1985
[5]P. Kornerup, High-Radix Modular Multiplication for Cryptosystems, Proc. IEEE Symp. Computer Arithmetic, pp. 277-283, Jun. 1993.
[6]William Stallings, Cryptography and Network Security Principles and Practice 5th, Prentice Hall, 2010.
[7]Alfred J. Menezes, Elliptic Curve Public Key Cryptosystems 1st, Springer, 1993.
[8]C. McIvor, M. McLoone, and J. V. McCanny, Modified Montgomery Modular Multiplication and RSA Exponentiation Techniques, IEE Proc.¬Computer and Digital Techniques, vol. 151, no.6, pp. 402-408. Nov. 2004.
[9]M.D. Shieh, J.H. Chen, H.S. Wu, and W.C. Lin, A New Modular Exponentiation Architecture for Efficient Design of RSA Cryptosystem, IEEE Trans. Very Large Scale Integration Systems, vol. 16, no. 9, pp. 1151-1161, Sept. 2008.
[10]M. Huang, K. Gaj, S. Kwon, and T. El-Ghazawi, An Optimized Hardware Architecture for Montgomery Multiplication Algorithm, Proc. Public Key Cryptography (PKC '08), pp. 214-228, 2008.
[11]F. Tenca and C.K. Koc, A scalable architecture for modular multiplication based on Montgomery’s algorithm, IEEE Trans. Computers., vol. 52, no. 9, pp. 1215-1221, Sept. 2003.
[12]D. Harris, R. Krishnamurthy, S. Mathew, and S. Hsu, An Improved Unified Scalable Radix-2 Montgomery Multiplier, IEEE Symp. Computer Arithmetic, pp. 1196–1200, June. 2005.
[13]H. Orup, Simplifying Quotient Determination in High-Radix Modular Multiplication, Proc. IEEE Symp. Computer Arithmetic, pp. 193-199, Jul. 1995.
[14] F. Tenca and A. Tawalbeh, An Efficient and Scalable Radix-4 Modular Multiplier Design Using Recoding Techniques, Proc. Asilomar Conf. Signals, Systems, and Computers, pp. 1445-1450, Nov. 2003.
[15]N. Pinckney and D. M. Harris, Parallel High-Radix Montgomery Multipliers,
Proc. Asilomar Conf. Signals, Systems, and Computers, pp.772-776, Oct. 2008.
[16]M.D. Shieh and W.C. Lin. Word-Based Montgomery Modular Multiplication Algorithm for Low-Latency Scalable Architectures, IEEE Trans. Computers, vol. 59, no. 8, pp.1145-1151, Aug. 2010.
[17]A. D. Booth, A Signed Binary Multiplication Technique, Q. J. Mech. Appl. Math., vol. 4, no.2, pp.236-240, 1951.
[18]N. Pinckney, P. Amberg, and D. Harris, “Parallelized Booth-Encoded Radix-4 Montgomery Multipliers, Proc. 16th IFIP/IEEE Int. Conf. Very Large Scale Integer. (VLSI), pp. 1-6, Oct. 2008.
[19]Huang, M. ; Gaj, K. ; El-Ghazawi, T. “New Hardware Architectures for Montgomery Modular Multiplication Algorithm, IEEE Trans. Computers., no. 99, pp. 923 -936, 2010.
[20]J.Y. Lai and C.Y. Huang, “Elixir: High-Throughput Cost-Effective Dual-Field Processors and the Design Framework for Elliptic Curve Cryptography, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 16, no. 11, pp. 1567-1580, Nov. 2008.
[21]M.D. Shieh, J.H. Chen, “A New Algorithm for high-speed Modular Multiplication Design, IEEE Trans. Circuit and Systems—I: Regular Papers, vol. 56, no. 9, pp. 2009-2019, Sept. 2009.

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top