ed25519-donna-batchverify.h (7651B)
1 /* 2 Ed25519 batch verification 3 */ 4 5 #define max_batch_size 64 6 #define heap_batch_size ((max_batch_size * 2) + 1) 7 8 /* which limb is the 128th bit in? */ 9 static const size_t limb128bits = (128 + bignum256modm_bits_per_limb - 1) / bignum256modm_bits_per_limb; 10 11 typedef size_t heap_index_t; 12 13 typedef struct batch_heap_t { 14 unsigned char r[heap_batch_size][16]; /* 128 bit random values */ 15 ge25519 points[heap_batch_size]; 16 bignum256modm scalars[heap_batch_size]; 17 heap_index_t heap[heap_batch_size]; 18 size_t size; 19 } batch_heap; 20 21 /* swap two values in the heap */ 22 static void 23 heap_swap(heap_index_t *heap, size_t a, size_t b) { 24 heap_index_t temp; 25 temp = heap[a]; 26 heap[a] = heap[b]; 27 heap[b] = temp; 28 } 29 30 /* add the scalar at the end of the list to the heap */ 31 static void 32 heap_insert_next(batch_heap *heap) { 33 size_t node = heap->size, parent; 34 heap_index_t *pheap = heap->heap; 35 bignum256modm *scalars = heap->scalars; 36 37 /* insert at the bottom */ 38 pheap[node] = (heap_index_t)node; 39 40 /* sift node up to its sorted spot */ 41 parent = (node - 1) / 2; 42 while (node && lt256_modm_batch(scalars[pheap[parent]], scalars[pheap[node]], bignum256modm_limb_size - 1)) { 43 heap_swap(pheap, parent, node); 44 node = parent; 45 parent = (node - 1) / 2; 46 } 47 heap->size++; 48 } 49 50 /* update the heap when the root element is updated */ 51 static void 52 heap_updated_root(batch_heap *heap, size_t limbsize) { 53 size_t node, parent, childr, childl; 54 heap_index_t *pheap = heap->heap; 55 bignum256modm *scalars = heap->scalars; 56 57 /* sift root to the bottom */ 58 parent = 0; 59 node = 1; 60 childl = 1; 61 childr = 2; 62 while ((childr < heap->size)) { 63 node = lt256_modm_batch(scalars[pheap[childl]], scalars[pheap[childr]], limbsize) ? childr : childl; 64 heap_swap(pheap, parent, node); 65 parent = node; 66 childl = (parent * 2) + 1; 67 childr = childl + 1; 68 } 69 70 /* sift root back up to its sorted spot */ 71 parent = (node - 1) / 2; 72 while (node && lte256_modm_batch(scalars[pheap[parent]], scalars[pheap[node]], limbsize)) { 73 heap_swap(pheap, parent, node); 74 node = parent; 75 parent = (node - 1) / 2; 76 } 77 } 78 79 /* build the heap with count elements, count must be >= 3 */ 80 static void 81 heap_build(batch_heap *heap, size_t count) { 82 heap->heap[0] = 0; 83 heap->size = 0; 84 while (heap->size < count) 85 heap_insert_next(heap); 86 } 87 88 /* extend the heap to contain new_count elements */ 89 static void 90 heap_extend(batch_heap *heap, size_t new_count) { 91 while (heap->size < new_count) 92 heap_insert_next(heap); 93 } 94 95 /* get the top 2 elements of the heap */ 96 static void 97 heap_get_top2(batch_heap *heap, heap_index_t *max1, heap_index_t *max2, size_t limbsize) { 98 heap_index_t h0 = heap->heap[0], h1 = heap->heap[1], h2 = heap->heap[2]; 99 if (lt256_modm_batch(heap->scalars[h1], heap->scalars[h2], limbsize)) 100 h1 = h2; 101 *max1 = h0; 102 *max2 = h1; 103 } 104 105 /* */ 106 static void 107 ge25519_multi_scalarmult_vartime_final(ge25519 *r, ge25519 *point, bignum256modm scalar) { 108 const bignum256modm_element_t topbit = ((bignum256modm_element_t)1 << (bignum256modm_bits_per_limb - 1)); 109 size_t limb = limb128bits; 110 bignum256modm_element_t flag; 111 112 if (isone256_modm_batch(scalar)) { 113 /* this will happen most of the time after bos-carter */ 114 *r = *point; 115 return; 116 } else if (iszero256_modm_batch(scalar)) { 117 /* this will only happen if all scalars == 0 */ 118 memset(r, 0, sizeof(*r)); 119 r->y[0] = 1; 120 r->z[0] = 1; 121 return; 122 } 123 124 *r = *point; 125 126 /* find the limb where first bit is set */ 127 while (!scalar[limb]) 128 limb--; 129 130 /* find the first bit */ 131 flag = topbit; 132 while ((scalar[limb] & flag) == 0) 133 flag >>= 1; 134 135 /* exponentiate */ 136 for (;;) { 137 ge25519_double(r, r); 138 if (scalar[limb] & flag) 139 ge25519_add(r, r, point); 140 141 flag >>= 1; 142 if (!flag) { 143 if (!limb--) 144 break; 145 flag = topbit; 146 } 147 } 148 } 149 150 /* count must be >= 5 */ 151 static void 152 ge25519_multi_scalarmult_vartime(ge25519 *r, batch_heap *heap, size_t count) { 153 heap_index_t max1, max2; 154 155 /* start with the full limb size */ 156 size_t limbsize = bignum256modm_limb_size - 1; 157 158 /* whether the heap has been extended to include the 128 bit scalars */ 159 int extended = 0; 160 161 /* grab an odd number of scalars to build the heap, unknown limb sizes */ 162 heap_build(heap, ((count + 1) / 2) | 1); 163 164 for (;;) { 165 heap_get_top2(heap, &max1, &max2, limbsize); 166 167 /* only one scalar remaining, we're done */ 168 if (iszero256_modm_batch(heap->scalars[max2])) 169 break; 170 171 /* exhausted another limb? */ 172 if (!heap->scalars[max1][limbsize]) 173 limbsize -= 1; 174 175 /* can we extend to the 128 bit scalars? */ 176 if (!extended && isatmost128bits256_modm_batch(heap->scalars[max1])) { 177 heap_extend(heap, count); 178 heap_get_top2(heap, &max1, &max2, limbsize); 179 extended = 1; 180 } 181 182 sub256_modm_batch(heap->scalars[max1], heap->scalars[max1], heap->scalars[max2], limbsize); 183 ge25519_add(&heap->points[max2], &heap->points[max2], &heap->points[max1]); 184 heap_updated_root(heap, limbsize); 185 } 186 187 ge25519_multi_scalarmult_vartime_final(r, &heap->points[max1], heap->scalars[max1]); 188 } 189 190 /* not actually used for anything other than testing */ 191 static unsigned char batch_point_buffer[3][32]; 192 193 static int 194 ge25519_is_neutral_vartime(const ge25519 *p) { 195 static const unsigned char zero[32] = {0}; 196 unsigned char point_buffer[3][32]; 197 curve25519_contract(point_buffer[0], p->x); 198 curve25519_contract(point_buffer[1], p->y); 199 curve25519_contract(point_buffer[2], p->z); 200 memcpy(batch_point_buffer[1], point_buffer[1], 32); 201 return (memcmp(point_buffer[0], zero, 32) == 0) && (memcmp(point_buffer[1], point_buffer[2], 32) == 0); 202 } 203 204 int 205 ED25519_FN(ed25519_sign_open_batch) (const unsigned char **m, size_t *mlen, const unsigned char **pk, const unsigned char **RS, size_t num, int *valid) { 206 batch_heap ALIGN(16) batch; 207 ge25519 ALIGN(16) p; 208 bignum256modm *r_scalars; 209 size_t i, batchsize; 210 unsigned char hram[64]; 211 int ret = 0; 212 213 for (i = 0; i < num; i++) 214 valid[i] = 1; 215 216 while (num > 3) { 217 batchsize = (num > max_batch_size) ? max_batch_size : num; 218 219 /* generate r (scalars[batchsize+1]..scalars[2*batchsize] */ 220 ED25519_FN(ed25519_randombytes_unsafe) (batch.r, batchsize * 16); 221 r_scalars = &batch.scalars[batchsize + 1]; 222 for (i = 0; i < batchsize; i++) 223 expand256_modm(r_scalars[i], batch.r[i], 16); 224 225 /* compute scalars[0] = ((r1s1 + r2s2 + ...)) */ 226 for (i = 0; i < batchsize; i++) { 227 expand256_modm(batch.scalars[i], RS[i] + 32, 32); 228 mul256_modm(batch.scalars[i], batch.scalars[i], r_scalars[i]); 229 } 230 for (i = 1; i < batchsize; i++) 231 add256_modm(batch.scalars[0], batch.scalars[0], batch.scalars[i]); 232 233 /* compute scalars[1]..scalars[batchsize] as r[i]*H(R[i],A[i],m[i]) */ 234 for (i = 0; i < batchsize; i++) { 235 ed25519_hram(hram, RS[i], pk[i], m[i], mlen[i]); 236 expand256_modm(batch.scalars[i+1], hram, 64); 237 mul256_modm(batch.scalars[i+1], batch.scalars[i+1], r_scalars[i]); 238 } 239 240 /* compute points */ 241 batch.points[0] = ge25519_basepoint; 242 for (i = 0; i < batchsize; i++) 243 if (!ge25519_unpack_negative_vartime(&batch.points[i+1], pk[i])) 244 goto fallback; 245 for (i = 0; i < batchsize; i++) 246 if (!ge25519_unpack_negative_vartime(&batch.points[batchsize+i+1], RS[i])) 247 goto fallback; 248 249 ge25519_multi_scalarmult_vartime(&p, &batch, (batchsize * 2) + 1); 250 if (!ge25519_is_neutral_vartime(&p)) { 251 ret |= 2; 252 253 fallback: 254 for (i = 0; i < batchsize; i++) { 255 valid[i] = ED25519_FN(ed25519_sign_open) (m[i], mlen[i], pk[i], RS[i]) ? 0 : 1; 256 ret |= (valid[i] ^ 1); 257 } 258 } 259 260 m += batchsize; 261 mlen += batchsize; 262 pk += batchsize; 263 RS += batchsize; 264 num -= batchsize; 265 valid += batchsize; 266 } 267 268 for (i = 0; i < num; i++) { 269 valid[i] = ED25519_FN(ed25519_sign_open) (m[i], mlen[i], pk[i], RS[i]) ? 0 : 1; 270 ret |= (valid[i] ^ 1); 271 } 272 273 return ret; 274 }