在現今的行動通訊中，個人的隱私與安全是使用者最關心的議題。密碼系統是保障機密與敏感性資料的一種重要技術，然而，主流的行動通訊設備製造商採用的處理器計算能力有限，以致於無法採用先進的安全技術。本論文將設計開發一些鑑別技術實現方法與有效率的鑑別技術。目前有許許多多的行動通訊安全協定是架構在RSA方法上，所以，我們首先設計一個架構於德州儀器公司的TMS320C55x系列數位訊號處理器的RSA實現方法，使得先進的安全協定可以運用於行動通訊設備上。然而，在許多的RSA應用中，常常選用較小的公開金鑰來縮短加密時間，解密部分依舊要耗費許多時間。為解決此一問題，我們提出一個利用強質數特性的RSA解密方法，此方法可以有效的提昇RSA的解密效率。最後，我們設計一個適用於行動通訊網路的鑑別機制。此機制植基於對稱式密碼系統、詢問-回覆與雜湊鍊節等密碼技術，而且提供了相互鑑別的特性。除此之外，本方法將產生使用者與服務供應商之間的通訊會談金鑰，以保護通訊內容，而且金鑰分配中心可利用金鑰轉換函數來避免使用者秘密金鑰的維護工作。

In mobile communications nowadays, personal privacy and security are of top concern to mobile phone subscribers.  In protecting the confidential and sensitive data in mobile networks, cryptosystem can be considered as an important technique.  Yet, mainstream mobile manufacturers can hardly adopt advanced security protocol to mobile devices, due to the limited computational ability of the processor they employ.  Against the backdrop that many good authentication protocols of mobile network are based on RSA operations, the author of this dissertation shall design and propose some implementation methods and authentication protocols.  First, the author designs an efficient and practical method to implement RSA algorithm originated from Texas Instruments TMS320C55x family, in order to make it possible to add an advanced security protocol to mobile networks.  The TMS320C55x family is widely adopted in many wireless and mobile devices.  While most of these RSA applications use a small public key to speed up the encryption operation, the decryption operation inevitably takes more computational time performing an operation of modular exponentiation.  To solve this problem, the author proposes a RSA decryption method based on the strong prime criterion.  The proposed method can greatly enhance the performance of the RSA decryption.  The author proposes some implementation methods of public key cryptosystem to enhance the performance; however, the public key cryptosystem is still slower than the symmetric key cryptosystem.  Finally, the author proposes a new efficient authentication protocol for mobile networks.  The proposed protocol is based on the symmetric cryptosystem, challenge-response, and hash chaining, in which the user, the service provider, and the key distribution center authenticate mutually.  In addition, the user and the service provider will generate a secret session key for their communication in this protocol.  With the key derivation function, the key distribution center of mobile networks does not need to maintain the secret key database of users.  The proposed protocol can be properly applied to the mobile networks.

CONTENTS

Abstract -i-
List of Figures -vi-
List of Tables -vii-
Chapter 1 Introduction -1-
1.1 Research motivation -1-
1.2 Objectives of the research -3-
1.3 Organization -4-
Chapter 2 Cryptanalysis on stream ciphers for GSM networks -6-
2.1 Lo and Chens'stream cipher architecture -6-
2.1.1 Key generator (KG) -7-
2.1.2 Stream ciphers -8-
2.1.2.1 Stream cipher 1 (S1) -8-
2.1.2.2 Stream cipher 2 (S2) -9-
2.1.2.3 Stream cipher 3 (S3) -10-
2.2 Cryptanalysis on Lo and Chen's key generator -11-
2.2.1 First cryptanalysis -12-
2.2.2 Second cryptanalysis -13-
2.3 Cryptanalysis on Lo and Chen's stream cipher -15-
2.3.1 Cryptanalysis on stream cipher 1 (S1) -15-
2.3.2 Cryptanalysis on stream cipher 2 (S2) -15-
2.3.3 Cryptanalysis on stream cipher 3 (S3) -16-
Chapter 3 Fast firmware implementation of RSA for mobile devices -17-
3.1 RSA algorithm -18-
3.2 TI TMS320C55x family of DSP -18-
3.3 Implementation -19-
3.3.1 Multiplication -20-
3.3.2 Modular reduction -22-
3.3.3 RSA implementation (Modular exponentiation)-23-
3.3.4 Decryption based on CRT -25-
3.4 Experiment results -27-
3.5 Discussion -30-
Chapter 4 An efficient RSA decryption method based on strong prime criterion -32-
4.1 Strong prime -33-
4.2 An efficient RSA decryption method -34-
4.3 Computational complexity -43-
Chapter 5 An efficient authentication protocol for mobile networks -48-
5.1 Related works -49-
5.2 Intra-domain authentication protocol -50-
5.2.1 The initial phase -51-
5.2.2 The subsequent phase -55-
5.3 Inter-domain authentication protocol -56-
5.3.1 The initial phase -57-
5.3.2 The subsequent phase -61-
5.4 Security analysis -63-
5.4.1 Authentication proof based on BAN logic -63-
5.4.2 Withstanding possible attacks-66-
5.5 Discussions -68-
Chapter 6 Conclusions and future researches -73-
6.1 Summary of contributions -73-
6.2 Future researches -76-
References -78-

List of Figures
Figure 2.1  The security architecture of GSM -7-
Figure 2.2  The stream cipher S1 -9-
Figure 2.3  The stream cipher S2……………………………………………………….9
Figure 2.4  The stream cipher S3……………………………………………………...10
Figure 3.1  Our enhanced multiplication algorithm on TMS320C55x………………..21
Figure 3.2  Barrett reduction algorithm……………………………………………….22
Figure 3.3  Modular exponentiation algorithm………………………………………..23
Figure 3.4  Times of multiplication operations for different k in our modular exponentiation method…………………………………………………...25
Figure 4.1  The structure of RSA parameter n…………………….…………………..33
Figure 4.2  The diagram of the proposed RSA decryption method…………………...37
Figure 5.1  The initial phase of intra-domain protocol……………...………………...54
Figure 5.2  The subsequent phase of intra-domain protocol………………………….55
Figure 5.3  The initial phase of inter-domain protocol……………………………......61
Figure 5.4  The subsequent phase of inter-domain protocol………………………….62

List of Tables
Table 3.1  Numbers of CPU cycles and lengths of time taken to realize RSA ..……...28
Table 3.2  Numbers of CPU cycles and lengths of time taken by modular exponentiations with exponent e being a 160-bit string…….……………...28
Table 3.3  Numbers of CPU cycles in the realization of RSA ….…………………….29
Table 3.4  Lengths of CPU time taken to realize the RSA decryption process……….30
Table 4.1  Numbers of CPU clock cycles for realizing the RSA decryptions based on three different methods…….……………………………………………….45
Table 4.2  Numbers of CPU clock cycles for realizing the modular multiplication…..46
Table 5.1  Summaries of comparisons………………………………………………...70
Table 5.2  The comparisons of the computational and communicational cost of initial authentication phase……………………………………………………......71
Table 5.3  The comparisons of the computational and communicational cost of subsequent phase…………………………………………………………...72
Table 5.4  The summaries of the computation speed of cryptographic functions…….72

[1]ANSI Standard X9.31, Digital Signatures Using Reversible Public Key Cryptography for the Financial Services Industry (rDSA), 1998.
[2]Asha Mehrotra and Leonard S. Golding, “Mobility and Security Management in the GSM System and Some Proposed Future Improvements,” Proc. IEEE, Vol. 86, No. 7, 1998, pp.1480-1497.
[3]A. Cilardo, A. Mazzeo, L. Romano, and G. P. Saggese, “Exploring the design-space for FPGA-based implementation of RSA,” Microprocessors and Microsystems, Vol. 28, 2004, pp. 183-191.
[4]A. Hayashi, “A new fast modular multiplication method and its application to modular exponentiation-based cryptography,” Electronics and Communications in Japan, Vol. 83, No. 12, 2000, pp. 88-93.
[5]B. Schneier, Applied Cryptography: protocols, algorithms, and source code in C, 2nd ed. John Wiley & Sons, Inc. 1996.
[6]Chi-Chun Lo and Yu-Jen Chen, “Stream ciphers for GSM networks,” Computer Communications, 24, 2001, pp.1090-1096.
[7]C. Ding, G. Xiao and W. Shan, The Stability Theory of Stream Ciphers, Springer-Verlag, 1991.
[8]C. G. Günther, “Alternating Step Generators Controlled by de Bruijn Sequences,” Proc. EUROCRYPT’87, 1998, pp.5-14.
[9]C. K. Koc, “Analysis Of Sliding Window Techniques for Exponentiation,” Computers and Mathematics with Applications, Vol. 30, No. 10, 1995, pp. 17-24.
[10]C. Perkins, IP mobility support, Internet Request for Comments 2002, 1996.
[11]C.-S. Lai, W.-C. Yang, and C.-H. Chen, “Efficient method for generating strong primes with constraint of bit length,” Electronics Letters, Vol. 27, No. 20, 1991, pp. 1807-1808.
[12]Dan Boneh and Hovav Shacham, “Fast Variants of RSA,” Cryptobytes, Vol. 5, No. 1, 2002, pp. 1-9.
[13]Davida GI, Wells DL, and Kam JB, “A database encryption system with subkeys,” ACM Trans. Database Systems, Vol. 6, 1981, pp. 312-328.
[14]D. E. Knuth, Seminumerical Algorithms, Volume 2 of The Art of Computer Programming, 3rd edition, Addison-Wesley, Reading, MA, USA, 1997.
[15]G. Dorðević, T. Unkašević, and M. Markocić, “Optimization of modular reduction procedure in RSA algorithm implementation on assembler of TMS320C54x signal processors,” Proc. of the IEEE 14th International Conference on Digital Signal Processing, 2002, pp. 811-814.
[16]G. P. Saggese, L. Romano, N. Mazzocca, and A. Mazzeo, “A tamper resistant hardware accelerator for RSA cryptographic applications,” Journal of Systems Architecture, Vol. 50, 2004, pp. 711-727.
[17]H. Y. Chien and J. K. Jan, “A hybrid authentication protocol for large mobile network,” The Journal of Systems and Software, Vol. 67, 2003, pp. 123-130.
[18]H.-Y. Lin, “Security and Authentication in PCS,” Computers and Electrical Engineering, Vol. 25, 1999, pp. 225-248.
[19]IEEE Standard 802.11, Wireless LAN medium access control (MAC) and physical layer (PHY) specifications, IEEE Draft Standard, 1996.
[20]Jovan Dj. Golic and Renato Menicocci, “Edit Distance Correlation Attack on the Alternating Step Generator,” Proc. CRYPT′97, 1997, pp.499-512.
[21]Jörg Eberspächer and Hans-Jörg Vögel, GSM Switching, Services and Protocols, John Wiley & Sons, 1998.
[22]J.-J. Quisquater, and C. Couvreur, “Fast decipherment algorithm for RSA public-key cryptosystem,” Electronics Letters, Vol. 18, No. 21, 1982, pp. 905-907.
[23]J. Gordon, “Strong RSA keys,” Electronics Letters, Vol. 20, No. 12, 1984, pp. 514-516.
[24]J. Grobschädl, “High-Speed RSA Hardware Based on Barret’s Modular Reduction Method,” CHES 2000, LNCS 1965, 2000, pp. 191-203.
[25]J. Grobschädl, “The Chinese Remainder Theorem and its Application in a High-Speed RSA Crypto Chip,” Proceedings of the IEEE 16th Annual Computer Security Applications Conference, 2000, pp. 384-393.
[26]J. G. Steiner, B. C. Neuman, and J. I. Schiller, “Kerberos: an authentication service for open network systems,” Proceedings of the Winter 1988 Usenix Conference, 1988, pp. 191-201.
[27]J. Kohl and C. Neuman, The Kerberos network authentication service (V5), Internet Request for Comments 1510, 1993.
[28]J. Pollard, “Monte Carlo method for factorization,” BIT, 15, 1975, pp.331-334.
[29]L. Batina, S. B. Ors, B. Preneel, and J. Vandewalle, “Hardware architectures for public key cryptography, Integration,” VLSI Journal, Vol. 34, 2003, pp. 1-64.
[30]M. Burrows, M. Abadi, and R. Needham, “A logic of authentication,” ACM Trans. Computer Systems, Vol. 8, No. 1, 1990, pp. 18-36.
[31]M. J. Ganley, “Note on the generation of P0 for RSA keysets,” Electronics Letters, Vol. 26, No. 6, 1990, pp. 369.
[32]M. Ogiwara, “A method for generating cryptographically strong primes,” IEICE Trans. Fundamentals, E73, Vol. 6, 1990, pp. 985-994.
[33]M. Shand and J. Vuillemin, “Fast Implementation of RSA Cryptography,” Proceedings of 11th Symposion on Computer Arithmetic, 1993, pp. 252-259.
[34]M. S. Hwang, “Dynamic participation in a secure conference scheme for mobile communications,” IEEE Trans. Vehicular Technology, Vol. 48, No. 5, 1990, pp. 1469-1474.
[35]M. S. Hwang, I. C. Lin, and L. H. Li, “A simple micro-payment scheme,” The Journal of Systems and Software, Vol. 55, 2001, pp. 221-229.
[36]N. Koblitz, A course in Number Theory and Cryptology, 2nd Edition, Graduate Text in Mathematics, Vol.114, Springer, Berlin, Germany, 1994.
[37]P. Barrett, “Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor,” Advances in Cryptology-CRYPTO’86, Lecture Notes in Computer Science, Springer Verlag, 1987, pp. 311-323.
[38]P. C. Kocher, J. Jaffe, and B. Jun., “Differential Power Analysis,” Advances in Cryptology-CRYPTO’99, Lecture Notes in Computer Science, Springer Verlag, 1999, pp. 388-397.
[39]P. Syverson and I. Cervesato, “The logic of authentication protocols,” Springer-Verlag, LNCS 2171, 2001, pp. 63-137.
[40]Qiang Tang and Chris J. Mitchell, “Cryptanalysis of a hybrid authentication protocol for large mobile networks,” The Journal of Systems and Software, In Press, Corrected Proof, Available online 1 June 2005.
[41]RSA Laboratories, PKCS#1: RSA Cryptography, Version 2.1, 2002.
[42]R. D. Díaz and J. M. Masqué, “Optimal strong primes,” Information processing Letters, Vol. 93, 2005, pp. 47-52.
[43]R. Rivest, A. Shamir, and L. Adleman, “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems,” Communication of the ACM, Vol. 21, No. 2, 1978, pp. 120-126.
[44]S. H. Park, A. Ganz, and Z. Ganz, “Secruity protocol for IEEE 802.11 wireless local area network,” Mobile Networks and Applications, Vol. 3, 1998, pp. 237-246.
[45]S. M. Bellovin and M. Merritt, “Limitations of the Kerberos authentication system,” ACM Communications Review, Vol. 20, No. 5, 1990, pp. 119-132.
[46]S. P. Shieh, F. S. Ho, and Y. L. Huang, “An efficient authentication protocol for mobile networks,” Journal of Information Science and Engineering, Vol. 15 1999, pp. 505-520.
[47]S. Ravi and A. Raghunathan, “Security in Embedded Systems: Design Challenges,” ACM Transaction on Embedded Computing Systems, Vol. 3, No. 3, 2004, pp. 461-491.
[48]S. Suzuki and K. Nakada, “An Authentication Technique Based on Distributed Security Management for the Global Mobility Network,” IEEE Journal on Selected Areas in Communications, Vol. 15, No. 8, 1997, pp. 1608-1617.
[49]Texas Instruments (2003, 8, 6), OMAP TM processors for wireless devices, [Online]. Available: http://focus.ti.com/graphics/omap/omap_020603.pdf.
[50]Texas Instruments, TMS320C55x DSP Programmer’s Guide, Product Bulletin, SPRU376.
[51]T. Unkasevie, M. Markovic, and G. Dordevic, “Optimization of RSA Algorithm Implementation on TI TMS320C54x Signal Processors,” Proceedings of the 5th International Conference on Telecommunication in Modern Satellite, Cable and Broadcasting Service, 2001, pp. 603-606.