New embedded S


Implementation of Elliptic Curve Cryptosystems



Download 1.14 Mb.
Page22/31
Date17.10.2016
Size1.14 Mb.
#272
1   ...   18   19   20   21   22   23   24   25   ...   31

6.5.4Implementation of Elliptic Curve Cryptosystems


The setup of an elliptic curve cryptographic device requires some high-correlated steps.

  1. A finite field (or Galois field) containing candidate elements to build the elliptic curve points. At this point one has to choose between prime fields ( or where p is a big prime natural number) and binary fields (). Another critical parameter to choose is the field order q.

  2. A representation for the finite field elements, in order to map correctly messages into elliptic curve points. For prime fields an element is a Montgomery residue [montgomery1985]; for binary fields an element is a polynomial with binary coefficients.

  3. Algorithms for implementing arithmetic operations over the previously chosen finite field. To make possible the evaluation of elliptic curve point operations, one has to define the modular sum, modular squaring, modular multiplication and modular inversion over the finite field elements. The finite field arithmetic is different from binary fields to prime fields. For example, the modular multiplication of binary field elements is attained by the extended Euclidean algorithm [cormen], and in prime fields is attained by the Montgomery multiplication algorithm [montgomery1985].

  4. An elliptic curve over . Not all elliptic curves are appropriate, since in some specific conditions the security of the overall cryptographic system can be substantially reduced. These specific conditions can take place when the chosen curve is defined weak. The NIST specification [nist] and Certicom SECG group specification [secg-B] help the designer to choose a non-weak and implementation-efficient curve but impose constraints on previous three facts: the order of the finite field, the representation of field elements and the finite field arithmetic algorithms.

  5. A suitable representation of the elliptic curve. A coordinate change, for example from affine coordinates to projective coordinates, cause modification of the elliptic curve point arithmetic algorithms, but can improve computational efficiency. A specific projective transformation that leads to so called jacobian coordinates, reduces to zero the number of finite field modular inversions, increasing the number of modular sums and modular multiplications needed in elliptic curve point operations. This fact, for some implementation cases, can improve dramatically the overall evaluation efficiency.

  6. Algorithms for the elliptic curve points arithmetic, dependent on curve representation. The efficiency can be improved in different ways depending on the overall system implementation and if the desired target platform is hardware or software.


6.5.4.1Implementation Issues


When one has to implement a particular protocol or functionality concerning elliptic curve cryptography, he has to face with a number or choices and factor that can affect entire system architecture, and consequently the system performances (running time, power consumption, hardware resource needs). Implementation choices regard:

  • desired security level of the baseline algorithm (this implies constraints on choosing the appropriate finite field where the curve will lie, and constraints about the specific elliptic curve that implemented protocol will exploit);

  • desired security level for the implemented cryptographic protocol (e.g. ECDSA, ECDH);

  • methods to maximize the efficiency of finite field arithmetic;

  • methods to maximize the efficiency of elliptic curve points operations;

  • the application platform (hardware or software);

  • constraints on computation resources (processor speed, code size, power consumption);

  • constraints on communication resources (bandwidth, response time).

All these choice can affect deeply the application design, and inherently the final device security level. They all are taken together for better results in terms of security and performance.

To ensure avoiding the choose of a weak curve, the National Institute of Standards and Technology [nist] and the Standards to Efficient Cryptography Group [secg-B] published a list of recommended elliptic curve equations. These recommendations are built following studies on specific curves, to ensure usage of non-weak and implementation-efficient equations.


Table - Elliptic curve point representations recommended by NIST for binary fields.



Finite field

Polynomial basis

Normal basis type



































6.5.4.2State of the Art


In the late 1990’s elliptic curve cryptography systems begin to enter into commercial devices. Some standard organization and private companies, like National Institute of Standards and Technology (NIST) [fips800], Standards for efficient cryptography group [secg-A] and Certicom [certicom-B] started to publish security standards and security protocols based on elliptic curves.

In February of 2005, the National Security Agency of the United States announced a coordinated set of algorithms for U.S. government use called Suite B, including symmetric encryption, key exchange, digital signature and hash functions [nsa]. NSA stated that certified Suite B implementations will be used for the protection of Top Secret information. At the same time, some countries in Europe proposed the same Suite B requirements for information protection. Suite B cryptography recommends use of elliptic curve Diffie-Hellman (ECDH) in many existing protocols such as the Internet Key Exchange (IKE, mainly used in IPsec [rfc]), transport layer security (TLS [dierks]), and Secure MIME (S/MIME[ramsdell]).


6.5.4.3Recommended Curves: NIST


Two types of curves are recommended by NIST specification [nist]: the pseudorandom curves and the special curves. Pseudorandom ones are curves with coefficients generated exploiting a seeded cryptographic hash evaluation. Special curves are particular cases of coefficients, curve equation and underlying fields notable for high computational efficiency.

NIST pseudorandom curves over prime fields are called P-192, P-224, P-256, P-384, P-521. All these curves are in the form mod . The recommendations regards all the curve parameters including the prime modulus , the order , the SHA1 seed input needed to generation of coefficients, the SHA1 output , the coefficient satifying mod , and the coordinates of the generator point G or .

NIST pseudorandom curves over binary fields are called B-163, B-233, B-283, B-409, B-571, all in the form. Every recommended curve is in the form .

NIST special curves, also called Koblitz curves, over binary fields are denoted with K-163, K-233, K-283, K-409, K-571, and are in the form .

All the previous curves over binary fields support two possible representations for point coordinates: a polynomial representation or a normal basis representation. Table shows representation possibilities over recommended binary fields.

6.5.4.4Recommended Curves: SECG


The Standards for Efficient Cryptography Group (SECG) [secg-B] proposed in year 2000 a set of curves, over prime fields and binary fields.

Over prime fields SECG recommends random curves called secp112r1, secp112r2, secp128r1, secp128r2, secp160r1, secp160r2, secp192r1, secp224r1, secp256r1, secp384r1, secp521r1. Definition of random curves is provided in previous section.

Over binary fields SECG recommends special curves denoted with secp160k1, secp192k1, secp224k1, secp256k1 (Table ). Definition of random curve is provided in previous section. Note that SECG recommendations include more elliptic curves defined over prime fields than NIST recommendations, and some special curves over prime fields are proposed.

Some cryptographic standards deals with elliptic curves and the SECG curves fit a number of them. In Table one can note some standards like ANSI X9.62 [ansi962], the draft ANSI x9.63 [ansi963], the draft FSML [fsml], IEEE P1363 [ieee], IPSEC [panjwani], the already described NIST [nist], and Wireless Application Forum’s WTLS standard (WAP) [wap]. In particular, IPSEC refers to the draft document regarding ECC and submitted to the IPSEC Internet Engineering Task Force working group.


Table - Elliptic curve point representations recommended by SECG for binary fields.




Finite field

Polynomial basis










































Over binary fields SECG recommends random curves called sect113r1, sect113r2, sect131r1, sect131r2, sect163r1, sect163r2, sect193r1, sect193r2, sect233r1, sect283r1, sect409r1, sect571r1. Also special curves over binary fields are mentioned and are called sect163k1, sect233k1, sect239k1, sect283k1, sect409k1, sect571k1. Table shows how these curves are recommended or compliant with several ECC standards mentioned above.

Table - SECG curves over prime fields and compliance with current standards.






Curve

ANSI X9.62

ANSI X9.63

FSML

IEEE P1363

IPSEC

NIST

WAP

secp112r1










C

C




R

secp112r2










C

C




C

secp128r1










C

C




C

secp128r2










C

C




C

secp160k1

C

R

C

C

C




C

secp160r1

C

C

C

C

C




R

secp160r2

C

R

C

C

C




C

secp192k1

C

R

C

C

C




C

secp192r1

R

R

C

C

C

R

C

secp224k1

C

R

C

C

C




C

secp224r1

C

R

C

C

C

R

C

secp256k1

C

R

C

C

C




C

secp256r1

R

R

C

C

C

R

C

secp384r1

C

R

C

C

C

R

C

secp521r1

C

R

C

C

C

R

C

C stands for compliant, R for recommended.

All SECG curves are provided with coefficients, point generator information, and somewhat all data that NIST presents for an elliptic curve. The curve formulations are explained in detail in SECG publication [secg-A].

For prime fields the curves are in the form mod , including a parameter set where is defining the finite field , are the curve coefficients, is the base point of the curve, the prime is the order of , and is the cofactor of the curve (number of curve points divided by the order of ).

For finite fields the curves are in the form , with a parameter set where is defining the finite field , is an irreducible polynomial of degree specifying the representation of binary field elements, are the curve coefficients, is the base point of the curve, the prime is the order of , and is the cofactor of the curve.



Table - SECG curves over binary fields and compliance with current standards.



Curve

ANSI X9.62

ANSI X9.63

FSML

IEEE P1363

IPSEC

NIST

WAP

sect113r1










C

C




R

sect113r2










C

C




C

sect131r1










C

C




C

sect131r1










C

C




C

sect163k1

C

R

R

C

R

R

R

sect163r1

C

C

R

C

R




C

sect163r2

C

R

R

C

C

R

C

sect193r1

C

R

C

C

C




C

sect193r2

C

R

C

C

C




C

sect233k1

C

R

C

C

C

R

C

sect233r1

C

R

C

C

C

R

C

sect239k1

C

C

C

C

C




C

sect283k1

C

R

R

C

R

R

C

sect283r1

C

R

R

C

R

R

C

sect409k1

C

R

C

C

C

R

C

sect409r1

C

R

C

C

C

R

C

sect571k1

C

R

C

C

C

R

C

sect571r1

C

R

C

C

C

R

C

C stands for compliant, R for recommended.



Download 1.14 Mb.

Share with your friends:
1   ...   18   19   20   21   22   23   24   25   ...   31



The database is protected by copyright ©ininet.org 2024
send message
    Main page
Guide
Instructions
Report
Request
Review