ge_scalarmult_base.c 2.6 KB

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