2018.sagews

Check the book's example of a Weil pairing using sage's routine:

factor(631)

631

E=EllipticCurve(GF(631),[30,34])

R,Q=E.gens(); R.order(), Q.order(); R;Q

(130, 5) (233 : 164 : 1) (36 : 571 : 1)

P=26*R; P.order(); P; P+Q

5 (595 : 410 : 1) (121 : 387 : 1)

The book's two points are $(36,60)$, which is $2P+4Q$ for us,  and $(121,387)$, which is our$-P-Q$:

for i in range(0,5):
    for j in range(0,5):
        print(i,j); i*P+j*Q

(0, 0) (0 : 1 : 0) (0, 1) (36 : 571 : 1) (0, 2) (617 : 5 : 1) (0, 3) (617 : 626 : 1) (0, 4) (36 : 60 : 1) (1, 0) (595 : 410 : 1) (1, 1) (121 : 387 : 1) (1, 2) (531 : 18 : 1) (1, 3) (428 : 25 : 1) (1, 4) (511 : 23 : 1) (2, 0) (586 : 47 : 1) (2, 1) (575 : 624 : 1) (2, 2) (420 : 583 : 1) (2, 3) (289 : 269 : 1) (2, 4) (339 : 499 : 1) (3, 0) (586 : 584 : 1) (3, 1) (339 : 132 : 1) (3, 2) (289 : 362 : 1) (3, 3) (420 : 48 : 1) (3, 4) (575 : 7 : 1) (4, 0) (595 : 221 : 1) (4, 1) (511 : 608 : 1) (4, 2) (428 : 606 : 1) (4, 3) (531 : 613 : 1) (4, 4) (121 : 244 : 1)

m = matrix(GF(631),2,2,[2,4,-1,-1]); m; m.determinant()

[ 2 4] [630 630] 2

This means that the Weil pairing in the book should be the square of the Weil pairing of $P$ and $Q$ that we compute.

p=2*P+4*Q; q=-P-Q; p;q; p.weil_pairing(q,5)

(531 : 613 : 1) (428 : 606 : 1) 242

This $242$ is the value that the book finds for the Weil pairing of its two points.

P.weil_pairing(Q,5)

242

_^2

242

This is the expected answer.  Note that sage understands that the output $228$ is a number mod $631$.

Now we try a very serious example, taken from a paper by my former student Dave Freeman:

q=6462310997348816962203124910505252082673338846966431201635262694402825461643; factor(q)

6462310997348816962203124910505252082673338846966431201635262694402825461643

Thus $q$ is a fairly large ($252$ bits) prime number.

E=EllipticCurve(GF(q),[-3,4946538166640251374274628820269694144249181776013154863288086212076808528141])

time E.order()

6462310997348816962203124910505252082512561846156628595562776459306292101261 Time: CPU 0.02 s, Wall: 12.98 s

n=_; factor(n)

6462310997348816962203124910505252082512561846156628595562776459306292101261

Thus the order of $E$ over GF$(q)$ is a prime number whose size is roughly that of $q$.

Mod(q,n).multiplicative_order()

10

This implies that the embedding degree is $10$ in this case.

K.<a>= GF(q^10)

time a.minimal_polynomial()

x^10 + 4046801187384385238607860828586071843611964326142986950226638705525478658673*x^9 + 5032959350959187998229560155278389426952337591144687525754820033979188974138*x^8 + 1495166367908406267566239262738983701824221854478121186176350709324714368439*x^7 + 5618278623462863088169339948670502280726641717220290869321071807915787570159*x^6 + 768497711817400373790628765577110788209199953609677020445204779584296514482*x^5 + 3909633414633175526578102643021482055950274485696606206486433012316592383727*x^4 + 4637996850489611488653064357348304679116556317850004762339081484813733504065*x^3 + 501575629307086254708244051394930463458458279512065149773133722748938324530*x^2 + 2532625670602441390340294958048292903189674127298507784425801304162686321470*x + 2845740050437884183520758838895693170305041635216153341473809858422880741512 Time: CPU 0.48 s, Wall: 0.49 s

P=E.gens(); P

((3976970442976636840450157747309011243652550859054367957179706659389438176350 : 3011735932494905909386675806705262729615299258071914933147214733178710941393 : 1),)

time E.change_ring(K).order()/n^2

3041605158780020331840786509660305255300134925723012643175926829845549839378380867225169137973156960170136211096545399736886202693846814132675107535675184718527017841043283819851472435058369925131617141811201600053263953749586850406416236455934702680906834055150378361328500022656004600621354872076309713719644116167652042308227937021218569032544281971777483690466544373658227433729794648211922171444884693210552354239889930850845346796473045899498962761997289579750141090729661175614611837688204924541642618835905269574332231972055806351010481354871938805233799744945188721887738663154626648771557214802567 Time: CPU 0.66 s, Wall: 13.14 s

As expected, the ratio is a whole number.  The following command seems to "take forever" on my laptop, so I don't want to run it:

time P,Q=E.change_ring(K).gens(); P; Q

Here is some distortion, starting with $p=607$ (random prime less than 1000, turned out to be 3 mod 4):

p=607; E=EllipticCurve(GF(p),[1,0]); E

Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 607

E.order()

608

This should be no surprise!  When you take $y^2=x^3+x$ over the field with $p$ elements, and $p$ is $3$ mod $4$, you get a supersingular elliptic curve!  We didn't like such curves because of the low embedding degree, but now we like them....

factor(608)

2^5 * 19

E.gens()

((345 : 342 : 1),)

One generator is $(510,306)$; this was output the last time I ran the command!

l=19; P = Integer(608/19)*E([510,306]); P

(154 : 502 : 1)

This is one point of order $19$.  Note that "gens" is not deterministic, so you can get difference generators when you apply the command twice in a row.

F.<x> = GF(p)[]; K.<alpha> = GF(607^2, name='alpha', modulus=x^2+1 )

K

Finite Field in alpha of size 607^2

alpha^2

606

F=E.change_ring(K) # completely different use for the letter 'F'!

Q=F(-154,alpha*502); Q; Q.order()

(453 : 502*alpha : 1) 19

P = Integer(608/19)*F([510,306]); P; P.order()

(154 : 502 : 1) 19

P.weil_pairing(Q,19)

414*alpha + 40

_.multiplicative_order()

19

Now let's reproduce the book's example.

p=547; E=EllipticCurve(GF(p),[1,0]); E

Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 547

E.abelian_group()

(Multiplicative Abelian Group isomorphic to C548, ((124 : 342 : 1),))

factor(548)

2^2 * 137

l=137

One generator of the group of points is $(512,238)$; gotten by a previous application of the commands that are above.

4*E(512,238)

(46 : 4 : 1)

The book finds $(67,481)$ instead of our point $(46,4)$.  Their point is $133$ times ours!  We can find this by running the following command:

for i in range(1,137):
    print i
    i*E(46,4)

F.<x> = GF(p)[]  # as before -- F is now a field instead of an elliptic curve

K.<alpha> = GF(p^2, name='alpha', modulus=x^2+1 ); F=E.change_ring(K)  # back to being an el. curve!

P=F(46,4); Q=F(-46,4*alpha); zeta=P.weil_pairing(Q,l)

zeta.multiplicative_order()

137

The root of unity in the book should be our zeta to the power $133^2$.

zeta^(133^2)

452*alpha + 37

And it is---on the nose!

Now let's do a "one-round three-way key exchange"with Alice, Bob and Connie; assume their secrets are 12, 34 and 56, respectively.

P=F(46,4); P

(46 : 4 : 1)

PA=12*P; PB = 34*P; PC = 56*P; PA; PB; PC

(256 : 394 : 1) (185 : 461 : 1) (504 : 50 : 1)

These three points are published for all to see.

PA.weil_pairing(F(-185,alpha*461),l)^56

59*alpha + 158

PB.weil_pairing(F(-504,50*alpha),l)^12

59*alpha + 158

PC.weil_pairing(F(-256,394*alpha),l)^34

59*alpha + 158

The three people Bob, Alice, Connie have a shared secret $158+59\alpha$.  What they do with this is their own business.

END OF COURSE!