1. Introduction and motivation
The sempiternel question of how to gain and maintain power has haunted the minds of humanity’s brightest and darkest since the dawn of civilization. Be it physical (e.g., military) or economical (e.g., wealth), power’s very existence relied in part on access to information. Asymmetric information that is. Numerous are history’s examples that demonstrate how entities that knew what others didn’t and that were able to act on it, benefited from an unfair advantage. The quest for sustainable power motivates the protection of one’s proprietary information and the attempt at breaching that of the others.
Although significant in its own right, the pursuit of power is not the only motivator to conceal information. Privacy, in so far as the individual’s wellbeing is concerned, is another. In that respect, two areas stand out. The first is concerned with the unique nature of a human persona. As a matter of observation, and at the risk of irritating adherents of monism, the attributes of a human personality are so varied. Each attribute exists on a wide spectrum, making it unlikely that any two individuals have the same profile so to speak. The privacy spectrum is no exception, and while some live their lives as an open book, others might not even be comfortable sharing their half title page. The second area is concerned with the safety of a certain subset of individuals, e.g., whistleblowers. They may hold sensitive information destined to be shared with a specific party. Should this information fall in the wrong hands, it could jeopardize the safety of the source.
It is therefore reasonable to assume that not every piece of information is meant to be common knowledge. One could certainly debate the merits of such a claim and in the process, revisit the very foundation of power, privacy and safety. The fact remains however, that information can be a source of influence, discomfort, and danger. One way of protecting specific content and limiting its access to intended parties only, is through the use of encryption and decryption algorithms.
Symmetrickey vs. public key cryptography: Encryption can be thought of as a map that takes a relevant piece of data known as a message, and outputs an altered version of it. The map can be either one of two types: 1) PTinvertible, or 2) Oneway.
 We say that a function is PTinvertible if one can find a polynomialtime algorithm to compute its inverse. In order for a sender to encrypt a message, he must be able to compute the map. On the other end, in order for a recipient to decrypt the message, she must be able to compute the inverse map. If a map is PT invertible, information used to build it is sufficient to build its inverse. As a result, senders and recipients alike can use the same information to encrypt and to decrypt messages in a process known as symmetrickey cryptography. The symmetric information shared between the sender and the recipient is known as the secret key.
As an example, consider a message space consisting of the caseagnostic latin alphabet of 26 letters. We represent each letter by its numerical equivalent (e.g., letter “a” or “A” represented by 1), and apply the following affine map:
where the superscript denotes a string of arbitrary length, and are predefined elements in such that is relatively prime to 26.
For instance, let and The word “chaos” has a representation given by (3, 8, 1, 15, 19). When fed to the map, one obtains an output given by This corresponds to “nchxj”.
The inverse map can be written as follows:
where is the inverse of in modulo 26 arithmetic (i.e., Since, and 26 are relatively prime, one can use the extended euclidean algorithm outlined in the Groups and Finite Fields post to calculate in polynomial time. Consequently, is a PTinvertible map. All that is required to build it and its inverse is the pair This pair constitutes the symmetric key shared between the sender and the recipient.
Symmetrickey cryptography is known to be efficient, with the possibility of encrypting and decrypting large amounts of data relatively fast. Its weakness however, lies in the fact that the secret key must be shared between two (or more) parties over a secure channel. Enforcing perfect security and eliminating the risk of leakage over a digital communication channel is a challenging endeavour. Moreover, if such a secure medium of communication could be constructed, it would be legitimate to question the usefulness of sharing a secret key in the first place as opposed to using the secure channel to directly send and receive the actual messages.
 Oneway or trapdoor functions have no known polynomialtime algorithm to compute their inverses in the absence of a specific piece of information referred to as the trapdoor. In other words, knowledge of the building blocks of a map is not sufficient to compute its inverse. In order to do so (and as a result decrypt a message), a recipient must have access to the trapdoor.
Algorithms where the information needed to encrypt is different than that needed to decrypt, form the basis of asymmetric cryptography. The nomenclature is a reflection of the informational asymmetry between encryption and decryption. More specifically, each recipient is associated with a key pair consisting of a unique private key only known to her, and a related public key that can be shared with anyone. Anyone can use the public key of a recipient to encrypt a message. Decryption however, requires knowledge of the private key which is only known to the recipient. In light of the above, a crucial criterion in the design of key pairs is that no entity should be able to derive the private key from the public one. The dualkey architecture is the reason why asymmetric cryptography is also known as publickey cryptography.
As an example we consider the RSA encrytion scheme. RSA generates the public and private keys of a user as follows:

Select two very large primes and such that

Let One can observe that given and it is easy to compute . However, given , it is extremely challenging to find and . This is known as the factoring problem, thought to be intractable on the group .

Find ‘s totient value Euler’s totient function returns the number of integers less than or equal to that are relatively prime to . If is prime, then . In addition, for any two coprime numbers and , . Consequently,
 Choose such that and such that . We let be the public key of the user.
 Choose such that . That means that for some integer . We observe that even if were known, it is computationally hard to calculate because this requires computing and which in turn, requires solving the prime factorization problem. This in turn, makes it challenging to calculate We let be the private key of the user. The previous observation shows that it is unlikely for anyone to derive the private key from the public key alone.
To encrypt a message destined to Bob, Alice first transforms it into an integer by using a commonknowledge predefined mapping. We require that and be coprime. Subsequently, Alice computes the encrypted value where is Bob’s public key. In order to decrypt the message, Bob uses his private key to compute To see why this works, note the following equalities:
We can invoke Euler’s theorem that states that if and are relatively prime, then (proof ommitted). We conclude that
Note that when the public key is known, it is straightforward to compute However, calculating its inverse (i.e., finding the value of when and are known) is thought to be hard. On the other hand, knowledge of the private key allows a quick retrieval of as we saw above.

A downside of public key cryptography is that it is not nearly as efficient as its symmetric counterpart, especially as the message size increases. However, symmetrickey cryptography depends on the existence of a secure channel which is challenging to build. The upside of asymmetric cryptography is that it bypasses the need for a secure channel altogether. It turns out that one can leverage the advantage of each type of cryptography to create a hybrid system that is both secure and efficient. This is accomplished through the use of a keyexchange protocol known as a DiffieHellman exchange.
The idea is to simply apply publickey cryptography to communicate a shared secret, which can then be used in a symmetrickey setting to encrypt and decrypt larger messages. Since the secretkey is relatively small (from a data standpoint), it can be encrypted rather efficiently using a publickey setting and then shared with a recipient on an untrusted channel. Larger message blocks can subsequently be effectively encoded and decoded using the secret key. More formally, an example of this setting can be described as follows:
 Consider the multiplicative cyclic group of the finite field of large prime order (The reader can consult the Group and Finite Fields post for more details). Let be one of its generators.
 Alice and Bob chose their individual secret keys from
 They compute their respective public keys
( times)
( times)
 Bob uses Alice’s public key to compute Similarly, Alice uses Bob’s public key to compute
 The two previously calculated values are equal and known only to Alice and Bob. This is because its calculation requires knowledge of at least one of the two secret keys. It can then be used as a shared secret as part of a symmetrickey algorithm.
As noted earlier, the most important design criterion is to ensure that the secret key cannot be derived from the public key. In our setting, this means that when given and no one should be able to calculate in polynomial time the value of This is known as the discrete logarithm (DL) problem and we will revisit it. On the multiplicative group of a finite field of large prime order, the DL problem is thought to be hard.
Digital signatures: Encryption schemes help protect the content. However, they provide no proof that a certain sender was the actual author. This is true especially in the context of publickey cryptography where encryption keys are made public, allowing any party to claim that it was the actual sender. This problem can have drastic consequences when dealing with cryptocurrencies. Indeed, a cryptocurrency transaction consists of a message whose content allows a transfer of spending control from one owner to another. In Bitcoin for example, all valid transactions are publicly registered on the blockchain, and their content is purposefully not encrypted in order to enforce transparency and allow nodes to validate or reject them. However, the message in this case must be accompanied by a proof that the sender is actually the initiator of the transaction. Otherwise, anyone could initate a transaction on behalf of someone else without their consent, potentially causing financial mayhem.
The authentication process is done through the use of a mathematical construct known as a digital signature. In the context of cryptocurrencies, we care about digital signature and less so about encryption. The most important attribute of a digital signature is that of unforgeability. This can be defined in a variety of ways, but for all practical matters we mean resilience against existential forgery in the adaptive chosenmessage attack. More details about digital signatures and the definitions of forgery can be found in the post entitled Digital Signature and Other Prerequisites. Generally speaking, digital signatures use the same publickey cryptography infrastructure described earlier for encryption and decryption. The sender signs with her private key in order to authenticate the message. Anyone on the network can then verify that she was the actual sender by running a verification algorithm that relies on the sender’s public key. Various examples of digital signatures including Schnorr, RSA, generic Pointcheval & Stern models, as well as a number of more elaborate ring signature schemes can be found in previous posts.
The discrete logarithm problem: A necessary condition to avoid forgery is that no one should be able to derive the private key from the public one. Here too, we realize the cruciality of oneway constructs. An important example of such a construct is the one associated with the DL poblem encountered earlier. The hardness of the DL problem on some welldefined groups underlies the security of various digital signature schemes, including those adopted in cryptocurrencies. Formally, we define the DL problem as follows:
 Let be a given group and an element of
 Given an element (i.e., the subgroup generated by ), find an integer such that ( times).
The smallest that satisfies the above equation is known as the logarithm of in base and we write
The difficulty associated with calculating knowing and depends on the underlying group On some groups, the problem is easy to solve (i.e., we know of polynomialtime algorithms that can solve it). On others, it is harder. Moreover, there exists different levels of difficulty, the highest being exponential (i.e., the only known algorithm(s) to solve the problem are exponential in time). In the context of publickey cryptography, it is always desirable to operate on groups where the hardness of the DL problem is exponential.
An example of a group on which the DL problem is easy to solve is (i.e., the group of integers modulo introduced in the Group and Finite Fields post). To see why, first note that this group is cyclic and that the equivalence class is a generator. Given the DL problem consists in finding such that
( times)
By the definition of this is equivalent to finding such that i.e., such that Consequently, one can compute efficiently using the Euclidean algorithm.
An example of a group on which the DL problem is believed to be hard is the multiplicative group of the finitefield of large prime order This group is cyclic and was introduced in the Group and Finite Fields post. The time required by the bestknown algorithm to solve DL on it is [10]. The running time is subexponential i.e., executes faster than an exponential algorithm but is less efficient than a polynomial one.
Despite the hardness of DL on the multiplicative cyclic subgroup of a large finite field, it remains more desirable to operate on groups where the DL is thought to be exponentially hard. An example of such a group is the one associated with elliptic curves over finite fields. The elliptic curve discrete logarithm problem (ECDLP) over is thought to be exponentially hard, with the best performing algorithm requiring time [10].
By way of comparison, ECDLP on a finite field of order has an equivalent difficulty to a DL problem on the multiplicative cyclic subgroup of One implication is that cryptographic primitives based on ECDLP require significantly smaller keys. This explains why the digital signature schemes used in various cryptocurrencies (e.g., Bitcoin’s ECDSA, Monero’s MLSAG) rely on elliptic curve groups.
With this motivation behind us, we are now in a position to introduce the concept of an elliptic curve. Its theory is very rich and sits at the intersection of different branches of mathematics including analysis, geometry, and algebra. Our objective is to build a group structure based on the geometry of elliptic curves. The new group is referred to as an elliptic curve group and forms the publickey infrastructure of a number of cryptocurrencies in use today. We highlight that this introduction is limited to the minimum that we think is needed to appreciate the subject. It is by no means a comprehensive treatise. Readers interested in a detailed treatment of elliptic curve theory can consult e.g., [10]
In what follows, we first introduce an analytic view of elliptic curves over arbitrary fields. We describe the general Weierstrass form and derive a more simplified version as long as some constraints are observed. We then look at the geometry of elliptic curves over real numbers, and build a group structure after augmenting the curve with a point at infinity. The group’s binary operation, also referred to as point addition, is described geometrically and analytically. Later, we introduce the elliptic curve group over finite fields and finally, we describe the two elliptic curves used in Bitcoin and in Monero.
2. Elliptic curves: An analytic description
One way of defining an elliptic curve is as a set of points satisfying the Weierstrass general equation and given by:
The coefficients are chosen from a field and we say that is defined over Note that is purposefully left out for reasons that we keep out of scope for now. could be for instance the field of real numbers or any finite field. Recall that in the Groups and Finite Fields post we mentioned that any finite field is either of prime order or is an extension of a field of prime order where can be any positive integer. We refer to as the characteristic of the finite field and write We derive below a simplified version of the Weierstrass equation applicable only if we exclude fields of characteristics 2 and 3.
Let’s first look at the lefthand side of the equation. It is tempting to complete the quadratic in We can always find such that
We could subsequently make a change of variables by substituting with Since does not depend on we would have eliminated all terms that contain as a factor. The aforementioned equation in can equivalently be written as
One would then be tempted to conclude that except that division by 2 is not always permissible on an arbitrary field If then will not admit a multiplicative inverse on However, division by 2 is possible on all other fields. In what follows, we always assume that Consequently, we can compute and perform the change of variable. The Weierstrass equation becomes:
Letting and the elliptic curve equation becomes:
The next step consists in simplifying the right handside of this equation. It turns out that any cubic equation can be transformed into an equivalent one with the quadratic term eliminated. We do so by substituting variable with a variable of the form The value of is derived by first performing the substitution and then eliminating the coefficient of the quadratic term as follows:
We require that the coefficient of be equal to 0. This imposes a constraint on ‘s value which must satisfy:
If we can always find a multiplicative inverse of in and as a result, solve for The elliptic curve equation becomes:
We can relabel the variables as and let and We then obtain the simplified Weierstrass equation of an elliptic curve over a field such that
In the following section we construct a group structure over elliptic curves. The tangent to the curve at a given point will play an essential role in this construction. As a result, elliptic curves that have singularities (i.e., points where the curve is not differentiable) are not desired and will be excluded. Examples of singularities on a curve include cusps and self intersections. Analytically, a necessary and sufficient condition for a point on a curve to be singular is for the partial derivatives at to be equal to 0. For the elliptic curve equation we get:
The last equation implies that If we substitute in the first and second equations, we conclude that
is singular and
Consequently, must be a cubic root of as well as of its derivative This means that is a double root of If we let denote the third root, we get the following factorization:
By comparing coefficients, we find that , and This in turn implies that the discriminant To summarize, we showed that given an elliptic curve over a field such that we have:
is singular
The contrapositive statement allows us to derive a sufficient condition for to be nonsingular. Specifically, if for all then is nonsingular. Going forward, we only consider nonsingular elliptic curves defined over fields of characteristic other than 2 or 3:
3. Elliptic curve groups: A geometric approach
In what follows, we endeavour to build the elliptic curve group over finite fields. To do so, we first consider elliptic curves over and study their geometry in order to devise a natural abelian group structure. Technically, the construction is performed in the projective plane as opposed to the euclidean plane. However, we attempt to motivate and justify the buildup without delving into the technicalities of projective geometry. Finally, we adapt the binary operation of the group to the case of a finite field.
Elliptic curves over can be easily drawn on the euclidean plane. We include below the graphs of five different elliptic curves, two of which are singular and three regular.
Elliptic curves exhibit xaxis symmetry. To see why, note that on the curve, it must hold that is also on the curve. Indeed,
Moreover, by virtue of being a point on the curve. Therefore, demonstrating that is also a point on the curve.
In order to define any group, one needs to have an underlying set of elements as well as a binary operation on it that ensures that the group axioms are observed. In our case, the underlying set contains all the points in the euclidean plane that satisfy the elliptic curve equation. Note that this does not mean that they are the only elements of the set. As a matter of fact, we also include a special point and refer to it as the point at infinity. We will motivate the introduction of in the next section. For such that the underlying set of the group takes the form:
We still need to define a suitable binary operation that acts on a notnecessarily distinct pair of points in Any group must satisfy the closure axiom and so the output of the binary operation must also be a point in Intuitively, the most natural way of geometrically linking two points in the euclidean plane is with a straight line. It is hence reasonable to look at the different configurations of pairs of points on an elliptic curve defined on The diagram below summarizes the possible scenarios:
It is easy to observe that any two elliptic curve points must belong to one of these categories. As a result, these categories are commonly exhaustive. The configurations are also mutually exclusive. This should be clear except possibly for the case of an inflection point. In what follows we argue that an elliptic curve point with ordinate equals to 0 cannot be an inflection point.
0ordinate points vs. inflection points: An inflection point of a curve is one where the curvature changes sign. Without delving deeper into the notion of curvature, this means that the second derivative of with respect to (assuming it exists on a neighborhood of ) changes sign as the values cross . Intuitively, this suggests the following necessary conditions for a point on the curve (where the second derivative is defined) to be an inflection point:
 The second derivative evaluated at is equal to 0, and
 for infinitesimally small.
However, an inflection point could still exist even when the second derivative is not defined at that point. The definition remains the same, i.e., an inflection point is one that marks a change in the curve’s concavity. As an example, one can look at the function defined on and verify that the point is an inflection point despite the fact that is not defined at
The domain of definition of an elliptic curve over consists of the set
This is due to the fact that over the field of real numbers, square values must be nonnegative. Consequently, must be greater than or equal to 0. It then holds that on As a result:
The second derivative is defined on the set
Among other things, this means that the second derivative is not defined on curve points whose ordinate is equal to 0. This however, is not enough to justify that 0ordinate points are not inflection points. To rule out this possibility, we note that by virtue of being a cubic equation, can admit either one or three roots (not necessarily distinct) in . We can then classify nonsingular elliptic curves on in two broad categories: disconnected or connected. The figures below showcase an example of each:
The curve is an example of a nonsingular disconnected curve. These curves admit three distinct real roots, none of which are interior points of the domain of definition (we do not prove this statement). They are boundary points and hence cannot be crossed from right to left or viceversa. The same applies to the connected curve which admits one real root instead of three, but whose unique root is also a boundary point of
An implication of the aforestated definition is that the abscissa of an inflection point of a curve in must be an interior point of Indeed, one should be able to cross it in order to validate a change in curvature. Consequently, points on the elliptic curve of the form cannot be inflection points since their abscissas (i.e., the real roots of ), are boundary points of
Building the binary operation: Having defined the possible configurations of a pair of points on a nonsingular elliptic curve on we now focus on finding a suitable binary operation. More specifically, given two points on the curve (notnecessarily distinct), our objective is to operate on them in such a way that the output is also a point on the curve.
A rather natural way of doing so is to check if the line passing through the two points intersects the curve at another point. In what follows, we consider each configuration separately and demonstrate that the procedure outputs one or two suitable candidate points. We then show that only one of the two points is permissible (whenever they coexist), paving the way to an algebraic description of the binary operation.
Configuration #1: and are two distinct points on the elliptic curve such that
 The equation of the line joining and is given by
We let and write
 As a result, any point of intersection of this line with the elliptic curve must have an abscissa that satisfies
 This is a cubic polynomial on and as noted earlier, can have either one or three real roots (not necessarily distinct).
 We already know that and are two distinct real roots. Consequently, there must exist a third root (not necessarily distinct from the other two) that we denote by
 We write which upon expansion shows that
 Consequently, is on the curve due to axis symmetry.
 Moreover, is also on the curve. Later, we specify which of the two points is the eligible one.
 Here is the graph of an instance of this configuration for the following elliptic curve
Configuration #2: and are two distinct points on the elliptic curve such that (and hence
 The equation of the line joining and is given by
 As a result, any point of intersection of this line with the elliptic curve must have an ordinate that satisfies the equation
 This is a quadratic polynomial in on It either has no solution or admits two notnecessarily distinct real roots.
 We already know that and are two distinct roots, and so we concude that these are the only solutions to the equation.
 The logic of our construction requires that a viable binary operation involving two roots yield a third one. Consequently, we add the point at infinity to the set of eligible group elements and let In this case we only have one elgible candidate as opposed to two.
 Here is the graph of an instance of this configuration for the following elliptic curve
Configuration #3: The two points on the elliptic curve are identical and have an ordinate equal to 0. We let the point be denoted by
 In the case of two distinct points, there was one and only one line that connected them. A single point however, admits an infinity of lines that go through it. A choice must hence be made.
 To do so, imagine that is a distinct point on the curve that is infinitesimally close to In the limit as approaches the line connecting them converges to the line of choice, i.e., the tangent to the elliptic curve at
 Note that on the domain of the elliptic curve, Consequently, on The tangent to the elliptic curve at a 0ordinate point is a vertical line. In particular, the equation of the tangent at is given by
 Any point of intersection of this tangent with the elliptic curve must have an ordinate that satisfies the equation
 This is a quadratic polynomial in on It either has no solution or admits two notnecessarily distinct real roots.
 We already know that is a root, hence so is Consequently 0 is a double root and as a result, the only solution to the equation.
 Following the same logic of configuration #2, we make use of (the point at infinity) and let In this case too, we only have one eligible candidate as opposed to two.
 Here is the graph of an instance of this configuration for the following elliptic curve
Configuration #4: The two points on the elliptic curve are identical and constitute an inflection point. We let the point be denoted by
 Following the same logic of configuration #3, we choose the line tangent to the elliptic curve at
 Without loss of generality let on Consequently, on
 Let Hence The equation of the tangent at becomes
 Any point of intersection of this tangent with the elliptic curve must have coordinates that satisfy This can be simplified to
 We claim that this equation admits as a triple root. To see why, note that over
 A necessary condition for a point on the curve (where the second derivative is defined) to be an inflection point is that its second derivative be 0. Since is such a point, it must be that And since we get
 Substituting with in
yields
Since we can cancel the factor from both sides and obtain
 Substituting with and with their and expressions, we get
This is equivalent to
 Canceling we get This is equivalent to Consequently, is a triple root.
 Since a cubic equation has a maximum of three roots on , is the only one.
 As a result, we could define a binary operation in one of two natural ways: or Shortly, we will see why we choose the latter.
 Here is the graph of an instance of this configuration for the following elliptic curve
Configuration #5: The two points on the elliptic curve are identical, have nonzero ordinate and are not an inflection point. We let the point be denoted by
 As in configuration #3, we choose the line tangent to the elliptic curve at
 On the tangent’s equation at is
Letting and we get
 As a result, any point of intersection of this line with the elliptic curve must have an abscissa that satisfies
 This is a cubic polynomial on and as noted earlier, can have either one or three real roots (not necessarily distinct)
 We know that is a double real root, and so there must be a third root. We denote it
 We write which upon expansion yields
 As a result, is on the curve. So is due to axis symmetry.
 Note that in configuration #1, if the resulting third root were equal to either or (recall that and have distinct absiscas), the outcome would be similar to that of configuration #5.
 Here is the graph of an instance of this configuration for the following elliptic curve
Choosing a candidate: In configurations #1, #4 and #5, we endedup with two points (symmetric about the axis) to choose from with regard to the output of the binary operation. Only one of them safeguards the group axioms. To see which one does not, consider configuration #4:
 Suppose that we choose point (as opposed to ). That means that
 Consequently, must be the identity of the group. We claim that this can not be.
 To see why, choose a curve point such that is not tangent to the curve at
 One can see that this is a special case of configuration #1 (if ) or of configuration #2 (if ), and that the procedure previously described results in candidates all of which are different than
 As a result, cannot be the identity element and is thus ruled out.
Defining the elliptic curve group: We are now in a position to introduce the elliptic curve group on and verify that it respects the abelian group axioms.
 For given such that the underlying set of the group is defined to be:
 Let and be points in . We define the binary operation as follows:
 If and (i.e., configuration #1), let
 If and (i.e., configuration #2),
 If and (i.e., configuration #3),
 If and (i.e., configurations #4 and #5), let
 The point at infinity is defined to be the identity element of the elliptic group.
thus defined, satisfies the abelian group axioms:
 Associativity: Using the aforestated definition of one can verify (with a bit of patience and willingness to write down lengthy formulas) that
 Existence of identity: We defined such that for all we have
Note that for any such that is never equal to This can be readily verified by checking each configuration separately.
 Closure: By construction of we made sure that the result of adding two points on the elliptic curve is another point on the curve. In other terms
 Existence of inverse: the point is also in This is because the elliptic curve exhibits axis symmetry. Moreover, and belong to either configuration #2 (if they are distinct) or configuration #3 (if they are identical) and so the definition of ensures that
As a result, is the inverse of
 Commutativity: The definition of implies that
4. Elliptic curve groups over finite fields
Going forward, we only consider finite fields of prime order and do not cover extension fields. For an introduction to finite fields, we refer the reader to this post. A nonsingular elliptic curve defined over a finite field of prime order differs from one defined over in the following way:
 The equation of the curve becomes as opposed to
 The parameters and are chosen in as opposed to
 The discriminant must satisfy as opposed to
 Points on are tuples such that This is in contrast to tuples such that
The main difference is that all computations are conducted in modulo arithmetic. In what follows, we depict the elliptic curve over and over The geometry of elliptic curves over finite fields is not as intuitive as that of those over However, we will see that the algebraic formulation of their associated group closely follows that of elliptic groups over
For example, in order to draw over we select each value of in the set and plug it into the expression We subsequently check whether the result is a quadratic residue or not by verifying whether such that is a match. We find that the euclidean representation of this curve over consists of the following 34 elements:
While on the elliptic curve exhibited axis symmetry, on it exhibits symmetry about the horizontal line Indeed, if is a point on the curve, then so will This is because
Formally, we denote by the group associated with an elliptic curve defined over In particular:
 For and such that the underlying set of the group is defined to be:
 Let and be points in . We define the binary operation as follows:
 If and let (division refers to multiplication by the inverse of the denominator over ,
 If and
 If and
 If let (division means multiplication by the inverse of the denominator over
 The point at infinity is defined to be the identity element of the elliptic group.
To illustrate point addition in elliptic curve groups over finite fields, we look at and operate on points and Since and we compute

where 5 is the inverse of 25 in modulo 31 arithmetic (recall that this can be efficiently computed using the extended euclidean algorithm introduced in the Groups and Finite Fields post).
We then compute
The construction of is similar to that of except for the fact that values are computed modulo thus defined, satisfies the abelian group axioms:
 Associativity: Using the aforestated definition of one can verify after lengthy and tedious calculations that
 Existence of identity: We defined such that for all we have
 Closure: By definition of the resulting output is either or a tuple (since all arithmetic is conducted modulo ). Moreover, one can readily use the definition of to check that the result of the binary operation always verifies the elliptic curve equation modulo . Consequently,
 Existence of inverse: is also in due to symmetry about the line . And so the definition of ensures that
As a result, is the inverse of
 Commutativity: The definition of implies that
ECDLP, cardinality, and point multiples in Recall that the importance of elliptic curve groups over finite fields is largely derived from the exponential hardness of the DL problem on them. The Elliptic Curve Discrete Logarithm Problem (also known as ECDLP) can be stated as follows:
 Let be an elliptic curve defined over a finite field (i.e., such that )
 Let be the group associated with it, where
 Let and find the smallest integer (if it exists) such that
( times)
The notation is unusual as it is commonly written as We decide to make explicit the appearance of the operator as a reminder that it is scalar multiplication with respect to the binary operator
Finding such an when it exists is thought to be exponentially hard. In the context of cryptoassets, we don’t operate on the full set Rather, we choose an element such that order() is a very large prime. We then limit ourselves to the subgroup generated by (refer to the post on Groups and Finite Fields for an introduction to subgroups). Given and ECDLP now consists in finding the smallest integer such that We are confident that such an exists since
In the digital signature schemes used in e.g., Bitcoin and Monero, represents the private key and the public one. It is important to derive efficiently from However, as we stated earlier, it must not be polynomially feasible to compute from . The exponential hardness of ECDLP helps with the latter requirement. Moreover, one can expect that the larger the set the better. This justifies the importance of having a sense of the cardinality of also denoted In order to ensure the former requirement, we need to have an efficient polynomialtime algorithm that can compute multiples of
 Cardinality of : We previously saw (e.g., in the case of ) that not every tuple is necessarily an element of . To get an upperbound on note that for every one can have at most two values of that satisfy the elliptic curve equation
If is a solution, then so will In addition, we have the point at infinity As a result, since there are distinct values in we get a maximum of points in Over there are quadratic residues and an equal number of quadratic nonresidues (we don’t prove this statement in this post). As a result, in the absence of any information, a random has equal probability of being a square or not. One can then calculate the expected value of the number of points in to be The German mathematician Helmut Hasse showed that
The Dutch mathematician René Schoof, relied partly on Hasse’s theorem to devise a deterministic algorithm that can compute with complexity This is known as the Schoof algorithm and its proof is beyond the scope of this post (readers interested in learning more about it can consult [9]). The important takeaway is that there exists a polynomialtime algorithm to calculate the order of an elliptic curve group over a finite field.
In so far as the structure of this group is concerned, we mention without proof that is always either cyclic or the product of two cyclic groups.
 Point multiplicity: Suppose is a very large integer, and is as defined earlier. In order to calculate one can do the following:
 Write in its base 2 expansion
for
This can be achieved in
 Subsequently, write as
for  Since the value is equal to can be evaluated by doubling the point (i.e., then ) a total of times. In the process, we store the value of for all for which
 Putting it altogether, in order to caculate one first needs steps to find then a total of point doublings, and finally, a worstcase total of additions. Hence, the worstcase complexity is Noting that is on the order of the complexity becomes The above procedure is known as the doubleandadd method and ensures that point addition can be efficiently carried on elliptic curves over finite fields.
 Write in its base 2 expansion
 A note on finding : A question of practical importance is whether one can efficiently find an adequate point such that its order is equal to a large prime. This question is justified since finite fields of interst have an astronomically large characteristic (usually larger that ) and one cannot expect to conduct an exhaustive search on the underlying group. The answer turns out to be positive, and one way of finding a suitable is as follows:
 Calculate using Schoof’s polynomialtime algorithm.
 Find a very large prime (ideally the largest) that divides Say Note that the integer factorization problem is thought to be hard. However, in some cases where the integer exhibits certain properties, one can employ more efficient algorithms to identify a prime factor. We will not go into the details of these algorithms but refer the interested reader to e.g., [4] for an accessible overview.
 Choose a random point We know that order order. By Lagrange’s theorem, the order of any subgroup divides the order of the parent group. As a result, the order of must divide and so
 Consequently, the order of the element must divide Since is prime, the order of can either be equal to 1 or If it is 1, then is the identity element In this case, we go back to step 3 and choose a different point Otherwise, we set which can be computed efficiently using the aforementioned doubleandadd method. We refer to as the cofactor of
5. Elliptic curve in Bitcoin
Bitcoin’s cryptography relies on a particular curve known as secp256k1:
 “sec” is short for Standard for Efficient Cryptography. It refers to a set of standards developed by the Certicom Research consortium [7].
 “p” refers to the fact that the curve is defined over a finite field of prime order
 “256” means that the curve points’ abscissas and ordinates are 256bit long.
 “k” states that the curve belongs to the Koblitz family. Usually, Koblitz curves are defined over extension fields of characteristic 2 i.e., over for some positive integer However, the Bitcoin curve is defined over a prime field of characteristic It belongs to a more general version of Koblitz curves. Without going into further details, it suffices to say that for all practical matters, the importance of this class of curves is derived from its higher efficiency in computing point multiples on its associated group.
 “1” is a reminder that it is the first curve of its kind that satisfies the previous attributes.
The parameters of secp256k1 can be found on page 9 of [7] and are as follows:
 or in hexadecimal notation (hex)
FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
Each element represents a halfbyte (i.e., 4 bits) known as a nibble. There are 64 nibbles corresponding to the 256bit representation mandated by the standard.
 which in standard hex is given by
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
 which in standard hex is given by
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000007
 Since and the curve is nonsingular and can be written in short Weierstrass form. The resulting group is where
Here is a euclidean representation of this curve when (it is not feasible to show it for ):
 The base point has abscissa and ordinate given by
which in standard hex notation are given by:
79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8
Bitcoin’s publickey cryptography is hence conducted on the subgroup
 The order of is chosen to be a prime number equal to
which in standard hex notation is given by
FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
 Recall that denotes the order of and must divide i.e., the order of . The cofactor is equal to which in this case is equal to 1 and is represented in standard hex notation by
0000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001
That means that the order of is equal to that of i.e., Since is prime, the order of must also be prime. As a result, is a cyclic group and any of its elements could serve as a generator (refer to Groups and Finite Fields for an introduction to cyclic groups).
Another noteworthy SEC2 curve is secp256r1. The “r” specifier refers to the attribute “random” since the generation of the curve parameters and relies on a supposedly random process involving a seed value fed to a hash function. The seed value as well as the other curve attributes can be found on pages 9 and 10 of [7].
There was a fair amount of questioning as to why Satoshi opted for the usage of secp256k1 as opposed to that of another curve such as secp256r1. The reason(s) remain obscure and advocates that favor one curve over the other abound (e.g., [5], [1]). The point of contention lies in the randomness involved in selecting the curve parameters:
 On the one hand, Koblitz curves exhibit slightly weaker security than other curves (although when using 256bit long parameters, the difference is negligible). Moreover, the National Institute of Standards and Technology or NIST (a US governmental agency) has been advocating the usage of secp256r1 on the basis that its parameters achieve very high security standards. Another common name of this curve is NIST P256, and constitutes one of fifteen curves that NIST recommends.
 On the other hand, skeptics argue that NIST’s endorsement, coupled with the absence of a rationale for the choice of the seed value are ground for dismissal. According to them, it is possible that the NIST (and affiliated entities) might have placed a backdoor to weaken the curve’s security standard. Their scepticism is not unfounded since the NSA and NIST have previously planted a backdoor in the elliptic curve algorithm known as Dual_EC_DRBG, which was validated by memos leaked by Edward Snowden. The interested reader can refer to [11] for a take on how the NSA might have accomplished this.
Suffice it to say that no one can tell with certainty whether one curve is preferred over the other. Assuming no backdoor, both curves exhibit comparable security standards.
6. Elliptic curve in Monero
The NIST debacle surrounding the Dual_EC_DRBG algorithm pushed some people away from NIST curves and closer to curves generated in academic circles instead. Two such curves are Curve25519 and its next of kin ed25519 used in Monero. Both are elliptic curves, but are not represented in short Weierstrass form. However, they could be transformed into one and we will see how shortly.
Curve25519 was originally introduced by the GermanAmerican mathematician and cryptologist Daniel Julius Bernstein. Unlike SEC curves and some of those advocated by NIST, Curve25519 is thougt to be patentfree. It is also hailed for its faster computation of point multiples when compared to e.g., sec256r1 (NIST P256) [6]. Moreover, it exhibits a security level comparable to that of secp256k1 and secp256r1 (assuming no backdoors). These favorable attributes paved the way for its everincreasing adoption.
We first provide an overview of Montgomery and Twisted Edward representations of elliptic curves of which Curve25519 and ed25519 are respective examples. We show that under certain constraints, any of these representations could be transformed into a short Weierstrass counterpart using a specific isomorphism. The existence of an isomorphism makes the two curves’ respective groups equivalent and guarantees that the hardness of ECDLP is preserved on both. In the last section, we introduce the attributes of Monero’s ed25519 curve.
Twisted Edward and Montgomery representations: A Twisted Edward curve defined on a field such that with parameters and such that is one that satisifies the following equation
It turns out that if in addition, is a square in and is not, the curve will define a group structure. For our purposes, on a finite field such a curve will define a group where the superscript refers to “Edward”. One could define the binary operation from basic principles as we did earlier for curves in short Weierstrass form. However, we show shortly that each such Twisted Edward curve is equivalent to another one in short Weierstrass form. The equivalence implicitly defines a corresponding group structure associated with it. The underlying set of the group is defined as
Note that it does not contain a point at infinity. We will attempt to justify its absence when we discuss the equivalence betwen curve representations.
A Montgomery curve defined on a field such that with given parameters and such that is one that satisifies the following equation
The curve thus defined, admits a group structure assoiated with it. For our purposes, on a finite field this curve defines a group where the superscript refers to “Montgomery”. Here too, one could define the binary operation from basic principles using the chord and tangent method presented earlier for Weierstrass curves in short form. However, we show shortly that every Montgomery curve is equivalent to another one in short Weierstrass form. As is the case for Twisted Edward curves, this equivalence implicitly defines a corresponding group structure associated with it. The underlying set of the group is defined as
Note that it contains a point at infinity denoted by . The need for such a point will be addressed when we discuss the equivalence betwen curve representations.
Every Montgomery curve is equivalent to a short Weierstrass one: Starting with a Montgomery curve
where (we will justify this constraint shortly), our objective is to transform it into a shortform Weierstrass curve
where the superscript refers to Weierstrass. Moreover, must be different than 2 or 3 for the short Weierstrass form to hold, and different than for it to be nonsingular.
The sought after transformation must map every point on to a point on . Let’s first exclude the point at infinity of and focus on the other points. Let’s substitute with and with This yields
In order to make the coefficient of equal to 1 (as mandated by the short Weierstrass form), it must be that so that we can multiply both sides of the equation by the modular inverse of We get
We recognize a short Weierstrass form with and For it to be valid, we still need to ensure that This means that
The constraints and can be combined into a single one given by This explains its inclusion earlier when we defined the Montgomery form.
The above derivation mapped every point of the Montgomery curve to a point on the shortWeierstrass curve. Note that the point at inifnity of the shortWeierstrass form was not attained by the previous transformation. As a result, we define a point at infinity on the Montgomery curve and map it to Consequently, we get the following injective map:
if
In order to show that this map is a bijection, we must demonstrate that it has an inverse. We claim that given such that the short Weierstrass form can be transformed into the Montgomery curve Here, parameters and are respectively given by and
This can be readily verified by substituting with and with This substitution shows that every point on the given short Weierstrass form is mapped to a point on the Montgomery curve. The only point left out is which we then map to As a result, we get the following inverse transformation:
if
Note that with the exception of and the map (and its inverse) have their two components expressed as a rational fraction in Such transformations are known as birational maps. As a result, the bijection between a Montgomery form and its associated short Weierstrass form is also referred to as a birational equivalence. One important observation is that any Montgomery form can be transformed into a short Weierstrass curve. However, the reverse is not always possible. We will not define the constraints that must be imposed on a short Weierstrass curve to admit a Montgomery counterpart. Suffice it to say that the specific values of and previously used satisfy the required constraints.
Equivalence of (certain) Twisted Edward and (certain) Montgomery curves: Starting with a Twisted Edward curve
where and requiring additionally that be a quadratic residue over and a quadratic nonresidue (we will justify these constraints shortly), our objective is to transform it into a Montgomery curve given by
where This is equivalent to and
The transformation must map every point on to a point on To do so, let’s substitute with and with This substitution attains every point on the Montgomery curve except for the following points:
 The point at infinity
 Points with The equation of a Montgomery elliptic curve would then dictate that This in turn means that or To minimize the number of points on the Montgomery curve that are not attained, we require that the quadratic equation admit no solution in In order to ensure that, the discriminant must be a quadratic nonresidue over Consequently, the only point to exclude from the Montgomery curve in this case is
 Points with The equation of a Montgomery elliptic curve would then dictate that Since this becomes To minimize the number of points on the Montgomery curve that are not attained, we require that also be a quadratic nonresidue over
The change of variable dictates that if then Consequently, we must exclude the points on the Twisted Edward curve that have One can readily verify that these are the points and So let’s apply the variable substitution, keeping these two points out for now. We will treat them separately in a moment.
And since we excluded the cases and we get
Since we can multiply both sides of the equation by the modular inverse of and get
To ensure that the coefficient of is equal to 1 as mandated by the Montgomery form, we must have so that we can multiply both sides of the equation by the modular inverse of In this case, we obtain
We recognize the Montgomery elliptic curve form with and However, we must still make sure that as mandated by the definition of a Montgomery form. Clearly, We only need to make sure that This translates to which implies that
To sumup, the variable substitution that we introduced defines a map from to given by The constraints that need to be observed are the following:
 must be a quadratic nonresidue over In terms of the Twisted Edward curve parameters and this translates to being a quadratic nonresidue.
 () must be a quadratic nonresidue over This means that is a quadratic nonresidue. Consequently, must be a quadratic nonresidue. Since 16 and are both quadratic residues, it must be that is a quadratic nonresidue. Now note that if both and were squares, then so will Moreover, if and were both nonsquares, there could still be a possibility that is a square (as an example, take the elements 3 and 5 over which are both quadratic nonresidues but their product is a square). As a result, we require that if is a square then be not and viceversa. Since we saw that is a quadratic nonresidue, then we require that be a quadratic residue.
 and We can combine both constraints into a single one
Finally, note that we left out two points on the Twisted Edward curve, namely and Observe however, that on the Montgomery elliptic curve, we also have two points that were not covered, namey the point and the point at infinity We thus define the following injective transformation:
, if
Conversely, starting with the Montgomery curve
where () and () are both quadratic nonresidues over we can show that it can be transformed into a Twisted Edward curve of the form
where
To do so, we make use of the inverse of the previous substitution. We substitute with and with Clearly, these are defined for all points as long as and But note that corresponds to In other words, points and of the Twisted Edward curve cannot be attained by the map defined by this substitution. Note also that the change of variable dictates that
 Case Since the Montgomery form dictates that As a result the point of the Montgomery curve must be excluded.
 Case The Montgomery form dictates that And so or Since we assumed that is a quadratic nonresidue, the discrimant of cannot be a square. Hence, this quadratic has no roots over
Consequently, the only two points of the Montgomery curve that are not covered by this substitution are the point at infinity and the point We will deal with them separately. After applying the change of variable, we get
After simplication, we obtain
Since and we simplify further and obtain
We recognize this as a Twisted Edward form with and This is a valid representation because
 (since for a Montgomery curve)
We then get the following inverse transformation:
, if
The maps and demonstrate the existence of a birational equivalence between the following two sets:
 Twisted Edward curves with a quadratic residue and a quadratic nonresidue over
 Montgomery curves with () a quadratic residue and () a quadratic nonresidue over .
Finally, note that one could transform such a Twisted Edward curve into a short form Weierstrass curve by applying the composition map Readers interested in learning more about Twisted Edward curves can consult [2].
Monero’s curve: The elliptic curve cryptography used by Monero [8] relies on a particular Twisted Edward curve known as [3]. It has the following attributes:
 is the prime number given by explaining the suffix in the curve’s name. It defines the underlying finite field In hex notation using 256 bitlong representation, it is given by
7FFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFED
 In standard hex notation, it is given by
7FFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFEC
 . In standard hex notation, it is given by
52036CEE 2B6FFE73 8CC74079 7779E898 00700A4D 4141D8AB 75EB4DCA 135978A3
Since and this curve qualifies as a Twisted Edward curve. Moreover, is a quadratic residue over while is not. Consequently, this curve admits a birationally equivalent Montgomery form known as Curve25519. The underlying set of the group associated with this Twisted Edward curve is given by
Here is a euclidean representation of this curve when (it is not feasible to show it for the value of )
 The base point has abscissa and ordinate given by
which in standard hex notation are given by:
216936D3 CD6E53FE C0A4E231 FDD6DC5C 692CC760 9525A7B2 C9562D60 8F25D51A
66666666 66666666 66666666 66666666 66666666 66666666 66666666 66666658
Monero’s publickey cryptography is hence conducted on the subgroup whose underlying set is
 The order of is chosen to be a prime number equal to
Which in standard hex notation is given by
10000000 00000000 00000000 00000000 14DEF9DE A2F79CD6 5812631A 5CF5D3ED
 Recall that denotes the order of , and must divide i.e., the order of The cofactor is equal to which in this case evaluates to 8. It is represented in standard hex notation by
00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000008
References
[1] behindtext. why did bitcoin choose secp256k1 over secp256r1?
[2] D. J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange, and Christiane Peters. Twisted edwards curves. AFRICACRYPT, pages 389405, 2008.
[3] Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo Yin Yang. Highspeed highsecurity signatures. Cryptographic Hardware and Embedded Systems, pages 124142, 2011.
[4] AnneSophie Charest. Pollard’s p1 and lenstra’s factoring algorithms.
[5] Hal Finney. secp256k1.
[6] ImperialViolet. What a difference a prime makes, December 2010.
[7] Certicom Research. Sec 2: Recommended elliptic curve domain parameters. Standards for Efficient Cryptography, 2010.
[8] N. Van Saberhagen. Cryptonote 2.0. , 2013.
[9] R. Schoof. Elliptic curves over finite fields and the computation of square roots mod p. Mathematics of computation, 44(170):483494, 1985.
[10] J. Silverman. The Arithmetic of Elliptic Curves. Springer, second edition, 2009.
[11] Nick Sullivan. How the nsa (may have) put a backdoor in rsa’s cryptography: A technical primer , January 2014.
Tags: Curve25519, ed25519, Edward, elliptic curve, elliptic curve group, Montgomery, Twisted edward, Weierstrass
No comments
Comments feed for this article
Trackback link: https://delfr.com/wptrackback.php?p=1211