Reduced Point Additive Operation

EC Cryptography Tutorials - Herong's Tutorial Examples

∟Reduced Point Additive Operation

This section describes what is the reduced point additive operation in algebraic format, which is the same as the original additive operation reduced by modular arithmetic of prime number p.

From the previous tutorial, we learned that the original additive operation based on the rule of chord operation failed to construct an Abelian group on a reduced elliptic curve.

Let's look at the algebraic equations for the additive operation presented earlier in the book again:

Original addition operation based rule of chord operation:

For any two given points on the curve:
   P = (x_P, y_P)
   Q = (x_Q, y_Q)

R = P + Q is a third point on the curve:
   R = (x_R, y_R)

Where:
   x_R = m² - x_P - x_Q              (8)
   y_R = m(x_P - x_R) - y_P           (9)

If P != Q, m is determined by:
       y_P - y_Q
   m = ---------                (10)
       x_P - x_Q

If P = Q, m is determined by:
       3(x_P)² + a
   m = ---------                 (6)
         2(y_P)

The issue with this addition operation is that the resulting point R is not an integer point and it is not in the first region of [(0,0) ... (p-1,p-1)]!

One quick way to resolve the issue to apply the same modular arithmetic reduction as the reduced elliptic equation on coordinates (x_R, y_R) of the resulting point R. This will bring it into the first region as an integer point.

Reduced addition operation based rule of chord operation:

For any two given points on the curve:
   P = (x_P, y_P)
   Q = (x_Q, y_Q)

R = P + Q is a third point on the curve:
   R = (x_R, y_R)

Where:
   x_R = m² - x_P - x_Q (mod p)     (11)
   y_R = m(x_P - x_R) - y_P (mod p)  (12)

If P != Q, m is determined by:
       y_P - y_Q
   m = ---------                (10)
       x_P - x_Q

If P = Q, m is determined by:
       3(x_P)² + a
   m = ---------                 (6)
         2(y_P)

If m is an integer, (x_R, y_R) of the resulting point R will be integers. Applying modular arithmetic reduction on integers is easy.

However, if m is rational number, (x_R, y_R) of the result point R will be rational numbers. Applying modular arithmetic reduction on rational numbers is tricky. We will discuss it in the next tutorial.

By the way, m will never be a true real number. Because P and Q are integer points and coefficients of the elliptic curve are integers. Equation (10) or (6) will only results to integers or rational numbers.

After reducing the resulting point to an integer point in the first region, we need to proof that it is still on the reduced elliptic curve. See next tutorials for more details.