Mr.P.Kanagaraju et al Int. Journal of Engineering Research and Applications www.ijera.

com
ISSN : 2248-9622, Vol. 4, Issue 3( Version 1), March 2014, pp.117-121

RESEARCH ARTICLE OPEN ACCESS

Secure Cluster Based Routing Using SAT/ILP Techniques and

ECC EL-Gamal Threshold Cryptography in MANET
Mr. P. Kanagaraju. Me, (Ph. D)*, Dr. R. Nallusamy Ph.D.**, Nandini. D. K***
*Department of Computer Science, K.S.Rangasamy college of Technology, Thiruchengode
** Professor
***Department of Computer Science, K.S.Rangasamy college of Technology, Thiruchengode.

ABSTRACT
The Elliptic curve cryptography ( ECC) a promising and important because it requires less computing power,
bandwidth, and also the memory when comparing to other cryptosystems The clustering algorithm using the
Integer Linear Programming (ILP) and Boolean Satisfiability (SAT) solvers. These improvements will secure
the application of SAT and ILP techniques in modeling composite engineering problem that is the Clustering
Problem in Mobile Ad-Hoc Networks (MANETs). The Clustering Problem in MANETs consists of selecting the
most appropriate nodes of a given MANET topology as clusterheads, and ensuring that regular nodes are related
to clusterheads such that the lifetime of the network is maximized. In which, discussing SAT/ILP techniques for
clustering techniques and ECC El Gamal Threshold Cryptography for the security. Through our implementation,
explored the possibility of using ECCEG-TC in MANETs.
Keywords - Boolean Satisfiability, Elliptic curve cryptography, ECC El Gamal Threshold Cryptography
Integer Linear Programming.

I. INTRODUCTION problems. Mainly one of such problem is clustering

Mobile ad hoc networks (MANETs) are in Mobile Ad-Hoc Networks (MANETs).
vulnerable to various attacks including denial-of- Cryptography is transforming a information it into an
service attacks because of wireless nature of these unreadable format in which a message can be
networks. Devices with constraint resources add to its concealed from reader and only the intended recipient
vulnerability. To ensure availability of nodes, will be able to convert it into original text. Its main
threshold cryptography can be implemented in these goal is to keep the data secure from unauthorized
networks so that even if some of the information is access. Data can be read and understood without any
lost still the actual message reaches the intended special measures are known as plaintext. Hiding
receiver without compromising security in terms of information into the plaintext is called encryption.
secrecy, reliability, and genuineness. Encrypted plaintext information into an unreadable
Elliptic Curve Cryptography (ECC) was first garbage known as cipher-text. Reverting process of
proposed by victor Miller and independently by Neal cipher text to its original plaintext is called
Koblitz in the mid-1980s and has evolved into a decryption. A system provides encryption and
mature public-key cryptosystem. Distinguish to its decryption is called cryptosystems. Cryptography
conventional counterparts, ECC offers the same level provides number of security goals to ensure the
of security using security. privacy of data, on-alteration of data and so on.
Threshold cryptography achieves the Types of various goals of cryptography are below
security needs such as confidentiality and integrity
against malicious nodes. It also provides data Confidentiality
integrity and availability in a hostile environment and Maintaining a secret communication
can also employ verification of the correct data between the two authorized persons.
sharing. All this is achieved without revealing the
secret key. Thus, taking into consideration these Authentication
characteristics, implementing TC to secure messages Checking the identity of the information
seems a perfect solution in MANETs. from the legitimate or authentication ID.
For the past few decades, Integer Linear
Programming (ILP) and Boolean Satisfiability (SAT) Data Integrity
solvers have enhanced a lot through the beginning of Verifying the information that has not been
new intelligent algorithms that allowed the solvers to altered by unauthorized which means no one in
handle a wider range of difficult Engineering based between the sender and receiver are allowed to alter

www.ijera.com 117 | P a g e
Mr.P.Kanagaraju et al Int. Journal of Engineering Research and Applications www.ijera.com
ISSN : 2248-9622, Vol. 4, Issue 3( Version 1), March 2014, pp.117-121

the given message. The assumptions which were made above in

the ILP formulations are also valid to the proposed
Non Repudiation ILP formulation. Variable b, in the intention role,
Thus when a message is sent, the receiver which represents the level of the node’s capability to
can prove that the message was in fact send by the act as a cluster head, gets its value from an external
suspected sender. Correspondingly, when a message source (algorithm, tool, etc). This is useful as
is received, the sender can prove the suspected multiple approaches or algorithms, which decide the
receiver in fact received the message. suitability of a node in acting as a cluster head, can
be combined with this model without altering the
Access Control equations, even though this is out of the range of
Only the certified parties are able to right to research. Then it is unspecified that nodes are able to
use the given information resolve each other’s spot.
.
II. Integer Linear Programming And
Boolean Satisfiability
Integer Linear Programming (ILP) involves
maximizing or minimizing a function with respect to
certain constraints where the optimal function and
constraints are linear and the used variables can only
take integer values [2]. Cases where the integer
values are restricted to (0–1) are called Binary ILP
Problems. In SAT the constraints between variables
are represented using what is called propositional
logic. It involves the use of AND, OR and NOT
operations to construct formulas in the Products-of- Fig. 1 Star-ring backbone.
Sums form or Conjunctive Normal Form (CNF). The
variables can only take Binary values (0–1). Given Intra Cluster Communication Enhancement
constraints articulated in CNF, the ambition is to spot Intra Cluster communication is introduced
a variable obligation that will satisfy all constraints in for two issues. First is that the most important
the problem or verify that no such task exists. To accountability of the cluster head should be to route
assure or to solve, SAT will go all the way through communication among clusters and not inside a
the hunt space and conclude whether or not there is a cluster. The aim is for the cluster head to preserve as
fulfilling variable assignment. Superior decision much energy as achievable for the contact between
heuristics and clever inconsistency analysis clusters, allowing it to last longer in its position as a
techniques can be used to evade probing through the cluster head. The second cause after enhancing the
complete tree of 2n assignments. intra cluster contact is that should a cluster head fail,
It proposes an ILP formulation of the the nodes inside a cluster will be able to
clustering problem, structure on the ideas and communicate.
assumptions put forward in the EEC-CB model
presented in this model improves on weaknesses Multihop Connections Enhancement
present in the EEC-CB model and adds idleness Multihop connections are introduced into
through the use of a Star-Ring backbone. In addition, the formulation to permit longer, extra exclusive
a proposed enhancement allows coverage to be taken links to be replaced by shorter less costly links.
into account. relatively than attach straight to a cluster head which
is further away, it is preferable to make a lesser cost
Proposed Base Model link to a cluster head during another regular node.
Variables are maintained below as: Though, the in-between regular node will now, in a
− N: Total number of nodes in the network sense, act like a second tier cluster head as it will
(predetermined) route the communication of the regular node through
− P: Number of clusters heads (predetermined) it to the cluster head. Price of this routing must be
− di j : Euclidean distance between nodes i and j taken into explanation. After that objective function
− K : Max number of nodes that can be connected is used to integrate the cost of multihop connections
to a CH (predetermined) to the proposed Star-Ring base model.
− ci j : Cost of connecting a regular node i
to CH j (proportional to di2j) Coverage Enhancement
− h j k : Cost of connecting CH j to CH k The proposed Base Model can be extended
(proportional to d3jk ) to take into account the coverage radius of the nodes

www.ijera.com 118 | P a g e
Mr.P.Kanagaraju et al Int. Journal of Engineering Research and Applications www.ijera.com
ISSN : 2248-9622, Vol. 4, Issue 3( Version 1), March 2014, pp.117-121

in the system, and make sure that links are , 0 ≤ a ≤ p-1, defining the random polynomial
1 j
recognized only between nodes that are within each f(x) over Zp, a Galois prime field GF(p).
other’s exposure radius. Likewise the same manner in • We compute n shares, M = f(x ) mod p, 1≤ i ≤ n,
which the distances between nodes are used to i i

determine the price of the links, it can also be where x can be just the public index i for
i
compared to the exposure radius of each node and simplicity, and convert them to points P on
i
used to Sample MANET topology. elliptic curve E (a, b).
p

III. Ecc Elgamal Tc (Ecceg-Tc) • Alice picks a random number r, and sends rG
The ELGamal public-key encryption scheme and P + rK to Bob with index t.
i B
can be viewed as Diffie-Hellman key agreement • Bob recovers each elliptic curve point by
protocol in key transmit mode. Its protection is based calculating P + rK – n rG = P .
i B B i
on the intractability of the discrete Logarithm • Bob converts P to M , and deduces M by using
Problem (DLP) and the Diffie-Hell man problem. i i

EC-ELGamal protocol implemented for safe Lagrange interpolation formula M.

communication. One essential tip is to note is unlike
ECDH protocol, this protocol does not create ECCEG-TC Implementation
common key, but using EC-ELGamal protocol a ECCEG-TC,to select the ECC parameters,
message M=(M1,M2),a point on elliptic curve, can i.e. a, b, p, widely accepted NIST curves were
be sent from Bank to Alice and vice versa. selected for implementation for 192, 224, and 256
Performing the decrypting, reverse the bits. For conversion of message to and from ECC
embedding process to create the message M starting point, method discussed by Kobiltz is used such that
to the point P. It is not trivial to find a point M for the (kappa*M)mod p < x <(kappa*(M+1))mod p, where
communication. Communication that is difficulty in (x, y) is a point on elliptic curve. In our ECCEG-TC
8
obtaining the private key from the public key is based implementation, kappa is fixed to 2 . To retrieve a
on the discrete log problem (DLP) for elliptic curves. message from a ECC point (x, y), M= x/kappa mod p
is used.
The ELGamal digital signature scheme: For calculating the shares and for combining
The ELGamal signature algorithm is similar partial messages, Shamir’s Lagrange interpolation
to the encryption algorithm in that the public key and scheme is implemented. For its polynomial, the
private key have the same form; however, encryption coefficients are randomly generated over the modulus
is not the same as signature verification, nor is p. The co-efficient zero depends on the x and y values
decryption the same as signature creation as RSA. of ECC point information that needs to be transmitted
In following sections, our goal is to implement ECC based on ECC algorithm used. As against RSA
based ElGamal threshold cryptography (ECCEG- algorithm where we are sharing the keys, in ECC-TC
TC). In this algorithm, key is not shared because the implementation, the partial shares of the message are
public as well as private keys are in form of points generated and then encrypted to get ECC point.
and we cannot apply Lagrange on the points Cryptography is transforming a information it into an
altogether to split message or to combine it. Hence, unreadable format in which a message can be
ECCEG-TC for message splitting before encryption concealed from reader and only the intended recipient
is simulated for MANET environment and then it is will be able to convert it into original text. Its main
compared with performance of RSA-TC. The ECC El goal is to keep the data secure from unauthorized
Gamal Threshold cryptography (ECCEG-TC) access.
algorithm is briefly explained.
IV. Performance Results Performance
ECCEG-TC Message Split before Encryption Results
Algorithm
Suppose that the ECC has a point G on an
elliptic curve E (a, b), and the order of G is q. p is a
p
large prime.
Bob’s private key and public key are n , 0 < n < q,
B B
and K = n G.
B B
• First we choose a prime number p > max(M, n),
and define a = M, the message. Then we select k
0
- 1 random, independent coefficients a , a ,…a Fig. 2 Topology generated by the ILP formulation
1 2 k-
without coverage constraints.

www.ijera.com 119 | P a g e
Mr.P.Kanagaraju et al Int. Journal of Engineering Research and Applications www.ijera.com
ISSN : 2248-9622, Vol. 4, Issue 3( Version 1), March 2014, pp.117-121

results in proportional increase in the decryption

timings irrespective of n and t.

Fig. 3 Topology generated by the ILP formulation

with coverage constraints.

Fig.4 illustrates that with increase in ECC Fig. 6 Decryption and Combination Timings for
key size, the total encryption timings increase ECCEG-TC
gradually for given n and t. For constant key size and
n, the encryption timings increase with t as the time Number of point addition of ECCEG-TC
to generated Lagrange polynomial and respective increases with n resulting into proportionate increase
message shares increases accordingly. in addition timing in encryption and decryption as
seen in Fig. 4 and Fig. 6. The time required
converting message to point and vice-versa is
significantly small compared to encryption and share
generation time and hence not shown separately. In
ECCEG-TC, the Lagrange is carried over prime field
p, hence the success rate is 100% as all the partial
messages are recovered without any issue of inverse
calculation.

V. Conclusion
Fig. 4 Total Encryption Timings for ECCEG-TC An improved ILP formulation to solve the
clustering trouble in MANETs. The future model
Fig. 5 shows that the share generation offered the utilize of a Star-Ring backbone. In
timings increase with increase in key size or with n or addition, the planned formulation incorporated the
t. Share generation timings are very small compared ability to enforce coverage constraints to ensure that
to the encryption timings. only connections that are within the physical
limitations of the node are established. Applications
of MANETs are on rise and hence it is necessary to
provide security to this vulnerable wireless networks.
And by further exploring and implementing ECC
ELgamal threshold cryptography algorithms, its
shown that secure MANETs are feasible.

References
[1] S. Chinara and S. Rath, “Energy efficient
mobility adaptive distributed clustering
algorithm for mobile ad hoc network,” in
Fig. 5 Share Generation Timings for ECCEG-TC Proc. Int. Conf. Adv. Comput. Commun.,
2008, pp. 265–272.
Combination time is the time required to [2] A. Schrijver, Theory of Linear and Integer
combine t partial messages using Shamir’s Lagrange Programming.New York, NY, USA: Wiley,
interpolation method to retrieve original message. 1999.
From Fig. 6, the total decryption and combination [3] F. Aloul, A. Ramani, I. Markov, and K.
timings increase gradually with increase in t for Sakallah, “Generic ILP versus specialized 0-
constant key size and n. This increase is due to time 1 ILP: An update,” in Proc. Int. Conf.
required to decrypt and combine additional partial Comput.-Aided Design, 2002, pp. 450–457.
messages as t is increased. Increase in the key size [4] D. Chai and A. Kuehlmann, “A fast pseudo-

www.ijera.com 120 | P a g e
Mr.P.Kanagaraju et al Int. Journal of Engineering Research and Applications www.ijera.com
ISSN : 2248-9622, Vol. 4, Issue 3( Version 1), March 2014, pp.117-121

[5] Boolean constraint solver,” IEEE Trans. cryptography and other network security
Comput.-Aided Design Integr. Circuits Syst., algorithms for constrained environments”.
vol. 24, no. 3, pp.305–317, Mar. 2005. IEEE International Workshop on WWC-5,
[6] A. Sagahyroon, F. Aloul, and A. Sudnitson, 2009.
“Using SAT-based tech-niques in low [9] K. Lauter, “The advantages of Elliptic
power state assignment,” J. Circuits, Syst., Curve Cryptography For Wireless
Comput, vol. 20, no. 8, pp. 1605–1618, Security”, IEEE Wireless Communications,
2011. vol. 11, no. 1, Feb. 2004, pp. 62-67.
[7] Yufang Huang, “Algorihtm for elliptic [10] Y. Desmedt and Y. Frankel, “Threshold
curve diffie-Hellman key exchange based cryptosystems”, in Advances in Cryptology
on DNA title self assembly In Proceedings - Crypto '89, Proceedings, Lecture Notes in
of 46th IEEE Theories and Computer Science 435, G. Brassard, Ed.,
Applications,pp.31-36, 2008. Santa Barbara: Springer-Verlag,1990, pp.
[8] A. M. Fiskiran and R. B. Lee. “Workload 307-315.
characterization of elliptic curve

www.ijera.com 121 | P a g e