Elliptic-curve discrete logarithm problem

As explained in Real-World Cryptography

The elliptic curve discrete logarithm problem is the problem of recovering a scalar from a known base point and its scalar multiple on an elliptic-curve group.

In an elliptic-curve group, scalar multiplication repeatedly adds a point to itself. The elliptic-curve discrete logarithm problem (ECDLP) asks you to recover the scalar x when you know G and P = [x]G. section 5.3.1

The recovery challenge

Choose a point G and add it to itself x times to produce P. Computing P from G and x is scalar multiplication; recovering x from only G and P is the ECDLP. section 5.3.1

Figure 5.11 Elliptic curve cryptography (ECC), in practice, is mostly specified with elliptic curves in coordinates modulo a large prime number p. This means that what we use in cryptography looks much more like the right graph than the left graph.

Use the coordinate view to see that practical elliptic-curve cryptography works with points modulo a large prime p. section 5.3.1

How Real-World Cryptography covers it

How deep it goes

Defines ECDLP through point addition and scalar multiplication without developing an algorithm for solving it.

Examples

Uses a base point G, a scalar x, and the resulting point P = [x]G.

What it assumes

Assumes familiarity with group operations and introduces scalar multiplication as repeated point addition.

What you can do after

Evaluate/understand how elliptic-curve key-exchange mathematics represents a discrete logarithm challenge.

How it connects

Connects elliptic-curve groups, elliptic-curve cryptography, scalar multiplication, and Diffie-Hellman.

liveBookmanning.com

Read Real-World Cryptography on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Elliptic Curve Cryptography for DevelopersThe elliptic curve discrete logarithm problem is the problem of recovering a scalar from a base point and its scalar multiple on an elliptic curve.
• 

  liveBookmanning.com
  Software Security for DevelopersThe elliptic-curve discrete logarithm problem is the computational problem of determining a scalar from an elliptic-curve point multiplication, believed to be computationally difficult for suitable curves.

Compare how 3 books explain elliptic-curve discrete logarithm problem →

Related concepts

• elliptic-curve diffie-hellmanused by · Elliptic-curve Diffie-Hellman is a public-key key-agreement method in which parties derive a shared secret through elliptic-curve point operations.
• scalar multiplicationuses · Scalar multiplication applies a scalar to a mathematical object according to the rules of its algebraic structure, such as scaling a vector or repeated addition of a group element.

This explainer was generated by Manning's knowledge graph from the text of Real-World Cryptography. The section links point to the parts of the book it draws on.