ec_point.c 31.6 KB
Newer Older
Michael Hamburg's avatar
Michael Hamburg committed
1 2 3 4 5 6 7 8
/**
 * @cond internal
 * @file ec_point.c
 * @copyright
 *   Copyright (c) 2014 Cryptography Research, Inc.  \n
 *   Released under the MIT License.  See LICENSE.txt for license information.
 * @author Mike Hamburg
 * @warning This file was automatically generated.
9
 *     Then it was edited by hand.  Good luck, have fun.
10 11 12 13 14
 *
 * This file contains a huge number of different options for EC point arithmetic,
 * but only a few of them will be used by any given library.  They are here for
 * reference and for consistency checks.  The Goldilocks library link step strips
 * out unused functions.
Michael Hamburg's avatar
Michael Hamburg committed
15 16 17
 */

#include "ec_point.h"
18
#include "magic.h"
Michael Hamburg's avatar
Michael Hamburg committed
19 20 21

void
add_tw_niels_to_tw_extensible (
22 23
    tw_extensible_a_t  d,
    const tw_niels_a_t e
Michael Hamburg's avatar
Michael Hamburg committed
24
) {
25
    ANALYZE_THIS_ROUTINE_CAREFULLY;
26
    field_a_t L0, L1;
27
    field_subx_nr ( L1, d->y, d->x );
Michael Hamburg's avatar
Michael Hamburg committed
28 29 30 31 32 33 34
    field_mul ( L0, e->a, L1 );
    field_add_nr ( L1, d->x, d->y );
    field_mul ( d->y, e->b, L1 );
    field_mul ( L1, d->u, d->t );
    field_mul ( d->x, e->c, L1 );
    field_add_nr ( d->u, L0, d->y );
    field_subx_nr ( d->t, d->y, L0 );
35
    field_subx_nr ( d->y, d->z, d->x );
Michael Hamburg's avatar
Michael Hamburg committed
36 37 38 39
    field_add_nr ( L0, d->x, d->z );
    field_mul ( d->z, L0, d->y );
    field_mul ( d->x, d->y, d->t );
    field_mul ( d->y, L0, d->u );
Michael Hamburg's avatar
Michael Hamburg committed
40 41
}

42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
void
add_tw_extended (
    tw_extended_a_t  d,
    const tw_extended_a_t e
) {
    ANALYZE_THIS_ROUTINE_CAREFULLY;
    field_a_t L0, L1, L2;
    field_subx_nr ( L1, d->y, d->x );
    field_subx_nr ( L2, e->y, e->x );
    field_mul ( L0, L2, L1 );
    field_add_nr ( L1, d->y, d->x );
    field_add_nr ( L2, e->y, e->x );
    field_mul ( d->y, L2, L1 );
    field_mul ( L1, e->t, d->t );
    field_mulw_scc_wr ( d->x, L1, 2-2*EDWARDS_D );
    field_add_nr ( L1, L0, d->y );
    field_subx_nr ( L2, d->y, L0 );
    field_mul ( L0, d->z, e->z );
    field_add_nr ( L0, L0, L0 );
    field_add_nr ( d->y, L0, d->x );
    field_subx_nr ( L0, L0, d->x );
    field_mul ( d->z, L0, d->y );
    field_mul ( d->x, d->y, L2 );
    field_mul ( d->y, L0, L1 );
    field_mul ( d->t, L1, L2 );
}

void
add_sub_tw_extended (
Michael Hamburg's avatar
Michael Hamburg committed
71 72
    tw_extended_a_t c,
    const tw_extended_a_t  d,
73 74 75 76 77 78 79 80 81 82
    const tw_extended_a_t e,
    mask_t sub
) {
    field_a_t L0, L1, L2, L3;
    field_sub ( L1, d->y, d->x );
    field_sub ( L2, e->y, e->x );
    field_add ( L3, e->y, e->x );
    constant_time_cond_swap(L2,L3,sizeof(L2),sub);
    field_mul ( L0, L2, L1 );
    field_add ( L1, d->y, d->x );
Michael Hamburg's avatar
Michael Hamburg committed
83
    field_mul ( c->y, L3, L1 );
84
    field_mul ( L1, e->t, d->t );
Michael Hamburg's avatar
Michael Hamburg committed
85
    field_mulw_scc_wr ( c->x, L1, 2-2*EDWARDS_D );
86
    field_add ( L1, L0, d->y );
Michael Hamburg's avatar
Michael Hamburg committed
87
    field_sub ( L2, c->y, L0 );
88 89
    field_mul ( L0, d->z, e->z );
    field_add ( L0, L0, L0 );
Michael Hamburg's avatar
Michael Hamburg committed
90 91 92 93 94 95 96
    field_add ( c->y, L0, c->x );
    field_sub ( L0, L0, c->x );
    constant_time_cond_swap(L0,c->y,sizeof(L0),sub);
    field_mul ( c->z, L0, c->y );
    field_mul ( c->x, c->y, L2 );
    field_mul ( c->y, L0, L1 );
    field_mul ( c->t, L1, L2 );
97 98
}

Michael Hamburg's avatar
Michael Hamburg committed
99 100
void
sub_tw_niels_from_tw_extensible (
101 102
    tw_extensible_a_t  d,
    const tw_niels_a_t e
Michael Hamburg's avatar
Michael Hamburg committed
103
) {
104
    ANALYZE_THIS_ROUTINE_CAREFULLY;
105
    field_a_t L0, L1;
Michael Hamburg's avatar
Michael Hamburg committed
106 107 108 109 110 111 112 113 114 115 116 117 118
    field_subx_nr ( L1, d->y, d->x );
    field_mul ( L0, e->b, L1 );
    field_add_nr ( L1, d->x, d->y );
    field_mul ( d->y, e->a, L1 );
    field_mul ( L1, d->u, d->t );
    field_mul ( d->x, e->c, L1 );
    field_add_nr ( d->u, L0, d->y );
    field_subx_nr ( d->t, d->y, L0 );
    field_add_nr ( d->y, d->x, d->z );
    field_subx_nr ( L0, d->z, d->x );
    field_mul ( d->z, L0, d->y );
    field_mul ( d->x, d->y, d->t );
    field_mul ( d->y, L0, d->u );
Michael Hamburg's avatar
Michael Hamburg committed
119 120 121 122
}

void
add_tw_pniels_to_tw_extensible (
123 124
    tw_extensible_a_t   e,
    const tw_pniels_a_t a
Michael Hamburg's avatar
Michael Hamburg committed
125
) {
126
    field_a_t L0;
Michael Hamburg's avatar
Michael Hamburg committed
127 128
    field_mul ( L0, e->z, a->z );
    field_copy ( e->z, L0 );
129
    add_tw_niels_to_tw_extensible( e, a->n );
Michael Hamburg's avatar
Michael Hamburg committed
130 131 132 133
}

void
sub_tw_pniels_from_tw_extensible (
134 135
    tw_extensible_a_t   e,
    const tw_pniels_a_t a
Michael Hamburg's avatar
Michael Hamburg committed
136
) {
137
    field_a_t L0;
Michael Hamburg's avatar
Michael Hamburg committed
138 139
    field_mul ( L0, e->z, a->z );
    field_copy ( e->z, L0 );
140
    sub_tw_niels_from_tw_extensible( e, a->n );
Michael Hamburg's avatar
Michael Hamburg committed
141 142 143 144
}

void
double_tw_extensible (
145
    tw_extensible_a_t a
Michael Hamburg's avatar
Michael Hamburg committed
146
) {
147
    ANALYZE_THIS_ROUTINE_CAREFULLY;
148
    field_a_t L0, L1, L2;
Michael Hamburg's avatar
Michael Hamburg committed
149 150 151 152 153 154 155
    field_sqr ( L2, a->x );
    field_sqr ( L0, a->y );
    field_add_nr ( a->u, L2, L0 );
    field_add_nr ( a->t, a->y, a->x );
    field_sqr ( L1, a->t );
    field_sub_nr ( a->t, L1, a->u );
    field_bias ( a->t, 3 );
156
    IF32( field_weak_reduce( a->t ) );
Michael Hamburg's avatar
Michael Hamburg committed
157 158 159 160 161 162 163 164 165
    field_subx_nr ( L1, L0, L2 );
    field_sqr ( a->x, a->z );
    field_bias ( a->x, 2-is32 /*is32 ? 1 : 2*/ );
    field_add_nr ( a->z, a->x, a->x );
    field_sub_nr ( L0, a->z, L1 );
    IF32( field_weak_reduce( L0 ) );
    field_mul ( a->z, L1, L0 );
    field_mul ( a->x, L0, a->t );
    field_mul ( a->y, L1, a->u );
Michael Hamburg's avatar
Michael Hamburg committed
166 167 168 169
}

void
double_extensible (
170
    extensible_a_t a
Michael Hamburg's avatar
Michael Hamburg committed
171
) {
172
    ANALYZE_THIS_ROUTINE_CAREFULLY;
173
    field_a_t L0, L1, L2;
Michael Hamburg's avatar
Michael Hamburg committed
174 175 176 177 178 179 180
    field_sqr ( L2, a->x );
    field_sqr ( L0, a->y );
    field_add_nr ( L1, L2, L0 );
    field_add_nr ( a->t, a->y, a->x );
    field_sqr ( a->u, a->t );
    field_sub_nr ( a->t, a->u, L1 );
    field_bias ( a->t, 3 );
181
    IF32( field_weak_reduce( a->t ) );
Michael Hamburg's avatar
Michael Hamburg committed
182 183 184 185 186 187 188 189 190
    field_subx_nr ( a->u, L0, L2 );
    field_sqr ( a->x, a->z );
    field_bias ( a->x, 2 );
    field_add_nr ( a->z, a->x, a->x );
    field_sub_nr ( L0, a->z, L1 );
    IF32( field_weak_reduce( L0 ) );
    field_mul ( a->z, L1, L0 );
    field_mul ( a->x, L0, a->t );
    field_mul ( a->y, L1, a->u );
Michael Hamburg's avatar
Michael Hamburg committed
191 192 193 194
}

void
twist_and_double (
195 196
    tw_extensible_a_t    b,
    const extensible_a_t a
Michael Hamburg's avatar
Michael Hamburg committed
197
) {
198
    field_a_t L0;
Michael Hamburg's avatar
Michael Hamburg committed
199 200
    field_sqr ( b->x, a->x );
    field_sqr ( b->z, a->y );
201 202
    field_add ( b->u, b->x, b->z );
    field_add ( b->t, a->y, a->x );
Michael Hamburg's avatar
Michael Hamburg committed
203 204 205 206
    field_sqr ( L0, b->t );
    field_sub ( b->t, L0, b->u );
    field_sub ( L0, b->z, b->x );
    field_sqr ( b->x, a->z );
207 208
    field_add ( b->z, b->x, b->x );
    field_sub ( b->y, b->z, b->u );
Michael Hamburg's avatar
Michael Hamburg committed
209 210 211
    field_mul ( b->z, L0, b->y );
    field_mul ( b->x, b->y, b->t );
    field_mul ( b->y, L0, b->u );
Michael Hamburg's avatar
Michael Hamburg committed
212 213 214 215
}

void
untwist_and_double (
216 217
    extensible_a_t          b,
    const tw_extensible_a_t a
Michael Hamburg's avatar
Michael Hamburg committed
218
) {
219
    field_a_t L0;
Michael Hamburg's avatar
Michael Hamburg committed
220 221 222
    field_sqr ( b->x, a->x );
    field_sqr ( b->z, a->y );
    field_add ( L0, b->x, b->z );
223
    field_add ( b->t, a->y, a->x );
Michael Hamburg's avatar
Michael Hamburg committed
224 225
    field_sqr ( b->u, b->t );
    field_sub ( b->t, b->u, L0 );
226
    field_sub ( b->u, b->z, b->x );
Michael Hamburg's avatar
Michael Hamburg committed
227
    field_sqr ( b->x, a->z );
228 229
    field_add ( b->z, b->x, b->x );
    field_sub ( b->y, b->z, b->u );
Michael Hamburg's avatar
Michael Hamburg committed
230 231 232
    field_mul ( b->z, L0, b->y );
    field_mul ( b->x, b->y, b->t );
    field_mul ( b->y, L0, b->u );
Michael Hamburg's avatar
Michael Hamburg committed
233 234 235 236
}

void
convert_tw_affine_to_tw_pniels (
237 238
    tw_pniels_a_t       b,
    const tw_affine_a_t a
Michael Hamburg's avatar
Michael Hamburg committed
239
) {
240 241
    field_sub ( b->n->a, a->y, a->x );
    field_add ( b->n->b, a->x, a->y );
Michael Hamburg's avatar
Michael Hamburg committed
242
    field_mul ( b->z, a->y, a->x );
243
    field_mulw_scc_wr ( b->n->c, b->z, 2*EDWARDS_D-2 );
Michael Hamburg's avatar
Michael Hamburg committed
244
    field_set_ui( b->z, 2 );
Michael Hamburg's avatar
Michael Hamburg committed
245 246 247 248
}

void
convert_tw_affine_to_tw_extensible (
249 250
    tw_extensible_a_t   b,
    const tw_affine_a_t a
Michael Hamburg's avatar
Michael Hamburg committed
251
) {
252 253
    field_copy ( b->x, a->x );
    field_copy ( b->y, a->y );
Michael Hamburg's avatar
Michael Hamburg committed
254
    field_set_ui( b->z, 1 );
255 256
    field_copy ( b->t, a->x );
    field_copy ( b->u, a->y );
Michael Hamburg's avatar
Michael Hamburg committed
257 258
}

259 260 261 262 263 264 265 266 267 268 269
void
convert_tw_extensible_to_tw_extended (
    tw_extended_a_t   b,
    const tw_extensible_a_t a
) {
    field_copy ( b->x, a->x );
    field_copy ( b->y, a->y );
    field_copy ( b->z, a->z );
    field_mul ( b->t, a->t, a->u );
}

Michael Hamburg's avatar
Michael Hamburg committed
270 271
void
convert_affine_to_extensible (
272 273
    extensible_a_t   b,
    const affine_a_t a
Michael Hamburg's avatar
Michael Hamburg committed
274
) {
275 276
    field_copy ( b->x, a->x );
    field_copy ( b->y, a->y );
Michael Hamburg's avatar
Michael Hamburg committed
277
    field_set_ui( b->z, 1 );
278 279
    field_copy ( b->t, a->x );
    field_copy ( b->u, a->y );
Michael Hamburg's avatar
Michael Hamburg committed
280 281 282 283
}

void
convert_tw_extensible_to_tw_pniels (
284 285
    tw_pniels_a_t           b,
    const tw_extensible_a_t a
Michael Hamburg's avatar
Michael Hamburg committed
286
) {
287 288
    field_sub ( b->n->a, a->y, a->x );
    field_add ( b->n->b, a->x, a->y );
Michael Hamburg's avatar
Michael Hamburg committed
289
    field_mul ( b->z, a->u, a->t );
290
    field_mulw_scc_wr ( b->n->c, b->z, 2*EDWARDS_D-2 );
291
    field_add ( b->z, a->z, a->z );
Michael Hamburg's avatar
Michael Hamburg committed
292 293 294 295
}

void
convert_tw_pniels_to_tw_extensible (
296 297
    tw_extensible_a_t   e,
    const tw_pniels_a_t d
Michael Hamburg's avatar
Michael Hamburg committed
298
) {
299 300
    field_add ( e->u, d->n->b, d->n->a );
    field_sub ( e->t, d->n->b, d->n->a );
Michael Hamburg's avatar
Michael Hamburg committed
301 302 303
    field_mul ( e->x, d->z, e->t );
    field_mul ( e->y, d->z, e->u );
    field_sqr ( e->z, d->z );
Michael Hamburg's avatar
Michael Hamburg committed
304 305 306 307
}

void
convert_tw_niels_to_tw_extensible (
308 309
    tw_extensible_a_t  e,
    const tw_niels_a_t d
Michael Hamburg's avatar
Michael Hamburg committed
310
) {
311 312
    field_add ( e->y, d->b, d->a );
    field_sub ( e->x, d->b, d->a );
Michael Hamburg's avatar
Michael Hamburg committed
313
    field_set_ui( e->z, 1 );
314 315
    field_copy ( e->t, e->x );
    field_copy ( e->u, e->y );
Michael Hamburg's avatar
Michael Hamburg committed
316 317
}

Michael Hamburg's avatar
Michael Hamburg committed
318
void
319
decaf_deserialize_montgomery (
320
    montgomery_aux_a_t a,
321
    const field_a_t s
Michael Hamburg's avatar
Michael Hamburg committed
322
) {
Michael Hamburg's avatar
Michael Hamburg committed
323
    field_copy ( a->s0, s );
324
    field_sqr ( a->xa, s );
325 326 327
    field_set_ui ( a->za, 1 );
    field_set_ui ( a->xd, 1 );
    field_set_ui ( a->zd, 0 );
Michael Hamburg's avatar
Michael Hamburg committed
328 329
}

330 331 332 333
void
montgomery_aux_step (
    struct montgomery_aux_t* a
) {
334
    ANALYZE_THIS_ROUTINE_CAREFULLY;
335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350
    field_add_nr ( a->xs, a->xa, a->za );
    field_subx_nr ( a->zs, a->xa, a->za );
    field_add_nr ( a->xa, a->xd, a->zd );
    field_subx_nr ( a->za, a->xd, a->zd );
    field_mul ( a->xd, a->xa, a->zs );
    field_mul ( a->zd, a->xs, a->za );
    field_add_nr ( a->xs, a->xd, a->zd );
    field_subx_nr ( a->zd, a->xd, a->zd );
    field_mul ( a->zs, a->zd, a->s0 );
    field_sqr ( a->zd, a->xa );
    field_sqr ( a->xa, a->za );
    field_subx_nr ( a->za, a->zd, a->xa );
    field_mul ( a->xd, a->xa, a->zd );
    field_mulw_scc_wr ( a->zd, a->za, 1-EDWARDS_D );
    field_add_nr ( a->xa, a->xa, a->zd );
    field_mul ( a->zd, a->xa, a->za );
Michael Hamburg's avatar
Michael Hamburg committed
351 352
    field_sqr ( a->xa, a->xs );         
    field_sqr ( a->za, a->zs );         
353 354
}

Michael Hamburg's avatar
Michael Hamburg committed
355 356
void
montgomery_step (
357
    montgomery_a_t a
Michael Hamburg's avatar
Michael Hamburg committed
358
) {
359
    ANALYZE_THIS_ROUTINE_CAREFULLY;
360
    field_a_t L0, L1;
Michael Hamburg's avatar
Michael Hamburg committed
361
    field_add_nr ( L0, a->zd, a->xd );
362 363
    field_subx_nr ( L1, a->xd, a->zd );
    field_subx_nr ( a->zd, a->xa, a->za );
Michael Hamburg's avatar
Michael Hamburg committed
364 365 366 367 368 369
    field_mul ( a->xd, L0, a->zd );
    field_add_nr ( a->zd, a->za, a->xa );
    field_mul ( a->za, L1, a->zd );
    field_add_nr ( a->xa, a->za, a->xd );
    field_sqr ( a->zd, a->xa );
    field_mul ( a->xa, a->z0, a->zd );
370
    field_subx_nr ( a->zd, a->xd, a->za );
Michael Hamburg's avatar
Michael Hamburg committed
371 372 373
    field_sqr ( a->za, a->zd );
    field_sqr ( a->xd, L0 );
    field_sqr ( L0, L1 );
374
    field_mulw_scc ( a->zd, a->xd, 1-EDWARDS_D ); /* FIXME PERF MULW */
375
    field_subx_nr ( L1, a->xd, L0 );
Michael Hamburg's avatar
Michael Hamburg committed
376 377 378 379 380
    field_mul ( a->xd, L0, a->zd );
    field_sub_nr ( L0, a->zd, L1 );
    field_bias ( L0, 4 - 2*is32 /*is32 ? 2 : 4*/ );
    IF32( field_weak_reduce( L0 ) );
    field_mul ( a->zd, L0, L1 );
Michael Hamburg's avatar
Michael Hamburg committed
381 382 383 384
}

void
deserialize_montgomery (
385
    montgomery_a_t a,
386
    const field_a_t sbz
Michael Hamburg's avatar
Michael Hamburg committed
387
) {
Michael Hamburg's avatar
Michael Hamburg committed
388 389 390 391
    field_sqr ( a->z0, sbz );
    field_set_ui( a->xd, 1 );
    field_set_ui( a->zd, 0 );
    field_set_ui( a->xa, 1 );
392
    field_copy ( a->za, a->z0 );
Michael Hamburg's avatar
Michael Hamburg committed
393 394 395 396
}

mask_t
serialize_montgomery (
397
    field_a_t             b,
398
    const montgomery_a_t a,
399
    const field_a_t       sbz
Michael Hamburg's avatar
Michael Hamburg committed
400
) {
401
    mask_t L4, L5, L6;
402
    field_a_t L0, L1, L2, L3;
Michael Hamburg's avatar
Michael Hamburg committed
403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438
    field_mul ( L3, a->z0, a->zd );
    field_sub ( L1, L3, a->xd );
    field_mul ( L3, a->za, L1 );
    field_mul ( L2, a->z0, a->xd );
    field_sub ( L1, L2, a->zd );
    field_mul ( L0, a->xa, L1 );
    field_add ( L2, L0, L3 );
    field_sub ( L1, L3, L0 );
    field_mul ( L3, L1, L2 );
    field_copy ( L2, a->z0 );
    field_addw ( L2, 1 );
    field_sqr ( L0, L2 );
    field_mulw_scc_wr ( L1, L0, EDWARDS_D-1 );
    field_add ( L2, a->z0, a->z0 );
    field_add ( L0, L2, L2 );
    field_add ( L2, L0, L1 );
    field_mul ( L0, a->xd, L2 );
    L5 = field_is_zero( a->zd );
    L6 = -   L5;
    constant_time_mask ( L1, L0, sizeof(L1), L5 );
    field_add ( L2, L1, a->zd );
    L4 = ~   L5;
    field_mul ( L1, sbz, L3 );
    field_addw ( L1, L6 );
    field_mul ( L3, L2, L1 );
    field_mul ( L1, L3, L2 );
    field_mul ( L2, L3, a->xd );
    field_mul ( L3, L1, L2 );
    field_isr ( L0, L3 );
    field_mul ( L2, L1, L0 );
    field_sqr ( L1, L0 );
    field_mul ( L0, L3, L1 );
    constant_time_mask ( b, L2, sizeof(L1), L4 );
    field_subw( L0, 1 );
    L5 = field_is_zero( L0 );
    L4 = field_is_zero( sbz );
439
    return    L5 |    L4;
Michael Hamburg's avatar
Michael Hamburg committed
440 441 442 443
}

void
serialize_extensible (
444
    field_a_t             b,
445
    const extensible_a_t a
Michael Hamburg's avatar
Michael Hamburg committed
446
) {
447
    field_a_t L0, L1, L2;
Michael Hamburg's avatar
Michael Hamburg committed
448 449 450 451 452 453 454 455 456 457 458
    field_sub ( L0, a->y, a->z );
    field_add ( b, a->z, a->y );
    field_mul ( L1, a->z, a->x );
    field_mul ( L2, L0, L1 );
    field_mul ( L1, L2, L0 );
    field_mul ( L0, L2, b );
    field_mul ( L2, L1, L0 );
    field_isr ( L0, L2 );
    field_mul ( b, L1, L0 );
    field_sqr ( L1, L0 );
    field_mul ( L0, L2, L1 );
Michael Hamburg's avatar
Michael Hamburg committed
459 460
}

461
static void
462
decaf_abs (
463
    field_a_t a
464
) {
465
    field_cond_neg ( a, field_high_bit(a) );
466 467 468
    field_strong_reduce ( a );
}

469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503
mask_t
decaf_serialize_montgomery (
    field_a_t             out,
    const montgomery_aux_a_t a,
    mask_t                swapped
) { 
    field_a_t xz_d, xz_a, x0, den, L0, L1, L2, L3;
    mask_t zcase, output_zero, flip, succ, za_zero;
    field_mul(xz_d, a->xd, a->zd);
    field_mul(xz_a, a->xa, a->za);
    output_zero = field_is_zero(xz_d);
    za_zero = field_is_zero(a->za);
    field_addw(xz_d, -output_zero); /* make xz_d always nonzero */
    zcase = output_zero | field_is_zero(xz_a);
    
    field_sqr(x0, a->s0);
    
    /* Curve test in zcase */
    field_copy(L0,x0);
    field_addw(L0,1);
    field_sqr(L1,L0);
    field_mulw_scc_wr(L0,x0,-4*EDWARDS_D);
    field_add(L1,L1,L0);
    constant_time_select(xz_a,L1,xz_a,sizeof(xz_a),zcase);
    
    /* Compute denominator */
    field_mul(L0, x0, xz_d);
    field_mulw(L2, L0, 4);
    field_mul(L1, L2, xz_a);
    field_isr(den, L1);

    /* Check squareness */
    field_sqr(L2, den);
    field_mul(L0, L1, L2);
    field_addw(L0, 1);
504
    succ = ~field_high_bit(a->s0) & ~field_is_zero(L0);
505 506 507 508 509 510 511 512 513 514 515 516 517

    /* Compute y/x */
    field_mul(L1, x0, a->xd);
    field_sub(L1, a->zd, L1);
    field_mul(L0, a->za, L1); /* L0 = "opq" */
    field_mul(L1, x0, a->zd);
    field_sub(L1, L1, a->xd);
    field_mul(L2, a->xa, L1); /* L2 = "pqr" */

    field_sub(L1, L0, L2);
    field_add(L0, L0, L2);
    field_mul(L2, L1, den); /* L2 = y0 / x0 */
    field_mul(L1, L0, den); /* L1 = yO / xO */
518
    flip = field_high_bit(L1) ^ field_high_bit(L2) ^ za_zero;
519 520 521 522 523 524 525 526
    constant_time_select(L0, a->zd, a->xd, sizeof(L0), flip); /* L0 = "times" */
    /* OK, done with y-coordinates */

    /* OK, now correct for swappage */
    field_add(den,den,den);
    field_mul(L1,den,a->s0);
    field_sqr(L2,L1);
    field_mul(L3,L2,xz_a);
527
    constant_time_select(den,L3,L1,sizeof(den),swapped | zcase);
528 529 530 531 532 533 534

    /* compute the output */
    field_mul(L1,L0,den);
    
    constant_time_select(L2,a->s0,a->zs,sizeof(L2),zcase); /* zs, but s0 in zcase */
    field_mul(L0,L1,L2);
    
535
    constant_time_select(L3,a->zd,a->xd,sizeof(L3),za_zero);
536 537 538 539
    constant_time_select(L2,L3,a->xs,sizeof(L2),zcase); /* xs, but zq or qq in zcase */
    field_mul(out,L0,L2);
    
    constant_time_mask(out,out,sizeof(field_a_t),~output_zero);
540
    decaf_abs(out);
541 542 543 544
    
    return succ;
}

545 546
void
decaf_serialize_extensible (
547
    field_a_t b,
548
    const extensible_a_t a
549
) {
550
    field_a_t L0, L1, L2, L3;
551
    field_mulw_scc_wr ( L2, a->y, EDWARDS_D ); 
Michael Hamburg's avatar
Michael Hamburg committed
552 553 554
    field_mul ( L3, L2, a->t ); 
    field_mul ( L2, L3, a->u ); 
    field_mul ( L0, a->x, a->z ); 
555
    field_sub ( L3, L0, L2 ); 
Michael Hamburg's avatar
Michael Hamburg committed
556
    field_add ( L0, a->y, a->z ); 
557 558
    field_sub ( L1, a->z, a->y ); 
    field_mul ( L2, L1, L0 );
559
    field_mulw_scc_wr ( L1, L2, 1-EDWARDS_D );
560
    field_isr ( L0, L1 );
561
    field_mulw_scc_wr ( L1, L0, 1-EDWARDS_D ); 
562 563 564
    field_mul ( L2, L1, L0 );
    field_mul ( L0, L2, L3 );
    field_add ( L3, L1, L1 );        
Michael Hamburg's avatar
Michael Hamburg committed
565
    field_mul ( L2, L3, a->z );   
566
    field_cond_neg ( L1, ~field_high_bit(L2) ); 
Michael Hamburg's avatar
Michael Hamburg committed
567 568
    field_mul ( L2, L1, a->y ); 
    field_add ( b, L0, L2 );
569
    decaf_abs ( b );
570 571
}

572 573
void
decaf_serialize_tw_extensible (
574
    field_a_t            b,
575
    const tw_extensible_a_t a
576
) {
577
    field_a_t L0, L1, L2, L3;
Michael Hamburg's avatar
Michael Hamburg committed
578 579 580 581 582 583 584
    field_mulw_scc ( L2, a->y, 1-EDWARDS_D ); 
    field_mul ( L3, L2, a->t ); 
    field_mul ( L2, L3, a->u ); 
    field_mul ( L0, a->x, a->z ); 
    field_sub ( L3, L2, L0 ); 
    field_add ( L0, a->z, a->y ); 
    field_sub ( L1, a->z, a->y ); 
585 586 587 588 589 590 591
    field_mul ( L2, L1, L0 );
    field_mulw_scc ( L1, L2, -EDWARDS_D );
    field_isr ( L0, L1 );
    field_mulw_scc ( L1, L0, -EDWARDS_D ); 
    field_mul ( L2, L1, L0 );
    field_mul ( L0, L2, L3 );
    field_add ( L3, L1, L1 );  
Michael Hamburg's avatar
Michael Hamburg committed
592
    field_mul ( L2, L3, a->z );   
593
    field_cond_neg ( L1, ~field_high_bit(L2) ); 
Michael Hamburg's avatar
Michael Hamburg committed
594 595
    field_mul ( L2, L1, a->y ); 
    field_add ( b, L0, L2 );
596
    decaf_abs ( b );
597 598
}

599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682
void
decaf_serialize_tw_extended (
    field_a_t b,
    const tw_extended_a_t a
) {
    field_a_t L0, L1, L2, L3;
    field_mulw_scc ( L0, a->y, 1-EDWARDS_D ); 
    field_mul ( L2, L0, a->t ); 
    field_mul ( L0, a->x, a->z ); 
    field_sub ( L3, L2, L0 ); 
    field_add ( L0, a->z, a->y ); 
    field_sub ( L1, a->z, a->y ); 
    field_mul ( L2, L1, L0 );
    field_mulw_scc ( L1, L2, -EDWARDS_D );
    field_isr ( L0, L1 );
    field_mulw_scc ( L1, L0, -EDWARDS_D ); 
    field_mul ( L2, L1, L0 );
    field_mul ( L0, L2, L3 );
    field_add ( L3, L1, L1 );  
    field_mul ( L2, L3, a->z );   
    field_cond_neg ( L1, ~field_high_bit(L2) ); 
    field_mul ( L2, L1, a->y ); 
    field_add ( b, L0, L2 );
    decaf_abs ( b );
}

/*
static void
tw_extended_efgh (
    tw_extended_a_t a,
    field_a_t x,
    field_a_t xz,
    field_a_t y,
    field_a_t yz
) {
    field_mul(a->x,x,yz);
    field_mul(a->y,y,xz);
    field_mul(a->z,xz,yz);
    field_mul(a->t,x,y);
}
*/

mask_t
decaf_deserialize_tw_extended (
    tw_extended_a_t a,
    const field_a_t s,
    mask_t allow_identity
) {
    field_a_t L0, L1, L2, L3, L4;
    mask_t succ, zero;
    zero = field_is_zero(s);
    succ = allow_identity | ~zero;
    succ &= ~field_high_bit(s);

    field_sqr ( L0, s ); // L0 = s^2
    field_neg ( a->z, L0 );
    field_addw ( a->z, 1 );
    field_sqr ( L1, a->z ); 
    field_mulw_scc_wr ( L2, L0, 4-4*EDWARDS_D );
    field_add ( L2, L2, L1 ); // L2 = [t^2]
    field_mul ( L1, L2, L0 ); // L1 = [t^2] s^2

    field_isr ( L3, L1 ); // L3 =? 1/ts; check it
    field_sqr ( L4, L3 );
    field_mul ( L0, L4, L1 );
    field_addw( L0, 1 );
    succ &= ~field_is_zero( L0 );

    field_mul ( L1, L2, L3 ); // L1 = t^2 * 1/ts = t/s
    field_cond_neg ( L3, field_high_bit(L1) ); // negate 1/ts?

    field_add( a->x, s, s );
    field_mul ( L2, L3, s );

    field_neg ( L1, a->z );      
    field_addw ( L1, 2 );
    field_mul ( L0, L1, L2 );
    field_mul(a->y,L0,a->z);
    field_mul(a->t,a->x,L0);
    field_addw ( a->y, -zero );

    return succ;
}

683 684
mask_t
decaf_deserialize_affine (
685
    affine_a_t a,
686
    const field_a_t s,
687 688
    mask_t allow_identity
) {
689
    field_a_t L0, L1, L2, L3, L4, L5;
690 691 692
    mask_t succ, zero;
    zero = field_is_zero(s);
    succ = allow_identity | ~zero;
693
    succ &= ~field_high_bit(s);
Michael Hamburg's avatar
Michael Hamburg committed
694
    field_sqr ( L0, s );
695 696 697 698 699 700 701 702 703 704 705 706 707 708 709
    field_copy ( L1, L0 );
    field_addw ( L1, 1 );
    field_make_nonzero ( L1 );
    field_sqr ( L2, L1 );
    field_mulw_scc_wr ( L3, L0, -4*EDWARDS_D );
    field_add ( L3, L3, L2 );
    field_mul ( L4, L3, L2 );
    field_mul ( L2, L4, L0 );
    field_isr ( L4, L2 );
    field_sqr ( L5, L4 );
    field_mul ( L0, L5, L2 );
    field_addw( L0, 1 );
    succ &= ~field_is_zero( L0 );
    field_mul ( L2, L3, L1 );
    field_mul ( L3, L2, L4 );
710
    field_cond_neg ( L4, field_high_bit(L3) );
711 712 713 714 715 716 717 718 719 720
    field_mul ( L3, L4, s );
    field_sqr ( L4, L3 );
    field_mul ( L0, L2, L4 );
    field_add ( L0, L0, L0 );
    field_mul ( a->x, L0, s );
    field_mul ( L2, L1, L3 );
    field_neg ( L1, L1 ); 
    field_addw ( L1, 2 );
    field_mul ( a->y, L1, L2 );
    field_addw ( a->y, -zero );
721 722 723 724 725
    return succ;
}

mask_t
decaf_deserialize_tw_affine (
726
    tw_affine_a_t a,
727
    const field_a_t s,
728 729
    mask_t allow_identity
) {
730
    field_a_t L0, L1, L2, L3, L4, L5;
731 732 733
    mask_t succ, zero;
    zero = field_is_zero(s);
    succ = allow_identity | ~zero;
734
    succ &= ~field_high_bit(s);
Michael Hamburg's avatar
Michael Hamburg committed
735
    field_sqr ( L0, s );
736 737 738 739 740 741 742 743 744 745 746 747 748 749 750
    field_neg ( L1, L0 );
    field_addw ( L1, 1 );
    field_make_nonzero ( L1 );
    field_sqr ( L2, L1 );
    field_mulw_scc_wr ( L3, L0, 4-4*EDWARDS_D );
    field_add ( L3, L3, L2 );
    field_mul ( L4, L3, L2 );
    field_mul ( L2, L4, L0 );
    field_isr ( L4, L2 );
    field_sqr ( L5, L4 );
    field_mul ( L0, L5, L2 );
    field_addw( L0, 1 );
    succ &= ~field_is_zero( L0 );
    field_mul ( L2, L3, L1 );
    field_mul ( L3, L2, L4 );
751
    field_cond_neg ( L4, field_high_bit(L3) );
752 753 754 755 756 757 758 759 760 761
    field_mul ( L3, L4, s );
    field_sqr ( L4, L3 );
    field_mul ( L0, L2, L4 );
    field_add ( L0, L0, L0 );
    field_mul ( a->x, L0, s );
    field_mul ( L2, L1, L3 );
    field_neg ( L1, L1 );      
    field_addw ( L1, 2 );
    field_mul ( a->y, L1, L2 );
    field_addw ( a->y, -zero );
762 763 764
    return succ;
}

Michael Hamburg's avatar
Michael Hamburg committed
765 766
void
untwist_and_double_and_serialize (
767
    field_a_t                b,
768
    const tw_extensible_a_t a
Michael Hamburg's avatar
Michael Hamburg committed
769
) {
770
    field_a_t L0, L1, L2, L3;
Michael Hamburg's avatar
Michael Hamburg committed
771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787
    field_mul ( L3, a->y, a->x );
    field_add ( b, a->y, a->x );
    field_sqr ( L1, b );
    field_add ( L2, L3, L3 );
    field_sub ( b, L1, L2 );
    field_sqr ( L2, a->z );
    field_sqr ( L1, L2 );
    field_add ( b, b, b );
    field_mulw_scc ( L2, b, EDWARDS_D-1 );
    field_mulw_scc ( b, L2, EDWARDS_D-1 );
    field_mul ( L0, L2, L1 );
    field_mul ( L2, b, L0 );
    field_isr ( L0, L2 );
    field_mul ( L1, b, L0 );
    field_sqr ( b, L0 );
    field_mul ( L0, L2, b );
    field_mul ( b, L1, L3 );
Michael Hamburg's avatar
Michael Hamburg committed
788 789 790 791
}

void
twist_even (
792 793
    tw_extensible_a_t    b,
    const extensible_a_t a
Michael Hamburg's avatar
Michael Hamburg committed
794
) {
Michael Hamburg's avatar
Michael Hamburg committed
795 796
    field_sqr ( b->y, a->z );
    field_sqr ( b->z, a->x );
797 798
    field_sub ( b->u, b->y, b->z );
    field_sub ( b->z, a->z, a->x );
Michael Hamburg's avatar
Michael Hamburg committed
799
    field_mul ( b->y, b->z, a->y );
800
    field_sub ( b->z, a->z, a->y );
Michael Hamburg's avatar
Michael Hamburg committed
801 802 803 804 805 806 807 808 809 810 811
    field_mul ( b->x, b->z, b->y );
    field_mul ( b->t, b->x, b->u );
    field_mul ( b->y, b->x, b->t );
    field_isr ( b->t, b->y );
    field_mul ( b->u, b->x, b->t );
    field_sqr ( b->x, b->t );
    field_mul ( b->t, b->y, b->x );
    field_mul ( b->x, a->x, b->u );
    field_mul ( b->y, a->y, b->u );
    field_addw ( b->y, -field_is_zero( b->z ) );
    field_set_ui( b->z, 1 );
812 813
    field_copy ( b->t, b->x );
    field_copy ( b->u, b->y );
Michael Hamburg's avatar
Michael Hamburg committed
814 815 816 817
}

void
test_only_twist (
818 819
    tw_extensible_a_t    b,
    const extensible_a_t a
Michael Hamburg's avatar
Michael Hamburg committed
820
) {
821
    field_a_t L0, L1;
Michael Hamburg's avatar
Michael Hamburg committed
822 823
    field_sqr ( b->u, a->z );
    field_sqr ( b->y, a->x );
824 825 826 827
    field_sub ( b->z, b->u, b->y );
    field_add ( b->y, b->z, b->z );
    field_add ( b->u, b->y, b->y );
    field_sub ( b->y, a->z, a->x );
Michael Hamburg's avatar
Michael Hamburg committed
828
    field_mul ( b->x, b->y, a->y );
829
    field_sub ( b->z, a->z, a->y );
Michael Hamburg's avatar
Michael Hamburg committed
830 831 832 833 834 835 836 837 838 839 840 841 842
    field_mul ( b->t, b->z, b->x );
    field_mul ( L1, b->t, b->u );
    field_mul ( b->x, b->t, L1 );
    field_isr ( L0, b->x );
    field_mul ( b->u, b->t, L0 );
    field_sqr ( L1, L0 );
    field_mul ( b->t, b->x, L1 );
    field_add ( L1, a->y, a->x );
    field_sub ( L0, a->x, a->y );
    field_mul ( b->x, b->t, L0 );
    field_add ( L0, b->x, L1 );
    field_sub ( b->t, L1, b->x );
    field_mul ( b->x, L0, b->u );
843
    field_addw ( b->x, -field_is_zero( b->y ) );
Michael Hamburg's avatar
Michael Hamburg committed
844
    field_mul ( b->y, b->t, b->u );
845 846 847 848
    field_addw ( b->y, -field_is_zero( b->z ) );
    field_set_ui( b->z, 1+field_is_zero( a->y ) );
    field_copy ( b->t, b->x );
    field_copy ( b->u, b->y );
Michael Hamburg's avatar
Michael Hamburg committed
849 850 851 852
}

mask_t
is_even_pt (
853
    const extensible_a_t a
Michael Hamburg's avatar
Michael Hamburg committed
854
) {
855
    field_a_t L0, L1, L2;
Michael Hamburg's avatar
Michael Hamburg committed
856 857 858 859
    field_sqr ( L2, a->z );
    field_sqr ( L1, a->x );
    field_sub ( L0, L2, L1 );
    return field_is_square ( L0 );
Michael Hamburg's avatar
Michael Hamburg committed
860 861 862 863
}

mask_t
is_even_tw (
864
    const tw_extensible_a_t a
Michael Hamburg's avatar
Michael Hamburg committed
865
) {
866
    field_a_t L0, L1, L2;
Michael Hamburg's avatar
Michael Hamburg committed
867 868 869 870
    field_sqr ( L2, a->z );
    field_sqr ( L1, a->x );
    field_add ( L0, L1, L2 );
    return field_is_square ( L0 );
Michael Hamburg's avatar
Michael Hamburg committed
871 872 873 874
}

mask_t
deserialize_affine (
875
    affine_a_t     a,
876 877 878
    const field_a_t sz
) {
    field_a_t L0, L1, L2, L3;
Michael Hamburg's avatar
Michael Hamburg committed
879 880 881 882 883 884 885 886 887
    field_sqr ( L1, sz );
    field_copy ( L3, L1 );
    field_addw ( L3, 1 );
    field_sqr ( L2, L3 );
    field_mulw_scc ( a->x, L2, EDWARDS_D-1 ); /* PERF MULW */
    field_add ( L3, L1, L1 );
    field_add ( a->y, L3, L3 );
    field_add ( L3, a->y, a->x );
    field_copy ( a->y, L1 );
888
    field_neg ( a->x, a->y );
Michael Hamburg's avatar
Michael Hamburg committed
889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904
    field_addw ( a->x, 1 );
    field_mul ( a->y, a->x, L3 );
    field_sqr ( L2, a->x );
    field_mul ( L0, L2, a->y );
    field_mul ( a->y, a->x, L0 );
    field_isr ( L3, a->y );
    field_mul ( a->y, L2, L3 );
    field_sqr ( L2, L3 );
    field_mul ( L3, L0, L2 );
    field_mul ( L0, a->x, L3 );
    field_add ( L2, a->y, a->y );
    field_mul ( a->x, sz, L2 );
    field_addw ( L1, 1 );
    field_mul ( a->y, L1, L3 );
    field_subw( L0, 1 );
    return field_is_zero( L0 );
Michael Hamburg's avatar
Michael Hamburg committed
905 906 907 908
}

mask_t
deserialize_and_twist_approx (
909
    tw_extensible_a_t a,
910 911 912
    const field_a_t    sz
) {
    field_a_t L0, L1;
Michael Hamburg's avatar
Michael Hamburg committed
913
    field_sqr ( a->z, sz );
914
    field_copy ( a->y, a->z );
Michael Hamburg's avatar
Michael Hamburg committed
915 916
    field_addw ( a->y, 1 );
    field_sqr ( L0, a->y );
917 918 919 920
    field_mulw_scc ( a->x, L0, EDWARDS_D-1 );
    field_add ( a->y, a->z, a->z );
    field_add ( a->u, a->y, a->y );
    field_add ( a->y, a->u, a->x );
Michael Hamburg's avatar
Michael Hamburg committed
921
    field_sqr ( a->x, a->z );
922
    field_neg ( a->u, a->x );
Michael Hamburg's avatar
Michael Hamburg committed
923 924 925 926 927 928 929 930 931 932 933 934 935 936
    field_addw ( a->u, 1 );
    field_mul ( a->x, sqrt_d_minus_1, a->u );
    field_mul ( L0, a->x, a->y );
    field_mul ( a->t, L0, a->y );
    field_mul ( a->u, a->x, a->t );
    field_mul ( a->t, a->u, L0 );
    field_mul ( a->y, a->x, a->t );
    field_isr ( L0, a->y );
    field_mul ( a->y, a->u, L0 );
    field_sqr ( L1, L0 );
    field_mul ( a->u, a->t, L1 );
    field_mul ( a->t, a->x, a->u );
    field_add ( a->x, sz, sz );
    field_mul ( L0, a->u, a->x );
937
    field_copy ( a->x, a->z );
Michael Hamburg's avatar
Michael Hamburg committed
938 939 940 941 942 943 944
    field_neg ( L1, a->x );
    field_addw ( L1, 1 );
    field_mul ( a->x, L1, L0 );
    field_mul ( L0, a->u, a->y );
    field_addw ( a->z, 1 );
    field_mul ( a->y, a->z, L0 );
    field_subw( a->t, 1 );
945
    mask_t ret = field_is_zero( a->t );
Michael Hamburg's avatar
Michael Hamburg committed
946
    field_set_ui( a->z, 1 );
947 948
    field_copy ( a->t, a->x );
    field_copy ( a->u, a->y );
Michael Hamburg's avatar
Michael Hamburg committed
949 950 951 952 953
    return ret;
}

void
set_identity_extensible (
954
    extensible_a_t a
Michael Hamburg's avatar
Michael Hamburg committed
955
) {
Michael Hamburg's avatar
Michael Hamburg committed
956 957 958 959 960
    field_set_ui( a->x, 0 );
    field_set_ui( a->y, 1 );
    field_set_ui( a->z, 1 );
    field_set_ui( a->t, 0 );
    field_set_ui( a->u, 0 );
Michael Hamburg's avatar
Michael Hamburg committed
961 962
}

963 964 965 966 967 968 969 970 971 972
void
set_identity_tw_extended (
    tw_extended_a_t a
) {
    field_set_ui( a->x, 0 );
    field_set_ui( a->y, 1 );
    field_set_ui( a->z, 1 );
    field_set_ui( a->t, 0 );
}

Michael Hamburg's avatar
Michael Hamburg committed
973 974
void
set_identity_tw_extensible (
975
    tw_extensible_a_t a
Michael Hamburg's avatar
Michael Hamburg committed
976
) {
Michael Hamburg's avatar
Michael Hamburg committed
977 978 979 980 981
    field_set_ui( a->x, 0 );
    field_set_ui( a->y, 1 );
    field_set_ui( a->z, 1 );
    field_set_ui( a->t, 0 );
    field_set_ui( a->u, 0 );
Michael Hamburg's avatar
Michael Hamburg committed
982 983 984 985
}

void
set_identity_affine (
986
    affine_a_t a
Michael Hamburg's avatar
Michael Hamburg committed
987
) {
Michael Hamburg's avatar
Michael Hamburg committed
988 989
    field_set_ui( a->x, 0 );
    field_set_ui( a->y, 1 );
Michael Hamburg's avatar
Michael Hamburg committed
990 991
}

992 993 994 995 996
mask_t
decaf_eq_extensible (
    const struct extensible_t* a,
    const struct extensible_t* b
) {
997 998
    field_a_t L0, L1;
    field_mul ( L0, b->y, a->x );
Michael Hamburg's avatar
Michael Hamburg committed
999
    field_mul ( L1, a->y, b->x );
1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011
    return field_eq(L0,L1);
}

mask_t
decaf_eq_tw_extended (
    const tw_extended_a_t a,
    const tw_extended_a_t b
) {
    field_a_t L0, L1;
    field_mul ( L0, b->y, a->x );
    field_mul ( L1, a->y, b->x );
    return field_eq(L0,L1);
1012 1013 1014 1015 1016 1017 1018
}

mask_t
decaf_eq_tw_extensible (
    const struct tw_extensible_t* a,
    const struct tw_extensible_t* b
) {
1019
    field_a_t L0, L1, L2;
Michael Hamburg's avatar
Michael Hamburg committed
1020 1021 1022 1023
    field_mul ( L2, b->y, a->x );
    field_mul ( L1, a->y, b->x );
    field_sub ( L0, L2, L1 );
    field_bias ( L0, 2 );
1024
    return field_is_zero ( L0 );
1025 1026
}

Michael Hamburg's avatar
Michael Hamburg committed
1027 1028
mask_t
eq_affine (
1029 1030
    const affine_a_t a,
    const affine_a_t b
Michael Hamburg's avatar
Michael Hamburg committed
1031
) {
1032
    mask_t L1, L2;
1033
    field_a_t L0;
Michael Hamburg's avatar
Michael Hamburg committed
1034 1035 1036 1037
    field_sub ( L0, a->x, b->x );
    L2 = field_is_zero( L0 );
    field_sub ( L0, a->y, b->y );
    L1 = field_is_zero( L0 );
1038
    return    L2 &    L1;
Michael Hamburg's avatar
Michael Hamburg committed
1039 1040 1041 1042
}

mask_t
eq_extensible (
1043 1044
    const extensible_a_t a,
    const extensible_a_t b
Michael Hamburg's avatar
Michael Hamburg committed
1045
) {
1046
    mask_t L3, L4;
1047
    field_a_t L0, L1, L2;
Michael Hamburg's avatar
Michael Hamburg committed
1048 1049 1050 1051 1052 1053 1054 1055
    field_mul ( L2, b->z, a->x );
    field_mul ( L1, a->z, b->x );
    field_sub ( L0, L2, L1 );
    L4 = field_is_zero( L0 );
    field_mul ( L2, b->z, a->y );
    field_mul ( L1, a->z, b->y );
    field_sub ( L0, L2, L1 );
    L3 = field_is_zero( L0 );
1056
    return    L4 &    L3;
Michael Hamburg's avatar
Michael Hamburg committed
1057 1058 1059 1060
}

mask_t
eq_tw_extensible (
1061 1062
    const tw_extensible_a_t a,
    const tw_extensible_a_t b
Michael Hamburg's avatar
Michael Hamburg committed
1063
) {
1064
    mask_t L3, L4;
1065
    field_a_t L0, L1, L2;
Michael Hamburg's avatar
Michael Hamburg committed
1066 1067 1068 1069 1070 1071 1072 1073
    field_mul ( L2, b->z, a->x );
    field_mul ( L1, a->z, b->x );
    field_sub ( L0, L2, L1 );
    L4 = field_is_zero( L0 );
    field_mul ( L2, b->z, a->y );
    field_mul ( L1, a->z, b->y );
    field_sub ( L0, L2, L1 );
    L3 = field_is_zero( L0 );
1074
    return    L4 &    L3;
Michael Hamburg's avatar
Michael Hamburg committed
1075 1076 1077 1078
}

void
elligator_2s_inject (
1079
    affine_a_t     a,
1080 1081 1082
    const field_a_t r
) {
    field_a_t L2, L3, L4, L5, L6, L7, L8;
Michael Hamburg's avatar
Michael Hamburg committed
1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095
    field_sqr ( a->x, r );
    field_sqr ( L3, a->x );
    field_copy ( a->y, L3 );
    field_neg ( L4, a->y );
    field_addw ( L4, 1 );
    field_sqr ( L2, L4 );
    field_mulw ( L7, L2, (EDWARDS_D-1)*(EDWARDS_D-1) );
    field_mulw ( L8, L3, 4*(EDWARDS_D+1)*(EDWARDS_D+1) );
    field_add ( a->y, L8, L7 );
    field_mulw ( L8, L2, 4*(EDWARDS_D)*(EDWARDS_D-1) );
    field_sub ( L7, a->y, L8 );
    field_mulw_scc ( L6, a->y, -2-2*EDWARDS_D );
    field_mul ( L5, L7, L6 );
1096
        /* FIXME Stability problem (API stability, not crash) / possible bug.
Michael Hamburg's avatar
Michael Hamburg committed
1097
         * change to: p448_mul ( L5, L7, L4 ); ?
1098 1099 1100 1101 1102 1103 1104 1105 1106 1107
         * This isn't a deep change: it's for sign adjustment.
         * Need to check which one leads to the correct sign, probably by writig
         * the invert routine.
         *
         * Also, the tool doesn't produce the optimal route to this.
         * Let incoming L6 = a, L7 = e, L4 = b.
         *
         * Could compute be, (be)^2, (be)^3, a b^3 e^3, a b^3 e^4. = 4M+S
         * instead of 6M.
         */
Michael Hamburg's avatar
Michael Hamburg committed
1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133
    field_mul ( L8, L5, L4 );
    field_mul ( L4, L5, L6 );
    field_mul ( L5, L7, L8 );
    field_mul ( L8, L5, L4 );
    field_mul ( L4, L7, L8 );
    field_isr ( L6, L4 );
    field_mul ( L4, L5, L6 );
    field_sqr ( L5, L6 );
    field_mul ( L6, L8, L5 );
    field_mul ( L8, L7, L6 );
    field_mul ( L7, L8, L6 );
    field_copy ( L6, a->x );
    field_addw ( a->x, 1 );
    field_mul ( L5, a->x, L8 );
    field_addw ( L5, 1 );
    field_sub ( a->x, L6, L5 );
    field_mul ( L5, L4, a->x );
    field_mulw_scc_wr ( a->x, L5, -2-2*EDWARDS_D );
    field_add ( L4, L3, L3 );
    field_add ( L3, L4, L2 );
    field_subw( L3, 2 );
    field_mul ( L2, L3, L8 );
    field_mulw ( L3, L2, 2*(EDWARDS_D+1)*(EDWARDS_D-1) );
    field_add ( L2, L3, a->y );
    field_mul ( a->y, L7, L2 );
    field_addw ( a->y, -field_is_zero( L8 ) );
Michael Hamburg's avatar
Michael Hamburg committed
1134 1135 1136 1137
}

mask_t
validate_affine (
1138
    const affine_a_t a
Michael Hamburg's avatar
Michael Hamburg committed
1139
) {
1140
    field_a_t L0, L1, L2, L3;
Michael Hamburg's avatar
Michael Hamburg committed
1141 1142 1143 1144 1145 1146 1147 1148
    field_sqr ( L0, a->y );
    field_sqr ( L1, a->x );
    field_add ( L3, L1, L0 );
    field_mulw_scc ( L2, L1, EDWARDS_D );
    field_mul ( L1, L0, L2 );
    field_addw ( L1, 1 );
    field_sub ( L0, L3, L1 );
    return field_is_zero( L0 );
Michael Hamburg's avatar
Michael Hamburg committed
1149 1150 1151 1152
}

mask_t
validate_tw_extensible (
1153
    const tw_extensible_a_t ext
Michael Hamburg's avatar
Michael Hamburg committed
1154
) {
1155
    mask_t L4, L5;
1156
    field_a_t L0, L1, L2, L3;
Michael Hamburg's avatar
Michael Hamburg committed
1157 1158 1159 1160
    /*
     * Check invariant:
     * 0 = -x*y + z*t*u
     */
Michael Hamburg's avatar
Michael Hamburg committed
1161 1162 1163 1164 1165 1166
    field_mul ( L1, ext->t, ext->u );
    field_mul ( L2, ext->z, L1 );
    field_mul ( L0, ext->x, ext->y );
    field_neg ( L1, L0 );
    field_add ( L0, L1, L2 );
    L5 = field_is_zero( L0 );
Michael Hamburg's avatar
Michael Hamburg committed
1167 1168 1169 1170
    /*
     * Check invariant:
     * 0 = d*t^2*u^2 + x^2 - y^2 + z^2 - t^2*u^2
     */
Michael Hamburg's avatar
Michael Hamburg committed
1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184
    field_sqr ( L2, ext->y );
    field_neg ( L1, L2 );
    field_sqr ( L0, ext->x );
    field_add ( L2, L0, L1 );
    field_sqr ( L3, ext->u );
    field_sqr ( L0, ext->t );
    field_mul ( L1, L0, L3 );
    field_mulw_scc ( L3, L1, EDWARDS_D );
    field_add ( L0, L3, L2 );
    field_neg ( L3, L1 );
    field_add ( L2, L3, L0 );
    field_sqr ( L1, ext->z );
    field_add ( L0, L1, L2 );
    L4 = field_is_zero( L0 );
1185
    return    L5 & L4 &~ field_is_zero(ext->z);
Michael Hamburg's avatar
Michael Hamburg committed
1186 1187 1188 1189
}

mask_t
validate_extensible (
1190
    const extensible_a_t ext
Michael Hamburg's avatar
Michael Hamburg committed
1191
) {
1192
    mask_t L4, L5;
1193
    field_a_t L0, L1, L2, L3;
Michael Hamburg's avatar
Michael Hamburg committed
1194 1195 1196 1197
    /*
     * Check invariant:
     * 0 = d*t^2*u^2 - x^2 - y^2 + z^2
     */
Michael Hamburg's avatar
Michael Hamburg committed
1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210
    field_sqr ( L2, ext->y );
    field_neg ( L1, L2 );
    field_sqr ( L0, ext->z );
    field_add ( L2, L0, L1 );
    field_sqr ( L3, ext->u );
    field_sqr ( L0, ext->t );
    field_mul ( L1, L0, L3 );
    field_mulw_scc ( L0, L1, EDWARDS_D );
    field_add ( L1, L0, L2 );
    field_sqr ( L0, ext->x );
    field_neg ( L2, L0 );
    field_add ( L0, L2, L1 );
    L5 = field_is_zero( L0 );
Michael Hamburg's avatar
Michael Hamburg committed
1211 1212 1213 1214
    /*
     * Check invariant:
     * 0 = -x*y + z*t*u
     */
Michael Hamburg's avatar
Michael Hamburg committed
1215 1216 1217 1218 1219 1220
    field_mul ( L1, ext->t, ext->u );
    field_mul ( L2, ext->z, L1 );
    field_mul ( L0, ext->x, ext->y );
    field_neg ( L1, L0 );
    field_add ( L0, L1, L2 );
    L4 = field_is_zero( L0 );
1221
    return L5 & L4 &~ field_is_zero(ext->z);
Michael Hamburg's avatar
Michael Hamburg committed
1222
}