1
$\begingroup$

Given the following curve:

$$ y^3 = x^2 - 7x $$

over the finite field $GF(271)$.

We have $P = (201, 247)$ belongs to the curve:

$$ 247^2 \equiv 201^3 - 7 \cdot 201 \equiv 34 \mod 271 $$

We also have $Q = (201, 24)$ belongs to the curve:

$$ 24^2 \equiv 201^3 - 7 \cdot 201 \equiv 34 \mod 271 $$

So, how to add $R = P+Q$ ? As far as I know, having $m=271$:

  • if $P=Q$, then $t = (3x^2+a)/(2y) \mod m$, where $1/(2y) = (2y)^{-1} \mod m$
  • if $P \neq Q$, then $t = (y_q - y_p)/(x_q - x_p)$, where $1/(x_q - x_p) = (x_q - x_p)^{-1} \mod m$

Then

$$x_r = t^2 - x_p - x_q \mod m$$

and:

$$y_r = t(x_p-x_r) - y_p \mod m$$

However, in this case we would have division by zero since $P \neq Q$ and $x_p = x_q$. How to proceed?

$\endgroup$
0

1 Answer 1

4
$\begingroup$

The obvious mistake is the slope. The two points are on the same vertical line. Indeed, $P = -Q$ and their sum is the group identity.

This requires a special case on the Affine Coordinates;

  • If $x_1 = x_2 $ and $y_1 = - y_2$, that is $Q =(x_2,y_2)=(x_1,−y_1)=−P$, then $$P+Q = P + (-P) = \mathcal{O}$$

    In your case $247 + 24 = 271$ so $x_1 = x_2$ and $y_1 = -y_1$.


Addendum

Below is the graph of this curve;

enter image description here

As we can see, the $P$ and $Q$ are on the same vertical line and have the same distance to the center line ( black)

The Sagemath code for verification and plot of the curve.

p = 271
a = -7
b = 0

K = GF(p)
E = EllipticCurve(K,[a,b])
print(E)

P = E(201,247)
Q = E(201,24)
R = P+ Q
print(R)

plotE = E.plot()
plotE += line([(0,136),(272,136)],color='black')
plotE += line([(201,24),(201,247)],color='blue')
plotE += point([201,247], color='red')
plotE += point([201,24], color='red')
plotE += text("P",(201,255), color='red')
plotE += text("Q",(201,18), color='red')

plotE

$\endgroup$
4
  • 1
    $\begingroup$ thanks foir pointing out my mistake! I missed this simple point $\endgroup$ Jun 14 at 17:16
  • $\begingroup$ @blackyellow this was not HW, right? I've forgot to ask. $\endgroup$
    – kelalaka
    Jun 14 at 18:48
  • 1
    $\begingroup$ what I'm doing is trying to implement a program to sign/verify documents using EC $\endgroup$ Jun 15 at 0:50
  • 2
    $\begingroup$ @blackyellow If what you're doing is not some toy implementation like for a school project, you'll really want to use an existing cryptosystem design if you want it to be secure. $\endgroup$
    – Myria
    Jun 15 at 21:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.