ENHANCING SECURITY FOR MOBILE AD HOC NETWORKS BY USING ELLIPTIC CURVE CRYPTOGRAPHY Rubaiyat Islam Rafat [MIT-806] Md. Majharul Haque [MIT-815] Institute of Information Technology APPROVED: Dr. Kazi Sakib, Assistant Professor Shafiul Alam Khan, Lecturer Dr. Zerina Begum, Professor Course Coordinator c Copyright by Rubaiyat Islam Rafat and Md. Majharul Haque 2009 to our MOTHER and FATHER with love ENHANCING SECURITY FOR MOBILE AD HOC NETWORKS BY USING ELLIPTIC CURVE CRYPTOGRAPHY by Rubaiyat Islam Rafat [MIT-806] Md. Majharul Haque [MIT-815] THESIS Presented to the Faculty of Institute of Information Technology The University of Dhaka in Partial Fulfillment of the Requirements for the Degree of MASTER OF INFORMATION TECHNOLOGY Institute of Information Technology UNIVERSITY OF DHAKA 17th October 2009 Declaration The work in this thesis is based on research carried out at Institute of Information Technology, University of Dhaka, Bangladesh. No part of this thesis has been submitted elsewhere for any other degree or qualification and it all our own works unless referenced to the contrary in the text. Rubaiyat Islam Rafat Md. Majharul Haque Copyright c 2009 by Rubaiyat Islam Rafat and Md. Majharul Haque. “The copyright of this thesis rests with the author(s). No quotations from it should be published without the authors’ prior written consent and information derived from it should be acknowledged”. v Acknowledgements This research work would not have been completed without help and support of many individuals. We would like to thank everyone who has helped us along the way. Particularly: Dr. Kazi Muheymin Sakib for providing us an opportunity to conduct our masters research under him and for his guidance and support over the course of it. His attention, guidance, insight, and support during this research and the preparation of this thesis improves the quality of this research work. We specially thank him for his infinite patience to this thesis. We are also grateful to Md. Shafiul Alam Khan for serving on our thesis committee, and valuable suggestions. Md. Hiron Miah for his invaluable help to understand Complex Cryptography Mathematics. Our present and past classmates at IIT for all the memorable times. Finally, our family without whose support none of this would have been possible. vi Abstract Unlike conventional infrastructure based wireless networks such as, wireless cellular networks, Mobile Ad Hoc Networks (MANET) contain rapidly deployable, self organizing and self maintaining capability features. Moreover, they can be formed on the fly as needed. More concerns for MANET’s security arise due to its high popularity to its users. Now-adays, more interests are given in Public Key Cryptography (PKC) rather than Secret Key Cryptography because of its strong security. However, in the context of wireless communication, although PKC offers robust solutions for many security problems, the excessive amount of required computational resources remarkably limit the usage of PKC. Using Elliptic Curve Cryptography (ECC) offers higher strength per key bit in comparison with other PKCs. The computational power needed to break 1024 bit RSA is equal to the computational power needed to break 163 bit ECC. Unlike the ordinary Discrete Logarithm Problem (DLP) and the Integer Factorization Problem (IFP) for PKCs, no subexponential-time algorithm is known for the Elliptic Curve Discrete Logarithm Problem (ECDLP). For this reason, the strength-per-key-bit is substantially greater in an algorithm that uses elliptic curves rather than existing RSA or El-Gamal PKC. This thesis paper gives an introduction to ECC, how it is used in the implementation of Digital Signature Algorithms (ECDSA) and provides a novel security framework based on ECC and ECDSA for MANET. In the proposed framework, namely Optimized Pretty Good Privacy (OPGP), a composition of ECC and ECDSA is introduced for enhancing security. In OPGP, the authentication, non repudiation, integrity of information is provided by ECDSA and confidentiality is provided by using ECC. The optimized ECC and ECDSA succeed to provide same security level of existing RSA, by performing relatively lower computations. vii Table of Contents Page Declaration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii Table of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii Chapter 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Security and Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Research Scope . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.4 Thesis Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Background and Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1 Security for Mobile Ad Hoc Networks . . . . . . . . . . . . . . . . . . . . . 5 2.2 Confidentiality Issue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2.1 Secure Group Communication . . . . . . . . . . . . . . . . . . . . . 7 2.2.2 Secret Sharing Scheme . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.3 Key Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Key Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Key Exchange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 Key Storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Key Usage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Authentication Issue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3.1 15 2.3 Key Agreement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii 2.3.2 Identity Based Cryptography . . . . . . . . . . . . . . . . . . . . . 16 2.3.3 Sybil Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.3.4 Location Based Authentication . . . . . . . . . . . . . . . . . . . . 19 Digital Signature Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.4.1 DSA Operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.4.2 Domain Parameter Generation . . . . . . . . . . . . . . . . . . . . . 22 2.4.3 DSA Key Pair Generation . . . . . . . . . . . . . . . . . . . . . . . 23 2.4.4 DSA Signature Generation . . . . . . . . . . . . . . . . . . . . . . . 23 2.4.5 DSA Signature Verification . . . . . . . . . . . . . . . . . . . . . . . 23 2.5 Certificate Authority . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3 Public Key Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.4 3.1 3.2 Essential Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.1.1 Integers in PKC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.1.2 Groups in PKC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.1.3 Rings in PKC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.1.4 Mappings in PKC . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.1.5 Fields in PKC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.1.6 Vector Spaces and Coordinate Geometry in PKC . . . . . . . . . . 34 3.1.7 Polynomial Rings in PKC . . . . . . . . . . . . . . . . . . . . . . . 35 3.1.8 Finite Fields in PKC . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.1.9 Projective Coordinates in PKC . . . . . . . . . . . . . . . . . . . . 38 Cryptosystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 Private-key Cryptosystems . . . . . . . . . . . . . . . . . . . . . . . 39 Public-key Cryptosystems . . . . . . . . . . . . . . . . . . . . . . . 40 3.2.1 Discrete Logarithm Problem . . . . . . . . . . . . . . . . . . . . . . 41 3.2.2 El Gamal Cryptosystem . . . . . . . . . . . . . . . . . . . . . . . . 41 3.2.3 Integer Factoring Problem . . . . . . . . . . . . . . . . . . . . . . . 42 ix 3.2.4 RSA Cryptosystem . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 Elliptic Curve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 [Characteristic 6= 2, 3] . . . . . . . . . . . . . . . . . . . . . . . . . 44 [Characteristic 2] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Point at Infinity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 3.3.1 Addition Operation of Elliptic Curve . . . . . . . . . . . . . . . . . 44 3.3.2 Elliptic Curve Discrete Logarithm Problem . . . . . . . . . . . . . . 47 3.4 Elliptic Curve Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.5 Impact of Key Size in PKI Security . . . . . . . . . . . . . . . . . . . . . . 48 3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4 Proposed Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.3 4.1 Pretty Good Privacy Framework . . . . . . . . . . . . . . . . . . . . . . . . 51 4.2 Optimized Pretty Good Privacy Framework . . . . . . . . . . . . . . . . . 53 4.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 5 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 5.1 5.2 Simulation Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 5.1.1 NS-2 Simulator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 5.1.2 Simulation Topography . . . . . . . . . . . . . . . . . . . . . . . . . 58 5.1.3 Queue Management . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 5.1.4 Routing Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 5.1.5 Mobility Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5.1.6 Transport Agent . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 5.1.7 Traffic Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 5.1.8 Performance Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . 60 Simulation Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 5.2.1 Average Throughput Analysis . . . . . . . . . . . . . . . . . . . . . 61 5.2.2 Average Delay Time Analysis . . . . . . . . . . . . . . . . . . . . . 61 5.2.3 Average Jitter Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 62 x 5.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 6.1 Problem Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 6.2 Result Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 6.3 Future Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 xi List of Tables 2.1 Key Size Comparison (in bits) for Equivalent Security Levels . . . . . . . . 14 3.1 Key Size Equivalent Operations Comparison for Equivalent Security Levels 48 3.2 RAM Required for NFS Operation . . . . . . . . . . . . . . . . . . . . . . 49 3.3 MIPS years to solve a generic ECDLP using the parallel Pollard Method . 49 xii List of Figures 2.1 Mobile Ad Hoc Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Secure Communication by Using Symmetric Key Cryptography . . . . . . 8 2.3 Blakley’s Secret Sharing Scheme . . . . . . . . . . . . . . . . . . . . . . . . 9 2.4 Man in The Middle Attack . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.5 Key Management Load Comparison . . . . . . . . . . . . . . . . . . . . . . 13 2.6 Nodes can Spoof MAC address or cause ARP Cache Poisoning . . . . . . . 21 2.7 Public and Private Key Generation of Certificate Authority . . . . . . . . . 25 3.1 Operations in Cryptosystem . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.2 Use of Symmetric Key Cryptography for Only Confidentiality . . . . . . . 39 3.3 Use of Asymmetric Key Cryptography for Confidentiality . . . . . . . . . . 40 3.4 Use of Asymmetric Key Cryptography for Authentication . . . . . . . . . . 40 3.5 3-D Elliptic Curve for Equation y 2 = x3 –x . . . . . . . . . . . . . . . . . . 43 3.6 3-D Region of Elliptic Curve for Equation y 2 = x3 –x . . . . . . . . . . . . 45 3.7 3-D Region of Elliptic Curve for Equation y 2 = x3 –x For Addition Operation 46 3.8 Elliptic Curve Addition Operation . . . . . . . . . . . . . . . . . . . . . . . 47 4.1 PGP Encryption Operation . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.2 Computational Complexity Analysis for ECDLP and DLP/IFP . . . . . . 54 4.3 OPGP Encryption Operation . . . . . . . . . . . . . . . . . . . . . . . . . 55 5.1 Average Throughput Analysis for ECC-163 and RSA-1024 bit . . . . . . . 62 5.2 Average Delay Time Analysis for ECC-163 and RSA-1024 bit . . . . . . . 63 5.3 Average Jitter Analysis for ECC-163 and RSA-1024 bit . . . . . . . . . . . 64 xiii Chapter 1 Introduction MANET is a special type of wireless network consisting of a collection of nodes capable to communicate with each other without help from a network infrastructure. Applications of MANETs include the battlefield applications, rescue works, as well as civilian applications like an outdoor meeting, or an ad hoc classroom. With the increasing number of applications to harness the advantages of Ad Hoc Networks, more concerns arise for security issues in MANETs. 1.1 Security and Cryptography Cryptography helps transmitting sensitive information across insecure networks. The strength of cryptography does not depend on the network size. For example, in a large distributed network like MANET, it cannot be read by anyone except the intended recipient. Cryptography is the science of using mathematics to encrypt and decrypt messages. In cryptographic terminology, the original, undisguised message is called plaintext or cleartext. Encoding the contents of the message in such a way that it hides its contents from outsiders is called encryption. The encrypted message is called ciphertext. The process of retrieving the plaintext from the ciphertext is called decryption. Modern cryptography, as applied in the commercial world, is concerned with a number of factors. The most important of these are: • Confidentiality, which is the process of keeping information private and secret so that only the intended recipient is able to understand it. 1 • Authentication, which is the process of providing proof of identity of the sender to the recipient, so that the recipient can be assured that the person sending the information is who or what he or she claims to be. • Integrity, which is the method to ensure that information is not tampered with during its transit or its storage on the network. • Non-repudiation, which is the method to ensure that information cannot be disowned. Once the non-repudiation process is in place, the sender cannot deny being the originator of the information. A system is considered secure system, if all of the above-mentioned factors are fulfilled by the cryptography algorithm. It is a big challenge for security researchers to introduce all the required features of cryptography within one algorithm. Moreover, the computational complexity optimization of the cryptography algorithms is also a prime concern for developing a secure cryptosystem. 1.2 Problem Statement The nature of ad hoc networks has thrown a big challenge to system security designers due to the following reasons: • The wireless network is more susceptible to attack ranging from passive eavesdropping to active interfering. • The lack of an online Certificate Authority (CA) or Trusted Third Party (TTP) adds the difficulty to deploy security mechanisms. • Mobile devices tend to have limited power consumption and computation capabilities. This makes it more vulnerable to Denial of Service (DoS) attacks and incapable to execute computation-heavy algorithms like public key algorithms. 2 • In MANETs, there are more probabilities for trusted node(s) being compromised and then being used by adversary to launch attacks on networks. In another word, we need to consider both insider attacks and outsider attacks in mobile ad hoc networks, in which insider attacks are more difficult to deal with. • Node’s mobility enforces frequent networking reconfiguration which creates more chances for attacks. For example, it is difficult to distinguish between stale routing information and faked routing information. 1.3 Research Scope Considering the characteristics of MANET, introducing a robust security framework for MANET is challenging. Security designers should more emphasize developing a hybrid framework rather than an individual cryptography scheme for providing robust security. For developing a hybrid framework, application layer oriented development should be easier and flexible for security designers than network layer. The core components for designing such a framework should consists of strong and optimized cryptography algorithm for ensuring authentication and confidentiality. Moreover, a fast and reliable hashing algorithm for ensuring data integrity should be included in the framework. Finally, additional components that can reduce consumption of resources in the network should be introduced. This research proposes such a hybrid framework that ensures authentication, confidentiality, integrity, non-repudiation and additional component data compression for the limited resource constraint MANET. 1.4 Thesis Structure The rest of the thesis is structured as follows: • Chapter 2 provides background information and previous research activities related to this research. Basic concepts of MANET, features of security along with different 3 secure communication techniques and different attacks on MANET are also discussed in this chapter. • One of the most popular and secure cryptosystem is PKC. Chapter 3 provides brief description over PKC and different methods of PKC. The underlying mathematics for cryptographic strength of different techniques are also discussed in this chapter. • Chapter 4 elaborately describes the existing security scheme and find out it’s major drawbacks. Moreover, a novel framework is proposed in this chapter that overcomes those drawbacks of existing solution. • The detail description of the performance analysis with simulation environment is provided in Chapter 5. In this chapter, result analysis is provided based on three performance metrics among the existing solution and the proposed solution. • Finally, this thesis concludes in Chapter 6 where the aim and achievements of this research are summarized and possible directions for future research are discussed. 4 Chapter 2 Background and Related Work Security is an important issue for wireless networks. In this chapter, a brief description of background knowledge and previous research work on Wireless Ad hoc Network Security has been provided. This chapter will help to understand different security aspects of wireless networks. Moreover, the related work on this arena will give a paradigm of challenges and scopes of wireless security. At the beginning, security for MANET has been discussed. The four major issues regarding security, Confidentiality, Authentication, Integrity and Non Repudiation are discussed. Later, Confidentiality issue ensures that the data transmitted through communication medium should not be eavesdropped. Authentication issue concerns with the access of information by only legitimate users in the network. Integrity issue ensures that the transmitted message has not been tampered by any intruders. Finally, Non Repudiation ensures that neither the sender nor the receiver can deny the transmission or acceptance of the information. 2.1 Security for Mobile Ad Hoc Networks As the popularity of ad hoc networks increase so does the need for improvement of their security. Solutions are required to prevent adversaries attempting to jeopardise the network operation. The Latin term Ad Hoc means For the Specific Purpose. Ad Hoc networks are instantly formed to serve a specific purpose and cease to exist after the network fulfills its purpose. MANET is a self-configuring network connected by wireless links. Most Ad Hoc networks do not rely on any underlying fixed infrastructure such as base stations or access points. Instead, mobile hosts (or nodes) rely on each other to keep the network connected 5 [Figure: 2.1]. Each device in MANET is free to move independently in any direction, and will therefore change its links to other devices frequently. Each node must forward traffic to make the network consistent. Therefore, every node in MANET are treated as a router. So, the construction of a suitable, secure framework for ad hoc networks is difficult to achieve [22]. This has been an area of very active and challenging research in recent years. The nodes of an ad hoc network are generally small, low energy, limited computational power, portable devices with a finite power source. These characteristics should be taken into consideration when choosing cryptography algorithms for Ad Hoc network security. Figure 2.1: Mobile Ad Hoc Networks Donald Welch et al. in their paper summarized different wireless security threats and their counter measures cryptographic techniques [1]. The researchers classified the threats based on different security issues. The classified three attacks that violates confidentiality or privacy of the session are traffic analysis, passive eavesdropping, and active eavesdropping. 6 The man-in-the-middle attack violates both confidentiality and integrity. The rest three attacks violate integrity of the network traffic namely, unauthorized access, session hijacking and the replay attack. For the countermeasures, the researchers suggests to choose an integrated secure framework consists of proper authentication mechanism and a strong and secure encryption algorithm using block cipher. 2.2 Confidentiality Issue The Confidentiality issue of Security focuses on avoiding Eavesdropping. Eavesdropping is the act of secretly listening to the private conversation of others without their consent. The communication of wireless networks takes place through the air using radio frequencies. So, the risk of interception in a wireless network is greater than that of a wired network. If the message is not encrypted or encrypted with a weak cryptography algorithm, the attacker can read it and confidentiality of the communication can be violated. Thereby, confidentiality is a vital issue for securing wireless networks. The topics regarding to confidentiality issue are discussed below. 2.2.1 Secure Group Communication Secure group communication (SGC) is a process by which members in a group can securely communicate with each other and the information is not eavesdropped by anybody outside the group [3]. In SGC, a group key is established among all the participating members and this key is used to encrypt all the messages destined to the group. A good SGC protocol should efficiently manage the group key when members join and leave. The efficiency of SGC in terms of security is an important issue in ad hoc networks where the members are highly mobile and the network topology is dynamic. 7 Figure 2.2: Secure Communication by Using Symmetric Key Cryptography 2.2.2 Secret Sharing Scheme Secret sharing refers to method for distributing a secret (e.g. splitting and distributing any secret key) among a group of participants, each of which, is allocated a share of the secret. The secret can be reconstructed only when a sufficient number of shares are combined together; individual shares are of no use on their own. More formally, in a secret sharing scheme there is one dealer and n players. The dealer gives a secret to the players, but only when specific conditions are fulfilled. The dealer accomplishes this by giving each player a share in such a way that any group of t (a threshold for example) or more players can together reconstruct the secret, but no group of fewer than t players can. Such a system is called a (t, n) - threshold scheme. For a n dimensional space, where n shares of a secret remains, each share is not enough to disclose the hidden secret. Even (n − 1) shares cannot disclose the secret. From Figure: 2.3, only the three portions of the secret can disclose the secret and that is the intersecting point of three individuals shares. Even two shares cannot discover the intersecting point. Some well-known Secret Sharing Schemes (SSS) are Shamir SSS [4] based on polynomial interpolation, Blakley SSS [5] based on hyperplane geometry, and Asmuth-Bloom SSS [6] based on the Chinese Remainder Theorem (CRT). A t-out-of-n secret sharing scheme contains two phases. In the dealer phase, the dealer shares a secret among n users. In the combiner phase, a coalition of size greater than or equal to t constructs the secret. There are some limitations of SSS such as, each share of the secret must be at least as large as the secret itself. For example, given (t − 1) shares, no information can be determined about the secret. Thus, the final share must contain as much information as the secret itself. Another flaw of SSS is usage of random bits. To 8 Figure 2.3: Blakley’s Secret Sharing Scheme distribute a one-bit secret among threshold t people, (t − 1) random bits are necessary. So, to distribute a secret of arbitrary length entropy of (t − 1) × length is necessary. Kamer Kaya et al. in their paper [7] showed that an SSS is considered verifiable if each user can verify the correctness of his share in the dealer phase and no user can lie about his share in the combiner phase. So, the success of SSS depends on the honesty of the dealer in dealer phase. Ravi K. Balachandran et al. in their paper proposed an efficient key agreement scheme namely Chinese Remainder Theorem and Diffie-Hellman (CRTDH) [8]. The proposed CRTDH protocol assume that there remains no pre-shared secrecy between the members and does not require the services of a trusted authority or a group controller. CRTDH uses the Diffie-Hellman key exchange and the Chinese Remainder Theorem for efficient key agreement of Symmetric Cipher. CRTDH solves two important problems of current SGC schemes namely, member serialization and central authority. The protocol emphasized more on efficient computation of group key, uniform workload distribution for all the members and few rounds of re keying. Besides these benefits, CRTDH suffers from man-in-the-middle attack and not optimized for a scalable ad hoc network where join and leave from a group occurs frequently. Moreover, the success of CRTDH depends more on the verification of SSS [7]. 9 Marianne A. Azer et al. in their paper surveyed over different threshold cryptography techniques and SSS [9]. In their paper, they point out many challenges and research options in the area of threshold cryptography and authentication. The major challenges of SSS are selections of the optimum threshold level, validity period of the partial key or secret sharing, behavior of corrupted nodes using incorrect partial keys and dynamic adjustment of the partial key validity time. Shichun Pang et al. proposed an optimized vector space verifiable SSS [10]. The security of their proposed model is based on Elliptic Curve Cryptography (ECC) [11]. The model had same precondition of (t, n) threshold SSS. In this model a verifiable infrastructure is provided, which detects the cheats from dealer and assignees. The shared key distributed by dealer is encrypted based on ECC. They showed that the computation and communication costs of the proposed model is less than any other existing SSS. The key length of elliptic curve cryptography is much less than RSA cryptography. So that, the model should be valuable in applications with limited memory and computing power. 2.2.3 Key Management Key management is the provision in a cryptography system that relates to generation, exchange, storage, safeguarding, use and replacement of keys. Successful key management is critical to the security of a cryptosystem. It is one of the most difficult aspects of cryptography because it involves system policy, type of interactions, storage structure and coordination between all of these elements. In practice, either Symmetric or Asymmetric Key management is chosen for a cryptosystem. Symmetric key management uses symmetric encryption keys. In a symmetric key algorithm the keys involved are identical for both encrypting and decrypting a message. Such keys must be chosen carefully, and distributed and stored securely. In any system, there may be multiple keys for various purposes. Accordingly, key management is central to the successful and secure use of symmetric key algorithms. The main characteristics of key management are discussed below10 Key Generation Key generation is the first phase of key management. It is one of the important parts of key management because weak keys make cryptanalysis easier for any cryptographic algorithms. The usual technique for generating a key is to select key from a pool of binary random numbers. The quality of the random number generator used should be as high as possible. This is difficult to achieve in practice. Many key derivation functions use a mathematical one way function, such as a cryptographic hash functions like MD5 or SHA1. Keys are often derived from a password or pseudo random number generator. Some of which are also cryptographically secure. Key Exchange Key Exchange is the second phase in key management. In symmetric key encryption algorithm, both the sender and the receiver must possess the same generated key. The exchange of such a key through an insecure network was extremely troublesome. The plain text exchange is quite impractical as any interceptor can immediately learn the key to be used and so will be able to decrypt messages. It has become possible to exchange a key over an insecure communications channel using Diffie-Hellman key exchange Algorithm (DHA). The simplest implementation of the protocol uses the Multiplicative Group of Integers modulo p, where p is prime and g is Primitive Root mod p. p and g is public and known to all users. The sender generates a secret random number a and sends g a mod p to receiver. Receiver generates a secret random number b and sends g b mod p to sender. Then, sender generates the secret key (g b mod p)a mod p or g ba mod p. Receiver generates the secret key (g a mod p)b mod p or g ab mod p. Send (g a mod p) to Receiver Sender −−−−−−−−−−−−−−−−→ Receiver Generates a Send (g b mod p) to Sender Receiver −−−−−−−−−−−−−−−→ Sender Generates b 11 Encrypt with (g ba mod p) Sender −−−−−−−−−−−−−−−−−−→ Receiver Calculates ((g b mod p)a mod p) Decrypt with (g ab mod p) Receiver −−−−−−−−−−−−−−−−−−→ Sender Calculates ((g a mod p)b mod p) However, DHA without proper authentication suffers from Man in the middle attack [Figure: 2.4]. In asymmetric key algorithm a session key is distributed as encrypted using the public key of the receiver, which is disclosed to all. The receiver decrypts the key with the help of his private key, which is only known to the receiver. This approach avoids even the necessity for using a key exchange protocol like Diffie-Hellman key exchange. Figure 2.4: Man in The Middle Attack Key Storage The third phase of key management is storing the keys. Symmetric keys must be stored securely to maintain secure communications. The threat for eavesdropping increases in symmetric key encryption algorithm because the same key is used by both the sender and the receiver for communication. In symmetric key encryption algorithm at least two 12 nodes know the secret key and repetition of same key might possible. In asymmetric key encryption algorithm the private key is known to only one node and corresponding public key is disclosed to all. Although the keys are related mathematically, the private key cannot be feasibly or actually derived from the public key. In a system of n nodes, symmetric key encryption algorithm needs to maintain n(n−1) 2 keys. On the other hand, asymmetric key encryption algorithm needs only 2n keys. So, the key management load increases in symmetric key encryption than asymmetric key encryption. Figure: 2.5 shows a comparative study of key management load on different cryptography techniques. Key Management Complexity Analysis 1200 Symmetric Key Asymmetric Key Number of Keys Needed 1000 800 600 400 200 0 5 10 15 20 25 30 35 40 45 50 Number of Nodes Figure 2.5: Key Management Load Comparison Key Usage One of the major issue of key management is the length of key used. As the length of the key increases so do the effort of attackers to retrieve the key. But the increasing size of key adds excessive computation for both encryption and decryption. So, the key size should neither small nor large. Table: 2.1 shows a comparison of key size of different encryption 13 algorithms [12]. From the table, it is clear that symmetric key encryption algorithm like Advanced Encryption System (AES) uses the lowest key size for encryption. On the other hand, the asymmetric key encryption algorithm like RSA or DH uses relatively higher key size than AES. In asymmetric key encryption algorithm, the higher key size is used making cryptanalysis attack difficult than symmetric key encryption algorithm. Although ECC dramatically reduces the key size, it provides the same security level as RSA/DH provides with higher key size. So ECC can provide strong security by using lower key size than any other asymmetric key encryption algorithm. Security Bits AES DH RSA ECC 80 80 1024 1024 160 112 112 2048 2048 224 128 128 3072 3072 256 192 192 7680 7680 384 256 256 15360 15360 512 Table 2.1: Key Size Comparison (in bits) for Equivalent Security Levels Clare McGrath et al. surveyed over different key management techniques [14]. In their paper they point out many challenges and research options in the area of efficient key management for MANET. Although the asymmetric key encryption is complex, they showed that it is more secure and flexible than symmetric key encryption. Finally, they proposed to deploy such a PKI protocol that must respect communication, computation, memory used and power restrictions of MANET. 2.3 Authentication Issue Authentication is the act of confirming the identity of an entity, tracing the origins of an artifact, or assuring that a node is a trusted one. The authentication of network nodes 14 and the establishment of secret keys among nodes are both target security objectives in ad hoc networks. The constrained devices and other special properties of ad hoc networks make achieving those security properties a challenging task. There remains many models of authentication containing different features and drawbacks. Providing entity authentication and authentic key exchange in ad hoc networks is still a challenge. The topics regarding to authentication issue are discussed below. 2.3.1 Key Agreement Key establishment is a process where two or more entities establish a shared secret key (session key) after message interactions. It is an important issue for secure communications between two or more parties over an insecure network [13]. There are two different approaches for key establishment between two entities. In first approach one entity generates a session key and securely transmits it to the other entity. In second approach both entities contribute to the derivation of the session key. Two-party authenticated key agreement (AK) protocols not only allow parties to compute a session key known only to them, but also ensure authenticity of the parties. This secret session key can then be used to provide privacy and data integrity during subsequent sessions. A protocol that provides mutual key authentication as well as mutual key confirmation is called an authenticated key agreement with key confirmation protocol (AKC). The commonly used AKC schemes are Public Key Infrastructure (PKI) and Identity based Public Key Cryptography (ID-PKC). Pierre E. Abi-Char et al. introduced a secure authenticated key agreement protocol based on ECC [15]. The model provides secure mutual authentication and explicit key establishment over an untrusted network. They proved that the security of the proposed model is stronger than any other existing Simple Key Agreement (SKA) protocols. The proposed model resists from dictionary attacks mounted by either passive or active network intruders. It also resists from Man In the Middle attack. In addition, the model resists from known-key and resilience to server attack. The proposed protocol used the signature 15 techniques of ECDSA and the SKA protocol concept. Moreover, the communication and computation cost of the model has been reduced significantly from other SKA protocols. 2.3.2 Identity Based Cryptography Identity based cryptography with much smaller length key can provide the same security level as the RSA and discrete logarithm cryptography, reducing the complex of the encryption and decryption operation [16]. Compared to the traditional PKI, Identity based cryptography needs no certificate management and CA. It greatly reduces the public key authentication computation, communication costs and the user’s storage capacity. However, ID-based cryptography suffers from two inherent problems namely, key escrow and secure channel requirement. The private key generator (PKG) has the knowledge of the users’ private keys and therefore can decrypt any cipher text or forge signature on any message, which is known as key escrow problem. Moreover, key issuing requires secure channel to avoid eavesdropping. A. Rex et al. provided a new security support for MANETs named Address-based Cryptography Scheme (ACS) [17]. ACS is a combination of Ad hoc node address and public key cryptography. Unlike other certificate based cryptography, ACS nodes are directly deliverable from their known Ad hoc node address plus some common information such as entry time, exit time and number of nodes in the network. They showed that their proposed framework protects from the masquerading and eavesdropping in wireless networks. The conventional key management techniques require trusted certificate server for key management and distribution. The infrastructure less nature of MANET prevents the use of server based protocols such as Kerberos. Although a certificate less public key cryptography reduces the overhead of key management, it is more vulnerable than certificate based key distribution and management system. The private and public key generation in ACS does not ensure uniform key distribution, which is essential for enhancing security in public key cryptography. ACS broadcasts encrypted message containing its own private key which 16 increases security threats for MANET. Wei Liu et al. emphasized in efficient key management named, ID-based key management (IKM) cryptography [18]. IKM is a certificate less solution where public keys of mobile nodes are directly derivable from their known IDs plus some common information. It thus eliminates the need for certificate-based authenticated public-key distribution indispensable in conventional public-key management schemes. Although the simulation result showed IKM is optimized and efficient than conventional certificate based authorization, the unique generation of ID for a distributed system is hard enough without any single certified key generation authority like Kerberos. Mahalingam Ramkumar et al. proposed a novel Identity based key predistribution model named, Hashed Random Preloaded Subsets (HARPS) [19]. Their Key Predistribution Scheme (KPD) is a composition of two Probablistic KPD namely, Random Pre Distribution Scheme (RPS) and Leighton and Micali Scheme (LM). The researchers used a cryptographic hash function h(.) for one way encryption and a public-key-generation function F (.) for higher security. HARPS is defined by three parameters (P, k, L). The Trusted Authority (TA) determines P secrets or root keys. From each root key one can get L derived keys by repeated application of the one-way function h(.). For a node of identity IDA , application of public function F (IDA ) yielded a sequence of k length ordered pairs. According to this scheme, all nodes are preloaded initially with k secrets so that authenticated secret sharing can be assured. Although the approach is novel, There remains some major drawbacks of the scheme. HARPS used PKI over symmetric key cryptography which increased overhead of the system. Since the entry and exit of a node in MANET is not fixed, Calculation and Key Predistribution and in MANET is not viable [20]. Moreover, how the system will manage the keys of leaving nodes has not been discussed in this model. Mengbo Hou et al. showed that ID based cryptography scheme is vulnerable to the key replicating attack [21]. Key Replication Attack is one form of the man-in-the-middle at17 tack, where an active adversary can intercept and properly modify the messages exchanged between two parties, and force two parties to accept the same session key, which is not the one that two parties really want to agree on. PI Jian-Yong et al. proposed a scheme to discard the traditional identity authentication mechanism for identity and PKI [23]. The identity of each node in Ad Hoc network is fixed compared with the key of session. The session key is different in every session, but the authentication code (AC) is unchanged in all sessions. Their performance analysis demonstrates that their scheme can prevent existential forgery attacks and Byzatine node conspiracy attacks. Although the simulation results of the proposed cryptography demanded high efficiency against Sybil Attack, the scheme is vulnerable to the key replicating attack [21]. Yuguang Fang et al. summarized different cryptographic techniques for wireless Ad Hoc networks [2]. Considering the limited resource constraints of MANET, they proposed to utilize Identity Based Cryptography [16]. Although the Identity Based Public Key Cryptography (ID-PKC) reduces the excessive overhead of key agreement from CA, the security of ID-PKC depends on the difficulty of computing Bilinear Diffie-Hellman Problem (BDHP). Suppose each user in the network has a public key QA , which is an element of group G1 corresponding to the identity A. The secret key of user A is DA = sQA in G1 . Let P, sP, rP, tP in G1 are global public parameter and e(P, Q) be the element of G2 which is the pairing applied to P and Q. Then, the BDHP should be hard to compute if for QA = tP , computation of e(DA , U ) = e(P, P )rst is hard [12]. 2.3.3 Sybil Attack The Sybil attack is an attack where a reputation system is subverted by forging identities in peer-to-peer networks [24]. It is named after the subject of the book Sybil, a case study of a woman with multiple personality disorder. In Sybil attack an attacker subverts the 18 reputation system of a peer-to-peer network by creating a large number of pseudonymous entities, using them to gain a disproportionately large influence. An entity on a peer-to-peer network is a piece of software which has access to local resources. An entity advertises itself on the peer-to-peer network by presenting itself with an identity. More than one identity can correspond to a single entity, in other words, the mapping of identities to entities is many to one. Entities in peer-to-peer networks use multiple identities for purposes of redundancy, resource sharing, reliability and integrity. In peer-to-peer networks the identity is used as an abstraction so that a remote entity is aware of identities without necessarily knowing the correspondence of the identities with their local entities. A faulty node or an adversary may present itself with multiple identities in a peer-to-peer network to appear and function as distinct nodes. Becoming part of the peer-to-peer network, the adversary may then overhear communications or act maliciously. The adversary can control the network substantially by masquerading and presenting multiple identities. Piro et al. have proposed an application domain specific detection mechanism for mobile ad hoc networks [25]. The scheme is based on the fact that Sybil nodes in mobile ad hoc networks normally move in clusters. The researchers showed that the evaluation of geographical location patterns of clusters of identifiers that are moving together can potentially indicate the presence of a device launching a Sybil attack. The scheme did not consider the multiple collaborating Sybil attackers that can thwart observers node and can cause Denial of Service (DoS). 2.3.4 Location Based Authentication Location Based Authentication (LBA) is a special authentication procedure to prove an individual’s identity and authenticity on appearance simply by detecting its presence at a distinct location [26]. To enable LBA, a special combination of objects is required, namely, the node has to present a sign of identity and the node has to carry at least one human authentication factor that may be recognized on the distinct location and finally a distinct 19 location. There are some limitations of LBA. In Ad hoc networks the LBA should conscious about detecting the leave and closing the granted access of leaving nodes and limiting the granted time for access. Tina Suen et al. concentrated on identification and authentication in ad hoc networks [27]. Identification and Authentication are particularly susceptible to identity attacks, for example, masquerading. For mitigating the identity attacks, they proposed to associate the message transmitter with a location and use this location information to find out identity. According to the proposed method, a Verifying Node (VN) authenticates a transmitting peer node’s location using a combination of signal properties, trusted-peer collaboration, and global positioning systems (GPS) for identification purposes. Although they emphasized in the direction information about peer identity from signal’s origin, signal direction by itself is not a strong identity indicator. Moreover, they consider identification based on triangular positioning system where the three key points are The VN, trusted peer, and transmitter. Then, triangulation and trigonometric functions are used to calculate the transmitter’s location. But a problem occurs when the three points lied on a same straight line. Moreover, calculation based on relative position is not an efficient approach for identifying a deceptive node. Sheng-Ti Li et al. in their paper presented a new approach to deal with security problems in routing protocols [28]. We focus on Dynamic Source Routing (DSR) as their test bed for its rich information in the routing discovery packets, and independence from addressing issues. Their proposed geography based routing discovery protocol combined with threshold cryptography for secure routing discovery as well as efficient ARP management. Although the simulation results based on DSR is promising on security perspective, the latency is not optimized and the scheme is highly biased by ARP cache poisoning. Figure: 2.6 shows a scenario where intruders can get ARP request and reply for modifying ARP cache. 20 Figure 2.6: Nodes can Spoof MAC address or cause ARP Cache Poisoning 2.4 Digital Signature Algorithm Digital signature schemes (DSS) are designed to provide the digital counterpart to hand written signatures. A digital signature is a number dependent on some secret known only to the signer (the signers private key), and additionally, on the contents of the message being signed. The generated or signed digital signatures must be verifiable. If a dispute arises as to whether an entity signed a document, an unbiased third party should be able to resolve the matter equitably, without requiring access to the signers private key. Disputes may arise when a forger makes a fraudulent claim. DSA should contain two major properties for performing it’s basic task. Firstly, a signature generated from a specified message and a specified private key must be verified by that message and the corresponding public key. Secondly, it should be computationally infeasible to generate a valid digital signature file for a party that does not possess the 21 appropriate private key. DSA can be used to provide the basic cryptographic services like, data integrity or the assurance that data has not been altered by unauthorized user, data origin authentication or the assurance that the source of data is as claimed. The non repudiation or the assurance that an entity cannot deny previous actions or commitments is also afforded. DSA is commonly used as primitives in cryptographic protocols that provide other services including entity authentication, authenticated key transport and authenticated key agreement. The digital signature schemes in use today can be classified according to the hard underlying mathematical problem which provides the basis for their security. For example, IFP, DLP and ECDLP. Integer Factorization scheme is based upon their security on the intractability of the integer factorization problem. RSA-DSA scheme is based on it. Discrete Logarithm scheme is based upon their security on the intractability of the ordinary discrete logarithm problem in a finite field. ElGamal-DSA scheme is based on it. Finally, Elliptic Curve scheme is based upon their security on the intractability of the ECDLP. 2.4.1 DSA Operation DSA consists of four types of operations. They are, domain parameter generation, DSA key pair generation, DSA signature generation or signing and finally DSA signature verification or verifying. The sender end performs the signing operation and the receiver end performs the verifying operation. The certificate authority performs the task of domain parameter generation and DSA key pair generation tasks. 2.4.2 Domain Parameter Generation 1. Select a 160bit prime q and a 1024bit prime p with the property that q|(p–1) 2. Select a generator G of the unique cyclic group of order q in Zp∗ 22 3. Select an element h ∈ Zp∗ and compute G = h p–1 q (mod p) 4. Domain parameters are p, q and G 2.4.3 DSA Key Pair Generation Each entity A in the domain with domain parameters (p, q, G) does the following: 1. Select a random or pseudorandom integer x such that 1 ≤ x ≤ q–1 2. Compute y = Gx (mod p) 3. A’s public key is y and private key is x 2.4.4 DSA Signature Generation To sign a message m, A does the following: 1. Select a random or pseudorandom integer k,1 ≤ k ≤ q–1 2. Compute X = Gk (mod p) and r = X (mod q) 3. Compute k –1 (mod q) 4. Compute e = SHA1(m) 5. Compute s = k –1 (e + xr) (mod q) 6. A’s signature for the message m is (r, s) 2.4.5 DSA Signature Verification To verify A’s signature (r, s) on m, B obtains authentic copies of A’s domain parameter (p, q, G) and public key y and does the following: 1. Verify r and s are integers in range [1, q–1] 23 2. Compute e = SHA1(m) 3. Compute w = s–1 (mod q) 4. Compute u1 = ew (mod q) and u2 = rw (mod q) 5. Compute X = Gu1 y u2 (mod p) and v = X (mod q) 6. Accept the signature if and only if v = r 2.5 Certificate Authority Certificate authority (CA) is an entity that issues digital certificates for use by other parties [29]. From Figure: 2.7 a CA issues digital certificates that contain a public key and the identity of the owner. The matching private key is not similarly made available publicly, but kept secret by the end user who generated the key pair. The certificate is also an attestation by the CA that the public key contained in the certificate belongs to the person, organization, server or other entity noted in the certificate. A CA’s obligation in such schemes is to verify an applicant’s credentials, so that users and relying parties can trust the information in the CA’s certificates. If a user trusts the CA and can verify the CA’s signature, he can also verify that a certain public key does indeed belong to whomever is identified in the certificate. Jun Luo et al. in their paper proposed a novel architecture for Distributed Certificate Authority (DCA) named DICTATE [30]. The general idea of DICTATE is to combine an offline Identification Authority (IA) and an online revocation authority (RA). The RA is implemented in a distributed fashion using threshold cryptography (TC) [4]. Therefore, the DICTATE system does not provide a single point of failure like a centralized system. However, DICTATE needs all offline IA configuration tasks to be carried out offline. Ricardo Marin et al. showed that such a distributed certification authority is not viable for 24 Figure 2.7: Public and Private Key Generation of Certificate Authority a Peer To Peer (P2P) mesh network [31]. Moreover, Denial of Service (DoS) attack is a serious threat for DICTATE architecture. 2.6 Summary This chapter provides us with a profound knowledge of different issues of security for MANET. Achieving secure framework for MANET is a difficult task. Combination of different approaches should be applied in wireless networks to achieve strong security. Although the RC4 symmetric key cryptography is currently used for wireless networks, it does not ensure strong encryption and authentication. On the other hand, asymmetric key cryptography ensures strong encryption and authentication, but performs more computations than symmetric key cryptography. For limited resources’ networks like MANET is not suitable for such high degree computations that RSA do. So, if we emphasize more on security, strong cryptography algorithm should not be implemented on limited resources’ networks. And if we emphasize more on optimizing the resources of the networks, symmetric key cryptography should be implemented that does not ensure strong security. So such 25 an asymmetric key cryptography should be chosen that provides not only strong security, but also suitable for limited resources’ networks. For enhancing security in MANET, such a PKI should be chosen that provides strong encryption facility as well as lower computation to perform the underlying tasks of encryption and decryption. Before choosing such a scheme we should study in-depth of all the existing asymmetric key cryptography schemes. 26 Chapter 3 Public Key Cryptography Public-key cryptosystems provides more robust security than private-key cryptosystems. Although the private-key cryptosystems is simple to implement and easy to access, it is not suitable for large and distributed networks. In Ad hoc networks where the entrance and exit of a node is not fixed, private-key cryptosystems should create security holes for its characteristics of inefficient key management. In this chapter, a brief description of mathematics for public key cryptography and how different public-key cryptosystems works has been discussed. This chapter will help us to understand how public-key cryptosystems ensure their security by using the difficulty of solving different mathematical problems. If a mathematical problem is difficult enough for solving without proper clues that problem might be implemented securely in cryptography to prevent intruders getting hidden information. Before beginning any discussion on public-key cryptosystems, review of some basics on number theory, linear algebra, cryptography are discussed that support the ideas of the public-key cryptosystems. Later, different components of a cryptosystem and how a cryptosystem works is described. Finally, three well-known mathematical problems and public-key cryptosystems based on those problems are discussed. A comparative study between different public-key cryptosystems is focused at the end of this chapter. 3.1 Essential Concepts the underlying security strength of different PKC systems depend on cryptography mathematics. This section overviewed some basic cryptography mathematics for understanding the security architecture of different PKC systems. 27 3.1.1 Integers in PKC The set of all integers will be denoted by Z. N stands for the set of all positive integers. For a finite set A, the number of elements of A is denoted by #A. Some important theorem are discussed below regarding divisibility of integers that should help to understand modular arithmetic of cryptography. Theorem 1 Euclids Division Algorithm: For a, b ∈ Z, b 6= 0, there exist uniquely determined q, r ∈ Z such that a = bq + r, (0 ≤ r ≤ |b|) If r = 0, we say that b is a divisor of a, and denote it as b|a. Otherwise we write b 6 |a. For a1 , . . . , ak ∈ Z , if b|ai (i = 1, . . . , k), then b is called a common divisor of a1 , . . . , ak . The largest common divisor of a1 , . . . , ak always exists. It is denoted by gcd(a1 , . . . , ak ). a, b ∈ Z are called relatively prime if and only if gcd(a, b) = 1 ([32] Page-45). Theorem 2 If a, b ∈ Z , not both zero, then d = gcd(a, b) is the smallest element in the set of all positive integers of the form ax + by (x, y ∈ Z). Let C = {c ∈ N | c = ax + by, x, y ∈ Z}. C 6= ∅, because if a 6= 0, –a ∈ C . Let e = ax0 + by0 be the smallest element of C . If d = e, where a = eq + r, 0 ≤ r < e then it proves d = gcd(a, b) is the smallest element. Now, r = a–eq = a(1–qx0 ) + b(–qy0 ) If r = 0, it would be in C and would contradict with e. Thus, e|a. Similarly, e ≤ d. On the other hand, since e = ax0 + by0 and d|a, d|b, it follows e|b, that d|e. Hence, d ≤ e. Therefore, d = e ([32] Page-49). Theorem 3 There exist x, y ∈ Z satisfying ax + by = c if and only if d|c, where d = gcd(a, b). 28 If a = ed, b = f d, then clearly d|c. On the other hand, if d|c, let kd = c. Since there exist x0 , y0 ∈ Z such that ax0 + by0 = d then a(kx0 ) + b(ky0 ) = kd = c For a, b, m ∈ Z, a≡b (mod m) ⇐⇒ m|(a–b) Theorem 4 For a, m ∈ Z , there remains x ∈ Z such that ax ≡ 1 (mod m) if and only if gcd(a, m) = 1. There is a x ∈ Z such that ax ≡ 1 (mod m) ⇐⇒ there are x, y ∈ Z such that ax–my = 1. Therefore, Theorem 3 completes the proof. p ∈ N is called a prime number if and only if p > 1 and a 6 |p for all a ∈ Z , 1 < a < p. Let p ∈ N, p > 1. p is prime if and only if for any a, b ∈ Z, p|ab =⇒ p|a or p|b ([32] Page-56). Theorem 5 Chinese Remainder Theorem: Suppose m1 , . . . , mr ∈ N are relatively prime in pairs, i.e. gcd(mi , mj ) = 1 for i 6= j . Let a1 , . . . , ar ∈ Z . Then, the system of r congruences x ≡ ai (mod mi ) (1 ≤ i ≤ r) has a unique solution modulo M = m1 × . . . × mr given by x= r X a i Mi y i (mod M ) i=1 where Mi = M/mi and Mi yi ≡ 1 (mod mi ) ([32] Page-60). Mi is the product of all mj where j 6= i. So if j 6= i, then Mi ≡ 0 (mod mj ) . Note that, gcd(Mi , mi ) = 1, so by Theorem 4, Mi yi ≡ 1 (mod mi ) has a solution yi . Thus, x= r X a i Mi y i ≡ a i Mi y i ≡ a i (mod mi ) i=1 for all i, 1 ≤ i ≤ r. Therefore, x is a solution to the system of congruences. 29 Theorem 6 φ(m) = #{a ∈ Zm | ab ≡ 1 (mod m) f or some b ∈ Zm } where φ(m) is the Eulers function φ: N − → N is def ined as φ(m) = #{k ∈ N | 1 ≤ k ≤ m, gcd(k, m) = 1} If p is a prime number, φ(p) = p–1 and for any a ∈ Zp , p 6 |a, there is b ∈ Zp such that ab ≡ 1 (mod p). Suppose p is an odd prime and x ∈ Z , 1 ≤ x ≤ p–1. Then x is called a quadratic residue modulo p if y 2 ≡ x (mod p) has a solution y ∈ Zp . x is a quadratic non-residue if x is not a quadratic residue modulo p and x 6≡ 0 (mod p) ([32] Page-62). 3.1.2 Groups in PKC A group is a structure consisting of a set G and a binary operation ⋆ on G ([33] Page-51)(i.e. for any a, b ∈ G, a ⋆ b ∈ G is defined) such that: 1. a ⋆ (b ⋆ c) = (a ⋆ b) ⋆ c for a, b, c ∈ G [associativity] 2. there is an element e ∈ G such that e ⋆ a = a ⋆ e = a for every a ∈ G. This unique element e is called the neutral element of G. 3. for each a ∈ G there is an element b ∈ G such that b ⋆ a = a ⋆ b = e. b is uniquely determined and called the inverse of a. The notation hG, ⋆i is used to represent a group with group operation ⋆. hG, +i and hG, .i are called an additive group and a multiplicative group, respectively. In an additive group, the neutral element is represented by the symbol and the inverse of a is denoted as –a. In a multiplicative group, the neutral element is represented by the symbol 1 and the inverse of a is denoted as a–1 ([33] Page-52). hG, ⋆i is called an abelian or commutative group if a ⋆ b = b ⋆ a for any a, b ∈ G ([33] Page-53). 30 Let hG, ⋆i be a group and let H be a subset of G. The structure hH, ⊙i is said to be a subgroup of hG, ⋆i, if ⊙ is the restriction of ⋆ to H × H and hH, ⊙i is a group ([33] Page-64). If G is a finite group, then the number of elements of G is called the order of G and it is denoted as |G|. Given a finite multiplicative group G, the order of an element a ∈ G is the smallest positive integer m such that am = 1. Such an m exists for every element in a finite multiplicative group([33] Page-51). Theorem 7 Let G be a finite multiplicative group of order n. If the order of an element a ∈ G is m, then ak ≡ 1 if and only if m|k If k = mq, then ak = (am )q = 1. For the converse, let k = mq + r, 0 ≤ r < m. Then ar = ak (a–1 )mq = 1. Therefore, it follows by the minimality of m that r must be 0. Theorem 8 If G is a finite multiplicative group of order n, then 1. for every element a ∈ G, an = 1. 2. the order of any element of G divides |G|. If a ∈ G is of order m, then H = {ak | k ∈ Z} is a subgroup of G of order m. If G has an element a of order n = |G|, then G = {ak | k ∈ Z} and G is called cyclic and a is called a generator of G ([33] Page-73). The set Zn = {0, 1, 2, . . . , n–1} is a cyclic group of order n under addition modulo n, i.e. a + b ≡ r (mod n), where r < n (r is the remainder when a + b is divided by n). Theorem 9 Euler’s Theorem: For a, m ∈ Z such that (a, m) = 1, aφ(m) ≡ 1 ([32] Page-62) 31 (mod m) Theorem 10 Fermat’s Theorem: Let p be a prime number and a ∈ Z. 1. ap–1 ≡ 1 (mod p), if p|a. 2. ap ≡ a (mod p). ([32] Page-62) 1. Since φ(p) = p–1, this is a special case of Eulers Theorem. 2. This Proof is trivial if a ≡ 0 (mod p). Otherwise, it follows from (1). 3.1.3 Rings in PKC A ring is a set R together with two binary operations + and · (called addition and multiplication, respectively) defined on R such that the following conditions are satisfied : 1. hR, +i is an abelian group. 2. a · (b · c) = (a · b) · c for any a, b, c ∈ R [associativity of ·] 3. a · (b + c) = a · b + a · c and (a + b) · c = a · c + b · c for any a, b, c ∈ R [distributivity of · over +] A ring in which the multiplication · is commutative is called a commutative ring. An element e in a ring R such that e · a = a · e = a for each a ∈ R is a unity element or multiplicative identity, and it is represented by 1. If R has a unity element, then it is said to be a unitary ring or a ring with unity element ([34] Page-16). 32 3.1.4 Mappings in PKC Given that ⋆ and ⊙ are binary operations on the sets A and B respectively, a mapping f :A− → B preserves the operation of A if for all a, b ∈ A we have f (a ⋆ b) = f (a) ⊙ f (b) Suppose A and B are two groups (or two rings). We call h : A − → B a homomorphism of A into B if h preserves the group operation (or ring operations + and ·) of A. A homomorphism h is a monomorphism if h is one-to-one (i.e. if a 6= b implies that h(a) 6= h(b)). h is said to be a map onto B if {h(a) | a ∈ A} = B . A monomorphism onto B is called an isomorphism. If there is an isomorphism of A onto B , then we say that A and B are isomorphic and we write A ≃ B ([34] Page-17). 3.1.5 Fields in PKC A field F is a commutative ring with unity element e 6= 0 such that F ∗ = {a ∈ F | a 6= 0} is a multiplicative group ([34] Page-17). Theorem 11 The ring Zp is a field if and only if p is a prime number. Let F be a field. A subset K of F that is also a field under the operations of F (with restriction to K ) is called a subfield of F . In this case, F is called an extension field of K. If K 6= F then K is a proper subfield of F . A field is called prime if it has no proper subfield. For any field F , the intersection F0 of all subfields of F has no proper subfield, and F0 ≃ Q ( = the field of all rational numbers) or F0 ≃ Zp , where p is a prime number. A field F is said to have characteristic 0 if F0 ≃ Q, that is, if F contains Q as a subfield. A field F is said to have characteristic p if F0 ≃ Zp . A finite field is a field that contains only finite number of elements. Every finite field has a prime number as its characteristic ([34] Page-43). 33 Let F be an extension field of a field K. F = K(α) if F is the smallest extension field (i.e. the intersection of all extension fields) of K which contains α. If F is a finite field of characteristic p, then the multiplicative group F ∗ = F –{0} is cyclic and F = Zp (α), where α is a generator of the group F ∗ (see [17, pp. 4647] for the proof). α is called a primitive element of F ([35] Page-48). 3.1.6 Vector Spaces and Coordinate Geometry in PKC Let K be a field and let V be an additive abelian group. V is called a vector space over K if an operation K × V − → V is defined so that the following conditions are satisfied : 1. a(u + v) = au + av 2. (a + b)u = au + bu 3. a(bu) = (a · b)u 4. 1u = u The elements of V are called vectors and the elements of K are called scalars. Let V be a vector space over a field K and let v1 , v2 , . . . , vm ∈ V . Any vector in V of the form c1 v1 + c2 v2 + . . . + cm vm where ci ∈ K (i = 1, . . . , m) is a linear combination of v1 , v2 , . . . , vm . The set of all such linear combinations is called the linear span of v1 , v2 , . . . , vm and it is denoted by span(v1 , v2 , . . . , vm ). The vectors v1 , v2 , . . . , vn are said to span or generate V if V = span(v1 , v2 , . . . , vn ) ([35] Page-30). Let V be a vector space over a field K. The vectors v1 , v2 , . . . , vm ∈ V are said to be linearly independent over K if there are no scalars c1 , c2 , . . . , cm ∈ K (not all 0) that satisfy c1 v1 + c2 v2 + . . . + cm vm = 0 34 A set S = {u1 , u2 , . . . , un } of vectors is a basis of V if and only if u1 , u2 , . . . , un are linearly independent and they span V . If S is a basis of V , then every element of V is uniquely represented as a linear combination of the elements of S. If a vector space V has a basis of a finite number of vectors, then any other basis of V will have the same number of elements. This number is called the dimension of V over K. If F is an extension field of a field K, then F is a vector space over K. The dimension of F over K is called the degree of the extension of F over K. 3.1.7 Polynomial Rings in PKC Let F be an arbitrary ring. A polynomial of degree n over F is an expression of the form f (x) = n X ai x i = a0 + a1 x + . . . + a n x n i=0 where n is a positive integer, the coefficients ai ∈ F (0 ≤ i ≤ n), and x is a symbol not belonging to F , called an indeterminate over F . To evaluate a polynomial f (a) for some a ∈ F , we replace every instance of the indeterminate x in f (x) with a. Given two polynomials n X f (x) = ai x i i=0 n X g(x) = bi xi i=0 The sum of f (x) and g(x) can be defined as f (x) + g(x) = n X (ai + bi )xi i=0 Given two polynomials f (x) = n X ai x i i=0 g(x) = m X j=0 35 bj xj The product of f (x) and g(x) can be defined as f (x)g(x) = n+m X X ck xk where ck = ai b j i+j=k 0≤i≤n, 0≤j≤m k=0 The ring formed by all polynomials over F with ordinary operations of addition and product is called the polynomial ring over F and denoted by F[x]. Theorem 12 (Division algorithm for F [x]) Let f (x), g(x) ∈ F [x] be of positive degrees. Then there exist unique polynomials q(x), r(x) ∈ F [x] such that f (x) = g(x) · q(x) + r(x) where the degree of r(x) is less than the degree of g(x). If r(x) is the zero polynomial (i.e. r(x) = 0), then g(x) is said to be a divisor of f (x). A non-constant polynomial f (x) in F [x] is irreducible in F [x] if it has no divisor of lower degree than f (x) in F [x]. An element a ∈ F is a root or zero of the polynomial f (x) ∈ F [x] if f (a) = 0. Theorem 13 An element a ∈ F is a root of the polynomial f (x) ∈ F [x] if and only if x–a is a divisor of f (x) in F [x]. Let f (a) = 0. Since f (x) = (x–a) · q(x) + r(x), then the degree of r(x) is less than 1, i.e. r(x) = c ∈ F . Hence, c = f (a) = 0. Conversely, if f (x) = (x–a) · q(x), then f (a) = 0 ([34] Page-23). Theorem 14 A nonzero polynomial f (x) ∈ F [x] of degree n can have at most n roots in F. 3.1.8 Finite Fields in PKC A field of a finite number of elements is denoted by Fq or GF (q), where q is the number of elements. 36 Theorem 15 Let F be a finite extension of degree n over a finite field K. If K has q elements, then F has q n elements. Let {α1 , . . . , αn } be a basis for F as a vector space over K. Then every β ∈ F is uniquely represented in the form β = c1 α1 + . . . + cn αn where ci ∈ K(i = 1, . . . , n). Since each ci may be any of q elements of K , the total number of such a linear combination is q n . Theorem 16 If F is a finite field of characteristic p then F has exactly pn elements for some positive integer n [17, page 44]. Therefore, every finite field is an extension of finite degree of a field isomorphic to Zp , where p is a characteristic of F . Theorem 17 A finite field F = Fpn is an extension field of Zp of degree n and every n element of Fpn is a root of the polynomial xp –x over Zp . The characteristic of Fpn must be p. The set F ∗ = F –{0} forms a multiplicative group of order pn –1 under the field multiplication. For α ∈ F ∗ , the order of α in this group divides the order of F ∗ , pn –1. Therefore, for every α ∈ F ∗ , we have αp n n –1 n = 1 i.e. αp = α. n Since xp –x has at most pn roots, Fpn consists of all roots of xp –x over Zp . The field F2r contains F2 (or Z2 ). If the addition operation in F2r is written as the vector addition and the product of k and v (k, v ∈ F2r ) as the scalar product kv of k ∈ F2 and v ∈ F2r , then F2r can be viewed as a vector space over F2 with a dimension of r. Furthermore, let d denote the dimension of this vector space. Then a one-to-one correspondence can be drawn between the elements (vectors) of this d-dimensional vector space and the set of all d-tuples of elements in F2 . Therefore, there must be 2d elements in this vector space. Since d = r, F2r is a vector space of dimension r. Let Fqm be an extension of Fq . Two elements α, β ∈ Fqm are conjugate over Fq if α and 2 β are roots of the same irreducible polynomial of degree m over Fq . α, αq , αq , . . . , αq are called the conjugates of α ∈ Fqm with respect to Fq [17, page 49]. 37 m–1 Let Fqm be an extension field of Fq . A basis of Fqm (a vector space over Fq ) of the form 2 {α, αq , αq , . . . , αq m–1 }, consisting of a suitable α ∈ Fqm and its conjugates with respect to Fq , is called a normal basis of Fqm over Fq . For every extension field of finite degree of a finite field there is a normal basis ([35] Page-45). 3.1.9 Projective Coordinates in PKC Consider L = K n+1 –{0}, where K is a field. For A = (a0 , a1 , . . . , an ), B = (b0 , b1 , . . . , bn ) ∈ L, define a relation AB to mean that A, B and the origin O = (0, 0, . . . , 0) are colinear, that is, there is a λ ∈ K such that λai = bi (i = 0, 1, . . . , n) The relation is an equivalence relation, and defines a partition of L. The quotient set is a projective space denoted by P n (K). The projective plane is the set of equivalence classes of triples (X, Y, Z) (not all components zero) where (λX, λY, λZ)(X, Y, Z)(λ ∈ K) ([36] Page-3). Each equivalence class (X, Y, Z) is called a projective point on the projective plane. If a projective point has Z = 0, then (x, y, 1) is a representative of its equivalence class where we set x = X ,y Z = Y . Z Therefore, the projective plane can be defined by all the points (x, y) of the ordinary (affine) plane (denoted in projective coordinates as (x, y, 1)) plus all the points for which Z = 0 ([36] Page-52). 3.2 Cryptosystem This section discusses some well-known means by which Alice can send a private (i.e. encrypted) message to Bob. The information that Alice wants to share with Bob is called the plaintext. The encrypted plaintext that Alice actually sends to Bob is called the ciphertext. A cryptosystem consists of a finite set of possible plaintexts, a finite set of possible ciphertexts, a finite set of possible keys, an encryption rule for encrypting plaintext into 38 ciphertext and a decryption rule for decrypting ciphertext back to plaintext. The general idea behind any cryptosystem is that Alice and Bob must share a secret key which is used to encrypt a message, and without which the plaintext cannot be recovered. Figure 3.1: Operations in Cryptosystem Private-key Cryptosystems If there is a way for Alice and Bob to secretly share a key K prior to the transmission of plaintext, they can use encryption and decryption rules defined by their secret value of K . Cryptosystems of this form are called private-key cryptosystems. One approach to sharing keys is the key agreement protocol whereby Alice and Bob jointly establish the secret key by using values they have sent each other over a public channel. In these systems, the decryption rule is identical to or easily derived from the encryption rule. Hence, exposure of the encryption rule to an eavesdropper will render the system insecure. Figure 3.2: Use of Symmetric Key Cryptography for Only Confidentiality 39 Public-key Cryptosystems The security of private-key systems depend on the secret exchange or establishment of keys between Alice and Bob. However, in public-key cryptosystems Bob keeps his key (and his decryption rule) to himself, whereas the corresponding encryption rule is publicly known. Therefore, Alice can send encrypted messages without any prior sharing of keys, and Bob will be the only person able to decrypt the messages sent to him. Figure 3.3: Use of Asymmetric Key Cryptography for Confidentiality Figure 3.4: Use of Asymmetric Key Cryptography for Authentication public key cryptography is based on strong mathematical proof. On the other hand private key cryptography is still vulnerable to well-known attacks. Although the public key cryptography operations are more complex than private key cryptography operations, public key cryptography provides the highest level of security for any network. So, it should 40 be a wise decision to exchange private key cryptography with public key cryptography for enhancing security. 3.2.1 Discrete Logarithm Problem For some group G, suppose α, β ∈ G. Solving for an integer x such that αx = β is called the Discrete Logarithm Problem (DLP). The DLP in Zp is considered difficult (or intractible) if p has at least 150 digits and p–1 has at least one large prime factor (as close to p as possible). These criteria for p are safeguards against the known attacks on DLP. Numerous cryptosystems base their security on the difficulty of solving the DLP. One such public-key cryptosystem is the El Gamal Cryptosystem in Zp∗ [37]. An attacker could decrypt Alices message if Bobs secret key aB could be computed from β ≡ αaB (mod p) and α which are publicly known. This is the DLP. The decryption rule can be explained as follows: y2 (y1aB )–1 ≡ xβk (αkaB )–1 ≡ xαaB k (α–kaB ) ≡ x 3.2.2 (mod p) El Gamal Cryptosystem Let p be a prime such that the DLP in Zp is intractible, and let α ∈ Zp∗ be a primitive element. p and α are publicly known. Each user X chooses a secret key aX (an integer, where (0 ≤ a ≤ p–2) and publishes β where β ≡ αaX (mod p). For Alice to send her message x ∈ Zp∗ , she must choose a random number k ∈ Zp –1 and send (y1 , y2 ) = (αk (mod p), xβ k To decrypt, the recipient Bob computes y2 (y1aB )–1 where aB is his secret key. 41 (mod p) (mod p)) 3.2.3 Integer Factoring Problem There are also a number of cryptosystems whose security is based on the difficulty of factoring large integers. One well-known example is the public-key system called the RSA Cryptosystem [28, 33]. It is presented in Figure 2.5. Note that Bob can compute a = b–1 (mod φ(n)) from b by using the Extended Euclidean Algorithm [33, page 119] presented in Figure 2.6. For x ∈ Zn∗ , the decryption rule can be verified as follows: since ab ≡ 1 (mod φ(n)), we can represent ab as ab = k · φ(n) + 1 for some integer k ≥ 1. Then y a ≡ (xb )a (mod n) y a ≡ xk·φ(n)+1 (mod n) y a ≡ (xφ(n) )k x (mod n) y a ≡ 1k x ya ≡ x 3.2.4 (mod n) (mod n) RSA Cryptosystem For RSA to be secure, it should be computationally infeasible to factor n = pq even when using the best factoring algorithms, i.e. p and q should be sufficiently large. If p and q are known, it is easy to compute φ(n) = (p–1)(q–1) and derive a. At present, it is recommended that p and q should each be primes having around 100 digits [33, page 126]. However, it should be noted that there are also a number of attacks on RSA that do not involve the factoring of n at all. They generally exploit weaknesses in the setup of the cryptosystem, such as poor choices of a, or Bobś usage of the same n to communicate with other people. For further information, see [28, 33]. Bob secretly chooses two primes, p and q, and publishes n = pq. Next, he randomly chooses b such that b and φ(n) = (p–1)(q–1) are relatively prime. Bob computes a such that ab ≡ 1 (mod φ(n)). a is his secret key, whereas b is revealed to the public. Alice 42 encrypts her plaintext message x ∈ Zn by computing y = xb (mod n) and sends y to Bob. Bob retrieves x by computing y a (mod n) 3.3 Elliptic Curve Let K be a field. For example, K can be the finite (extension) field Fqr of Fq , the prime field Zp where p is a (large) prime, the field R of real numbers, the field Q of rational numbers, or the field C of complex numbers. Then an elliptic curve over a field K is defined by the Weierstrass equation: y 2 + a1 xy + a3 y = x3 + a2 x2 + a4 x + a6 where a1 , a3 , a2 , a4 , a6 ∈ K . The elliptic curve E over K is denoted by E(K). The number of points on E is denoted by #E(K). Elliptic Curve for Equation y2=x3-x 2 3 y =x -x 5 4 3 2 4 1 2 0 -1 -0.5 0 0 0.5 -2 1 1.5 2 -4 2.5 Figure 3.5: 3-D Elliptic Curve for Equation y 2 = x3 –x For fields of various characteristics, the Weierstrass equation can be transformed and simplified into different forms by a linear change of variables. For example, the equations for fields of characteristic 6= 2, 3 and of characteristic 2. 43 [Characteristic 6= 2, 3] Let K be a field of characteristic 6= 2, 3, and let x3 + ax + b (where a, b ∈ K ) be a cubic polynomial with the condition that 4a3 + 27b2 6= 0 (this ensures that the polynomial has no multiple roots). An elliptic curve E over K is the set of points (x, y) with x, y ∈ K that satisfy the equation y 2 = x3 + ax + b and also the point at infinity that denoted by . [Characteristic 2] If K is a field of characteristic 2, then there are two types of elliptic curves namely, elliptic curve of zero j-invariant and elliptic curve of nonzero j-invariant An elliptic curve of zero j-invariant is the set of points satisfying y 2 + a3 y = x 3 + a4 x + a6 and the point at infinity . Where a3 , a4 , a6 ∈ Fq , a3 6= 0. Point at Infinity The line at infinity is the collection of points on the projective plane for which Z = 0. The point at infinity is the point of intersection where the y-axis and the line at infinity meet. More precisely, the point at infinity is (0, 1, 0) in the projective plane (the equivalence class with X = Z = 0). An elliptic curve E over a finite field K can be made into an abelian group by defining an additive operation on its points [38]. 3.3.1 Addition Operation of Elliptic Curve Given two points P, Q ∈ E(K) we define a third point P +Q so that E(K) forms an abelian group with addition operation. If P 6= Q, then the line connecting P and Q intersects E(K) in a uniquely determined point which we denote as R. If P = Q then the tangent of E(K) 44 at P gives rise to the point R. It is tempting to take R as P + Q, but it would not define a group structure since there is no neutral element in this case. Therefore, we find a point of intersection where E(K) meets the line connecting R and the point at infinity call this point P + Q. By joining , and to a point R on the affine part of E(K), we mean that a vertical line is drawn through R. A vertical line intersects E(K) at 3 points: (x, y), (x, –y) and . Hence, the point at infinity P +Q+R = serves as the additive identity element and or P + Q = –R, the inverse of R. Figure 3.1 illustrates these concepts on the elliptic curve y 2 = x3 –3x, plotted in the xy-plane. 2 3 Elliptic Curve for Equation y =x -x y2=x3-x 4 2 0 4 -2 2 0 -4 -2 -2 -1 0 1 -4 2 Figure 3.6: 3-D Region of Elliptic Curve for Equation y 2 = x3 –x For each of the three cases of elliptic curves described above, the algebraic formulas which represent P + Q are easily derived from the following geometric procedures: 45 2 3 Elliptic Curve for Equation y =x -x 2 3 y =x -x Line at Infinity 4 -R Q P 2 0 4 -2 2 0 -4 -2 -2 -1 0 1 -4 2 Figure 3.7: 3-D Region of Elliptic Curve for Equation y 2 = x3 –x For Addition Operation For the Addition Formula of y 2 = x3 + ax + b, the inverse of P = (x1 , y1 ) ∈ E is –P = (x1 , –y1 ). If Q = –P , then P + Q = (x3 , y3 ) where, x3 = λ2 –x1 –x2 y3 = λ(x1 –x3 )–y1 where λ= λ= y2 –y1 if P 6= Q x2 –x1 3x21 + a if P = Q 2y1 46 Figure 3.8: Elliptic Curve Addition Operation 3.3.2 Elliptic Curve Discrete Logarithm Problem Since an elliptic curve E is made into an abelian group by an additive operation, the exponentiation of a point on E actually refers to repeated addition. Therefore, the ith power of α ∈ E is ith multiple of α, i.e. β = αi = iα. The logarithm of β to the base α would be i, the inverse of exponentiation. In Discrete Logarithm Problem (DLP) for some group G, suppose α, β ∈ G, an integer x such that αx = β should be solved. Analogously, in the Elliptic Curve Discrete Logarithm Problem (ECDLP), an integer x such that xα = β given α, β ∈ E is solved. For the ECDLP over E(Fq ) to be intractible, it is important to select an appropriate E and q such that #E(Fq ) is divisible by a large prime (of more than 30 digits) or such that q is itself a large prime. The elliptic curve cryptosystems are dependent on the presumed intractibility of the ECDLP. It is believed that the ECDLP is more intractible than the DLP since some of the strongest algorithms for solving the DLP cannot be adapted to the ECDLP. 3.4 Elliptic Curve Cryptography Let E be an elliptic curve over the prime field Zp (p > 3) such that E contains a cyclic subgroup H in which the EDLP is intractible [39]. Zp, E(Zp ), and a base point P ∈ E (preferably a generator of E), are fixed and publicly known. Each user X chooses a random integer aX which will be his/her own secret key, then computes and publishes the point 47 aX P . Suppose Alice wishes to send a message M = (x1 , x2 ) ∈ Zp∗ × Zp∗ to Bob. Let aB denote Bobs secret key. Alice chooses a random integer k ∈ Z|H| and sends (y0 , y1 , y2 ) = (kP, c1 x1 (mod p), c2 x2 (mod p)) where (c1 , c2 ) = k(aB P ). To decrypt the ciphertext, Bob computes (y1 c–1 1 (mod p), y2 c–1 2 (mod p)) = (x1 , x2 ) where aB y0 = (c1 , c2 ). 3.5 Impact of Key Size in PKI Security For different cryptosystems there are different key size recommendations. These recommendations may be expected to be equivalent for a certain specified level of security in the sense that the computational effort or number of Mips Years for a successful attack is more or less the same for all cryptosystems. So, different cryptosystems offer more or less equivalent security from a computational point of view when the recommended key sizes are used as per guideline. RSA/El-Gamal ECC Arithmetic Operations 428 110 5.5 × 1017 512 119 1.7 × 1019 768 144 1.1 × 1023 1024 163 1.3 × 1026 2048 222 1.5 × 1035 Table 3.1: Key Size Equivalent Operations Comparison for Equivalent Security Levels 48 Key Size [in bits] Sieve memory Matrix Memory 332 24 Mbytes 128 Mbytes 428 64 Mbytes 2 Gbytes 512 160 Mbytes 20 Gbytes 1024 256 Gbytes 100 Gbytes Table 3.2: RAM Required for NFS Operation q, Key Length p πq MIPS Years 160 280 8.5 × 1011 186 293 7.0 × 1015 234 2117 1.2 × 1023 354 2177 1.3 × 1041 426 2213 9.2 × 1051 2 Table 3.3: MIPS years to solve a generic ECDLP using the parallel Pollard Method 3.6 Summary Today the security of the three primary used public-key systems is depending on the intractability of the integer factorization problem (IFP) for RSA cryptosystems, DLP for El-Gamal cryptosystems, and ECDLP for ECC. RSA was invented in the late 1970’s, and ECC and El-Gamal were invented during 1985. Argumants on the topic, How secure is RSA, El-Gamal or ECC, still have not result. So mathematicians and computer scientists just depend on the hard work and experience in trying to develop efficient algorithms for these three problems. At present, the best algorithms known for the IFP and DLP are far superior to the best algorithm known for the ECDLP. Which means that solving the ECDLP is still challenging for intruders. For this reason, one can use considerably smaller parameters for ECC than for RSA, while accomplishing the same level of security against 49 known attacks [12]. Another important issue is, IFP has been studied for almost centuries, on the other hand the ECDLP has only been studied for last 15 years. Works on factoring really originated in the late 1970s that was primarily motivated by the invention of RSA. On the other side, all of the work that has been done since the late 1970’s on the DLP is directly applicable to the ECDLP (such as the Pollard-rho algorithms, etc.). Under these penomenon both the IFP and the ECDLP have been seriously studied for around the same lengths of time. By considering all the above discussion and the information from Table: 3.3, 3.2, 3.1 focused in [12], conclusion can be drawn that the ECDLP is essentially harder than the IFP. So, ECC should be the optimized and probably the best PKI among the existing ones. 50 Chapter 4 Proposed Solution Security is an important topic for wireless networks. For providing a robust security solution public key cryptosystems should be used. Public key cryptosystems should be used for ensuring confidentiality, authentication, integrity and non repudiation. For providing all these features of security, we should design a hybrid framework on application layer. Security framework implementation on application layer should provide more flexibility to the users. Currently the most popular application layer based composite security framework is Pretty Good Privacy (PGP). PGP currently used for email security. PGP is not suitable for limited resource constrained networks because of its high computations. If PGP is optimized for limited resource constraint networks without sacrificing the security level, it should be the best security solution in MANET. In this chapter, a novel framework is discussed as our proposed solution namely Optimized Pretty Good Privacy (OPGP) Framework. Both the PGP and OPGP provide their authentication, integrity and non repudiation by using Digital Signature Algorithm (DSA). DSA is a new security tool developed by public key cryptography. At the beginning of this chapter brief description of DSA and how DSA works are discussed. Later limitations of existing PGP solution is focused. Finally, considering the limitations of PGP, how the proposed OPGP should enhance security and optimize the network traffic is discussed. 4.1 Pretty Good Privacy Framework PGP, the acronym of Pretty Good Privacy, is an established framework that ensures all the security primitives of a hybrid cryptosystem. It combines with the best features of both 51 Figure 4.1: PGP Encryption Operation symmetric and asymmetric key cryptography. PGP encryption uses a serial combination of hashing, symmetric key cryptography and finally, public key cryptography. PGP uses a session key or one-time-secret key for fast symmetric key encryption over the plaintext for ensuring confidentiality of data. Asymmetric key encryption is used once for ensuring authentication and again for confidentiality. A fast and reliable hashing algorithm is used for ensuring integrity issue of security. In recent versions of PGP, authentication, integrity and non repudiation is ensured by using Digital Signature Algorithm (DSA). From Figure 4.1, the complete PGP operation can be understood. First the sender creates a fixed length hash message digest from the variable length message. Later, creates 52 the digital signature by encrypting the hash digest with the private key of sender. After successful encryption, a digital signature file or .sig file is created that should be verified by the receiver to ensure authentication, non repudiation and integrity of data. Now, the message is encrypted with one time shared secret key for fast computation. The encrypted message and the digital signature file are joined together for ensuring compression. Finally, the document is encrypted with public key of the receiver and being sent to the receiver. Receiver performs the same tasks for encryption in reverse sequential order to get the original message. Although PGP provides a strong composite security, it has a high time complexity for using conventional public key cryptosystem. The high complexity of PGP increases jitter and delay, which degrades the good-put of the system. The time complexity for both 1 2 IFP and DLP are O(e1.923(log n) 3 (log log n) 3 ). So, the run-times of IFP and DLP are sub p exponential. On the other hand, the ECDLP occupies time complexity of O( πn ) by 2 using pollard rho algorithm. The run-times of ECDLP is fully exponential. From the Figure 4.2, the time complexity analysis clearly supports that, ECC is optimized based on number of computations among the existing public key cryptosystems. So, it should be a wise decision to implement ECC in PGP for limited resource constraint system like MANET. If proper optimization has been introduced in PGP, it should be the best security solution for wireless networks. 4.2 Optimized Pretty Good Privacy Framework Optimized Pretty Good Privacy Framework (OPGP) is the proposed solution to minimize computational cost and network traffic over PGP. It is currently using RSA-DSA for encryption. But El-Gamal and RSA both are not suitable for wireless networks due to their high computational complexity. Moreover, higher security should not be provided by increasing key length in RSA and El-Gamal for MANET. But ECDSA can provide same 53 Computational Complexity Analysis of different PKIs Number Field Sieve (NFS) 200 DLP ECDLP 150 100 50 0 100 150 200 250 300 350 400 450 500 Key Length Figure 4.2: Computational Complexity Analysis for ECDLP and DLP/IFP security level as RSA does with lower key sizes. In OPGP, for both DSA and encryption ECC has been used. 160-bit ECC can provide 1024-bit RSA equivalent security. And finally one most important feature has been added into OPGP namely lossless compression. Generally, PGP does not use any standardized compression techniques to optimize network traffic. For large network it is important to reduce the network traffic. Lossless data compression is a class of data compression algorithms that allows the exact original data to be reconstructed from the compressed data. There are many algorithms for lossless data compression. For OPGP implementation, one of the most popular Houffman’s coding based DEFLATE algorithm is used, based lossless data compression and decompression technique. From Figure 4.3, the complete OPGP operation can be understood. In PGP both the symmetric and asymmetric key cryptography has been used. The use of additional encryp- 54 Figure 4.3: OPGP Encryption Operation tion does not bring any additional security for PGP. Initially, symmetric key cryptography was used for faster computations than asymmetric key cryptography. If any alternative solutions can be found that can provide higher security than symmetric key cryptography with faster encryption and lower computations, it should be applied for enhancing security. ECC is such an alternative. In OPGP, ECC has been exchanged with symmetric key cryptography for encryption purposes. Initially, the sender encrypts the message with the public key of the receiver. The initial encryption should reduce some overhead that traditional late encryption in PGP. The sender then creates a fixed length hash message digest from the variable length ciphertext message. Sender then creates the digital signature by encrypting the hash digest with the private key of sender. After successful encryption, a 55 digital signature file or .sig file is created that should be verified by the receiver to ensure authentication, non repudiation and integrity of data. Now the digital signature file and the encrypted ciphertext is compressed together by using DEFLATE algorithm based lossless data compression technique [40]. The compressed file is then sends to the receiver. The compression technique reduces network traffic and lossless data compression technique ensures that no bit should be missing or corrupted while decompressing the compresed file. Receiver performs the same tasks for decompression and encryption in reverse sequential order to get the original message. 4.3 Summary In future versions of PGP, the developers are providing more concentrations over compression of documents, so that PGP should be utilized in dense networks. The major contributions of OPGP are optimizing network traffic by introducing compression technique, ensuring lossless compression for security, reducing computations by replacing ECC over RSA thus OPGP should be utilize over MANET. Finally, OPGP tried to open a new horizon in wireless security by implementing ECC and DEFLATE over PGP. Theoritically it proves that the performance should be increased for OPGP rather than PGP. Real world data and simulation results should be taken to strong the result of analytical comparison between OPGP and PGP. 56 Chapter 5 Performance Analysis Theoretically, ECC showed its improvement over RSA. But in real world where scalability is an important issue, ECC needs to prove its improvement over RSA. For analyzing the performance over a large distributed network we usually use network simulators. These simulators virtually create nodes and simulate them. The previous chapter explains a detailed description of the proposed ECC based composite framework OPGP. This chapter compares the performance of the proposed ECC and existing RSA method with respect to the parameters of the average throughput, average delay time and average jitter of the network. Before representing the results of the simulation, its environment and methodology are explained which was used to carry out the results. Later, the simulation result analysis based on the performance metrics are discussed. Finally, a comprehensive summary of the simulation result analysis is given. 5.1 Simulation Description In this section the detailed description about the simulator environment and how the environment variables are configured for analysis is given. 5.1.1 NS-2 Simulator NS-2 is a discrete event simulator targeted at networking research developed by University of Berkley. It provides substantial support both wired and wireless networks. It is an object-oriented simulator, written in C++ and provides a simulation interface through OTcl as dialect of Tcl. The user describes a network topology by writing OTcl scripts, and 57 then the main ns program simulates that topology with specified parameters such as nodes, links, protocols, traffic etc. For this purpose, the algorithms were implemented extending the base class Agent of NS-2. 5.1.2 Simulation Topography The network simulations carried out within an area of 1000×1000m2 Flat Grid topography. Both proposed and existing methods were measured in the same topography. The number of nodes was in between 10 and 50. There remains two mechanisms in NS-2 for defining topography structure. First one, by defining flat grid of desired dimensions and secondly, by including any dimension file from existing NS-2 Tcl file. Defining through flat grid, provides unlimited flexibility for creating new topography. On the other hand, including any dimension file restricted the modification and creation on topography structure. So, flat grid topography is used. 5.1.3 Queue Management In NS-2 Interface Queue holds the information of how many packets should be remained in the queue of each node in NS-2. The proposed and existing models do not rely upon data link layer, rather concentrated more on application layer. So, default value of Interface Queue size 50 is kept for simulation. 5.1.4 Routing Protocol To implement the existing and proposed algorithm, we preferred to use the same Routing Algorithm AODV. For MANET implementation in NS-2, four different ad hoc routing protocols currently exists. They are DSDV, DSR, TORA and AODV. In DSDV routing protocol, routing messages are only exchanged between neighbouring mobile nodes. A packet for which the route to its destination is not known, is cached while routing queries are sent out. DSR is required for future implementation of piggy-backed routing information 58 on data packets which would not flow through the routing agent. In TORA, when a node needs a route to a given destination it broadcasts a QUERY message containing the address of the destination for which it requires a route. This packet travels through the network until it reaches the destination or an intermediate node that has a route to the destination node. AODV is a combination of both DSR and DSDV protocols and it is the most optimized protocol used for MANET. 5.1.5 Mobility Patterns The Radio Propagation model was chosen as the mobility model for the simulation in accordance with TwoRayGround model. In NS-2 TwoRayGround is the default radio propagation model. A single line-of-sight path between two mobile nodes is seldom the only means of propagation. The TwoRayGround reflection model considers both the direct path and a ground reflection path. In TwoRayGround model, the shadowing fading factor is not considered. Therefore, for a unique distance d, a deterministic value Pr is considered. Usually, TwoRayGround uses Free Space model when d is less than the crossing distance. Another important utility of NS-2 is setdest, which was used to generate random mobility of the nodes. The nodes in NS-2 move randomly with a random direction with a constant speed 20ms–1 . Speed is a major factor for throughput and packet drop. If nodes move with different random speeds, throughput must be biased with high mobility nodes. So, constant speed has been chosen for each and every node. NS-2’s General Operation Direction (GOD) was used to store the total number of mobile nodes. At the start of the simulation, all the nodes are laid out randomly on the rectangular topography and start moving random destination at their own speed of movement. Whenever a node came across to the transmission range of another node, its start transmitting packet. 59 5.1.6 Transport Agent To implement the existing and proposed algorithm, UDP Transport Agent has been chosen. In wireless simulation, if any receiver node exits from the transmission range of sender while data transmission, TCP considers it as an occurence of congestion although congestion has not been occurred. So, for wireless simulation in NS-2, UDP should be chosen over TCP. A UDP agent accepts data in variable size chunks from an application, and segments the data if needed. In NS-2, UDP packets contain a monotonically increasing sequence number and an RTP timestamp. Although real UDP packets do not contain sequence numbers or timestamps, the sequence number in NS-2 does not incur any simulated overhead, and can be useful for tracefile analysis. 5.1.7 Traffic Model The same traffic model is used for both existing and proposed method. A source node selects its destination randomly and sends Constant Bit Rate (CBR) traffic through UDP with a rate of 10 Mbps. In real world wireless devices use same data rate for communication. The maximum size of each packet is set to 1024 bit. 5.1.8 Performance Metrics To evaluate the performance of the ECC with the existing RSA, three parameters were chosen. These parameters are, 1. Average Throughput of the Network 2. Average Delay Time of the Network 3. Average Jitter of the Network 60 5.2 Simulation Result This section describes the performance of the proposed method with comparing the existing method considering the performance metrics. The following subsections show the performance of the proposed and existing method. 5.2.1 Average Throughput Analysis Throughput is the ratio of number of packets received successfully by a node within a given period of time. Throughput of the network fluctuates with respect to time depends upon the size of the interface queue. When the queue size is full then packet drops starts and throughput decreases. Average throughput gives us a view of the network data communication. The higher throughput indicates the higher data transmission in the network. From the Figure 5.1: the simulation analysis of ECC and RSA with equivalent security strength is visualized. When the number of nodes is lower, for example 10, ECC improves the average throughput to 3% over RSA with equivalent security level. But dramatically ECC increases average throughput to 26% when number of nodes increased to 50. The average throughput curve of ECC increases exponentially than RSA because of the sub exponential behavior of computational complexity of RSA. 5.2.2 Average Delay Time Analysis Delay time is another important factor for optimizing a system. If delay time increases of a system that system should not be declared as optimized one in terms of delay. The delay time of the simulation fluctuates because of random positioning and movement of the nodes. The average delay time should provide a profound knowledge of time optimization of a system. From the Figure 5.2: the simulation analysis of ECC and RSA with equivalent security strength is visualized. When the number of nodes is lower, for example 10, ECC improves the average delay time to 7% over RSA with equivalent security level. But dramatically ECC increases average delay time to 37% when number of nodes increased to 61 Average Throughput Analysis for ECC-163 and RSA-1024 bit 750 Average Throughput in [kbps] 700 650 600 550 500 450 400 ECC-163 RSA-1024 350 10 15 20 25 30 35 40 45 50 Number of Nodes Figure 5.1: Average Throughput Analysis for ECC-163 and RSA-1024 bit 50. The average delay time curve of ECC decreases exponentially than RSA because of the sub exponential behavior of computational complexity of RSA. 5.2.3 Average Jitter Analysis Jitter is a vital factor for signal propagation. Jitter plays a major role in VoIP and cellular communication. If jitter is reduced then, quality of signal increases. So, for good-put jitter should be reduced. The jitter of the simulation fluctuates because of random positioning and movement of the nodes. The average jitter should provide a profound knowledge of good-put of the system. From the Figure 5.3: the simulation analysis of ECC and RSA with equivalent security strength is visualized. When the number of nodes is lower, for example 10, ECC improves the average jitter to 6% over RSA with equivalent security level. But dramatically ECC increases average throughput abruptly to 89% when number of nodes increased to 50. The average delay time curve of ECC decreases exponentially 62 Average Delay Time Analysis for ECC-163 and RSA-1024 bit 260 ECC-163 RSA-1024 240 Average Delay in [ms] 220 200 180 160 140 120 100 10 15 20 25 30 35 40 45 50 Number of Nodes Figure 5.2: Average Delay Time Analysis for ECC-163 and RSA-1024 bit than RSA because of the sub exponential behavior of computational complexity of RSA. 5.3 Summary In this chapter, first the simulation environment was explained. Next the performance evaluation result of the proposed model with the existing model were discussed. The observation from the analysis states that the proposed ECC based security framework perform 25% better performance than the existing RSA based method in term of the throughput. The delay time analysis shows ECC can upgrade performance up to 37% over RSA. The improvement of delay time analysis proves that ECC takes lower computations time and should be implemented in MANET rather than RSA, where resources are limited. Finally, the high improvement of ECC over RSA in jitter analysis proves that ECC not only optimized for MANET, but also suitable for cellular networks where jitter is an important factor. So, it concludes that ECC is not only the best, but most optimized security solution 63 Average Jitter Analysis for ECC 163 and RSA 1024 bit 40 ECC-163 RSA-1024 35 Average Jitter in [ms] 30 25 20 15 10 5 0 10 15 20 25 30 35 40 45 50 Number of Nodes Figure 5.3: Average Jitter Analysis for ECC-163 and RSA-1024 bit for low power consuming MANET. 64 Chapter 6 Conclusion In recent years, ECC has gained widespread exposure and acceptance, and has already been included in many security standards. But implementation of ECC is still challenging. Moreover, implementation over MANET, where resources are limited, are still challenging for researchers. This paper proposes a novel security architecture for MANET based on ECC. The analytical and simulation performance analysis showed that ECC is the most optimized security choice for MANET. This chapter describes the aim and achievements of this research and summarize the possible directions for the future research. 6.1 Problem Description MANET is often vulnerable to security attacks due to its features of open medium, dynamic changing topology, cooperative algorithms, lack of centralized management and often lack of a clear line of defense. All these have changed the landscape of network security. The traditional way of protecting networks with firewalls and encryption algorithms are no longer sufficient and effective. Secure encryption algorithms perform high computation complexities that do not effective for MANET. Search for new optimized architectures or mechanisms to protect MANET infrastructure and applications is creating scope for security researchers. 65 6.2 Result Discussion The simulation result showed that ECC is optimized for MANET over existing popular RSA cryptosystems on the basis of throughput, delay time and jitter. ECC improves average throughput up to 25%, delay time up to 37% and jitter up to 89% over RSA. The comprehensive improvement of ECC proves that ECC can provide enhanced security for resource constraint MANETs. Moreover, the high improvement of ECC over RSA on the basis of jitter, indicates that ECC can also be implemented for infrastructure based cellular networks, where jitter is a vital factor. 6.3 Future Works In this research, ECC system based on GF (2n ) is utilized for its simple field arithmetic and efficient scalar multiplication algorithms. Another two different coordinates, the affine coordinate and the projective coordinate can be used for the ECC where the curve is defined over GF (2n ). Affine coordinates and projective coordinates reduces the number of operations for addition and doubling [41]. So, ECC should be more optimized under these coordinates. In future we will implement our model over affine and projective coordinates. 66 References [1] Donald Welch and Scott Lathrop, Wireless Security Threat Taxonomy, IEEE Workshop on Information Assurance. 2003, pp. 76–83. [2] Yuguang Fang, Xiaoyan Zhu and Yanchao Zhang, Securing resource-constrained wireless ad hoc networks, IEEE Wireless Communications. 2009, Vol. 16, No. 2, pp. 24–30. [3] Li Gong, Enclaves: Enabling Secure Collaboration over the Internet, Sixth USENIX Security Symposium, Focusing on Applications of Cryptography. 1996, pp. 149–160. [4] Adi Shamir, How to share a secret, Communications of the ACM. 1979, Vol. 22, No. 11, pp. 612–613. [5] Blakley G. R., Safeguarding cryptographic keys, Proceedings of the National Computer Conference. 1979, Vol. 48, pp. 313–317. [6] C. A. Asmuth and J. Bloom, A modular approach to key safeguarding, IEEE Transactions on Information Theory. 1983, Vol. 29, No. 2, pp. 208–210. [7] Kamer Kaya and Ali Aydm Selcuk, A Verifiable Secret Sharing Scheme Based on the Chinese Remainder Theorem, Lecture Notes In Computer Science, Proceedings of the 9th International Conference on Cryptology in India: Progress in Cryptology. 2008, Vol. 5365, pp. 414–425. [8] Balachandran R.K., Ramamurthy B., Xukai Zou and Vinodchandran N.V., CRTDH: An Efficient Key Agreement Scheme for Secure Group Communications in Wireless Ad Hoc Networks, IEEE International Conference on Communications. 2005, Vol. 2, pp. 1123–1127. 67 [9] Marianne A. Azer, Sherif M. El-Kassas and Magdy S. El-Soudani, Threshold Cryptography and Authentication in Ad Hoc Networks Survey and Challenges, Second International Conference on Systems and Networks Communications. 2007, pp. 5–11. [10] Shichun Pang and Shufen Liu, An ECC based Vector Space Key Sharing Scheme, 1st International Symposium on Pervasive Computing and Applications. 2006, pp. 524– 527. [11] D. Hankerson,A. Menezes and S. Vanstone, Guide to Elliptic Curve Cryptography, Springer Verlag. 2004. [12] Kristin Lauter, The advantages of elliptic curve cryptography for wireless security, IEEE Wireless Communications. 2004, Vol. 11, No. 1, pp. 62–67. [13] Pasini Sylvain and Vaudenay Serge, SAS-based Authenticated Key Agreement, The 9th International Conference on Theory and Practice of Public Key Cryptography. 2006, Vol. 3958, pp. 395–409. [14] Clare McGrath, Ghazanfar Ali Safdar and Maiire McLoone, Novel Authenticated Key Management Framework for Ad Hoc Network Security, IEEE Irish Signals and Systems Conference, Dublin. 2006, pp. 185–190. [15] Pierre E. Abi-Char, Abdallah Mhamed and Bachar El-Hassan, A Secure Authenticated Key Agreement Protocol Based on Elliptic Curve Cryptography, Proceedings of the Third International Symposium on Information Assurance and Security. 2007, pp. 89–94. [16] Joonsang Baek, Reihaneh Safavi Naini, Willy Susilo and Jan Newmarch, A Survey of Identity-Based Cryptography, Proceedings of AUUG 2004 : Identification and Authentication Issues in Computing. 2004. 68 [17] A. Rex Macedo Arokiaraj and A. Shanmugam, ACS: An efficient address based cryptography scheme for Mobile ad hoc networks security, International Conference on Computer and Communication Engineering, 2008. 2008 pp. 52–56. [18] Wei Liu, Yanchao Zhang, Wenjing Lou and Yuguang Fang, Securing Mobile Ad Hoc Networks with Certificateless Public Keys, IEEE Transactions on Dependable and Secure Computing. 2006, Vol. 3, No. 4, pp. 386–399. [19] Mahalingam Ramkumar and Nasir D. Memon, An efficient key predistribution scheme for ad hoc network security, IEEE Journal on Selected Areas in Communications. 2005, Vol. 23, No. 3, pp. 611–621. [20] A. Khalili, J. Katz, and W. A. Arbaugh, Toward Secure Key Distribution in Truly Ad-Hoc Networks, IEEE Workshop on Security and Assurance in Ad-Hoc Networks in conjunction with the 2003 International Symposium on Applications and the Internet. 2003, pp. 342–346. [21] Mengbo Hou and Qiuliang Xu, Key Replicating Attack on Certificateless Authenticated Key Agreement Protocol, Asia-Pacific Conference on Information Processing. 2009, pp. 47–50. [22] Marco Carvalho, Security in Mobile Ad Hoc Networks, IEEE Security and Privacy. 2008, Vol. 6, No. 2, pp. 72–75. [23] PI Jian-yong, LIU Xin-song, WU Ai and LIU Dan, A Novel Cryptography for Ad Hoc Network Security, International Conference on Communications, Circuits and Systems Proceedings. 2006, Vol. 3, pp. 1448–1452. [24] Stefan Schiffner and Markulf Kohlweiss, Privacy Friendly SybilGuard, 2nd Benelux Workshop on Information and System Security (WISSec 2007). 2007. [25] Chris Piro, Clay Shields, and Brian Neil Levine, Detecting the Sybil Attack in Ad Hoc 69 Networks, Proceedings from IEEE/ACM International Conference on Security and Privacy in Communication Networks (SecureComm). 2006, pp. 1–11. [26] Nishiki Kenya, Sakata Masayuki and Tanaka Erika, Location-based Authentication and Access Control Mechanism for Ubiquitous Mobile Nodes, Joho Shori Gakkai Kenkyu Hokoku. 2004, Vol. 2004, No. 66, pp. 79–85. [27] Suen T. and Yasinsac A., Ad hoc network security: peer identification and authentication using signal properties, Proceedings from the Sixth Annual IEEE SMC Information Assurance Workshop. 2005, pp. 432–433. [28] Sheng-Ti Li and Xiong Wang, Ad hoc network security with geographical aids, IEEE International Conference on Networking, Sensing and Control. 2004, Vol. 1, pp. 474– 479. [29] Fernando Carlos Pereira, Joni da Silva Fraga and Ricardo Felipe Cust, Self-Adaptable and Intrusion Tolerant Certificate Authority for Mobile Ad Hoc Networks, 22nd International Conference on Advanced Information Networking and Applications. 2008, pp. 705–712. [30] Jun Luo, Hubaux J. P. and Eugster P. T., DICTATE: DIstributed CerTification Authority with probabilisTic frEshness for ad hoc networks, IEEE Transactions on Dependable and Secure Computing. 2005, Vol. 2, No. 4, pp. 311–323. [31] Ricardo Marin, Julio Vivero, Philipp Leitner, Andreas Neppach, Martin Zach, David Ortega,Bertrand Baesjou and Pablo Arozarena, Securing the Madeira Network Management System, International Conference on Software, Telecommunications and Computer Networks : Symposium on Mobile Wireless Networks. 2008. [32] Robert B. Ash, A Primer of Abstract Mathematics, The Mathematical Association of America. ISBN 0-88385-708-1 1998. 70 [33] John B. Fraleigh, A First Course in Abstract Algebra, Pearson Education. ISBN 97881-7758-900-9 2003. [34] Masayoshi Nagata, Theory of Commutative Fields, American Mathematical Society. ISBN 0-8218-4572-1 1998. [35] Rudolf Lidl, Harald Niederreiter, Introduction to Finite Fields and their Applications, Cambridge University Press. ISBN 0-521-46094-8 2002. [36] Dale Husemöller, Elliptic Curves, Springer Verlag. ISBN 0-387-95490-2 2002. [37] Taher El Gamal, A public key cryptosystem and a signature scheme based on discrete logarithms, In Proceedings of CRYPTO 84 on Advances in cryptology, Springer-Verlag New York. 1985, pp. 10–18. [38] Kimmo Järvinen and Jorma Skyttä, On Parallelization of High-Speed Processors for Elliptic Curve Cryptography, IEEE Transactions on VLSI Systems. 2008, Vol. 16, No. 9, pp. 1162–1175. [39] Alessandro Cilardo, Luigi Coppolino, Nicola Mazzocca, and Luigi Romano, Elliptic Curve Cryptography Engineering, Proceedings of the IEEE. 2006, Vol. 94, No. 2, pp. 395–406. [40] Zied Jaoua, Anissa Mokraoui Zergä and Pierre Duhamelnoh, Robust Transmission of HTML Files: Iterative Joint Source Channel Decoding of DEFLATE Codes, 16th European Signal Processing Conference. 2008. [41] Qingwei Li, Zhongfeng Wang and Xingcheng Liu, Fast Point Operation Architecture for Elliptic Curve Cryptography, Proceedings of the IEEE. 2008, pp. 184–188. 71