#include "ge.h" /* r = p + q */ void ge_add(ge_p1p1 *r,const ge_p3 *p,const ge_cached *q) { fe t0; #include "ge_add.h" } static void slide(signed char *r,const unsigned char *a) { int i; int b; int k; for (i = 0;i < 256;++i) r[i] = 1 & (a[i >> 3] >> (i & 7)); for (i = 0;i < 256;++i) if (r[i]) { for (b = 1;b <= 6 && i + b < 256;++b) { if (r[i + b]) { if (r[i] + (r[i + b] << b) <= 15) { r[i] += r[i + b] << b; r[i + b] = 0; } else if (r[i] - (r[i + b] << b) >= -15) { r[i] -= r[i + b] << b; for (k = i + b;k < 256;++k) { if (!r[k]) { r[k] = 1; break; } r[k] = 0; } } else break; } } } } static ge_precomp Bi[8] = { #include "base2.h" } ; /* r = a * A + b * B where a = a[0]+256*a[1]+...+256^31 a[31]. and b = b[0]+256*b[1]+...+256^31 b[31]. B is the Ed25519 base point (x,4/5) with x positive. */ void ge_double_scalarmult_vartime(ge_p2 *r,const unsigned char *a,const ge_p3 *A,const unsigned char *b) { signed char aslide[256]; signed char bslide[256]; ge_cached Ai[8]; /* A,3A,5A,7A,9A,11A,13A,15A */ ge_p1p1 t; ge_p3 u; ge_p3 A2; int i; slide(aslide,a); slide(bslide,b); ge_p3_to_cached(&Ai[0],A); ge_p3_dbl(&t,A); ge_p1p1_to_p3(&A2,&t); ge_add(&t,&A2,&Ai[0]); ge_p1p1_to_p3(&u,&t); ge_p3_to_cached(&Ai[1],&u); ge_add(&t,&A2,&Ai[1]); ge_p1p1_to_p3(&u,&t); ge_p3_to_cached(&Ai[2],&u); ge_add(&t,&A2,&Ai[2]); ge_p1p1_to_p3(&u,&t); ge_p3_to_cached(&Ai[3],&u); ge_add(&t,&A2,&Ai[3]); ge_p1p1_to_p3(&u,&t); ge_p3_to_cached(&Ai[4],&u); ge_add(&t,&A2,&Ai[4]); ge_p1p1_to_p3(&u,&t); ge_p3_to_cached(&Ai[5],&u); ge_add(&t,&A2,&Ai[5]); ge_p1p1_to_p3(&u,&t); ge_p3_to_cached(&Ai[6],&u); ge_add(&t,&A2,&Ai[6]); ge_p1p1_to_p3(&u,&t); ge_p3_to_cached(&Ai[7],&u); ge_p2_0(r); for (i = 255;i >= 0;--i) { if (aslide[i] || bslide[i]) break; } for (;i >= 0;--i) { ge_p2_dbl(&t,r); if (aslide[i] > 0) { ge_p1p1_to_p3(&u,&t); ge_add(&t,&u,&Ai[aslide[i]/2]); } else if (aslide[i] < 0) { ge_p1p1_to_p3(&u,&t); ge_sub(&t,&u,&Ai[(-aslide[i])/2]); } if (bslide[i] > 0) { ge_p1p1_to_p3(&u,&t); ge_madd(&t,&u,&Bi[bslide[i]/2]); } else if (bslide[i] < 0) { ge_p1p1_to_p3(&u,&t); ge_msub(&t,&u,&Bi[(-bslide[i])/2]); } ge_p1p1_to_p2(r,&t); } } static const fe d = { #include "d.h" } ; static const fe sqrtm1 = { #include "sqrtm1.h" } ; int ge_frombytes_negate_vartime(ge_p3 *h,const unsigned char *s) { fe u; fe v; fe v3; fe vxx; fe check; fe_frombytes(h->Y,s); fe_1(h->Z); fe_sq(u,h->Y); fe_mul(v,u,d); fe_sub(u,u,h->Z); /* u = y^2-1 */ fe_add(v,v,h->Z); /* v = dy^2+1 */ fe_sq(v3,v); fe_mul(v3,v3,v); /* v3 = v^3 */ fe_sq(h->X,v3); fe_mul(h->X,h->X,v); fe_mul(h->X,h->X,u); /* x = uv^7 */ fe_pow22523(h->X,h->X); /* x = (uv^7)^((q-5)/8) */ fe_mul(h->X,h->X,v3); fe_mul(h->X,h->X,u); /* x = uv^3(uv^7)^((q-5)/8) */ fe_sq(vxx,h->X); fe_mul(vxx,vxx,v); fe_sub(check,vxx,u); /* vx^2-u */ if (fe_isnonzero(check)) { fe_add(check,vxx,u); /* vx^2+u */ if (fe_isnonzero(check)) return -1; fe_mul(h->X,h->X,sqrtm1); } if (fe_isnegative(h->X) == (s[31] >> 7)) fe_neg(h->X,h->X); fe_mul(h->T,h->X,h->Y); return 0; } /* r = p + q */ void ge_madd(ge_p1p1 *r,const ge_p3 *p,const ge_precomp *q) { fe t0; #include "ge_madd.h" } /* r = p - q */ void ge_msub(ge_p1p1 *r,const ge_p3 *p,const ge_precomp *q) { fe t0; #include "ge_msub.h" } /* r = p */ extern void ge_p1p1_to_p2(ge_p2 *r,const ge_p1p1 *p) { fe_mul(r->X,p->X,p->T); fe_mul(r->Y,p->Y,p->Z); fe_mul(r->Z,p->Z,p->T); } /* r = p */ extern void ge_p1p1_to_p3(ge_p3 *r,const ge_p1p1 *p) { fe_mul(r->X,p->X,p->T); fe_mul(r->Y,p->Y,p->Z); fe_mul(r->Z,p->Z,p->T); fe_mul(r->T,p->X,p->Y); } void ge_p2_0(ge_p2 *h) { fe_0(h->X); fe_1(h->Y); fe_1(h->Z); } /* r = 2 * p */ void ge_p2_dbl(ge_p1p1 *r,const ge_p2 *p) { fe t0; #include "ge_p2_dbl.h" } void ge_p3_0(ge_p3 *h) { fe_0(h->X); fe_1(h->Y); fe_1(h->Z); fe_0(h->T); } /* r = 2 * p */ void ge_p3_dbl(ge_p1p1 *r,const ge_p3 *p) { ge_p2 q; ge_p3_to_p2(&q,p); ge_p2_dbl(r,&q); } /* r = p */ static const fe d2 = { #include "d2.h" } ; extern void ge_p3_to_cached(ge_cached *r,const ge_p3 *p) { fe_add(r->YplusX,p->Y,p->X); fe_sub(r->YminusX,p->Y,p->X); fe_copy(r->Z,p->Z); fe_mul(r->T2d,p->T,d2); } /* r = p */ extern void ge_p3_to_p2(ge_p2 *r,const ge_p3 *p) { fe_copy(r->X,p->X); fe_copy(r->Y,p->Y); fe_copy(r->Z,p->Z); } void ge_p3_tobytes(unsigned char *s,const ge_p3 *h) { fe recip; fe x; fe y; fe_invert(recip,h->Z); fe_mul(x,h->X,recip); fe_mul(y,h->Y,recip); fe_tobytes(s,y); s[31] ^= fe_isnegative(x) << 7; } void ge_precomp_0(ge_precomp *h) { fe_1(h->yplusx); fe_1(h->yminusx); fe_0(h->xy2d); } static uint8_t equal(int8_t b,int8_t c) { uint8_t ub = b; uint8_t uc = c; uint8_t x = ub ^ uc; /* 0: yes; 1..255: no */ uint32_t y = x; /* 0: yes; 1..255: no */ y -= 1; /* 4294967295: yes; 0..254: no */ y >>= 31; /* 1: yes; 0: no */ return y; } static uint8_t negative(int8_t b) { unsigned long long x = b; /* 18446744073709551361..18446744073709551615: yes; 0..255: no */ x >>= 63; /* 1: yes; 0: no */ return x; } static void cmov(ge_precomp *t,ge_precomp *u,int8_t b) { fe_cmov(t->yplusx,u->yplusx,b); fe_cmov(t->yminusx,u->yminusx,b); fe_cmov(t->xy2d,u->xy2d,b); } /* base[i][j] = (j+1)*256^i*B */ static ge_precomp base[32][8] = { #include "base.h" } ; static void select(ge_precomp *t,int pos,int8_t b) { ge_precomp minust; uint8_t bnegative = negative(b); uint8_t babs = b - (((-bnegative) & b) << 1); ge_precomp_0(t); cmov(t,&base[pos][0],equal(babs,1)); cmov(t,&base[pos][1],equal(babs,2)); cmov(t,&base[pos][2],equal(babs,3)); cmov(t,&base[pos][3],equal(babs,4)); cmov(t,&base[pos][4],equal(babs,5)); cmov(t,&base[pos][5],equal(babs,6)); cmov(t,&base[pos][6],equal(babs,7)); cmov(t,&base[pos][7],equal(babs,8)); fe_copy(minust.yplusx,t->yminusx); fe_copy(minust.yminusx,t->yplusx); fe_neg(minust.xy2d,t->xy2d); cmov(t,&minust,bnegative); } /* h = a * B where a = a[0]+256*a[1]+...+256^31 a[31] B is the Ed25519 base point (x,4/5) with x positive. Preconditions: a[31] <= 127 */ void ge_scalarmult_base(ge_p3 *h,const uint8_t *a) { int8_t e[64]; int8_t carry; ge_p1p1 r; ge_p2 s; ge_precomp t; int i; for (i = 0;i < 32;++i) { e[2 * i + 0] = (a[i] >> 0) & 15; e[2 * i + 1] = (a[i] >> 4) & 15; } /* each e[i] is between 0 and 15 */ /* e[63] is between 0 and 7 */ carry = 0; for (i = 0;i < 63;++i) { e[i] += carry; carry = e[i] + 8; carry >>= 4; e[i] -= carry << 4; } e[63] += carry; /* each e[i] is between -8 and 8 */ ge_p3_0(h); for (i = 1;i < 64;i += 2) { select(&t,i / 2,e[i]); ge_madd(&r,h,&t); ge_p1p1_to_p3(h,&r); } ge_p3_dbl(&r,h); ge_p1p1_to_p2(&s,&r); ge_p2_dbl(&r,&s); ge_p1p1_to_p2(&s,&r); ge_p2_dbl(&r,&s); ge_p1p1_to_p2(&s,&r); ge_p2_dbl(&r,&s); ge_p1p1_to_p3(h,&r); for (i = 0;i < 64;i += 2) { select(&t,i / 2,e[i]); ge_madd(&r,h,&t); ge_p1p1_to_p3(h,&r); } } /* r = p - q */ void ge_sub(ge_p1p1 *r,const ge_p3 *p,const ge_cached *q) { fe t0; #include "ge_sub.h" } void ge_tobytes(unsigned char *s,const ge_p2 *h) { fe recip; fe x; fe y; fe_invert(recip,h->Z); fe_mul(x,h->X,recip); fe_mul(y,h->Y,recip); fe_tobytes(s,y); s[31] ^= fe_isnegative(x) << 7; }