On Implementation of Elliptic Curve Cryptography and Self-Certified Public Key Cryptosystems in Wireless Mesh Networks
A B.Tech Project Report submitted in fulfilment of the requirements for the Degree of Bachelor of Technology Submitted by K Bharadwaj Sharma 07010219 M Krishna Chaitanya 07010228 Under the Guidance of Dr.Ratnajit Bhattacharjee

Department of Electronics and Electrical Engineering Indian Institute of Technology Guwahati Guwahati-781039, Assam

i

Candidate’s Declaration
I hereby declare that the work which is being reported in this thesis entitled “ On Implementation of Elliptic Curve Cryptography and self-certified public key cryptosystems in Wireless Mesh Networks “ in partial fulfilment of the requirements for the award of the Degree of Bachelor of Technology, submitted in the Department of Electronics and Communication Engineering, Indian Institute of Technology Guwahati, is a record of my own work carried out during my thesis work under the supervision of Dr.Ratnajit Bhattacharjee, Associate Professor, Department of EEE, IIT Guwahati. The matter entitled in this thesis has not been submitted elsewhere for the award of any other degree.

Place: Guwahati Date: 21st April, 2011 This is to certify that the above statement made by the candidate is correct to the best of my knowledge.

April,2011 IIT Guwahati

`

Supervisor: Dr. Ratnajit Bhattacharjee Associate Professor

Dept. of EEE IIT Guwahati

ii

ACKNOWLEDGEMENT
First and foremost, I would like to take this opportunity to express my deepest and sincere gratitude to my thesis supervisor, Dr. Ratnajit Bhattacharjee. I value the freedom he gave me to carry out research in the field of my interest and I sincerely thank him for that. His stimulating suggestions and encouragement helped me in the time of research and writing of this thesis. I am very much thankful to him for his continuos help and support during entire thesis. Finally, I would like to thank my parents, siblings and friends for their immense love and support during my entire student life.

iii

Abstract
We consider wireless mesh networks where the main challenge in design of these networks is their vulnerability to security attacks. As WMN has memory and computational constraints, the traditional schemes for achieving security are not applicable. This report discusses how Elliptic Curve Cryptography (ECC) can be used in providing security features in a Wireless Mesh Networks (WMN). WMN is an architecture which is becoming increasingly popular. It does not have the security features well developed as in WLAN. Since such mesh network contains a large number of wireless transceivers cryptographic protocols which can provide energy efficiency and small key size is a desirable feature. Recently ECC is being investigated as it promises these features. This report then discusses about an efficient Elliptic Curve Cryptography (ECC)based self-certified public key cryptosystem (ECCSCPKC) and why it is considered to be an efficient authentication and key agreement (AKA) scheme to provide fundamental user authentication and transmission confidentiality services in a Wireless Mesh Network. ECCSCPKC is constructed based on elliptic curve cryptosystems (ECC) and the ID-based self-certified public key cryptosystems. It also discusses about related security schemes constructed using proposed ECCSCPKC: the Identification scheme, the session key exchange scheme, the encryption-decryption scheme, the digital signature scheme and the authenticated encryption scheme.

iv

Contents
Abstract ………………………………………………………………………………………………… iv List of figures ………………………………………………………………………………………… 1 List of Tables …………………………………………………………………………………………. 2 1. Introduction ………………………………………………………………………………….. 1.1 Background…………………………………………………………………………… 1.2 Thesis Objective……………………………………………………………………. 1.3 Literature Review…………………………………………………………………. 3 3 6 7

2.

Elliptic Curve Cryptography …………………………………………………………… 2.1 Background…………………………………………………………………………… 2.2 Operations on Elliptic Curves ……………………………………………….. 2.2.1 Point Addition ……………………………………………………………………. 2.2.2 Point Multiplication ……………………………………………………………. 2.3 Elliptic Curve Discrete Logarithm Problem …………………………..

8 8 9 9 9 9

3.

Elliptic Curves ………………………………………………………………………………. 3.1 Elliptic Curves over finite field …………………………………………….. 3.2 Elliptic Curves over prime field ……………………………………………. 3.3 Domain parameters of elliptic curves ………………………………….

11 11 11 12

4.

Benefits of Elliptic Curve Cryptography ……………………………………… 13

v

5.

ECC based schemes ……………………………………………………………………….. 5.1 Elliptic Curve Encryption and Decryption Scheme …………………. 5.2 Elliptic Curve Key Agreement Scheme …………………………………… 5.3 Results and Analysis ………………………………………………………………

15 15 16 16

6.

Elliptic Curve Cryptography – based Self – Certified Public key Cryptosystem (ECCSCPKC) ……………………………………………………………………………………... 21 6.1 Background …………………………………………………………………………….. 21 6.2 Proposed scheme of ECCSCPKC ……………………………………………….. 22

7.

ECCSCPKC based schemes …………………………………………………………………. 7.1 The Identification scheme ……………………………………………………….. 7.2 The session key exchange scheme …………………………………………… 7.2.1 Time-invariant session key exchange ……………………………………. 7.2.2 Time-variant session key exchange ………………………………………. 7.3 The Encryption-Decryption scheme ………………………………………… 7.3.1 Encryption ……………………………………………………………………………. 7.3.2 Decryption …………………………………………………………………………… 7.4 The Digital signature scheme …………………………………………………. 7.4.1 Signature generation …………………………………………………………… 7.4.2 Signature verification ………………………………………………………….

24 24 25 25 25 26 26 26 27 27 27

8.

Analysis of ECCSCPKC …………………………………………………………………….. 8.1 Benefits …………………………………………………………………………………. 8.2 Security features ……………………………………………………………………. 8.2.1 Security of secret keys …………………………………………………………. 8.2.2 Security against active attacks ……………………………………………… 8.2.3 Security of related security schemes ……………………………………. 8.3 Results of the proposed schemes …………………………………………… vi

28 28 28 29 29 30 31

9.

Conclusion and Discussion ……………………………………………………………… 37

Bibliography ……………………………………………………………………………………………. 38

vii

List of figures
1.1 A typical WMN architecture…………………………………………………………………….. 4

2.3 Elliptic Curve showing the operation P + Q = R …………………………………………. 10

5.3 Elliptic group…………………………………………………………………………………………….. 17 5.3 Encryption of a message using elliptic curve …………………………………………….. 18 5.3 Decryption of an encrypted message ……………………………………………………….. 19 5.3 Key Agreement between two users for a shared secret key ……………………… 20

8.3 User registration scheme …………………………………………………………………………. 32 8.3 Identification scheme ………………………………………………………………………………. 33 8.3 Session key exchange scheme …………………………………………………………………. 34 8.3 Encryption/Decryption scheme ……………………………………………………………….. 35 8.3 Digital Signature scheme …………………………………………………………………………. 36

1

List of Tables
Table 1. Comparison of strength of RSA and ECC …………………………………………… 14

2

Chapter 1 Introduction
1.1 Background
Wireless Mesh Network (WMN) is a new wireless networking paradigm. WMN is a promising technology for numerous applications such as broadband home networking, community networks. This technology allows a fast, easy and inexpensive network deployment. It is characterized by dynamic self-organization, self-configuration and self-healing to enable flexible integration, quick deployment, easy maintenance, low costs, high scalability, and reliable services [8]. WMN is a wireless co-operative communication infrastructure between large amounts of individual wireless transceivers .The infrastructure is decentralized, as each node need only transmit as far as the next node. Nodes act as repeaters to transmit data from nearby nodes to nodes that are too far away to reach, resulting in a network that can span large distances. Typical wireless mesh networks consist of mesh routers and mesh clients. Mesh routers, which are static and power-enabled, forms a wireless backbone of the WMNs. Mesh clients access the network through mesh routers. They can also directly mesh with each other. The main constraints in mesh clients are large computations on nodes are slow, as computing power of the processor is small and total energy resource is very limited and it is not desirable for large computations and transmissions. The main challenge in design of these networks is their vulnerability to security attacks [4]. Their security is easily compromised due to the distributed network architecture, the vulnerability of channels and nodes in the shared wireless medium, and the dynamic change of network topology. As WMN has memory and computational constraints, the traditional schemes for achieving security are not applicable. However, Elliptic Curve Cryptography[11] provides energy and 3

computation efficient techniques in implementing cryptographic algorithm, which can be suitable for mesh clients. WMN infrastructure consists of mesh routers and mesh clients, where mesh routers have minimal mobility and form the backbone of WMN. Fig. shows most a typical architecture of WMN in a community network.

There are many security issues, challenges and requirements of WMNs.The issues of user authentication,acces control as well as transmission confidentiality are extremely fundamental in security.The authentication and key agreement between two entities is the crucial issue. Public key cryptosystems are vulnerable to active attacks,such as attempts to modify a genuine public key by a fake one during key distribution.The most widely adopted solution to this is for a cerification authority(CA) to provide authenticated public keys.The certificate-based approach requires an extra public key issued by cerification authority (CA) after user registration.In this approach,anyone that wants to use a public key for certain subsequent cryptographic application(e.g, key exchange) should independently perform public key verification and subsequent cryptographic application through two separate steps.Another approach to generate authenticated public keys is known as the ID-based public key cryptosystem.This approach employs the user’s identity as his/her public key and hence need no extra public key certificate and 4

no verification of signatures which can reduce amount of storage,communication and computation.Although ID-based approach effectively solves the problem of public key verification for practical usage,its security disadvantage is that CA knows all user’s secret keys after user registration.Therefore,the CA my have the opportunity to masquerade as any legitimate user by generating a valid publickey/secret-key pair for the user without being detected. To resolve the problem of public key verification,a self-certified public key system was proposed in [22].A self-certified public key system has three features: First, the secret key can be determined by the user himself/herself or together by the user and CA, and does not be known to CA. Second,the user can use his/her own secret key to verify the authenticity of the self-certified public key issued by CA, and thus no extra certificate is required.Third, the task of public key verification can be further accomplished with subsequent cryptographic application in a logically single step. Therefore, public key verification of the self-certified approach earns more efficiency in saving the communicational cost and the computational effort as compared to that of the certificate-based approaches. The implemented ECCSCPKC is constructed based on the elliptic curve cryptosystems (ECC) and the ID-based self-certified public key cryptosystems.ECCSCPKC and its related security schemes can gain much efficiency in saving both the communicational cost and the computational effort via simplifying the public key distribution.Also,the cost of system maintanence can be greatly reduced without the need of managing the key directory.Therefore,it is quite suitable for the devices with inadequate memory space,limited computing power and low bandwidth which are features of wireless mesh networks. In this report, we discuss about ECCSCPKC to construct WMN security infrastructure.The implemented scheme is efficient in both communication and computation, resistant to some common attacks (e.g., impersonation and replay), as well as easy to maintain. Then, we discuss about related security schemes constructed using implemented ECCSCPKC: the Identification scheme, the session 5

key exchange scheme, the encryption-decryption scheme, the digital signature scheme and the authenticated encryption scheme.

1.2 Thesis Objective
The main objective of this thesis is to study and analyse how Elliptic Curve Cryptography (ECC) can be used in providing energy and computation efficient techniques in implementing cryptographic algorithms, which can be suitable for wireless mesh networks and implement various security schemes based on ECC. With this in mind, this thesis investigates the following:

i. Compare and analyse the advantages of elliptic curve cryptography compared to other cryptographic schemes. Here we have considered key sizes of various cryptographic schemes for same security strength. ii. Investigate the benefits of elliptic curve cryptography in memory and computationally constrained environments. Here, the key sizes are considered to be of equivalent strength based on Million Instructions per second (MIPS) years needed to recover one key. iii. Implement basic encryption-decryption algorithm and key agreement schemes using Elliptic Curve Cryptography. The security of these schemes depend on the difficulty of elliptic curve discrete logarithm problem(ECDLP). iv. Construct and implement several security schemes using ECC-based selfcertified public key cryptosystems. It is ID-based self-certified public key distribution.

6

1.3 Literature Review
The vulnerability to security attacks has been the main challenge for wireless mesh networks. As WMN has memory and computational constraints, the traditional schemes for achieving security are not applicable. However, Elliptic Curve Cryptography [11] provides energy and computation efficient techniques in implementing cryptographic algorithms. Dr. R.Shanmugalakshmi and M.Prabu [3] have discussed about the comparison between ECC and other cryptography algorithms. ECC is a kind of public key cryptosystem. But it differs in its quicker evolving capacity and by providing attractive and alternative way to researchers of cryptographic algorithm. The security level which is given by others, can be provided even by smaller keys of ECC. Zia Xiangya , Wang Chao [12] have analysed on elliptic curve discrete logarithm problem , on which the security of ECC depends.The main operation involved in ECC is point multiplication and it is computationally infeasible to obtain the scalar Involved between two points. Shamir[20] proposed ID-based public key cryptosystems. In this approach employs the user’s identity as his/her public key, and hence needs no extra public key certificate which can reduce the amount of storage, communication and computation. But its security disadvantage is that certification authority(CA) knows all users secret keys after user registration. In 1991, Girault [21] proposed a self-certified public key system to resolve the problem of public key verification. In this the secret key can be determined by the user himself/herself and does not be known to CA. The user can use his/her own secret key to verify the authenticity of the self-certified public key issued by CA.

7

Chapter 2 Elliptic Curve Cryptography
2.1 Background
Elliptic Curve Cryptography is an approach to public-key cryptography, based on elliptic curves over finite fields. The technique was first proposed individually by Neal Koblitz and Victor Miller in 1985. It differs from RSA in its quicker evolving capacity and by providing attractive and alternative way to researchers of cryptographic algorithm. The security level which is given by RSA, can be provided even by smaller keys of ECC. For example, the 1024 bit security strength of a RSA could be offered by 163 bit security strength of ECC [3].The ECC is based on the Elliptic Curve Discrete Logarithm problem. An elliptic curve is defined by:

Where ‘a’ and ‘b’ take real values. The mathematical operations of ECC is defined over the elliptic curve (1), with 4a3 + 27b2 ≠ 0. Each value of the ‘a’ and ‘b’ gives a different elliptic curve. All points (x, y) which satisfies the above equation plus a point at infinity lies on the elliptic curve. The public key is a point in the curve and the private key is a random number. The public key is obtained by multiplying the private key with the generator point G in the curve. The generator point G, the curve parameters ‘a’ and ‘b’, together with few more constants constitutes the domain parameter of ECC.

y 2 = x 3 + ax + b

(1)

8

2.2 Operations on Elliptic Curves
The addition and multiplication operations on elliptic curves are performed geometrically in a different manner than the arithmetic addition and multiplication operations. 2.2.1 Point Addition If P(XP,YP) and Q(XQ,YQ) are points on the elliptic curve and if - XP ≠ XQ (equally P ≠-Q), then, R(XR, YR) = P+ Q can be defined geometrically. In the case P ≠Q, a line intersecting the curve at the points P and Q must also intersect the curve at a third point -R, and R(XR, YR) is the answer, if P=Q (point doubling),the tangent line is used. X R = s2 - X P - XQ YR = -YP + s(XP - XR) s is the slope of the line through P and Q. (2) (3)

(4) XR = s2 – 2XP YR = -YP + s(XP - XR) (5) 2 And s is the tangent on the point P i.e., s = (3XP + a) / (2YP ) for the case where P=Q. 2.2.2 Point Multiplication A point P on the elliptic curve is multiplied with a scalar k using elliptic curve equation to obtain another point Q on the same elliptic curve by repeated addition.

Q= kP= P+P+....+P. (k times addition)[14]

2.3 Elliptic Curve Discrete Logarithm Problem
The security of ECC depends on the difficulty of Elliptic Curve Discrete Logarithm Problem. Let P and Q be two points on an elliptic curve such that kP = Q, where k is a scalar. Given P and Q, it is computationally infeasible to obtain k, if k is sufficiently large. k is the discrete logarithm of Q to the base P. 9

Hence the main operation involved in ECC is point multiplication i.e. multiplication of a scalar k with any point P on the curve to obtain another point Q on the curve[12][13].

Figure 2: Elliptic curve showing the operation P+Q = R

10

Chapter 3 Elliptic Curves
3.1 Elliptic Curves over Finite fields
The elliptic curve [2] operations defined above are on real numbers. Operations over the real numbers are slow and inaccurate due to round-off error. Cryptographic operations need to be faster and accurate. To make operations on elliptic curve accurate and more efficient, the curve cryptography is defined over finite fields. • Prime field ������������������������ and • Binary field F2������������ The field is chosen with finitely large number of points suited for cryptographic operations. The operations in these sections are defined on affine coordinate system. Affine coordinate system is the normal coordinate system that we are familiar with in which each point in the coordinate system is represented by the vector (x, y). An elliptic group over the Prime Field[1] Ep(a, b) is obtained by computing ������������ 2 mod p = x 3 + ax + b mod p for 0 ≤ x < p. The constants a and b are non negative integers smaller than the prime number p and must satisfy the condition: 4a3 + 27b2 mod p ≠ 0. Here the elements of the finite field are integers between 0 and p – 1. The prime number p is chosen such that there is finitely large number of points on the elliptic curve to make the cryptosystem secure. The graph for this elliptic curve equation is not a smooth curve. Hence the geometrical explanation of point 11

3.2 Elliptic Curves on Prime Field Fp

addition and doubling as in real numbers will not work here. However, the algebraic rules for point addition and point doubling can be adapted for elliptic curves over Fp. For each value of x, one needs to determine whether or not in it a quadratic residue. If it is the case, then there are two values in the elliptic group. If not, then the point is not in the elliptic group Ep(a, b). For addition to be well defined for any two points, we need to include an extra zero point 0, which does not satisfy the elliptic curve equation. 0 is taken to be a point of the curve. The order of the curve is the number of distinct points on the curve, including the zero point .

3.3 Domain parameters for EC over Prime field Fp
The domain parameters[2] for Elliptic curve over Fp are p, a, b, G and n. p is the prime number defined for finite field Fp. a and b are the parameters defining the curve y 2 mod p= x 3 + ax + b mod p. G is the generator point (xG , yG ), a point on the elliptic curve chosen for cryptographic operations. n is the order of the elliptic curve. The scalar for point multiplication is chosen as a number between 0 and n – 1[1].

12

Chapter 4 Benefits of ECC
ECC has same security strength as other cryptographic schemes for a smaller key size. The benefits of this higher-strength per-bit are • Higher speeds • Lower power consumption • Bandwidth savings • Storage efficiencies and • Smaller Certificates The result is that ECC is especially well suited for constrained environments. ECC’s inverse operation gets harder, faster[10] against increasing key length than do the inverse operations in Diffie-Hellman and RSA. Moreover as security requirements increase, ECC can be implemented with much smaller key size compared to other cryptographic schemes. The advantage ECC has over RSA is that the basic operation in ECC is point addition, which is known to be computationally very expensive. This is one of the reasons why it is very unlikely that a general sub-exponential attack on ECC will be discovered. On the other hand, RSA already has a known sub-exponential attack which works in general [5]. Table below compares the key sizes needed for equivalent strength security in ECC with RSA. Given the best known algorithms to factor integers for RSA and compute elliptic curve logarithms for ECC, the key sizes are considered to be of equivalent strength based on Million Instructions per second(MIPS) years needed to recover one key. It can be observed that as the requirement of security strength increases ECC key size becomes much smaller compared to RSA.

13

Time to break in RSA key ECC key RSA/ECC key MIPS years size size size 104 512 106 5:1 1020 1078 1011 108 768 132 6:1 1024 2048 21000 160 210 600 7:1 10 : 1 35 : 1

Source: NIST Guidelines for Public Key Sizes with Equivalent Security Levels

Table 1: Comparision of strength of RSA and ECC

Security is not the only attractive feature of elliptic curve cryptography. Elliptic curve cryptosystems also are more computationally efficient than the RSA and Diffie-Hellman. Although elliptic curve arithmetic is slightly more complex per bit than either RSA or DH arithmetic, the added strength per bit more than makes up for any extra compute time. Closely related to the key size of different public key systems is the channel overhead required to perform key exchanges and digital signatures on a communication link. The key sizes for public key in Table (above) is also roughly the number of bits that need to be transmitted each way over a communications channel for a key exchange. In channel-constrained environments, elliptic curves offer a much better solution Diffie-Hellman and RSA [9].

14

Chapter 5 ECC based Schemes - Algorithms
We have implemented encryption-decryption and key agreement schemes using Elliptic Curve Cryptography. These schemes have been implemented using the following algorithms.

5.1 Elliptic Curve Encryption and Decryption Algorithm
Elliptic curve cryptography can be used to encrypt plaintext messages, M, into cipher texts. The plaintext message M is encoded into a point PM form the finite set of points in the elliptic group, Ep(a, b). The first step consists in choosing a generator point, G ∈ Ep(a, b), such that the smallest value of n such that nG = O is a very large prime number. The elliptic group Ep(a, b) and the generator point G are made public. Each user selects a private key, nA < n and computes the public key PA as: PA = nA G. To encrypt the message point PM for Bob (B), Alice (A) choses a random integer k and compute the cipher text pair of points PC using Bob’s public key PB : PC = [(kG), (PM + kPB )] (6) After receiving the cipher text pair of points, PC , Bob multiplies the first point, (kG) with his private key, nB , and then adds the result to the second point in the cipher text pair of points, (PM + kPB ): (PM + kPB ) − [nB (kG)] = (PM + knB G) − [nB (kG)] = PM (7)

which is the plaintext point, corresponding to the plaintext message M. Only Bob, knowing the private key, nB , can remove , nB (kG) from the second point of the cipher text pair of point, i.e. (PM + kPB ), and hence retrieve the plaintext information PM [7]. 15

5.2 ECC key agreement Algorithm
It is a key agreement protocol that allows two parties to establish a shared secret key that can be used for private key algorithms. Both parties exchange some public information to each other. Using this public data and their own private data these parties calculate the shared secret. Any third party, who doesn’t have access to the private details of each device, will not be able to calculate the shared secret from the available public information. For generating a shared secret between A and B using ECDH, both have to agree up on Elliptic Curve domain parameters. Both end have a key pair consisting of a private key d and a public key Q = d * G (G is the generator point). Let (dA , Q A ) be the private key - public key pair of A and (dB , Q B ) be the private key - public key pair of B. • • • • The end A computes K = (xK , yK ) = dA * Q B . The end B computes L = (xL , yL ) = dB * Q A . Since dA Q B = dA dB G = dB dA G = dB Q A . Therefore K = L. Hence K is the shared secret key.

Since it is practically impossible to find the private key dA or dB from the public key K or L, it is not possible to obtain the shared secret for a third party[2].

5.3 Results and Analysis
The finite field generated for elliptic curve in (1) with a=1 and b=1 choosing the prime number p = 263.Points on the curve i.e., the group elements are given in the following figure.It can be noted that the size of elliptic curve is 259 which is the number of points in the elliptic group.

16

Fig.3 The field generated for elliptic curve in (1).

17

Fig.4 Encryption of a message using elliptic curve with above domain parameters

18

Fig.5 Decryption of the encrypted message

19

Fig.6 The key agreement between two users for generating a shared secret key using ECC.

20

Chapter 6 Elliptic Curve Cryptography-based selfcertified public key Cryptosystem (ECCSCPKC)
6.1 Background
In earlier sections, we have discussed ECCSCPKC scheme. In the current section and two subsequent sections, we discuss the implementation of such schemes. Minor modifications of the original proposal are also been made. Operational procedures of the implemented ECCSCPKC are divided in to two phases: system setup and user registration. At the system setup phase, certification authority(CA) defines system parameters and generates a secret/public key pair that will be used to generate self-certified public keys for the registering users dueing the registration phase, the registering user prepares an identitity information (example: username, IP address or other personal related information), randomly chooses a master key,and then submits the identity information and the master key (protected by a zero-knowledge proof) to CA for public key generation.The zero-knowledge proof (ZKP) can be easily established by an ECC function where computing elliptic curve discrete logarithm over finite field is computationally infeasible [15,16,17]. With the usage of a ZKP originated by the registering user, CA does not know the user’s master key during user registration and hence has no opportunity to masquerade as that user in later time.According to the submitted identity information and the protected master key,CA will return as elf-certified public key and a witness for the public key to the registering user.Thereafter,the registering user can use his/her master key to derive a secret key from the witness issued by CA.Meanwhile, he/she can use the derived secret key to verify the authenticity of the public key issued by CA.Here, the derived secret key and 21

the self-certified public key can be used as the decryption/encryption or the signature generation/verification key-pair in the subsequent cipher text generation or digital signature application.

6.2 Implemented scheme of ECCSCPKC
The system setup and user registration phases of the implemented ECCSCPKC[18] are described in detail in the following:

The system setup phase
CA defines system parameters as follows: (1) p: a field size,where p is typically either an odd prime or a power of 2 in general applications, and its length is about 160bits. (2) An elliptic curve E over Fp: E: y2= x3+ ax + b, where the two field elements a,b ϶ Fp and 4a3+27b2 ≠ 0(mod p), and all the points (x,y),x ϶ Fp, y ϶ Fp,on E form the set of E(Fp) containing a point O called the point at infinity. (3) B: a base point of order n over E(Fp),where n is a large prime (160bits) and the number of Fp-rational points on E denoted by #E(Fp), is divisible by n. (4) sSA: CA’s secret key, where sSA ϶ [2,n -2]. (5) PSA:CA’s public key, where PSA = sSA.B (“.” Means the multiplication of a number and an elliptic curve point). (6) h( ): a one-way hash function that accepts a variable length input and produces a fixed length output value j,where j ϶ [2, n - 2] and its length is 160bits. The one-way hash function h should satisfy the properties [10] that given h(x),it is computationally infeasible to find x1≠ x such that h(x1)= h(x), meanwhile , h(x1) ≠ h(x) if and only if x1≠ x . After that , CA publishes E, B, p, n, PSA and h,while keeping sSA secret.

The user registration phase
Suppose that a user Ui wants to register with CA.The procedure for user registration is stated below: Step1.Ui executes the following tasks: 22

(1.1)Select an identity information,denotedby Ii. (1.2)Randomly choose an integer xi ϶ [2, n -2] as the master key. (1.3)Compute (8) V i = h(xi||Ii). B. (1.4)Submit {Ii,Vi} to CA. Step2. CA executes the following tasks: (2.1)Randomly choose a time-variant integer ki ϶ [2, n - 2]. (2.2)Compute a public key Pi and its witness wi for Ui, where Pi = V i + ( ki – h( Ii ) . B = ( Pix , Piy ), wi = ki + sSA . ( Pi + h( Ii ) ) . (2.3) Return {Pi,wi} to Ui. Step3.Ui then executes thefollowing tasks: (3.1)Derive a secret key si as si = wi + h( xi ||Ii ) . (3.2) Verify the authenticity of Pi by testing if si . B = Pi + h ( Ii ) . B + [ ( Pix + h( Ii )) ] . PSA . (12) (11) (9) (10)

At the user registration stage ,the registering user uses a hashed-based ECC function,which acts as ZKP, to protect his/her master key xi during transmission. One may notice that different registering users mayc hoose the same xi as their master keys, however ,they donot evenknow that they possess the same master key. From eq. (11), it can be seen that the derived secret key si is cooperatively determined by Ui (contributing the master key xi) and CA (contributing the witness wi); however, CA does not know si during the user registration phase. The secret key si (derivedby Ui)and the public key Pi (issued by CA) satisfy Eq. (12).

23

Chapter 7 ECCSCPKC based schemes
7.1 The identification scheme
Alice proves to Bob her identity with the help of the identification scheme as follows: Step1. Alice sends toBob her identification information Ia and public key Pa. Step2. Bob computes Va = Pa + h( Ia ) . B + [ ( Pax + h( Ia ) ) ] . PSA . Step3. Alice randomly chooses an integer ra ϶ [2,n - 2] to compute T a = ra . B And then transmits Ta to Bob. Step4. Bob randomly chooses an integer x ϶ [2,n - 2], and returns it to Alice. Step5. Alice uses her secret key sa to compute ya = r a + s a . x and sends it to Bob. Step6. Bob verifies Alice’s identity by testing if ya . B -x . V a = T a 24 (16) (15) (14) (13)

If the correspondence holds, then Bob accepts the identity Alice claims; otherwise, he rejects her claim. The prover Alice can convince the verifier Bob of her identity by using Eq. (16).

7.2 The session key exchange schemes
The session key exchange schemes between Alice and Bob, including the timeinvariant and time-variant session key exchange.The time-invariant session key exchange means that the session key generated for each session is always unchanged; however, the time-variant one indicates that the session key generated for each session is always distinct. 7.2.1 Time-invariant session key exchange (1)Alice sends her identity information Ia and public key Pa to Bob. (2)Bob returns his identity information Ib and public key Pb to Alice. (3)Alice computes the session key(SK) shared with Bob as follows: (17) V b = Pb + h( Ib ) . B + [ Pax + h( Ia ) ] . PSA SK = sb . V a = ( sa sb ) . B (4)Bob computes the SK shared with Alice as follows: V a = Pa + h ( Ia ) . B + [ Pax + h( Ia ) ] . PSA SK = sb . Va = ( sb sa ) . B 7.2.2 Time-variant session key exchange (1)Alice randomly chooses an integer xa ϶ [2, n - 2] to compute Ta = x a . B , (21) and sends Ia,Pa and Ta to Bob. (2)Bob also randomly chooses an integer xb ϶ [2, n - 2]to compute Tb = x b . B , 25 (22) (19) (20) (18)

And returns Ib,Pb, and Tb to Alice. (3)Alice computes the session key (SK) shared with Bob as follows: V b = Pb + h( Ib ) . B + [ Pbx + h( Ib ) ] . PSA SK = xa . Vb + sa . T b = ( xa sb ) . B + ( sa xb ) . B (4)Bob computes the session key (SK) shared with Alice as follows: V a = Pa + h( Ia ) . B + [ Pax + h( Ia ) ] . PSA SK = xb . Va + sb . T a = ( xb sa ) . B + ( sb xa ) . B (25) (26) (23) (24)

7.3 The encryption/decryption scheme
The notations used in this scheme explained are: M : a message to be encrypted, Uj: encrypter, Ui: decrypter. 7.3.1 Encryption (1)Uj first transforms M in to a point (mx,my) on the Ellipticcurve E [4] (2)Uj randomly chooses an integer w ϶ [2,n - 2], and computes Vi, C1, and C2 as follows: (27) V i = Pi + h( Ii ) . B + [ Pix + h( Ii ) ] . PSA C1 = w . B (28) (29) C2 = M + w . V I (3) Uj transmits cipher text C1 and C2 to Ui 7.3.2 Decryption (1) Ui obtains cipher text C1 and C2 from a public channel (2) Ui computes the following to recover M: C2 - si . C1 = M + w . Vi- ( wsi ) . B = M + ( wsi ) . B- ( wsi ) . B = M

(30)

26

7.4 The digital signature scheme
The notations used in this scheme explained are: M : a message to be signed, Ua: signer, Ub: verifier. 7.4.1 Signature generation (1) Ua randomly chooses a time-variant integer k ϶ [2,n - 2], and computes (31) k .B = (Xa,Ya) (2) Ua computes r = Xa (32) (33) (3) Ua computes s = k + sa . h( M || r) (4) Ua transmits the signature (r, s) and M to Ub 7.4.2 Signature verification (1) Ub computes Va = Pa + h( Ia ) . B + [ Pax + h(Ia )] . PSA and s . B - Va . h( M || r ) = k . B + ( sa h( M || r ) ).B – ( sa .B ).h( M || r ) = k . B = ( x1 , y1 ) (2) If x1 = r holds, then the signature is valid.

(34) (35)

27

Chapter 8 Analysis of ECCSCPKC
8.1 Benefits of ECCSCPKC
ECCSCPKC possess the following advantages: 1. When verifying the validity of public key, it does not need to spend extra much time to verify the signature in the digital certificate used in the certificate-based public key cryptosystem. 2. Both distributing a session key and verifying the validity of public key can be concurrently achieved in a logically single step. 3. Verifying both a signature and the validity of public key can be concurrently accomplished in a logically single step. 4. Both decrypting a cipher correctly and verifying the validity of public key can be concurrently finished in a logically single step. 5. Since the implemented methods are combined with ID-based and ECC public key cryptosystems, they can reduce computation cost greatly. Thus, it reduces the cost of system maintenance as it does not need to manage key directory .It can gain much efficiency in saving both the communicational cost and computational effort, because they can simplify public key distribution.

8.2 Security Analysis
The security of the implemented ECCSCPKC and related security schemes is based on the following two well-known cryptographic assumptions: Elliptic curve discrete logarithm(ECDL) assumption which is stated in section 2.3. 28

One-way hash function (OWHF) assumption: Let h be a one-way hash function. Given h(M) ,it is computationally infeasible to find M [5].Furthermore, given M, h(M) and h(M’), it is computationally infeasible to obtain M’. For theoretical analysis, sometimes it is assumed that finding two different values M and M’ such that h(M)= h(M’) is computationally infeasible [19]. 8.2.1 Security of secret keys The secret keys used in the implemented ECCSCPKC include CA’s secret key, users master keys, and users derived(personal) secret keys. Revealing CA’s secret key. CA’s secret key sSA and the corresponding public key PSA, which are defined at the system setup phase, are only used for public key generation at the user registration phase. It is obvious that directly computing sSA from PSA is based on the intractability of solving the ECDL problem. At the user registration phase, sSA is protected by the time-variant parameter ki whose security is based on the intractability of solving the ECDL problem. Therefore, under the ECDL assumption, it is computationally infeasible to reveal sSA from all available public information. Revealing any registering user’s master key. As one can see that the registering user’s master key xi is protected by ZKP, whose security is based on the intractability of the ECDL and the OWHF problems .Even in the worst case that a user’s derived secret key si has compromised due tos ome unpredictable human factors, e.g., accidentally present to a unauthorized person, the user’s master key xi is still protected under the OWHF assumption. Revealing any registering user’s derived secret key. During the user registration phase, the registering user’s derived secret key si is protected by the master key xi that is protected under the OWHF and the ECDL assumptions as discussed above. 8.2.2 Security against active attacks Consider the scenario of an active attack that an adversary attempt to re-register his/her identity information already registered by an existing user with CA in such a way that CA will generate another validself-certified public key for the 29

masqueraded user. If this attack is successful, then the adversary can universally impersonate that user in the subsequent cryptographi capplications, since he/she possesses the corresponding secret key associated to there generated public key. This active attack can be easily detected or eliminated if a log file that stores all registered users identity is used. Each time a registering request is accepted, CA should check the submitted identity information with the entries in the log file to find out the re-registration attempt. Consider the scenario of another active attack that an adversary attempts to generate a pair of valid secret/publickey ( si’ , Pi’ ) for a non-existing user with a forged identity information Ii’ without the assistance of CA. In such a case, the secret/public key pair (si’ , Pi’ ) and the forged identity Ii’ should satisfy Eq. (5) otherwise, they cannot be applied to the subsequent cryptographic applications without being detected. However, inorder to plot this active attack successfully, adversary will face the intractability of solving the ECDL problem and reversing the adopted one-way hashfunction h. From the above discussions, it can be seen that under the ECDL and the OWHF assumptions, the implemented ECCSCPKC can effectively with stand the above active attacks that are originated either by re-registering any registered identity information or by creating a forged identity for any non-existinguser. 8.2.3 Security of related security schemes Secure identification scheme.As the prover Alice can convince the verifier Bob of her identity an adversary with the forged Ii’ and Pi’ cannot pass the verification procedure of the identification scheme implemented. Secure session key exchange. Although an attacker can get Pi and Ii from the public channel, he/she cannot derive each user’s secret key as discussed in section 8.2.1. Thus , he/she cannot also obtain the session key shared between any two users. Secure encryption/decryption scheme. If anattacker wants to derive message M from the cipher text C1 and C2,then he/she will encounter the intractability of solving the ECDL problem. Moreover, due to the fact that the integer w is randomly chosen in the encryption scheme each time, it is hard to compute 30

message M from the massively collected cipher text C1’s and C2’s. Secure digital signature scheme. Consider the scenario that an adversary attempts to reveal a user’s derived secret key si from an intercepted signature(r, s) generated by that user. It can be seen that one can solve the derived secret key si from s = k + si .h(M || r) (mod n) only if he/she knows the time-variant variable k in advance.However,the time-variant variable k is protected by the ECDL assumption Therefore, for a given message M, an adversary will face the intractability of solving the ECDL problem to forge a validsignature of M by the name of any user without knowing the user’s derived secret key. Secure authenticated encryption scheme. An adversary cannot get a user’s derived secret key si from an intercepted ciphertext (R, s) generated by that user,because he/she can solve si from s = w - si . Rx( mod n ) only if he/she obtains the variable w in advance. However, the variable w is also protected by the ECDL assumption.

8.3 Results and Discussion of the implemented schemes
These are the results achieved with the elliptic group used for ECC .It also shows clearly the debugging of the programs of each of the scheme steps wise. First, we present the user registration scheme.After both Alice and Bob registers, they need to identify each other.Thus, we present the identification scheme.After identifying each other, they exchange their session keys.After exchanging their session keys, Alice sends Bob an encrypted message and Bob decrypts back the message.We also implemented the Digital Signature Algorithm, which Alice uses to digitally sign his message.

31

Fig.7 The user registration scheme

32

Fig.8 Identification Scheme

33

Fig.9 Session Key exchange Scheme

34

Fig.10 Encryption/Decryption Scheme

35

Fig.11 Digital Signature Scheme

36

Chapter 9 Conclusion and Discussion
In this report, we have discussed about ECC and how it provides greater security and more efficient performance for a far smaller key size than other public key cryptographic techniques. We have implemented the encryption-decryption and key agreement schemes using Elliptic Curve Cryptography. Then, we have discussed the problem of public key verification in WMN ,and implemented a self-certified public key system based on ECC, ECCSCPKC[22]. Based on the results for simplifying public key distribution, the implemented ECCSCPKC and its related security schemes can gain much efficiency in saving both the communicational cost and the computational effort,so it is quite suitable to be used for the devices with inadequatememoryspace, limited computing power and low network bandwidth in wireless environments, like the smartcard, mobile phone, personal digital assistant(PDA), etc which are members of WMNs. Also, since the implemented ECCSCPKC does not need to manage the key directory, the cost of system maintenance can be greatly reduced. The security analysis discussed that the implemented ECCSCPKC can withstand potential active attacks and protect CA’s secret key, users master keys, and usersderived(personal) secret keys in effect.All of the implemented security schemes are secure enough, based on the intractability of the ECDL and the OWHF problems.

37

Bibliography
[1] Certicom , http://www.certicom.com/index.php?action=ecc_tutorial,home [2] M. S. Anoop, Elliptic Curve Cryptography - An Implementation Guide, January 2007.

[3] R. Shanmugalakshmi, and M.Prabu, “Research Issues on Elliptic Curve Cryptography and Its applications”, in IJCSNS. International Journal of Computer Science and Network Security,. VOL.9 No.6, June 2009 [4] M.S. Siddiqui and C. Seon, "Security Issues in Wireless Mesh Networks", in Proc. MUE, 2007, pp.717-722.. [5] Vivek Kapoor, Vivek Sonny Abraham and Ramesh Singh, “Elliptic Curve Cryptography”, ACM Ubiquity, Vol. 9, No. 20, May 2008. [6] Fuwen Liu, “A Tutorial on Elliptic Curve Cryptography(ECC)”. [7] V. Vijayalakshmi and Dr. T.G. Palanivelu, ”Secure Localization Using Elliptic Curve Cryptography in Wireless Sensor Networks”, IJCSNS International Journal of Computer Science and Network Security, VOL.8 No.6, June 2008. [8] Ian F. Akyildiz, Xudong Wang and Weilin Wang, “Wireless mesh networks: a survey“ Journal Computer Networks: The International Journal of Computer and Telecommunications Networking Volume 47 Issue 4, March, 2005. [9] National Security Agency, http://www.nsa.gov/business/programs/elliptic_curve.shtml . [10] Design & Reuse, cryptography.html. http://www.design-reuse.com/articles/7409/ecc-holds-key-to-next-gen-

[11] L. Batina, N. Mentens, K. Sakiyama, B. Preneel, and I. Verbauwhede, "Low-cost Elliptic Curve Cryptography for Wireless Sensor Networks" in 3rd European Workshop on Security and Privacy in Ad hoc and Sensor Networks, 2006. [12] Jia Xiangya, Wang Chao. “The Application of Elliptic Curve Cryptosystem in Wireless Communication”, 2005 IEEE International Symposium on Microwave, Antenna, Propagation and EMC Technologies for Wireless Communication, 2005. [13] Kristin Lauter, “The Advantage of Elliptic Curve Cryptography For Wireless Security”, IEEE Wireless Communications, Microsoft Corporation, 2004. [14] Darrel Hankerson, Julio Lopez Hernandez, Alfred Menezes, “Software Implementation of Elliptic Curve Cryptography over Binary Fields”, Proceedings of the Second International Workshop on Cryptographic Hardware and Embedded Systems, 2000.

38

[15]

A. Jurisic, A.J. Menezes, “Elliptic curves and cryptography”, Dr. Dobb_ s Journal (1997) 26–35. 48 (17) (1987) 203–

[16] N. Koblitz, “Elliptic curve cryptosystems”, Mathematics of Computation 209. [17]

J. Sliverman, “The Arithmetic of Elliptic Curves”, Springer-Verlag, New York, 1986.

[18] W. Tsaur, “Several Security Schemes Constructed Using ECC-Based Self Certified Public Key Cryptosystems,” Applied Mathematics and Computation, vol. 168, no. 1, pp. 447-464, 2005. [19] B. Schneier,” Applied Cryptography, second ed.”, John Wiley, New York, 1996.

[20] A. Shamir, “Identity-based cryptosystems and signature schemes, in: Advances in Cryptology”, Proceedings of CRYPTO_84LNCS, vol. 7, Springer-Verlag, New York, 1985, pp. 47–53. [21] M. Girault, “Self-certified public keys, in: Advances in Cryptology” Proceedings of EUROCRYPT 91LNCS, vol. 547, Springer-Verlag, New York, 1992, pp. 490–497.

[22] Woei-Jiunn Tsaur, “Several security schemes constructed using ECC-based self-certified public key cryptosystems” Applied Mathematics and Computation 168 (2005) 447–464

39