Elliptic Curve Cryptography in C++
Part 2) Building an ECC class in code
In part 1 we discussed how elliptic curve cryptography works in theory. If you haven't yet read part 1 we recommend that you read that first to get an understanding of the theory.
A modification to the theory to implement it in code
In part 1 we arrived at this step in the elliptic curve theory to get point R from P ⊕ Q = R.
To implement this in code to run on a computer, we need to add an additional step. The theory allows for any point P, Q where P ⊕ Q = R for any points P and Q on the curve. While this works theoretically, the issue with this is that we have an infinite amount of points P, Q, and thus R. Having an infinite amount of points is bad for computers because we want fast computations.
To fix this problem, we restrict points P and Q to whole numbers in a fixed range. To make this work, when computing the formula for the elliptic curve (y² = x³ + ax + b), we use modulus division as a trick of rolling over numbers when we hit the maximum. If we pick the maximum to be a prime number, the elliptic curve is called a prime curve and has excellent cryptographic properties.
Our plot looks like this when we only allow for the whole numbers in a fixed range.
While these look like random numbers, these are just the whole numbers of points P, Q, and thus R. It is a flat representation of points, and the operation P ⊕ Q = R is able to wrap from the ends of the graph to the other side.
This “wrapping” around effect can be visualized in 3 dimensions as a torus. Notice how the blue lines on the left and right images are all straight, continuous lines.
Need help visualizing the wrap effect?
A way we can imagine this wrapping effect is in the game Pacman, specifically how Pacman is able to seemingly teleport from the left to the right of the screen. If we are told Pacman can’t teleport then how would this be possible?
There is only one way that this can be possible but requires us to question what were looking at. We originally see that the gameboard is a flat, 2D representation of a cylinder, and instead folded the left and right of the board to each other, we get a cylinder where Pacman never teleports to get to the other side!
Why is it a cylinder and not a torus or another shape?
The reason why 3D Pacman is a cylinder and not another shape is that he can only exit the board from the left and right and vice versa. If Pacman was able to exist from the top, bottom, left, and right the 3D representation would be a sphere. If he was able to leave anywhere and appear on the other side, then the game would be on the surface of a torus.
The graph above is a torus because the lines can leave the plot on any side, and appear on the opposite side.
Elliptic Point Class
Now that we’ve restricted points P and Q to the surface of the torus, we can implement the functions in the code. One last important consideration we need to make is we will use the a and b parameters of secp256k1, i.e. respectively zero and seven. We need to agree on these parameters because it's important that all participants in the ECC encryption need to agree on these variables so that they are all working with the same curve.
Let's create a class called Elliptic Point which has the functions. Scroll past the steps for the full code implementation or click here.
Make the class & define class variables
class EllipticPoint
{
double m_x, m_y;
static constexpr double ZeroThreshold = 1e20;
static constexpr double B = 7;
}First, we start by giving the elliptic point an x and a y. This is its location on the 2d surface of the torus. Next, we define the zero thresholds. This value is used in the izZero function to determine if the point is zero. This value is used in the case where we get a result 0.00001, so that it can be considered “zero”. Finally, we define variable b, which is the b in the elliptic curve formula (y² = x³ + ax + b).
Constructors
constexpr EllipticPoint() noexcept : m_x(0), m_y(ZeroThreshold * 1.01) {}
explicit EllipticPoint(double yCoordinate) noexcept
{
m_y = yCoordinate;
m_x = cbrt(m_y * m_y - B);
}
The first constructor is the default constructor which initializes the values to zero. The reason why the m_y variable gets set to ZeroThreshold * 1.01 is that we're using a zero threshold to determine if a number is zero. Therefore multiplying the zero thresholds by 1.01 it will put the y value just above the zero thresholds so that it's not considered zero, but it's so close to zero that it doesn't affect our calculations.
The second constructor takes in the y coordinate as a parameter and calculates the value of the x coordinate via the elliptic curve formula (y² = x³ + ax + b).
Helper Functions
- IsZero: Determines if an elliptic point is zero
- Negate (override - operator): Can negate an elliptic point
bool IsZero() const noexcept
{
bool isNotZero = abs(m_y) < ZeroThreshold;
return !isNotZero;
}This checks if the y variable is below the zero thresholds. For example, if our threshold is 0.01 and the y point is 0.001, we would consider the point y as zero.
EllipticPoint operator-() const noexcept
{
EllipticPoint negPt;
negPt.m_x = m_x;
negPt.m_y = -m_y;
return negPt;
}Creates a new Elliptic point and sets its y variable to the negative.
Elliptic Curve Arithmetic
- Add (override += operator): Can add 2 elliptic points from each other and return the resulting elliptic point
- Subtract (override -= operator): Can subtract 2 elliptic points from each other and return the resulting elliptic point
- Multiply (override *= operator): Can multiply an elliptic point by an integer and return the resulting elliptic point
- Double: Returns P+P for any given point P.
EllipticPoint &operator+=(const EllipticPoint &rhs) noexcept
{
if (IsZero())
{
*this = rhs;
}
else if (rhs.IsZero())
{
// since rhs is zero this point does not need to be
// modified
}
else
{
double L = (rhs.m_y - m_y) / (rhs.m_x - m_x);
if (isfinite(L))
{
double newX = L * L - m_x - rhs.m_x;
m_y = L * (m_x - newX) - m_y;
m_x = newX;
}
else
{
if (signbit(m_y) != signbit(rhs.m_y))
{
*this = EllipticPoint();
}
else
{
Double();
}
}
}
return *this;
}The function starts off by taking in an elliptic point object and its goal is to add it to another elliptic point. The function first starts off by checking if the current elliptic point is zero. If it is, no additional needs to take place as we can just set the values of the other elliptic point.
If the incoming elliptic point object is the zero point, then we do nothing.
Otherwise, the function calculates the line between the two points and finds the new x coordinate for the object on which the operator+= function is called. The y coordinate is then set accordingly. If the line is vertical, then the operator+= function doubles the point. If the line is horizontal and the two points have different signs for their y coordinates, then the operator+= function sets the point to the zero point.
EllipticPoint &operator-=(const EllipticPoint &rhs) noexcept
{
*this += -rhs;
return *this;
}Subtracts one point by another point. It does this by adding the negative of one point.
EllipticPoint &operator*=(int rhs) noexcept
{
EllipticPoint r;
EllipticPoint p = *this;
if (rhs < 0)
{
rhs = -rhs;
p = -p;
}
for (int i = 1; i <= rhs; i <<= 1)
{
if (i & rhs)
r += p;
p.Double();
}
*this = r;
return *this;
}
};Multiplies the elliptic point by an integer by first checking if the value is negative. If the value is multiplied by a negative number, the point is negated before the operation is performed.
The next part of the function is the for loop. This code is implementing an algorithm known as exponentiation by squaring. This algorithm is used to calculate the value of a number raised to a power. Exponentiating by squaring is a general method for fast computation of large positive integer powers of a number.
void Double() noexcept
{
if(IsZero())
{
return;
}
if(m_y == 0)
{
*this = EllipticPoint();
}
else
{
double L = (3 * m_x * m_x) / (2 * m_y);
double newX = L * L - 2 * m_x;
m_y = L * (m_x - newX) - m_y;
m_x = newX;
}
}The double of an elliptic point is the point that is twice as far away from the origin as the original point. To understand how the Double function works in more detail here is a video that visually shows it.
Other Elliptic Curve Arithmetics
We can then use these arithmetic functions to overload the (+,-,*) operators. We can do this by using our (+=, -=, and *=) overloaded functions.
inline EllipticPoint operator+(EllipticPoint lhs, const EllipticPoint &rhs) noexcept
{
lhs += rhs;
return lhs;
}
inline EllipticPoint operator-(EllipticPoint lhs, const EllipticPoint &rhs) noexcept
{
lhs += -rhs;
return lhs;
}
inline EllipticPoint operator*(EllipticPoint lhs, const int rhs) noexcept
{
lhs *= rhs;
return lhs;
}
inline EllipticPoint operator*(const int lhs, EllipticPoint rhs) noexcept
{
rhs *= lhs;
return rhs;
}Next Step
Now that we have an understanding of the theory and math, and we have an elliptic point class, we can create an Elliptic Curve Digital Signature Algorithm to generate private keys and public keys!
The code for the Elliptic Point Class can be found here
Cabal Labs
Cabal Labs is on a mission to enhance human freedoms and rights through technological innovation. We have grown a network of companies that serve under our banner. These developers and researchers have made it their life’s goal to break the status quo and deliver revolutionary solutions to age-old problems.
We would love to hear from you: caballabs@gmail.com
References
This was article was made possible by these articles.
- https://www.allaboutcircuits.com/technical-articles/elliptic-curve-cryptography-in-embedded-systems/
- https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/
- https://blog.cloudflare.com/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/
- https://rosettacode.org/wiki/Elliptic_curve_arithmetic
