adam's notes

Elliptic Curve Cryptography (ECC)

Elliptic curve cryptography (ECC) is a class of cryptographic algorithms that uses elliptic curves for generating public and private key pairs.

  • sometimes referred to as if it were a single algorithm
  • named by the type of math problem it is based on
    • An elliptic curve is the set of points that satisfy a specific mathematical equation
  • can use shorter keys while maintaining a higher cryptographic strength than other discrete logarithm algorithms (e.g., RSA or D-H)
  • fast and efficient
    • good for hardware with low processing power
  • security is based on the difficulty of solving Elliptic Curve Discrete Logarithm Problem (ECDLP)
  • provides the same level of security as RSA but with smaller key sizes
  • more computationally efficient than RSA
    • used in resource-limited devices
  • E.g.
    • Secure Hash Algorithm 2 (SHA-2)
    • Elliptic Curve Digital Signature Algorithm (ECDSA)
  • used in
    • TOR project
    • part of proof of ownership for Bitcoin
    • Apple’s iMessage
    • DNS as part of DNSCurve to secure DNS information

Elliptic Curve-based Algorithms

  • categories:
    • key-agreement
    • message signature
    • message encryption

Security Strength of EC Algorithms

  • level of security is measured in bits
    • represents the capacity of the EC algorithms to resist attacks
  • each extra bit of security doubles the amount of computation needed to compromise
  • ECC standards specify 4 security strength levels:
    • is the order of the base point
    1. 112:
    2. 128:
    3. 192:
    4. 256:

EC Key-Agreement

EC Diffie-Hellman (ECDH) Key-Agreement Protocol

Elliptic curve Diffie-Hellman (ECDH) is a key-agreement protocol that enables two parties to generate a shared secret, while using an elliptic curve.

  • recommended as a standard for key-agreement protocol by NIST
  • small-subgroup attack focuses on domain parameter selection of ECDH
    • not the design directly

EC Menezes-Qu-Vanstone (ECMQV) Key-Agreement Protocol

MQV (Menezes-Qu-Vanstone) key-agreement is one of the numerous extensions to the original Diffie-Hellman key-exchange protocol.

  • designed to work in an arbitrary finite group and, in particular, elliptic curve groups
  • recommended by NIST
  • MQV makes use of two key-pairs for each party:
    • a static key-pair
      • i.e., long-term
    • and an ephemeral key-pair
      • i.e., a key-pair used only in the key-agreement transaction
  • ECMQV provides a countermeasure to some attacks against the ECDH, including the small group attack

EC Message Signature Algorithms

  • Elliptic Curve Digital Signature Algorithm (ECDSA)
    • newer and more performant than RSA-based signatures
  • Edwards Curve Digital Signature Algorithm (EdDSA)
    • digital signature is produced using an Edwards curve
    • efficient compared to ECDSA

EC Encryption Algorithms

EC encryption algorithms provide public-key-based mechanisms to encrypt messages exchanged over an insecure network.

Elliptic Curve Integrated Encryption Scheme (ECIES)

  • best known EC encryption scheme
  • provides encryption, key exchange, and digital signature
  • exist different versions depending on the standards
    • e.g. ANSI X9-63, IEEE 1363, ISO 18033-2
  • considered secure when used with a large base point
    • as secure as solving EC discrete logarithm problem
How It Works
  • two parties share elliptic curve domain parameters
  • then, each party generates a key pair
  • from the key pairs and the base point , both parties calculate the shared secret
  • then, from the shared secret, the same key derivation function is used to generate two keys
    • one for symmetric encryption
    • one for authentication
  • thus, ECIES is a hybrid scheme that uses a public key system to transport a session key to be used by a symmetric cipher

ElGammal Encryption Using Elliptic Curve (EEEC)

The ElGamal Encryption using elliptic curve (EEEC) is an adaptation of the original ElGamal encryption scheme to the elliptic curve context.

  • core of the EEEC is that the message to encrypt is hidden in an EC point coordinate
  • fully-based on public key cryptography
  • breaking EEEC is equivalent to solving the EC discrete logarithm problem
    • thus considered secure when used with a large size fields

Graph View

Backlinks