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

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:洪清波
研究生(外文):Ching-Po Hung
論文名稱:多指數運算演算法使用無相鄰非零位元碼
論文名稱(外文):Algorithms for Multicomputations with Nonadjacent Form
指導教授:楊吳泉楊吳泉引用關係
指導教授(外文):Wu-Chuan Yang
學位類別:博士
校院名稱:義守大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2016
畢業學年度:104
語文別:英文
論文頁數:73
中文關鍵詞:多指數運算無相鄰位元碼公開金鑰滑動視窗
外文關鍵詞:Multicomputationsnonadjacent formpublic keysliding window
相關次數:
  • 被引用被引用:0
  • 點閱點閱:203
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
多指數運算(Multicomputations)使用於ElGamal類型密碼器。基於平方與乘法演算法及無相鄰非零位元碼,許多的多指數運算演算法,致力於降低其效能参數(平均聯合漢明加權率AJHR),以加速多指數運算。公元2000年,Dimitrov等提出三位元重編碼法則(簡稱DJM法),它是簡單且易實現的,藉由軟體模擬,它的效能(AJHR)提升為0.534。公元2007年,Yang等提出非同步的方法(簡稱SS1),比較DJM法,SS1僅多使用兩個記憶體,它的效能提升為0.444。另外,公元1995年,Koc針對單指數運算(ax),提出固定長度非零視窗法(簡稱CLNW)。本論文分別延伸DJM、SS1、與CLNW,提出如下多指數運算演算法。
1. 延伸DJM,提出三種DJM-type:三位元滑動視窗方式(DJM-O)、由右到左 一位元滑動視窗方式(DJM-R)、及由左到右一位元滑動視窗方式(DJM-L);他們的效能參數分別是 0.521、 0.515、與0.511。
2. 提出四位元重編碼法則、延伸三種DJM-type為DJM-4O、DJM-4R、與
DJM-4L;他們的效能參數分別是0.50958、0.50958、與0.5043。
3. 延伸SS1,提出SS2~SS5;他們的效能參數分別是0.389、0.3773、0.3745、與0.3738。
4. 延伸CLNW至多指數運算,提出兩種固定非零長度滑動視窗法(CNSW2與 CNSW3);他們的效能參數分別是0.407與0.248。

Multicomputations are used in some ElGamal-like public key cryptosystems. Based on the square & multiply method with nonadjacent form, some algorithms aim to reduce the average Joint Hamming Ratio (AJHR) to enhance the performance of computing multicomputations. In 2000, Dimitrov et al. showed a simple and practical recoding algorithm with eight 3-bit reduction rules named DJM and simulated its AJHR equals 0.534 by software. In 2007, Yang et al. displayed an asynchronous strategy SS1 which needed only two extra registers compared to the DJM method and proved its AJHR equals 0.444. In 1995, Koc published the constant length nonzero window method (CLNW) for single-exponentiation ax. In this dissertation, we extend DJM, SS1 and CLNW to new algorithms respectively as follows.
1. Based on the DJM method, three DJM-types are showed: the 3-digit sliding window (DJM-O), the 1-digit right-to-left sliding window (DJM-R), and the 1-digit left-to-right sliding window (DJM-L). Their AJHRs equal 0.521, 0.515, and 0.511, respectively.
2. We show 4-bit reduction rules and extend the DJM-types with 4-bit reduction rules to DJM-4O, DJM-4R, and DJM-4L. Their AJHRs equal 0.50958, 0.50958, and 0.5043, respectively.
3. Based on SS1, SS2~SS5 are proposed and their AJHRs equal 0.389, 0.3773, 0.3745, and 0.3738 respectively.
4. Based on CLNW, constant nonzero sliding window methods named CNSW2, CNSW3 for multicomputations are showed. Their AJHRs equal 0.407, 0.248 respectively.

Abstract (in Chinese) ------------------------------------ i
Abstract (in English) ----------------------------------- ii
Acknowledgments ---------------------------------------- iii
Contents ------------------------------------------------ iv
List of Figures ----------------------------------------- vi
List of Tables ----------------------------------------- vii
Chapter 1 Introducton ------------------------------------ 1
Chapter 2 Preliminaries ---------------------------------- 4
2.1 Review of the DJM Method ------------------------------5
2.2 Review of the SS1 method ------------------------------6
2.3 CLNW for Scalar Computation xA -----------------------12
Chapter 3 The DJM-type Methods ---------------------------13
3.1 Preparation of Proving the DJM Algorithm -------------13
3.2 Analysis of the DJM-O Method -------------------------15
3.3 Analysis of the DJM-R and DJM-L Methods --------------17
Chapter 4 Algorithms with 4-bit Reduction Rules ----------22
4.1 The DJM-4O Algorithm ---------------------------------22
4.2 Preparation of Proving the DJM-4O Algorithm ----------24
4.3 Analysis of the DJM-4O Method ------------------------26
4.4 Analysis of the DJM-4R and DJM-4L Methods ------------28
Chapter 5 Asynchronous Algorithms with NAF ---------------33
5.1 SS2 --------------------------------------------------33
5.2 SS3 --------------------------------------------------38
5.3 SS4 --------------------------------------------------40
5.4 SS5 --------------------------------------------------43
Chapter 6 Constant Nonzero Sliding Window Methods --------47
6.1 CNSW2 ------------------------------------------------47
6.2 CNSW3 ------------------------------------------------51
Chapter 7 Conclusion -------------------------------------56
Conferences ----------------------------------------------57
Publication ----------------------------------------------61
Vita -----------------------------------------------------62

[1] S. Arno and F. S. Wheeler, “Signed digit representations of minimal hamming weight,” IEEE Transactions on Computers, vol. 42, no. 8, pp. 1007–1010, 1993.
[2] J. Bos and M. Coster. Addition chain heuristics. In G. Brassard, editor, Advances in Cryptology-CRYPTO 89, Proceedings, Lecture Notes in Computer Science, No. 435, pages 222-229. New York, NY: Springer-Verlag, 1990.
[3] E. F. Brickelland, D. M. Gordon, K. S. McCurley, and D. Wilson, “Fast exponentiation with precomputation,” Advances in Cryptology–Eurocrypt’92, LNCS 658, Springer-Verlag, pp. 200–207, 1992.
[4] H. Cohen, A. Miyagi, and T. Ono, “Efficient elliptic curve exponentiation using mixed coordinates,” in Advances in Cryptology–AsiaCrypt’98, LNCS 1514. Springer-Verlag, pp. 51–65, 1998.
[5] H. Cohen, “Analysis of the Sliding Window Powering Algorithm” J. Cryptology, vol. 18, no. 1, pp.63-76, 2005.
[6] V. S. Dimitrov, G. A. Jullien, and W. C. Miller, “Algorithms for multi- exponentiation based on complex arithmetic,” in Proceedings of the 13th IEEE Symposium on Computer Arithmetic, pp. 208–215, 1997.
[7] V. S. Dimitrov, G. A. Jullien, and W. C. Miller, “Complexity and fast algorithms for multi-exponentiation,” IEEE Transactions on Computers, vol. 49, no. 2, pp. 141–147, 2000.
[8] T. ElGamal, “A public key cryptosystem and a signature scheme based on discrete logarithms,” IEEE Transactions on Information Theory, vol. 31, no. 4, pp. 469–472, 1985.
[9] FIPS186-2, “Digital Signature Standard (DSS),” 2001, http://csrc.nist.gov/publications/fips/.
[10] D. M. Gordon, “A survey of fast exponentiation methods,” Journal of Algorithms, vol. 27, pp. 129–146, 1998.
[11] J. Jedwab and C. J. Mitchell, “Minimum weight modified signed-digit representations and fast exponentiation,” Electronics Letters, vol. 25, no. 17, pp. 1171-1172, 1989.
[12] M. Joye and S. M. Yen, “Optimal left-to-right binary signed-digit recoding,” IEEE Transactions on Computers, vol. 49, no. 7, pp. 740–748, 2000.
[13] M. E. Kaihara, N. Takagi, “Bipartite modular multiplication method”, IEEE Transactions on Computers, vol. 57, no. 2, pp. 157–164, 2008.
[14] D. E. Knuth, The Art of Computer Programming, vol 2. Seminumerical algorithms, Addison-Wesley, 1969, 2nd edition 1982, 3rd edition 1998.
[15] Ç. K. Koç, “High-speed RSA implementations,” RSA Laboratories, Technique Notes TR201, Available from URL: http://www.rsasecurity.com/ rsalabs/, pp. 9–32, 1994.
[16] C. K. Koc, “Analysis of Sliding Window Techniques for Exponentiation”, Computers and Mathematics with Applications, 30(10):17-24, 1995.
[17] C. H. Lim and P. J. Lee, “More flexible exponentiation with precomputation,” Advances in Cryptology-Crypto''94, LNCS 839, Springer-Verlag, pp. 95–107, 1994.
[18] A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1997.
[19] B. Möller, “Algorithms for multi-exponentiations," 8th Annual Workshop on Selected Areas in Cryptography -SAC 2001, LNCS 2259, Springer-Verlag, pp. 165–180, 2001.
[20] P. L. Montgomery, “Modular multiplication without trial division,” Mathematics of Computation, vol. 44, no. 170, pp. 519–521, 1985.
[21] J. Muir and D. Stinson, “Minimality and other properties of the width-w nonadjacent form,” University of Waterloo, Tech. Rep. CORR 2004-08, 2004, http://www.cacr.math.uwaterloo.ca, 2005.
[22] G. W. Reitwiesner, “Binary arithmetic,” Advance in computers, pp. 231–308, 1960.
[23] X. Ruan, R. S. Katti, “Left-to-Right Optimal Signed-Binary Representation of a Pair of Integers”, IEEE Transactions on Computers, vol. 54, no. 2, pp. 124–131, 2005.
[24] C. P. Schnorr, “Efficient Identification and Signatures for Smart Cards,” Advances in Crypto- graphy, Proc. CRYPTO’89, pp. 239-252, 1989.
[25] J. A. Solinas, “Low-weight Binary Representations for Pairs of Integers,” available from URL: http://www.cacr.math.uwaterloo.ca/techreports/2001/coor2001-41.ps, 2001.
[26] C. D. Walter, “Exponentiation using Division Chains,” IEEE Transactions on Computers, vol. 47, No. 7, pp. 757-765, 1998.
[27] W. C. Yang, K. M. Lin, and C. S. Laih, “A precomputation method for elliptic curve point multiplication,” Journal of the Chinese Institute of Electrical Engineering, vol. 9, no. 4, pp. 339–344, 2002.
[28] W. C. Yang, P. Y. Hsieh, and C. S. Laih, “Efficient Squaring of Large Integers,” IEICE Transactions on Fundamentals, vol. E87-A, no. 5, pp. 1189-1192, 2004.
[29] W. C. Yang, D. J. Guan, and C. S. Laih, “Algorithm of Asynchronous Binary Signed-Digit Re-coding on Fast Multi-exponentiation,” Applied Mathematics and Computation, vol. 167, issue. 1, pp. 108-117, 2005.
[30] W. C. Yang, “The Study of Multi-computation in Public Key Cryptography,” Ph. D dissertation of National Cheng Kung University, 2005.
[31] W. C. Yang, D. J. Guan, and C. S. Laih, “Fast Multi-Computations with Asynchronous Strategy,” IEEE Transactions on Computers, vol. 56, no. 2, pp. 234–242, 2007.
[32] S. M. Yen, C. S. Laih, and A. K. Lenstra, “Multi-exponentiation,” IEE Proceedings, Computers and Digital Techniques, vol. 141, no. 6, pp. 325–326, 1994.
[33] W. C. Yang, C. P. Hung, and J. J. Wang, "On the performance of Dimitrov-Jullien-Miller recoding algorithm", 2010 International Computer Symposium (ICS 2010), pp. 210- 214, Dec. 2010.
[34] W. C. Yang and C. P. Hung, “Analysis of the Dimitrov-Jullien-Miller Recoding Algorithm,” IEICE Trans. on Fundamentals of Electronics, Communications and Computer Sciences, vol. E99-A. no. 1. pp. 139-144, Jan. 2016.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
無相關期刊
 
無相關點閱論文
 
系統版面圖檔 系統版面圖檔