Elliptic curves are a fascinating and important mathematical concept, widely used in cryptography. In most cryptographic applications, elliptic curves are mostly defined over prime fields, where all the calculations are done modulo a prime number. These curves have an infinite number of points, but defining them over a finite field, such as prime fields, limits the number of points, making them suitable for secure cryptographic systems because it will show cyclic group features.
While prime fields are commonly used, elliptic curves can also be defined over binary fields. This is of great interest to cryptography practitioners, as binary fields offer unique advantages, particularly in hardware design. For this purpose, elliptic curves are often used in the Koblitz form, although other forms, like Binary Edwards curves, also exist, though they are less popular.
🙋♂️ You may consider to enroll my top-rated cryptography course on Udemy
In this blog post, we’ll explore elliptic curves over binary fields, discussing their significance in cryptography, hardware applications, and why they are becoming increasingly important in the context of modern technology, especially with the rise of the Internet of Things (IoT)
Elliptic Curves in Koblitz Form
Let’s take a look at elliptic curves in Koblitz form, or simply Koblitz curves. They are represented by the equation:
y2 + xy = x3 + ax2 + b
Here are some key features of Koblitz curves:
The negative of the point (x, y) is (x, -(x+y)), and this point still lies on the curve.
Adding two distinct points on a Koblitz curve will yield a third point on the curve. This is expressed as:
(x1, y1) + (x2, y2) = (x3, y3)
The coordinates of the third point are:
ß = (y1-y2)/(x1-x2)
x3 = ß2 + ß – x1 – x2 – a
y3 = ß(x1 – x3) – x3 – y1
Doubling a point on the curve will yield another point. For instance:
(x1, y1) + (x1, y1) = (x2, y2)
The coordinates of the doubled point are:
ß = (3.(x1)2 + 2.a.x1 – y1)/(2y1 + x1)
x2 = ß2 + ß – 2.x1 – a
y2 = ß(x1 – x2) – x2 – y1
We have already covered the addition formulas in detail in a previous blog post titled The Math Behind Elliptic Curves in Koblitz Form. If you’re curious about how these formulas were derived, we strongly recommend checking out that post for a deeper understanding.
Simplified Addition Formulas
Although we have already proven the formulas for point addition and doubling, we still need to incorporate the characteristics of binary fields into these formulas.
In a binary field, addition and subtraction are identical because the XOR operation is used, and no carry chain is required. Here’s how the operations work:
0 + 0 = 0 (mod 2) = 0
0 – 0 = 0 (mod 2) = 0
1 + 0 = 1 (mod 2) = 1
1 – 0 = 1 (mod 2) = 1
0 + 1 = 1 (mod 2) = 1
0 – 1 = -1 (mod 2) = 1
1 + 1 = 2 (mod 2) = 0
1 – 1 = 0 (mod 2) = 0
As you can see, we can replace any addition or subtraction operation with XOR. We’ll use the + symbol to represent the XOR operation.
In a binary field, 1 is equal to its own inverse (i.e., 1 = -1), and the negative of the point (x, y) was represented as (x, -(x + y)), which simplifies to (x, x + y).
In a binary field, 2 = 0 (mod 2). As a result, terms like 2a or 2y1 become zero and vanish
The addition formula for two distinct points is:
ß = (y1-y2)/(x1-x2)
x3 = ß2 + ß – x1 – x2 – a
y3 = ß(x1 – x3) – x3 – y1
This can be replaced with XOR operations in the binary field as follows:
ß = (y1 + y2)/(x1 + x2)
x3 = ß2 + ß + x1 + x2 + a
y3 = ß(x1 + x3) + x3 + y1
The formula for doubling a point on an Koblitz curve is:
ß = (3.(x1)2 + 2.a.x1 – y1)/(2y1 + x1)
x2 = ß2 + ß – 2.x1 – a
y2 = ß(x1 – x2) – x2 – y1
The term 3.(x1)2 can be written as 2.(x1)2 + (x1)2, so:
ß = (2.(x1)2 + (x1)2 + 2.a.x1 – y1)/(2y1 + x1)
Since terms like 2a or 2y1 vanish in a binary field, this simplifies to:
ß = (x12 – y1)/(x1)
Or more simply:
ß = x1 – (y1/x1)
When replacing subtraction with XOR, the slope becomes:
ß = x1 + (y1/x1)
x-coordinate formula is:
x2 = ß2 + ß – 2.x1 – a
In binary field, terms like 2a or 2y1 become zero and vanish, so:
x2 = ß2 + ß – a
Replacing addition and subtraction with XOR gives:
x2 = ß2 + ß + a
y-coordinate formula is:
y2 = ß(x1 – x2) – x2 – y1
First, replace additions and subtractions with XOR:
y2 = ß(x1 + x2) + x2 + y1
Next, expand ß(x1 + x2)
ß(x1 + x2) = (x1 + (y1/x1))(x1 + x2)
ß(x1 + x2) = x1(x1 + x2) + (y1/x1)(x1 + x2)
ß(x1 + x2) = x12 + x1x2 + y1 + (y1x2 / x1)
Substitute this back into the y2 formula
y2 = ß(x1 + x2) + x2 + y1
y2 = x12 + x1x2 + y1 + (y1x2 / x1) + x2 + y1
The redundant y1 terms cancel out
y2 = x12 + x1x2 + (y1x2 / x1) + x2
Group terms with a common x2 multiplier
y2 = x1^2 + (x1 + (y1 / x1))x2 + x2
Since ß was x1 + (y1 / x1), we can write this as:
y2 = x12 + ßx2 + x2
Summary of Formulas for Addition and Doubling
We can summarize the point addition and doubling formulas as:
(x1, y1) + (x2, y2) = (x3, y3)
ß = (y1+y2)/(x1+x2)
x3 = ß2 + ß + x1 + x2 + a
y3 = ß(x1 + x3) + x3 + y1
(x1, y1) + (x1, y1) = (x2, y2)
ß = x1 + (y1/x1)
x2 = ß2 + ß + a
y2 = x12 + ßx2 + x2
Where + operator is representing XOR gate operations.
Binary Operations
To compute addition and doubling formulas, we also need to perform some additional operations on binary fields. Instead of performing standard ones, we will perform carry-less variants of them. In summary, carry-less operations are arithmetic operations in binary fields (GF(2)) where addition uses XOR and multiplication ignores carry propagation, treating binary numbers as polynomials.
- Multiplication in GF(2): In standard arithmetic, multiplication involves multiplying each digit and handling carry propagation between positions. In GF(2), carry-less multiplication performs the multiplication by XORing partial products and shifting, without propagating carries. The multiplication works by treating the numbers as polynomials and multiplying them bitwise, where the carry is ignored. As a result, a carry-less variant of multiplication, where bits are shifted and XORed without the need to handle carries, making it efficient for binary field operations.
- Division in GF(2): In standard arithmetic, division involves repeated subtraction with carries handled during the process. In GF(2), carry-less division computes the quotient of two binary numbers by performing polynomial division using XOR for subtraction and bit shifts, instead of traditional subtraction with carry. As a result, A carry-less variant of division, where the result is obtained by reducing the degree of the numerator using XOR operations.
- Modulo in GF(2): In standard arithmetic, the modulo operation involves division and the remainder is computed while considering carries during subtraction. In GF(2), carry-less modulo reduces a number by XORing it with a shifted version of the modulo until the degree of the number is less than that of the modulo polynomial, with no carry propagation. As a result, a carry-less variant of modulo, where the operation uses XOR and shifts to reduce the number’s degree without carry propagation.
- Squareing in GF(2): In standard arithmetic, squaring includes multiplying a number by itself with carries handled. In GF(2), squaring is simplified: each bit of the number is shifted to its corresponding squared position without carry propagation.
- Exponentiation Modulo in GF(2): In standard arithmetic, exponentiation involves repeated multiplication with carry propagation. In GF(2), power with modulo performs repeated carry-less multiplication (multi) combined with reduction using carry-less modulo.
- Invere in GF(2): In standard arithmetic, the modular inverse involves extended Euclidean algorithms with carries during subtraction and multiplication. In GF(2), inverse uses carry-less operations (div, multi, mod) to compute the inverse as per the polynomial division rules in binary fields.
# Copied from github.com/serengil/LightPHE/blob/master/lightphe/commons/binary_operations.py
def divide(a: int, b: int, p: int) -> int:
"""
Returns a_bin * (b_bin)^-1 (mod p)
Args:
a (int): nominator
b (int): denominator
p (int): modulo
Returns:
result (int): (a_bin * (b_bin)^-1 (mod p)) mod p
"""
result = mod(multi(a, inverse(b, p)), p)
return result
def multi(a: int, b: int) -> int:
"""
Multiply two binary numbers in GF(2).
Args:
a (int): first number
b (int): second number
Returns:
result (int): carry-less multiplication between a and b
"""
result = 0
shift = 0
while b > 0:
if b & 1: # Check if the least significant bit of b is 1
result ^= a << shift
shift += 1
b >>= 1 # Shift b to the right by 1
return result
def power_mod(num: int, exp: int, modulo: int) -> int:
"""
Calculate num^exp (mod m) in GF(2).
Args:
num (int): base
exp (int): exponent
modulo (int): modulo
Returns:
result (int): num^exp (mod m)
"""
result = 1
base = num % modulo
while exp > 0:
if exp & 1: # Check if the least significant bit of exp is 1
result = multi(base, result) # multiply result by base
result = mod(result, modulo) # apply modulo
base = square(base) # square the base
exp >>= 1 # right shift exp by 1
return result
def square(num: int) -> int:
"""
Square a binary number in GF(2).
Args:
num (int): number
Returns:
result (int): square of num
"""
result = 0
shift = 0
while num > 0:
if num & 1: # Check if the least significant bit of num is 1
result ^= 1 << (2 * shift) # Set the appropriate bit in the result
num >>= 1 # Right shift num by 1
shift += 1
return result
def mod(num: int, modulo: int) -> int:
"""
Perform modulo operation for binary numbers in GF(2).
Args:
num (int): number
modulo (int): modulo
Returns:
result (int): num mod modulo
"""
degP = num.bit_length() - 1
degR = modulo.bit_length() - 1
while degP >= degR and degR != 0:
shift = degP - degR
num ^= modulo << shift # Perform XOR to reduce the degree of num
degP = num.bit_length() - 1 # Update the degree of num
return num
def div(num: int, modulo: int) -> int:
"""
Return the quotient of the polynomial division num / modulo in GF(2).
Args:
num (int): numerator
modulo (int): denominator
Returns:
result (int): quotient
"""
deg_p = num.bit_length() - 1
deg_r = modulo.bit_length() - 1
q = 0
while deg_p >= deg_r:
shift = deg_p - deg_r
q |= 1 << shift # Set the corresponding bit in the quotient
num ^= modulo << shift # Perform XOR to reduce the degree of num
deg_p = num.bit_length() - 1 # Update the degree of num
return q
def inverse(num: int, modulo: int) -> int:
"""
Calculate the inverse of a binary number modulo a polynomial in GF(2).
Args:
num (int): number
modulo (int): modulo
Returns:
result (int): inverse of num mod modulo
"""
a, b = num, modulo
p1, p2 = 1, 0
while b != 1:
q = div(a, b)
r = mod(a, b)
a, b = b, r
p_a = p1 ^ multi(q, p2)
p1, p2 = p2, p_a
return p2
Koblitz Curves in Python
Building a Koblitz curve with LightPHE is very straightforward.
from lightphe.elliptic_curve_forms.koblitz import Koblitz curve = Koblitz(curve="k163")
Once the curve is initialized, you can perform operations such as point addition, doubling, and scalar multiplication.
# Base Point G = curve.G assert curve.is_on_curve(G) is True _2G = curve.double_point(G) assert curve.is_on_curve(_2G) is True _3G = curve.add_points(G, _2G) assert curve.is_on_curve(_2G) is True _2025G = curve.double_and_add(G, 2025) assert curve.is_on_curve(_2025G) is True
Homomorphic Encryption with Koblitz Curves
LightPHE supports several curves in Koblitz form. To use the Elliptic Curve ElGamal cryptosystem, simply set the form to “koblitz” and choose any Koblitz curve. This will enable additively homomorphic features.
from lightphe import LightPHE # build an Elliptic Curve ElGamal cryptosystem # in Koblitz form for K163 curve phe = LightPHE( algoritm_name = "EllipticCurve-ElGamal", form = "koblitz", curve = "k163" ) # define plaintexts m1 = 10 m2 = 5 # encrypt plaintexts c1 = phe.encrypt(m1) c2 = phe.encrypt(m2) # homomorphic addition c3 = c1 + c3 # proof of work assert phe.decrypt(c3) == m1 + m2
Conclusion
Elliptic curves over binary fields offer unique advantages in the realm of cryptography, especially in contexts like hardware design and the growing demand for secure systems in the Internet of Things (IoT). By utilizing the Koblitz form of elliptic curves, cryptography practitioners can take advantage of efficient operations in binary fields, which simplify computations and enhance performance, particularly in hardware implementations.
This post explored the structure and mathematical foundation of Koblitz curves over binary fields, emphasizing the simplified formulas for point addition and doubling, as well as the binary operations involved. Understanding these operations is essential for implementing elliptic curve-based cryptographic systems, which are central to modern encryption techniques such as Elliptic Curve ElGamal cryptosystems.
A Python implementation of the elliptic curve cryptosystem has been demonstrated, showing how the Koblitz form can be practically applied in code. In addition, the implementation showcases the additively homomorphic features of elliptic curve ElGamal, which are significant in encryption schemes that require the ability to perform operations on encrypted data without decryption. This homomorphic property enhances the flexibility and security of cryptographic systems by enabling secure computations directly on encrypted values.
With the increasing need for secure, efficient cryptographic solutions, elliptic curves over binary fields will continue to play a crucial role in shaping the future of cryptography, particularly as IoT and other hardware-intensive applications expand. Whether you are building encryption systems, implementing secure protocols, or working with hardware designs, a solid understanding of elliptic curves in Koblitz form will provide you with the tools to create secure and optimized cryptographic systems.
As cryptography continues to evolve, the significance of binary field operations, such as carry-less multiplication and division, will become even more pronounced, offering further improvements in computational efficiency and security for future technologies. The additively homomorphic features of the elliptic curve ElGamal in Koblitz form also point to a future where privacy-preserving computations are seamlessly integrated into everyday applications.
Support this blog if you do like!
