23 Elliptic Curve Cryptosystem

Objectives

•  To learn about elliptic curves
•  To discuss about elliptic curve cryptosystems
•  Compare with Elgamal Cryptosystem
• To discuss about security of ECC

1 Introduction

Mathematically definition of a “Elliptic Curve” is a smooth, projective algebraic curve of genus one and third degree with a distinct point O (at infinity).

1.1 Elliptic Curve Equation

If we’re talking about an elliptic curve in Fp, what we’re talking about is a cloud of points which fulfil the “curve equation”. This equation is:

Here, y, x, a and b are all within Fp, i.e. they are integers modulo p. The coefficients a and b are the so-called characteristic coefficients of the curve — they determine what points will be on the curve.

Note that the curve coefficients have to fulfill one condition:

This condition guarantees that the curve will not contain any singularities.

2. Point Operations

To do any meaningful operations on an elliptic curve, one has to be able to do calculations with points of the curve. The two basic operations to perform with on-curve points are:

1. Point addition: R = P + Q
2. Point doubling: R = P + P

Out of these operations, there’s one compound operation, scalar point multiplication, which can be implemented by the two above. This will also be described. Note that adding any point to the special point at infinity yields the point, or mathematically speaking:

2.1 Point Addition

Adding two points is not as easy as simply adding their x- and y-components and taking them modulo p. Instead it is more like connecting the two points via a line and then intersecting that line with the curve (although this operation will not yield the resulting point, but its conjugate). What it exactly relates to is not really important, however.

What is important is how you perform the calculation based on what you’ve already implemented.

Note that point addition only works on two points which are not the same:

Point doubling comes into play if two points shall be added which are identical, i.e.:

These are the calculations needed to get R. Note that a, which is needed for calculating s, is one of the curve parameters:

2.2 Scalar Point Multiplication

When point multiplication and point doubling are implemented, one can derive from those two basic building blocks scalar point multiplication, i.e. multiplying a scalar value (a integer) with a point:

R= KA

The inverse of that operation, i.e. finding k for a given A and R, is called the “discrete logarithm”. This is an operation which is (without any further tricks like knowing a secret “helper” value) considered computationally infeasible. Therefore it lays the foundation for the ECC cryptosystem: Finding R for given k and A is easy, the opposite direction is hard — unless you have the “helper” value called “private key”.

Elliptic Curve Cryptography

• Elliptic curve cryptography is a public key cryptosystem just like RSA, Rabin, and El Gamal. Every user has a public and a private key. Public key is used for encryption/signature verification. Private key is used for decryption/signature generation. Elliptic curves are used as an extension to other current cryptosystems.
  • Elliptic Curve Diffie-Hellman Key Exchange
  • Elliptic Curve Digital Signature Algorithm

3.1 Curve cryptosystem parameters

In order to turn all these mathematical basics into a cryptosystem, some parameters have to be defined that are sufficient to do meaningful operations. There are 6 distinct values for the Fp case and they comprise the so-called “domain parameters”:

1.   p: The prime number which defines the field in which the curve operates, Fp. All point operations are taken modulo p.

2.     a, b: The two coefficients which define the curve. These are integers.

3.     G: The generator or base point. A distinct point of the curve which resembles the “start” of the curve. This is either given in point form G or as two separate integers gx and gy

4.     n: The order of the curve generator point G. This is, in layman’s terms, the number of different points on the curve which can be gained by multiplying a scalar with G. For most operations this value is not needed, but for digital signing using ECDSA the operations are congruent modulo n, not p.

5.     h: The cofactor of the curve. It is the quotient of the number of curve-points, or #E(Fp), divided by n.

3.2 Generating a keypair

Generating a keypair for ECC is trivial. To get the private key, choose a random integer dA, so that

Then getting the accompanying public key QA is equally trivial, you just have to use scalar point multiplication of the private key with the generator point G:

Note that the public and private key are not equally exchangeable (like in RSA, where both are integers): the private key dA is a integer, but the public key QA is a point on the curve.

4. Encrypting using ECIES 4.1 Encryption

Performing encryption using ECIES is then relatively easy. Let’s assume we want to encrypt data with the public key QA that we just generated. Again, first choose a random number r so that

Now, R is publicly transmitted with the message and from the point S a symmetric key is derived with which the message is encrypted. A HMAC will also be appended, but we’ll skip that part here and just show the basic functionality.

4.3.2 Decryption

Now assume that you receive a message, which is encrypted with a symmetric key. Together with that message you receive a value of R in plain text. How can you — with the aid of your private key, of course — recover the symmetric key? Well, that’s also easy:

By just multiplying your private key with the publicly transmitted point R, you will receive the shared secret point S, from which you can then derive the symmetric key (with the same mechanism that the sender did generate it, of course).

To see why this works so beautifully, you just have to take a look at the equations and substitute:

5     Elliptic Curve Cryptosystem Analog to El Gamal

–  Alice chooses another random integer, k from the interval [1, p-1]

–  The ciphertext is a pair of points

•      PC = [ (kB), (PM + kPB) ]

To decrypt, Bob computes the product of the first point from PC and his private key, b

•      b * (kB)

– Bob then takes this product and subtracts it from the second point from PC

• (PM + kPB) – [b(kB)] = PM + k(bB) – b(kB) = PM

–  Bob then decodes PM to get the message, M.

5. Security of ECC

To protect a 128 bit AES key it would take a:

RSA Key Size: 3072 bits

ECC Key Size: 256 bits

7. Applications of ECC

• Many devices are small and have limited storage and computational power. Since key size of ECC is less when compared to other public key cryptosystems, it is applicable for the following systems:
  • Wireless communication
  • devices Smart cards
• Web servers that need to handle many encryption sessions
  • Any application where security is needed but lacks the power, storage and computational power that is necessary for our current cryptosystems

Summary

We studied :

–  about elliptic curves

–  Point operations on the elliptic curves

–  Encryption and decryption operations using elliptic curves

–  Different usage of ECC.