/**
* \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
*
*
* ⎧ 2ᵖ⁻¹ ≡ 1 (mod p) ⎧ p | (a-1)
* ⎨ → a ≡ 2^(B!) ≡ 1 (mod p) → ⎨ → p | gcd(a-1, N)
* ⎩ p-1 | B! ⎩ p | N
*
*
* And gcd(a-1, N) is a non-trivial factor of N, unless a = 1.
*/
#include
#include
#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
};