util.c 8.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386
  1. /*
  2. * util.c
  3. *
  4. * Created on: May 30, 2018
  5. * Author: vader
  6. */
  7. #include "../../include/util/util.h"
  8. #define min(a,b) (((a)<(b))?(a):(b))
  9. void store(matrix *src, unsigned char *dst) {
  10. int counter = 0;
  11. for (int i = 0; i < src->rows; i++) {
  12. for (int j = code_dimension; j < src->cols; j++) {
  13. dst[counter] = src->data[i * src->cols + j];
  14. counter++;
  15. //printf(" %d, \n", counter);
  16. }
  17. }
  18. //printf(" %d, \n", counter);
  19. /*print_matrix(src);
  20. for (int i = 0; i < CRYPTO_PUBLICKEYBYTES; i++) {
  21. printf(" %" PRIu16 ", ", dst[i]);
  22. }
  23. printf("\n");*/
  24. }
  25. void store_u_y(const gf *v, const gf *y, unsigned char *sk) {
  26. for (int i = 0; i < 2 * code_length; i = i + 2) {
  27. gf a = v[i / 2] >> 8;
  28. gf b = v[i / 2] & 0xFF;
  29. sk[i] = a;
  30. sk[i + 1] = b;
  31. }
  32. for (int i = 2 * code_length; i < 4 * code_length; i = i + 2) {
  33. gf a = y[(i / 2) - code_length] >> 8;
  34. gf b = y[(i / 2) - code_length] & 0xFF;
  35. sk[i] = a;
  36. sk[i + 1] = b;
  37. }
  38. /*int i, a = 0;
  39. gf c1, c2;
  40. unsigned char c;
  41. for (i = 0; i < (code_length / 2); i++) {
  42. c1 = v[2 * i];
  43. c2 = v[2 * i + 1];
  44. c = c1 >> 4;
  45. sk[a] = c;
  46. a += 1;
  47. c1 = c1 & 15;
  48. c = (c1 << 4) ^ (c2 >> 8);
  49. sk[a] = c;
  50. a += 1;
  51. c = c2 & 255;
  52. sk[a] = c;
  53. a += 1;
  54. }
  55. for (i = 0; i < (code_length / 2); i++) {
  56. c1 = y[2 * i];
  57. c2 = y[2 * i + 1];
  58. c = c1 >> 4;
  59. sk[a] = c;
  60. a += 1;
  61. c1 = c1 & 15;
  62. c = (c1 << 4) ^ (c2 >> 8);
  63. sk[a] = c;
  64. a += 1;
  65. c = c2 & 255;
  66. sk[a] = c;
  67. a += 1;
  68. }*/
  69. }
  70. void recover_sk(const unsigned char * sk, gf* v, gf * y) {
  71. for (int i = 0; i < 2 * code_length; i = i + 2) {
  72. v[i / 2] = sk[i + 1] | (sk[i] << 8);
  73. }
  74. for (int i = 2 * code_length; i < 4 * code_length; i = i + 2) {
  75. y[(i / 2) - code_length] = sk[i + 1] | (sk[i] << 8);
  76. }
  77. }
  78. void recover_G(const unsigned char *public_key, matrix *G) {
  79. gf z[code_dimension] = { 0 };
  80. for (int i = 0; i < code_dimension; i++) {
  81. z[i] = 1;
  82. }
  83. for (int i = 0;
  84. i
  85. < min(
  86. code_length - ((signature_block_size * pol_deg) * extension),
  87. code_dimension); i++) {
  88. G->data[i * G->cols + i] = z[i];
  89. }
  90. int counter = 0;
  91. for (int i = 0; i < G->rows; i++) {
  92. for (int j = code_dimension; j < G->cols; j++) {
  93. G->data[i * G->cols + j] = public_key[counter];
  94. counter++;
  95. }
  96. }
  97. }
  98. void recover_public_key(const unsigned char *public_key, matrix *G) {
  99. int a = 0;
  100. int i, j, k, p, l, m, q;
  101. matrix *M = make_matrix(code_dimension, code_length - code_dimension);
  102. k = code_dimension / (signature_block_size);
  103. p = (code_length - code_dimension) / 4;
  104. gf c1 = 0, c2 = 0, c3 = 0, c4 = 0, tmp1 = 0, tmp2 = 0;
  105. q = (code_length - code_dimension) / (signature_block_size);
  106. unsigned char c = 0;
  107. gf sig[signature_block_size] = { 0 };
  108. gf signature_all_line[(code_length - code_dimension)] = { 0 };
  109. for (i = 0; i < k; i++) {
  110. for (j = 0; j < p; j++) {
  111. c = public_key[a];
  112. //printf("--c= %d \t",c);
  113. c1 = c >> 2;
  114. signature_all_line[4 * j] = c1;
  115. tmp1 = (c & 3);
  116. a += 1;
  117. c = public_key[a];
  118. //printf("--c= %d \t",c);
  119. c2 = (tmp1 << 4) ^ (c >> 4);
  120. signature_all_line[4 * j + 1] = c2;
  121. tmp2 = c & 15;
  122. a += 1;
  123. c = public_key[a];
  124. a += 1;
  125. //printf("--c= %d \t",c);
  126. c3 = (tmp2 << 2) ^ (c >> 6);
  127. signature_all_line[4 * j + 2] = c3;
  128. c4 = c & 63;
  129. signature_all_line[4 * j + 3] = c4;
  130. }
  131. for (l = 0; l < q; l++) {
  132. for (m = 0; m < (signature_block_size); m++) {
  133. sig[m] = signature_all_line[l * (signature_block_size) + m];
  134. }
  135. //affiche_vecteur(sig,order);
  136. quasi_dyadic_bloc_matrix(M, sig, l * (signature_block_size),
  137. i * (signature_block_size));
  138. }
  139. }
  140. for (i = 0; i < G->rows; i++) {
  141. G->data[i * G->cols + i] = 1;
  142. for (j = M->rows; j < G->cols; j++) {
  143. G->data[i * G->cols + j] = M->data[(i * M->cols) + j - M->rows];
  144. }
  145. }
  146. free_matrix(M);
  147. }
  148. void generate_int_list_of_size(int *list, int length) {
  149. for (int i = 0; i < length; i++) {
  150. list[i] = i;
  151. }
  152. }
  153. /*
  154. * generate_elements_in_F_q_m:
  155. * The list that is generated is a list of elements 1,2,3 ...
  156. * all the way up to F_q_m
  157. */
  158. void generate_elements_in_order(gf * set_of_elements_in_F_q_m, int start_value,
  159. unsigned int size) {
  160. int i;
  161. for (i = 0; i < size; i++) {
  162. set_of_elements_in_F_q_m[i] = start_value + i;
  163. }
  164. }
  165. /*
  166. * random_m:
  167. * Currently this function is used to allow changes to the random byte function
  168. * called without having to affect change multiple location in code.
  169. */
  170. void random_m(unsigned char *m) {
  171. randombytes_buf(m, k_prime);
  172. }
  173. /*
  174. * element_in_vector:
  175. * This function goes through and checks if "value_to_check" in array v up to
  176. * "size" elements in the array.
  177. *
  178. * Param:
  179. * v: Provide the array to check for the value in
  180. * value_to_check: Provide the value that needs to be checked for
  181. * size: Provide the number of elements in the array that need to be checked.
  182. *
  183. * Return:
  184. * Return EXIT_SUCCESS if the value is not contained in the array otherwise
  185. * EXIT_FAILURE if it is.
  186. */
  187. int element_in_vector(unsigned int *v, int value_to_check, int size) {
  188. int i;
  189. for (i = 0; i < size; i++) {
  190. if (v[i] == value_to_check) {
  191. return EXIT_FAILURE;
  192. }
  193. }
  194. return EXIT_SUCCESS;
  195. }
  196. /*
  197. * random_e:
  198. * Put errors into the error array based on the sigma provided
  199. *
  200. * Param:
  201. * sigma: Provide the hash_sigma
  202. * error_array: Provide an array to hold the values and locations of the errors
  203. */
  204. void random_e(const unsigned char *sigma, unsigned char *error_array) {
  205. int i, j = 0, k = 0, jeton = 0;
  206. unsigned char gf_sigma;
  207. unsigned int v[weight] = { 0 };
  208. PRINT_DEBUG_UTIL("error_position: ");
  209. for (i = 0; i < code_length; i++) {
  210. gf_sigma = sigma[i] % F_q_size;
  211. if (gf_sigma == 0) {
  212. continue;
  213. }
  214. do {
  215. jeton = (sigma[k + 1] ^ (sigma[k] << 4)) % code_length;
  216. k++;
  217. } while (element_in_vector(v, jeton, j + 1) == 1); //Only check j elements
  218. v[j] = jeton;
  219. error_array[jeton] = gf_sigma;
  220. PRINT_DEBUG_UTIL("%d, ", jeton);
  221. j++;
  222. // Onlyl need to find weight errors
  223. if (j == weight) {
  224. break;
  225. }
  226. }
  227. #ifdef DEBUG_UTIL
  228. PRINT_DEBUG_UTIL("\n");
  229. for (int i = 0; i < code_length; i++) {
  230. PRINT_DEBUG_UTIL("%d, ", error_array[i]);
  231. }
  232. PRINT_DEBUG_UTIL("\n");
  233. #endif
  234. }
  235. void set_vy_from_sk(gf* v, gf * y, const unsigned char * sk) {
  236. int i, a = 0;
  237. unsigned char c;
  238. gf c1, c2, c3;
  239. for (i = 0; i < (code_length / 2); i++) {
  240. c = sk[a];
  241. c1 = c;
  242. a += 1;
  243. c = sk[a];
  244. c2 = c;
  245. a += 1;
  246. c = sk[a];
  247. c3 = c;
  248. a += 1;
  249. v[2 * i] = (c1 << 4) ^ (c2 >> 4);
  250. c1 = c2 & 15;
  251. v[2 * i + 1] = (c1 << 8) ^ c3;
  252. }
  253. for (i = 0; i < (code_length / 2); i++) {
  254. c = sk[a];
  255. c1 = c;
  256. a += 1;
  257. c = sk[a];
  258. c2 = c;
  259. a += 1;
  260. c = sk[a];
  261. c3 = c;
  262. a += 1;
  263. y[2 * i] = (c1 << 4) ^ (c2 >> 4);
  264. c1 = c2 & 15;
  265. y[2 * i + 1] = (c1 << 8) ^ c3;
  266. }
  267. }
  268. int compute_weight(unsigned char *vector, int size) {
  269. int i = 0, w = 0;
  270. for (i = 0; i < size; i++) {
  271. if (vector[i] != 0)
  272. w++;
  273. }
  274. return w;
  275. }
  276. int index_of_element(const gf *v, gf element) {
  277. for (int i = 0; i < code_length; i++) {
  278. if (v[i] == element) {
  279. return i;
  280. }
  281. }
  282. return -1;
  283. }
  284. void swap(gf* str, int i, int j) {
  285. char temp = str[i];
  286. str[i] = str[j];
  287. str[j] = temp;
  288. }
  289. void permute(gf *array, int i, int length) {
  290. int j = i;
  291. for (j = i; j < length; j++) {
  292. swap(array, i, j);
  293. permute(array, i + 1, length);
  294. swap(array, i, j);
  295. }
  296. return;
  297. }
  298. /*
  299. * check_positions
  300. * This function checks all of the values of an array to ensure that they
  301. * are no longer set to -1
  302. *
  303. * param:
  304. * pos Provide an interger array
  305. * size Provide the number of elements in the array to check
  306. *
  307. * Results:
  308. * Returns EXIT_SUCCESS if there are no longer any values that are -1.
  309. * Otherwise EXIT_FAILURE
  310. */
  311. int check_positions(const int *pos, const int size) {
  312. int i = 0;
  313. for (i = size; i > -1; i--) {
  314. if (pos[i] == -1) {
  315. return EXIT_FAILURE;
  316. }
  317. }
  318. return EXIT_SUCCESS;
  319. }
  320. int multiplicative_order(const int a) {
  321. int order = 1;
  322. gf result = gf_pow_f_q_m(a, order);
  323. while (result != 1) {
  324. order++;
  325. result = gf_pow_f_q_m(a, order);
  326. }
  327. return order;
  328. }
  329. gf discrete_logarithm(const gf a, const gf b) {
  330. int p = multiplicative_order(b); // multiplicative order of base
  331. gf y = a;
  332. int N = sqrt(p) + 1;
  333. gf tbl[N];
  334. for (int i = 0; i <= N; i++) {
  335. tbl[i] = gf_pow_f_q_m(b, i);
  336. }
  337. gf temp = gf_pow_f_q_m(b, N);
  338. gf inv_a_m = gf_q_m_inv(temp);
  339. for (int j = 0; j < N; j++) {
  340. for (int i = 0; i < N; i++) {
  341. if (y == tbl[i]) {
  342. gf result = i + (N * j);
  343. return result;
  344. }
  345. }
  346. y = gf_q_m_mult(y, inv_a_m);
  347. }
  348. return -1;
  349. }