1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192 |
- /**
- * \file Fermat's factorization
- *
- * According to the Digital Signature Standard, |p - q| = Δ < √N 2⁻¹⁰⁰
- * Otherwise, it is possible to factorize N using Fermat's Factorization.
- * Specifically, we try to solve
- * a² - N = b²
- * which can be algebreically factorable as
- * N = (a-b)(a+b), where p = (a-b) q = (a+b)
- * and by construction a ~ ⌈√N⌉
- */
- #include <assert.h>
- #include <openssl/bn.h>
- #include <openssl/rsa.h>
- #include <openssl/x509.h>
- #include "qa/questions/questions.h"
- #include "qa/questions/qarith.h"
- static RSA *
- fermat_question_ask(const RSA *rsa)
- {
- BN_CTX *ctx;
- BIGNUM *a, *b, *a2, *b2;
- BIGNUM *n;
- BIGNUM *tmp, *rem, *dssdelta;
- RSA *ret = NULL;
- ctx = BN_CTX_new();
- n = rsa->n;
- a = BN_new();
- b = BN_new();
- a2 = BN_new();
- b2 = BN_new();
- rem = BN_new();
- tmp = BN_new();
- dssdelta = BN_new();
- BN_sqrtmod(tmp, rem, n, ctx);
- /* Δ = |p - q| = |a + b - a + b| = |2b| > √N 2⁻¹⁰⁰ */
- BN_rshift(dssdelta, tmp, 101);
- /* a² = (⌊√N⌋ + 1)² = N + 1 + 2⌊√N⌋ */
- BN_copy(a, tmp);
- BN_uiadd1(a);
- /* b² = a² - N */
- BN_sub(b2, a2, n);
- do {
- /* b² += 2a + 1 */
- BN_lshift(tmp, a, 1);
- BN_uiadd1(tmp);
- BN_uadd(b2, b2, tmp);
- /* a += 1 */
- BN_uiadd1(a);
- /* b */
- BN_sqrtmod(b, rem, b2, ctx);
- } while (!BN_is_zero(rem) && BN_ucmp(b, dssdelta) == 1);
- if (BN_is_zero(rem)) {
- /* p, q found :) */
- ret = RSA_new();
- ret->q = BN_new();
- ret->p = BN_new();
- BN_sqrtmod(a, rem, a2, ctx);
- assert(BN_is_zero(rem));
- BN_uadd(ret->p, a, b);
- BN_usub(ret->q, a, b);
- }
- BN_CTX_free(ctx);
- BN_free(a);
- BN_free(b);
- BN_free(a2);
- BN_free(b2);
- BN_free(dssdelta);
- return ret;
- }
- qa_question_t FermatQuestion = {
- .name = "fermat",
- .pretty_name = "Fermat's Factorization",
- .ask_rsa = fermat_question_ask,
- .ask_crt = NULL,
- .test = NULL,
- .setup = NULL,
- .teardown = NULL,
- };
|