(3.235.139.152) 您好！臺灣時間：2021/05/11 12:56

### 詳目顯示:::

:

• 被引用: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) ------------------------------------ iAbstract (in English) ----------------------------------- iiAcknowledgments ---------------------------------------- iiiContents ------------------------------------------------ ivList of Figures ----------------------------------------- viList of Tables ----------------------------------------- viiChapter 1 Introducton ------------------------------------ 1Chapter 2 Preliminaries ---------------------------------- 42.1 Review of the DJM Method ------------------------------52.2 Review of the SS1 method ------------------------------62.3 CLNW for Scalar Computation xA -----------------------12Chapter 3 The DJM-type Methods ---------------------------133.1 Preparation of Proving the DJM Algorithm -------------133.2 Analysis of the DJM-O Method -------------------------153.3 Analysis of the DJM-R and DJM-L Methods --------------17Chapter 4 Algorithms with 4-bit Reduction Rules ----------224.1 The DJM-4O Algorithm ---------------------------------224.2 Preparation of Proving the DJM-4O Algorithm ----------244.3 Analysis of the DJM-4O Method ------------------------264.4 Analysis of the DJM-4R and DJM-4L Methods ------------28Chapter 5 Asynchronous Algorithms with NAF ---------------335.1 SS2 --------------------------------------------------335.2 SS3 --------------------------------------------------385.3 SS4 --------------------------------------------------405.4 SS5 --------------------------------------------------43Chapter 6 Constant Nonzero Sliding Window Methods --------476.1 CNSW2 ------------------------------------------------476.2 CNSW3 ------------------------------------------------51Chapter 7 Conclusion -------------------------------------56Conferences ----------------------------------------------57Publication ----------------------------------------------61Vita -----------------------------------------------------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.
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 無相關期刊

 無相關點閱論文

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室