kris
/
sike_ifma
1
0
포크 0
코드 이슈 0 풀 리퀘스트 0 릴리즈 0 위키 활동
25개 이상의 토픽을 선택하실 수 없습니다. Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
1 커밋
1 브렌치
116 KiB
 
 
 
브렌치: master
브랜치 태그
${ item.name }
${ searchTerm } 브랜치 생성
from 'master'
${ noResults }
sike_ifma/sidh_ref/fpx.c

474 lines
14 KiB
Raw 고유링크 Blame 히스토리 

  1. /********************************************************************************************

  2. * Supersingular Isogeny Key Encapsulation Library

  3. *

  4. * Abstract: core functions over GF(p) and GF(p^2)

  5. *********************************************************************************************/

  6. 

  7. #include "P751_internal.h"

  8. 

  9. __inline void fpcopy(const felm_t a, felm_t c)

  10. { // Copy a field element, c = a.

  11.     unsigned int i;

  12. 

  13.     for (i = 0; i < NWORDS_FIELD; i++)

  14.         c[i] = a[i];

  15. }

  16. 

  17. __inline void fpzero(felm_t a)

  18. { // Zero a field element, a = 0.

  19.     unsigned int i;

  20. 

  21.     for (i = 0; i < NWORDS_FIELD; i++)

  22.         a[i] = 0;

  23. }

  24. 

  25. void to_mont(const felm_t a, felm_t mc)

  26. {   // Conversion to Montgomery representation,

  27.     // mc = a*R^2*R^(-1) mod p = a*R mod p, where a in [0, p-1].

  28.     // The Montgomery constant R^2 mod p is the global value "Montgomery_R2".

  29. 

  30.     fpmul_mont(a, (digit_t *)&Montgomery_R2, mc);

  31. }

  32. 

  33. void from_mont(const felm_t ma, felm_t c)

  34. {   // Conversion from Montgomery representation to standard representation,

  35.     // c = ma*R^(-1) mod p = a mod p, where ma in [0, p-1].

  36.     digit_t one[NWORDS_FIELD] = {0};

  37. 

  38.     one[0] = 1;

  39.     fpmul_mont(ma, one, c);

  40.     fpcorrection(c);

  41. }

  42. 

  43. void copy_words(const digit_t *a, digit_t *c, const unsigned int nwords)

  44. { // Copy wordsize digits, c = a, where lng(a) = nwords.

  45.     unsigned int i;

  46. 

  47.     for (i = 0; i < nwords; i++)

  48.     {

  49.         c[i] = a[i];

  50.     }

  51. }

  52. 

  53. void fpmul_mont(const felm_t ma, const felm_t mb, felm_t mc)

  54. { // Multiprecision multiplication, c = a*b mod p.

  55.     dfelm_t temp = {0};

  56. 

  57.     mp_mul(ma, mb, temp, NWORDS_FIELD);

  58.     rdc_mont(temp, mc);

  59. }

  60. 

  61. void fpsqr_mont(const felm_t ma, felm_t mc)

  62. { // Multiprecision squaring, c = a^2 mod p.

  63.     dfelm_t temp = {0};

  64. 

  65.     mp_mul(ma, ma, temp, NWORDS_FIELD);

  66.     rdc_mont(temp, mc);

  67. }

  68. 

  69. void fpinv_mont(felm_t a)

  70. { // Field inversion using Montgomery arithmetic, a = a^(-1)*R mod p.

  71.     felm_t tt;

  72. 

  73.     fpcopy(a, tt);

  74.     fpinv_chain_mont(tt);

  75.     fpsqr_mont(tt, tt);

  76.     fpsqr_mont(tt, tt);

  77.     fpmul_mont(a, tt, a);

  78. }

  79. 

  80. void fp2copy(const f2elm_t a, f2elm_t c)

  81. { // Copy a GF(p^2) element, c = a.

  82.     fpcopy(a[0], c[0]);

  83.     fpcopy(a[1], c[1]);

  84. }

  85. 

  86. void fp2zero(f2elm_t a)

  87. { // Zero a GF(p^2) element, a = 0.

  88.     fpzero(a[0]);

  89.     fpzero(a[1]);

  90. }

  91. 

  92. void fp2neg(f2elm_t a)

  93. { // GF(p^2) negation, a = -a in GF(p^2).

  94.     fpneg(a[0]);

  95.     fpneg(a[1]);

  96. }

  97. 

  98. __inline void fp2add(const f2elm_t a, const f2elm_t b, f2elm_t c)

  99. { // GF(p^2) addition, c = a+b in GF(p^2).

  100.     fpadd(a[0], b[0], c[0]);

  101.     fpadd(a[1], b[1], c[1]);

  102. }

  103. 

  104. __inline void fp2sub(const f2elm_t a, const f2elm_t b, f2elm_t c)

  105. { // GF(p^2) subtraction, c = a-b in GF(p^2).

  106.     fpsub(a[0], b[0], c[0]);

  107.     fpsub(a[1], b[1], c[1]);

  108. }

  109. 

  110. void fp2div2(const f2elm_t a, f2elm_t c)

  111. { // GF(p^2) division by two, c = a/2  in GF(p^2).

  112.     fpdiv2(a[0], c[0]);

  113.     fpdiv2(a[1], c[1]);

  114. }

  115. 

  116. void fp2correction(f2elm_t a)

  117. { // Modular correction, a = a in GF(p^2).

  118.     fpcorrection(a[0]);

  119.     fpcorrection(a[1]);

  120. }

  121. 

  122. __inline static void mp_addfast(const digit_t *a, const digit_t *b, digit_t *c)

  123. { // Multiprecision addition, c = a+b.

  124. 

  125.     mp_add_asm(a, b, c);

  126. }

  127. 

  128. __inline static void mp_addfastx2(const digit_t *a, const digit_t *b, digit_t *c)

  129. { // Double-length multiprecision addition, c = a+b.

  130. 

  131.     mp_addx2_asm(a, b, c);

  132. }

  133. 

  134. void fp2sqr_mont(const f2elm_t a, f2elm_t c)

  135. {   // GF(p^2) squaring using Montgomery arithmetic, c = a^2 in GF(p^2).

  136.     // Inputs: a = a0+a1*i, where a0, a1 are in [0, 2*p-1]

  137.     // Output: c = c0+c1*i, where c0, c1 are in [0, 2*p-1]

  138.     felm_t t1, t2, t3;

  139. 

  140.     mp_addfast(a[0], a[1], t1); // t1 = a0+a1

  141.     fpsub(a[0], a[1], t2);      // t2 = a0-a1

  142.     mp_addfast(a[0], a[0], t3); // t3 = 2a0

  143.     fpmul_mont(t1, t2, c[0]);   // c0 = (a0+a1)(a0-a1)

  144.     fpmul_mont(t3, a[1], c[1]); // c1 = 2a0*a1

  145. }

  146. 

  147. __inline unsigned int mp_sub(const digit_t *a, const digit_t *b, digit_t *c, const unsigned int nwords)

  148. { // Multiprecision subtraction, c = a-b, where lng(a) = lng(b) = nwords. Returns the borrow bit.

  149.     unsigned int i, borrow = 0;

  150. 

  151.     for (i = 0; i < nwords; i++)

  152.     {

  153.         SUBC(borrow, a[i], b[i], borrow, c[i]);

  154.     }

  155. 

  156.     return borrow;

  157. }

  158. 

  159. __inline static digit_t mp_subfast(const digit_t *a, const digit_t *b, digit_t *c)

  160. {   // Multiprecision subtraction, c = a-b, where lng(a) = lng(b) = 2*NWORDS_FIELD.

  161.     // If c < 0 then returns mask = 0xFF..F, else mask = 0x00..0

  162. 

  163.     return mp_subx2_asm(a, b, c);

  164. }

  165. 

  166. void fp2mul_mont(const f2elm_t a, const f2elm_t b, f2elm_t c)

  167. {   // GF(p^2) multiplication using Montgomery arithmetic, c = a*b in GF(p^2).

  168.     // Inputs: a = a0+a1*i and b = b0+b1*i, where a0, a1, b0, b1 are in [0, 2*p-1]

  169.     // Output: c = c0+c1*i, where c0, c1 are in [0, 2*p-1]

  170.     felm_t t1, t2;

  171.     dfelm_t tt1, tt2, tt3;

  172.     digit_t mask;

  173.     unsigned int i, borrow = 0;

  174. 

  175.     mp_mul(a[0], b[0], tt1, NWORDS_FIELD); // tt1 = a0*b0

  176.     mp_mul(a[1], b[1], tt2, NWORDS_FIELD); // tt2 = a1*b1

  177.     mp_addfast(a[0], a[1], t1);            // t1 = a0+a1

  178.     mp_addfast(b[0], b[1], t2);            // t2 = b0+b1

  179.     mask = mp_subfast(tt1, tt2, tt3);      // tt3 = a0*b0 - a1*b1. If tt3 < 0 then mask = 0xFF..F, else if tt3 >= 0 then mask = 0x00..0

  180.     for (i = 0; i < NWORDS_FIELD; i++)

  181.     {

  182.         ADDC(borrow, tt3[NWORDS_FIELD + i], ((digit_t *)PRIME)[i] & mask, borrow, tt3[NWORDS_FIELD + i]);

  183.     }

  184.     rdc_mont(tt3, c[0]);               // c[0] = a0*b0 - a1*b1

  185.     mp_addfastx2(tt1, tt2, tt1);       // tt1 = a0*b0 + a1*b1

  186.     mp_mul(t1, t2, tt2, NWORDS_FIELD); // tt2 = (a0+a1)*(b0+b1)

  187.     mp_subfast(tt2, tt1, tt2);         // tt2 = (a0+a1)*(b0+b1) - a0*b0 - a1*b1

  188.     rdc_mont(tt2, c[1]);               // c[1] = (a0+a1)*(b0+b1) - a0*b0 - a1*b1

  189. 

  190.     //a1*b0+a0*b1

  191. }

  192. 

  193. void fpinv_chain_mont(felm_t a)

  194. { // Chain to compute a^(p-3)/4 using Montgomery arithmetic.

  195.     unsigned int i, j;

  196.     felm_t t[27], tt;

  197. 

  198.     // Precomputed table

  199.     fpsqr_mont(a, tt);

  200.     fpmul_mont(a, tt, t[0]);

  201.     fpmul_mont(t[0], tt, t[1]);

  202.     fpmul_mont(t[1], tt, t[2]);

  203.     fpmul_mont(t[2], tt, t[3]);

  204.     fpmul_mont(t[3], tt, t[3]);

  205.     for (i = 3; i <= 8; i++)

  206.         fpmul_mont(t[i], tt, t[i + 1]);

  207.     fpmul_mont(t[9], tt, t[9]);

  208.     for (i = 9; i <= 20; i++)

  209.         fpmul_mont(t[i], tt, t[i + 1]);

  210.     fpmul_mont(t[21], tt, t[21]);

  211.     for (i = 21; i <= 24; i++)

  212.         fpmul_mont(t[i], tt, t[i + 1]);

  213.     fpmul_mont(t[25], tt, t[25]);

  214.     fpmul_mont(t[25], tt, t[26]);

  215. 

  216.     fpcopy(a, tt);

  217.     for (i = 0; i < 6; i++)

  218.         fpsqr_mont(tt, tt);

  219.     fpmul_mont(t[20], tt, tt);

  220.     for (i = 0; i < 6; i++)

  221.         fpsqr_mont(tt, tt);

  222.     fpmul_mont(t[24], tt, tt);

  223.     for (i = 0; i < 6; i++)

  224.         fpsqr_mont(tt, tt);

  225.     fpmul_mont(t[11], tt, tt);

  226.     for (i = 0; i < 6; i++)

  227.         fpsqr_mont(tt, tt);

  228.     fpmul_mont(t[8], tt, tt);

  229.     for (i = 0; i < 8; i++)

  230.         fpsqr_mont(tt, tt);

  231.     fpmul_mont(t[2], tt, tt);

  232.     for (i = 0; i < 6; i++)

  233.         fpsqr_mont(tt, tt);

  234.     fpmul_mont(t[23], tt, tt);

  235.     for (i = 0; i < 6; i++)

  236.         fpsqr_mont(tt, tt);

  237.     fpmul_mont(t[2], tt, tt);

  238.     for (i = 0; i < 9; i++)

  239.         fpsqr_mont(tt, tt);

  240.     fpmul_mont(t[2], tt, tt);

  241.     for (i = 0; i < 10; i++)

  242.         fpsqr_mont(tt, tt);

  243.     fpmul_mont(t[15], tt, tt);

  244.     for (i = 0; i < 8; i++)

  245.         fpsqr_mont(tt, tt);

  246.     fpmul_mont(t[13], tt, tt);

  247.     for (i = 0; i < 8; i++)

  248.         fpsqr_mont(tt, tt);

  249.     fpmul_mont(t[26], tt, tt);

  250.     for (i = 0; i < 8; i++)

  251.         fpsqr_mont(tt, tt);

  252.     fpmul_mont(t[20], tt, tt);

  253.     for (i = 0; i < 6; i++)

  254.         fpsqr_mont(tt, tt);

  255.     fpmul_mont(t[11], tt, tt);

  256.     for (i = 0; i < 6; i++)

  257.         fpsqr_mont(tt, tt);

  258.     fpmul_mont(t[10], tt, tt);

  259.     for (i = 0; i < 6; i++)

  260.         fpsqr_mont(tt, tt);

  261.     fpmul_mont(t[14], tt, tt);

  262.     for (i = 0; i < 6; i++)

  263.         fpsqr_mont(tt, tt);

  264.     fpmul_mont(t[4], tt, tt);

  265.     for (i = 0; i < 10; i++)

  266.         fpsqr_mont(tt, tt);

  267.     fpmul_mont(t[18], tt, tt);

  268.     for (i = 0; i < 6; i++)

  269.         fpsqr_mont(tt, tt);

  270.     fpmul_mont(t[1], tt, tt);

  271.     for (i = 0; i < 7; i++)

  272.         fpsqr_mont(tt, tt);

  273.     fpmul_mont(t[22], tt, tt);

  274.     for (i = 0; i < 10; i++)

  275.         fpsqr_mont(tt, tt);

  276.     fpmul_mont(t[6], tt, tt);

  277.     for (i = 0; i < 7; i++)

  278.         fpsqr_mont(tt, tt);

  279.     fpmul_mont(t[24], tt, tt);

  280.     for (i = 0; i < 6; i++)

  281.         fpsqr_mont(tt, tt);

  282.     fpmul_mont(t[9], tt, tt);

  283.     for (i = 0; i < 8; i++)

  284.         fpsqr_mont(tt, tt);

  285.     fpmul_mont(t[18], tt, tt);

  286.     for (i = 0; i < 6; i++)

  287.         fpsqr_mont(tt, tt);

  288.     fpmul_mont(t[17], tt, tt);

  289.     for (i = 0; i < 8; i++)

  290.         fpsqr_mont(tt, tt);

  291.     fpmul_mont(a, tt, tt);

  292.     for (i = 0; i < 10; i++)

  293.         fpsqr_mont(tt, tt);

  294.     fpmul_mont(t[16], tt, tt);

  295.     for (i = 0; i < 6; i++)

  296.         fpsqr_mont(tt, tt);

  297.     fpmul_mont(t[7], tt, tt);

  298.     for (i = 0; i < 6; i++)

  299.         fpsqr_mont(tt, tt);

  300.     fpmul_mont(t[0], tt, tt);

  301.     for (i = 0; i < 7; i++)

  302.         fpsqr_mont(tt, tt);

  303.     fpmul_mont(t[12], tt, tt);

  304.     for (i = 0; i < 7; i++)

  305.         fpsqr_mont(tt, tt);

  306.     fpmul_mont(t[19], tt, tt);

  307.     for (i = 0; i < 6; i++)

  308.         fpsqr_mont(tt, tt);

  309.     fpmul_mont(t[22], tt, tt);

  310.     for (i = 0; i < 6; i++)

  311.         fpsqr_mont(tt, tt);

  312.     fpmul_mont(t[25], tt, tt);

  313.     for (i = 0; i < 7; i++)

  314.         fpsqr_mont(tt, tt);

  315.     fpmul_mont(t[2], tt, tt);

  316.     for (i = 0; i < 6; i++)

  317.         fpsqr_mont(tt, tt);

  318.     fpmul_mont(t[10], tt, tt);

  319.     for (i = 0; i < 7; i++)

  320.         fpsqr_mont(tt, tt);

  321.     fpmul_mont(t[22], tt, tt);

  322.     for (i = 0; i < 8; i++)

  323.         fpsqr_mont(tt, tt);

  324.     fpmul_mont(t[18], tt, tt);

  325.     for (i = 0; i < 6; i++)

  326.         fpsqr_mont(tt, tt);

  327.     fpmul_mont(t[4], tt, tt);

  328.     for (i = 0; i < 6; i++)

  329.         fpsqr_mont(tt, tt);

  330.     fpmul_mont(t[14], tt, tt);

  331.     for (i = 0; i < 7; i++)

  332.         fpsqr_mont(tt, tt);

  333.     fpmul_mont(t[13], tt, tt);

  334.     for (i = 0; i < 6; i++)

  335.         fpsqr_mont(tt, tt);

  336.     fpmul_mont(t[5], tt, tt);

  337.     for (i = 0; i < 6; i++)

  338.         fpsqr_mont(tt, tt);

  339.     fpmul_mont(t[23], tt, tt);

  340.     for (i = 0; i < 6; i++)

  341.         fpsqr_mont(tt, tt);

  342.     fpmul_mont(t[21], tt, tt);

  343.     for (i = 0; i < 6; i++)

  344.         fpsqr_mont(tt, tt);

  345.     fpmul_mont(t[2], tt, tt);

  346.     for (i = 0; i < 7; i++)

  347.         fpsqr_mont(tt, tt);

  348.     fpmul_mont(t[23], tt, tt);

  349.     for (i = 0; i < 8; i++)

  350.         fpsqr_mont(tt, tt);

  351.     fpmul_mont(t[12], tt, tt);

  352.     for (i = 0; i < 6; i++)

  353.         fpsqr_mont(tt, tt);

  354.     fpmul_mont(t[9], tt, tt);

  355.     for (i = 0; i < 6; i++)

  356.         fpsqr_mont(tt, tt);

  357.     fpmul_mont(t[3], tt, tt);

  358.     for (i = 0; i < 7; i++)

  359.         fpsqr_mont(tt, tt);

  360.     fpmul_mont(t[13], tt, tt);

  361.     for (i = 0; i < 7; i++)

  362.         fpsqr_mont(tt, tt);

  363.     fpmul_mont(t[17], tt, tt);

  364.     for (i = 0; i < 8; i++)

  365.         fpsqr_mont(tt, tt);

  366.     fpmul_mont(t[26], tt, tt);

  367.     for (i = 0; i < 8; i++)

  368.         fpsqr_mont(tt, tt);

  369.     fpmul_mont(t[5], tt, tt);

  370.     for (i = 0; i < 8; i++)

  371.         fpsqr_mont(tt, tt);

  372.     fpmul_mont(t[8], tt, tt);

  373.     for (i = 0; i < 6; i++)

  374.         fpsqr_mont(tt, tt);

  375.     fpmul_mont(t[2], tt, tt);

  376.     for (i = 0; i < 6; i++)

  377.         fpsqr_mont(tt, tt);

  378.     fpmul_mont(t[11], tt, tt);

  379.     for (i = 0; i < 7; i++)

  380.         fpsqr_mont(tt, tt);

  381.     fpmul_mont(t[20], tt, tt);

  382.     for (j = 0; j < 61; j++)

  383.     {

  384.         for (i = 0; i < 6; i++)

  385.             fpsqr_mont(tt, tt);

  386.         fpmul_mont(t[26], tt, tt);

  387.     }

  388.     fpcopy(tt, a);

  389. }

  390. 

  391. void fp2inv_mont(f2elm_t a)

  392. { // GF(p^2) inversion using Montgomery arithmetic, a = (a0-i*a1)/(a0^2+a1^2).

  393.     f2elm_t t1;

  394. 

  395.     fpsqr_mont(a[0], t1[0]);    // t10 = a0^2

  396.     fpsqr_mont(a[1], t1[1]);    // t11 = a1^2

  397.     fpadd(t1[0], t1[1], t1[0]); // t10 = a0^2+a1^2

  398.     fpinv_mont(t1[0]);          // t10 = (a0^2+a1^2)^-1

  399.     fpneg(a[1]);                // a = a0-i*a1

  400.     fpmul_mont(a[0], t1[0], a[0]);

  401.     fpmul_mont(a[1], t1[0], a[1]); // a = (a0-i*a1)*(a0^2+a1^2)^-1

  402. }

  403. 

  404. void to_fp2mont(const f2elm_t a, f2elm_t mc)

  405. {   // Conversion of a GF(p^2) element to Montgomery representation,

  406.     // mc_i = a_i*R^2*R^(-1) = a_i*R in GF(p^2).

  407. 

  408.     to_mont(a[0], mc[0]);

  409.     to_mont(a[1], mc[1]);

  410. }

  411. 

  412. void from_fp2mont(const f2elm_t ma, f2elm_t c)

  413. {   // Conversion of a GF(p^2) element from Montgomery representation to standard representation,

  414.     // c_i = ma_i*R^(-1) = a_i in GF(p^2).

  415. 

  416.     from_mont(ma[0], c[0]);

  417.     from_mont(ma[1], c[1]);

  418. }

  419. 

  420. __inline unsigned int mp_add(const digit_t *a, const digit_t *b, digit_t *c, const unsigned int nwords)

  421. { // Multiprecision addition, c = a+b, where lng(a) = lng(b) = nwords. Returns the carry bit.

  422.     unsigned int i, carry = 0;

  423. 

  424.     for (i = 0; i < nwords; i++)

  425.     {

  426.         ADDC(carry, a[i], b[i], carry, c[i]);

  427.     }

  428. 

  429.     return carry;

  430. }

  431. 

  432. void mp_shiftleft(digit_t *x, unsigned int shift, const unsigned int nwords)

  433. {

  434.     unsigned int i, j = 0;

  435. 

  436.     while (shift > RADIX)

  437.     {

  438.         j += 1;

  439.         shift -= RADIX;

  440.     }

  441. 

  442.     for (i = 0; i < nwords - j; i++)

  443.         x[nwords - 1 - i] = x[nwords - 1 - i - j];

  444.     for (i = nwords - j; i < nwords; i++)

  445.         x[nwords - 1 - i] = 0;

  446.     if (shift != 0)

  447.     {

  448.         for (j = nwords - 1; j > 0; j--)

  449.             SHIFTL(x[j], x[j - 1], shift, x[j], RADIX);

  450.         x[0] <<= shift;

  451.     }

  452. }

  453. 

  454. void mp_shiftr1(digit_t *x, const unsigned int nwords)

  455. { // Multiprecision right shift by one.

  456.     unsigned int i;

  457. 

  458.     for (i = 0; i < nwords - 1; i++)

  459.     {

  460.         SHIFTR(x[i + 1], x[i], 1, x[i], RADIX);

  461.     }

  462.     x[nwords - 1] >>= 1;

  463. }

  464. 

  465. void mp_shiftl1(digit_t *x, const unsigned int nwords)

  466. { // Multiprecision left shift by one.

  467.     int i;

  468. 

  469.     for (i = nwords - 1; i > 0; i--)

  470.     {

  471.         SHIFTL(x[i], x[i - 1], 1, x[i], RADIX);

  472.     }

  473.     x[0] <<= 1;

  474. }