Implementation of Diffie Hellmann Key Exchange protocol using Vedic Mathematics
Diffie-Hellman key exchange (D-H) is a commonly existent cryptographic protocol that allows two parties having no prior knowledge about each other to jointly share a secret key over an insecure communications channel. This key is used to encipher the subsequent communications using a symmetric key cipher such as DES etc., Vedic mathematics is the name given to the ancient system of mathematics, which was rediscovered, from the Vedas between 1911 and 1918 by Sri Bharathi Krishna Tirthaji. The whole of Vedic mathematics is based on 16 sutras (word formulae) and manifests a unified structure of mathematics. In this paper, implementation of the prime number multiplication and power calculation are demonstrated using Vedic mathematics for generating the keys and exchange it via the communication channel.
Keywords - Key Exchange, vedic mathematics, symmetric key cipher, key generation
Diffie-Hellman establishes a shared secret that can be used for secret communications by exchanging data over a public network. Let m denote a prime number and x denote the primitive root mod m. Consider the following scenario where the two parties Alice and Bob want to share a secret key in an insecure communication channel.
The algorithm works as follows:
- Alice and Bob plan to use a prime number m=17 and base x=15
- Alice chooses a secret integer a=10, then sends Bob A=xa mod m A=1510 mod 17 = 4
- Bob chooses a secret integer b=7, then sends Alice B=xb mod m B = 157 mod 17 = 8
- Alice calculates s=Ba mod m 810 mod 17 = 13
- Bob calculates s=Ab mod m 47 mod 17 = 13
Both Alice and Bob have arrived at the same value, because xab and xba are equal mod m. It is to be noted that only a, b and xab = xba mod m are kept secret. All the other values - m, x, xa mod m, and xb mod m - are sent in the clear. Once Alice and Bob compute the shared secret they can use it as an encryption key, known only to them, for sending messages across the same open communications channel. Of course, much larger values of a, b, and m would be needed to make this example secure, since it is easy to try all the possible values of xab mod 23 . If m were a prime of at least 300 digits, and a and b were at least 100 digits long, then even the best algorithms known today could not find a given only x, m,xb mod m and xa mod m, even using all of mankind's computing power.
II. VEDIC MATHEMATICS
Vedic mathematics is the ancient Indian system of mathematics based on simple rules and principles with which any mathematical problem can be solved like arithmetic, algebra, geometry or calculus. The system is based on 16 Vedic sutras or aphorisms, which are actually word formulae describing natural ways of solving a whole range of mathematical problems. Vedic mathematics was rediscovered from the ancient Indian scriptures by Sri Bharati Krishna Tirthaji. All the leading manufacturers of microprocessors have developed their architectures to be suitable for conventional binary arithmetic methods. The need for faster processing speed is continuously driving major improvements in processor technologies, as well as the search for new algorithms. The Vedic mathematics approach is novel and a large amount of work has so far been done in understanding various methodologies (sutras). However, hardly any meaningful applications of Vedic algorithms have been thought of.
III. VEDIC METHOD OF EXPONENTIATION
Here we make use of the aphorism 'Anurupya Sutra'. Consider the hypothetical case where only the first ten natural numbers cubes are known. i.e from 1 to 10. With the help of an intelligent principle, we extend it to: 1. Cubes of higher numbers, 2. Higher powers of higher numbers.
IV. CUBES OF HIGHER NUMBERS
The algorithm for finding the cube of any number is as follows starting with 113 :
1. We compute (a+b)3 as a3 + 3a2b + 3ab2 + b3 . Leaving the extreme pure terms, the other terms can be split as 3a2b = a2b + 2a2b and 3ab2 = ab2 + 2ab2 . Hence we get the middle term co-efficients as 2 and 2 on unit splitting. This will be used in step 3 as the multiplication co-efficients of the middle terms.
2. Put down the cube of the first digit (that is the unit digit of the number) in a row of four figures in a geometric ratio in the exact proportion between them. The upper row actually denotes the following terms in order a3 a2b ab2 b3 , here a denotes tens digit and b denotes units digit.
3. The next step is to put under the second and third numbers, just two times the above said numbers themselves and hence we get
4. Add them up and that is all.
V. HIGHER POWERS OF HIGHER NUMBERS
The algorithm for finding higher powers of higher numbers can be stated as follows:
- For calculating the cube, we used the Binomial expansion of power 3. Similarly, to calculate the power n, n is decomposed into simpler powers, say upto 5.
- Then the smaller subunits are multiplied using vedic multiplication (discussed in the next section) based on the law of exponentiation to get back the original bigger result.
The divide and conquer strategy is used here.
VI. VEDIC METHOD OF MULTIPLICATION
The Vedic multiplication of two numbers namely 63 and 14 is depicted as shown below. The digits on the two sides of line are multiplied and the result is added in the previous carry. When more than one line is in the step, all the results are added with the previous carry and the process is thus continued. A unit place digit of addition result is one of the digits in the answer; this is derived from full multiplication, while the remaining digits act as a carry. If the numbers are having dissimilar number of digits, then the smaller number can be padded with 0'(s) in order to equate the number of digits.
VII. VEDIC IMPLEMENTATION OF DIFFIE-HELLMAN KEY EXCHANGE
As previously discussed, the schematic of Diffie-Hellman key exchange algorithm is as follows:
Fig 1 : Schematic of Diffie Hellman Key Exchange
Vedic methodology can be implemented here in the following places: 1. Computation of xi , 2. Combination of smaller exponents to get the bigger exponent . We take the same example as quoted in section I.
VIII. EXPERIMENTAL RESULTS AND SCOPE OF WORK
The current work can be regarded as an extension to the implementation of the Rivest Shamir Adleman (RSA) public key cryptography algorithm. Vedic mathematics ensures a faster way of mathematical computation that is involved in the key generation and key exchange procedures taking place between the two parties.
It can be easily observed from the above comparison table that Vedic mathematical multiplication process is very efficient. Implementation of Vedic multiplication will be more efficient in terms of its implementation using conventional multiplication process. If all those methods are effectively implemented in computers, it will reduce the computational speed drastically.
The following references have been used in this paper:
1. Jagadguru Swami Sri Bharati Krsna Tirthaji Maharaja," VEDIC MATHEMATICS" 1965 (various reprints). Paperback, 367 pages, A5 in size. ISBN 81 208 0163 6 (cloth) ISBN 82 208 0163 4 (paper).
2. S.K. Kapoor, "VEDIC MATHEMATICAL CONCEPTS OF SRI VISHNU SAHASTRANAMA STOTRAM " , 1988.
3. K. Williams,"DISCOVER VEDIC MATHEMATICS "1984, Comb bound, 180 pages, A4. ISBN 1 869932 01 3.
4. Stallings, William. " Cryptography and network security",
4. "ISSUES IN VEDIC MATHEMATICS", Proceedings of the National workshop on Vedic Mathematics 25-28 March 1988 at the University of Rajasthan, Jaipur. Paperback, 139 pages, A5 in size. ISBN 81 208 0944 0/p
5.Vedic Mathematics Teacher's Manual [Intermediate Level] (v. 2) Kenneth R. Williams
6. Vedic Mathematics Teacher's Manual, Vol. 3 Kenneth R. Williams
7. Thapliyal, Himanshu and M.B.Srinivas, " VLSI Implementation of RSA Encryption System using Ancient Indian Vedic Mathematics", Proceedings of conference on Vedic Mathematics, 2003
8. Nicholas A.P, K.R Williams, J. Pickles, " Application of Urdhava Sutra", Spiritual Study Group, Roorkee (India), 1984.