5 #define max_batch_size 64 6 #define heap_batch_size ((max_batch_size * 2) + 1) 33 size_t node = heap->
size, parent;
41 parent = (node - 1) / 2;
43 heap_swap(pheap, parent, node);
45 parent = (node - 1) / 2;
52 heap_updated_root(
batch_heap *heap,
size_t limbsize) {
53 size_t node, parent, childr, childl;
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);
66 childl = (parent * 2) + 1;
71 parent = (node - 1) / 2;
72 while (node && lte256_modm_batch(scalars[pheap[parent]], scalars[pheap[node]], limbsize)) {
73 heap_swap(pheap, parent, node);
75 parent = (node - 1) / 2;
85 heap_insert_next(heap);
90 heap_extend(
batch_heap *heap,
size_t new_count) {
91 while (heap->
size < new_count)
92 heap_insert_next(heap);
99 if (lt256_modm_batch(heap->
scalars[h1], heap->
scalars[h2], limbsize))
109 size_t limb = limb128bits;
112 if (isone256_modm_batch(scalar)) {
116 }
else if (iszero256_modm_batch(scalar)) {
118 memset(r, 0,
sizeof(*r));
127 while (!scalar[limb])
132 while ((scalar[limb] & flag) == 0)
137 ge25519_double(r, r);
138 if (scalar[limb] & flag)
139 ge25519_add(r, r, point);
162 heap_build(heap, ((
count + 1) / 2) | 1);
165 heap_get_top2(heap, &max1, &max2, limbsize);
168 if (iszero256_modm_batch(heap->
scalars[max2]))
172 if (!heap->
scalars[max1][limbsize])
176 if (!extended && isatmost128bits256_modm_batch(heap->
scalars[max1])) {
177 heap_extend(heap,
count);
178 heap_get_top2(heap, &max1, &max2, limbsize);
184 heap_updated_root(heap, limbsize);
187 ge25519_multi_scalarmult_vartime_final(r, &heap->
points[max1], heap->
scalars[max1]);
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);
201 return (memcmp(point_buffer[0],
zero, 32) == 0) && (memcmp(point_buffer[1], point_buffer[2], 32) == 0);
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) {
210 unsigned char hram[64];
213 for (i = 0; i < num; i++)
221 r_scalars = &batch.
scalars[batchsize + 1];
222 for (i = 0; i < batchsize; i++)
223 expand256_modm(r_scalars[i], batch.
r[i], 16);
226 for (i = 0; i < batchsize; i++) {
227 expand256_modm(batch.
scalars[i], RS[i] + 32, 32);
230 for (i = 1; i < batchsize; 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]);
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]))
245 for (i = 0; i < batchsize; i++)
246 if (!ge25519_unpack_negative_vartime(&batch.
points[batchsize+i+1], RS[i]))
249 ge25519_multi_scalarmult_vartime(&p, &batch, (batchsize * 2) + 1);
250 if (!ge25519_is_neutral_vartime(&p)) {
254 for (i = 0; i < batchsize; i++) {
256 ret |= (valid[i] ^ 1);
268 for (i = 0; i < num; i++) {
270 ret |= (valid[i] ^ 1);
struct batch_heap_t batch_heap
bignum256modm scalars[heap_batch_size]
unsigned char r[heap_batch_size][16]
unsigned char batch_point_buffer[3][32]
mdb_size_t count(MDB_cursor *cur)
#define bignum256modm_limb_size
#define bignum256modm_bits_per_limb
heap_index_t heap[heap_batch_size]
void ED25519_FN() ed25519_randombytes_unsafe(void *p, size_t len)
const GenericPointer< typename T::ValueType > T2 T::AllocatorType & a
void * memcpy(void *a, const void *b, size_t c)
bignum256modm_element_t bignum256modm[9]
int ed25519_sign_open(const unsigned char *m, size_t mlen, const ed25519_public_key pk, const ed25519_signature RS)
ge25519 points[heap_batch_size]
int 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)
uint32_t bignum256modm_element_t