Discrete Logarithm Problem (DLP)
This chapter provides an introduction to the Discrete Logarithm Problem (DLP), which is the reverse operation of the exponentiation operation in Abelian Groups in multiplicative notation, or the scalar multiplication in additive notation. The DLP in many Abelian Groups is easy to solve. But the DLP in elliptic curve groups is very hard to solve, which make them good candidates to create trapdoor functions.
Doubling or Squaring in Abelian Group
Scalar Multiplication or Exponentiation
What Is Discrete Logarithm Problem (DLP)
Examples of Discrete Logarithm Problem (DLP)
What Is Trapdoor Function
DLP And Trapdoor Function
Scalar Multiplication on Elliptic Curve as Trapdoor Function
- Point doubling (or squaring) is the addition (or multiplication)
of two identical elements in an Abelian group in additive (multiplicative) notation.
- Scalar multiplication is an extension of point doubling by
adding the same point multiple times sequentially. This is also
called point exponentiation in multiplicative notation.
- The Discrete Logarithm Problem (DLP) is the reverse operation of the
exponentiation operation in an Abelian Group in the multiplicative notation,
or the reverse operation of the scalar multiplication operation in the additive notation.
- The DLP is very easy to solve in some Abelian Groups and
very difficult to solve in other Abelian Groups.
- A trapdoor function is an operation that is much easier to perform
than its reverse operation.
- Multiplication of two large prime numbers is a trapdoor function,
because the reverse operation, factoring a large number into prime numbers,
is much harder.
- Many Abelian Groups are not good candidates to create trapdoor functions, because
their DLP are easy to resolve.
- Elliptic Curve groups are good candidates to create trapdoor functions,
because we have a very efficient double-and-add algorithm for the scalar multiplications
and no efficient way for the reverse operation, which is the DLP.
Table of Contents
About This Book
Geometric Introduction to Elliptic Curves
Algebraic Introduction to Elliptic Curves
Abelian Group and Elliptic Curves
►Discrete Logarithm Problem (DLP)
Generators and Cyclic Subgroups
Reduced Elliptic Curve Groups
Elliptic Curve Subgroups
tinyec - Python Library for ECC
EC (Elliptic Curve) Key Pair
ECDH (Elliptic Curve Diffie-Hellman) Key Exchange
ECDSA (Elliptic Curve Digital Signature Algorithm)
ECES (Elliptic Curve Encryption Scheme)
Full Version in PDF/EPUB