目 錄 第一章緒論 ............................................... 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