pollard.c 2.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127
  1. /**
  2. * \file pollard.c
  3. *
  4. * \brief Pollard's (p-1) factorization algorithm.
  5. *
  6. * This file contains an implementations of Pollard's (p-1) algorithm, used to
  7. * attack the public modulus of RSA.
  8. *
  9. * Consider the public modulus N = pq. Now,
  10. * (p-1) = q₀ᵉ⁰q₁ᵉ¹… qₖᵉᵏ . q₀ᵉ⁰ < q₁ᵉ¹ < … < qₖᵉᵏ ≤ B
  11. * implies that (p-1) | B! , since all factors of (p-1) belongs to {1, …, B}.
  12. * Consider a ≡ 2^(B!) (mod N)
  13. * a = 2^(B!) + kN = 2^(B!) + kqp → a ≡ 2^(B!) (mod p)
  14. * Since
  15. * <pre>
  16. *
  17. * ⎧ 2ᵖ⁻¹ ≡ 1 (mod p) ⎧ p | (a-1)
  18. * ⎨ → a ≡ 2^(B!) ≡ 1 (mod p) → ⎨ → p | gcd(a-1, N)
  19. * ⎩ p-1 | B! ⎩ p | N
  20. *
  21. * </pre>
  22. * And gcd(a-1, N) is a non-trivial factor of N, unless a = 1.
  23. */
  24. #include <openssl/x509.h>
  25. #include <openssl/err.h>
  26. #include "qa/questions/questions.h"
  27. #include "qa/questions/qarith.h"
  28. #include "qa/questions/qpollard.h"
  29. static BIGNUM *two;
  30. static int
  31. pollard1_question_setup(void)
  32. {
  33. /* create 2 */
  34. two = BN_new();
  35. BN_one(two);
  36. BN_uadd(two, two, BN_value_one());
  37. return 1;
  38. }
  39. static int
  40. pollard1_question_teardown(void)
  41. {
  42. BN_free(two);
  43. return 1;
  44. }
  45. /**
  46. * \brief Pollard (p-1) factorization.
  47. *
  48. * Trivially the algorithm computes a = 2^(B!) (mod N), and then verifies that
  49. * gcd(a-1, N) is a nontrivial factor of N.
  50. *
  51. * According to Wikipedia™,
  52. * « By Dixon's theorem, the probability that the largest factor of such a
  53. * number is less than (p − 1)^ε is roughly ε^(−ε); so there is a probability of
  54. * about 3^(−3) = 1/27 that a B value of n^(1/6) will yield a factorisation.»
  55. *
  56. */
  57. static RSA*
  58. pollard1_question_ask_rsa(const RSA *rsa)
  59. {
  60. RSA *ret = NULL;
  61. BIGNUM *a, *B, *a1;
  62. BIGNUM *gcd, *rem;
  63. BIGNUM *n;
  64. BIGNUM *p, *q;
  65. BN_CTX *ctx;
  66. n = rsa->n;
  67. a = BN_new();
  68. B = BN_new();
  69. a1 = BN_new();
  70. gcd = BN_new();
  71. rem = BN_new();
  72. ctx = BN_CTX_new();
  73. /* take ⁸√N */
  74. BN_sqrtmod(gcd, rem, n, NULL);
  75. BN_sqrtmod(B, rem, gcd, NULL);
  76. /* compute 2^(B!) */
  77. for (BN_copy(a, two), BN_one(gcd);
  78. !(BN_is_zero(B) || !BN_is_one(gcd) || BN_cmp(gcd, n)==0);
  79. BN_usub(B, B, BN_value_one())) {
  80. BN_mod_exp(a, a, B, n, ctx);
  81. /* p ≟ gcd(a-1, N) */
  82. BN_usub(a1, a, BN_value_one());
  83. BN_gcd(gcd, a1, n, ctx);
  84. }
  85. /* Either p or q found :) */
  86. if (!BN_is_zero(B)) {
  87. ret = RSA_new();
  88. ret->n = rsa->n;
  89. ret->e = rsa->e;
  90. ret->q = q = BN_new();
  91. ret->p = p = BN_dup(gcd);
  92. BN_div(q, NULL, n, gcd, ctx);
  93. }
  94. BN_free(a);
  95. BN_free(B);
  96. BN_free(a1);
  97. BN_free(gcd);
  98. BN_free(rem);
  99. BN_CTX_free(ctx);
  100. return ret;
  101. }
  102. qa_question_t PollardQuestion = {
  103. .name = "pollard1",
  104. .pretty_name = "Pollard's (p-1) factorization",
  105. .setup = pollard1_question_setup,
  106. .teardown = pollard1_question_teardown,
  107. .test = NULL,
  108. .ask_rsa = pollard1_question_ask_rsa,
  109. .ask_crt = NULL
  110. };