Contents

• 1 Elliptic Curves
• 1.1 Degenerate curves
• 1.2 The Point at Infinity
• 1.3 Elliptic Curve [Group] Operation
• 1.3.0.1 Common math notation: P + Q, -R, and N*P
• 1.3.1 Special cases: P + P and P + -P
• 1.4 Reference: Elliptic curve group operation formulas
• 1.4.1 Special case where one point is infinity
• 1.4.2 General case where XP =/= XQ (not inverses, not doubling, neither point is infinity)
• 1.4.3 Special case YP = -Y*Q (points are mutual inverses)
• 1.4.4 Special case P + P (point doubling)
• 2 Modular arithmetic
• 3 Orbits of points
• 3.1 Every point in the orbit is distinct until we cycle back to the original point
• 4 How to build a cryptography scheme out of this
• 5 What is a keypair?
• 6 Classroom application: Elliptic Curve Diffie-Hellmann
• 7 Disclaimers (Introduction)
• 8 Looking forward (Conclusion)
• 9 Appendix: a brief look at projective geometry
• 9.1 Example: pole/polar construction

1 Elliptic Curves

This is a written adaptation of a YouTube video I made in March 2024:

An [elliptic curve] is defined by an equation

y^2 = x^3 + Ax + B

The definition of a specific curve is a pair of numbers {A, B}. For instance, the elliptic curve that Bitcoin uses is the curve {A=0, B=7}

Here is a collection of some elliptic curves from Wikipedia:¹

If a point (X, Y) satisfies the equation (meaning you plug the coordinates in and the equation is true), then the point is on the curve. Otherwise, the point is not on the curve.

Notice that because an elliptic curve is defined as

y^2 = (some function involving only terms in x)

if any point {X, Y} is on the curve, then so is {X, -Y} So elliptic curves are always symmetrical about the x-axis.

1.1 Degenerate curves

There is a subset of elliptic curves called [degenerate curves] which we cannot use in elliptic curve cryptography.

Visually these are curves with sharp “cusps” or self-intersections. The example in the catalog is (A=0, B=0). You can also produce one in the applet with (A=-3, B=2).

Algebraically, there is a [statistic]² called the [discriminant] of the curve, which is

discriminant({ec, A, B}) ->
    -16 * (4*pow(A, 3) + 27*pow(B, 2)).

Degenerate curves are those where the discriminant is 0. You can manufacture parameters A and B for degenerate curves using this formula:

degenerate_curve(K) when is_integer(N) ->
    A = -3*K*K,
    B = 2*K*K*K,
    {ec, A, B}.

• If the discriminant is positive, the curve has 2 [connected components].
• If the discriminant is negative, the curve has 1 [connected component].

1.2 The Point at Infinity

There is additionally this special point, which in math sources is denoted 𝒪, pronounced “the point at infinity”, and which we will simply denote as infinity.

infinity is “off the page”; that is, infinity is too cool to have (X, Y) coordinates like all the pleb points. But still, definitionally, infinity is a point that is on every elliptic curve.

infinity is very important in order to make the cryptography logic work.

If you’re in a hurry, it’s ok to think of the question “what is the purpose of infinity?” as kind of the complement of “why can’t I divide by zero?”. The reason you can’t divide by zero is it breaks algebra. The reason this infinity is added to the picture is to make the algebra work.

See the appendix on projective geometry if you want a slightly deeper dive.

1.3 Elliptic Curve [Group] Operation

The next thing to understand is the elliptic curve group operation.

Now suppose we have two points on the curve, P = {XP, YP} and Q = {XQ, YQ}.

There are weird edge cases if the points are the same point or are mirror({X, Y}) -> {X, -1*Y} reflections of each other. We will ignore those for now and handle them later as special cases.

We use normal algebra from high school to compute the line y = Mx + b that intersects both P and Q.

Because of algebraic geometry that I don’t understand, this line will intersect the curve in a third point R. The mirror of R (negate the Y-coordinate) is the result of the group operation on P and Q. In pseudocode:

%% pseudocode
ec_group_operation(Curve, P, Q) ->
    Line      = join(P, Q),
    [P, Q, R] = intersections(Curve, Line),
    mirror(R).

1.3.0.1 Common math notation: P + Q, -R, and N*P

Mathematicians are semiotic sadists, so it is common practice to denote ec_group_operation(Curve, P, Q) as P + Q, with the curve being implicit. Nothing arouses a semiotic sadist quite so much as hidden computation context.

The operating convention here in math is that + is used for binary operations that are symmetrical (so P + Q is the same as Q + P).

By further abuse of notation, P + P + ... + P (N times) is denoted as N*P. Note that integers can be multiplied by points, but there is no way to multiply points by points. Again, semiotic sadism.

1.3.1 Special cases: P + P and P + -P

To operate a point P with itself, you do the same construction but instead of using the secant line between P and Q, you instead use the tangent line at P.

A special case arises when Q = -P, because when we join the two points we get a vertical line that obviously™ doesn’t have a third intersection of the curve.

In this case we say that P + (-P) = infinity. infinity acts the same way 0 acts in normal addition:

P + infinity = infinity + P = P

1.4 Reference: Elliptic curve group operation formulas

1.4.1 Special case where one point is infinity

P + infinity = infinity + P = P

1.4.2 General case where XP =/= XQ (not inverses, not doubling, neither point is infinity)

This is the case where the points are not inverses, it’s not point doubling, and neither point is infinity.

The two points are P = {XP, YP} and Q = {XQ, YQ}

Define

S = (YP - YQ) / (XP - XQ)

This is simply the slope of the line joining the two points.

ResultX = S*S - XP - XQ
ResultY = S*(XP - ResultX) - YP

1.4.3 Special case YP = -Y*Q (points are mutual inverses)

Then P + Q = infinity

NOTE: this case also covers P + P in the case where YP = 0.

1.4.4 Special case P + P (point doubling)

Then

S = (3*XP*XP + A) / (2 * YP)

Notice that because we are computing a tangent line (as opposed to a secant line), the slope of that tangent line depends on the curve parameter A. Equally interestingly, the slope of the tangent line does not depend on B.

Compare to the other cases, when the line joining the two points was purely a function of their coordinates.

In this case,

ResultX = S*S - 2*XP
ResultY = S*(XP - ResultX) - YP

Note that the only point of deviation here is in computing the slope of the tangent line. Given the slope S, the formula to compute {ResultX, ResultY} is the same as in the general case, just with XP = XQ and YP = YQ.

2 Modular arithmetic

The next big question is how to build a cryptography scheme out of this?

The first thing to understand is that computers are really bad at doing math with continuous numbers.

>>> 0.1 + 0.2
0.30000000000000004

Computers however are very good at doing arithmetic with whole numbers.

So instead we do math with what is called “modular arithmetic”, or clock arithmetic. So, right now it is 7:38 PM. In 6 hours it will be 1:38 AM. So,

7 + 6 = 1   (mod 12)

Modular arithmetic is the same concept of cyclic arithmetic but with an arbitrary modulus.

The way modular addition, subtraction, and multiplication would work is really not hard to imagine. Any time you encounter an integer, modulo it to be in 0..(Modulus-1), then just do the operations.

The tricky operation is modular division. Normally the trick in math is to think of division as “inverse multiplication.” For instance, in mod-12 arithmetic, we can say that

1/5 = 5         (mod 12)
because
5*5 = 25 = 1    (mod 12)

However, this doesn’t work for numbers that have common divisors with the modulus. For instance, if we look at the [orbit] of 4 (ie its multiples mod 12), we see

4, 8, 12=0, 4, 8, 12=0, ...

And we’re stuck. If we use a prime modulus, we avoid these problems entirely, because there’s no numbers in the module with which the modulus shares divisors.

So from now on, if someone asks you why prime numbers are important in cryptography, you have the answer: prime numbers are important in cryptography because they’re prime which means they have no divisors.

3 Orbits of points

Now that you understand the idea of modular arithmetic and why we use it, there’s an important implication that jumps out: modular elliptic curves have a finite number of points. It might be an unimagably large number of points, but it is still a finite number of points.

So, for any point P, we can look at its [orbit]: P, 2*P, 3*P, 4*P, ....

Because the number of points is finite, we know that at some point the orbit of P has to circle back on itself.

3.1 Every point in the orbit is distinct until we cycle back to the original point

Let’s call CycleLength (for cycle) the smallest positive integer such that CycleLength*P = P.

It is less obvious that every point in the orbit is distinct until we get back to P.

This true is because the group operation is invertible and associative. Associative means (P + Q) + R = P + (Q + R). I have not proven for you that the group operation is associative because it’s annoying and I don’t want to. You can do it if you want. But the group operation is associative.

Suppose K*P = N*P, where K < N. So for instance 4*P = 15*P.

We obtain successive points by adding P to the most recent point. So it must be true that (N-1)*P = (K-1)*P, (N-2)*P = (K-2)*P, etc.

That is, it’s not just that N*P = K*P, but also their neighbors are equal, and by extension, it’s just the sequence repeating itself.

If we play this back far enough, it should be clear™ that (CycleLength - 1)*P = infinity, because infinity is the point where when you add P to it, you get P.

This is a little bit more intuitive if you think of orbits as literal orbits:

The orbit is continuous and 1-dimensional. There’s no way for you to be 1/3 of the way around the sun and suddenly find yourself 4/5ths of the way around the sun. That’s not how time works. If you find yourself in a place you’ve already been, it’s because you cycled all the way around.

Another angle that might be helpful is to think of there being a homomorphic (structure-preserving) mapping from

(Integers mod CycleLength) -> OrbitOfGenerator

Analogously, there’s a homomorphic mapping

(Time mod LengthOfThatPlanetsYear) -> ThatPlanetsCurrentLocation

4 How to build a cryptography scheme out of this

Another thing that should jump out at you from the graphs of orbits of points is that they’re pretty janky and kind of random.

There are two ingredients we need in a cryptography scheme:

1. structured randomness
2. computational asymmetry

This asymmetry is given to us from the fact that given N and P, it’s very very fast to compute N*P. You can do this in O(log(N)) time, actually, from the binary representation of N, using successive doubling:

7*P = 4*P + 2*P + P
4*P = 2*P + 2*P
2*P = P + P

The opposite is not true: suppose you are given GeneratorPoint and TargetPoint, and you know TargetPoint is in the orbit of GeneratorPoint.

It is hoped/believed to be computationally infeasible to find the N such that N*GeneratorPoint = TargetPoint.

Very basically:

EASY/FAST:
(N, GeneratorPoint)           -> TargetPoint = N*GeneratorPoint

IMPOSSIBLE:
(GeneratorPoint, TargetPoint) -> N

5 What is a keypair?

OK we’re ready.

You ready?

So, I said earlier that an elliptic curve is defined by a pair of equation parameters {A, B}. But, like IRL, the definition of the curve that you’re actually going to use is {A, B, PrimeModulus, GeneratorPoint}.

Ready?

• Your secret key is a very large random number N.
• Your public key is the point N*GeneratorPoint

Ta-da!

6 Classroom application: Elliptic Curve Diffie-Hellmann

Let’s suppose that I want to talk with my friend Craig in secret, but all of our communication is in a public channel. We can actually use what we’ve done so far to accomplish this task. I wrote “classroom application,” but the concept here is a foundational technique that is used pretty much every single time two computers talk to each other on the internet.

So Craig picks his private key

CraigPrivateKey = 69

and doesn’t tell anyone. There’s some agreed upon elliptic curve, modulus, and generator. That information can be public, it doesn’t really matter.

Craig tells me, in public, the coordinates for

CraigPublicKey = {CPubX, CPubY} = ec_point_multiply(CraigPrivateKey, GeneratorPoint)

He doesn’t share the number CraigPrivateKey with anyone.

I can verify that Craig’s point CraigPublicKey is indeed on the curve, but there’s no way for me to figure out that his secret key is 69.

In practice of course, we would never use cartoonishly small numbers like 69. that can be brute-forced. That’s why this is a classroom example, because the numbers are small, not because the concept is infantile.

Likewise, my private key is

PeterPrivateKey :: int()
PeterPrivateKey = 420

I share in public

PeterPublicKey :: point()
PeterPublicKey = {PPubX, PPubY} = ec_point_multiply(PeterPrivateKey, GeneratorPoint)

Remember, Craig’s public key is 69*GeneratorPoint and my public key is 420*GeneratorPoint.

In private,

• I add CraigPublicKey to itself PeterPrivateKey times. So I compute

  SharedSecret :: point()
  SharedSecret = ec_point_multiply(PeterPrivateKey, CraigPublicKey)

  Note I am NOT multiplying the generator by anything. I am multiplying Craig’s public key by my private key.

• Craig does the same thing: he takes his private key times my point:

  SharedSecret :: point()
  SharedSecret = ec_point_multiply(CraigPrivateKey, PeterPublicKey)

Both of us have computed (69 * 420) * GeneratorPoint, although neither of us knows that the coefficient attached to GeneratorPoint is 69*420.

Crucially, nobody except me or Craig can compute this SharedSecret (which is a point).

We can then, separately and privately, use the coordinates for SharedSecret as the seed for a random number generator that we agreed upon beforehand (even in public).

Let’s say (in binary) that my message to Craig is 1111_1111 1111_1111 1111_1111. The scheme goes as follows:

my message   = 1111_1111 1111_1111 1111_1111
random bytes = 0111_0000 1101_1101 1010_0010
xor          = 1000_1111 0010_0010 0101_1101

The xor operation is its own inverse. So Craig simply does the opposite:

encrypted msg = 1000_1111 0010_0010 0101_1101
random bytes  = 0111_0000 1101_1101 1010_0010
decrypted     = 1111_1111 1111_1111 1111_1111

From the perspective of an attacker trying to decipher our communications, the xor cipher amounts to randomly flipping bits in the encrypted message.

In general, the goal of any cryptography scheme is to make the encrypted data look like random garbage to the untrained eye.

If Craig and I could convene in secret and agree on some shared secret, none of this would be necessary. The premise here was that Craig and I lacked the ability to come up with a shared secret in secret, so we had to come up with a shared secret in public.

This basic idea is what is actually used when your computer and Amazon need to talk privately on the public internet.

7 Disclaimers (Introduction)

I hate when the introduction to an article is at the beginning. I always want to get straight down to business so the introduction is here.

I don’t really care for rigorlicious mathematics. The concept here is to use the prose exposition portion to gain intuition over the mathematics, and then use programming as the setting to formalize the math and make sure we dot all our ts and cross all our is. So be forewarned that a lot of corners are being cut in the mathematical exposition here.

Also note that this article is meant to be a starting point, not an endpoint. You are supposed to use this article as something that gives you broad outlines of the concepts and ideas, and then go pursue any questions you have on your own. If I wrote an article that rigorously covered every base, it would be so rote and dense that you wouldn’t want to read it, and more importantly, I wouldn’t want to write it.

8 Looking forward (Conclusion)

I definitely want to write out all of this in overly clear, straightforward code.

In the meantime, Hans Svensson’s ec_utils library is a good starting point. It makes perfect sense to me (someone who already understands the code). From the POV of someone trying to understand this for the first time, it might be a bit intimidating. I’m not sure. It’s worth a look-see.

I definitely want to dive in a bit into projective geometry and modular arithmetic. I owe you an explanation for how modular division could be done efficiently.³ There’s also a lot of exploration we can do into logic and language design that I’m excited to illustrate.

Next post is probably modular division, then maybe some formal logic.

9 Appendix: a brief look at projective geometry

As a young math pupil, it always bothered me whenever some weird corner situation like the point-at-infinity showed up, and the explanation for it was “well you’ll learn about that later”.

I’m going to give a very brief shallow dive into a world of geometry called projective geometry, which not only contains a “point at infinity”, but in fact an entire “line at infinity”. Projective geometry deserves a deeper dive, but I’m going to give you the elevator pitch for now.

The basic concept can be seen in that painting above: projective geometry always has an implicit “point of perspective”. To draw the mandolin, you:

1. take a sample of points on the mandolin
2. draw a straight line from each sample point to the eyeball
3. intersect each line with the viewing plane
4. result is the sample of points on the viewing plane

It was during the European renaissance that projective geometry grew its beard and became an obviously distinct field of math. The primary motivation actually came from the world of art: projective geometry is precisely the language of geometry you need in order to do draw forced perspective accurately.

The crucial insight they had was as follows: each family of parallel lines meets at a point on the horizon.

The key notion is perspective:

• if you’re looking straight down at the parallel lines, they don’t meet
• if you’re looking at them from an angle, they meet, but “off the page”
• within the context of the flat-earth coordinate system:
  • the horizon is the “line at infinity”
  • each point on the horizon is a “point at infinity”

This is essentially what the point-at-infinity is: there’s a bigger 3-dimensional picture in which the point-at-infinity operates just like any other point. We are looking at a 2-dimensional slice of it and pretending that’s the whole universe. That works perfectly well except for this one little teeny point of leakage. So we plug that leak by calling it infinity.

I’ll leave you with a more elaborate example.

9.1 Example: pole/polar construction

Don’t get too caught up in the detail here. The takeaway I want you to have from this is simply if you take two shapes in 3d and intersect them the result is often interesting on its own terms.

The earliest substantial work that in hindsight was projective geometry was the work of Apollonius of Perga (ca. 200 BC), who studied [conic sections].

The idea is to take two cones tip-to-tip, then intersect it with a plane, then study the curve on which they intersect.

The most basic construction that is interesting is the relationship between poles (points) and polars (lines). Interestingly this construction works identically for all types of conics

Steps:

• Take any conic (move around the solid gray points)
• Take an arbitrary point Pole (move around the red point) anywhere on the plane
• Our goal is to construct the Polar line (solid red line)
• Pick two arbitrary points on the conic (the solid blue (SB) and solid orange (SO) points)
• Join the pole to each of those two points (blue line/orange line)
• Find the other intersections (hollow blue/orange points HB and HO)
• Join hollow-blue to solid-orange, call this line HB-to-SO
• Join solid-blue to hollow-orange, call this line SB-to-HO
• The meet of HB-to-SO and SB-to-HO is CrossPoint
• Join hollow-blue to hollow-orange to get HB-to-HO
• Join solid-blue to solid-orange to get SB-to-SO
• The meet of HB-to-HO and SB-to-SO is SamePoint
• The Polar is the join of CrossPoint and SamePoint

Interesting properties (play with yourself!):

• This construction works on any conic (move around the solid gray points)
• This works irrespective of whether the pole is inside, outside, or on the conic
• This construction does not depend on the choice of SB and SO; that is, the resulting polar is only a function of the pole and the conic
• The intermediate values (HO, HB, CrossPoint, SamePoint, etc) change depending on the choice of SB and SO, but the construction always ends up with the same Polar line.
• The polar of CrossPoint is the join of Pole and SamePoint
• The polar of SamePoint is the join of Pole and CrossPoint
• The construction is symmetrical: if you instead started with the Polar line, take two points on it, compute their polars, then the intersection, you get the Pole: