main
1package x448
2
3import (
4 fp "github.com/cloudflare/circl/math/fp448"
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 w[1] = fp.Elt{ // x1 = S
13 0xfe, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
14 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
15 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
16 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xff,
17 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
18 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
19 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
20 }
21 fp.SetOne(&w[2]) // z1 = 1
22 w[3] = fp.Elt{ // x2 = G-S
23 0x20, 0x27, 0x9d, 0xc9, 0x7d, 0x19, 0xb1, 0xac,
24 0xf8, 0xba, 0x69, 0x1c, 0xff, 0x33, 0xac, 0x23,
25 0x51, 0x1b, 0xce, 0x3a, 0x64, 0x65, 0xbd, 0xf1,
26 0x23, 0xf8, 0xc1, 0x84, 0x9d, 0x45, 0x54, 0x29,
27 0x67, 0xb9, 0x81, 0x1c, 0x03, 0xd1, 0xcd, 0xda,
28 0x7b, 0xeb, 0xff, 0x1a, 0x88, 0x03, 0xcf, 0x3a,
29 0x42, 0x44, 0x32, 0x01, 0x25, 0xb7, 0xfa, 0xf0,
30 }
31 fp.SetOne(&w[4]) // z2 = 1
32
33 const n = 448
34 const h = 2
35 swap := uint(1)
36 for s := 0; s < n-h; s++ {
37 i := (s + h) / 8
38 j := (s + h) % 8
39 bit := uint((k[i] >> uint(j)) & 1)
40 copy(w[0][:], tableGenerator[s*Size:(s+1)*Size])
41 diffAdd(&w, swap^bit)
42 swap = bit
43 }
44 for s := 0; s < h; s++ {
45 double(&w[1], &w[2])
46 }
47 toAffine((*[fp.Size]byte)(k), &w[1], &w[2])
48}
49
50// ladderMontgomery calculates a generic scalar point multiplication
51// The algorithm implemented is the left-to-right Montgomery's ladder.
52func ladderMontgomery(k, xP *Key) {
53 w := [5]fp.Elt{} // [x1, x2, z2, x3, z3] order must be preserved.
54 w[0] = *(*fp.Elt)(xP) // x1 = xP
55 fp.SetOne(&w[1]) // x2 = 1
56 w[3] = *(*fp.Elt)(xP) // x3 = xP
57 fp.SetOne(&w[4]) // z3 = 1
58
59 move := uint(0)
60 for s := 448 - 1; s >= 0; s-- {
61 i := s / 8
62 j := s % 8
63 bit := uint((k[i] >> uint(j)) & 1)
64 ladderStep(&w, move^bit)
65 move = bit
66 }
67 toAffine((*[fp.Size]byte)(k), &w[1], &w[2])
68}
69
70func toAffine(k *[fp.Size]byte, x, z *fp.Elt) {
71 fp.Inv(z, z)
72 fp.Mul(x, x, z)
73 _ = fp.ToBytes(k[:], x)
74}
75
76var lowOrderPoints = [3]fp.Elt{
77 { /* (0,_,1) point of order 2 on Curve448 */
78 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
79 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
80 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
81 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
82 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
83 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
84 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
85 },
86 { /* (1,_,1) a point of order 4 on the twist of Curve448 */
87 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
88 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
89 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
90 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
91 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
92 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
93 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
94 },
95 { /* (-1,_,1) point of order 4 on Curve448 */
96 0xfe, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
97 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
98 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
99 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xff,
100 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
101 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
102 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
103 },
104}