ns2 coding for the implementation of eliptic curve diffie hellman key exchange between nodes in manet

ns2 coding for the implementation of eliptic curve diffie hellman key exchange between nodes in manet

Abstract

Elliptic curve Diffie–Hellman (ECDH) is an anonymous key agreement protocol that allows two parties, each having an elliptic curve public–private key pair, to establish a shared secret over an insecure channel.[1][2][3] This shared secret may be directly used as a key, or to derive another key which can then be used to encrypt subsequent communications using a symmetric key cipher. It is a variant of the Diffie–Hellman protocol using elliptic curve cryptography.

In the previous posts, we have seen what an elliptic curve is and we have defined a group law in order to do some math with the points of elliptic curves. Then we have restricted elliptic curves to finite fields of integers modulo a prime. With this restriction, we have seen that the points of elliptic curves generate cyclic subgrups and we have introduced the terms base point, order and cofactor.

Finally, we have seen that scalar multiplication in finite fields is an "easy" problem, while the discrete logarithm problem seems to be "hard". Now we'll see how all of this applies to cryptography.

Domain parameters
Our elliptic curve algorithms will work in a cyclic subgroup of an elliptic curve over a finite field. Therefore, our algorithms will need the following parameters:

The prime p that specifies the size of the finite field.
The coefficients a and b of the elliptic curve equation.
The base point G that generates our subgroup.
The order n of the subgrouop.
The cofactor h of the subgroup.
In conclusion, the domain parameters for our algorithms are the sextuple (p,a,b,G,n,h).

Random curves

When I said that the discrete logarithm problem was "hard", I wasn't entirely right. There are some classes of elliptic curves that are particularly weak and allow the use of special purpose algorithms to solve the discrete logarithm problem efficiently. For example, all the curves that have p=hn (that is, the order of the finite field is equal to the order of the elliptic curve) are vulnerable to Smart's attack, which can be used to solve discrete logarithms in polynomial time on a classical computer.

Now, suppose that I give you the domain parameters of a curve. There's the possibility that I've discovered a new class of weak curves that nobody knows, and probably I have built a "fast" algorithm for computing discrete logarithms on the curve I gave you. How can I convince you of the contrary, i.e. that I'm not aware of any vulnerability? How can I assure you that the curve is "safe" (in the sense that it can't be used for special purpose attacks by me)?

In an attempt to solve this kind of problem, sometimes we have an additional domain parameter: the seed S. This is a random number used to generate the coefficients a and b, or the base point G, or both. These parameters are generated by computing the hash of the seed S. Hashes, as we know, are "easy" to compute, but "hard" to reverse.

Random curve generation
A simple sketch of how a random curve is generated from a seed: the hash of a random number is used to calculate different parameters of the curve.
Building a seed from a hash
If we wanted to cheat and try to construct a seed from the domain parameters, we would have to solve a "hard" problem: hash inversion.
A curve generated through a seed is said to be verifiably random. The principle of using hashes to generate parameters is known as "nothing up my sleeve", and is commonly used in cryptography.

This trick should give some sort of assurance that the curve has not been specially crafted to expose vulnerabilities known to the author. In fact, if I give you a curve together with a seed, it means I was not free to arbitrarily choose the parameters a and b, and you should be relatively sure that the curve cannot be used for special purpose attacks by me. The reason why I say "relatively" will be explained in the next post.

A standardized algorithm for generating and checking random curves is described in ANSI X9.62 and is based on SHA-1. If you are curious, you can read the algorithms for generating verifiable random curves on a specification by SECG (look for "Verifiably Random Curves and Base Point Generators").

I've created a tiny Python script that verifies all the random curves currently shipped with OpenSSL. I strongly recommend you to check it out!

Elliptic Curve Cryptography
It took us a long time, but finally here we are! Therefore, pure and simple:

The private key is a random integer d chosen from {1,…,n−1} (where n is the order of the subgroup).
The public key is the point H=dG (where G is the base point of the subgroup).
You see? If we know d and G (along with the other domain parameters), finding H is "easy". But if we know H and G, finding the private key d is "hard", because it requires us to solve the discrete logarithm problem.

Now we are going to describe two public-key algorithms based on that: ECDH (Elliptic curve Diffie-Hellman), which is used for encryption, and ECDSA (Elliptic Curve Digital Signature Algorithm), used for digital signing.

Encryption with ECDH

ECDH is a variant of the Diffie-Hellman algorithm for elliptic curves. It is actually a key-agreement protocol, more than an encryption algorithm. This basically means that ECDH defines (to some extent) how keys should be generated and exchanged between parties. How to actually encrypt data using such keys is up to us.

The problem it solves is the following: two parties (the usual Alice and Bob) want to exchange information securely, so that a third party (the Man In the Middle) may intercept them, but may not decode them. This is one of the principles behind TLS, just to give you an example.

Here's how it works:

First, Alice and Bob generate their own private and public keys. We have the private key dA and the public key HA=dAG for Alice, and the keys dB and HB=dBG for Bob. Note that both Alice and Bob are using the same domain parameters: the same base point G on the same elliptic curve on the same finite field.

Alice and Bob exchange their public keys HA and HB over an insecure channel. The Man In the Middle would intercept HA and HB, but won't be able to find out neither dA nor dB without solving the discrete logarithm problem.

Alice calculates S=dAHB (using her own private key and Bob's public key), and Bob calculates S=dBHA (using his own private key and Alice's public key). Note that S is the same for both Alice and Bob, in fact:
S=dAHB=dA(dBG)=dB(dAG)=dBHA
The Man In the Middle, however, only knows HA and HB (together with the other domain parameters) and would not be able to find out the shared secret S. This is known as the Diffie-Hellman problem, which can be stated as follows:

Given three points P, aP and bP, what is the result of abP?
Or, equivalently:

Given three integers k, kx and ky, what is the result of kxy?
(The latter form is used in the original Diffie-Hellman algorithm, based on modular arithmetic.)