main
1package x25519
2
3import (
4 fp "github.com/cloudflare/circl/math/fp25519"
5)
6
7// ladderJoye calculates a fixed-point multiplication with the generator point.
8// The algorithm is the right-to-left Joye's ladder as described
9// in "How to precompute a ladder" in SAC'2017.
10func ladderJoye(k *Key) {
11 w := [5]fp.Elt{} // [mu,x1,z1,x2,z2] order must be preserved.
12 fp.SetOne(&w[1]) // x1 = 1
13 fp.SetOne(&w[2]) // z1 = 1
14 w[3] = fp.Elt{ // x2 = G-S
15 0xbd, 0xaa, 0x2f, 0xc8, 0xfe, 0xe1, 0x94, 0x7e,
16 0xf8, 0xed, 0xb2, 0x14, 0xae, 0x95, 0xf0, 0xbb,
17 0xe2, 0x48, 0x5d, 0x23, 0xb9, 0xa0, 0xc7, 0xad,
18 0x34, 0xab, 0x7c, 0xe2, 0xee, 0xcd, 0xae, 0x1e,
19 }
20 fp.SetOne(&w[4]) // z2 = 1
21
22 const n = 255
23 const h = 3
24 swap := uint(1)
25 for s := 0; s < n-h; s++ {
26 i := (s + h) / 8
27 j := (s + h) % 8
28 bit := uint((k[i] >> uint(j)) & 1)
29 copy(w[0][:], tableGenerator[s*Size:(s+1)*Size])
30 diffAdd(&w, swap^bit)
31 swap = bit
32 }
33 for s := 0; s < h; s++ {
34 double(&w[1], &w[2])
35 }
36 toAffine((*[fp.Size]byte)(k), &w[1], &w[2])
37}
38
39// ladderMontgomery calculates a generic scalar point multiplication
40// The algorithm implemented is the left-to-right Montgomery's ladder.
41func ladderMontgomery(k, xP *Key) {
42 w := [5]fp.Elt{} // [x1, x2, z2, x3, z3] order must be preserved.
43 w[0] = *(*fp.Elt)(xP) // x1 = xP
44 fp.SetOne(&w[1]) // x2 = 1
45 w[3] = *(*fp.Elt)(xP) // x3 = xP
46 fp.SetOne(&w[4]) // z3 = 1
47
48 move := uint(0)
49 for s := 255 - 1; s >= 0; s-- {
50 i := s / 8
51 j := s % 8
52 bit := uint((k[i] >> uint(j)) & 1)
53 ladderStep(&w, move^bit)
54 move = bit
55 }
56 toAffine((*[fp.Size]byte)(k), &w[1], &w[2])
57}
58
59func toAffine(k *[fp.Size]byte, x, z *fp.Elt) {
60 fp.Inv(z, z)
61 fp.Mul(x, x, z)
62 _ = fp.ToBytes(k[:], x)
63}
64
65var lowOrderPoints = [5]fp.Elt{
66 { /* (0,_,1) point of order 2 on Curve25519 */
67 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
68 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
69 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
70 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
71 },
72 { /* (1,_,1) point of order 4 on Curve25519 */
73 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
74 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
75 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
76 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
77 },
78 { /* (x,_,1) first point of order 8 on Curve25519 */
79 0xe0, 0xeb, 0x7a, 0x7c, 0x3b, 0x41, 0xb8, 0xae,
80 0x16, 0x56, 0xe3, 0xfa, 0xf1, 0x9f, 0xc4, 0x6a,
81 0xda, 0x09, 0x8d, 0xeb, 0x9c, 0x32, 0xb1, 0xfd,
82 0x86, 0x62, 0x05, 0x16, 0x5f, 0x49, 0xb8, 0x00,
83 },
84 { /* (x,_,1) second point of order 8 on Curve25519 */
85 0x5f, 0x9c, 0x95, 0xbc, 0xa3, 0x50, 0x8c, 0x24,
86 0xb1, 0xd0, 0xb1, 0x55, 0x9c, 0x83, 0xef, 0x5b,
87 0x04, 0x44, 0x5c, 0xc4, 0x58, 0x1c, 0x8e, 0x86,
88 0xd8, 0x22, 0x4e, 0xdd, 0xd0, 0x9f, 0x11, 0x57,
89 },
90 { /* (-1,_,1) a point of order 4 on the twist of Curve25519 */
91 0xec, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
92 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
93 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
94 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f,
95 },
96}