Debian Codegraph @

external/boringssl/crypto/curve25519/x25519-x86_64.c

raw
1 /* Copyright (c) 2015, Google Inc.
2 *
3 * Permission to use, copy, modify, and/or distribute this software for any
4 * purpose with or without fee is hereby granted, provided that the above
5 * copyright notice and this permission notice appear in all copies.
6 *
7 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
8 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
9 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
10 * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
11 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
12 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
13 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */
14
15 /* This code is mostly taken from the ref10 version of Ed25519 in SUPERCOP
16 * 20141124 (http://bench.cr.yp.to/supercop.html). That code is released as
17 * public domain but this file has the ISC license just to keep licencing
18 * simple.
19 *
20 * The field functions are shared by Ed25519 and X25519 where possible. */
21
22 #include <openssl/curve25519.h>
23
24 #include <string.h>
25
26 #include "internal.h"
27
28
29 #if defined(BORINGSSL_X25519_X86_64)
30
31 typedef struct { uint64_t v[5]; } fe25519;
32
33 /* These functions are defined in asm/x25519-x86_64.S */
34 void x25519_x86_64_work_cswap(fe25519 *, uint64_t);
35 void x25519_x86_64_mul(fe25519 *out, const fe25519 *a, const fe25519 *b);
36 void x25519_x86_64_square(fe25519 *out, const fe25519 *a);
37 void x25519_x86_64_freeze(fe25519 *);
38 void x25519_x86_64_ladderstep(fe25519 *work);
39
40 static void fe25519_setint(fe25519 *r, unsigned v) {
41 r->v[0] = v;
42 r->v[1] = 0;
43 r->v[2] = 0;
44 r->v[3] = 0;
45 r->v[4] = 0;
46 }
47
48 /* Assumes input x being reduced below 2^255 */
49 static void fe25519_pack(unsigned char r[32], const fe25519 *x) {
50 fe25519 t;
51 t = *x;
52 x25519_x86_64_freeze(&t);
53
54 r[0] = (uint8_t)(t.v[0] & 0xff);
55 r[1] = (uint8_t)((t.v[0] >> 8) & 0xff);
56 r[2] = (uint8_t)((t.v[0] >> 16) & 0xff);
57 r[3] = (uint8_t)((t.v[0] >> 24) & 0xff);
58 r[4] = (uint8_t)((t.v[0] >> 32) & 0xff);
59 r[5] = (uint8_t)((t.v[0] >> 40) & 0xff);
60 r[6] = (uint8_t)((t.v[0] >> 48));
61
62 r[6] ^= (uint8_t)((t.v[1] << 3) & 0xf8);
63 r[7] = (uint8_t)((t.v[1] >> 5) & 0xff);
64 r[8] = (uint8_t)((t.v[1] >> 13) & 0xff);
65 r[9] = (uint8_t)((t.v[1] >> 21) & 0xff);
66 r[10] = (uint8_t)((t.v[1] >> 29) & 0xff);
67 r[11] = (uint8_t)((t.v[1] >> 37) & 0xff);
68 r[12] = (uint8_t)((t.v[1] >> 45));
69
70 r[12] ^= (uint8_t)((t.v[2] << 6) & 0xc0);
71 r[13] = (uint8_t)((t.v[2] >> 2) & 0xff);
72 r[14] = (uint8_t)((t.v[2] >> 10) & 0xff);
73 r[15] = (uint8_t)((t.v[2] >> 18) & 0xff);
74 r[16] = (uint8_t)((t.v[2] >> 26) & 0xff);
75 r[17] = (uint8_t)((t.v[2] >> 34) & 0xff);
76 r[18] = (uint8_t)((t.v[2] >> 42) & 0xff);
77 r[19] = (uint8_t)((t.v[2] >> 50));
78
79 r[19] ^= (uint8_t)((t.v[3] << 1) & 0xfe);
80 r[20] = (uint8_t)((t.v[3] >> 7) & 0xff);
81 r[21] = (uint8_t)((t.v[3] >> 15) & 0xff);
82 r[22] = (uint8_t)((t.v[3] >> 23) & 0xff);
83 r[23] = (uint8_t)((t.v[3] >> 31) & 0xff);
84 r[24] = (uint8_t)((t.v[3] >> 39) & 0xff);
85 r[25] = (uint8_t)((t.v[3] >> 47));
86
87 r[25] ^= (uint8_t)((t.v[4] << 4) & 0xf0);
88 r[26] = (uint8_t)((t.v[4] >> 4) & 0xff);
89 r[27] = (uint8_t)((t.v[4] >> 12) & 0xff);
90 r[28] = (uint8_t)((t.v[4] >> 20) & 0xff);
91 r[29] = (uint8_t)((t.v[4] >> 28) & 0xff);
92 r[30] = (uint8_t)((t.v[4] >> 36) & 0xff);
93 r[31] = (uint8_t)((t.v[4] >> 44));
94 }
95
96 static void fe25519_unpack(fe25519 *r, const uint8_t x[32]) {
97 r->v[0] = x[0];
98 r->v[0] += (uint64_t)x[1] << 8;
99 r->v[0] += (uint64_t)x[2] << 16;
100 r->v[0] += (uint64_t)x[3] << 24;
101 r->v[0] += (uint64_t)x[4] << 32;
102 r->v[0] += (uint64_t)x[5] << 40;
103 r->v[0] += ((uint64_t)x[6] & 7) << 48;
104
105 r->v[1] = x[6] >> 3;
106 r->v[1] += (uint64_t)x[7] << 5;
107 r->v[1] += (uint64_t)x[8] << 13;
108 r->v[1] += (uint64_t)x[9] << 21;
109 r->v[1] += (uint64_t)x[10] << 29;
110 r->v[1] += (uint64_t)x[11] << 37;
111 r->v[1] += ((uint64_t)x[12] & 63) << 45;
112
113 r->v[2] = x[12] >> 6;
114 r->v[2] += (uint64_t)x[13] << 2;
115 r->v[2] += (uint64_t)x[14] << 10;
116 r->v[2] += (uint64_t)x[15] << 18;
117 r->v[2] += (uint64_t)x[16] << 26;
118 r->v[2] += (uint64_t)x[17] << 34;
119 r->v[2] += (uint64_t)x[18] << 42;
120 r->v[2] += ((uint64_t)x[19] & 1) << 50;
121
122 r->v[3] = x[19] >> 1;
123 r->v[3] += (uint64_t)x[20] << 7;
124 r->v[3] += (uint64_t)x[21] << 15;
125 r->v[3] += (uint64_t)x[22] << 23;
126 r->v[3] += (uint64_t)x[23] << 31;
127 r->v[3] += (uint64_t)x[24] << 39;
128 r->v[3] += ((uint64_t)x[25] & 15) << 47;
129
130 r->v[4] = x[25] >> 4;
131 r->v[4] += (uint64_t)x[26] << 4;
132 r->v[4] += (uint64_t)x[27] << 12;
133 r->v[4] += (uint64_t)x[28] << 20;
134 r->v[4] += (uint64_t)x[29] << 28;
135 r->v[4] += (uint64_t)x[30] << 36;
136 r->v[4] += ((uint64_t)x[31] & 127) << 44;
137 }
138
139 static void fe25519_invert(fe25519 *r, const fe25519 *x) {
140 fe25519 z2;
141 fe25519 z9;
142 fe25519 z11;
143 fe25519 z2_5_0;
144 fe25519 z2_10_0;
145 fe25519 z2_20_0;
146 fe25519 z2_50_0;
147 fe25519 z2_100_0;
148 fe25519 t;
149 int i;
150
151 /* 2 */ x25519_x86_64_square(&z2, x);
152 /* 4 */ x25519_x86_64_square(&t, &z2);
153 /* 8 */ x25519_x86_64_square(&t, &t);
154 /* 9 */ x25519_x86_64_mul(&z9, &t, x);
155 /* 11 */ x25519_x86_64_mul(&z11, &z9, &z2);
156 /* 22 */ x25519_x86_64_square(&t, &z11);
157 /* 2^5 - 2^0 = 31 */ x25519_x86_64_mul(&z2_5_0, &t, &z9);
158
159 /* 2^6 - 2^1 */ x25519_x86_64_square(&t, &z2_5_0);
160 /* 2^20 - 2^10 */ for (i = 1; i < 5; i++) { x25519_x86_64_square(&t, &t); }
161 /* 2^10 - 2^0 */ x25519_x86_64_mul(&z2_10_0, &t, &z2_5_0);
162
163 /* 2^11 - 2^1 */ x25519_x86_64_square(&t, &z2_10_0);
164 /* 2^20 - 2^10 */ for (i = 1; i < 10; i++) { x25519_x86_64_square(&t, &t); }
165 /* 2^20 - 2^0 */ x25519_x86_64_mul(&z2_20_0, &t, &z2_10_0);
166
167 /* 2^21 - 2^1 */ x25519_x86_64_square(&t, &z2_20_0);
168 /* 2^40 - 2^20 */ for (i = 1; i < 20; i++) { x25519_x86_64_square(&t, &t); }
169 /* 2^40 - 2^0 */ x25519_x86_64_mul(&t, &t, &z2_20_0);
170
171 /* 2^41 - 2^1 */ x25519_x86_64_square(&t, &t);
172 /* 2^50 - 2^10 */ for (i = 1; i < 10; i++) { x25519_x86_64_square(&t, &t); }
173 /* 2^50 - 2^0 */ x25519_x86_64_mul(&z2_50_0, &t, &z2_10_0);
174
175 /* 2^51 - 2^1 */ x25519_x86_64_square(&t, &z2_50_0);
176 /* 2^100 - 2^50 */ for (i = 1; i < 50; i++) { x25519_x86_64_square(&t, &t); }
177 /* 2^100 - 2^0 */ x25519_x86_64_mul(&z2_100_0, &t, &z2_50_0);
178
179 /* 2^101 - 2^1 */ x25519_x86_64_square(&t, &z2_100_0);
180 /* 2^200 - 2^100 */ for (i = 1; i < 100; i++) {
181 x25519_x86_64_square(&t, &t);
182 }
183 /* 2^200 - 2^0 */ x25519_x86_64_mul(&t, &t, &z2_100_0);
184
185 /* 2^201 - 2^1 */ x25519_x86_64_square(&t, &t);
186 /* 2^250 - 2^50 */ for (i = 1; i < 50; i++) { x25519_x86_64_square(&t, &t); }
187 /* 2^250 - 2^0 */ x25519_x86_64_mul(&t, &t, &z2_50_0);
188
189 /* 2^251 - 2^1 */ x25519_x86_64_square(&t, &t);
190 /* 2^252 - 2^2 */ x25519_x86_64_square(&t, &t);
191 /* 2^253 - 2^3 */ x25519_x86_64_square(&t, &t);
192
193 /* 2^254 - 2^4 */ x25519_x86_64_square(&t, &t);
194
195 /* 2^255 - 2^5 */ x25519_x86_64_square(&t, &t);
196 /* 2^255 - 21 */ x25519_x86_64_mul(r, &t, &z11);
197 }
198
199 static void mladder(fe25519 *xr, fe25519 *zr, const uint8_t s[32]) {
200 fe25519 work[5];
201
202 work[0] = *xr;
203 fe25519_setint(work + 1, 1);
204 fe25519_setint(work + 2, 0);
205 work[3] = *xr;
206 fe25519_setint(work + 4, 1);
207
208 int i, j;
209 uint8_t prevbit = 0;
210
211 j = 6;
212 for (i = 31; i >= 0; i--) {
213 while (j >= 0) {
214 const uint8_t bit = 1 & (s[i] >> j);
215 const uint64_t swap = bit ^ prevbit;
216 prevbit = bit;
217 x25519_x86_64_work_cswap(work + 1, swap);
218 x25519_x86_64_ladderstep(work);
219 j -= 1;
220 }
221 j = 7;
222 }
223
224 *xr = work[1];
225 *zr = work[2];
226 }
227
228 void x25519_x86_64(uint8_t out[32], const uint8_t scalar[32],
229 const uint8_t point[32]) {
230 uint8_t e[32];
231 memcpy(e, scalar, sizeof(e));
232
233 e[0] &= 248;
234 e[31] &= 127;
235 e[31] |= 64;
236
237 fe25519 t;
238 fe25519 z;
239 fe25519_unpack(&t, point);
240 mladder(&t, &z, e);
241 fe25519_invert(&z, &z);
242 x25519_x86_64_mul(&t, &t, &z);
243 fe25519_pack(out, &t);
244 }
245
246 #endif /* BORINGSSL_X25519_X86_64 */