fermat.c 1.9 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192
  1. /**
  2. * \file Fermat's factorization
  3. *
  4. * According to the Digital Signature Standard, |p - q| = Δ < √N 2⁻¹⁰⁰
  5. * Otherwise, it is possible to factorize N using Fermat's Factorization.
  6. * Specifically, we try to solve
  7. * a² - N = b²
  8. * which can be algebreically factorable as
  9. * N = (a-b)(a+b), where p = (a-b) q = (a+b)
  10. * and by construction a ~ ⌈√N⌉
  11. */
  12. #include <assert.h>
  13. #include <openssl/bn.h>
  14. #include <openssl/rsa.h>
  15. #include <openssl/x509.h>
  16. #include "qa/questions/questions.h"
  17. #include "qa/questions/qarith.h"
  18. static RSA *
  19. fermat_question_ask(const RSA *rsa)
  20. {
  21. BN_CTX *ctx;
  22. BIGNUM *a, *b, *a2, *b2;
  23. BIGNUM *n;
  24. BIGNUM *tmp, *rem, *dssdelta;
  25. RSA *ret = NULL;
  26. ctx = BN_CTX_new();
  27. n = rsa->n;
  28. a = BN_new();
  29. b = BN_new();
  30. a2 = BN_new();
  31. b2 = BN_new();
  32. rem = BN_new();
  33. tmp = BN_new();
  34. dssdelta = BN_new();
  35. BN_sqrtmod(tmp, rem, n, ctx);
  36. /* Δ = |p - q| = |a + b - a + b| = |2b| > √N 2⁻¹⁰⁰ */
  37. BN_rshift(dssdelta, tmp, 101);
  38. /* a² = (⌊√N⌋ + 1)² = N + 1 + 2⌊√N⌋ */
  39. BN_copy(a, tmp);
  40. BN_uiadd1(a);
  41. /* b² = a² - N */
  42. BN_sub(b2, a2, n);
  43. do {
  44. /* b² += 2a + 1 */
  45. BN_lshift(tmp, a, 1);
  46. BN_uiadd1(tmp);
  47. BN_uadd(b2, b2, tmp);
  48. /* a += 1 */
  49. BN_uiadd1(a);
  50. /* b */
  51. BN_sqrtmod(b, rem, b2, ctx);
  52. } while (!BN_is_zero(rem) && BN_ucmp(b, dssdelta) == 1);
  53. if (BN_is_zero(rem)) {
  54. /* p, q found :) */
  55. ret = RSA_new();
  56. ret->q = BN_new();
  57. ret->p = BN_new();
  58. BN_sqrtmod(a, rem, a2, ctx);
  59. assert(BN_is_zero(rem));
  60. BN_uadd(ret->p, a, b);
  61. BN_usub(ret->q, a, b);
  62. }
  63. BN_CTX_free(ctx);
  64. BN_free(a);
  65. BN_free(b);
  66. BN_free(a2);
  67. BN_free(b2);
  68. BN_free(dssdelta);
  69. return ret;
  70. }
  71. qa_question_t FermatQuestion = {
  72. .name = "fermat",
  73. .pretty_name = "Fermat's Factorization",
  74. .ask_rsa = fermat_question_ask,
  75. .ask_crt = NULL,
  76. .test = NULL,
  77. .setup = NULL,
  78. .teardown = NULL,
  79. };