keygeneration.c 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665
  1. /*
  2. * keygeneration.c
  3. *
  4. * Created on: May 3, 2018
  5. * Author: Gustavo Banegas
  6. */
  7. #include "../include/keygeneration.h"
  8. #include "time.h"
  9. static int build_dyadic_signature_part_1(gf *signature_h);
  10. static int build_dyadic_signature_part2(gf *signature_h, int * block_position);
  11. /*
  12. * contains_zero:
  13. * Check to see if the array does not contain zeros
  14. * exit:
  15. * Return EXIT_SUCCESS if the array does not contain zeros
  16. * and EXIT_FAILURE if the array does contain zeros.
  17. */
  18. int contains_zero(gf *list, int length) {
  19. for (int i = 0; i < length; i++) {
  20. if (list[i] == 0)
  21. return EXIT_FAILURE;
  22. }
  23. return EXIT_SUCCESS;
  24. }
  25. /*
  26. * remove_integer:
  27. * This functions goes through a list and sets the element that is equal
  28. * to the @element variable to -1
  29. *
  30. * Function returns EXIT_SUCCESS if the if the element was found and set to -1
  31. * otherwise EXIT_FAILURE
  32. */
  33. int remove_integer(int element, int *list, int size) {
  34. int i;
  35. for (i = 0; i < size; i++) {
  36. if (list[i] == element) {
  37. list[i] = -1;
  38. return EXIT_SUCCESS;
  39. }
  40. }
  41. return EXIT_FAILURE;
  42. }
  43. /*
  44. * This function goes through and checks all of the entries in the length to make
  45. * sure that they do not contain @random_e up to length.
  46. * Returns:
  47. * EXIT_SUCCESS if the element is not present
  48. * EXIT_FAILURE if the element is present
  49. */
  50. int vector_contains(gf *signature_h, gf random_e, int length) {
  51. int i;
  52. for (i = 0; i < length; i++) {
  53. if (signature_h[i] == random_e)
  54. return EXIT_FAILURE;
  55. }
  56. return EXIT_SUCCESS;
  57. }
  58. /*
  59. * build_dyadic_signature function
  60. * This function is used to create the dyadic matrix required for the key_gen.
  61. *
  62. * Param:
  63. * dyadic_signature The dyadic_signature is returned in this provided array.
  64. *
  65. * Return:
  66. * EXIT_SUCCESS if the signature was created correctly. If the matrix will fail
  67. * to be dyadic return EXIT_FAILURE so additional checks do not have to be performed.
  68. */
  69. int build_dyadic_signature(gf *dyadic_signature) {
  70. //PRINT_DEBUG("Build_dyadic_signature start\n");
  71. int block_position[n0] = { 0 };
  72. gf signature_h[F_q_m_size] = { 0 };
  73. int i, aux_count_transfer_block = 0;
  74. if (EXIT_SUCCESS != build_dyadic_signature_part_1(signature_h)) {
  75. PRINT_DEBUG("build_dyadic_signature_part_1 failed\n");
  76. return EXIT_FAILURE;
  77. }
  78. if (EXIT_SUCCESS
  79. != build_dyadic_signature_part2(signature_h, block_position)) {
  80. PRINT_DEBUG("build_dyadic_signature_part_2 failed\n");
  81. return EXIT_FAILURE;
  82. }
  83. for (i = 0; i < n0; i++) {
  84. memcpy(&dyadic_signature[aux_count_transfer_block],
  85. &signature_h[signature_block_size * block_position[i]],
  86. signature_block_size * sizeof(gf));
  87. aux_count_transfer_block += signature_block_size;
  88. }
  89. return EXIT_SUCCESS;
  90. }
  91. static int build_dyadic_signature_part_1(gf *signature_h) {
  92. gf h0 = 0, h0_inverse, i_inverse;
  93. int t, i, j; //for loop variables
  94. gf random_e, temp, temp_inv;
  95. //Set h0 to anything but 0
  96. do {
  97. h0 = randombytes_uniform(F_q_m_size - 1);
  98. } while (h0 == 0);
  99. h0_inverse = gf_q_m_inv(h0);
  100. signature_h[0] = h0;
  101. for (t = 0; t < extension * subfield; t++) {
  102. i = 1 << t;
  103. random_e = 0;
  104. //random_e must be not in signature_h or equal 0
  105. do {
  106. random_e = randombytes_uniform(F_q_m_size - 1);
  107. } while (random_e == 0
  108. || vector_contains(signature_h + i, random_e, code_length));
  109. //Set signature_h[1<<t] to random_e
  110. signature_h[i] = random_e;
  111. //For loop through values from 1 to i setting signature_h values to the
  112. i_inverse = gf_q_m_inv(signature_h[i]);
  113. for (j = 1; j < i; j++) {
  114. if (signature_h[i] != 0 && signature_h[j] != 0) {
  115. temp = i_inverse ^ gf_q_m_inv(signature_h[j]) ^ h0_inverse;
  116. if (temp != 0) {
  117. temp_inv = gf_q_m_inv(temp);
  118. signature_h[i + j] = temp_inv;
  119. } else {
  120. signature_h[i + j] = 0;
  121. }
  122. } else {
  123. signature_h[i + j] = 0;
  124. }
  125. }
  126. }
  127. if (EXIT_SUCCESS == contains_zero(signature_h, signature_block_size)) {
  128. return EXIT_SUCCESS;
  129. } else {
  130. print_vector(signature_h, signature_block_size);
  131. return EXIT_FAILURE;
  132. }
  133. }
  134. int build_dyadic_signature_part2(gf *signature_h, int * block_position) {
  135. int i, j; //for loop variables
  136. int ll = 0;
  137. int size_part = (F_q_m_size / signature_block_size) - 1;
  138. int part[(F_q_m_size / signature_block_size) - 1] = { 0 };
  139. int count_part = 0;
  140. gf aux_list[signature_block_size] = { 0 };
  141. gf temp_list[signature_block_size]; // = { 0 };
  142. memcpy(temp_list, signature_h, signature_block_size * sizeof(gf));
  143. for (i = 0; i < size_part; i++) {
  144. part[i] = randombytes_uniform(size_part - 1);
  145. }
  146. //Check to see if temp_list does not contain zeros
  147. block_position[0] = ll;
  148. ll++;
  149. while (ll * signature_block_size != code_length) {
  150. j = 0;
  151. do {
  152. j = part[count_part];
  153. count_part++;
  154. } while (j == 0 && count_part < size_part);
  155. if (count_part >= size_part) {
  156. PRINT_DEBUG("Invalid index into part array\n");
  157. return EXIT_FAILURE;
  158. }
  159. if (EXIT_FAILURE == remove_integer(j, part, size_part)) {
  160. PRINT_DEBUG("Failed to remove int likely already occurred\n");
  161. }
  162. memcpy(aux_list, &signature_h[(j * signature_block_size)],
  163. signature_block_size * sizeof(gf));
  164. if (EXIT_SUCCESS == contains_zero(aux_list, signature_block_size)) {
  165. block_position[ll] = j;
  166. ll++;
  167. }
  168. }
  169. return EXIT_SUCCESS;
  170. }
  171. /*
  172. * is_vectors_disjoint:
  173. * Goes through value of u and ensure that no value of v is the same
  174. * param:
  175. * u vector u from Cauchy support
  176. * v vector v from the Cauchy support
  177. * Return:
  178. * Return EXIT_SUCCESS if there are no matches otherwise EXIT_FAILURE
  179. */
  180. int is_vectors_disjoint(gf *u, gf *v) {
  181. int i, j;
  182. //PRINT_DEBUG("is_vector_disjoint\n");
  183. for (i = 0; i < (signature_block_size); i++) {
  184. for (j = 0; j < code_length; j++) {
  185. if (u[i] == v[j]) {
  186. return EXIT_FAILURE;
  187. }
  188. }
  189. }
  190. return EXIT_SUCCESS;
  191. }
  192. /*
  193. * is_vector_disjoint:
  194. * Go through the vector and ensure that there are no duplicate entries
  195. * param:
  196. * list provide a vector
  197. * size provide the size of the vector to check
  198. *
  199. * Return:
  200. * Return EXIT_SUCCESS if the values are not the same otherwise EXIT_FAILURE
  201. *
  202. */
  203. int is_vector_disjoint(gf *list, int size) { //TODO consider wrapping these tests to one function
  204. int i, j;
  205. for (i = 0; i < size; i++) {
  206. for (j = i + 1; j < size; j++) {
  207. if (list[i] == list[j]) {
  208. return EXIT_FAILURE;
  209. }
  210. }
  211. }
  212. return EXIT_SUCCESS;
  213. }
  214. /*
  215. * For loop through both arrays and if remove elements from the to_remove array
  216. * exists in they elements array then remove it.
  217. */
  218. void remove_elements(gf *to_remove, gf *elements, int length) {
  219. int i, j;
  220. for (i = 0; i < length; i++) {
  221. for (j = 0; j < length; j++) {
  222. if (to_remove[i] == elements[j]) {
  223. to_remove[i] = 0;
  224. }
  225. }
  226. }
  227. }
  228. /*
  229. * build_support
  230. * This function is used to generate the u and v vectors from the signature_h
  231. *
  232. * params:
  233. * signature_h Provide the signature vector
  234. * u and v Provide allocated vectors
  235. * elements Provide the generated elements vector to be copied from.
  236. *
  237. * Returns:
  238. * Vectors u and v are filled in appropriately
  239. */
  240. void build_support(gf *signature_h, gf *u, gf *v, gf *elements) {
  241. gf elements_in_F_q_m[code_length];
  242. gf signature_h_inv[code_length];
  243. gf aux[code_length] = { 0 };
  244. gf h0_inv = gf_q_m_inv(signature_h[0]);
  245. int i;
  246. gf omega = 0;
  247. memcpy(elements_in_F_q_m, elements, code_length);
  248. PRINT_DEBUG("build_support start\n");
  249. for (i = 0; i < code_length; i++) {
  250. signature_h_inv[i] = gf_q_m_inv(signature_h[i]);
  251. aux[i] = h0_inv ^ signature_h_inv[i];
  252. }
  253. remove_elements(elements_in_F_q_m, aux, code_length);
  254. do {
  255. omega = elements_in_F_q_m[randombytes_uniform(code_length - 1)];
  256. } while (omega == 0);
  257. for (i = 0; i < code_length; i++) {
  258. if (signature_h[i] != 0) {
  259. if (i < signature_block_size) {
  260. u[i] = signature_h_inv[i] ^ omega;
  261. v[i] = u[i] ^ h0_inv;
  262. } else {
  263. v[i] = signature_h_inv[i] ^ h0_inv ^ omega;
  264. }
  265. }
  266. }
  267. }
  268. /*
  269. * build_cauchy_matrix
  270. * This function builds the cauchy matrix using the provided u and v vectors
  271. *
  272. * param:
  273. * v Provide the v vector used to generate the cauchy matrix
  274. * u Provide the u vector used to generate the cauchy matrix
  275. * H_cauchy Provide the cauchy matrix to be filled in
  276. *
  277. * Results:
  278. * The cauchy matrix is calculated and stored in the pointer
  279. */
  280. void build_cauchy_matrix(gf *u, gf *v, matrix *H_cauchy) {
  281. int i, j, k;
  282. PRINT_DEBUG("Building the cauchy matrix\n");
  283. for (k = 0; k < pol_deg; k++) {
  284. for (i = 0; i < signature_block_size; i++) {
  285. for (j = 0; j < code_length; j++) {
  286. H_cauchy->data[(k * signature_block_size + i) * code_length + j] =
  287. gf_pow_f_q_m(gf_q_m_inv((u[i] ^ v[j])), k + 1);
  288. }
  289. }
  290. }
  291. }
  292. /*
  293. * build_trapdoor:
  294. * This function builds the trap vector y and returns int in the pointer y
  295. *
  296. * param:
  297. * H_cauchy Provide the cauchy matrix
  298. * v and u Provide the vectors v and u
  299. * y A pointer to return the trapdoor in
  300. * H A matrix to be filled out with the data
  301. *
  302. * Return:
  303. * EXIT_SUCCES if trapdoor is build otherwise EXIT_FAILURE
  304. */
  305. int build_trapdoor(const matrix* restrict H_cauchy, const gf* restrict v,
  306. const gf* restrict u, gf* restrict y, matrix* restrict H) {
  307. gf z[code_length] = { 0 };
  308. gf random_el = 0;
  309. gf pol, sum_u_v, result;
  310. int i, j, ret_val = EXIT_FAILURE;
  311. matrix *diagonal_z_matrix = NULL, *H3 = NULL;
  312. PRINT_DEBUG("build_trapdoor start\n");
  313. for (i = 0; i < n0; i++) {
  314. do {
  315. random_el = randombytes_uniform(F_q_m_size - 1);
  316. //TODO this vector_contains function could be optimized but very little gained
  317. // only need to check every signature_block_size element to see if it matches
  318. } while (random_el == 0 || vector_contains(z, random_el, code_length));
  319. // This cannot be shortened with a memset because gf not full byte size;
  320. for (j = 0; j < signature_block_size; j++) {
  321. z[(i * signature_block_size) + j] = random_el;
  322. }
  323. }
  324. if (NULL
  325. == (diagonal_z_matrix = diagonal_matrix(z, code_length, code_length))) {
  326. PRINT_DEBUG("Failed to create diagonal_matrix\n");
  327. goto failout;
  328. }
  329. PRINT_DEBUG("Critical section\n");
  330. H3 = matrix_multiply(H_cauchy, diagonal_z_matrix);
  331. PRINT_DEBUG("DONE Critical section\n");
  332. memcpy(H->data, H3->data, sizeof(gf) * H3->rows * H3->cols);
  333. PRINT_DEBUG("H3 row cols = %d %d \n", H3->rows, H3->cols);
  334. PRINT_DEBUG("free 1 \n");
  335. for (i = 0; i < code_length; i++) {
  336. pol = 1;
  337. for (j = 0; j < signature_block_size; j++) {
  338. sum_u_v = (v[i] ^ u[j]);
  339. result = gf_pow_f_q_m(sum_u_v, pol_deg);
  340. pol = gf_q_m_mult(pol, result);
  341. }
  342. y[i] = gf_div_f_q_m(z[i], pol);
  343. }
  344. ret_val = EXIT_SUCCESS;
  345. failout: free_matrix(H3);
  346. PRINT_DEBUG("free 2 \n");
  347. free_matrix(diagonal_z_matrix);
  348. return ret_val;
  349. }
  350. void project_H_on_F_q(const matrix *H, matrix *Hbase) {
  351. int k, i, j;
  352. int nr_rows = H->rows;
  353. int nr_cols = H->cols;
  354. PRINT_DEBUG("project_H on f_q\n");
  355. for (k = 0; k < extension; k++) {
  356. for (i = 0; i < nr_rows; i++) {
  357. for (j = 0; j < nr_cols; j++) {
  358. Hbase->data[(k * nr_rows + i) * nr_cols + j] =
  359. relative_field_representation(H->data[i * nr_cols + j],
  360. k);
  361. }
  362. }
  363. }
  364. }
  365. int generate_systematic_matrix(const matrix* Hbase) {
  366. int mm, i, j, l = 0;
  367. int num_cols = Hbase->cols;
  368. int num_rows = Hbase->rows;
  369. gf invPiv = 1;
  370. gf piv_align;
  371. for (i = 0; i < num_rows; i++) {
  372. l = 0;
  373. j = i + num_cols - num_rows;
  374. if (Hbase->data[(i * num_cols) + j] == 0) { //We're looking for a non-zero pivot
  375. //printf("search Pivot\n");
  376. for (l = i + 1; l < num_rows; l++) {
  377. if (Hbase->data[l * num_cols + j]) {
  378. //printf("Find Pivot\n");
  379. for (mm = 0; mm < num_cols; mm++) {
  380. Hbase->data[(l * num_cols) + mm] ^= Hbase->data[(i
  381. * num_cols) + mm];
  382. Hbase->data[(i * num_cols) + mm] ^= Hbase->data[(l
  383. * num_cols) + mm];
  384. Hbase->data[(l * num_cols) + mm] ^= Hbase->data[(i
  385. * num_cols) + mm];
  386. }
  387. break;
  388. }
  389. }
  390. }
  391. if (l == num_rows && (i != (num_rows - 1))) {
  392. printf("Non systematic Matrix %d\num_cols", l);
  393. return EXIT_FAILURE;
  394. }
  395. // if (test == 1) { // We switches the lines l and i
  396. // test = 0;
  397. // //printf("Permut line\n");
  398. // //temp=P[i+n-num_rows];
  399. // //P[i+n-num_rows]=P[j];
  400. // //P[j]=temp;
  401. // }
  402. // Matrix standardization
  403. if (Hbase->data[(i * num_cols) + j] != 1) {
  404. invPiv = gf_inv(Hbase->data[(i * num_cols) + j]);
  405. Hbase->data[(i * num_cols) + j] = 1;
  406. // for (mm = 0; mm < num_cols; mm++) {
  407. // if (mm != j) {
  408. // // continue;
  409. // Hbase->data[(i * num_cols) + mm] = gf_mult(
  410. // Hbase->data[(i * num_cols) + mm], invPiv);
  411. // }
  412. // }
  413. for (mm = 0; mm < j; mm++) {
  414. Hbase->data[(i * num_cols) + mm] = gf_mult(
  415. Hbase->data[(i * num_cols) + mm], invPiv);
  416. }
  417. for (mm = j + 1; mm < num_cols; mm++) {
  418. Hbase->data[(i * num_cols) + mm] = gf_mult(
  419. Hbase->data[(i * num_cols) + mm], invPiv);
  420. }
  421. }
  422. //Here we do the elimination on column i + num_cols-num_rows
  423. // TODO: BLOCKING LOOP
  424. // for (l = 0; l < num_rows; l++) {
  425. // if (l != i) {
  426. // if (Hbase->data[(l * num_cols) + j]) {
  427. // piv_align = Hbase->data[(l * num_cols) + j];
  428. // for (mm = 0; mm < num_cols; mm++) {
  429. // Hbase->data[(l * num_cols) + mm] ^= gf_mult(piv_align,Hbase->data[(i * num_cols) + mm]);
  430. // }
  431. // }
  432. // }
  433. // }
  434. for (l = 0; l < i; l++) {
  435. if (Hbase->data[(l * num_cols) + j]) {
  436. piv_align = Hbase->data[(l * num_cols) + j];
  437. for (mm = 0; mm < num_cols; mm++) {
  438. Hbase->data[(l * num_cols) + mm] ^= gf_mult(piv_align,
  439. Hbase->data[(i * num_cols) + mm]);
  440. }
  441. }
  442. }
  443. for (l = i + 1; l < num_rows; l++) {
  444. if (Hbase->data[(l * num_cols) + j]) {
  445. piv_align = Hbase->data[(l * num_cols) + j];
  446. for (mm = 0; mm < num_cols; mm++) {
  447. Hbase->data[(l * num_cols) + mm] ^= gf_mult(piv_align,
  448. Hbase->data[(i * num_cols) + mm]);
  449. }
  450. }
  451. }
  452. }
  453. return 0;
  454. }
  455. /*
  456. * generate_public_key
  457. * Function used to generate the public key
  458. */
  459. int generate_public_key(const matrix *Hbase, matrix *G) {
  460. int num_cols, num_rows, i;
  461. matrix *M, *m_temp, *m_transposed, *final;
  462. if (EXIT_FAILURE == generate_systematic_matrix(Hbase)) {
  463. PRINT_DEBUG("Failed to generate_systematic_matrix\n");
  464. return EXIT_FAILURE;
  465. }
  466. num_cols = Hbase->cols;
  467. num_rows = Hbase->rows;
  468. M = submatrix(Hbase, 0, 0, num_rows, (num_cols - num_rows));
  469. m_transposed = transpose_matrix(M);
  470. free_matrix(M);
  471. m_temp = make_matrix((num_cols - num_rows), (num_cols - num_rows));
  472. for (i = 0; i < (num_cols - num_rows); i++)
  473. m_temp->data[i * (num_cols - num_rows) + i] = 1;
  474. // TODO augment is only used here. We could save memory usages by passing in
  475. // G to this function
  476. final = augment(m_temp, m_transposed);
  477. free_matrix(m_temp);
  478. free_matrix(m_transposed);
  479. memcpy(G->data, final->data, final->rows * final->cols * sizeof(gf));
  480. free_matrix(final);
  481. return EXIT_SUCCESS;
  482. }
  483. int key_pair_generation(unsigned char *pk, unsigned char *sk) {
  484. gf v[code_length] = { 0 };
  485. gf y[code_length] = { 0 };
  486. matrix G;
  487. G.cols = code_length;
  488. G.rows = code_length - ((signature_block_size * pol_deg) * extension);
  489. gf data_G[code_length
  490. * (code_length - ((signature_block_size * pol_deg) * extension))] =
  491. { 0 };
  492. G.data = data_G;
  493. key_gen(v, y, &G);
  494. store_public_key(&G, pk);
  495. printf("[ ");
  496. for (int i = 0; i < code_length; i++) {
  497. printf(" %" PRIu16 " ,", v[i]);
  498. }
  499. printf("]\n");
  500. printf("[ ");
  501. for (int i = 0; i < code_length; i++) {
  502. printf(" %" PRIu16 " ,", y[i]);
  503. }
  504. printf("]\n");
  505. store_secret_key(v, y, sk);
  506. return 0;
  507. }
  508. void key_gen(gf *v, gf *y, matrix *G) {
  509. int ret_value = 0;
  510. gf signature_h[code_length];
  511. gf *elements_in_F_q_m = NULL;
  512. gf *elements_in_F_q_m_constant = NULL;
  513. gf u[signature_block_size];
  514. long build_support_failures = 0;
  515. long build_dyadic_sig_failures = 0;
  516. matrix H_cauchy;
  517. gf data_cauchy[signature_block_size * pol_deg * code_length] = { 0 };
  518. H_cauchy.rows = signature_block_size * pol_deg;
  519. H_cauchy.cols = code_length;
  520. H_cauchy.data = data_cauchy;
  521. matrix H; // TODO H.data is filled allocated in build_trapdoor
  522. gf data_H[signature_block_size * pol_deg * code_length] = { 0 };
  523. H.rows = signature_block_size * pol_deg;
  524. H.cols = code_length;
  525. H.data = data_H;
  526. PRINT_DEBUG("H row col = %d %d\n", H.rows, H.cols);
  527. matrix Hbase;
  528. Hbase.rows = (signature_block_size * pol_deg) * extension;
  529. Hbase.cols = code_length;
  530. gf data_Hbase[signature_block_size * pol_deg * code_length * extension] = {
  531. 0 };
  532. Hbase.data = data_Hbase;
  533. PRINT_DEBUG("Key Gen start\n");
  534. if (NULL == (elements_in_F_q_m_constant = calloc(F_q_m_size, sizeof(gf)))) {
  535. PRINT_DEBUG("Failed to allocate memory for elements_in_F_q_m");
  536. goto failout;
  537. }
  538. // Only generate_elements in F_q_m once and copied when used in build_support()
  539. // With starting value of 1
  540. generate_elements_in_order(elements_in_F_q_m_constant, 1, F_q_m_size);
  541. do {
  542. if (NULL == (elements_in_F_q_m = calloc(F_q_m_size, sizeof(gf)))) {
  543. PRINT_DEBUG("Failed to allocate memory for elements_in_F_q_m");
  544. goto failout;
  545. }
  546. memcpy(elements_in_F_q_m, elements_in_F_q_m_constant,
  547. F_q_m_size * sizeof(gf));
  548. memset(signature_h, 0, code_length * sizeof(gf));
  549. memset(u, 0, signature_block_size * sizeof(gf));
  550. do {
  551. build_support_failures++;
  552. ret_value = build_dyadic_signature(signature_h);
  553. if (ret_value == EXIT_SUCCESS) {
  554. build_support(signature_h, u, v, elements_in_F_q_m);
  555. } else {
  556. build_dyadic_sig_failures++;
  557. build_support_failures--;
  558. }
  559. if (build_support_failures % 100 == 0) {
  560. PRINT_DEBUG("interations %ld vs %ld\n", build_support_failures,
  561. build_dyadic_sig_failures);
  562. }
  563. } while (ret_value != EXIT_SUCCESS || is_vectors_disjoint(u, v)
  564. || is_vector_disjoint(v, code_length)
  565. || is_vector_disjoint(u, signature_block_size));
  566. free(elements_in_F_q_m);
  567. elements_in_F_q_m = NULL;
  568. build_cauchy_matrix(u, v, &H_cauchy);
  569. if (EXIT_FAILURE
  570. == (ret_value = build_trapdoor(&H_cauchy, v, u, y, &H))) {
  571. PRINT_DEBUG("Failed to build_trapdoor\n");
  572. continue;
  573. }
  574. project_H_on_F_q(&H, &Hbase);
  575. PRINT_DEBUG("Generating public_key\n");
  576. ret_value = generate_public_key(&Hbase, G);
  577. } while (ret_value);
  578. failout: free(elements_in_F_q_m);
  579. free(elements_in_F_q_m_constant);
  580. return;
  581. }