dixon.c 6.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280
  1. /**
  2. * \file dixon.c
  3. * \brief An implementation of Dixon's Attack using bignums.
  4. *
  5. * Given a non-empty set B of primes, called factor-base, and
  6. * given a non-empty set of random numbers R, s.t. ∀ r ∈ R, s ≡ r² (mod N) is B-smooth.
  7. *
  8. * Try to find
  9. * U ⊂ R | (Πᵤ rᵢ)² ≡ Π s (mod N) and by defining x ≝ Πᵤ rᵢ, y ≝ √(Π s)
  10. * x² ≡ y² (mod N)
  11. * Asserting that x ≢ y (mod N) we claim to have found the two non-trivial
  12. * factors of N by computing gcd(x+y, N) and gcd(x-y, N).
  13. *
  14. * \note N = pq is assumed to be the public modulus,
  15. * while e, d . ed ≡ 1 (mod φ(N)) are respectively the public and the private
  16. * exponent.
  17. */
  18. #include <assert.h>
  19. #include <stdlib.h>
  20. #include <strings.h>
  21. #include <openssl/bn.h>
  22. #include "qa/questions/qarith.h"
  23. #include "qa/questions/qstrings.h"
  24. #include "qa/questions/questions.h"
  25. #define EPOCHS 100
  26. #define REPOP_EPOCHS 50
  27. #define BPOOL_EXTEND_STEP 42
  28. #define BPOOL_STARTING_BITS 7
  29. #define RPOOL_EXTEND_STEP 42
  30. #define U_SIZE 10
  31. #define qa_rand rand
  32. static BIGNUM* zero;
  33. /**
  34. * \struct dixon_number_t
  35. * \brief Auxiliary structure holding informations for R_pool.
  36. */
  37. typedef struct dixon_number {
  38. BIGNUM *r; /**< the random number which have been chosen */
  39. BIGNUM *s; /**< s ≡ r² (mod N) */
  40. BIGNUM **v; /**< a cached vectors holding the exponents for the prime
  41. * factorization of s. */
  42. } dixon_number_t;
  43. /** Pool of random numbers, i.e. the set R. */
  44. dixon_number_t *R_pool = NULL;
  45. static size_t R_size = 0;
  46. /** Pool of prime numbers, i.e. B, the factor base. */
  47. static BIGNUM** B_pool = NULL;
  48. static size_t B_size = 0;
  49. /**
  50. * \brief Extends the factor base, and then adjusts R_pool
  51. *
  52. */
  53. static void extend_B_pool(int max_bits)
  54. {
  55. size_t i, j, old_B_size;
  56. int bits;
  57. old_B_size = B_size;
  58. B_size += BPOOL_EXTEND_STEP;
  59. /* check for size_t overflow */
  60. assert(old_B_size < B_size);
  61. B_pool = realloc(B_pool, B_size * sizeof(BIGNUM*));
  62. for (i=old_B_size; i!=B_size; i++) {
  63. bits = 1 + qa_rand() % max_bits;
  64. B_pool[i] = BN_generate_prime(NULL, bits, 0, NULL, NULL, NULL, NULL);
  65. }
  66. /* reallocate space for vectors in R_pool */
  67. for (i=0; i!=R_size; i++) {
  68. R_pool[i].v = realloc(R_pool[i].v, sizeof(BIGNUM*) * B_size);
  69. for (j=old_B_size; j!=B_size; j++) R_pool[i].v[j] = NULL;
  70. }
  71. }
  72. #define B_pool_free() free(B_pool)
  73. /**
  74. * We have two possible choices here, for generating a valid random rumber
  75. * satisfying Dixon's theorem requirements.
  76. *
  77. * Alg. 1 - 1. Start by generating a random r such that r > √N,
  78. * 2. Calculate s ≡ r² (mod N)
  79. * 3. Factorize s using B and see if that's B-smooth
  80. * This algorithm shall have complexity O(k + N² + |B|lg N)
  81. *
  82. * Alg. 2 - 1. Generate the random exponents for s, {e₀, e₁, …, eₘ} where m = |B|
  83. * 2. From the generated exponents, calculate s = p₀^e₀·p₁^e₁·…·pₘ^eₘ
  84. * knowing that s < N
  85. * 3. Find an r = √(s + tN) , t ∈ {1..N-1}
  86. * This algorithm shall have complexity O(k|B| + (N-1)lg N)
  87. */
  88. static void extend_R_pool(BIGNUM* N)
  89. {
  90. const size_t old_R_size = R_size;
  91. size_t i, j;
  92. int e_bits;
  93. BN_CTX *ctx = BN_CTX_new();
  94. BIGNUM
  95. *e,
  96. *tmp = BN_new(),
  97. *rem = BN_new(),
  98. *t = BN_new();
  99. dixon_number_t *d;
  100. R_size += RPOOL_EXTEND_STEP;
  101. /* size_t overflow */
  102. assert(R_size > old_R_size);
  103. R_pool = realloc(R_pool, sizeof(dixon_number_t));
  104. /*
  105. * XXX. There is much more to think about this.
  106. * We are trying to generate some random exponents e₀…eₖ such that s < N .
  107. * Hence, log(N) = ae₀ + be₁ + … + leₖ
  108. */
  109. e_bits = BN_num_bits(N) / 5;
  110. for (i=old_R_size; i!= R_size; i++) {
  111. d = &R_pool[i];
  112. d->s = BN_new();
  113. d->r = BN_new();
  114. /* generate exponents and calculate s */
  115. for (j=0; j != B_size && BN_cmp(N, d->s) == 1; j++) {
  116. e = d->v[j] = BN_new();
  117. /* XXX. better check for error here. */
  118. BN_pseudo_rand(e, e_bits, -1, 0);
  119. BN_exp(tmp, B_pool[j], e, ctx);
  120. BN_mul(d->s, tmp, d->s, ctx);
  121. }
  122. /* Find an r = √(s + tN) , t ∈ {1..N-1} */
  123. BN_sqr(tmp, N, ctx);
  124. BN_one(t);
  125. for (BN_add(t, t, N); BN_cmp(tmp, t) == 1; BN_add(t, t, N))
  126. if (BN_sqrtmod(d->r, rem, t, ctx)) break;
  127. }
  128. BN_CTX_free(ctx);
  129. BN_free(rem);
  130. BN_free(tmp);
  131. BN_free(t);
  132. }
  133. #define R_pool_free() free(R_pool)
  134. int dixon_question_setup(void)
  135. {
  136. extern BIGNUM* zero;
  137. zero = BN_new();
  138. BN_zero(zero);
  139. extend_B_pool(BPOOL_STARTING_BITS);
  140. return 0;
  141. }
  142. int dixon_question_teardown(void) {
  143. BN_free(zero);
  144. B_pool_free();
  145. R_pool_free();
  146. return 0;
  147. }
  148. int dixon_question_ask_rsa(RSA *rsa) {
  149. /* key data */
  150. BIGNUM
  151. *n,
  152. *p, *q;
  153. /* x, y */
  154. BIGNUM
  155. *x, *x2,
  156. *y, *y2;
  157. BN_CTX *ctx;
  158. /* U ⊆ R */
  159. ssize_t *U_bucket;
  160. /* internal data */
  161. int epoch;
  162. BIGNUM *tmp;
  163. char *even_powers;
  164. size_t i, j, k;
  165. n = rsa->n;
  166. U_bucket = malloc(sizeof(ssize_t) * U_SIZE);
  167. even_powers = malloc(sizeof(char) * B_size);
  168. ctx = BN_CTX_new();
  169. x = BN_new();
  170. y = BN_new();
  171. x2 = BN_new();
  172. y2 = BN_new();
  173. tmp = BN_new();
  174. /* mainloop: iterate until a key is found, or convergence. */
  175. for (epoch=0; epoch < EPOCHS; epoch++) {
  176. /* depending on the epoch, populate R_pool and B_pool */
  177. if (epoch % REPOP_EPOCHS) extend_R_pool(n);
  178. /* reset variables */
  179. for (i=0; i!=U_SIZE; i++) U_bucket[i] = -1;
  180. bzero(even_powers, B_size * sizeof(char));
  181. j = 0;
  182. /* choose a subset of R such that the product of primes can be squared */
  183. do {
  184. for (i=0; i!=B_size && j < U_SIZE; i++) {
  185. /* choose whether to take or not R_pool[i] */
  186. if (qa_rand() % 2) continue;
  187. /* add the number */
  188. U_bucket[j++] = i;
  189. for (k=0; k!=B_size; k++)
  190. even_powers[k] ^= BN_is_odd(R_pool[i].v[j]);
  191. }
  192. } while (!is_vzero(even_powers, B_size * sizeof(char)));
  193. /* let x = Πᵢ rᵢ , y² = Πᵢ sᵢ */
  194. BN_one(x);
  195. BN_one(y2);
  196. for (i=0; i != U_SIZE; i++) {
  197. if (U_bucket[i] == -1) continue;
  198. j = U_bucket[i];
  199. BN_mul(x, x, R_pool[j].r, ctx);
  200. BN_mul(y2, y2, R_pool[j].s, ctx);
  201. }
  202. /* retrieve x² from x */
  203. BN_sqr(x2, x, ctx);
  204. /* retrieve y from y² */
  205. /* test: shall *always* be a perfect square */
  206. if (!BN_sqrtmod(y, tmp, y2, ctx)) continue;
  207. /* test: assert that x ≡ y (mod N) */
  208. if (!BN_cmp(x, y)) continue;
  209. /* p, q found :) */
  210. p = BN_new();
  211. q = BN_new();
  212. BN_uadd(tmp, x, y);
  213. BN_gcd(p, tmp, n, ctx);
  214. assert(!BN_is_one(p) && BN_cmp(p, n));
  215. BN_usub(tmp, x, y);
  216. BN_gcd(q, tmp, n, ctx);
  217. assert(!BN_is_one(q) && BN_cmp(q, n));
  218. }
  219. BN_free(x);
  220. BN_free(x2);
  221. BN_free(y);
  222. BN_free(y2);
  223. free(U_bucket);
  224. free(even_powers);
  225. return 0;
  226. }
  227. qa_question_t DixonQuestion = {
  228. .name = "dixon",
  229. .pretty_name = "Dixon's Factorization",
  230. .setup = dixon_question_setup,
  231. .teardown = dixon_question_teardown,
  232. .test = NULL,
  233. .ask_rsa = dixon_question_ask_rsa,
  234. .ask_crt = NULL
  235. };