keygeneration.c 16 KB

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