OLD | NEW |
---|---|
(Empty) | |
1 // Copyright (c) 2011 The Chromium Authors. All rights reserved. | |
2 // Use of this source code is governed by a BSD-style license that can be | |
3 // found in the LICENSE file. | |
4 | |
5 // This is an implementation of the P224 elliptic curve group. It's written to | |
6 // be short and simple rather than fast, although it's still constant-time. | |
7 | |
8 #include <string.h> | |
9 #include <arpa/inet.h> | |
10 | |
11 #include "crypto/p224.h" | |
12 | |
13 namespace { | |
14 | |
15 // Field element functions. | |
16 // | |
17 // The field that we're dealing with is ℤ/pℤ where p = 2**224 - 2**96 + 1. | |
18 // | |
19 // Field elements are represented by a FieldElement, which is a typedef to an | |
20 // array of 8 uint32's. The value of a FieldElement, a, is: | |
21 // a[0] + 2**28·a[1] + 2**56·a[1] + ... + 2**196·a[7] | |
22 // | |
23 // Using 28-bit limbs means that there's only 4 bits of headroom, which is less | |
24 // than we would really like. But it has the useful feature that we hit 2**224 | |
25 // exactly, making the reflections during a reduce much nicer. | |
26 | |
27 typedef crypto::P224::FieldElement FieldElement; | |
Wez
2011/11/02 23:46:06
nit: Why not just "using crypto::P224::FieldElemen
agl
2011/11/03 17:20:49
Doesn't work I'm afraid:
../../crypto/p224.cc:35:
| |
28 | |
29 // Add computes *out = a+b | |
30 // | |
31 // Bounds on a and b are such that the sum of each corresponding limb of a and | |
32 // b mustn't exceed 2**32. | |
Wez
2011/11/02 23:46:06
Express this similarly to the comment on Sub(), fo
agl
2011/11/03 17:20:49
Done.
| |
33 void Add(FieldElement* out, const FieldElement& a, const FieldElement& b) { | |
34 for (int i = 0; i < 8; i++) { | |
35 (*out)[i] = a[i] + b[i]; | |
36 } | |
37 } | |
38 | |
39 static const uint32 kTwo31p3 = (1u<<31) + (1u<<3); | |
40 static const uint32 kTwo31m3 = (1u<<31) - (1u<<3); | |
41 static const uint32 kTwo31m15m3 = (1u<<31) - (1u<<15) - (1u<<3); | |
42 // kZero31ModP is 0 mod p where bit 31 is set in all limbs. | |
43 static const FieldElement kZero31ModP = { | |
44 kTwo31p3, kTwo31m3, kTwo31m3, kTwo31m15m3, | |
45 kTwo31m3, kTwo31m3, kTwo31m3, kTwo31m3 | |
Wez
2011/11/02 23:46:06
It would be great to clarify with _why_ we want to
agl
2011/11/03 17:20:49
That could go on for a while so I've cited hthe su
Wez
2011/11/03 20:03:46
What I had in mind was a sentence explaining that
agl
2011/11/04 20:13:22
Have updated the comment.
| |
46 }; | |
47 | |
48 // Sub computes *out = a-b | |
49 // | |
50 // a[i], b[i] < 2**30 | |
51 // out[i] < 2**32 | |
52 void Sub(FieldElement* out, const FieldElement& a, const FieldElement& b) { | |
Wez
2011/11/02 23:46:06
nit: Sub -> Subtract, according to the style guide
agl
2011/11/03 17:20:49
Done.
| |
53 for (int i = 0; i < 8; i++) { | |
54 (*out)[i] = a[i] + kZero31ModP[i] - b[i]; | |
Wez
2011/11/02 23:46:06
It looks like the "zero" constant here is being us
agl
2011/11/03 17:20:49
Have also cited the same section in ecc.html.
| |
55 } | |
56 } | |
57 | |
58 static const uint64 kTwo63p35 = (1ull<<63) + (1ull<<35); | |
59 static const uint64 kTwo63m35 = (1ull<<63) - (1ull<<35); | |
60 static const uint64 kTwo63m35m19 = (1ull<<63) - (1ull<<35) - (1ull<<19); | |
61 // kZero31ModP is 0 mod p where bit 63 is set in all limbs. | |
Wez
2011/11/02 23:46:06
kZero31ModP -> kZero63ModP
agl
2011/11/03 17:20:49
Done.
| |
62 static const uint64 kZero63ModP[8] = { | |
63 kTwo63p35, kTwo63m35, kTwo63m35, kTwo63m35, | |
64 kTwo63m35m19, kTwo63m35, kTwo63m35, kTwo63m35, | |
65 }; | |
66 | |
67 static const uint32 kBottom12Bits = 0xfff; | |
Wez
2011/11/02 23:46:06
You define this but never use it?
agl
2011/11/03 17:20:49
Removed.
| |
68 static const uint32 kBottom28Bits = 0xfffffff; | |
69 | |
70 // LargeFieldElement also represents an element of the field. The limbs are | |
71 // still spaced 28-bits apart and in little-endian order. | |
Wez
2011/11/02 23:46:06
Since LargeFieldElement still represents 28-bits w
agl
2011/11/03 17:20:49
It only has coefficients up to 392 bits, but it's
Wez
2011/11/03 20:03:46
Would it be correct to say that each limb "represe
agl
2011/11/04 20:13:22
"represents"? Not really I'm afraid.
| |
72 typedef uint64 LargeFieldElement[15]; | |
73 | |
74 // ReduceLarge converts a LargeFieldElement to a FieldElement. | |
75 // | |
76 // in[i] < 2**62 | |
77 void ReduceLarge(FieldElement* out, LargeFieldElement& in) { | |
Wez
2011/11/02 23:46:06
You're modifying LargeFieldElement, so it should r
agl
2011/11/03 17:20:49
Done.
| |
78 for (int i = 0; i < 8; i++) { | |
79 in[i] += kZero63ModP[i]; | |
80 } | |
81 | |
82 // Eliminate the coefficients at 2**224 and greater. | |
Wez
2011/11/02 23:46:06
Explain that you're using a mod p operation to red
agl
2011/11/03 17:20:49
Done.
| |
83 for (int i = 14; i >= 8; i--) { | |
84 in[i-8] -= in[i]; | |
85 in[i-5] += (in[i] & 0xffff) << 12; | |
86 in[i-4] += in[i] >> 16; | |
Wez
2011/11/02 23:46:06
nit: It would help laymen like me to have each of
agl
2011/11/03 17:20:49
Done.
| |
87 } | |
88 in[8] = 0; | |
89 // in[0..8] < 2**64 | |
90 | |
91 // As the values become small enough, we start to store them in |out| and use | |
92 // 32-bit operations. | |
93 for (int i = 1; i < 8; i++) { | |
94 in[i+1] += in[i] >> 28; | |
95 (*out)[i] = static_cast<uint32>(in[i] & kBottom28Bits); | |
96 } | |
97 in[0] -= in[8]; | |
98 (*out)[3] += static_cast<uint32>(in[8] & 0xffff) << 12; | |
99 (*out)[4] += static_cast<uint32>(in[8] >> 16); | |
Wez
2011/11/02 23:46:06
This looks like another mod p operation?
agl
2011/11/03 17:20:49
Done.
| |
100 // in[0] < 2**64 | |
101 // out[3] < 2**29 | |
102 // out[4] < 2**29 | |
103 // out[1,2,5..7] < 2**28 | |
104 | |
105 (*out)[0] = static_cast<uint32>(in[0] & kBottom28Bits); | |
106 (*out)[1] += static_cast<uint32>((in[0] >> 28) & kBottom28Bits); | |
107 (*out)[2] += static_cast<uint32>(in[0] >> 56); | |
108 // out[0] < 2**28 | |
109 // out[1..4] < 2**29 | |
110 // out[5..7] < 2**28 | |
111 } | |
112 | |
113 // Mul computes *out = a*b | |
114 // | |
115 // a[i] < 2**29, b[i] < 2**30 (or vice versa) | |
116 // out[i] < 2**29 | |
117 void Mul(FieldElement* out, const FieldElement& a, const FieldElement& b) { | |
118 LargeFieldElement tmp; | |
119 memset(&tmp, 0, sizeof(tmp)); | |
120 | |
121 for (int i = 0; i < 8; i++) { | |
122 for (int j = 0; j < 8; j++) { | |
123 tmp[i+j] += static_cast<uint64>(a[i]) * static_cast<uint64>(b[j]); | |
124 } | |
125 } | |
126 | |
127 ReduceLarge(out, tmp); | |
128 } | |
129 | |
130 // Square computes *out = a*a | |
131 // | |
132 // a[i] < 2**29 | |
133 // out[i] < 2**29 | |
134 void Square(FieldElement* out, const FieldElement& a) { | |
135 LargeFieldElement tmp; | |
136 memset(&tmp, 0, sizeof(tmp)); | |
137 | |
138 for (int i = 0; i < 8; i++) { | |
139 for (int j = 0; j <= i; j++) { | |
140 uint64 r = static_cast<uint64>(a[i]) * static_cast<uint64>(a[j]); | |
141 if (i == j) { | |
142 tmp[i+j] += r; | |
143 } else { | |
144 tmp[i+j] += r << 1; | |
145 } | |
146 } | |
147 } | |
148 | |
149 ReduceLarge(out, tmp); | |
150 } | |
151 | |
152 // Reduce reduces the coefficients of a to smaller bounds. | |
153 // | |
154 // On entry: a[i] < 2**31 + 2**30 | |
155 // On exit: a[i] < 2**29 | |
156 void Reduce(FieldElement* in) { | |
Wez
2011/11/02 23:46:06
Either rename in to in_out, or update the comment.
agl
2011/11/03 17:20:49
Done.
| |
157 FieldElement& a = *in; | |
158 | |
159 for (int i = 0; i < 7; i++) { | |
160 a[i+1] += a[i] >> 28; | |
161 a[i] &= kBottom28Bits; | |
162 } | |
163 uint32 top = a[7] >> 28; | |
164 a[7] &= kBottom28Bits; | |
165 | |
166 // top < 2**4 | |
167 uint32 mask = top; | |
168 mask |= mask >> 2; | |
169 mask |= mask >> 1; | |
170 mask <<= 31; | |
171 mask = static_cast<uint32>(static_cast<int32>(mask) >> 31); | |
172 // Mask is all ones if top != 0, all zero otherwise | |
Wez
2011/11/02 23:46:06
I think you're doing this to ensure constant-time
agl
2011/11/03 17:20:49
Done.
| |
173 | |
174 a[0] -= top; | |
175 a[3] += top << 12; | |
Wez
2011/11/02 23:46:06
This comes, again, as a result of folding things d
agl
2011/11/03 17:20:49
Yes. Commented.
| |
176 | |
177 // We may have just made a[0] negative but, if we did, then we must | |
178 // have added something to a[3], this it's > 2**12. Therefore we can | |
Wez
2011/11/02 23:46:06
typo: this -> thus?
agl
2011/11/03 17:20:49
Done.
| |
179 // carry down to a[0]. | |
180 a[3] -= 1 & mask; | |
181 a[2] += mask & ((1<<28) - 1); | |
182 a[1] += mask & ((1<<28) - 1); | |
183 a[0] += mask & (1<<28); | |
184 } | |
185 | |
186 // Invert calcuates *out = in^-1 using Fermat's little theorem. | |
Wez
2011/11/02 23:46:06
Suggest indicating as part of this comment that th
agl
2011/11/03 17:20:49
Done.
| |
187 void Invert(FieldElement* out, const FieldElement& in) { | |
188 FieldElement f1, f2, f3, f4; | |
189 | |
190 Square(&f1, in); // 2 | |
191 Mul(&f1, f1, in); // 2**2 - 1 | |
192 Square(&f1, f1); // 2**3 - 2 | |
193 Mul(&f1, f1, in); // 2**3 - 1 | |
194 Square(&f2, f1); // 2**4 - 2 | |
195 Square(&f2, f2); // 2**5 - 4 | |
196 Square(&f2, f2); // 2**6 - 8 | |
197 Mul(&f1, f1, f2); // 2**6 - 1 | |
198 Square(&f2, f1); // 2**7 - 2 | |
199 for (int i = 0; i < 5; i++) { // 2**12 - 2**6 | |
200 Square(&f2, f2); | |
Wez
2011/11/02 23:46:06
I like the exuberance of your indentation, but the
agl
2011/11/03 17:20:49
Done.
| |
201 } | |
202 Mul(&f2, f2, f1); // 2**12 - 1 | |
203 Square(&f3, f2); // 2**13 - 2 | |
204 for (int i = 0; i < 11; i++) { // 2**24 - 2**12 | |
205 Square(&f3, f3); | |
206 } | |
207 Mul(&f2, f3, f2); // 2**24 - 1 | |
208 Square(&f3, f2); // 2**25 - 2 | |
209 for (int i = 0; i < 23; i++) { // 2**48 - 2**24 | |
210 Square(&f3, f3); | |
211 } | |
212 Mul(&f3, f3, f2); // 2**48 - 1 | |
213 Square(&f4, f3); // 2**49 - 2 | |
214 for (int i = 0; i < 47; i++) { // 2**96 - 2**48 | |
215 Square(&f4, f4); | |
216 } | |
217 Mul(&f3, f3, f4); // 2**96 - 1 | |
218 Square(&f4, f3); // 2**97 - 2 | |
219 for (int i = 0; i < 23; i++) { // 2**120 - 2**24 | |
220 Square(&f4, f4); | |
221 } | |
222 Mul(&f2, f4, f2); // 2**120 - 1 | |
223 for (int i = 0; i < 6; i++) { // 2**126 - 2**6 | |
224 Square(&f2, f2); | |
225 } | |
226 Mul(&f1, f1, f2); // 2**126 - 1 | |
227 Square(&f1, f1); // 2**127 - 2 | |
228 Mul(&f1, f1, in); // 2**127 - 1 | |
229 for (int i = 0; i < 97; i++) { // 2**224 - 2**97 | |
230 Square(&f1, f1); | |
231 } | |
232 Mul(out, f1, f3); // 2**224 - 2**96 - 1 | |
233 } | |
234 | |
235 // Contract converts a FieldElement to its minimal, distinguished form. | |
236 // | |
237 // On entry, in[i] < 2**32 | |
238 // On exit, in[i] < 2**28 | |
239 void Contract(FieldElement* inout) { | |
240 FieldElement& out = *inout; | |
241 | |
242 for (int i = 0; i < 7; i++) { | |
Wez
2011/11/02 23:46:06
Again, a comment on this block indicating that we'
agl
2011/11/03 17:20:49
Done.
| |
243 out[i+1] += out[i] >> 28; | |
244 out[i] &= kBottom28Bits; | |
245 } | |
246 uint32 top = out[7] >> 28; | |
247 out[7] &= kBottom28Bits; | |
248 | |
249 out[0] -= top; | |
Wez
2011/11/02 23:46:06
... and a comment to indicate that we're then goin
agl
2011/11/03 17:20:49
Done.
| |
250 out[3] += top << 12; | |
251 | |
252 // We may just have made out[0] negative. So we carry down. If we made | |
253 // out[0] negative then we know that out[3] is sufficiently positive | |
254 // because we just added to it. | |
255 for (int i = 0; i < 3; i++) { | |
256 uint32 mask = static_cast<uint32>(static_cast<int32>(out[i]) >> 31); | |
257 out[i] += (1 << 28) & mask; | |
258 out[i+1] -= 1 & mask; | |
259 } | |
260 | |
261 // Now we see if the value is >= p and, if so, subtract p. | |
Wez
2011/11/02 23:46:06
For what purpose? Is the value in the range 0-2p,
agl
2011/11/03 17:20:49
Done.
| |
262 | |
263 // First we build a mask from the top four limbs, which must all be | |
264 // equal to bottom28Bits if the whole value is >= p. If top4AllOnes | |
265 // ends up with any zero bits in the bottom 28 bits, then this wasn't | |
266 // true. | |
267 uint32 top4AllOnes = 0xffffffffu; | |
268 for (int i = 4; i < 8; i++) { | |
269 top4AllOnes &= (out[i] & kBottom28Bits) - 1; | |
270 } | |
271 top4AllOnes |= 0xf0000000; | |
272 // Now we replicate any zero bits to all the bits in top4AllOnes. | |
273 top4AllOnes &= top4AllOnes >> 16; | |
274 top4AllOnes &= top4AllOnes >> 8; | |
275 top4AllOnes &= top4AllOnes >> 4; | |
276 top4AllOnes &= top4AllOnes >> 2; | |
277 top4AllOnes &= top4AllOnes >> 1; | |
278 top4AllOnes = | |
279 static_cast<uint32>(static_cast<int32>(top4AllOnes << 31) >> 31); | |
280 | |
281 // Now we test whether the bottom three limbs are non-zero. | |
282 uint32 bottom3NonZero = out[0] | out[1] | out[2]; | |
283 bottom3NonZero |= bottom3NonZero >> 16; | |
284 bottom3NonZero |= bottom3NonZero >> 8; | |
285 bottom3NonZero |= bottom3NonZero >> 4; | |
286 bottom3NonZero |= bottom3NonZero >> 2; | |
287 bottom3NonZero |= bottom3NonZero >> 1; | |
288 bottom3NonZero = | |
289 static_cast<uint32>(static_cast<int32>(bottom3NonZero << 31) >> 31); | |
290 | |
291 // Everything depends on the value of out[3]. | |
292 // If it's > 0xffff000 and top4AllOnes != 0 then the whole value is >= p | |
293 // If it's = 0xffff000 and top4AllOnes != 0 and bottom3NonZero != 0, | |
294 // then the whole value is >= p | |
295 // If it's < 0xffff000, then the whole value is < p | |
296 uint32 n = out[3] - 0xffff000; | |
297 uint32 out3Equal = n; | |
298 out3Equal |= out3Equal >> 16; | |
299 out3Equal |= out3Equal >> 8; | |
300 out3Equal |= out3Equal >> 4; | |
301 out3Equal |= out3Equal >> 2; | |
302 out3Equal |= out3Equal >> 1; | |
303 out3Equal = | |
304 ~static_cast<uint32>(static_cast<int32>(out3Equal << 31) >> 31); | |
305 | |
306 // If out[3] > 0xffff000 then n's MSB will be zero. | |
307 uint32 out3GT = ~static_cast<uint32>(static_cast<int32>(n << 31) >> 31); | |
308 | |
309 uint32 mask = top4AllOnes & ((out3Equal & bottom3NonZero) | out3GT); | |
310 out[0] -= 1 & mask; | |
311 out[3] -= 0xffff000 & mask; | |
312 out[4] -= 0xfffffff & mask; | |
313 out[5] -= 0xfffffff & mask; | |
314 out[6] -= 0xfffffff & mask; | |
315 out[7] -= 0xfffffff & mask; | |
316 } | |
317 | |
318 | |
319 // Group element functions. | |
320 // | |
321 // These functions deal with group elements. The group is an elliptic curve | |
322 // group with a = -3 defined in FIPS 186-3, section D.2.2. | |
323 | |
324 typedef crypto::P224::InternalPoint GroupElement; | |
325 | |
326 // kP is the P224 prime. | |
327 const FieldElement kP = { | |
328 1, 0, 0, 268431360, | |
329 268435455, 268435455, 268435455, 268435455, | |
330 }; | |
331 | |
332 // kB is parameter of the elliptic curve. | |
333 const FieldElement kB = { | |
334 55967668, 11768882, 265861671, 185302395, | |
335 39211076, 180311059, 84673715, 188764328, | |
336 }; | |
337 | |
338 // AddJacobian computes *out = a+b where a != b. | |
Wez
2011/11/02 23:46:06
nit: The body of this function may be easier to re
agl
2011/11/03 17:20:49
Done.
| |
339 void AddJacobian(GroupElement *out, | |
340 const GroupElement& a, | |
341 const GroupElement& b) { | |
342 // See http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#addition-a dd-2007-bl | |
343 FieldElement z1z1, z2z2, u1, u2, s1, s2, h, i, j, r, v; | |
344 | |
345 // Z1Z1 = Z1² | |
346 Square(&z1z1, a.z); | |
347 // Z2Z2 = Z2² | |
348 Square(&z2z2, b.z); | |
349 // U1 = X1*Z2Z2 | |
350 Mul(&u1, a.x, z2z2); | |
351 // U2 = X2*Z1Z1 | |
352 Mul(&u2, b.x, z1z1); | |
353 // S1 = Y1*Z2*Z2Z2 | |
354 Mul(&s1, b.z, z2z2); | |
355 Mul(&s1, a.y, s1); | |
356 // S2 = Y2*Z1*Z1Z1 | |
357 Mul(&s2, a.z, z1z1); | |
358 Mul(&s2, b.y, s2); | |
359 // H = U2-U1 | |
360 Sub(&h, u2, u1); | |
361 Reduce(&h); | |
362 // I = (2*H)² | |
363 for (int j = 0; j < 8; j++) { | |
364 i[j] = h[j] << 1; | |
365 } | |
366 Reduce(&i); | |
367 Square(&i, i); | |
368 // J = H*I | |
369 Mul(&j, h, i); | |
370 // r = 2*(S2-S1) | |
371 Sub(&r, s2, s1); | |
372 Reduce(&r); | |
373 for (int i = 0; i < 8; i++) { | |
374 r[i] <<= 1; | |
375 } | |
376 Reduce(&r); | |
377 // V = U1*I | |
378 Mul(&v, u1, i); | |
379 // Z3 = ((Z1+Z2)²-Z1Z1-Z2Z2)*H | |
380 Add(&z1z1, z1z1, z2z2); | |
381 Add(&z2z2, a.z, b.z); | |
382 Reduce(&z2z2); | |
383 Square(&z2z2, z2z2); | |
384 Sub(&out->z, z2z2, z1z1); | |
385 Reduce(&out->z); | |
386 Mul(&out->z, out->z, h); | |
387 // X3 = r²-J-2*V | |
388 for (int i = 0; i < 8; i++) { | |
389 z1z1[i] = v[i] << 1; | |
390 } | |
391 Add(&z1z1, j, z1z1); | |
392 Reduce(&z1z1); | |
393 Square(&out->x, r); | |
394 Sub(&out->x, out->x, z1z1); | |
395 Reduce(&out->x); | |
396 // Y3 = r*(V-X3)-2*S1*J | |
397 for (int i = 0; i < 8; i++) { | |
398 s1[i] <<= 1; | |
399 } | |
400 Mul(&s1, s1, j); | |
401 Sub(&z1z1, v, out->x); | |
402 Reduce(&z1z1); | |
403 Mul(&z1z1, z1z1, r); | |
404 Sub(&out->y, z1z1, s1); | |
405 Reduce(&out->y); | |
406 } | |
407 | |
408 // DoubleJacobian computes *out = a+a. | |
409 void DoubleJacobian(GroupElement* out, const GroupElement& a) { | |
410 // See http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-d bl-2001-b | |
411 FieldElement delta, gamma, beta, alpha, t; | |
412 | |
413 Square(&delta, a.z); | |
414 Square(&gamma, a.y); | |
415 Mul(&beta, a.x, gamma); | |
416 | |
417 // alpha = 3*(X1-delta)*(X1+delta) | |
418 Add(&t, a.x, delta); | |
419 for (int i = 0; i < 8; i++) { | |
420 t[i] += t[i] << 1; | |
421 } | |
422 Reduce(&t); | |
423 Sub(&alpha, a.x, delta); | |
424 Reduce(&alpha); | |
425 Mul(&alpha, alpha, t); | |
426 | |
427 // Z3 = (Y1+Z1)²-gamma-delta | |
428 Add(&out->z, a.y, a.z); | |
429 Reduce(&out->z); | |
430 Square(&out->z, out->z); | |
431 Sub(&out->z, out->z, gamma); | |
432 Reduce(&out->z); | |
433 Sub(&out->z, out->z, delta); | |
434 Reduce(&out->z); | |
435 | |
436 // X3 = alpha²-8*beta | |
437 for (int i = 0; i < 8; i++) { | |
438 delta[i] = beta[i] << 3; | |
439 } | |
440 Reduce(&delta); | |
441 Square(&out->x, alpha); | |
442 Sub(&out->x, out->x, delta); | |
443 Reduce(&out->x); | |
444 | |
445 // Y3 = alpha*(4*beta-X3)-8*gamma² | |
446 for (int i = 0; i < 8; i++) { | |
447 beta[i] <<= 2; | |
448 } | |
449 Reduce(&beta); | |
450 Sub(&beta, beta, out->x); | |
451 Reduce(&beta); | |
452 Square(&gamma, gamma); | |
453 for (int i = 0; i < 8; i++) { | |
454 gamma[i] <<= 3; | |
455 } | |
456 Reduce(&gamma); | |
457 Mul(&out->y, alpha, beta); | |
458 Sub(&out->y, out->y, gamma); | |
459 Reduce(&out->y); | |
460 } | |
461 | |
462 // CopyConditional sets *out=a if mask is 0xffffffff. mask must be either 0 of | |
463 // 0xffffffff. | |
464 void CopyConditional(GroupElement* out, | |
465 const GroupElement& a, | |
466 uint32 mask) { | |
467 for (int i = 0; i < 8; i++) { | |
468 out->x[i] ^= mask & (a.x[i] ^ out->x[i]); | |
469 out->y[i] ^= mask & (a.y[i] ^ out->y[i]); | |
470 out->z[i] ^= mask & (a.z[i] ^ out->z[i]); | |
471 } | |
472 } | |
473 | |
474 // ScalarMult calculates *out = a*scalar where scalar is a big-endian number of | |
475 // length scalar_len and != 0. | |
476 void ScalarMult(GroupElement* out, const GroupElement& a, | |
477 const uint8* scalar, size_t scalar_len) { | |
478 memset(out, 0, sizeof(*out)); | |
479 GroupElement tmp; | |
480 | |
481 uint32 first_bit = 0xffffffff; | |
482 for (size_t i = 0; i < scalar_len; i++) { | |
483 for (unsigned int bit_num = 0; bit_num < 8; bit_num++) { | |
484 DoubleJacobian(out, *out); | |
485 uint32 bit = static_cast<uint32>(static_cast<int32>( | |
486 (((scalar[i] >> (7 - bit_num)) & 1) << 31) >> 31)); | |
487 AddJacobian(&tmp, a, *out); | |
488 CopyConditional(out, a, first_bit & bit); | |
489 CopyConditional(out, tmp, ~first_bit & bit); | |
490 first_bit = first_bit & ~bit; | |
491 } | |
492 } | |
493 } | |
494 | |
495 // Get224Bits reads 7 words from in and scatters their contents in | |
496 // little-endian form into 8 words at out, 28 bits per output word. | |
497 void Get224Bits(uint32* out, const uint32* in) { | |
498 out[0] = ntohl(in[6]) & kBottom28Bits; | |
499 out[1] = ((ntohl(in[5]) << 4) | (ntohl(in[6]) >> 28)) & kBottom28Bits; | |
500 out[2] = ((ntohl(in[4]) << 8) | (ntohl(in[5]) >> 24)) & kBottom28Bits; | |
501 out[3] = ((ntohl(in[3]) << 12) | (ntohl(in[4]) >> 20)) & kBottom28Bits; | |
502 out[4] = ((ntohl(in[2]) << 16) | (ntohl(in[3]) >> 16)) & kBottom28Bits; | |
503 out[5] = ((ntohl(in[1]) << 20) | (ntohl(in[2]) >> 12)) & kBottom28Bits; | |
504 out[6] = ((ntohl(in[0]) << 24) | (ntohl(in[1]) >> 8)) & kBottom28Bits; | |
505 out[7] = (ntohl(in[0]) >> 4) & kBottom28Bits; | |
506 } | |
507 | |
508 // Put224Bits performs the inverse operation to Get224Bits: taking 28 bits from | |
509 // each of 8 input words and writing them in big-endian order to 7 words at | |
510 // out. | |
511 void Put224Bits(uint32* out, const uint32* in) { | |
512 out[6] = htonl((in[0] >> 0) | (in[1] << 28)); | |
513 out[5] = htonl((in[1] >> 4) | (in[2] << 24)); | |
514 out[4] = htonl((in[2] >> 8) | (in[3] << 20)); | |
515 out[3] = htonl((in[3] >> 12) | (in[4] << 16)); | |
516 out[2] = htonl((in[4] >> 16) | (in[5] << 12)); | |
517 out[1] = htonl((in[5] >> 20) | (in[6] << 8)); | |
518 out[0] = htonl((in[6] >> 24) | (in[7] << 4)); | |
519 } | |
520 | |
521 } // anonymous namespace | |
522 | |
523 namespace crypto { | |
524 | |
525 bool P224::ToInternal(const ExternalPoint& in, InternalPoint* out) { | |
526 const uint32* inwords = reinterpret_cast<const uint32*>(in.affine); | |
527 Get224Bits(out->x, inwords); | |
528 Get224Bits(out->y, inwords + 7); | |
529 memset(&out->z, 0, sizeof(out->z)); | |
530 out->z[0] = 1; | |
531 | |
532 // Check that the point is on the curve, i.e. that y² = x³ - 3x + b. | |
533 FieldElement lhs; | |
534 Square(&lhs, out->y); | |
535 Contract(&lhs); | |
536 | |
537 FieldElement rhs; | |
538 Square(&rhs, out->x); | |
539 Mul(&rhs, out->x, rhs); | |
540 | |
541 FieldElement three_x; | |
542 for (int i = 0; i < 8; i++) { | |
543 three_x[i] = out->x[i] * 3; | |
544 } | |
545 Reduce(&three_x); | |
546 Sub(&rhs, rhs, three_x); | |
547 Reduce(&rhs); | |
548 | |
549 ::Add(&rhs, rhs, kB); | |
550 Contract(&rhs); | |
551 return memcmp(&lhs, &rhs, sizeof(lhs)) == 0; | |
552 } | |
553 | |
554 void P224::ToExternal(const InternalPoint& in, ExternalPoint* out) { | |
555 FieldElement zinv, zinv_sq, x, y; | |
556 | |
557 Invert(&zinv, in.z); | |
558 Square(&zinv_sq, zinv); | |
559 Mul(&x, in.x, zinv_sq); | |
560 Mul(&zinv_sq, zinv_sq, zinv); | |
561 Mul(&y, in.y, zinv_sq); | |
562 | |
563 Contract(&x); | |
564 Contract(&y); | |
565 | |
566 uint32* outwords = reinterpret_cast<uint32*>(out->affine); | |
567 Put224Bits(outwords, x); | |
568 Put224Bits(outwords + 7, y); | |
569 } | |
570 | |
571 void P224::ScalarMult(const InternalPoint& in, | |
572 const uint8* scalar, | |
573 InternalPoint* out) { | |
574 ::ScalarMult(out, in, scalar, 28); | |
575 } | |
576 | |
577 static const P224::InternalPoint kBasePoint = { | |
578 {22813985, 52956513, 34677300, 203240812, | |
579 12143107, 133374265, 225162431, 191946955}, | |
580 {83918388, 223877528, 122119236, 123340192, | |
581 266784067, 263504429, 146143011, 198407736}, | |
582 {1, 0, 0, 0, 0, 0, 0, 0}, | |
583 }; | |
584 | |
585 void P224::ScalarBaseMult(const uint8* scalar, InternalPoint* out) { | |
586 ::ScalarMult(out, kBasePoint, scalar, 28); | |
587 } | |
588 | |
589 void P224::Add(const InternalPoint& a, const InternalPoint& b, | |
590 InternalPoint* out) { | |
591 AddJacobian(out, a, b); | |
592 } | |
593 | |
594 void P224::Negate(const InternalPoint& in, InternalPoint* out) { | |
595 // Guide to elliptic curve cryptography, page 89 suggests that (X : X+Y : Z) | |
596 // is the negative in Jacobian coordinates, but it doesn't actually appear to | |
597 // be true in testing so this performs the negation in affine coordinates. | |
598 FieldElement zinv, zinv_sq, y; | |
599 Invert(&zinv, in.z); | |
600 Square(&zinv_sq, zinv); | |
601 Mul(&out->x, in.x, zinv_sq); | |
602 Mul(&zinv_sq, zinv_sq, zinv); | |
603 Mul(&y, in.y, zinv_sq); | |
604 | |
605 Sub(&out->y, kP, y); | |
606 Reduce(&out->y); | |
607 | |
608 memset(&out->z, 0, sizeof(out->z)); | |
609 out->z[0] = 1; | |
610 } | |
611 | |
612 } // namespace crypto | |
OLD | NEW |