wiener.c 5.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241
  1. /**
  2. * \file wiener.c
  3. * \brief An implementation of Wiener's Attack using bignums.
  4. *
  5. * Wiener's atttack states that:
  6. * given N = pq the public modulus, the couple e, d . ed ≡ 1 (mod φ(N))
  7. * respectively the private and public exponent,
  8. * given p < q < 2p and d < ⅓ ⁴√N,
  9. * one can efficently recover d knowing only <N, e>.
  10. *
  11. */
  12. #include <math.h>
  13. #include <stdlib.h>
  14. #include <openssl/x509.h>
  15. #include <openssl/rsa.h>
  16. #include <openssl/bn.h>
  17. #include "qa/questions/questions.h"
  18. #include "qa/questions/qarith.h"
  19. #include "qa/questions/qwiener.h"
  20. cf_t* cf_new(void)
  21. {
  22. cf_t *f;
  23. f = (cf_t *) malloc(sizeof(cf_t));
  24. size_t i;
  25. for (i=0; i!=3; i++) {
  26. f->fs[i].h = BN_new();
  27. f->fs[i].k = BN_new();
  28. }
  29. f->a = BN_new();
  30. f->x.h = BN_new();
  31. f->x.k = BN_new();
  32. f->ctx = BN_CTX_new();
  33. return f;
  34. }
  35. void cf_free(cf_t* f)
  36. {
  37. size_t i;
  38. for (i=0; i!=3; i++) {
  39. BN_free(f->fs[i].h);
  40. BN_free(f->fs[i].k);
  41. }
  42. BN_free(f->a);
  43. BN_free(f->x.h);
  44. BN_free(f->x.k);
  45. free(f);
  46. }
  47. /**
  48. * \brief Initialized a continued fraction.
  49. *
  50. * A continued fraction for a floating number x can be expressed as a series
  51. * <a₀; a₁, a₂…, aₙ>
  52. * such that
  53. * <pre>
  54. *
  55. * 1
  56. * x = a₀ + ⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽
  57. * 1
  58. * a₁ + ⎽⎽⎽⎽⎽⎽⎽⎽⎽
  59. * a₂ + …
  60. *
  61. * </pre>
  62. * , where for each i < n, there exists an approximation hᵢ / kᵢ.
  63. * By definition,
  64. * a₋₁ = 0
  65. * h₋₁ = 1 h₋₂ = 0
  66. * k₋₁ = 0 k₋₂ = 1
  67. *
  68. * \param f A continued fraction structure. If f is NULL, a new one is
  69. * allocated.
  70. * \param num Numerator to be used as initial numerator for the fraction to be
  71. * approximated.
  72. * \param den Denominator to be used as denominator for the fraction to be
  73. * approximated.
  74. *
  75. * \return the continued fraction fiven as input.
  76. */
  77. cf_t* cf_init(cf_t* f, BIGNUM* num, BIGNUM* den)
  78. {
  79. if (!f) f = cf_new();
  80. BN_zero(f->fs[0].h);
  81. BN_one(f->fs[0].k);
  82. BN_one(f->fs[1].h);
  83. BN_zero(f->fs[1].k);
  84. f->i = 2;
  85. if (!BN_copy(f->x.h, num)) return NULL;
  86. if (!BN_copy(f->x.k, den)) return NULL;
  87. return f;
  88. }
  89. /**
  90. * \brief Produces the next fraction.
  91. *
  92. * Each new approximation hᵢ/kᵢ is defined rec ursively as:
  93. * hᵢ = aᵢhᵢ₋₁ + hᵢ₋₂
  94. * kᵢ = aᵢkᵢ₋₁ + kᵢ₋₂
  95. * Meanwhile each new aᵢ is simply the integer part of x.
  96. *
  97. *
  98. * \param f The continued fraction.
  99. * \return NULL if the previous fraction approximates at its best the number,
  100. * a pointer to the next fraction in the series othw.
  101. */
  102. bigfraction_t* cf_next(cf_t *f)
  103. {
  104. bigfraction_t *ith_fs = &f->fs[f->i];
  105. BIGNUM* rem = BN_new();
  106. if (BN_is_zero(f->x.h)) return NULL;
  107. BN_div(f->a, rem, f->x.h, f->x.k, f->ctx);
  108. /* computing hᵢ */
  109. BN_mul(f->fs[f->i].h , f->a, f->fs[(f->i-1+3) % 3].h, f->ctx);
  110. BN_uadd(f->fs[f->i].h, f->fs[f->i].h, f->fs[(f->i-2+3) % 3].h);
  111. /* computing kᵢ */
  112. BN_mul(f->fs[f->i].k , f->a, f->fs[(f->i-1+3) % 3].k, f->ctx);
  113. BN_uadd(f->fs[f->i].k, f->fs[f->i].k, f->fs[(f->i-2+3) % 3].k);
  114. f->i = (f->i + 1) % 3;
  115. /* update x. */
  116. BN_copy(f->x.h, f->x.k);
  117. BN_copy(f->x.k, rem);
  118. return ith_fs;
  119. }
  120. /*
  121. * Weiner Attack Implementation
  122. */
  123. int wiener_question_ask_rsa(RSA *rsa)
  124. {
  125. /* key data */
  126. BIGNUM *n, *e, *d, *phi;
  127. BIGNUM *p, *q;
  128. /* continued fractions coefficient, and mod */
  129. cf_t* cf;
  130. bigfraction_t *it;
  131. size_t i;
  132. BIGNUM *t, *tmp, *rem;
  133. /* equation coefficients */
  134. BIGNUM *b2, *delta;
  135. BN_CTX *ctx;
  136. int bits;
  137. phi = BN_new();
  138. tmp = BN_new();
  139. rem = BN_new();
  140. n = rsa->n;
  141. e = rsa->e;
  142. b2 = BN_new();
  143. delta = BN_new();
  144. /*
  145. * Generate the continued fractions approximating e/N
  146. */
  147. bits = BN_num_bits(n);
  148. cf = cf_init(NULL, e, n);
  149. ctx = cf->ctx;
  150. for (i=0, it = cf_next(cf);
  151. // XXX. how many keys shall I test?
  152. i!=bits && it;
  153. i++, it = cf_next(cf)) {
  154. t = it->h;
  155. d = it->k;
  156. /*
  157. * Recovering φ(N) = (ed - 1) / t
  158. * TEST1: obviously the couple {t, d} is correct → (ed-1) | t
  159. */
  160. BN_mul(phi, e, d, cf->ctx);
  161. BN_usub(tmp, phi, BN_value_one());
  162. BN_div(phi, rem, tmp, t, cf->ctx);
  163. if (!BN_is_zero(rem)) continue;
  164. // XXX. check, is it possible to fall here, assuming N, e are valid?
  165. if (BN_is_odd(phi) && BN_cmp(n, phi) == 1) continue;
  166. /*
  167. * Recovering p, q
  168. * Solving the equation
  169. * x² + [N-φ(N)+1]x + N = 0
  170. * which, after a few passages, boils down to:
  171. * x² + (p+q)x + (pq) = 0
  172. *
  173. * TEST2: φ(N) is correct → the two roots of x are integers
  174. */
  175. BN_usub(b2, n, phi);
  176. BN_uadd(b2, b2, BN_value_one());
  177. BN_rshift(b2, b2, 1);
  178. if (BN_is_zero(b2)) continue;
  179. /* delta */
  180. BN_sqr(tmp, b2, ctx);
  181. BN_usub(delta, tmp, n);
  182. if (!BN_sqrtmod(tmp, rem, delta, ctx)) continue;
  183. /* key found :) */
  184. p = BN_new();
  185. q = BN_new();
  186. BN_usub(p, b2, tmp);
  187. BN_uadd(q, b2, tmp);
  188. //printf("Primes: %s %s", BN_bn2dec(p), BN_bn2dec(q));
  189. break;
  190. }
  191. cf_free(cf);
  192. BN_free(rem);
  193. BN_free(tmp);
  194. BN_free(b2);
  195. BN_free(delta);
  196. BN_free(phi);
  197. return i;
  198. }
  199. qa_question_t WienerQuestion = {
  200. .name = "wiener",
  201. .pretty_name = "Wiener's Attack",
  202. .setup = NULL,
  203. .teardown = NULL,
  204. .test = NULL,
  205. .ask_rsa = wiener_question_ask_rsa,
  206. .ask_crt = NULL,
  207. };