S·P·Q·R

### {a,k}@kparc.io # S·P·Q·R <blockquote> The two legal entities mentioned are sovereign when combined. <footer>The regents of kparc</footer> </blockquote> This is a tale about two friends who knew the price of making wrong assumptions. Their names are __*Alice*__ and __*Bob,*__ and they are proverbial heroes of a story called cryptography. ## Key Exchange <blockquote> Two households, both alike in dignity, In fair Verona, where we lay our scene. <footer>“Romeo and Juliet”, Act I, Prologue</footer> </blockquote> Once upon a time, Alice and Bob decided that they want to exchange messages in private. They took it seriously and began by inventing an unbreakable algorithm to encrypt their messages — only to face a major difficulty. For their algorithm to work, they realize, they must somehow agree on some ==encryption key==, only known to them and them only. This is what their algorithm requires for both encryption and decryption to work on both ends. This would be an easy task if they could meet in person or rely on a trusted messenger, but sadly they don’t have that luxury for some reason. What is known instead is that the only communication channel at their disposal is ==compromised== — please meet __*Eve The Eavesdropper,*__ a third party who isn’t friends with Alice and Bob. Not only Eve can intercept their communications — she is known to be very intelligent and completely devoid of human decency. Luckily, Bob and Alice are not unaware of Eve, and they devise a plan. To explain how their plan will work, let’s imagine a world where no efficient division algorithm has yet been discovered. This would mean, for example, that while we can still compute $57\cdot 42$ in very little time, computing $\frac{2394}{57}$ would take us a few million years because we don’t know a faster way. Alice and Bob begin by sharing a ==compromised key== — let’s call it $G$. That would simply be a large random number, which they don’t mind to be intercepted by Eve. Then, both would pick an additional random number — suppose Alice picks $a$, and Bob picks $b$. These numbers, let’s call them ==private keys==, they will keep secret — also from each other because sharing them with anyone would mean sharing them with Eve. Instead, they do the following. Bob would use $b$ to compute a __*product,*__ which is very fast: $$B=b\cdot G$$ And Alice would do the same with $a$: $$A=a\cdot G$$ These two numbers, $A$ and $B$, are their ==public keys== — and they openly exchange them too. Now that Alice knows $a$ and $B$, and Bob knows $b$ and $A$, they can both compute: $$S = a\cdot B = b\cdot A = a\cdot b\cdot G$$ And $S$ becomes their ==shared secret==, which they can safely use as their encryption key. This is a bad day for Eve. Although she is very much aware of how exactly Alice and Bob arrived at $A$ and $B$ and is also in possession of $A$, $B$, and $G$, she is helpless to *reverse* multiplication to obtain either $a$ or $b$ to arrive at $S$. To do so, she would need to invent a fast division method — which, as intelligent as she is, she is not smart enough to do, or so Alice and Bob hope. Of course, in the world we live in, efficient division algorithms have been known for a while, and Eve can compute the shared key with little difficulty: $$S=\frac{A\cdot B}{G}$$ However, we note that the essence of the idea of deriving a shared secret over an insecure channel is perfectly sound. This algorithm has been known at least since 1969 but remained classified until its rediscovery in 1976. It became known as ==Diffie-Hellman== key exchange protocol, or DH handshake, or simply $DH$. Today, this idea is used in the vast majority of communication systems, and we all rely on it countless times per day — $DH$ is the foundation of ==public-key cryptography==. ## One-way Functions <blockquote> I live on a one-way street that is also a dead end. I'm not sure how I got there. <footer>Steven Wright</footer> </blockquote> What Alice and Bob seem to need is a real mathematical device sharing the same property — some computation that is very easy and effortless to perform in one direction, and as difficult and inefficient as possible to perform in another. Such devices do exist, and they are known as ==one-way functions==. A __*good*__ one-way function should be based on a mathematical problem that would leave little hope of somebody ever discovering an efficient method of escaping the one-way “trap”, which will instantly compromise all communication channels that ever relied on it. An __*ideal*__ one-way function, as you would guess, should leave no such hope at all — but proving that ideal one-way functions even exist is by itself one of the greatest unanswered questions in the history of science. This problem, known as ==P vs. NP==, might easily be the hardest possible way to earn $10^6$ dollars, but that’s a story for another day. As of current, certain one-way functions are considered __*good enough*__ to be safe for use in cryptography. Different classes of such functions rely on different mathematical ideas, with their own strengths and weaknesses. You could be asking yourself: “hold on, but what if someone could also modify what goes between Alice and Bob, instead of passively observing it?”. You are naturally wired to think like a cryptographer, and please welcome __*Mallory The Attacker.*__ Indeed, dealing with active attacks requires a modified DH protocol which provides ==authenticity== — a guarantee that Alice and Bob are talking to each other. For that, DH is typically used in combination with the ==Digital Signature Algorithm==, an idea that also relies on one-way functions. So, we must first deal with Eve — and that means we need to find a cryptographically strong one-way function, which sounds somewhat complicated. _Not at all._ Here's the math we will need: $+$ add $×$ multiply $x^n$ raise to the power $x^{-1}$ reciprocal, same as $\frac{1}{x}$ $\mathrm{mod}$ remainder $=$ equal $\ne$ not equal $\approx$ about the same $|x|$ number of elements $∈$ member of $∪$ union $\mathbb R$ the reals $\mathbb Z$ the integers ${\mathbb Z}_p$ the integers modulo _p_ $\equiv\ \ (\mathrm{mod}\ p)$ equivalent modulo _p_ $\infty$ infinity There exists a state-of-the-art family of such functions that provides excellent security using a handful of simple and elegant ideas given to us by brilliant young minds. These ideas are easy to explain and easy to understand and come together in a truly remarkable way. ## Galois Fields <blockquote> Your paper was returned with a report which we quote: «The author claims that the prepositions contained in his manuscript are a part of some general theory which has rich application. We have made every effort to understand his proofs . . . it is not even possible to give an idea of what his paper is about.» We hope you’ll find these remarks useful in your future work. <footer>The Secretary to the French Academy of Sciences</footer> </blockquote> The name of a man who once wrote this letter is among the 72 names engraved on the sides of the Eiffel tower in homage to the great men of French science. In a twist of fate, the name of a man whom he quotes in this letter is engraved right next to his. In contrast, the name of a man who once received this spirit-crushing verdict will be forever engraved in ever so many hearts. The name is Évariste Galois, a brilliant French mathematician who didn’t live to see his 21^st^ birthday — but this is not the reason why a mathematical structure also known as __*the finite field*__ is called ==Galois field== in his honor. In 1830, two years before his tragic death, young Galois elucidated the importance of what turned out to be ubiquitously useful in modern mathematics and is instrumental in many cryptographic applications. The idea of a Galois field is simple, and they are easy to construct. Let’s pick a prime number: $$p=7$$ We can reduce the familiar __*infinite*__ set of all integers $\mathbb Z$ to a __*finite*__ set of just $7$ elements by wrapping the number line around an imaginary circle of circumference $7$. All integers that fall on the same point on a circle are considered equal. In other words, $0,\ \pm7,\ \pm14, \dots$ will all represent the same __*element*__ of a finite field, and so will $1,\ 1\pm7,\ 1\pm14, \dots$ That is, for any $i\in{\mathbb Z}$: $$i=i\pm 1p=i\pm 2p\dots$$ We could also say that for any integer $i$ there exists a corresponding element $e$ in a finite set of order $p$ which is obtained by finding the remainder of its division by $p$. Concisely, $e$ is the same as $i\ modulo\ p$: $$e = i\;\mathrm{mod}\; p$$ The elements of a set are thus represented by numbers $0$ thru $6$, which is a common convention, but for our purpose it will be more convenient to use $-3$ thru $3$, which is merely a cosmetic change: $$e = (i\;\mathrm{mod}\;7) - 3$$ The crucial property of such a finite set is that we can define the elementary arithmetic on it. In our case, multiplication and addition are defined as follows: if the result of ordinary addition or multiplication falls outside of the $[-3,\, 3]$ range, we shift it by a multiple of $7$ to bring it back into the range. Now that the arithmetic is defined, we have a Galois field of order 7, or $GF(7)$, complete with the following addition and multiplication tables: |$+$|$-3$| $-2$|$-1$| $0$| $1$| $2$| $3$| |--:|---:|---:|---:|---:|---:|---:|---:| |$-3$| $1$| $2$| $3$|$-3$|$-2$|$-1$| $0$| |$-2$| $2$| $3$|$-3$|$-2$|$-1$| $0$| $1$| |$-1$| $3$|$-3$|$-2$|$-1$| $0$| $1$| $2$| | $0$|$-3$|$-2$|$-1$| $0$| $1$| $2$| $3$| | $1$|$-2$|$-1$| $0$| $1$| $2$| $3$|$-3$| | $2$|$-1$| $0$| $1$| $2$| $3$|$-3$|$-2$| | $3$| $0$| $1$| $2$| $3$|$-3$|$-2$|$-1$| #### Fig.1: Addition mod 7 |$\times$|$-3$|$-2$|$-1$| $0$| $1$| $2$| $3$| |---:|---:|---:|---:|---:|---:|---:|---:| |$-3$| $2$|$-1$| $3$| $0$|$-3$| $1$|$-2$| |$-2$|$-1$|$-3$| $2$| $0$|$-2$| $3$| $1$| |$-1$| $3$| $2$| $1$| $0$|$-1$|$-2$|$-3$| | $0$| $0$| $0$| $0$| $0$| $0$| $0$| $0$| | $1$|$-3$|$-2$|$-1$| $0$| $1$| $2$| $3$| | $2$| $1$| $3$|$-2$| $0$| $2$|$-3$|$-1$| | $3$|$-2$| $1$|$-3$| $0$| $3$|$-1$| $2$| #### Fig.2: Multiplication mod 7 For example, $3\times 3$ gives $9$, which falls outside $[-3,\, 3]$, so we shift it by $7$ and arrive at $2$. No shift is required for $1+1=2$, which is not the case for: $$2+2=4-7=-3$$ And it so happens that the one-way function we are looking for exists in the alternate reality of Galois fields, where everything makes perfect sense, only $2+2$ is not necessarily Welcome to mathematics, Eve The Eavesdropper. $4$. While the tiny field of order $7$ has everything we need to illustrate how that function works, it is worth observing that: ___ **1. Every element of a finite field is itself an ==infinite set==.** **2. Galois fields are finite, but there are infinitely many Galois fields.** ___ It is also hard to overlook some pronounced symmetry-like patterns that arise in both tables above, which is one of the reasons to prefer the $[-3,\, 3]$ range. But a truly important fact is a bit harder to spot: except for two notable exceptions in the multiplication table produced by multiplying by $0,$ every other row and column contains every field element *exactly once,* i.e. every such column and row contains the complete set of elements of the field. It easy to see why the same must be true for any other $GF(p)$, on one small condition: $p$ must be a ==prime number==. Using the multiplication table above, we can easily derive the values of $x^2$ and $x^{-1}$ for every $x\in {\mathbb Z}_7$. In the table below, the second column is simply the main diagonal of the multiplication table, and the third column is constructed by locating $1$’s in its every row: | $x$ | $x^2$ | $x^{-1}$| |-----:|------:|--------:| | $-3$ | $2$ | $2$ | | $-2$ | $-3$ | $3$ | | $-1$ | $1$ | $-1$ | | $0$ | $0$ | $—$ | | $1$ | $1$ | $1$ | | $2$ | $-3$ | $-3$ | | $3$ | $2$ | $-2$ | #### Fig.3: Square and inverse mod 7 Note that the multiplicative inverse of $x$, or its ==reciprocal==, is given as $x^{-1}$ instead of $\frac{1}{x}$, which is the same thing. This is a deliberate choice because it naturally takes to a tremendously important realization: in a finite field, there is no need for the tricky concept of __*fractions.*__ In the world of finite fields, where $\frac{1}{3}$ looks like $-2$ instead of $0.3333333\dots$, the division is essentially a free operation. This is one of the reasons why Galois fields are instrumental in $ECC$ — discrete modulo arithmetic is extremely fast. Not only computations in real numbers are dramatically slower — they are generally unsuitable for cryptography due to severe practical limitations of how ${\mathbb R}$ can be represented and dealt with by a binary computer. Generally speaking, it is impossible to represent a real number $r\in{\mathbb R}$ using __*any finite amount of computer memory.*__ For example, there must exist at least one $r$ that encodes not only all texts ever written by humans in the past, including the one in front of you, but also all texts that will ever be written by humans in the future, followed by DNA sequences of all their authors for the sake of completeness. This fact alone is enough to make cryptographers appreciate the set ${\mathbb R}$ from a very safe distance. For other purposes, floating-point arithmetic is governed by an international standard known as ==IEEE 754== which defines a reasonably fast and sufficiently precise approximation of arithmetic over real numbers. ## Elliptic Curves <blockquote> “And what is the use of a book,” thought Alice, “without pictures or conversations?” <footer>Lewis Carroll</footer> </blockquote> Consider a cubic equation in two variables: $$ y^2 = x^3 + a\,x + b $$ Since we reserved $a$ and $b$ to refer to Alice and Bob’s private keys, let’s reassign coefficients to avoid confusion: $$ y^2 = x^3 + \alpha\,x + \beta \tag 0 $$ A class of curves specified by the equation $(0)$ is so famous that it has its own beautiful name in mathematics. To qualify for that name, such a curve must meet an additional requirement: the coefficients $(\alpha,\beta)$ must be chosen so that the curve does not have cusps or self-intersections, collectively referred to as singularities. In other words, the curve must be ==non-singular==, or more formally: $$ {\displaystyle 4\alpha^{3}+27\beta^{2}\neq 0} $$ Once this requirement is met, such a curve is called an ==elliptic curve,== or $EC$ for short. Here are some examples of valid elliptic curves: ![](https://i.imgur.com/UerQZtS.png "Examples") The following two curves are not elliptic curves, since both of them have singularties, marked in red. Simply put, a ==singularity== is a point on a curve at which no single unambiguous tangent line can be drawn: [1] [2] __*Elliptic curve*__ is a striking and elegant name, but it creates a false impression that their appearance must have something to do with ellipses. In reality, as any curve defined by a cubic polynomial, an elliptic curve is a ==cubic plane curve==, or simply a __*cubic.*__ In turn, an ellipse is a __*conic,*__ which is defined by a quadratic polynomial. What contributes to the perpetual confusionRice, A., Brown. E., <a target="_blank" href="ref/Rice2013_WhyEllipsesAreNotEllipticCurves.pdf">Why Ellipses Are Not Elliptic Curves</a> (2013)<label for="" class="margin-toggle sidenote-number"></label> is the distinctive feature of certain elliptic curves, which is an __*oval*__. This shape has no exact definition in mathematics and is therefore not an ellipse, which does have one. The term comes from the Latin __*ovum*__ to describe any shape that loosely resembles an egg, which is not always true for elliptic curves either. Elliptic curves borrow their name from their equation, which was closely studied in the 19^th^ century in the context of an important problem related to ellipses. If we recall that the shape of the Earth’s orbit around the Sun is an ellipse, then any part of its orbit must be an ==elliptic arc== — and elliptic functions are called that way because they emerge in the mathematical machinery of elliptic arcs. It was not until the late 20^th^ century when it has been discovered Miller, V. S., <a target="_blank" href="ref/Miller1986_UseOfEllipticCurvesInCryptography.pdf">Use of Elliptic Curves In Cryptography</a> (1986)<label for="" class="margin-toggle sidenote-number"></label> Koblitz, N., <a target="_blank" href="ref/Koblitz1987_EllipticCurveCryptosystems.pdf">Elliptic Curve Cryptosystems</a> (1987)<label for="" class="margin-toggle sidenote-number"></label> that elliptic curves have an unexpected application in cryptography. After twenty years of research, elliptic curve cryptography, or $ECC$, has entered wide use and is now ubiquitous. ___ Let $C$ be __*an elliptic curve over a finite field of order $p$*__: This notation was introduced into mathematics by __*Carl Friedrich Gauss.*__ Given the integers A, B and p, the expression A ≡ B (mod p) means that A-B is an integer multiple of p, and pronounced as “A is equivalent to B modulo p”. $$ C: y^2 \equiv x^3 + \alpha\,x + \beta\ \ \ \ ({mod}\ p) \tag{1} $$ For the curve $C$, there exists a way to construct a one-way function based on a mathematical problem that is believed to be computationally infeasible. ___ We are now ready to study elliptic curves over the field $GF(7)$. Since the ==cardinal number== of a finite field of order $p$ is also $p$, our field has $7$ unique elements: $$|GF(7)| = 7$$ This means there must be exactly $7^2=49$ distinct pairs of $(x,y)$ where $x$ and $y$ are drawn from $GF(7)$. An elliptic curve defined over a finite field can be neither *contiguous* nor *smooth,* which doesn’t seem to qualify for a *curve* in the traditional sense. Indeed, it becomes a discrete set of pairs $(x,\,y)$ that satisfy the equation $(1)$ parametrized by some given pair $(\alpha,\,\beta)$. > However, it still very much a curve in every right — only to plot it, we would need more than two dimensions, but we don’t have to. For our purpose, the elliptic curve modulo $p$ can be pictured as a set of discrete points on a flat surface. Since there are only $49$ possible pairs $(\alpha,\,\beta)$, there must be exactly $49$ distinct elliptic curves we can define over $GF(7)$. The task at hand is to select one single curve which will become the foundation of our cryptographic system. This is a critical decision that cannot be undone, so we must be sure to pick a curve that provides the best possible cryptographic strength — and for that, we must identify which criteria to consider, i.e. which properties constitute “best”. With the aid of a simple computer program, we can iterate over all possible curves and find all pairs $(x,\,y)$ which are their valid solutions. The table below displays the number of solutions for every possible elliptic curve over $GF(7)$: |$\small \alpha\backslash \beta$|$-3$|$-2$|$-1$|$0$| $1$|$2$| $3$| |---:|---:|---:|---:|--:|---:|--:|---:| |$-3$| $9$| $6$|$10$|$7$| $4$|$8$| $5$| |$-2$| $9$| $6$| $3$|$7$|$11$|$8$| $5$| |$-1$| $9$| $6$| $3$|$7$|$11$|$8$| $5$| | $0$| $2$| $6$| $3$|$7$|$11$|$8$|$12$| | $1$| $9$| $6$|$10$|$7$| $4$|$8$| $5$| | $2$| $9$| $6$|$10$|$7$| $4$|$8$| $5$| | $3$| $9$| $6$| $3$|$7$|$11$|$8$| $5$| #### Fig.4: Number of solutions for $y^2 \equiv x^3 + \alpha x + \beta\ ({mod}\ 7)$ It is evident that some curves are considerably “larger” than others. Indeed, the curve: $$y^2 = x^3 + 3x - 1$$ has only 3 points, while the following curve has 12: $$y^2 = x^3 + 3$$ The common wisdom “bigger is better” hints at the curve with maximum points — but there is a compelling reason to prefer a curve with 10 points instead, which is covered in detail in __*Appendix I*__. There are only three such curves to choose from, and for now, we will take a leap of faith and pick the following curve: $$y^2 = x^3 + x -1 \tag 2$$ Note that this is only a provisional choice — we simply need a vehicle to advance. In the world of real cryptography, tossing coins and taking chances at the design stage is the mother of all disasters. A poorly designed cryptosystem could be the sole cause of untold damages and sorrow, and designing them is an activity reserved for highly skilled professionals who know what they are doing and understand the responsibility they bear. For the rest of us, the only actionable rule of applied cryptography is “never roll your own”. ## The Group Law <blockquote> If needed be, one might take the hero to be a symbol of the human spirit, but one ponders the deeper significance of the two monsters in vain. Are they the conquered quintic equations or elliptic functions? Or the sorrows and cares of his everyday life? The pedestal of the monument bears, in immense letters, the inscription ABEL. <footer>Felix Klein, “Development of mathematics in the 19th century” (1926)</footer> </blockquote> Elliptic curves are useful in cryptography because they enjoy a very special property which is easier to illustrate over real numbers. **Point and drag to draw arbitrary straight lines over the following curve:** [1] We observe that any non-vertical line intersects with the curve in at most three places, and is guaranteed to intersect it at least once. If we recall that $EC$ is defined by a cubic equation in two variables, which cannot have more than three solutions, we are safe to assume that this property must hold for any valid elliptic curve. **Click or tap to pick a random point on the following curve:** [2] We observe that any non-vertical tangent line of an elliptic curve intersects with it exactly once. We also note the obvious fact that elliptic curves are __*symmetric,*__ i.e. for any point $(x,y)$ on a curve, there exists a mirror point $(x,-y)$ for any $y\ne0$. These properties are of crucial importance for our purpose, but sadly do not hold in the special case of vertical lines — and it is possible to escape this limitation. The way out is first to observe that a straight line drawn with an infinitely small deviation from $90$ degrees still intersects with the curve, only at some infinitely distant point. We can build on that fact by agreeing that a perfect vertical line also has an intersection with an elliptic curve at a special imaginary point, called ==point at infinity==. It might sound a bit like hand-weaving at first, but a vanishing point at $\infty$ is of key importance. Once we agree that such a point is permitted to exist on a plane, the immediate consequence is that there are no parallel lines on it — any two lines must intersect sooner or later, even if at some infinite abstract point. We arrive at the following key observation: --- __*With the inclusion of a special point at $\infty$, **any** straight line drawn through any two points on an elliptic curve intersects the curve at a third point, and there can only be one such point.*__ --- To acquire some intuition why this must be true, it helps to revisit the metaphor we have used to construct a Galois field. Since the process of wrapping the number line around a circle with a finite number of points can be continued forever, each element in a finite field maps to an infinite number of integers. What follows is that upon hitting the “edge” of a Galois space, a straight line wraps around it and emerges from the other side, much unlike the snake from the classic computer game, which dies on impact. On the contrary, the protagonist of another classic computer game called ==Asteroids==, a __*spaceship*__, is able to wrap around screen edges in any direction. The key difference is that the “elliptic spaceship” doesn’t even need to take any turns — it is set off to travel through space __*at an angle*__ defined by two EC points and __*always*__ arrives at a third point on the same curve — and there can be only __*one*__ such point. It doesn’t matter how many times the ship has to traverse the edge of space before eventually reaching the third point — what matters is that it always will, even if __*at infinity.*__ --- An elliptic curve defined by the equation $(2)$ is a set of $10$ points, and a line drawn through any two of them produces exactly one other point from the same set, which can be visualized as follows: ![](https://blog.cloudflare.com/content/images/image01.gif) --- Before we proceed, it helps to think of this peculiar property of elliptic curves in a more abstract way: What we have is a set of some elements for which there exists an _operation_ that takes any two elements from a set and produces a third element from the same set, the same way ordinary addition works over integers — only in our case the set is not infinite. It is easy to see how an operation can be defined for certain finite sets as well, if we recall the famous set of __*paper, rock and scissors*__. Indeed, there exists an operation defined for this set, and its properties are universally known — only it doesn't have an established __*name*__, simply because it is unnecessary — the properties of that particular operation are universally known under the name of the game in which it is meaningful. In mathematics, however, nothing prevents us from choosing any naming convention if it seems convenient to communicate sense, and we are free to refer to the action of combining two EC points to produce a third point as __*point addition.*__ Similarly, nothing prevents us from denoting this operation by some symbol, and we will use $⊕$. First, let's define this operation in a more formal way: --- 1. **Point addition** of two points $P=(x_1,y_1)$ and $Q=(x_2,y_2)$ is defined as drawing a straight line through $P$ and $Q$ to obtain a third point of intersection, and mirroring it over the $x$-axis, which gives a point $R=(x_3,y_3)$ on the same curve: $$P⊕Q=R.$$ 2. **Point doubling** of a point $P=(x_1,y_1)$ is defined as drawing a tangent line at $P$ and mirroring the second point of intersection over the $x$-axis, which gives $R=(x_2,y_2)$: $$P⊕P=R.$$ In real numbers, addition and doubling are visualized as follows: ![](https://i.imgur.com/O2fENah.png) This visual cue helps to observe an obvious property: --- 3. **The point addition is commutative.** That is, for any $(P,Q) \in C$, a line drawn through $P$ via $Q$ is the same as the line drawn through $Q$ via $P$, i.e. we have: $$P⊕Q=Q⊕P.$$ At this point, we must ask a less obvious question: why did we define point addition and doubling such that they involve the final __*mirroring step*__? The answer is simple — without this step, the $⊕$ operation would not satisfy another crucial property: --- 4. **The point addition is associative**. For any $(P,Q,R) \in C$, the following is true: $$P⊕(Q⊕R)=(P⊕Q)⊕R.$$ This property is much less self-evident than the previous, and requires a formal proof. It can be demonstrated in a purely algebraic way, which is somewhat bulky. However, associativity of $⊕$ also follows from a creative application of a famous <a target="_blank" href="https://en.wikipedia.org/wiki/Cayley%E2%80%93Bacharach_theorem">Cayley–Bacharach theorem.</a> result<label for="" class="margin-toggle sidenote-number"></label> which gives an excellent visual intuition why this property holds. Moving on, we must also formalize the mind trick which deals with vertical lines: --- 5. For the $⊕$ operation to hold universally, we must redefine all of the above for an extended set of curve points $\overline C$ which includes the special point at $\infty$ which guarantees the existence of $R$: $$\overline C = C \cup \{\infty\}.$$ Furthermore, in the set $\overline C$, the point at $\infty$ plays the same role as $0$ for addition of integers, and $1$ for multiplication: --- 6. **The point at $\infty$ is the neutral element of the set.** For any $P\in \overline C$, the following is true: $$P⊕\infty = \infty⊕P=\ P.$$ Moving on, as we discussed earlier, elliptic curves exibit symmetry over $x$, and we can formalize it as follows: --- 7. **Every element in $\overline C$ has an inverse.** For any $P = (x,y)\in \overline C$, there exists $Q = (x,-y)\in \overline C$ such that $$P⊕Q = Q⊕P = \infty$$ $$\Downarrow$$ $$Q=-P.$$ Finally, for the sake of completeness, let's formalize the idea that the $⊕$ operation involves the mirroring step: --- 8. **The point $R = P⊕Q$ is an inverse of the third point of intersection on a straight line through $(P,Q)$.** Points $(P,Q,R)\in \overline C$ lie on the same straight line if and only if: $$P⊕Q⊕R = \infty$$ $$\Downarrow$$ $$P⊕Q=-R.$$ --- Statements 1–8 are сollectively known as __*The Elliptic Curve Group Law.*__ This means that the set of points on an elliptic curve qualifies for the definition of a ==group==, a fundamental algebraic structure. Moreover, the group formed by the set $\overline C$ and the operator $⊕$ belongs to a specific, very well understood class of groups. We can restate all of the above in a single concise and profound statement: --- $$The\ triple\ (\overline C,⊕,\infty)\ is\ an\ abelian\ group.$$ --- An ==abelian group==, called that way in remembrance of __*Niels Henrik Abel,*__ meets the requirement that the result of point addition does not depend on the order of operands, i.e. is ==commutative==. Note that we did not define any explicit numeric formula for calculating a sum of two points. There can be more than one concrete method of obtaining the coordinates of the point $R$. Some methods could be simpler to implement, some are more efficient on a specific computer architecture, some designed with certain resource constraints in mind. There can be very efficient ways to exploit properties unique to specific curves over specific finite fields. What we have instead is a general “recipe” for an operation on two elements from a set of points, and a set of axioms this operation satisfies. All concrete methods will implement the very same operation $⊕$, and will obey the same set of rules. We have an abelian group, a simple, robust and unbreakable structure, which enables us to make one final transition to achieve our goal, and it is nothing short of illuminating. ## Elliptic Curve Discrete Logarithm Problem <blockquote> Finally, it must be emphasized that for the moment none of the approaches are practical at all . . . for any key size currently in use. The difficulty to make practical experiments with non-tiny examples is an explanation why the assumptions are hard to (in-)validate. <footer>S. Galbraith, P. Gaudry, “Recent progress on the ECDLP” (2015)</footer> </blockquote> From the Group Law, we can trivially derive an additional operation on the group of points $\overline C$, called ==scalar multiplication==, as follows: for any $P\in\overline C$ and some integer $k\in {\mathbb Z}$, scalar multiplication is defined as point $P$ added to itself $k$ times: $$\underbrace{P\oplus P\oplus\cdots\oplus P}_{k~{\rm times}}= kP$$ __*And this is it.*__ It turns out that scalar multiplication on a group of points on an elliptic curve over a finite field of prime order is a very cheap operation that is very hard to undo. Given: $$kP = Q$$ it is very easy to compute $Q$, while it is very difficult to compute $k$ from a known pair of curve points $(P,Q)$. It takes a moment to fully appreciate this fact, and it helps to think about it less formally. If we recall the analogy of an “elliptic spaceship”: **If $\ P$ is the starting point on an elliptic curve, and $Q$ is the final point, then $k$ is the number of intermediate points visited by the spaceship before it reaches $Q.$** Continuing the analogy, not only the ship is free to traverse the edges of a finite field — during scalar multiplication, the ship makes a sharp and unexpected turn at every intermediate point it visits, and figuring out its exact path by only knowing the start and finish proves to be problematic: --- **For a well-chosen elliptic curve over a finite field, there is no known way of reversing scalar multiplication other than by trying all possible values of $k$.** --- With that in mind, we can try to imagine a spaceship traversing a curve defined over a Galois field of the following order, which happens to be a prime number: $$p =2^{255}-19 = \underbrace{57,896,044,6\cdots364,819,949}_{77~{\rm digits}}$$ Surprisingly, even over a gigantic finite field, computing $kP=Q$ requires very little time regardless of the value of $k$ — it is usually fast enough to be measured in microseconds. The warp drive the spaceship is using to visit a huge number of points with very little effort is nothing secret: it is called ==finite field arithmetic==. On the other hand, for the recovery of a single $k$ from a known pair of points $(P,Q)$ over a field of a comparable order, __*time*__ is no longer a convenient measure; since computation requires __*energy,*__ the following unit of measurement is more helpful. If we rely on the estimate that the full power output of the Sun, or its luminosity $L_{☉}\approx386\;\mathrm{yottawatt}$, is sufficient to boil out Earth's oceans in approximately 4 minutes, we arrive at a ballpark amount of energy ![](img/carrington.gif) The consequences of a __*Carrington-class*__ event. A major coronal mass ejection similar to that of 1859 is an incomparably more gentle release of stellar energy than $E_{dry}$. required to evaporate all water on Earth into outer space: $$E_{dry} \approx 240 \times L_{☉} \approx 92,640\;{\rm yottajoules}$$ This is a convenient frame of reference because an average utility bill for exhaustive search of a single value of $k$ on a decent curve defined over $GF(2^{255}-19)$ would be no less than: $$E_{k}\gt E_{dry}\times10^5$$ --- **To appreciate the magnitude of energies involved in the above inequality, it will suffice to say that it would take significantly less energy than $E_{k}$ to disintegrate the planet Earth into atoms.** --- On a less sentimental note, we conclude that for sufficiently large $(k,p)$ the following is true: * finding $k$ by exhaustive search is neither computationally feasible nor economically viable; * finding a reasonably efficient method of finding $k$ is believed to be out of reach of currently understood science. This problem is known as the __*Elliptic Curve Discrete Logarithm Problem.*__ It is called that way because scalar multiplication can be understood as raising $P$ to the power of $k$ if we re-label point addition operation as point multiplication, which is merely a change of _naming convention._ Then, scalar multiplication becomes: $$P^k = Q$$ And the discrete logarithm problem can then be written down as: $$\log_{P}Q = k$$ The qualifier “discrete” refers to fact that the underlying elliptic curve is defined over a finite field in which it can only have integer solutions. Regardless of the choice of names and symbols that humans consider convenient for their purpose, the scalar multiplication is understood to be a very practical and efficient __*one-way function.*__ ## Elliptic Curve Diffie-Hellman <blockquote> It is possible to write endlessly on elliptic curves. (This is not a threat.) <footer>S. Lang, “Elliptic Curves: Diophantine Analysis” (1978)</footer> </blockquote> Now that Alice and Bob have a one-way function based on the properties of elliptic curves over finite fields, their updated Diffie-Hellman protocol will look like this. First, they agree to use an elliptic curve $C$ defined over a finite field of order $p$. The curve is specified by three parameters, all of which are public: $$С :(p,\ \alpha,\ \beta)$$ Then, they choose an additional public parameter — a special point $G$ on the curve, called ==generator point==, which plays the role of a ==compromised key,== and share its coordinates as well: $$G=(x_g,y_g)$$ Then, each party picks a ==private key==, $a$ and $b$ respectively, which is a random integer such that: $$0\lt (a,b)\lt p$$ They proceed to compute their ==public keys== as follows: $$A=aG$$ $$B=bG$$ And once they exchange their public keys, Alice and Bob compute: $$S_{a} = aB = abG$$ $$S_{b} = bA = baG$$ What they have is a ==shared key==, known to them and them only, which they can safely use to encrypt messages in the presence of Eve: $$\bf S_{a} = S_{b} = S \tag ∎$$ ## Coda <blockquote> Don, do you know where Q comes from in Dual_EC_DRBG? Thanks. <footer>john@nist.gov</footer> </blockquote> Elliptic Curve Cryptography exibits highly desirable properties that some of the competing ideas do not possess. Notable advantages are: 1. The length of keys used in $ECC$ is dramatically shorter compared to other systems, while providing the same level of security. 2. Computational requirements for $ECC$ are comparatively modest, which makes them a go-to choice for resource-constrained environments, most importantly in the booming industry of ==IoT==. 3. Unlike other popular systems, $ECC$ does not rely on the compexity of __*factorization problem,*__ which is very prone to rapid scientific advances. 4. State-of-the-art solutions based on $ECC$, such as ==X/Ed25519==, are free from patents, and are placed into public domain by scientists renowned for their immaculate reputation<a target="_blank" href="http://hyperelliptic.org/tanja/">Tanja Lange</a><label for="" class="margin-toggle sidenote-number"></label>and unquestionable integrity <a target="_blank" href="https://cr.yp.to">Daniel J. Bernstein</a><label for="" class="margin-toggle sidenote-number"></label>. 5. Although the advent of quantum computing packs a promise to render certain one-way functions unsuitable for mission-critical cryptography, as of current there are no known practical attacks on any well-designed system based on the properties of elliptic curves. There's virtually no progress made in this area in the past 15 years. 6. The epigraph to this chapter is an infamous preamble to the worst disaster in the history of modern cryptography, in which a certain party made an attempt to promote a cryptographic standard based on the mechanics of elliptic curves, with the malicious intent to plant a gaping backdoor which would have weakened public cryptography worldwide. Not only this attempt failed miserably. It also irreversibly marred the reputation of a commercial entity behind the main competing idea of a towering achievement of science and engineering known as ==Elliptic Curve Cryptography==. --- The title of this essay is an emblematic acronym which expands to ==Senātus Populusque Rōmānus==, and stands for “The Senate and People of Rome”. For our purpose, it is a useful mnemonic: * $S$ is Alice and Bob's shared key, known to them and them only. * $P$ and $Q$ is the universal convention for labelling two random points on an elliptic curve. * $R$ is the typical label of the point obtained by $P⊕Q$. --- # S·P·Q·R --- This document is hereby placed into public domain by the regents of kparc. There is absolutely no ownership claimed such as copyright, trademark, or patent.