| 1 |
/* |
| 2 |
This file is for implementing the Gao-Mateer FFT, see |
| 3 |
http://www.math.clemson.edu/~sgao/papers/GM10.pdf |
| 4 |
|
| 5 |
For the implementation strategy, see |
| 6 |
https://eprint.iacr.org/2017/793.pdf |
| 7 |
*/ |
| 8 |
// 20240805 djb: more use of cryptoint |
| 9 |
// 20221230 djb: split these arrays into separate .c files |
| 10 |
// 20221230 djb: rename powers array as fft_powers |
| 11 |
// 20221230 djb: rename consts array as fft_consts |
| 12 |
// 20221230 djb: rename s array as fft_scalars_2x |
| 13 |
// 20221230 djb: add linker lines |
| 14 |
|
| 15 |
// linker define fft |
| 16 |
// linker use vec_mul |
| 17 |
// linker use fft_scalars_2x fft_consts fft_powers |
| 18 |
|
| 19 |
#include "fft.h" |
| 20 |
#include "fft_scalars_2x.h" |
| 21 |
#include "fft_consts.h" |
| 22 |
#include "fft_powers.h" |
| 23 |
|
| 24 |
#include "transpose.h" |
| 25 |
|
| 26 |
#include <stdint.h> |
| 27 |
#include "crypto_int64.h" |
| 28 |
|
| 29 |
/* input: in, polynomial in bitsliced form */ |
| 30 |
/* output: in, result of applying the radix conversions on in */ |
| 31 |
static void radix_conversions(vec in[][GFBITS]) |
| 32 |
{ |
| 33 |
int i, j, k; |
| 34 |
|
| 35 |
const vec mask[5][2] = |
| 36 |
{ |
| 37 |
{0x8888888888888888, 0x4444444444444444}, |
| 38 |
{0xC0C0C0C0C0C0C0C0, 0x3030303030303030}, |
| 39 |
{0xF000F000F000F000, 0x0F000F000F000F00}, |
| 40 |
{0xFF000000FF000000, 0x00FF000000FF0000}, |
| 41 |
{0xFFFF000000000000, 0x0000FFFF00000000} |
| 42 |
}; |
| 43 |
|
| 44 |
for (j = 0; j <= 5; j++) |
| 45 |
{ |
| 46 |
for (i = 0; i < GFBITS; i++) |
| 47 |
{ |
| 48 |
in[1][i] ^= in[1][i] >> 32; |
| 49 |
in[0][i] ^= in[1][i] << 32; |
| 50 |
} |
| 51 |
|
| 52 |
for (i = 0; i < GFBITS; i++) |
| 53 |
for (k = 4; k >= j; k--) |
| 54 |
{ |
| 55 |
in[0][i] ^= (in[0][i] & mask[k][0]) >> (1 << k); |
| 56 |
in[0][i] ^= (in[0][i] & mask[k][1]) >> (1 << k); |
| 57 |
in[1][i] ^= (in[1][i] & mask[k][0]) >> (1 << k); |
| 58 |
in[1][i] ^= (in[1][i] & mask[k][1]) >> (1 << k); |
| 59 |
} |
| 60 |
|
| 61 |
if (j < 5) |
| 62 |
{ |
| 63 |
vec_mul(in[0], in[0], fft_scalars_2x[j][0]); |
| 64 |
vec_mul(in[1], in[1], fft_scalars_2x[j][1]); |
| 65 |
} |
| 66 |
} |
| 67 |
} |
| 68 |
|
| 69 |
/* input: in, result of applying the radix conversions to the input polynomial */ |
| 70 |
/* output: out, evaluation results (by applying the FFT butterflies) */ |
| 71 |
static void butterflies(vec out[][ GFBITS ], vec in[][ GFBITS ]) |
| 72 |
{ |
| 73 |
int i, j, k, s, b; |
| 74 |
|
| 75 |
vec tmp[ GFBITS ]; |
| 76 |
vec pre[8][ GFBITS ]; |
| 77 |
vec buf[128]; |
| 78 |
|
| 79 |
uint64_t consts_ptr = 2; |
| 80 |
|
| 81 |
const unsigned char reversal[128] = |
| 82 |
{ |
| 83 |
0, 64, 32, 96, 16, 80, 48, 112, |
| 84 |
8, 72, 40, 104, 24, 88, 56, 120, |
| 85 |
4, 68, 36, 100, 20, 84, 52, 116, |
| 86 |
12, 76, 44, 108, 28, 92, 60, 124, |
| 87 |
2, 66, 34, 98, 18, 82, 50, 114, |
| 88 |
10, 74, 42, 106, 26, 90, 58, 122, |
| 89 |
6, 70, 38, 102, 22, 86, 54, 118, |
| 90 |
14, 78, 46, 110, 30, 94, 62, 126, |
| 91 |
1, 65, 33, 97, 17, 81, 49, 113, |
| 92 |
9, 73, 41, 105, 25, 89, 57, 121, |
| 93 |
5, 69, 37, 101, 21, 85, 53, 117, |
| 94 |
13, 77, 45, 109, 29, 93, 61, 125, |
| 95 |
3, 67, 35, 99, 19, 83, 51, 115, |
| 96 |
11, 75, 43, 107, 27, 91, 59, 123, |
| 97 |
7, 71, 39, 103, 23, 87, 55, 119, |
| 98 |
15, 79, 47, 111, 31, 95, 63, 127 |
| 99 |
}; |
| 100 |
|
| 101 |
const uint16_t beta[7] = {2522, 7827, 7801, 8035, 6897, 8167, 3476}; |
| 102 |
|
| 103 |
// |
| 104 |
|
| 105 |
for (i = 0; i < 7; i++) |
| 106 |
{ |
| 107 |
for (j = 0; j < GFBITS; j++) |
| 108 |
{ |
| 109 |
pre[i][j] = crypto_int64_bitmod_mask(beta[i], j); |
| 110 |
} |
| 111 |
|
| 112 |
vec_mul(pre[i], in[1], pre[i]); |
| 113 |
} |
| 114 |
|
| 115 |
for (i = 0; i < GFBITS; i++) |
| 116 |
{ |
| 117 |
buf[0] = in[0][i]; |
| 118 |
|
| 119 |
buf[1] = buf[0] ^ pre[0][i]; buf[32] = in[0][i] ^ pre[5][i]; |
| 120 |
buf[3] = buf[1] ^ pre[1][i]; buf[96] = buf[32] ^ pre[6][i]; |
| 121 |
buf[97] = buf[96] ^ pre[0][i]; |
| 122 |
buf[2] = in[0][i] ^ pre[1][i]; buf[99] = buf[97] ^ pre[1][i]; |
| 123 |
buf[6] = buf[2] ^ pre[2][i]; buf[98] = buf[99] ^ pre[0][i]; |
| 124 |
buf[7] = buf[6] ^ pre[0][i]; buf[102] = buf[98] ^ pre[2][i]; |
| 125 |
buf[5] = buf[7] ^ pre[1][i]; buf[103] = buf[102] ^ pre[0][i]; |
| 126 |
buf[101] = buf[103] ^ pre[1][i]; |
| 127 |
buf[4] = in[0][i] ^ pre[2][i]; buf[100] = buf[101] ^ pre[0][i]; |
| 128 |
buf[12] = buf[4] ^ pre[3][i]; buf[108] = buf[100] ^ pre[3][i]; |
| 129 |
buf[13] = buf[12] ^ pre[0][i]; buf[109] = buf[108] ^ pre[0][i]; |
| 130 |
buf[15] = buf[13] ^ pre[1][i]; buf[111] = buf[109] ^ pre[1][i]; |
| 131 |
buf[14] = buf[15] ^ pre[0][i]; buf[110] = buf[111] ^ pre[0][i]; |
| 132 |
buf[10] = buf[14] ^ pre[2][i]; buf[106] = buf[110] ^ pre[2][i]; |
| 133 |
buf[11] = buf[10] ^ pre[0][i]; buf[107] = buf[106] ^ pre[0][i]; |
| 134 |
buf[9] = buf[11] ^ pre[1][i]; buf[105] = buf[107] ^ pre[1][i]; |
| 135 |
buf[104] = buf[105] ^ pre[0][i]; |
| 136 |
buf[8] = in[0][i] ^ pre[3][i]; buf[120] = buf[104] ^ pre[4][i]; |
| 137 |
buf[24] = buf[8] ^ pre[4][i]; buf[121] = buf[120] ^ pre[0][i]; |
| 138 |
buf[25] = buf[24] ^ pre[0][i]; buf[123] = buf[121] ^ pre[1][i]; |
| 139 |
buf[27] = buf[25] ^ pre[1][i]; buf[122] = buf[123] ^ pre[0][i]; |
| 140 |
buf[26] = buf[27] ^ pre[0][i]; buf[126] = buf[122] ^ pre[2][i]; |
| 141 |
buf[30] = buf[26] ^ pre[2][i]; buf[127] = buf[126] ^ pre[0][i]; |
| 142 |
buf[31] = buf[30] ^ pre[0][i]; buf[125] = buf[127] ^ pre[1][i]; |
| 143 |
buf[29] = buf[31] ^ pre[1][i]; buf[124] = buf[125] ^ pre[0][i]; |
| 144 |
buf[28] = buf[29] ^ pre[0][i]; buf[116] = buf[124] ^ pre[3][i]; |
| 145 |
buf[20] = buf[28] ^ pre[3][i]; buf[117] = buf[116] ^ pre[0][i]; |
| 146 |
buf[21] = buf[20] ^ pre[0][i]; buf[119] = buf[117] ^ pre[1][i]; |
| 147 |
buf[23] = buf[21] ^ pre[1][i]; buf[118] = buf[119] ^ pre[0][i]; |
| 148 |
buf[22] = buf[23] ^ pre[0][i]; buf[114] = buf[118] ^ pre[2][i]; |
| 149 |
buf[18] = buf[22] ^ pre[2][i]; buf[115] = buf[114] ^ pre[0][i]; |
| 150 |
buf[19] = buf[18] ^ pre[0][i]; buf[113] = buf[115] ^ pre[1][i]; |
| 151 |
buf[17] = buf[19] ^ pre[1][i]; buf[112] = buf[113] ^ pre[0][i]; |
| 152 |
buf[80] = buf[112] ^ pre[5][i]; |
| 153 |
buf[16] = in[0][i] ^ pre[4][i]; buf[81] = buf[80] ^ pre[0][i]; |
| 154 |
buf[48] = buf[16] ^ pre[5][i]; buf[83] = buf[81] ^ pre[1][i]; |
| 155 |
buf[49] = buf[48] ^ pre[0][i]; buf[82] = buf[83] ^ pre[0][i]; |
| 156 |
buf[51] = buf[49] ^ pre[1][i]; buf[86] = buf[82] ^ pre[2][i]; |
| 157 |
buf[50] = buf[51] ^ pre[0][i]; buf[87] = buf[86] ^ pre[0][i]; |
| 158 |
buf[54] = buf[50] ^ pre[2][i]; buf[85] = buf[87] ^ pre[1][i]; |
| 159 |
buf[55] = buf[54] ^ pre[0][i]; buf[84] = buf[85] ^ pre[0][i]; |
| 160 |
buf[53] = buf[55] ^ pre[1][i]; buf[92] = buf[84] ^ pre[3][i]; |
| 161 |
buf[52] = buf[53] ^ pre[0][i]; buf[93] = buf[92] ^ pre[0][i]; |
| 162 |
buf[60] = buf[52] ^ pre[3][i]; buf[95] = buf[93] ^ pre[1][i]; |
| 163 |
buf[61] = buf[60] ^ pre[0][i]; buf[94] = buf[95] ^ pre[0][i]; |
| 164 |
buf[63] = buf[61] ^ pre[1][i]; buf[90] = buf[94] ^ pre[2][i]; |
| 165 |
buf[62] = buf[63] ^ pre[0][i]; buf[91] = buf[90] ^ pre[0][i]; |
| 166 |
buf[58] = buf[62] ^ pre[2][i]; buf[89] = buf[91] ^ pre[1][i]; |
| 167 |
buf[59] = buf[58] ^ pre[0][i]; buf[88] = buf[89] ^ pre[0][i]; |
| 168 |
buf[57] = buf[59] ^ pre[1][i]; buf[72] = buf[88] ^ pre[4][i]; |
| 169 |
buf[56] = buf[57] ^ pre[0][i]; buf[73] = buf[72] ^ pre[0][i]; |
| 170 |
buf[40] = buf[56] ^ pre[4][i]; buf[75] = buf[73] ^ pre[1][i]; |
| 171 |
buf[41] = buf[40] ^ pre[0][i]; buf[74] = buf[75] ^ pre[0][i]; |
| 172 |
buf[43] = buf[41] ^ pre[1][i]; buf[78] = buf[74] ^ pre[2][i]; |
| 173 |
buf[42] = buf[43] ^ pre[0][i]; buf[79] = buf[78] ^ pre[0][i]; |
| 174 |
buf[46] = buf[42] ^ pre[2][i]; buf[77] = buf[79] ^ pre[1][i]; |
| 175 |
buf[47] = buf[46] ^ pre[0][i]; buf[76] = buf[77] ^ pre[0][i]; |
| 176 |
buf[45] = buf[47] ^ pre[1][i]; buf[68] = buf[76] ^ pre[3][i]; |
| 177 |
buf[44] = buf[45] ^ pre[0][i]; buf[69] = buf[68] ^ pre[0][i]; |
| 178 |
buf[36] = buf[44] ^ pre[3][i]; buf[71] = buf[69] ^ pre[1][i]; |
| 179 |
buf[37] = buf[36] ^ pre[0][i]; buf[70] = buf[71] ^ pre[0][i]; |
| 180 |
buf[39] = buf[37] ^ pre[1][i]; buf[66] = buf[70] ^ pre[2][i]; |
| 181 |
buf[38] = buf[39] ^ pre[0][i]; buf[67] = buf[66] ^ pre[0][i]; |
| 182 |
buf[34] = buf[38] ^ pre[2][i]; buf[65] = buf[67] ^ pre[1][i]; |
| 183 |
buf[35] = buf[34] ^ pre[0][i]; |
| 184 |
buf[33] = buf[35] ^ pre[1][i]; buf[64] = in[0][i] ^ pre[6][i]; |
| 185 |
|
| 186 |
transpose_64x64(buf + 0, buf + 0); |
| 187 |
transpose_64x64(buf + 64, buf + 64); |
| 188 |
|
| 189 |
for (j = 0; j < 128; j++) |
| 190 |
out[ reversal[j] ][i] = buf[j]; |
| 191 |
} |
| 192 |
|
| 193 |
for (i = 1; i <= 6; i++) |
| 194 |
{ |
| 195 |
s = 1 << i; |
| 196 |
|
| 197 |
for (j = 0; j < 128; j += 2*s) |
| 198 |
for (k = j; k < j+s; k++) |
| 199 |
{ |
| 200 |
vec_mul(tmp, out[k+s], fft_consts[ consts_ptr + (k-j) ]); |
| 201 |
|
| 202 |
for (b = 0; b < GFBITS; b++) out[k ][b] ^= tmp[b]; |
| 203 |
for (b = 0; b < GFBITS; b++) out[k+s][b] ^= out[k][b]; |
| 204 |
} |
| 205 |
|
| 206 |
consts_ptr += (1 << i); |
| 207 |
} |
| 208 |
|
| 209 |
// adding the part contributed by x^128 |
| 210 |
|
| 211 |
for (i = 0; i < 128; i++) |
| 212 |
for (b = 0; b < GFBITS; b++) |
| 213 |
out[i][b] ^= fft_powers[i][b]; |
| 214 |
} |
| 215 |
|
| 216 |
/* input: in, polynomial in bitsliced form */ |
| 217 |
/* output: out, bitsliced results of evaluating in all the field elements */ |
| 218 |
void fft(vec out[][GFBITS], vec in[][GFBITS]) |
| 219 |
{ |
| 220 |
radix_conversions(in); |
| 221 |
butterflies(out, in); |
| 222 |
} |