bachelor/src/questions/pollard.c

/**
 * \file pollard.c
 *
 * \brief Pollard's (p-1) factorization algorithm.
 *
 * This file contains an implementations of Pollard's (p-1) algorithm, used to
 * attack the public modulus of RSA.
 *
 * Consider the public modulus N = pq. Now,
 *  (p-1) = q₀ᵉ⁰q₁ᵉ¹… qₖᵉᵏ .  q₀ᵉ⁰ < q₁ᵉ¹ < … < qₖᵉᵏ ≤ B
 * implies that  (p-1) | B! , since all factors of (p-1) belongs to {1, …, B}.
 * Consider a ≡ 2^(B!) (mod N)
 *   a = 2^(B!) + kN  = 2^(B!) + kqp → a ≡ 2^(B!) (mod p)
 * Since
 * <pre>
 *
 *   ⎧ 2ᵖ⁻¹ ≡ 1 (mod p)                              ⎧ p | (a-1)
 *   ⎨                  →  a ≡ 2^(B!) ≡ 1 (mod p) →  ⎨           → p | gcd(a-1, N)
 *   ⎩ p-1 | B!                                      ⎩ p | N
 *
 * </pre>
 * And gcd(a-1, N) is a non-trivial factor of N, unless a = 1.
 */

#include <openssl/x509.h>
#include <openssl/err.h>

#include "qa/questions/questions.h"
#include "qa/questions/qarith.h"
#include "qa/questions/qpollard.h"


static BIGNUM *two;

static int
pollard1_question_setup(void)
{
  /* create 2 */
  two = BN_new();
  BN_one(two);
  BN_uadd(two, two, BN_value_one());
  return 1;
}

static int
pollard1_question_teardown(void)
{
  BN_free(two);
  return 1;
}


/**
 * \brief Pollard (p-1) factorization.
 *
 * Trivially the algorithm computes a = 2^(B!) (mod N), and then verifies that
 * gcd(a-1, N) is a nontrivial factor of N.
 *
 * According to Wikipedia™,
 * « By Dixon's theorem, the probability that the largest factor of such a
 * number is less than (p − 1)^ε is roughly ε^(−ε); so there is a probability of
 * about 3^(−3) = 1/27 that a B value of n^(1/6) will yield a factorisation.»
 *
 */
static RSA*
pollard1_question_ask_rsa(const RSA *rsa)
{
  RSA *ret = NULL;
  BIGNUM *a, *B, *a1;
  BIGNUM *gcd, *rem;
  BIGNUM *n;
  BIGNUM *p, *q;
  BN_CTX *ctx;

  n = rsa->n;
  a = BN_new();
  B = BN_new();
  a1 = BN_new();
  gcd = BN_new();
  rem = BN_new();
  ctx = BN_CTX_new();

  /* take ⁸√N */
  BN_sqrtmod(gcd, rem, n, NULL);
  BN_sqrtmod(B, rem, gcd, NULL);
  /* compute 2^(B!) */
  for (BN_copy(a, two), BN_one(gcd);
       !(BN_is_zero(B) || !BN_is_one(gcd) || BN_cmp(gcd, n)==0);
       BN_usub(B, B, BN_value_one())) {

    BN_mod_exp(a, a, B, n, ctx);
    /* p ≟ gcd(a-1, N) */
    BN_usub(a1, a, BN_value_one());
    BN_gcd(gcd, a1, n, ctx);
  }

  /* Either p or q found :) */
  if (!BN_is_zero(B)) {
    ret = RSA_new();
    ret->n = rsa->n;
    ret->e = rsa->e;
    ret->q = q = BN_new();
    ret->p = p = BN_dup(gcd);
    BN_div(q, NULL, n, gcd, ctx);
  }

  BN_free(a);
  BN_free(B);
  BN_free(a1);
  BN_free(gcd);
  BN_free(rem);
  BN_CTX_free(ctx);

  return ret;
}


qa_question_t PollardQuestion = {
  .name = "pollard1",
  .pretty_name = "Pollard's (p-1) factorization",
  .setup = pollard1_question_setup,
  .teardown = pollard1_question_teardown,
  .test = NULL,
  .ask_rsa = pollard1_question_ask_rsa,
  .ask_crt = NULL
};