decoding.c 4.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187
  1. /*
  2. * decoding.c
  3. *
  4. * Created on: Jun 2, 2018
  5. * Author: vader
  6. */
  7. #include "../include/decoding.h"
  8. /*
  9. * Decoding:
  10. * This function is used to find the error vector and the code_word.
  11. *
  12. * Return:
  13. * Return EXIT_SUCCESS if the successful at decoding otherwise EXIT_FAILURE
  14. */
  15. int decoding(const gf* v, const gf* y, const unsigned char *c,
  16. unsigned char *error, unsigned char *code_word) {
  17. int i, k, j, dr, position;
  18. int st = (signature_block_size * pol_deg);
  19. polynomial *syndrom;
  20. polynomial *omega, *sigma, *re, *uu, *u, *quotient;
  21. polynomial *rest, *app, *temp, *temp_sum,*delta, *pos;
  22. gf pol_gf, tmp, tmp1, o;
  23. gf alpha;
  24. int aux_position[weight];
  25. gf aux_perm[F_q_m_size];
  26. memset(aux_position, -1, weight * sizeof(int));
  27. gf exp_alpha = (F_q_m_size - 1) / (F_q_size - 1);
  28. alpha = gf_pow_f_q_m(2, exp_alpha); //b^((q^m)-1)/(q-1)
  29. //Compute Syndrome normally
  30. PRINT_DEBUG_DEC("Decoding:Computing syndrom\n");
  31. syndrom = create_polynomial(st - 1);
  32. compute_syndrom(v, y, c, syndrom);
  33. if (syndrom->degree == -1) {
  34. return EXIT_FAILURE;
  35. }
  36. //Resolution of the key equation
  37. re = create_polynomial(st);
  38. re->coefficient[st] = 1;
  39. polynomial_get_update_degree(re);
  40. app = create_polynomial(st);
  41. uu = create_polynomial(st);
  42. u = create_polynomial(st);
  43. u->coefficient[0] = 1;
  44. u->degree = 0;
  45. dr = syndrom->degree;
  46. PRINT_DEBUG_DEC("Computing re,u,quotient\n");
  47. while (dr >= (st / 2)) {
  48. quotient = poly_quo(re, syndrom);
  49. rest = poly_rem(re, syndrom);
  50. poly_set(re, syndrom); // re = p
  51. poly_set(syndrom, rest); // p = mo2d_re
  52. poly_set(app, uu); // app = UU
  53. poly_set(uu, u); //UU = U
  54. temp = poly_multiplication(u, quotient);
  55. temp_sum = polynomial_addition(temp, app);
  56. poly_set(u, temp_sum); // U = (U*quotient) + app
  57. polynomial_free(temp);
  58. polynomial_free(temp_sum);
  59. polynomial_free(quotient);
  60. polynomial_free(rest);
  61. dr = syndrom->degree;
  62. }
  63. polynomial_free(re);
  64. polynomial_free(uu);
  65. polynomial_free(app);
  66. PRINT_DEBUG_DEC("Computing delta, omega, sigma\n");
  67. delta = create_polynomial(0);
  68. // u over z with z = 0
  69. delta->coefficient[0] = gf_q_m_inv(polynomial_evaluation(u, 0));
  70. omega = poly_multiplication(syndrom, delta);
  71. polynomial_free(syndrom);
  72. sigma = poly_multiplication(u, delta);
  73. polynomial_free(delta);
  74. polynomial_free(u);
  75. generate_elements_in_order(aux_perm, 0, F_q_m_size);
  76. j = 0;
  77. PRINT_DEBUG_DEC("Computing error position\n");
  78. for (i = 0; i < F_q_m_size; i++) {
  79. // If the polynomial evaluates to zero
  80. if (!polynomial_evaluation(sigma, aux_perm[i])) {
  81. position = index_of_element(v, gf_q_m_inv(aux_perm[i]));
  82. PRINT_DEBUG_DEC("%d, ", position);
  83. aux_position[j] = position;
  84. j += 1;
  85. }
  86. }
  87. PRINT_DEBUG_DEC("\n");
  88. polynomial_free(sigma);
  89. //Element for determining the value of errors
  90. if (check_positions(aux_position, st / 2)) {
  91. return -1;
  92. }
  93. #ifdef DEBUG
  94. PRINT_DEBUG_DEC("decoding error_position: ");
  95. for (i = 0; i < weight; i++) {
  96. PRINT_DEBUG_DEC("%d, ", aux_position[i]);
  97. }
  98. PRINT_DEBUG_DEC("\n");
  99. #endif
  100. pos = create_polynomial(st / 2);
  101. for (i = 0; i < st / 2; i++) {
  102. pos->coefficient[i] = (gf) aux_position[i];
  103. }
  104. polynomial_get_update_degree(pos);
  105. if (pos->degree == -1) {
  106. return EXIT_FAILURE;
  107. }
  108. PRINT_DEBUG_DEC("Computing evaluating error position\n");
  109. app = create_polynomial(pos->degree);
  110. for (j = 0; j <= pos->degree; j++) {
  111. pol_gf = 1;
  112. for (i = 0; i < j; i++) {
  113. tmp = gf_q_m_mult(v[pos->coefficient[i]],
  114. gf_q_m_inv(v[pos->coefficient[j]]));
  115. tmp = gf_add(1, tmp);
  116. pol_gf = gf_q_m_mult(pol_gf, tmp);
  117. }
  118. for (i = j + 1; i <= pos->degree; i++) {
  119. tmp = gf_q_m_mult(v[pos->coefficient[i]],
  120. gf_q_m_inv(v[pos->coefficient[j]]));
  121. tmp = gf_add(1, tmp);
  122. pol_gf = gf_q_m_mult(pol_gf, tmp);
  123. }
  124. o = polynomial_evaluation(omega, gf_q_m_inv(v[pos->coefficient[j]]));
  125. tmp1 = gf_q_m_mult(y[pos->coefficient[j]], pol_gf);
  126. if (tmp1 != 0) {
  127. app->coefficient[j] = gf_div_f_q_m(o, tmp1);
  128. }
  129. }
  130. polynomial_get_update_degree(app);
  131. polynomial_free(omega);
  132. PRINT_DEBUG_DEC("Reconstruction of the error vector\n");
  133. //Reconstruction of the error vector
  134. for (i = 0; i <= app->degree; i++) {
  135. k = discrete_logarithm(app->coefficient[i], alpha);
  136. error[pos->coefficient[i]] = gf_pow_f_q(2, k); // Correction
  137. }
  138. polynomial_free(app);
  139. polynomial_free(pos);
  140. //Reconstruction of code_word
  141. for (i = 0; i < code_length; i++) {
  142. code_word[i] = (c[i] ^ error[i]) & F_q_m_order;
  143. }
  144. return EXIT_SUCCESS;
  145. }