"A High Speed and Efficient Method of Elliptic Curve Encryption Using Ancient Indian Vedic Mathematics"

Himanshu Thapliyal and M.B Srinivas
International Institute of Information Technology

Abstract:

RSA and ECC (Elliptic Curve Arithmetic) are the two major standards used for public-key cryptography.  The key length of the RSA has increased over recent years and this has put heavier processing loads on application using RSA. Nowadays, ECC is major attraction compared to RSA as it offers equal security for a smaller key size thereby reducing processing overhead. The benefits of ECC, when compared with classical cryptosystems such as RSA, include: higher speed, lower power consumption and smaller certificates, which are especially useful for wireless applications. The major time consuming arithmetic operations operation in ECC are point additions and doubling. Exponentiation operations like square and cube are the major bottlenecks in the efficiency of the point additions and doubling. This paper presents efficient hardware circuitry for point addition and doubling using multiplication and square algorithms of Ancient Indian Vedic Mathematics. The multiplier architecture is based on the vertical and crosswise algorithm of ancient Indian Vedic Mathematics. In the proposed architecture we have grouped 4 bits of the multiplicand and multiplier at a time and the partial product is available within a single clock cycle. Thus the whole multiplication operation is broken up into 4x4 bit multiplication modules. The 4x4 multiplication modules can be implemented by using any efficient multiplier. In order to calculate the square of a number “Duplex” D property of binary numbers has been proposed. In the Duplex, we take twice the product of the outermost pair, and then add twice the product of the next outermost pair, and so on till no pairs are left. When there are odd number of bits in the original sequence there is one bit left by itself in the middle, and this enters as such. Thus,

  1. For a 1 bit number, D is the same number i.e D(X0)=X0.
  2. For a 2 bit number D is twice their product i.e D(X1X0)=2 * X1 * X0.
  3. 3. For a 3 bit number D is twice the product of the outer pair + the e middle bit i.e D(X2X1X0)=2 * X2 * X0+X1.
  4. For a 4 bit number D is twice the product of the outer pair + twice the product of the inner pair i.e D(X3X2X1X0) =2 * X3 * X0+2 * X2 * X1

The pairing of the bits 4 at a time is done for number to be squared. It has been found that the proposed square is faster than conventional squares and the latest fastest square proposed by Flynn et.al. There is a considerable improvement in the point additions and doubling when implemented using proposed multiplication and square for performing multiplication and square operation respectively. The result shows that ECC hardware implemented using proposed architectures is faster than ECC hardware implemented using traditional multiplication and square algorithm. Thus the paper provides an efficient method of encryption to be implemented in computer networks. The results obtained are quite encouraging and are tested in Xilinx Virtex FPGA.

Keywords: Cryptography, RSA, Elliptic Curve Encryption.

 

2005 MAPLD International Conference Home Page