Subscribe Now Subscribe Today
Research Article
 

Implementation of Elliptic Curve Diffie-Hellman and EC Encryption Schemes



Kefa Rabah
 
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail
ABSTRACT

In recent years the rapid deployment of applications like online banking, stock trading and corporate remote access, have seen an explosive growth in the amount of sensitive data exchanged over the internet. Moreover, these internet hosts increasingly are battery-powered, wireless, handheld devices with strict memory, CPU, latency and bandwidth constraints. Given these trends, there is a clear need for efficient, scalable security mechanisms and protocols that operate well in both wired and wireless environments. To date elliptic curve cryptography is gaining wide acceptance as an alternative to the conventional cryptosystems (DES, RSA, AES, etc.) which tend to be power hungry. Elliptic curve ciphers require less computational power, memory and communication bandwidth giving it a clear edge over the traditional crypto-algorithms. This study describes the basic design principle of Elliptic Curve Crypto (ECC), EC discrete logarithm problem, ECDH key agreement and encryption protocols.

Services
Related Articles in ASCI
Similar Articles in this Journal
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

Kefa Rabah , 2005. Implementation of Elliptic Curve Diffie-Hellman and EC Encryption Schemes. Information Technology Journal, 4: 132-139.

DOI: 10.3923/itj.2005.132.139

URL: https://scialert.net/abstract/?doi=itj.2005.132.139

INTRODUCTION

The rapid growth of information technology that has resulted in significant advances in cryptography to protect the integrity and confidentiality of data is astounding. The historical cryptosystem has been a symmetric-key approach, in which both communicating partners share a common key and a level of trust is required to ensure that neither party divulges the key[1,2]. Considered by some to be the only major abstract advance in encryption techniques, Diffie and Hellman[3] proposed Public Key Encryption in 1976 and has remained a very popular protocol for strong authentication of entities[4]. By this mthod each user of the network has a personalized private key and a public key. The public key is distributed to all members of the network, while only the user holds the private key. This implies that the user is the only person able to read any messages encrypted with his public key. It is designed to be computationally intractable to calculate a private-key from its associated public-key. With public key cryptography, more sophisticated cryptographic tools such as tokens (e.g., smart cards), digital signatures and certificates are used to provide the full scope of cryptographic security services.

However, it is important to note that traditional cryptographic algorithms like DES[1], DLP[5], RSA[6] etc. are not particularly efficient in small form factor, low-power, resource constrained devices, as they require memory intensive power hungry big integer computation co-processor to complete the calculations in a timely manner. Adding such a co-processor significantly raises the cost of manufacture, rendering many devices impractical. The cost of producing a smart card, for example, is increased by as much as 400% when an additional processor is required[7]. For embedded systems or telecommunications applications characterized by extremely high volumes and a wide variety of devices, many of which have limited computing resources and wireless, the trend has been towards alternate cryptographic algorithms.

One technology in particular, known as Elliptic Curve Cryptography (ECC), has become the cryptography of choice for mobile computing and communications devices due to its size and efficiency benefits. Koblitz[8] and Miller[9] independently proposed the Elliptic Curve Cryptosystem (ECC), a method of utilizing a Discrete Logarithm problem over the points on an elliptic curve. By their proposal, ECC could be used to provide both digital signatures and an encryption scheme. Over the past decade, ECC and later ECDLP (Elliptic Curve Discrete Logarithm Problem) received considerable attention from mathematicians around the world[10], but to-date no significant breakthroughs have been made in determining weaknesses in the algorithm and to-date has weathered umpteen mathematical attacks[11,12]. Elliptic curve systems have thereby come to be accepted today as the most viable public-key technology for high-security applications.

The ECC provides higher strength-per-bit than any other current public-key cryptosystems[12]. If you compare elliptic curves to RSA and DLP you find many advantages: to obtain the same security e.g., the use of smaller fields for elliptic curves. Therefore, elliptic curves can be implemented easier and faster. Moreover, because of its higher strength-per-bit, ECCs is being increasingly used in practical applications (e.g. IC card and mobile devices) instead of RSA, which is the most used public-key cryptosystems today. They are also most suitable for constrained environments such as those in which smart cards and personal wireless devices are typically deployed. Elliptic curve ciphers are today commonly found in smart cards, personal digital assistants (PDAs), pagers and mobile phones. The Elliptic Curve Cryptosystems are also used for implementing protocols such as ECDSA digital signature scheme[13,14], Diffie-Hellman key exchange scheme[3], EC ElGamal Encryption/Decryption scheme[15] etc. In this study we analyze the elliptic curve operations and design procedure involving ECDLP, ECDH key exchange agreement and EC encryption protocols.

ECC ARITHMETIC OVER GALOIS FIELD

The core of the ECC is when it is used with Galois Field it becomes a one way function i.e., the math’s needed to compute the inverse is not known. Let an elliptic curve group over the Galois Field Ep(a, b) where, p>3 and is prime, be the set of solutions or points P = (x, y) such that (x, y∈ Ep(a,b)) that satisfy the equation: y2 = x3+ax+b (mod p) for 0≤x<p together with the extra point O called the point at infinity. For a given point P = (xp, yp), xp and yp are called the x and y coordinates of P, respectively. The number of points on Ep(a, b) is denoted by # E(Fp). The constants a and b are non negative integers smaller than the prime number p and must satisfy the condition: 4a3+27 b2 ≠ 0 (mod p). For each value of x, one needs to determine whether or not it is a quadratic residue. If it is the case, then there are two values in the elliptic group. If not, then the point is not in the elliptic group Ep(a, b). So there will be a lot of points modulo p. In fact, the general theory says that there will be about p points (x, y) with error bounded by O ().

Construction of an elliptic curve over Fp: Let the prime number p =23 and consider an elliptic curve E: y2 = x3+x+4 mod 23 defined over F23, with the constants a = 1 and b=4, which have been checked to satisfy that E is indeed an elliptic curve. We then determine the quadratic residues Q23 from the reduced set of residue Z23 = {1,2,3,.....,21,22}, which is given by Q23 = {1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18}. Which we use to determine the values of E23(1,4), i.e.,:

Group Order-Let E be the elliptic curve order over a finite field Fq. Hasse’s theorem states that the number of points on an elliptic curve (including the point at infinity) is # E (Fq) = q+1-t where |t|≤2 , # E(Fq) is called the order of an elliptic curve E and t is called the trace of E[16]. In other words, the order of an elliptic curve E(Fq) is roughly equal to the size q of the underlying field[17]. However, since the number of points in our elliptic curve is small, we can use the naïve approach to determine #E(Fq) using scalar multiplication/addition approach.

In the development and implementation of elliptic curve cryptography we are interested in the method for computing an equation of the form kP where, k is an integer in the range of [1, n-1], n is the order of the elliptic curve E and P = (xp, yp) ∈ E (Fq) is a non zero point on a given elliptic curve E. Here, P is usually a fixed point that generates a large, prime subgroup of E (Fq)including the point at O, or P is an arbitrary point in such a subgroup. This system of computation is known as scalar multiplication and is the heart of ECC scheme.

Point addition: Scalar multiplication i.e., the computation of kP, where k is a random integer and P is an elliptic curve generation point, can be defined as the combination of additions of two points on an elliptic curve. Scalar multiplication of elliptic curve points can be computed efficiently using the addition rule together with the double-and-add algorithm or one of its variants. Its properties, computation and uses will be, therefore, the core of ECC implementation. The addition of two points on an elliptic curve is defined in order that the addition results will be another point on the curve as presented in Algorithm 1 and Fig. 1.

Algorithm 1: Point addition equation

Fig. 1: Elliptic curve

In either case, when P1 = P2 (doubling) and P1≠P2 (point addition), major operations are field multiplication and field inversion. (Squaring and field addition are enough ignorable because of its less computation time.) From these formulas of Algorithm 1, we can determine the number of field operations required for each kind of elliptic curve operation. We see that an addition step usually requires eight additions, two multiplications, one squaring, three reductions mod f(x) and one inversion. A Doubling step usually requires four additions, two multiplications, two squaring, four reductions mod f(x) and one inversion. A Negation step requires one addition. The important contributors to the run time are the multiplications and inversions[17]. Just as modular exponentiation determines the efficiency of RSA cryptographic systems[4], scalar multiplication dominates the execution time of ECC systems. In all the protocols that are fundamental implementation of ECC, say ECDH, ECDSA, ECAES etc., the most time consuming part of the computations are scalar multiplications. Elliptic curves have some properties that allow optimization of scalar multiplications.

Implementation of multiplication/addition over an elliptic curve group modulo p: Let us consider an equation of the form Q = kP. For a positive integer k we let [k] denote the multiplication-by-k map from the curve to itself. This map takes a point P to P+P+.....+P (k summands). The notation [k] is extended to k≤0 by defining [0]P = O and [-k]P = -([k]P). So for instance, [2]P = P+P, [3]P = P+P+P and [-3]P = -(P+P+P). Furthermore, for a given point P on an elliptic curve E, there is a minimum positive integer n such that nP = O, the identity point or point at infinity. Integer n is called the order of the point P. It is known that n is a divisor of the order of the curve E. These scalar multiples form a subgroup of points<P>. Here,<P> is the finite cyclic group<P> = {P, 2P, 3P,.....,nP}, with order n.

To test the algorithm, let P = (7,3)∈ E23 (1,4). Then 2P = (x3, y3) is equal to: 2P = P + P = (x1, y1)+( x1, y1) = (22, 18). Next, test addition of two different points on the curve, i.e., Q = (4,16) ∈ E23(1, 4) and R = (14,18) ∈ E23(1, 4). Then Q+R = (x3, y3) = (17,9), which we can observe also to be on the curve. However, for real implementation of ECC, we need to know the order of the elliptic curve group.

Let us now implement the scalar multiplication to form a subgroup of points<P>, where,<P> is the finite cyclic group<P> = {P, 2P, 3P,.......nP}, with order n, by following the same additive rules and a generator point P. For example, let P = (7,3) ∈ E23(1,4) be a generator point which we use through repeated addition of point to generate all the point on the curve (Table 1).

Cyclic elliptic curve-Since # E(F23) = 29, which is prime and which is found by counting all the points, also known as naïve method. E(F23) is cyclic and any point other than O is a generator of E(F23). The order n of a point P≠O on an elliptic curve is a positive integer such that nP = Q and mP≠O for any integer m such that 1≤m<n. The order n of a point must divide the order N of the elliptic curve. In fact, it is true for any group. If the elliptic curve order N = #E(Fq) is a prime number, then the group is cyclic and obviously all points except the point at infinity O are of order N and which is the case looking from Table 1.

ECC PROTOCOLS

Key establishment schemes: Key establishment is the process by which two (or more) entities establish a shared cryptographic secret key and are essential for distribution of keys in today’s communication systems for use with symmetric and asymmetric cryptography. Essentially, two methods are used to establish cryptographic keying material between parties: key agreement and key transport. With a key agreement scheme, all parties contribute to the derived keying material with information that allows each party to derive the shared keying material. With key transport schemes, the sender determines the key to be transported, wraps (i.e., encrypts) the key and sends the wrapped key to the receiver, who then unwraps (i.e., decrypts) the key.

For the scheme which involves symmetric-key only system, the communicating partners have to manually establish a shared symmetric-key to be used as the key-wrapping key between the two parties. The keying material is wrapped using a NIST-approved key-wrapping algorithm (such as the AES key wrap algorithm). The public-key based key agreement schemes can be transformed into a key transport scheme using an approved key-wrapping scheme, as recommended in NIST SP 800-56.

Table 1: Point addition/scalar point multiplicative values of P
kP ≡ Pk, is that 29P ≡ P0 ≡ [O]etc

An example is S/MIME, where key agreement is combined with key wrapping to achieve the effect of key transport. This is useful because it allows the efficient encryption of large emails to multiple recipients. The efficiency is that the email content is encrypted just once, with the content encryption key encrypted (wrapped) multiple times, once for each recipient.

Elliptic Curve Discrete Logarithm Problem (ECDLP): Recall that the core of elliptic curve arithmetic is an operation called scalar point multiplication, which computes Q = kP. (For example, 11P can be expressed as 11P = (2*((2*(2*P))+P))+P). The problem of calculating k from a given points P and Q is called the discrete logarithm problem over the elliptic curve (ECDLP). Note that we can easily calculate Q = kP from given k and P, but it is computationally difficult to calculate the scalar k from points Q and P.

The corresponding problem in additive (i.e., abelian) groups is: given P and kP (P added to itself k times), find the integer k. This is much more difficult. There is no one-step operation like taking logarithms that we can use to get the solution. So we may know P and kP and yet not be able to find k in a reasonable amount of time. This is called the Discrete Log Problem for abelian groups. We could always repeatedly subtract P from kP till we got O. But if k is large, this will take us a very long time. Several important cryptosystems are based on the difficulty of solving the DLP over finite abelian groups. The solution is even tougher if the underlying group arises from an elliptic curve over a prime finite field Fq.

Implementation of ECDLP algorithm: As a simple example, let’s use an overly small value of k and our earlier elliptic curve i.e., Ep(a, b) = E23(1, 4) (Table 1). Let’s choose a point (1, 12) ∈ E23(1, 4) and try to determine k such that kP = Q. For example, if Q= (1, 12) and P=(7, 3), then 5P = Q so k = 5 is the solution to the discrete logarithm problem. One can also compute Q = kP = 1P+1P+1P+1P+1P = (1, 12) = 5P. Here k=5. Alternatively, given Q = kP = (1, 12), we can continuously subtract P from kP until we get O. But if the curve is of a large prime order then it is impossible to use this naïve approach for our computation. Take, for example, an elliptic curve Ep(a, b) of a large prime number with:

p = 6,277,101,735,386,680,763,835,789,423,207,666,416, 083,908,700,390,324,961,279

containing a large group of points exactly N points:

N = 6,277,101,735,386,680,763,835,789,423,337,720,473,986 773,608,255,189,015,329

with

k = 6,708,050,311,399,110,513,517,527,207,693,060,456,300 217,054,473

The security of ECC relies on the hardness of solving the Elliptic Curve Discrete Logarithm Problem (ECDLP), which states that given P and Q = kP, it is hard to find k[11]. Because Pohlig-Hellman algorithm reduces the computation of k to the problem of computing k modulo each prime factor of n. So if n is a large prime, the ECDLP becomes harder. In practice, one must select an elliptic curve that has some points (base point G) which has large prime order n and #E(Fq) = n.h, where, h is a small integer. While a brute-force approach is to compute all multiples of P until Q is found, k would be so large in a real cryptographic application (as indicated above) that it would be infeasible to determine k in this way. If a prime p as large as 160-bits long is selected, we cannot find k within a reasonable time, even if we use the most efficient algorithms known so far with the world’s most powerful computers.

KEY AGREEMENT PROTOCOL

EC Diffie-Hellman key agreement protocol: The Diffie-Hellman key agreement protocol is the basic public-key cryptosystem proposed for computing key sharing agreement for both private and public key protocols. ECDH is the elliptic curve analog of the traditional Diffie-Hellman key agreement algorithm[1,3,4]. The Diffie-Hellman method requires no prior contact between the two parties. Each party generates a dynamic, or ephemeral, public key and private key. They exchange their public keys. Each party then combines its private key with the other party’s public key to compute the shared secret[18].

As an example of ECDH key agreement scheme let us consider a home-banking subscriber, entity A (Alice), setting up a secure communication channel with her Bank entity (B). Alice and the Bank first agree to use a specific curve, field size and type of mathematics. Alice generates a public key and a private key; she sends the public key to her bank. Independently, her bank generates a public key and a private key; the bank’s public key is sent to Alice. Alice combines her private key and the bank’s public key to form a shared secret. Her bank combines its private key and Alice’s public key to arrive at the same shared secret key. The shared secret may now be used to generate a shared key for encrypting and decrypting the communication sessions, as shown in Algorithm 2. We can see that we just need scalar multiplication in order to implement the ECDH protocol.

Algorithm 2: Diffie-Hellman protocol

Implementation of ECDH key agreement protocol: As a simple example, let’s use our earlier elliptic curve i.e., is Ep(a, b) = E23(1, 4). Alice (A) chooses the secret-key kA = 12 and computes her public-key (Table 1): QA = kAP = 12P = (13, 11). Similarly, Bank (B) chooses the secret-key kB = 23 and computes its public-key: QB = kBP = 23P = (0, 2).

Thus, their common secret-key SAB = kAkB. Alice computes: kAQB = 12(23P) = 15P = (17, 9) and the Bank computes: kBQA = 23(12P) = 15P = (17, 9). Such that: SAB= kAQB = kBQA = 15P = (17, 9).

An alternative form of ECDH is the Elliptic curve decision Diffie-Hellman problem (ECDDHP) Boneh[19]. The ECDDHP is stated as follows: Given a point P of order n in an elliptic curve E over a finite field Fq and three points (kP), (sP) and (mP), the ECDDHP is to decide whether m = kl (modulo the order of point P). The ECDDHP is not harder than the ECDHP. Boneh, Venkatesan[20], Boneh and Shparlinski[21] discussed many issues on security of the ECDHP and related schemes.

Key agreement and setup scheme: The ECDH Key Agreement Scheme as specified in ANSI X9.63 and IEEE P1363 In ECKAS-DH1 (the Elliptic Curve Key Agreement Scheme, Diffie-Hellman 1), each party combines its own private key with the other party’s public key to calculate a shared secret key which can then be used as the key for a symmetric encryption algorithm such as AES. Other (public or private) information known to both parties may be used as key derivation parameters to ensure that a different secret key is generated in every session. This key agreement scheme is described in more detail in section 9.2 of the IEEEP1363 standard.

Pure DH or ECDH applications are, however, susceptible to impersonation or “man in the middle” attack, whereby an adversary establishes digital facades between two parties in order to obtain private information. For example, Alice may be setting up a secure session with someone impersonating her bank. Because the private and public keys are generated on the fly, there is no way to prove you have a secure session with the intended party unless you add a method for user authentication. Advanced key exchange protocols such as the Menezes-Qu-Vanstone (MQV) introduce mutual strong authentication which allows both parties to confidently identify each other before exchanging sensitive information. MQV is currently deployed through ECC systems[4,19].

THE MECHANICS OF ELLIPTIC CURVE ENCRYPTION ALGORITHM

Elliptic curve cryptography can be used to encrypt plaintext message, M, into ciphertexts. The plaintext message M is encoded into a message point PM from the finite set of points in the elliptic group, Ep(a, b). The first step consists in choosing a generator point, G ∈ Ep(a, b), such that the smallest value of n for which nG = O is a very large prime number. The elliptic group Ep(a, b) and the generator G are made public.

Assume that the Bank and Alice intends to communicate. Each user select a private key and use it to compute their public-key. For example, Alice (A) selects a random integer kA<n as her private-key and computes her public-key PA as: PA = kAG. To encrypt the message PM to the Bank (B); Alice uses her private-key and the Bank’s public-key PB to compute the ciphertext pair of points PC:

PC = [(kAG), (PM+kAPB)]

After receiving the ciphertext pair of points, PC, the Bank multiplies the first point, (kAG) with its private-key, kB and then adds the result to the second point in the ciphertext pair of points, (PM+kAPB):

(PM+kAPB)-[kB(kG)] = (PM+kAkBG)-[kB(kAG)] = PM

which is the plaintext point, corresponding to the plaintext message M. Only the Bank, knowing the private-key kB, can remove kB(kAG) from the second point of the ciphertext pair of point, i.e., (PM+kAPB) and hence retrieve the plaintext information PM.

Implementation of Elliptic Curve Encryption Scheme (ECES): Since #E(F23) = 29, which is prime. E(F23) is cyclic and any point other than O is a generator of E(F23). For example, G ≡ P = (7,3) is a generator point such that the multiples kG of the generator point G (for 1≤k≤29), are as shown in Table 1.

If Alice wants to send to Bank the message M which is encoded as the plaintext point PM = (10, 18) ∈ E23(1, 4). She must use the Bank’s public-key to encrypt it. Suppose that the Bank’s secret-key is kB = 17, then its public-key will be: PB = kBG = 17(7, 3) = 17G = (13, 12).

Alice uses her secret-key kA = 25 and Bank’s public-key PB = (13, 12) to encrypt the message point into the ciphertext pair of points: PC = [(kAG), (PM+kAPB)] = [(4, 16), (22, 5)].

Upon receiving the ciphertext pair of points, PC = [(4, 16), (22, 5)], the Bank uses its private-key, kB, to compute the plaintext point, PM, as follows:

(PM+kAPB)-[kB(kAG)] = 27G-19G = 8G (10, 18)

and which maps the plaintext point PM = (10, 18) back into the original plaintext message M.

Practical Application of ECES: For this part let’s get real and simulate real application. Let an elliptic curve group over the Galois Field Ep(a, b) where, p>3 and is prime, be the set of solutions or points P = (x, y) such that (x, y∈ Ep(a, b)) that satisfy the equation: y2 = x3+ax+b(mod p) for 0≤x<p together with the extra point O called the point at infinity. The parameters of the elliptic curve are as follows:

a = 317689081251325503476317476413827693272746955927
b = 79052896607878758718120572025718535432100651934
p = 85963102379428822376694789446897396207498568951
n = 785963102379428822376693024881714957612686157429 \\number of points #E
G = (x, y) \\ generator point

Where:

x = 771507216262649826170648268565579889907769254176
y = 9015 751024655662852527945926651499556253319 6655
kA = 670805031139911051351752720769306045630021705 4473 \\Alice’s priv. key
kB = 7860050311399110513517527207693060456300217054 473 \\Bank’s priv. key
kM = 235505031139911051351752720769306045630021705 4473 \\Message enc. key

This is playing Big Boys game so we need a number cruncher software to do similar computation done above. Here we will content ourselves with PARI a Free, open source, number cruncher[22].

Here the curve E(FP) is cyclic and any point other than O is a generator of all points on curve. For example, G = (x, y) is a generator point such that the multiples kG of the generator point G (for 1≤k≤n), which is too huge to show here.

If the Bank wants to send to Alice the message M (Append. A), which is encoded as the plaintext point

PM = (xM, yM) =(285128110405972368863732180717016601141242058721, 948739026223210722329407 7342398725955 8219668492)

The Bank must use Alice’s public-key to encrypt it. Suppose that Alice’s secret-key is kA, then her public-key will be:

PA = kAG = (90517135491294082980111512034183665522 537517216, 3004291515310424027770375706419 81602845 272146478)

The Bank selects a random number kB and Alice’s public-key PA to encrypt the message point into the ciphertext pair of points:

PC = [(kBG), (PM+kBPA)]
  = [(550605361672557316113111615482588146434984456674, 598206702584597415537642011495635814925894203618), (172390835777057262225071793643950755716065775457, 742617052078859878050112020239322107499028298971)]

Upon receiving the ciphertext pair of points, PC, Alice uses her private-key, kA, to compute the plaintext message point, PM, as follows:

(PM+kAPB)-[kB(kAG)] = PM
  = (285128110405972368863732180717016601141242058721, 94873902622321072232940773423987259558219668492)

Table 2: NIST guidelines for public-key sizes with equivalent security levels

and which maps the plaintext point PM = (xM, yM) back into the original plaintext message M.

Elliptic Curve Integrated Encryption Scheme (ECIES): ECIES combines elliptic curve asymmetric encryption and the AES symmetric encryption algorithm with the SHA-1 hash algorithm to provide an easy to use encryption scheme with message authentication support. An ECIES ciphertext object (Q, C, T) consisting of EC public key Q, encrypted message C and authentication tag T is generated from a message M and the recipient’s EC public key W. The recipient decrypts this ciphertext with their EC private key and an exception is thrown if the authentication tag is invalid. This encryption scheme is described in more detail in section 11.3 of the IEEE P1363a draft standard[23].

Following in the footsteps of DES[1]; ECC in conjunction with advance symmetric algorithm, AES[24], has already been incorporated into a number of key international standards, including ANSI X9.63, IEEE Std 1363-2000, IETF RFC 3278, ISO 15946-3 and NIST SP 800-56[2]. Adoption into global standards will assist in pushing ECC into wider commercial usage. Table 2 compares the equivalent security level for some commonly considered cryptographic key sizes[19].

Relative public-key sizes: So what does this mean in practice? NIST has recommended that 128-bit protection is necessary to achieve relatively lasting security (to the year 2036 and beyond). This means moving from 3DES to AES. To avoid compromising the security of the system, NIST's FIPS 140-2 standard indicates that keys for symmetric ciphers such as AES must be matched in strength by public-key algorithms such as RSA and ECC. For example, a 128-bit AES key demands an RSA key size of 3,072-bits for equivalent security, however, for the same strength the ECC key size is only 256-bits. As you can observe from Table 2, while ECC key sizes scale linearly, RSA does not. The result is that the gap between systems grows as the key sizes increase. This is especially relevant to implementations of AES where at 256-bit security you need an RSA key size of 15,360-bits compared to 512-bits for ECC. This will have a significant impact on a communication system as the relative computational performance advantage of ECC versus RSA is not indicated by the key sizes but by the cube of the key sizes. The difference becomes even more dramatic as the greater increase in RSA key sizes leads to an even greater increase in computational cost. So going from 1024-bit RSA key to 3072-bit RSA key requires about 27 times (33) as much computation while ECC would only increase the computational cost by just over 4 times (1.63).

CONCLUSION

We have shown that elliptic curve ciphers require less computational power, memory and communication bandwidth giving it a clear edge over the traditional crypto-algorithms. To date elliptic curve cryptography is gaining wide acceptance, especially in wireless and hand-held devices, when compared to the conventional cryptosystems (DES, RSA, AES, etc.) which tend to be power hungry. However, while the performance advantages are impressive with ECC, the data security industry need to ensure that the security system, using elliptic curve algorithm has been studied extensively in the public forum and also specified by major standards worldwide. But we think that elliptic curve cryptography is here today and is without question the next generation of public-key cryptography of choice.

Appendix A: Sample text message from the bank to alice

Miss Alice Johnson
Nairobi, Kenya

Dear Miss Johnson,

This letter is to inform you that we have received US$ 2.0 million as your first installment due for your mortgage down payment and opened mortgage servicing account No. 6688668024 on your behalf and deposited therein said amount. To service your account you will need to use your new password GKGQU78BR53.

Yours very truly,
James M Kavungu
Vice President, Finance
First Finance Bank of Nairobi

REFERENCES
ANSI X9.62, 1999. The Elliptic Curve Digital Signature Algorithm (ECDSA). American Bankers Association, USA.

Aigner, H., J. Wolkerstorfer, M. Huetter and H. Bock, 2004. Low-cost ECC coprocessor for smartcards. Proceedings of the 6th International Workshop on Cryptographic Hardware and Embedded Systems, Aug. 11-13, Cambridge, MA, USA., pp: 65-78.

Basham, L., D. Johnson and T. Polk, 1999. Representation of elliptic curve digital signature algorithm (ECDSA) keys and signatures in internet X.509 public-key infrastructure certificates. Internet Draft, pp: 252-266.

Dan, B. and I.E. Shparlinski, 2001. On the unpredictability of bits of the elliptic curve Diffie-hellman scheme. Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, Aug. 19-23, Santa Barbara, California, pp: 201-212.

Dan, B. and R. Venkatesan, 1996. Hardness of computing the most significant bits of secret keys in Diffie-hellman and related schemes. Proceedings of the 16th Annual International Cryptology Conference on Advances in Cryptology, Aug. 18-22, London, UK., pp: 129-142.

Dan, B., 1998. The decision diffie-hellman problem. Proceedings of the 3rd International Symposium on Algorithmic Number Theory, Jun. 21-25, London, UK., pp: 48-63.

Diffie, W. and M.E. Hellman, 1976. Multi-user cryptographic techniques. Proceedings of the AFIPS National Computer Conference, Jun. 7-10, New York, USA., pp: 109-112.

Diffie, W., P.V. Oorschot and M. Wiener, 1992. Authentication and authenticated key exchanges. Des. Codes Cryptogr., 2: 107-125.
Direct Link  |  

ECDLP-I, 1998. A semav, evaluation of discrete logarithm on some elliptic curve. Math. Comput., 67: 353-356.

Elgamal, T., 1985. A public-key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inform. Theory, 31: 469-472.
Direct Link  |  

Koblitz, N., 1987. Elliptic curve cryptosystems. Math. Comput., 48: 203-209.
Direct Link  |  

Menezes, A.J., P.C. van Oorschot and S.A. Vanstone, 1997. Handbook of Applied Cryptography. CRC Press, New York, USA.

Miller, V.S., 1986. Use of Elliptic Curve in Cryptography. Springer Verlag, New York, pp: 417-426.

Odlyzko, A., 1984. Discrete logarithms in finite fields andtheir cryptographic significance. Proceedings of EUROCRYPT 84 a Workshop on the Theory and Application of Cryptographic Techniques, April 1984, Paris, France, pp: 224-314.

Rabah, K., 2004. Data security and cryptographic techniques: A review. Inform. Technol. J., 3: 106-132.
CrossRef  |  Direct Link  |  

Rabah, K., 2004. A review of RSA and public-key cryptosystems. Botswana J. Technol., 13: 1-11.
Direct Link  |  

Rabah, K., 2004. Elliptic curve cryptography. J. Applied Sci., 5: 604-633.

Rivest, R.L., A. Shamir and L. Adleman, 1978. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM., 21: 120-126.
CrossRef  |  Direct Link  |  

Silverman, J.H., 1985. The Arithmetic of Elliptic Curves. Springer-Verlag, Berlin.

US, Department of Commerce/National Institute of Standards and Technology, 1997. Announcing Request for Candidate Algorithm Nominations for the Advanced Encryption Standard (AES). National Institute of Standards and Technology, USA.

©  2020 Science Alert. All Rights Reserved