"Fossies" - the Fresh Open Source Software Archive

Member "tor-0.4.1.6/src/ext/ed25519/donna/ed25519-donna-impl-sse2.h" (10 Jun 2019, 11815 Bytes) of package /linux/misc/tor-0.4.1.6.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file.

    1 /*
    2     conversions
    3 */
    4 
    5 static void
    6 ge25519_p1p1_to_partial(ge25519 *r, const ge25519_p1p1 *p) {
    7     packed64bignum25519 ALIGN(16) xz, tt, xzout;
    8     curve25519_mul(r->y, p->y, p->z);
    9     curve25519_tangle64(xz, p->x, p->z);
   10     curve25519_tangleone64(tt, p->t);
   11     curve25519_mul_packed64(xzout, xz, tt);
   12     curve25519_untangle64(r->x, r->z, xzout);
   13 }
   14 
   15 static void 
   16 ge25519_p1p1_to_full(ge25519 *r, const ge25519_p1p1 *p) {
   17     packed64bignum25519 ALIGN(16) zy, xt, xx, zz, ty;
   18     curve25519_tangle64(ty, p->t, p->y);
   19     curve25519_tangleone64(xx, p->x);
   20     curve25519_mul_packed64(xt, xx, ty);
   21     curve25519_untangle64(r->x, r->t, xt);
   22     curve25519_tangleone64(zz, p->z);
   23     curve25519_mul_packed64(zy, zz, ty);
   24     curve25519_untangle64(r->z, r->y, zy);
   25 }
   26 
   27 static void
   28 ge25519_full_to_pniels(ge25519_pniels *p, const ge25519 *r) {
   29     curve25519_sub(p->ysubx, r->y, r->x);
   30     curve25519_add(p->xaddy, r->x, r->y);
   31     curve25519_copy(p->z, r->z);
   32     curve25519_mul(p->t2d, r->t, ge25519_ec2d);
   33 }
   34 
   35 /*
   36     adding & doubling
   37 */
   38 
   39 static void
   40 ge25519_add_p1p1(ge25519_p1p1 *r, const ge25519 *p, const ge25519 *q) {
   41     bignum25519 ALIGN(16) a,b,c,d;
   42     packed32bignum25519 ALIGN(16) xx, yy, yypxx, yymxx, bd, ac, bdmac, bdpac;
   43     packed64bignum25519 ALIGN(16) at, bu, atbu, ptz, qtz, cd;
   44 
   45     curve25519_tangle32(yy, p->y, q->y);
   46     curve25519_tangle32(xx, p->x, q->x);
   47     curve25519_add_packed32(yypxx, yy, xx);
   48     curve25519_sub_packed32(yymxx, yy, xx);
   49     curve25519_tangle64_from32(at, bu, yymxx, yypxx);
   50     curve25519_mul_packed64(atbu, at, bu);
   51     curve25519_untangle64(a, b, atbu);
   52     curve25519_tangle64(ptz, p->t, p->z);
   53     curve25519_tangle64(qtz, q->t, q->z);
   54     curve25519_mul_packed64(cd, ptz, qtz);
   55     curve25519_untangle64(c, d, cd);
   56     curve25519_mul(c, c, ge25519_ec2d);
   57     curve25519_add_reduce(d, d, d);
   58     /* reduce, so no after_basic is needed later */
   59     curve25519_tangle32(bd, b, d);
   60     curve25519_tangle32(ac, a, c);
   61     curve25519_sub_packed32(bdmac, bd, ac);
   62     curve25519_add_packed32(bdpac, bd, ac);
   63     curve25519_untangle32(r->x, r->t, bdmac);
   64     curve25519_untangle32(r->y, r->z, bdpac);
   65 }
   66 
   67 
   68 static void
   69 ge25519_double_p1p1(ge25519_p1p1 *r, const ge25519 *p) {
   70     bignum25519 ALIGN(16) a,b,c,x;
   71     packed64bignum25519 ALIGN(16) xy, zx, ab, cx;
   72     packed32bignum25519 ALIGN(16) xc, yz, xt, yc, ac, bc;
   73 
   74     curve25519_add(x, p->x, p->y);
   75     curve25519_tangle64(xy, p->x, p->y);
   76     curve25519_square_packed64(ab, xy);
   77     curve25519_untangle64(a, b, ab);
   78     curve25519_tangle64(zx, p->z, x);
   79     curve25519_square_packed64(cx, zx);
   80     curve25519_untangle64(c, x, cx);
   81     curve25519_tangle32(bc, b, c);
   82     curve25519_tangle32(ac, a, c);
   83     curve25519_add_reduce_packed32(yc, bc, ac);
   84     curve25519_untangle32(r->y, c, yc);
   85     curve25519_sub(r->z, b, a);
   86     curve25519_tangle32(yz, r->y, r->z);
   87     curve25519_tangle32(xc, x, c);
   88     curve25519_sub_after_basic_packed32(xt, xc, yz);
   89     curve25519_untangle32(r->x, r->t, xt);
   90 }
   91 
   92 static void
   93 ge25519_nielsadd2_p1p1(ge25519_p1p1 *r, const ge25519 *p, const ge25519_niels *q, unsigned char signbit) {
   94     const bignum25519 *qb = (const bignum25519 *)q;
   95     bignum25519 *rb = (bignum25519 *)r;
   96     bignum25519 ALIGN(16) a,b,c;
   97     packed64bignum25519 ALIGN(16) ab, yx, aybx;
   98     packed32bignum25519 ALIGN(16) bd, ac, bdac;
   99 
  100     curve25519_sub(a, p->y, p->x);
  101     curve25519_add(b, p->y, p->x);
  102     curve25519_tangle64(ab, a, b);
  103     curve25519_tangle64(yx, qb[signbit], qb[signbit^1]);
  104     curve25519_mul_packed64(aybx, ab, yx);
  105     curve25519_untangle64(a, b, aybx);
  106     curve25519_add(r->y, b, a);
  107     curve25519_add_reduce(r->t, p->z, p->z);
  108     curve25519_mul(c, p->t, q->t2d);
  109     curve25519_copy(r->z, r->t);
  110     curve25519_add(rb[2+signbit], rb[2+signbit], c);
  111     curve25519_tangle32(bd, b, rb[2+(signbit^1)]);
  112     curve25519_tangle32(ac, a, c);
  113     curve25519_sub_packed32(bdac, bd, ac);
  114     curve25519_untangle32(r->x, rb[2+(signbit^1)], bdac);
  115 }
  116 
  117 static void
  118 ge25519_pnielsadd_p1p1(ge25519_p1p1 *r, const ge25519 *p, const ge25519_pniels *q, unsigned char signbit) {
  119     const bignum25519 *qb = (const bignum25519 *)q;
  120     bignum25519 *rb = (bignum25519 *)r;
  121     bignum25519 ALIGN(16) a,b,c;
  122     packed64bignum25519 ALIGN(16) ab, yx, aybx, zt, zt2d, tc;
  123     packed32bignum25519 ALIGN(16) bd, ac, bdac;
  124 
  125     curve25519_sub(a, p->y, p->x);
  126     curve25519_add(b, p->y, p->x);
  127     curve25519_tangle64(ab, a, b);
  128     curve25519_tangle64(yx, qb[signbit], qb[signbit^1]);
  129     curve25519_mul_packed64(aybx, ab, yx);
  130     curve25519_untangle64(a, b, aybx);
  131     curve25519_add(r->y, b, a);
  132     curve25519_tangle64(zt, p->z, p->t);
  133     curve25519_tangle64(zt2d, q->z, q->t2d);
  134     curve25519_mul_packed64(tc, zt, zt2d);
  135     curve25519_untangle64(r->t, c, tc);
  136     curve25519_add_reduce(r->t, r->t, r->t);
  137     curve25519_copy(r->z, r->t);
  138     curve25519_add(rb[2+signbit], rb[2+signbit], c);
  139     curve25519_tangle32(bd, b, rb[2+(signbit^1)]);
  140     curve25519_tangle32(ac, a, c);
  141     curve25519_sub_packed32(bdac, bd, ac);
  142     curve25519_untangle32(r->x, rb[2+(signbit^1)], bdac);
  143 }
  144 
  145 static void
  146 ge25519_double(ge25519 *r, const ge25519 *p) {
  147     ge25519_p1p1 ALIGN(16) t;
  148     ge25519_double_p1p1(&t, p);
  149     ge25519_p1p1_to_full(r, &t);
  150 }
  151 
  152 static void
  153 ge25519_add(ge25519 *r, const ge25519 *p, const ge25519 *q) {
  154     ge25519_p1p1 ALIGN(16) t;
  155     ge25519_add_p1p1(&t, p, q);
  156     ge25519_p1p1_to_full(r, &t);
  157 }
  158 
  159 static void
  160 ge25519_double_partial(ge25519 *r, const ge25519 *p) {
  161     ge25519_p1p1 ALIGN(16) t;
  162     ge25519_double_p1p1(&t, p);
  163     ge25519_p1p1_to_partial(r, &t);
  164 }
  165 
  166 static void
  167 ge25519_nielsadd2(ge25519 *r, const ge25519_niels *q) {
  168     packed64bignum25519 ALIGN(16) ab, yx, aybx, eg, ff, hh, xz, ty;
  169     packed32bignum25519 ALIGN(16) bd, ac, bdac;
  170     bignum25519 ALIGN(16) a,b,c,d,e,f,g,h;
  171 
  172     curve25519_sub(a, r->y, r->x);
  173     curve25519_add(b, r->y, r->x);
  174     curve25519_tangle64(ab, a, b);
  175     curve25519_tangle64(yx, q->ysubx, q->xaddy);
  176     curve25519_mul_packed64(aybx, ab, yx);
  177     curve25519_untangle64(a, b, aybx);
  178     curve25519_add(h, b, a);
  179     curve25519_add_reduce(d, r->z, r->z);
  180     curve25519_mul(c, r->t, q->t2d);
  181     curve25519_add(g, d, c); /* d is reduced, so no need for after_basic */
  182     curve25519_tangle32(bd, b, d);
  183     curve25519_tangle32(ac, a, c);
  184     curve25519_sub_packed32(bdac, bd, ac); /* d is reduced, so no need for after_basic */
  185     curve25519_untangle32(e, f, bdac);
  186     curve25519_tangle64(eg, e, g);
  187     curve25519_tangleone64(ff, f);
  188     curve25519_mul_packed64(xz, eg, ff);
  189     curve25519_untangle64(r->x, r->z, xz);
  190     curve25519_tangleone64(hh, h);
  191     curve25519_mul_packed64(ty, eg, hh);
  192     curve25519_untangle64(r->t, r->y, ty);
  193 }
  194 
  195 static void
  196 ge25519_pnielsadd(ge25519_pniels *r, const ge25519 *p, const ge25519_pniels *q) {
  197     ge25519_p1p1 ALIGN(16) t;
  198     ge25519 ALIGN(16) f;
  199     ge25519_pnielsadd_p1p1(&t, p, q, 0);
  200     ge25519_p1p1_to_full(&f, &t);
  201     ge25519_full_to_pniels(r, &f);
  202 }
  203 
  204 /*
  205     pack & unpack
  206 */
  207 
  208 static void
  209 ge25519_pack(unsigned char r[32], const ge25519 *p) {
  210     bignum25519 ALIGN(16) tx, ty, zi;
  211     unsigned char parity[32];
  212     curve25519_recip(zi, p->z);
  213     curve25519_mul(tx, p->x, zi);
  214     curve25519_mul(ty, p->y, zi);
  215     curve25519_contract(r, ty);
  216     curve25519_contract(parity, tx);
  217     r[31] ^= ((parity[0] & 1) << 7);
  218 }
  219 
  220 
  221 static int
  222 ge25519_unpack_negative_vartime(ge25519 *r, const unsigned char p[32]) {
  223     static const bignum25519 ALIGN(16) one = {1};
  224     static const unsigned char zero[32] = {0};
  225     unsigned char parity = p[31] >> 7;
  226     unsigned char check[32];
  227     bignum25519 ALIGN(16) t, root, num, den, d3;
  228 
  229     curve25519_expand(r->y, p);
  230     curve25519_copy(r->z, one);
  231     curve25519_square_times(num, r->y, 1); /* x = y^2 */
  232     curve25519_mul(den, num, ge25519_ecd); /* den = dy^2 */
  233     curve25519_sub_reduce(num,  num, r->z); /* x = y^2 - 1 */
  234     curve25519_add(den, den, r->z); /* den = dy^2 + 1 */
  235 
  236     /* Computation of sqrt(num/den) */
  237     /* 1.: computation of num^((p-5)/8)*den^((7p-35)/8) = (num*den^7)^((p-5)/8) */
  238     curve25519_square_times(t, den, 1);
  239     curve25519_mul(d3, t, den);
  240     curve25519_square_times(r->x, d3, 1);
  241     curve25519_mul(r->x, r->x, den);
  242     curve25519_mul(r->x, r->x, num);
  243     curve25519_pow_two252m3(r->x, r->x);
  244 
  245     /* 2. computation of r->x = t * num * den^3 */
  246     curve25519_mul(r->x, r->x, d3);
  247     curve25519_mul(r->x, r->x, num);
  248 
  249     /* 3. Check if either of the roots works: */
  250     curve25519_square_times(t, r->x, 1);
  251     curve25519_mul(t, t, den);
  252     curve25519_copy(root, t);
  253     curve25519_sub_reduce(root,  root, num);
  254     curve25519_contract(check, root);
  255     if (!ed25519_verify(check, zero, 32)) {
  256         curve25519_add_reduce(t, t, num);
  257         curve25519_contract(check, t);
  258         if (!ed25519_verify(check, zero, 32))
  259             return 0;
  260         curve25519_mul(r->x, r->x, ge25519_sqrtneg1);
  261     }
  262 
  263     curve25519_contract(check, r->x);
  264     if ((check[0] & 1) == parity) {
  265         curve25519_copy(t, r->x);
  266         curve25519_neg(r->x, t);
  267     }
  268     curve25519_mul(r->t, r->x, r->y);
  269     return 1;
  270 }
  271 
  272 
  273 
  274 /*
  275     scalarmults
  276 */
  277 
  278 #define S1_SWINDOWSIZE 5
  279 #define S1_TABLE_SIZE (1<<(S1_SWINDOWSIZE-2))
  280 #define S2_SWINDOWSIZE 7
  281 #define S2_TABLE_SIZE (1<<(S2_SWINDOWSIZE-2))
  282 
  283 static void
  284 ge25519_double_scalarmult_vartime(ge25519 *r, const ge25519 *p1, const bignum256modm s1, const bignum256modm s2) {
  285     signed char slide1[256], slide2[256];
  286     ge25519_pniels ALIGN(16) pre1[S1_TABLE_SIZE];
  287     ge25519 ALIGN(16) d1;
  288     ge25519_p1p1 ALIGN(16) t;
  289     int32_t i;
  290 
  291     contract256_slidingwindow_modm(slide1, s1, S1_SWINDOWSIZE);
  292     contract256_slidingwindow_modm(slide2, s2, S2_SWINDOWSIZE);
  293 
  294     ge25519_double(&d1, p1);
  295     ge25519_full_to_pniels(pre1, p1);
  296     for (i = 0; i < S1_TABLE_SIZE - 1; i++)
  297         ge25519_pnielsadd(&pre1[i+1], &d1, &pre1[i]);
  298 
  299     /* set neutral */
  300     memset(r, 0, sizeof(ge25519));
  301     r->y[0] = 1;
  302     r->z[0] = 1;
  303 
  304     i = 255;
  305     while ((i >= 0) && !(slide1[i] | slide2[i]))
  306         i--;
  307 
  308     for (; i >= 0; i--) {
  309         ge25519_double_p1p1(&t, r);
  310 
  311         if (slide1[i]) {
  312             ge25519_p1p1_to_full(r, &t);
  313             ge25519_pnielsadd_p1p1(&t, r, &pre1[abs(slide1[i]) / 2], (unsigned char)slide1[i] >> 7);
  314         }
  315 
  316         if (slide2[i]) {
  317             ge25519_p1p1_to_full(r, &t);
  318             ge25519_nielsadd2_p1p1(&t, r, &ge25519_niels_sliding_multiples[abs(slide2[i]) / 2], (unsigned char)slide2[i] >> 7);
  319         }
  320 
  321         ge25519_p1p1_to_partial(r, &t);
  322     }
  323 }
  324 
  325 #if !defined(HAVE_GE25519_SCALARMULT_BASE_CHOOSE_NIELS)
  326 
  327 static uint32_t
  328 ge25519_windowb_equal(uint32_t b, uint32_t c) {
  329     return ((b ^ c) - 1) >> 31;
  330 }
  331 
  332 static void
  333 ge25519_scalarmult_base_choose_niels(ge25519_niels *t, const uint8_t table[256][96], uint32_t pos, signed char b) {
  334     bignum25519 ALIGN(16) neg;
  335     uint32_t sign = (uint32_t)((unsigned char)b >> 7);
  336     uint32_t mask = ~(sign - 1);
  337     uint32_t u = (b + mask) ^ mask;
  338     uint32_t i;
  339 
  340     /* ysubx, xaddy, t2d in packed form. initialize to ysubx = 1, xaddy = 1, t2d = 0 */
  341     uint8_t ALIGN(16) packed[96] = {0};
  342     packed[0] = 1;
  343     packed[32] = 1;
  344 
  345     for (i = 0; i < 8; i++)
  346         curve25519_move_conditional_bytes(packed, table[(pos * 8) + i], ge25519_windowb_equal(u, i + 1));
  347 
  348     /* expand in to t */
  349     curve25519_expand(t->ysubx, packed +  0);
  350     curve25519_expand(t->xaddy, packed + 32);
  351     curve25519_expand(t->t2d  , packed + 64);
  352 
  353     /* adjust for sign */
  354     curve25519_swap_conditional(t->ysubx, t->xaddy, sign);
  355     curve25519_neg(neg, t->t2d);
  356     curve25519_swap_conditional(t->t2d, neg, sign);
  357 }
  358 
  359 #endif /* HAVE_GE25519_SCALARMULT_BASE_CHOOSE_NIELS */
  360 
  361 static void
  362 ge25519_scalarmult_base_niels(ge25519 *r, const uint8_t table[256][96], const bignum256modm s) {
  363     signed char b[64];
  364     uint32_t i;
  365     ge25519_niels ALIGN(16) t;
  366 
  367     contract256_window4_modm(b, s);
  368 
  369     ge25519_scalarmult_base_choose_niels(&t, table, 0, b[1]);
  370     curve25519_sub_reduce(r->x, t.xaddy, t.ysubx);
  371     curve25519_add_reduce(r->y, t.xaddy, t.ysubx);
  372     memset(r->z, 0, sizeof(bignum25519)); 
  373     r->z[0] = 2;
  374     curve25519_copy(r->t, t.t2d);
  375     for (i = 3; i < 64; i += 2) {
  376         ge25519_scalarmult_base_choose_niels(&t, table, i / 2, b[i]);
  377         ge25519_nielsadd2(r, &t);
  378     }
  379     ge25519_double_partial(r, r);
  380     ge25519_double_partial(r, r);
  381     ge25519_double_partial(r, r);
  382     ge25519_double(r, r);
  383     ge25519_scalarmult_base_choose_niels(&t, table, 0, b[0]);
  384     curve25519_mul(t.t2d, t.t2d, ge25519_ecd);
  385     ge25519_nielsadd2(r, &t);
  386     for(i = 2; i < 64; i += 2) {
  387         ge25519_scalarmult_base_choose_niels(&t, table, i / 2, b[i]);
  388         ge25519_nielsadd2(r, &t);
  389     }
  390 }