Cryptology Academy · Lesson

Scalar Multiplication & the ECDLP

Understand repeated point addition and why inverting it is hard.

Lesson 2 of 413 steps

Scalar Multiplication & the ECDLP is a free Cryptology Academy lesson on CoddyKit. This is lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Cryptology Academy learning path, and your progress syncs across the web and the CoddyKit app. The Cryptology Academy course includes 4 lessons in total.

Welcome

Scalar multiplication is the core EC operation: compute k×P by repeatedly applying the group law. The ECDLP — finding k given k×P — is the hard problem securing all elliptic-curve cryptography.

Scalar Multiplication Definition

k×P = P + P + ... + P (k times). For k=4: 4P = P+P = 2P; 2P+2P = 4P. For k=2^256, direct iteration is infeasible. We need an efficient algorithm.

Double-and-Add Algorithm

Analogous to square-and-multiply: For each bit of k from MSB to LSB: R = 2R (double) if bit is 1: R = R + P (add) O(log k) group operations ≈ O(256) for P-256.

Example: 13×P

13 = 1101 in binary Start: R = P 1: R = 2P+P = 3P (for bit 1) 0: R = 6P 1: R = 12P+P = 13P ✓ 4 doublings + 2 additions for k=13.

The Elliptic Curve Discrete Log Problem (ECDLP)

Given points G and Q = k×G on a curve, find k. Forward: easy (O(log k) operations) Reverse: no polynomial algorithm known for cryptographic curves Best generic algorithm: Pollard's rho in O(√n) ≈ 2^128 for P-256.

Why ECDLP Is Harder Than DLP

Classical DLP (g^k mod p): index-calculus algorithms work in sub-exponential time. ECDLP: no index-calculus equivalent known for generic elliptic curves. Same key length = much harder problem.

Pohlig-Hellman Attack

If the group order has small prime factors, ECDLP can be solved efficiently in each subgroup. Defenses: use curves with prime or near-prime group orders; avoid small-subgroup curves.

MOV Attack

The MOV attack maps ECDLP to DLP in a finite field via the Weil pairing. Only works for supersingular curves (embedding degree k=1,2). All NIST curves are resistant to MOV.

Constant-Time Scalar Multiplication

Naive double-and-add reveals k via timing (conditional add step). Use Montgomery ladder or comb algorithms that perform the same operations regardless of key bits. Essential for secure implementations.

ECDLP Security Levels

P-192: 96-bit security (deprecated by NIST) P-224: 112-bit security P-256: 128-bit security (current standard) P-384: 192-bit security P-521: 260-bit security Curve25519: 128-bit security

From ECDLP to ECDH Security

ECDH security reduces to ECDLP: if you can solve ECDLP (find a from A=a×G), you can compute the shared secret. The computational Diffie-Hellman assumption (CDH) assumes this is hard.

Quick Check

What is the time complexity of the best generic algorithm (Pollard's rho) for ECDLP with group order n?

Answer it in the interactive lesson

Recap

Scalar multiplication and ECDLP understood. Next we compare standard curves: P-256, Curve25519, and secp256k1.

Free to start

Learn Cryptology Academy with an AI tutor — free

Write and run real code in your browser, get instant help from a 24/7 AI tutor, and pick up where you left off on the web or in the app.

Courses: 67
Lessons: 261

Start learning free View the full course

Frequently Asked Questions

Is the “Scalar Multiplication & the ECDLP” lesson free?

Yes — the full text of “Scalar Multiplication & the ECDLP” is free to read here on the web. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Cryptology Academy course, upgrade to CoddyKit PRO. The Cryptology Academy course includes 4 lessons in total.

What will I learn in “Scalar Multiplication & the ECDLP”?

Understand repeated point addition and why inverting it is hard. You practise Cryptology Academy with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.

Do I need any experience to start Cryptology Academy?

No prior experience is required. Cryptology Academy on CoddyKit is structured for beginners through advanced learners, so you can start here or from the beginning and move at your own pace. This is lesson 2 of 4.

How long does the “Scalar Multiplication & the ECDLP” lesson take?

Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.

Can I write and run code in this Cryptology Academy lesson?

Yes. Every Cryptology Academy lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.

All lessons in this course

Elliptic Curve Group Law
Scalar Multiplication & the ECDLP
Standard Curves: P-256, Curve25519, secp256k1
ECC vs RSA: Security & Performance Trade-offs

← Back to Cryptology Academy