Find Consecutive X-Coordinate algorithm

Cryptography Asked by kmart875 on December 21, 2021

The question is as follows: Is there an algorithm to calculate a $(x,y)$ pair which is consecutive to an existing $x$-Coordinate on an elliptic curve?

Background Information for the curve:

Known Values: Prime Curve ($p$), Prime Multiplier ($N$), Trace ($P-N$), Curve is Half. Multipliers $(M_1 + M_2) = N$, $y$ Coordinates + Inverse $Y$ Coordinate = $P$.

Any help is greatly appreciated.

Update: An algorithm to calculate a $(x,y)$ pair and integer multiplier which is consecutive to an existing $x$-coordinate on the curve.

One Answer

Let $P = (x,y)$ be a point on the curve $E$ with the $y^2 = x^3 + ax + b$ with Weierstrass equation over the prime field $operatorname{GF}(p)$1, i.e. it satisfies the curve equation.

The consecutive $x$-coordinate point can be found with the below algorithm.

for i from 1 to number_of_poinst_on_the_curve
    temp = x + i mod p
    if  (temp, y) satisfies the curve equation
       return (temp,y')   
throw no_consecutive_element

1 This is used to simplify the algorithm. EC doesn't need to be defined over a prime finite field. In Cryptography, we use the general case of Finite Fields $operatorname{GF}(q=p^m), m in mathbb{Z}, mgeq 1$. Expect the prime field, the other fields have different representation for the elements.

For $y^2 = x^3 + x^2 + x$ over $GF(131)$

enter image description here

E = EllipticCurve(GF(131),[0,1,0,1,0])

P=E.lift_x(0) #lift can throw an error if there is no point with the given input
              #tested before that there is a point with x=0

plotE = E.plot()

for t in srange(1,129):
        R =  E.lift_x(t)
        plotE += line([P.xy(),R.xy()],color='red')
        P = R
    except ValueError:  


Though I don't see the direct effect on Cryptography, there are academic works on this;

Answered by kelalaka on December 21, 2021

Add your own answers!

Related Questions

Using XOR to derive a data key for ECIES

2  Asked on December 26, 2021 by maarten-bodewes


Computing PGP ed25519 and curve25519 keygrips?

2  Asked on December 21, 2021 by skaht


Find Consecutive X-Coordinate algorithm

1  Asked on December 21, 2021 by kmart875


Why we can’t implement AES 512 key size?

3  Asked on December 17, 2021 by hamedb71


How can Cipher Block Chaining (CBC) in SSL be attacked?

3  Asked on December 14, 2021 by antonpug


Subset Sum Hashes

1  Asked on December 14, 2021 by lev-knoblock


LWR parameter estimation

0  Asked on December 4, 2021 by mev


Ask a Question

Get help from others!

© 2022 All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP, SolveDir