util.c 8.3 KB

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