Score:3

Crypto

Is it possible to calculate multiplication inverse of a point on elliptic curve?

Lordi

4/12/23, 1:22 PM

The title must be confusing. Imagine we have this curve:

$y^2 = x^3 + 9x + 17$ over $\mathbb F_{23}$

And we know

[4]P = (19 , 20)

[8]P = (12 , 17)

If we only have the value of $[8]P$, Is it possible to calculate $2^{-1}X$ and $2^{-1}Y$ of $[8]P$ to get $[4]P$?

124

0 + 0

elliptic-curves

public-key

kelalaka

4/12/23, 2:38 PM

Point halving: [Point halving on elliptic curves of even order](https://crypto.stackexchange.com/q/66106/18298) and article [Point halving on elliptic curves of even order](https://arxiv.org/pdf/0706.4379.pdf). I've corrected the notation, and even we say $x(P)$ for the x-coordinate of point $P$. This curve has an even order = 32, so it is applicable but not the way you look. Point doubling doesn't work in that way.

kelalaka

4/12/23, 2:47 PM

[If you look at the addition formulas](https://crypto.stackexchange.com/a/66296/18298) you will see that when $P_1 = P_2 = [2]P_1$ is not multiplication by 2. You can plug your numbers and do the arithmetic in the first link to find it without discrete log.

Lordi

4/12/23, 3:46 PM

@kelalaka Thanks for your answer. Is point halving possible on elliptic curves of odd order?

kelalaka

4/12/23, 4:17 PM

Be careful halving in even order may result in a double solution that prevents solving DLOG. In the odd case, let $n = 2k-1$ be the order then we can find the halve as; $[1/2]G = [k]G$ why? Because $[2k-1]G = \mathcal{O}$ then $[2k-1]G + G = G$ so $[k]G = [1/2]G$. This is a well-defined map for abelian groups of odd order.

kelalaka

4/14/23, 11:04 AM

Now, you can vote up and accept in Cryptography.SE. upvote if the answer is good, accept if the answer is satisfactory.

Score:1

Crypto

Fractalice

4/13/23, 6:45 AM

Since 2 divides the group order (which is 32), there are two preimages. They can be found as roots of the multiplication-by-2 polynomial minus the target $x$ (which can be computed from division polynomials).

Example in Sage:

sage: E = EllipticCurve(GF(23), [9, 17])                                                                                                                                                                                                      
sage: E.multiplication_by_m(2)                                                                                                                                                                                                                
((x^4 + 5*x^2 + 2*x - 11)/(4*x^3 - 10*x - 1),
 (8*x^6*y - 8*x^4*y + 6*x^3*y + 3*x^2*y + 3*x*y + 6*y)/(-5*x^6 + 2*x^4 - 9*x^3 + 9*x^2 + 11*x + 4))

These are the two rational maps for computing $x$ and $y$ of the point $[2](x,y)$. We want $x$ to be equal 19, so:

sage: (E.multiplication_by_m(2)[0] - 19)
  .numerator()
  .univariate_polynomial()
  .roots(multiplicities=False)
[20, 10]

We can verify that $[2](20, *) = (19, *)$. Note that the sign of $y$ has to be chosen to match the output sign.

sage: P = E.lift_x(20)                                                                                                                                                                                                                        
sage: 2*P                                                                                                                                                                                                                                     
(19 : 3 : 1)
sage: 2*(-P)                                                                                                                                                                                                                                  
(19 : 20 : 1)

Can be repeated twice to get 4-roots, or use the multiplication-by-4 map directly (which is a bit less efficient).

0 + 0

kelalaka

4/13/23, 11:59 AM

Is there a formal definition of `multiplication_by_m`

Fractalice

4/14/23, 6:02 AM

@kelalaka `multiplication_by_m` is a pair of functions $(f(x),y\cdot g(x))$, such that this pair equals to $[n]P$ when $P=(x,y)$. On the wikipedia page about division polynomials I linked, there are formulas for constructing $f(x)$ and $g(x)$, which are rational functions.

kelalaka

4/14/23, 11:03 AM

And. you may edit the question so that for future references it can be found easier.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Is it possible to calculate multiplication inverse of a point on elliptic curve?

TH: เป็นไปได้ไหมที่จะคำนวณการคูณผกผันของจุดบนเส้นโค้งวงรี?

RO: Este posibil să se calculeze multiplicarea inversă a unui punct pe curba eliptică?

RU: Можно ли вычислить обратное умножение точки на эллиптической кривой?

VI: Có thể tính nghịch đảo phép nhân của một điểm trên đường cong elip không?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.