FORM-2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENTS RULES, 2003
PROVISIONAL
Specification
(See section 10 and rule 13)
METHOD AND APPARATUS FOR IMPLEMENTING THE ELLIPTIC CURVE SCALAR MULTIPLICATION METHOD IN
CRYPTOGRAPHY
TATA CONSULTANCY SERVICES LTD.,
an Indian Company
of Bombay House, 24, Sir Homi Mody Street, Mumbai 400 01,
Maharashtra, India
THE FOLLOWING SPECIFICATION DESCRIBES THE INVENTION.

Field of Invention
The present invention is in the field of cryptography.
Particularly, the invention relates to the use of Elliptic Curve scalar multiplication in cryptography.
This invention envisages a system and method for implementing the Elliptic Curve scalar multiplication method in cryptography.
Background of Invention
Elliptic Curve Cryptography (ECC) was proposed by N. Koblitz and V. Miller independently. ECC has obtained a lot of applications because of smaller key-length and increased theoretical robustness. In ECC, scalar multiplication (or point multiplication) is the operation of calculating an integer multiple of an element in additive group of elliptic curve. In other words, it is a computation of kP for any integer k and a point P on the elliptic curve. To compute EC scalar multiplications, one can easily adapt historical exponentiation methods to scalar multiplication, replacing multiplication by addition and squaring by doubling.
In ECC, elliptic curves over finite fields are used to implement ECDSA and ECE algorithms. There is no known subexponential method and system to solve the elliptic curve discrete algorithm so that the elliptic curves are secure and safe. It is known that an important core operation in the elliptic curves is scalar multiplication. For the last couple of years, many methods have been proposed to reduce the computational complexity of EC scalar multiplications.
Prior Art
The present invention is to find out an approximation for DBNS, which uses to


compute EC scalar multiplication. Due to this invention, the performance of ECDSA and ECE can be speeded up.
Elliptic Curve Cryptography (ECC) was proposed by N. Koblitz and V. Miller independently. ECC has quickly received a lot of attention because of smaller key-length and increased theoretical robustness.
For last couple of years, DBNS has been proposed by many authors. Mathieu Ciet and Francesco Sica published a paper "An Analysis of Double Base Number Systems and a Sublinear Scalar Multiplication Algorithm" which produces an efficient algorithm for DBNS to compute nP on some supersingular elliptic curves of characteristic 3. This DBNS representation does not express the exponents of 2 and 3 in decreasing order.
V.S. Dimitrov, L. Imbert, and P.K. Mishra published a paper "Fast elliptic curve point multiplication using double-base chains". This paper has provided an efficient EC scalar multiplication algorithm.
United States Patent No. 6252959 by Christof Paar discloses a method of point multiplier implementation that reduces the number of point doubling operations.
United States Patent No. 6263081 by Atsuko Miyaji discloses a method of implementing point multiplication, in software using certain pre-computations.
United States Patent No. 6490352 by Richard Schroeppel discloses an apparatus for operating a cryptographic engine that may include a key generation module for creating key pairs for encrypting substantive content to be shared between two users over a secured or unsecured communication link.


The key generation module may include a point-doubling module as part of an elliptic curve module for creating and processing keys.
United States Patent No. 20070064931 by Bin Zhu discloses systems and methods configured for recoding an odd integer and elliptic curve point multiplication, having general utility and also specific application to elliptic curve point multiplication and cryptosystems. In one implementation, the recoding is performed by converting an odd integer k into a binary representation. The binary representation could be, for example, coefficients for powers of two representing the odd integer. The binary representation is then configured as comb bit-columns, wherein every bit-column is a signed odd integer. Another implementation applies this recoding method and discloses a variation of comb methods that computes elliptic curve point multiplication more efficiently and with less saved points than known comb methods. The disclosed point multiplication methods are then modified to be Simple Power Analysis (SPA)-resistant.
United States Patent No. 7024559 Jerome A. Solinas discloses a method of generating and verifying a cryptographic digital signature using joint sparse expansion.
United States Patent No. 7079650 by Erik Knudsen discloses a fast cryptographic method between two entities exchanging data via a non-secure communication channel. The method, for example, forms a common key between two entities (A,B), each having a secret key (a,b) and using a public key (P) formed by a point of an elliptic curve (E), and includes at least multiplying the odd order point (P) by an integer by additions and halving operations.


Summary of Invention
Number Theory and Cryptography are based on mathematical problems that are considered difficult to solve. In the theory of Double Base Number System (DBNS)/ Multiple Base Number System (MBNS), finding the best approximation for a given integer is a difficult problem.
This invention envisages in accordance with envisages the use of DBNS (Double Base Number Systems) and MBNS (Multi Base Number Systems) methods to reduce the computational complexity of EC scalar multiplications.'
In accordance with the system and method of this invention DBNS is used to devise efficient steps to express a given integer n in decreasing order. These steps can be applied to compute EC scalar multiplication, with improved performance of the Elliptic Curve Digital Signature Algorithm (ECDSA) and Elliptic Curve Encryption (ECE).
In accordance with this invention there is provided an approximation, which expresses any integer n in the form of DBNS with decreasing order of exponents. The approximation is used to compute Elliptic curve scalar multiplication.. It has a lot of applications in ECDSA and ECE.
Therefore in accordance with this invention there is provide a method and a system for designing a new Double Base Number System representation in decreasing order of exponents.
Typically, the DBNS representation can write the representation in an efficient way. Sometimes, the DBNS writes with repeated summands.
In accordance with a preferred embodiment of the invention, in the event there exists a summand with repetition, the summand never appears more than two.


Typically, the DBNS representation as defined by a first aspect of the invention uses bmax = min (bi, (Llog2 k +1))
and tmax = min (t,, (Llog3 k+1)).
In accordance with one aspect of the invention the steps include a method to compute EC scalar multiplication using Algorithm 1 as shown in the accompanying drawings.
Brief Description of the Accompanying Drawings
The invention is described with reference to the accompanying drawings in
which;
Figure 1 shows that z satisfies the minimal condition.
Figure 2 shows to find (s,x,y).
Figure 3 shows to compute DBNS for Algorithm 1.
Figure 4 shows to compute Case 1 for Algorithm 2.
Figure 5 shows to compute Cases 2-5 for Algorithm 2.
Figure 6 shows to compute EC scalar multiplication for Algorithm 2.
Figure 7 shows the applications of Algorithms 1& 2 in ECC.
Detailed Description of Invention
In ECC, elliptic curves over finite fields are used to implement ECDSA and ECE algorithms. There is no known subexponential method and system to solve the elliptic curve discrete algorithm so that the elliptic curves are secure and safe. It is known that an important core operation in the elliptic curves is scalar multiplication. For the last couple of years, many methods have been proposed to reduce the computational complexity of EC scalar multiplications.


For elliptic curves, although DBNS representations using 2 and 3 as bases have been tried. To compute DBNS, there is no uniformity to express a number in a decreasing order.
The present invention provides a method and system to express a DBNS in decreasing order. It is used to calculate EC scalar multiplication over a finite elliptic curve. The methods involves steps for DBNS and EC scalar multiplication. These steps perform an elliptic curve E over a prime / binary field F.
Various methods of EC scalar multiplication
The Binary method is the first known exponentiation method applied to compute EC scalar multiplication. Binary representation of a scalar enables us to interpret the multiplication as a cumulative addition of non-zero components. For example, the binary method computes 54P as 32P + 16P + 4P + 2P.
Non-adjacent Form (NAF) method is used to compute EC scalar multiplication. This method writes any integer in terms of signed binary representation. To get fast computation for kP, NAF allows negative values in the representation set. This method is more efficient than the binary method. For example, NAF computes 15P = 16P-P.
Double-base number system (DBNS) is a representation scheme in which every positive integer, n, is represented as the sum or difference of 2-integers. 2-integers are numbers of the form 2a3b. In general, an s-integer is a positive integer, whose largest prime factor does not exceed the s prime number. For example, 314158 can expressed using DBNS as 215 32 + 211 32+ 28 31+ 24 31 –213° (all exponents of 2 and 3 are in decreasing order of exponents without


repetition of summands), whereas DBNS Greedy form writes 314158 = 215 32 + 211 32+ 28 31+ 22 32 + 2°32 + 2°3° not in the decreasing order of exponents.
Multiple Base Number System (MBNS) is a representation scheme in which every positive integer, n, is represented as the sum or difference of s-integers and 2-integers (where s > 2), that is, numbers of the form 2a3b5c7d... pl (where p is prime). For example, 66 can be expressed using MBNS as 223151 + 21315° (all exponents of 2, 3 and 5 are in decreasing order without repetition of summands).
Public-key cryptosystems are based on problems that are considered difficult to solve. "Difficult" in this case refers more to the computational requirements in finding a solution than to the conception of the problem. These problems are called hard problems. Some of the most well known examples are factoring, theorem-proving, and the Traveling Salesman Problem.
There are two major classes of problems that interest cryptographers - P (Polynomial time) and NP (Non-deterministic polynomial time). Briefly, a problem is in P if it can be solved in polynomial time, while a problem is in NP if the validity of a proposed solution can be checked in polynomial time. Every problem in P is in NP, but we do not know whether P = NP or not.
For example, the problem of multiplying two numbers is in P. Namely, the number of bit operations required to multiply two numbers of bit length k is at most A2, a polynomial. The problem of finding a factor of a number is in NP, because a proposed solution can be checked in polynomial time. However, it is not known whether this problem is in P.


Since Number theory and Cryptography are interlinked, there are some hard problems in number theory, which have directly links with ECC. Let us start with a hard problem identified by us in DBNS that computing the best approximation of a given integer n, expressed as n = finite 213J with decreasing order of exponents is difficult. For instance, n =100 can be expressed as 402 different DBNS expressions. It is really a tough job to find out an efficient method for this hard problem. This invention envisages a method and apparatus for DBNS, which expresses any integer n in the form of DBNS with decreasing order of exponents. The proposed algorithm writes n = 13225 = 21 38 + 2° 34 + 2° 33 - 2° 3' - 2° 3° - 2° 3° with some repeated summands. Still the research problem is open that a given n can be expressed as an optimal DBNS form with decreasing order of exponents and no repetition of summands.
In accordance with this invention there is provided a method and system to compute DBNS with decreasing order of exponents (Fig. 3). In accordance with the method of the invention, the output (DBNS sum) sometimes consists of repetition of summands (order of exponents). It is mathematically proved that suppose there exists some summands with repetitions, each summand never appears more than twice .
Algorithm 1: A pseudo code of the proposed DBNS representation
Conversion to DBNS with decreasing order of exponents
Input: A positive integer n
Output: the sequence of exponents (bm, tm) (such that bi > b2 > .. .> bm > 0,
and t1 > t2 > ... > tm > 0) leading to one DBNS representation of n.
1. Find z = 2bl 311 the largest integer 2-integer less than or equal to n
2. k  n
3. k  |k-z|



To compute EC scalar multiplication, this invention envisages an efficient method and system using the DBNS sum. After obtaining the output from Algorithm 1, the DBNS sum is used to compute EC scalar multiplication. It follows that the invented steps of the method for EC scalar multiplication computes Rsum separately when the given DBNS sum consists of repeated exponents. It is an important thing to note that the Rsum takes only one repeated summand at a time for each repeated exponent. When there is no repeated summands in the given DBNS sum, the method considers Rsum = 0. The proposed EC scalar multiplication method (Algorithm 2, Fig. 6), produces the output z, known as nP. With the invention of Algorithms 1 & 2, the performance of ECDSA and ECE has been good (Fig. 7).

Let us take 980 expressed as 25 33 + 23 32+ 23 31+ 22 31 + 22 3°+ 21 3° + 21 3° using Algorithm 1. Then 980P can be computed using Algorithm 2. Similarly, we can express 240 = 24 32 + 23 32+ 2231+2231 and 24 = 21 32 + 21 31- 2°3°. It is clear that Algorithm 1 allows sometimes repetition of summands, but each summand never appears more than two.
Our Algorithm 1 computes 145673465 = 21637 + 21037+2736 + 2436+2335 - 21 34 - 2° 32 - 2° 3' - 2° 3° with 9 summands in decreasing order of exponents (without repetition). Similarly, 841232 = 2738 + 21 36- 2°33 - 2°32+ 2° 3° + 2° 3° with 6 summands in decreasing order of exponents with repetition. Note that Algorithm 1 produces better DBNS representation and reduced complexity. However, it seems impossible to determine an optimal DBNS representation for a given integer n.
Given an integer n, we can express n in the form of DBNS - a deterministic polynomial time problem. This result is proved using transcendental number theory and exponential Diophantine equations. To compute the best approximation of n in DBNS (decreasing order), it is not yet proven in the complexity class of P. For instance, n =1000 has 1295579 DBNS in which it will be a difficult task to find the best one in decreasing order without repetition of summands.
IMPLEMENTATION RESULTS
Using the method and system in accordance with this invention e the DBNS representation and tested Algorithm 1 for various large size numbers.


Value of n Total no. of summands in DBNS No. of summands with repetition
343894 5 0
5678904 4 0
14678913 9 0
3211313123134234234344142 23 0
2192-l 59 10 (2x 5)
2256-1 97 30(2x15)
2512-1 190 50 (2x 25)
Table 1: DBNS sum using Algorithm 1
INDUSTRIAL APPLICATIONS
The method and apparatus of this invention has a number of applications in ECDSA and ECE. Some specific areas where this invention can be applied are:
1. Digital Signatures through Smart Cards: A smart card employing the implementation of ECDSA using Algorithms 1 & 2 can be used for secure signing of electronic documents such as tax forms, airline reservations etc.
2. Authentication of connection to a remote host: Certain web transactions such as banking and e-commerce need to be authenticated at the server-end. This has been achieved by establishing an SSL connection between the client and server using ECC.
3. Key Generation: This invention can also be used for the secure generation of a public/private ECC key pair. The private key is stored inside the card and never leaves the card thus providing the most secure storage of private keys. The public key is output to the terminal that the card is attached to and is used for generating a certificate.


4. Symmetric Key Generation: Using public key cryptography to encrypt messages is usually inefficient compared to symmetric key techniques. For this reason, when two parties want to set up a secure communication channel, they use their public/private key pairs to generate a symmetric key through some session key generation protocol such as Elliptic Curve Diffie-Hellman key exchange. This invention can be adapted to facilitate this session key generation.
While considerable emphasis has been placed herein on the components and component parts of the preferred embodiments, it will be appreciated that many embodiments can be made and that many changes can be made in the preferred embodiments without departing from the principles of the invention. These and other changes in the preferred embodiment as well as other embodiments of the invention will be apparent to those skilled in the art from the disclosure herein, whereby it is to be distinctly understood that the foregoing descriptive matter is to be interpreted merely as illustrative of the invention and not as a limitation.