CYS406 · Chapter 5 · Annotated SlidesElliptic Curve Cryptography
Original
Overview

Elliptic Curve Cryptography

Elliptic curves and their properties, trapdoor functions, groups and point addition, finite fields, scalar multiplication and cyclic subgroups, the elliptic-curve discrete logarithm problem, ECC encryption, ECDH key exchange, and why ECC gives the same security with smaller keys.

How to read this page

Every original slide is shown unchanged. Yellow marks on a slide point to a numbered note: hover or tap a mark to jump to its note, and hover a note to see its marks. Questions tagged Past exam appeared on a real paper; Prediction questions are likely angles, not confirmed. Pick an answer to each question: a wrong pick tells you why it is wrong, so you can try again.

All 33 slides
  1. 1 Slide 1
  2. 2 WHAT ARE ELLIPTIC
  3. 3 EXAMPLES
  4. 4 PROPERTIES OF ELLIPTIC
  5. 5 TRAP DOOR FUNCTION
  6. 6 A group in mathematics is a set for which we
  7. 7 closure: if and a b are members of G, then
  8. 8 GROUPS OVER ELLIPTIC
  9. 9 SUM AND INVERSE
  10. 10 A finite field is a set with a finite
  11. 11 In fields we have two binary
  12. 12 MULTIPLICATION OVER
  13. 13 CYCLIC BEHAVIOR
  14. 14 CYCLIC SUBGROUPS AND
  15. 15 a cyclic subgroup we can give a new,
  16. 16 In the light of this, we can outline the following
  17. 17 ELLIPTIC CURVES IN CRYPTOGRAPHY
  18. 18 DISCRETE LOGARITHMS IN FINITE FIELDS
  19. 19 DEFINITION OF ELLIPTIC CURVES
  20. 20 WHAT IS ELLIPTIC CURVE CRYPTOGRAPHY (ECC)?
  21. 21 USING ELLIPTIC CURVES IN CRYPTOGRAPHY
  22. 22 GENERIC PROCEDURES OF ECC
  23. 23 EXAMPLE – ELLIPTIC CURVE CRYPTOSYSTEM ANALOG TO EL GAMAL
  24. 24 EXAMPLE – ELLIPTIC CURVE CRYPTOSYSTEM ANALOG TO EL GAMAL
  25. 25 EXAMPLE – COMPARE TO EL GAMAL
  26. 26 DIFFIE-HELLMAN (DH) KEY EXCHANGE
  27. 27 ECC DIFFIE-HELLMAN
  28. 28 EXAMPLE – ELLIPTIC CURVE DIFFIE-HELLMAN EXCHANGE
  29. 29 WHY USE ECC?
  30. 30 SECURITY OF ECC
  31. 31 APPLICATIONS OF ECC
  32. 32 BENEFITS OF ECC
  33. 33 SUMMARY OF ECC
Slide 1 / 33

Slide 1

Slide 1: Slide 1
Slide 2 / 33

WHAT ARE ELLIPTIC

Slide 2: WHAT ARE ELLIPTIC

Notes

  1. Elliptic curve: y² = x³ + ax + b (with 4a³ + 27b² ≠ 0). Symmetric about the x-axis.

Slide 3 / 33

EXAMPLES

Slide 3: EXAMPLES
Slide 4 / 33

PROPERTIES OF ELLIPTIC

Slide 4: PROPERTIES OF ELLIPTIC
Slide 5 / 33

TRAP DOOR FUNCTION

Slide 5: TRAP DOOR FUNCTION

Notes

  1. Trapdoor function: easy one way, hard to reverse without secret information.

Slide 6 / 33

A group in mathematics is a set for which we

Slide 6: A group in mathematics is a set for which we
Slide 7 / 33

closure: if and a b are members of G, then

Slide 7: closure: if and a b are members of G, then
Slide 8 / 33

GROUPS OVER ELLIPTIC

Slide 8: GROUPS OVER ELLIPTIC
Slide 9 / 33

SUM AND INVERSE

Slide 9: SUM AND INVERSE

Notes

  1. Point addition: the line through P and Q meets the curve at a third point; reflect it to get P + Q. The inverse of (x, y) is (x, −y).

Slide 10 / 33

A finite field is a set with a finite

Slide 10: A finite field is a set with a finite
Slide 11 / 33

In fields we have two binary

Slide 11: In fields we have two binary
Slide 12 / 33

MULTIPLICATION OVER

Slide 12: MULTIPLICATION OVER

Notes

  1. Scalar multiplication nP = P + P + … + P (n times), computed fast with double-and-add.

Slide 13 / 33

CYCLIC BEHAVIOR

Slide 13: CYCLIC BEHAVIOR
Slide 14 / 33

CYCLIC SUBGROUPS AND

Slide 14: CYCLIC SUBGROUPS AND
Slide 15 / 33

a cyclic subgroup we can give a new,

Slide 15: a cyclic subgroup we can give a new,
Slide 16 / 33

In the light of this, we can outline the following

Slide 16: In the light of this, we can outline the following
Slide 17 / 33

ELLIPTIC CURVES IN CRYPTOGRAPHY

Slide 17: ELLIPTIC CURVES IN CRYPTOGRAPHY
Slide 18 / 33

DISCRETE LOGARITHMS IN FINITE FIELDS

Slide 18: DISCRETE LOGARITHMS IN FINITE FIELDS

Notes

  1. ECDLP: given P and Q = kP, finding k is infeasible. That is ECC’s hard problem.

Exam angle

PredictionQ1

ECC’s security relies on the difficulty of:

Slide 19 / 33

DEFINITION OF ELLIPTIC CURVES

Slide 19: DEFINITION OF ELLIPTIC CURVES
Slide 20 / 33

WHAT IS ELLIPTIC CURVE CRYPTOGRAPHY (ECC)?

Slide 20: WHAT IS ELLIPTIC CURVE CRYPTOGRAPHY (ECC)?
Slide 21 / 33

USING ELLIPTIC CURVES IN CRYPTOGRAPHY

Slide 21: USING ELLIPTIC CURVES IN CRYPTOGRAPHY
Slide 22 / 33

GENERIC PROCEDURES OF ECC

Slide 22: GENERIC PROCEDURES OF ECC
Slide 23 / 33

EXAMPLE – ELLIPTIC CURVE CRYPTOSYSTEM ANALOG TO EL GAMAL

Slide 23: EXAMPLE – ELLIPTIC CURVE CRYPTOSYSTEM ANALOG TO EL GAMAL
Slide 24 / 33

EXAMPLE – ELLIPTIC CURVE CRYPTOSYSTEM ANALOG TO EL GAMAL

Slide 24: EXAMPLE – ELLIPTIC CURVE CRYPTOSYSTEM ANALOG TO EL GAMAL
Slide 25 / 33

EXAMPLE – COMPARE TO EL GAMAL

Slide 25: EXAMPLE – COMPARE TO EL GAMAL
Slide 26 / 33

DIFFIE-HELLMAN (DH) KEY EXCHANGE

Slide 26: DIFFIE-HELLMAN (DH) KEY EXCHANGE
Slide 27 / 33

ECC DIFFIE-HELLMAN

Slide 27: ECC DIFFIE-HELLMAN

Notes

  1. ECDH: Alice sends aG, Bob sends bG; both compute the shared point abG.

  2. Seen again Chapter 8: Diffie-Hellman Key Exchange, slide 6: classic Diffie–Hellman

Slide 28 / 33

EXAMPLE – ELLIPTIC CURVE DIFFIE-HELLMAN EXCHANGE

Slide 28: EXAMPLE – ELLIPTIC CURVE DIFFIE-HELLMAN EXCHANGE
Slide 29 / 33

WHY USE ECC?

Slide 29: WHY USE ECC?

Notes

  1. A 256-bit ECC key ≈ 3072-bit RSA security: smaller keys, faster, less power and bandwidth (good for mobile and IoT).

Exam angle

PredictionQ1

The main advantage of ECC over RSA is:

Slide 30 / 33

SECURITY OF ECC

Slide 30: SECURITY OF ECC
Slide 31 / 33

APPLICATIONS OF ECC

Slide 31: APPLICATIONS OF ECC

Notes

  1. Applications: TLS key exchange, ECDSA signatures, Bitcoin, mobile devices.

Slide 32 / 33

BENEFITS OF ECC

Slide 32: BENEFITS OF ECC
Slide 33 / 33

SUMMARY OF ECC

Slide 33: SUMMARY OF ECC