1 // Package fp448 provides prime field arithmetic over GF(2^448-2^224-1).
2 package fp448
3
4 import (
5 "errors"
6
7 "github.com/cloudflare/circl/internal/conv"
8 )
9
10 // Size in bytes of an element.
11 const Size = 56
12
13 // Elt is a prime field element.
14 type Elt [Size]byte
15
16 func (e Elt) String() string { return conv.BytesLe2Hex(e[:]) }
17
18 // p is the prime modulus 2^448-2^224-1.
19 var p = Elt{
20 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
21 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
22 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
23 0xff, 0xff, 0xff, 0xff, 0xfe, 0xff, 0xff, 0xff,
24 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
25 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
26 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
27 }
28
29 // P returns the prime modulus 2^448-2^224-1.
30 func P() Elt { return p }
31
32 // ToBytes stores in b the little-endian byte representation of x.
33 func ToBytes(b []byte, x *Elt) error {
34 if len(b) != Size {
35 return errors.New("wrong size")
36 }
37 Modp(x)
38 copy(b, x[:])
39 return nil
40 }
41
42 // IsZero returns true if x is equal to 0.
43 func IsZero(x *Elt) bool { Modp(x); return *x == Elt{} }
44
45 // IsOne returns true if x is equal to 1.
46 func IsOne(x *Elt) bool { Modp(x); return *x == Elt{1} }
47
48 // SetOne assigns x=1.
49 func SetOne(x *Elt) { *x = Elt{1} }
50
51 // One returns the 1 element.
52 func One() (x Elt) { x = Elt{1}; return }
53
54 // Neg calculates z = -x.
55 func Neg(z, x *Elt) { Sub(z, &p, x) }
56
57 // Modp ensures that z is between [0,p-1].
58 func Modp(z *Elt) { Sub(z, z, &p) }
59
60 // InvSqrt calculates z = sqrt(x/y) iff x/y is a quadratic-residue. If so,
61 // isQR = true; otherwise, isQR = false, since x/y is a quadratic non-residue,
62 // and z = sqrt(-x/y).
63 func InvSqrt(z, x, y *Elt) (isQR bool) {
64 // First note that x^(2(k+1)) = x^(p-1)/2 * x = legendre(x) * x
65 // so that's x if x is a quadratic residue and -x otherwise.
66 // Next, y^(6k+3) = y^(4k+2) * y^(2k+1) = y^(p-1) * y^((p-1)/2) = legendre(y).
67 // So the z we compute satisfies z^2 y = x^(2(k+1)) y^(6k+3) = legendre(x)*legendre(y).
68 // Thus if x and y are quadratic residues, then z is indeed sqrt(x/y).
69 t0, t1 := &Elt{}, &Elt{}
70 Mul(t0, x, y) // x*y
71 Sqr(t1, y) // y^2
72 Mul(t1, t0, t1) // x*y^3
73 powPminus3div4(z, t1) // (x*y^3)^k
74 Mul(z, z, t0) // z = x*y*(x*y^3)^k = x^(k+1) * y^(3k+1)
75
76 // Check if x/y is a quadratic residue
77 Sqr(t0, z) // z^2
78 Mul(t0, t0, y) // y*z^2
79 Sub(t0, t0, x) // y*z^2-x
80 return IsZero(t0)
81 }
82
83 // Inv calculates z = 1/x mod p.
84 func Inv(z, x *Elt) {
85 // Calculates z = x^(4k+1) = x^(p-3+1) = x^(p-2) = x^-1, where k = (p-3)/4.
86 t := &Elt{}
87 powPminus3div4(t, x) // t = x^k
88 Sqr(t, t) // t = x^2k
89 Sqr(t, t) // t = x^4k
90 Mul(z, t, x) // z = x^(4k+1)
91 }
92
93 // powPminus3div4 calculates z = x^k mod p, where k = (p-3)/4.
94 func powPminus3div4(z, x *Elt) {
95 x0, x1 := &Elt{}, &Elt{}
96 Sqr(z, x)
97 Mul(z, z, x)
98 Sqr(x0, z)
99 Mul(x0, x0, x)
100 Sqr(z, x0)
101 Sqr(z, z)
102 Sqr(z, z)
103 Mul(z, z, x0)
104 Sqr(x1, z)
105 for i := 0; i < 5; i++ {
106 Sqr(x1, x1)
107 }
108 Mul(x1, x1, z)
109 Sqr(z, x1)
110 for i := 0; i < 11; i++ {
111 Sqr(z, z)
112 }
113 Mul(z, z, x1)
114 Sqr(z, z)
115 Sqr(z, z)
116 Sqr(z, z)
117 Mul(z, z, x0)
118 Sqr(x1, z)
119 for i := 0; i < 26; i++ {
120 Sqr(x1, x1)
121 }
122 Mul(x1, x1, z)
123 Sqr(z, x1)
124 for i := 0; i < 53; i++ {
125 Sqr(z, z)
126 }
127 Mul(z, z, x1)
128 Sqr(z, z)
129 Sqr(z, z)
130 Sqr(z, z)
131 Mul(z, z, x0)
132 Sqr(x1, z)
133 for i := 0; i < 110; i++ {
134 Sqr(x1, x1)
135 }
136 Mul(x1, x1, z)
137 Sqr(z, x1)
138 Mul(z, z, x)
139 for i := 0; i < 223; i++ {
140 Sqr(z, z)
141 }
142 Mul(z, z, x1)
143 }
144
145 // Cmov assigns y to x if n is 1.
146 func Cmov(x, y *Elt, n uint) { cmov(x, y, n) }
147
148 // Cswap interchanges x and y if n is 1.
149 func Cswap(x, y *Elt, n uint) { cswap(x, y, n) }
150
151 // Add calculates z = x+y mod p.
152 func Add(z, x, y *Elt) { add(z, x, y) }
153
154 // Sub calculates z = x-y mod p.
155 func Sub(z, x, y *Elt) { sub(z, x, y) }
156
157 // AddSub calculates (x,y) = (x+y mod p, x-y mod p).
158 func AddSub(x, y *Elt) { addsub(x, y) }
159
160 // Mul calculates z = x*y mod p.
161 func Mul(z, x, y *Elt) { mul(z, x, y) }
162
163 // Sqr calculates z = x^2 mod p.
164 func Sqr(z, x *Elt) { sqr(z, x) }
165