ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 15 Jun 2020 17:01:42 +0200Halving Point on curve25519https://ask.sagemath.org/question/49463/halving-point-on-curve25519/ Hi there,
Is there any ways in sagemath to half a point in curve25519? I found that mod inverse of 2 are not defined in this curve.
Thanks beforeThu, 09 Jan 2020 09:30:27 +0100https://ask.sagemath.org/question/49463/halving-point-on-curve25519/Answer by John Cremona for <p>Hi there,</p>
<p>Is there any ways in sagemath to half a point in curve25519? I found that mod inverse of 2 are not defined in this curve.</p>
<p>Thanks before</p>
https://ask.sagemath.org/question/49463/halving-point-on-curve25519/?answer=51609#post-id-51609If E is your elliptic curve and P is a point on E then P.division_points(2) returns a list of solutions Q to 2*Q=P.Thu, 28 May 2020 17:46:17 +0200https://ask.sagemath.org/question/49463/halving-point-on-curve25519/?answer=51609#post-id-51609Answer by dan_fulea for <p>Hi there,</p>
<p>Is there any ways in sagemath to half a point in curve25519? I found that mod inverse of 2 are not defined in this curve.</p>
<p>Thanks before</p>
https://ask.sagemath.org/question/49463/halving-point-on-curve25519/?answer=52015#post-id-52015Wikipedia provides the following information on the curve:
[https://en.wikipedia.org/wiki/Curve25519](https://en.wikipedia.org/wiki/Curve25519)
So we can initialize it - with some related ingredients - in sage as follows:
p = 2^255 - 19
F = GF(p)
E = EllipticCurve( F, [0, 486662, 0, 1, 0] )
q = 2^252 + 27742317777372353535851937790883648493
ord = 8 * q
G = E.lift_x(9) # generator of a subgroup of E(F) of order q
Note that the order of "the curve" is $8q=|E(F)|$, an even number. So it is not always possible to build $Q=\frac 12 P$ for some $P\in E(F)$, but we can do this after adjoining $\sqrt 2$, since
sage: F(2).is_square()
False
and the extension $F[\sqrt 2]$ is $\cong\Bbb F_{p^2}$.
But in practice, for cryptographic reasons, a subgroup of index $8$ (i.e. of order $q$) is used only. This group is generated by a point of the shape $(9,?)$, and sage gives a `lift_x` point for the value $9$ as above. We can check that $G$ has this (prime) order:
sage: G
(9 : 43114425171068552920764898935933967039370386198203806730763910166200978582548 : 1)
sage: q*G
(0 : 1 : 0)
sage: q.is_prime()
True
The question is now, if i transpose it correctly, the following one:
> Fix some $n$, and construct $P=nG$.
> Submit now $P$, so the information on
> $n$ is lost. How can we get one point $Q$ such that $2Q=P$?
The answer is simple, we just invert $2$ modulo $q$. This is in a quick experiment:
sage: half_mod_q = ZZ( (q+1)/2 )
sage: half_mod_q
3618502788666131106986593281521497120428558179689953803000975469142727125495
sage: n = 2020 # my secret n
sage: P = n*G
sage: P
(20456558607578987432334349036785445183540679505228589881934565555120204340945 :
33436819791958610943855936500332845106265211955865934902600537963312721779170 :
1)
sage: Q = half_mod_q * P
sage: Q
(37018768415917781021250140199383617818364544364725057743698692568223983613701 :
18895822023094723102686898411321685453553895391224520755056144094371343510515 :
1)
sage: 2*Q == P
True
(Code was manually adjusted.)
Mon, 15 Jun 2020 17:01:42 +0200https://ask.sagemath.org/question/49463/halving-point-on-curve25519/?answer=52015#post-id-52015