Elliptic Curves: Repeated Steps, Compact Public Keys

If you have ever looked closely at a modern security setting, you have probably met names like P-256, X25519 or Ed25519 and wondered why there are so many of them, and why the keys they make are so much shorter than the older kind. All three are built from the same idea, called elliptic-curve cryptography, and that idea is easier to picture than its name suggests. A public key on an elliptic curve is simply a place you reach by taking one fixed kind of step, over and over, from an agreed starting point. The private key is how many steps you took. Anyone can see where you ended up; working out how many steps got you there is the hard part. This article builds that picture from nothing: what the curve is, what a single step looks like, how the steps wrap around on a clock, a complete small example you can check, why the step count stays hidden, why the keys are so compact, and finally which named curve does which job, including the jobs it does inside the connections an artificial intelligence (AI) agent makes every day.

Why a new kind of public key was worth having

Public-key cryptography lets strangers do two remarkable things: agree on a shared secret while everyone listens, and prove who signed a message without revealing anything that would let someone else sign. The older ways of doing this, RSA (named after its inventors Rivest, Shamir and Adleman) and classic Diffie-Hellman key exchange, work by doing arithmetic on very large numbers on a clock that wraps around. They are well understood and still widely used, but to stay safe they need numbers that are thousands of bits long, and those numbers keep growing as computers get faster.

In the mid-1980s two mathematicians, Neal Koblitz and Victor Miller, independently suggested doing the same kind of public-key work on a different mathematical object: the set of points on an elliptic curve. The appeal was efficiency. The best known ways to attack elliptic-curve keys are much weaker than the best known ways to attack RSA or classic Diffie-Hellman keys of the same size, so a far shorter key gives comparable protection.

Shorter keys matter more than they might seem. They mean smaller messages on the network, less memory on small devices, faster handshakes when millions of connections start every second, and less to store and protect. That is why almost every new protocol of the last decade reaches for elliptic curves first.

One word of reassurance before going further: despite the name, an elliptic curve has nothing to do with ellipses, the oval shapes of planetary orbits. The name is a historical accident from older mathematics. You will not need any of that history here.

The curve, and what one step looks like

An elliptic curve, for our purposes, is the set of all points that satisfy one particular kind of rule relating two numbers, x and y. In words, the rule says: y squared equals x cubed, plus some fixed multiple of x, plus some fixed number. Drawn on ordinary graph paper, such a curve looks like a smooth, sideways S-shape that is perfectly mirrored above and below the horizontal axis. That mirror symmetry is important, so keep it in mind.

The remarkable property of these curves is that you can 'add' two points on them to get a third point that is also on the curve. The rule is geometric. Take two points on the curve and draw a straight line through them. That line will cross the curve at exactly one more place. Take that third crossing and flip it to its mirror image across the horizontal axis. The flipped point is the sum of the first two. That is the whole step: draw the line, find the third crossing, flip it.

Adding a point to itself is called doubling, and it uses the same idea with a small twist. Instead of a line through two different points, you use the line that just touches the curve at your one point, the tangent line, and follow it to where it crosses the curve again. Flip that crossing, and you have twice your point.

Now the key idea. Pick an agreed starting point, which cryptographers call the base point. Adding the base point to itself once gives 'two times the base point'. Adding it again gives 'three times', and so on. Doing this a certain number of times is called scalar multiplication, where the scalar is simply the count. The count is the private key. The point you land on is the public key. That is the entire design: a public key is a destination, and the private key is the number of steps it took to get there.

Putting the curve on a clock

The smooth S-shaped curve is perfect for building intuition, but computers do not work with points on a smooth curve, because those involve fractions and endless decimals. Instead, cryptography uses the same rule on a clock: every number wraps around at a fixed modulus, so all coordinates are whole numbers from zero up to the modulus minus one. The arithmetic of 'draw a line, find the third point, flip it' still works; it is just carried out with wrap-around arithmetic instead of drawing.

On a clock the curve no longer looks like a curve at all. Plotted on a grid, its points look like a scattering of dots with no obvious pattern, apart from the mirror symmetry that survives: for every dot above the middle there is a partner below. That loss of visible shape is part of the protection. On the smooth curve you could almost watch where repeated steps were taking you. On the clock, each step jumps to what looks like a random dot.

There is one extra point that every curve needs, called the point at infinity. It plays the role that zero plays in ordinary addition: adding it to any point leaves that point unchanged. You reach it when you add a point to its own mirror image, because the line through two mirror-image points is vertical and never meets the curve a third time. It sounds exotic, but you can think of it as 'back to the start'.

Here is the consequence that makes the whole scheme tidy. Because there are only finitely many dots on a clock, if you keep adding the base point to itself you must eventually come back to where you began. The number of steps in that loop is called the order of the base point. Real curves are chosen so that this loop is astronomically long, a number with more than 75 decimal digits for the curves discussed later, so that every possible private key lands on a different public point.

A tiny curve you can walk by hand

Here is a complete example, small enough to check with a pencil or a phone calculator. The clock has 17 positions, and the rule is: y squared equals x cubed, plus two times x, plus two, with everything wrapped around 17. This toy curve has exactly 18 ordinary points plus the point at infinity, 19 in all, which makes it a favourite of textbooks.

Choose the base point G to be the point with x equal to 5 and y equal to 1, written (5, 1). You can check it is on the curve: 1 squared is 1, and 5 cubed plus 10 plus 2 is 137, which leaves 1 after removing eight lots of 17. Both sides agree, so (5, 1) belongs.

Now walk. Doubling G lands on (6, 3). Adding G again lands on (10, 6), which is 3G. The walk continues: 4G is (3, 1), 5G is (9, 16), 6G is (16, 13), 7G is (0, 6), and so on, each point looking unrelated to the one before. 18G is (5, 16), the mirror image of the start, and one more step reaches the point at infinity. The loop has 19 steps, so the order of G is 19, and the walk then repeats.

Now use the walk as a key exchange, the elliptic-curve version of Diffie-Hellman, usually shortened to ECDH. Alice secretly picks 3 and publishes 3G, which is (10, 6). Bob secretly picks 7 and publishes 7G, which is (0, 6). Alice takes Bob's point and walks it 3 more times; Bob takes Alice's point and walks it 7 more times. Both are taking 21 steps from G in total, and since the loop is 19 long, 21 steps is the same as 2 steps. Both land on (6, 3). That point is their shared secret, and neither of them ever sent it.

Someone who watched the exchange saw only (10, 6) and (0, 6). To find the shared point they need either 3 or 7, which means answering: how many steps from (5, 1) lead to (10, 6)? With only 19 possibilities you could simply try them all. That is the reason real curves have about 2 to the power 256 possible step counts instead of 19.

Notice three things the tiny example already shows. The public points give no visible hint of their step counts: 3G and 7G even share the same y value, 6, purely by coincidence. The order of the steps does not matter, because 3 then 7 and 7 then 3 both total 21. And wrapping is built in, because 21 steps on a 19-step loop is the same as 2. Every real elliptic-curve key agreement relies on exactly these three facts, just with numbers too large to write on a page.

Why the step count stays hidden

Going forwards is fast. Given a private count, even one more than 75 digits long, a computer does not take that many single steps. It uses a shortcut: double, double, double, and add the base point in at the right moments, reading the count one binary digit at a time. Reaching any destination takes only a few hundred doublings and additions, which is a fraction of a millisecond.

Going backwards is the hard direction. Given only the start and the destination, finding the count is called the elliptic-curve discrete logarithm problem. For a well-chosen curve, the best known method on ordinary computers takes roughly the square root of the number of possible counts. For a curve with about 2 to the power 256 points, the square root is about 2 to the power 128, a number of operations far beyond any realistic budget. That is why a 256-bit elliptic-curve key is described as giving about 128 bits of security.

Contrast that with RSA and classic Diffie-Hellman. Their hard problems have special structure that cleverer attacks can exploit, attacks that are much faster than the square root of the number of possibilities. To stay ahead of those attacks, their numbers must be far larger. Reaching about 128 bits of security takes an RSA modulus of about 3,072 bits, according to the key-size guidance published by the United States National Institute of Standards and Technology (NIST). Elliptic curves get there with about 256 bits, because no comparable shortcut is known for a well-chosen curve.

That word 'well-chosen' carries real weight. Some curves have hidden weaknesses that make the backwards problem easy, and implementations can leak the private count through timing or by accepting maliciously crafted points. This is why everyone uses a small set of carefully studied, standardised curves rather than inventing their own, and why using a mature library matters more than understanding every detail of the arithmetic.

Three famous names, three different jobs

Elliptic curves come with names, and the names that matter most in practice are P-256, X25519 and Ed25519. They are often listed together as if they were interchangeable. They are not. Each one is a specific curve paired with a specific job, and mixing up the jobs is a common source of confusion.

P-256 is a curve standardised by NIST, also known by the name secp256r1. It is the general-purpose workhorse. It is used both for key agreement, through ECDH, and for digital signatures, through the Elliptic Curve Digital Signature Algorithm (ECDSA). It is everywhere in certificates, the electronic documents that tie a public key to a name, in hardware security chips and in government and enterprise systems that need its long standardisation record. Using it safely requires care: for example, a receiver must check that a public point it is given really lies on the curve before using it.

X25519 is a key-agreement function built on a curve called Curve25519, designed by Daniel J. Bernstein and standardised for internet use in Request for Comments (RFC) 7748. It does exactly one job: Diffie-Hellman-style key agreement. It was designed to be fast and hard to implement wrongly, for example by working only with x coordinates so that many bad-input cases simply cannot arise. In modern Transport Layer Security (TLS), the protocol that protects web and machine-to-machine connections, X25519 is the most commonly used key-agreement option.

Ed25519 is a signature scheme on an equivalent version of the same curve, standardised in RFC 8032 as part of the Edwards-curve Digital Signature Algorithm (EdDSA). It does exactly one job: signing and verifying. Its design produces the per-signature secret value deterministically from the private key and the message, which removes a well-known way that badly implemented signatures leak keys. It is popular for Secure Shell (SSH) keys, software signing and newer identity systems.

The practical rule that follows is simple: a key belongs to one job. An X25519 key agrees secrets; an Ed25519 key signs. Even where the same curve could technically serve both purposes, as P-256 can, well-designed systems keep separate keys for agreement and for signing, so that a weakness or a compromise in one role does not spill into the other.

Why do both families exist? Partly history and partly philosophy. P-256 arrived first and was built into standards, certificates and hardware over many years, so it is hard to replace. Curve25519 and its relatives were designed later with a strong emphasis on simple, fast and mistake-resistant implementation, and with every design choice explained in public. Both are considered secure today; the difference is mostly about how much care an implementation needs and where each one is already supported.

• P-256: agreement (ECDH) and signatures (ECDSA); widest compliance and hardware support.
• X25519: agreement only; the most common key share in modern TLS.
• Ed25519: signatures only; deterministic per-signature secret, common for SSH and code signing.
• One key, one job: keep agreement keys and signing keys separate.

Where the protection quietly fails

The hard backwards problem is rarely what breaks in practice. Elliptic-curve systems fail in the places around the mathematics, and the failures are worth knowing by name because each has a simple guard.

The first is a weak private count. The private key must be chosen uniformly at random from the whole loop. If a device generates it from a poor source of randomness, for example a small embedded system that starts with the same internal state every time it boots, an attacker does not need to solve anything; they can simply try the few counts the device was ever likely to produce. Good libraries draw from the operating system's secure random number generator, and that is the only acceptable source.

The second is trusting a point you were handed. In key agreement, the other side sends you its public point, and your device multiplies that point by your private count. If an attacker sends a carefully chosen point that is not really on the agreed curve, or that sits in a tiny loop of only a few steps, the result can leak small pieces of your private count, and repeating the trick can recover all of it. For P-256 the defence is to check that every received point satisfies the curve rule before using it. X25519 was designed so that its way of working with only x coordinates makes this class of mistake largely harmless, which is one reason it is a popular default, but even it expects the shared result to be checked for an all-zero value in some protocols.

The third is leaking the count through behaviour. If a program takes a slightly different amount of time, or draws slightly different amounts of power, depending on each binary digit of the private count, an attacker who can measure those differences may reconstruct the count. Careful implementations use a constant-time method, often a technique called a ladder, that performs the same operations in the same order whatever the secret digits are.

The fourth is using the raw shared point directly. The point two sides agree on has structure; it is not a uniformly random key. Protocols pass it through a key derivation function, a one-way recipe that turns it into clean, separate keys for each purpose. Using the raw coordinate as an encryption key is a classic shortcut in hand-written code.

What this means for practitioners and for AI agents

For most teams, the elliptic-curve decisions are made by protocols and libraries, and the job is to choose sensible defaults and avoid breaking them. In TLS, allow X25519 and P-256 for key agreement and let the library negotiate. For new signing keys, Ed25519 is a strong default where it is supported, with P-256 and ECDSA where compliance or hardware requires it. Never invent a curve, never write the arithmetic yourself, and never accept a public point from someone else without the validation your library performs for you.

AI agents touch elliptic curves constantly, usually without anyone noticing. An agent, meaning software that uses a language model to decide on actions and then calls tools to carry them out, opens a protected connection for nearly every tool call, and that connection almost always begins with an X25519 or P-256 key agreement. The server's certificate is very often signed with ECDSA on P-256. When an agent signs in with a workload identity rather than a password, its credential is often an elliptic-curve key pair, and when an organisation signs the code or model files an agent runs, Ed25519 or ECDSA is a common choice.

That makes the agent's private keys, whichever curve they use, worth protecting like any other identity. An elliptic-curve private key is just a 32-byte number; it is small enough to paste into a prompt, a chat message, a configuration file or a log line without anyone noticing. It belongs in a key store or hardware security module, a locked-down device that performs signing on the agent's behalf and never hands the key itself out, and it should never appear anywhere a model can read it back.

Code assistants deserve a specific caution. Asked to 'add elliptic-curve encryption', an assistant may produce something that runs but misuses the building blocks: reusing one key for both agreement and signing, using a raw shared point directly as an encryption key instead of passing it through a key derivation function, or hand-rolling point arithmetic. Review generated cryptography for a mature library, a named curve matched to its job, and a key derivation step, not just for whether it produces output.

Finally, a forward look. Elliptic-curve keys, like RSA keys, would be breakable by a sufficiently large quantum computer, which is why new hybrid key agreements combine X25519 with a post-quantum method. That transition changes what sits next to the curve, not the lessons here: the public key is a destination, the private key is a secret count, and each key should have exactly one job.

Glossary

Elliptic curve

The set of points satisfying a rule of the form y squared equals x cubed plus a multiple of x plus a constant, on which points can be added.

Base point

The agreed starting point from which every public key is reached by repeated steps.

Scalar multiplication

Adding the base point to itself a given number of times; the number is the private key.

Point at infinity

The extra point that acts like zero, reached when a point is added to its own mirror image.

Order

The number of steps it takes to walk from the base point all the way back to the start.

Elliptic-curve discrete logarithm problem

The hard task of finding the step count given only the base point and the destination point.

ECDH

Elliptic-curve Diffie-Hellman: two sides agree a shared point by each applying its secret step count to the other's public point.

ECDSA

Elliptic Curve Digital Signature Algorithm, a signature scheme commonly used with the P-256 curve.

EdDSA

Edwards-curve Digital Signature Algorithm; Ed25519 is its most widely used form.

Further reading

1. RFC 7748: Elliptic Curves for Security (IETF)
2. RFC 8032: Edwards-Curve Digital Signature Algorithm (EdDSA) (IETF)
3. NIST SP 800-186: Recommendations for Discrete Logarithm-based Cryptography: Elliptic Curve Domain Parameters
4. NIST SP 800-57 Part 1 Rev. 5: Recommendation for Key Management