跳到主要內容

臺灣博碩士論文加值系統

(44.222.64.76) 您好!臺灣時間:2024/06/14 04:30
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:楊吳泉
研究生(外文):Wu-Chuan Yang
論文名稱:公鑰密碼學多重運算之研究
論文名稱(外文):The Study of Multi-computation in Public Key Cryptography
指導教授:賴溪松賴溪松引用關係
指導教授(外文):Chi-Sung Laig
學位類別:博士
校院名稱:國立成功大學
系所名稱:電機工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:英文
論文頁數:108
中文關鍵詞:非同步策略聯合漢明加權帶號二進位表示法多指數運算多純量積運算整數重編碼公鑰密碼學多重運算
外文關鍵詞:asynchronous strategyinteger recoding strategyjoint Hamming weightmulti-scalar multiplicationbinary signed-digit representationPublic key cryptographymulti-exponentiationmulti-computation
相關次數:
  • 被引用被引用:0
  • 點閱點閱:310
  • 評分評分:
  • 下載下載:65
  • 收藏至我的研究室書目清單書目收藏:0
有限群之多重運算,包括有限乘法群之多指數運算,c = axby,及橢圓曲線有限加法群之多純數積運算,C = xA + yB (A, B, 及 C 表某一橢圓曲線上之點),都是使用於ElGamal類型密碼元件之重要運算。基於密碼元件之安全考量,參與這些運算的數值都非常大而使得這些運算十分耗時,因此有效率之演算法研究便有其必要性,本論文研究多重運算並提出一些效率良好之演算法與設計。
關於多重運算之基礎演算法,包括單一運算演算法與多指數運算觀念等,可容易在相關書籍及文獻論文中發現,這些演算法提供多重運算良好之運算基礎。進一步提升多重運算效率之演算法可概分為兩類:預先計算法及重新編碼法。前者多用於記憶體充足之環境,後者常見於記憶體受限之環境。
本論文著重於記憶體受限之環境。若 為(x,y)之聯合漢明距離(Joint Hamming distance)之平均值,亦即非零數字對個數之平均值,x、y為兩n-bit整數,則在 計算時,直接使用二進位表示法, =0.750n。 若改用帶號二進位之稀疏表示法(Sparse form, SF)時,可被改進為0.556n。因為帶號二進位表示法有多種形式,一些演算法變針對此特性來重新編碼以圖進一步改進效率,這類典型之演算法說明如下:
(1) 直接使用稀疏表示法[KN69]: 。
(2) 使用DJM法重新編碼 [DJM00]: 。
(3) 編碼成聯合稀疏表示法[SO01]: 當 時。
上述重新編碼法屬於同步方式,亦即編碼時同時處理x及y。本論文中,我們提出了一個非同步之重新編碼法,亦即先針對一個整數編碼再對另一個整數來編碼。在我們的程式模擬中,我們的方法可將 降為0.509n。雖然略遜於聯合稀疏表示法(Joint sparse form, JSF),但是非同步之特性較適用於二維以上之多重運算。
有別於重新編碼之策略,我們也提出一個全新之策略,稱為非同步策略,來改進多重運算。之前所提之演算法都是在計算時都將相同加權之數字同時處理。我們所提出之策略在計算過程中並不一定同時處理相同權位之數字,以利於將非0數字能夠盡量一起處理。這個方式可藉由將x或y之數字移位來達成。
在論文中,我們證明非同步策略可以有效改進所有重新編碼之效率,植基於帶號二進位表示法 (Binary signed-digit representation),我們提出兩個簡單有效之方法,分別稱之為SS1法及DS1法. 使用SS1法及DS1法於各式編碼法之效率,如下表所示。
Classical method SS1 method DS1 method
2 Sparse forms 0.556n 0.444n 0.407n
Recode by DJM 0.534n 0.453n 0.414n
Recode to JSF 0.500n 0.469n 0.438n
正因為非同步策略未做編碼之動作,因此也可用於單一編碼形式之二進位表示法我們也針對這部份提出相關演算法,其中最通用的為SUt法,其中t表示非同步數字最大加權差距之級數。其效能與空間之描述如下表。
演算法 SU0 SU1 SU2 … SUt

0.750n+1 0.667n+3 0.636n+5 …

memory 4 6 (5) 7 … t+5
此外,我們也針對多重運算之基礎運算之平方運算,提出改進與瑕疵(bug)修正之演算法,所提出來之演算法改進了典型平方運算演算法存在有”進位失控 (carry handling bug)瑕疵”,並進一步改進效率。在我們的分析中,我們所提來之演算法在Pentium系列之CPU,1024位元整數平方運算之效能為一般乘法運算之2.5倍。以平方使用次數為乘法之兩倍來評估,1024位元RSA系統中使用可以節省34.3%之效能。
為了有實現有效率之多重運算,我們在本論文中提出了全新之策略、演算法、以及設計。其中,依照非同步策略所設計之演算法,記憶體之需求為線性成長,不但效率良好且可適用於更多元之環境。
Multi-computations in finite groups, such as multi-exponentiations in finite multiplicative group (e.g. c=axby), and multi-scalar multiplications in finite additive grpup (e.g. C=xA+yB, where A, B, and C denote points in one elliptic curve), are very important but expensive in many ElGamal-like public key cryptosystems. In this dissertation, we study the multi-computations in public key cryptography and propose some efficient algorithms and implementations.
Fundamental algorithms for multi-computation can be found in many books and papers. The algorithms which further improve the performance of multi-computation can be classified by the following two conditions: pre-computing strategy and recoding strategy. Pre-computing type is usually applied in sufficient memory environment; however, the recoding type is used in limited memory environment.
In this dissertation, the study focuses on limited memory environment. Let be the expected value of the joint Hamming distance of x and y, that is the expected number of non-zero columns, where x and y are both n-bit integers. While is computed, is 0.750n by using binary representations. The value of can be improved to 0.556n by using two binary signed-digit (BSD) sparse forms. Because there are many minimal weight BSD representations for an integer, efficient recoding algorithm can be used to improve multi-computation. Classical recoding methods are shown as follows.

(1) Directly using two sparse forms [KN69]: .
(2) Using the DJM algorithm [DJM00]: .
(3) Using joint sparse form (JSF) [SO01]: , when .
These recoding algorithms, including the DJM algorithm and the JSF, all recode the integer pair simultaneously. We propose a new efficient asynchronous recoding algorithm. The asynchronous recoding means that we first recoding one integer, and then recoding the other integer. The joint Hamming distance is reduced to 0.509n in our recoding algorithm. Although the result is not better than JSF, the asynchronous property makes the proposed algorithm usable for multiple dimension multi-computations.
The study proposes the new strategy that is called the asynchronous strategy in the dissertation, to improve multi-computations with linear additional registers. Almost all existing algorithms compute the partial results by the same weight digit pair (xi,yi). The proposed strategy compute the partial results by different weight digit pairs, (xi,yj) with i¹j, such that the probability that xi and yj are both nonzero is increased. This can be done by shifting a block of digits in x and y.
The asynchronous strategy improves the performance of all the recoding forms. This study shows two efficient algorithms, the single signed-digit-integer one-stage algorithm (the SS1 method) and the double signed-digit-integer one-stage algorithm (the DS1 method) in BSD representations. By using SS1 and DS1 method, the values of joint hamming distance are illustrated in the following table.
Classical method SS1 method DS1 method
2 Sparse forms 0.556n 0.444n 0.407n
Recode by DJM 0.534n 0.453n 0.414n
Recode to JSF 0.500n 0.469n 0.438n
Because asynchronous strategy does not recode integer representations anymore, it can be used in binary representations, too. We also proposed efficient algorithms for binary representations. The most general one is called the single unsigned-digit-integer one-stage algorithm (the SUt algorithm), where t is maximal difference of digit weight. The performance and memory requirement are illustrated in the following table.
algorithm SU0 SU1 SU2 … SUt

0.750n+1 0.667n+3 0.636n+5 …

memory 4 6 (5) 7 … t+5
Besides, the study proposes an efficient squaring algorithm. The proposed algorithm fixes the improper carry handling bug in standard squaring algorithm and improves the performance in squaring computation. Our analysis indicates that the proposed squaring algorithm is about 2.5 times faster in comparison with the standard multiplication algorithm in Pentium series CPU. The performance of 1024-bit RSA cryptosystem can be saved 34.3% by using the proposed squaring algorithm to replace the standard multiplication, where the number of squares is double of the number of multiplications.
In order to achieve efficient multi-computation, this dissertation proposed new strategy, algorithms and implementations. The memory requirement is linearly increased in the algorithms based on asynchronous strategy. This property makes that these algorithms are efficient and flexible.
摘要 i
Abstract iv
誌謝 vii
Contents ix
LIST of Figures xi
LIST of Tables xiii
Chapter 1 Background 1
1.1 Public Key Cryptosystems 1
1.2 Basic Algorithms of Multi-computations 6
1.3 Synopsis 11
Chapter 2 Preliminaries 15
2.1 Basic Notations 15
2.2 Signed-Digit Representations 16
2.3 Strategies for Multi-computations 19
Chapter 3 Recoding Strategy 23
3.1 Directly using Two Sparse Form 23
3.2 Recoding by the DJM Algorithm 24
3.3 Recoding to JSF 25
3.4 Asynchronous Recoding Algorithm 26
3.5 Summary 33
Chapter 4 BSD Asynchronous Strategy 37
4.1 The Concept of Asynchronous Strategy 38
4.2 The Single Signed-digit-integer One-Stage (SS1) Algorithm 40
4.3 The Double Signed-digit-integer One-Stage (DS1) Algorithm 46
4.4 Summary 51
Chapter 5 Binary Asynchronous Strategy 55
5.1 The Single Unsigned-digit-integer One-Stage (SU1) Algorithm 55
5.2 The sliding-window SU1 (SU1w) Algorithm 58
5.3 The Single Unsigned-digit-integer t-Stage (SUt) Algorithm 60
5.4 Summary 64
Chapter 6 Implementation of Squaring 65
6.1. The importance of Squaring 65
6.2. The Classical Squaring Algorithm 67
6.3. The Guajardo-Paar Squaring Algorithm 68
6.4. The Proposed Squaring Algorithm 70
6.5. Summary 72
Chapter 7 Conclusion 79
Bibliography 83
Publication 90
簡 歷 91
Vita 92
[AN98a] American National Standards Institute, ANSI X9.31-1998: Public Key Cryptography Using Reversible Algorithms for the Financial Services Industry (rDSA), 1998.
[AN98b] American National Standards Institute, ANSI X9.62-1998-Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA), 1998.
[AV02] R. M. Avanzi, “On multi-exponentiation in cryptography,” IACR Cryptology ePrint Archive 2002/154, http://eprint.iacr.org, 2002.
[AV05] R. M. Avanzi, “The complexity of Certain multi-exponentiation Techniques in Cryptography,” Journal of Cryptology, vol. 18, pp. 357-373, 2005.
[AW93] 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.
[BC89] J. Bos and M. J. Coster, “Addition Chain Heuristics”, Advances in Cryptology - Crypto’89, LNCS 435, Springer-Verlag, pp. 400–407, 1989.
[BDK98] J. C. Bajard, L. S. Didier, and P. Komerup, “An RNS Montgomery modular multiplication algorithm.” IEEE Transaction on Computers, vol. 47, no. 7, pp. 766–776, Jul. 1998.
[BG92] 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.
[CMO98] 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.
[CO05] H. Cohen, “Analysis of the sliding window powering algorithm,” Journal of Cryptology, vol. 18, no. 1, pp. 63–76, 2005.
[DH76] W. Diffie and M.E. Hellman, “New Directions in Cryptography,” IEEE Trans. on Information Theory, vol. IT-22, ,pp.638–654, Nov. 1976.
[DJM00] 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, Feb. 2000.
[FIPS186] FIPS186-2, “Digital signature standard (DSS),” http://csrc.nist.gov/ publications/fips/, 2001
[EH03] N. Ebeid and A. Hasan, Analysis of DPA Countermeasures Based on Randomizing the Binary Algorithm, http://www.cacr.math.uwaterloo.ca/techreports/2003/ corr2003-14.ps, 2003.
[EL85] 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, Jul. 1985.
[GHP03] P. Grabner, C. Heuberger, and H. Prodinger, Distribution results for low-weight binary represenations for pairs of integers, Available from URL: http://finanz.math.tugraz.at/ prodinger/paperlst.htm, 2003.
[GMP04] The GNU MP 4.1.4 Manual, Available from URL: http://www.swox.com/ gmp/gmp-man-4.1.4.pdf, Sep. 2004.
[GO98] D. M. Gordon, “A survey of fast exponentiation methods,” Journal of Algorithms, vol. 27, pp. 129–146, 1998.
[GP92] J. Guajardo and C. Paar, “Modified Squaring Algorithm”, Available from URL: http://www.crypto.ruhr-uni-bochum.de/~guajardo/cv.html#pubs.
[IEEE1363] IEEE Working Group IEEE1363, “Standard Specifications for Public-key Cryptography,” Available from URL:http://grouper.ieee.org/groups/1363/.
[JM89] 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.
[JY00] 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.
[KN69] D. E. Knuth, The Art of Computer Programming, vol 2. Seminumerical algorithms, Addison-Wesley, 1969, 2nd edition 1982, 3rd edition 1998.
[KO63] A. Karatsuba and Y. Ofman, “Multiplication of multidigit numbers on automata,” Soviet Phys. Doklagy, vol. 7, no. 7, pp.595–596, 1963.
[KO94] C. K. Koc, “High-speed RSA implementations,” RSA Laboratories, Technique Notes TR201, Available from URL: http://www.rsasecurity.com/ rsalabs/, pp. 9–32, Nov. 1994.
[LK97] C. S. Laih and W. C. Kuo, “Speeding Up the Computations of Elliptic Curve Cryptoschemes,” International J. of Computers & Mathematics with Applications, vol. 33, no. 5, pp. 29-36, Mar. 1997.
[LL94] 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.
[MI04] P. K. Mishra, “Scalar multiplication in elliptic curve cryptosystems: Pipelining with pre-computations,” IACR Cryptology ePrint Archive 2004/191, http://eprint.iacr.org, 2004.
[MOL01] B. Moller, “Algorithms for multi-exponentiations," 8th Annual Workshop on Selected Areas in Cryptography -SAC 2001, LNCS 2259, Springer-Verlag, pp. 165–180, 2001.
[MON85] P. L. Montgomery, “Modular multiplication without trial division,” Mathematics of Computation, vol. 44, no. 170, pp. 519–521, Apr. 1985.
[MOV97] A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone, Handbook of Applied Cryptography, CRC Press, 1997.
[MS05] 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. Aug., 2005.
[OS03] K. Okeya and K. Sakurai, “Fast multi-scalar multiplication methods on elliptic curves with precomputation using montgomery trick,” 4th International Workshop on Cryptographic Hardware and Embedded Systems–CHES 2002, LNCS 2523, Springer-Verlag, pp. 564–578, 2003.
[OS04] K. Okeya, K. Schmidt-Samoa, C. Spahn, and T. Takagi, “Signed binary representations revisited,” IACR Cryptology ePrint Archive 2004/195, http://eprint.iacr.org, 2004.
[PKCS] Public-Key Cryptography Standards (PKCS), available from URL: http://www.rsasecurity.com/rsalabs/node.asp?id=2124
[PR03] J. Proos, “Joint Sparse Forms and Generating Zero Columns when Combing,” available from URL: http://www.cacr.math.uwaterloo.ca/ techreports/2003/ corr2003-23.ps, 2003.
[RE60] G. W. Reitwiesner, “Binary arithmetic,” Advance in computers, pp. 231–308, 1960.
[RK05] X. Ruan and 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.
[RSA78]R. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” Communication of ACM, vol. 21, pp. 120 126, 1978.
[SC96] B. Schneier, Applied Cryptography, 2nd edition, John Wiley & Sons, 1996.
[SC89] C. P. Schnorr, “Efficient identification and signatures for smart cards,” in Advances in Cryptology-Crypto’89, LNCS 435. Springer-Verlag, pp. 239–252, 1989.
[SEC] SECG SEC1,SEC2, Available from URL: http://www.secg.org.
[SO01] J. A. Solinas, “Low-weight Binary Representations for Pairs of Integers,” available fron URL: http://www.cacr.math.uwaterloo.ca/ techreports/ 2001/coor2001-41.ps, 2001.
[SYL99] H.M. Sun, W.C. Yang & C. S. Laih, “On the Design of RSA with Short Secret Exponent,” Advances in Cryptology–AsiaCrypt’99, LNCS 1716, Springer-Verlag, pp. 150 164, Nov. 1999.
[TO63]A. L. Toom, “The complexity of a scheme of functional elements realizing the multiplication of integers”, Soviet Math., vol. 3, pp.714-716, 1963.
[WA98] C. D. Walter, “Exponentiation using Division Chains,” IEEE Transactions on Computers, vol. 47, No. 7, pp. 757-765, July 1998.
[YG03] W. C. Yang, D. J. Guan, and C. S. Laih, “A New Binary Algorithm of 2-dimension Multi- exponentiation,” 2003 International Conference on Informatics, Cybernetics, and Systems (ICICS 2003), pp.391-395, Dec. 2003.
[YG05a] 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, Aug. 2005.
[YG05b] W. C. Yang, D. J. Guan, and C. S. Laih, “Fast multi-computations with integer similarity strategy,” in International Workshop on Practice and Theory in Public key Cryptography-PKC 2005, LNCS 3386. Springer-Verlag, pp. 139–153, Jan. 2005.
[YG05c] W. C. Yang, D. J. Guan, and C. S. Laih, " Fast Multi-Computations with Asynchronous Strategy," Submitted to IEEE Transactions on Computers in Aug. 2005.
[YH04] 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, May. 2004.
[YL94] 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.
[YL02] 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, Nov. 2002.
[ZU93] Dan Zuras, “On Squaring and Multiplying Large Integers,” 11th IEEE Symposium on Computer Arithmetic, pp 260-271, 1993.
[ZU94] Dan Zuras, “More On Squaring and Multiplying Large Integers”, IEEE Transactions on Computers, vol. 48, no. 3, pp. 899-908, 1994.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top