curvepoint_fp_multiscalar.c 1.7 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364
  1. /*
  2. * File: dclxvi-20130329/curvepoint_fp_multiscalar.c
  3. * Author: Ruben Niederhagen, Peter Schwabe
  4. * Public Domain
  5. */
  6. #include "curvepoint_fp.h"
  7. #include "scalar.h"
  8. #include "index_heap.h"
  9. #define MAX_HEAP_SIZE 63 // Can also try 127 or 255
  10. void curvepoint_fp_multiscalarmult_vartime(curvepoint_fp_t rop, struct curvepoint_fp_struct *p, scalar_t *s, const unsigned long long npoints)
  11. {
  12. unsigned long long pos[MAX_HEAP_SIZE];
  13. unsigned long long max1, max2,i;
  14. curvepoint_fp_t t;
  15. unsigned long long tctr, ctr = npoints;
  16. curvepoint_fp_setneutral(rop);
  17. while(ctr>=MAX_HEAP_SIZE)
  18. {
  19. heap_init(pos, MAX_HEAP_SIZE, s);
  20. for(i=0;;i++)
  21. {
  22. heap_get2max(pos, &max1, &max2, s);
  23. if(scalar_iszero_vartime(s[max2])) break;
  24. scalar_sub_nored(s[max1],s[max1],s[max2]);
  25. curvepoint_fp_add_vartime(&p[max2],&p[max2],&p[max1]);
  26. heap_rootreplaced(pos, MAX_HEAP_SIZE, s);
  27. }
  28. curvepoint_fp_scalarmult_vartime(t, &p[max1], s[max1]);
  29. curvepoint_fp_add_vartime(rop,rop,t);
  30. p += MAX_HEAP_SIZE;
  31. s += MAX_HEAP_SIZE;
  32. ctr -= MAX_HEAP_SIZE;
  33. }
  34. if(ctr > 5)
  35. {
  36. tctr = (ctr-1)|1; // need an odd heap size
  37. heap_init(pos, tctr, s);
  38. for(i=0;;i++)
  39. {
  40. heap_get2max(pos, &max1, &max2, s);
  41. if(scalar_iszero_vartime(s[max2])) break;
  42. scalar_sub_nored(s[max1],s[max1],s[max2]);
  43. curvepoint_fp_add_vartime(&p[max2],&p[max2],&p[max1]);
  44. heap_rootreplaced(pos, tctr, s);
  45. }
  46. curvepoint_fp_scalarmult_vartime(t, &p[max1], s[max1]);
  47. curvepoint_fp_add_vartime(rop,rop,t);
  48. p += tctr;
  49. s += tctr;
  50. ctr -= tctr;
  51. }
  52. while(ctr>0)
  53. {
  54. curvepoint_fp_scalarmult_vartime(t,p,*s);
  55. curvepoint_fp_add_vartime(rop,rop,t);
  56. p++;
  57. s++;
  58. ctr--;
  59. }
  60. }