ge_scalarmult_base.c (2617B)
1 #include "ge.h" 2 #include "crypto_uint32.h" 3 4 /* Rename this so as not to interfere with select() which torint.h apparently 5 * grabs. :p */ 6 #define select ed25519_ref10_select 7 8 static unsigned char equal(signed char b,signed char c) 9 { 10 unsigned char ub = b; 11 unsigned char uc = c; 12 unsigned char x = ub ^ uc; /* 0: yes; 1..255: no */ 13 crypto_uint32 y = x; /* 0: yes; 1..255: no */ 14 y -= 1; /* 4294967295: yes; 0..254: no */ 15 y >>= 31; /* 1: yes; 0: no */ 16 return y; 17 } 18 19 static unsigned char negative(signed char b) 20 { 21 uint64_t x = b; /* 18446744073709551361..18446744073709551615: yes; 0..255: no */ 22 x >>= 63; /* 1: yes; 0: no */ 23 return x; 24 } 25 26 static void cmov(ge_precomp *t,ge_precomp *u,unsigned char b) 27 { 28 fe_cmov(t->yplusx,u->yplusx,b); 29 fe_cmov(t->yminusx,u->yminusx,b); 30 fe_cmov(t->xy2d,u->xy2d,b); 31 } 32 33 /* base[i][j] = (j+1)*256^i*B */ 34 static ge_precomp base[32][8] = { 35 #include "base.h" 36 } ; 37 38 static void select(ge_precomp *t,int pos,signed char b) 39 { 40 ge_precomp minust; 41 unsigned char bnegative = negative(b); 42 unsigned char babs = b - SHL8( (-bnegative) & (unsigned char)b, 1); 43 44 ge_precomp_0(t); 45 cmov(t,&base[pos][0],equal(babs,1)); 46 cmov(t,&base[pos][1],equal(babs,2)); 47 cmov(t,&base[pos][2],equal(babs,3)); 48 cmov(t,&base[pos][3],equal(babs,4)); 49 cmov(t,&base[pos][4],equal(babs,5)); 50 cmov(t,&base[pos][5],equal(babs,6)); 51 cmov(t,&base[pos][6],equal(babs,7)); 52 cmov(t,&base[pos][7],equal(babs,8)); 53 fe_copy(minust.yplusx,t->yminusx); 54 fe_copy(minust.yminusx,t->yplusx); 55 fe_neg(minust.xy2d,t->xy2d); 56 cmov(t,&minust,bnegative); 57 } 58 59 /* 60 h = a * B 61 where a = a[0]+256*a[1]+...+256^31 a[31] 62 B is the Ed25519 base point (x,4/5) with x positive. 63 64 Preconditions: 65 a[31] <= 127 66 */ 67 68 void ge_scalarmult_base(ge_p3 *h,const unsigned char *a) 69 { 70 signed char e[64]; 71 signed char carry; 72 ge_p1p1 r; 73 ge_p2 s; 74 ge_precomp t; 75 int i; 76 77 for (i = 0;i < 32;++i) { 78 e[2 * i + 0] = (a[i] >> 0) & 15; 79 e[2 * i + 1] = (a[i] >> 4) & 15; 80 } 81 /* each e[i] is between 0 and 15 */ 82 /* e[63] is between 0 and 7 */ 83 84 carry = 0; 85 for (i = 0;i < 63;++i) { 86 e[i] += carry; 87 carry = e[i] + 8; 88 carry >>= 4; 89 e[i] -= SHL8(carry,4); 90 } 91 e[63] += carry; 92 /* each e[i] is between -8 and 8 */ 93 94 ge_p3_0(h); 95 for (i = 1;i < 64;i += 2) { 96 select(&t,i / 2,e[i]); 97 ge_madd(&r,h,&t); ge_p1p1_to_p3(h,&r); 98 } 99 100 ge_p3_dbl(&r,h); ge_p1p1_to_p2(&s,&r); 101 ge_p2_dbl(&r,&s); ge_p1p1_to_p2(&s,&r); 102 ge_p2_dbl(&r,&s); ge_p1p1_to_p2(&s,&r); 103 ge_p2_dbl(&r,&s); ge_p1p1_to_p3(h,&r); 104 105 for (i = 0;i < 64;i += 2) { 106 select(&t,i / 2,e[i]); 107 ge_madd(&r,h,&t); ge_p1p1_to_p3(h,&r); 108 } 109 }