123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241 |
- /**
- * \file wiener.c
- * \brief An implementation of Wiener's Attack using bignums.
- *
- * Wiener's atttack states that:
- * given N = pq the public modulus, the couple e, d . ed ≡ 1 (mod φ(N))
- * respectively the private and public exponent,
- * given p < q < 2p and d < ⅓ ⁴√N,
- * one can efficently recover d knowing only <N, e>.
- *
- */
- #include <math.h>
- #include <stdlib.h>
- #include <openssl/x509.h>
- #include <openssl/rsa.h>
- #include <openssl/bn.h>
- #include "qa/questions/questions.h"
- #include "qa/questions/qarith.h"
- #include "qa/questions/qwiener.h"
- cf_t* cf_new(void)
- {
- cf_t *f;
- f = (cf_t *) malloc(sizeof(cf_t));
- size_t i;
- for (i=0; i!=3; i++) {
- f->fs[i].h = BN_new();
- f->fs[i].k = BN_new();
- }
- f->a = BN_new();
- f->x.h = BN_new();
- f->x.k = BN_new();
- f->ctx = BN_CTX_new();
- return f;
- }
- void cf_free(cf_t* f)
- {
- size_t i;
- for (i=0; i!=3; i++) {
- BN_free(f->fs[i].h);
- BN_free(f->fs[i].k);
- }
- BN_free(f->a);
- BN_free(f->x.h);
- BN_free(f->x.k);
- free(f);
- }
- /**
- * \brief Initialized a continued fraction.
- *
- * A continued fraction for a floating number x can be expressed as a series
- * <a₀; a₁, a₂…, aₙ>
- * such that
- * <pre>
- *
- * 1
- * x = a₀ + ⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽⎽
- * 1
- * a₁ + ⎽⎽⎽⎽⎽⎽⎽⎽⎽
- * a₂ + …
- *
- * </pre>
- * , where for each i < n, there exists an approximation hᵢ / kᵢ.
- * By definition,
- * a₋₁ = 0
- * h₋₁ = 1 h₋₂ = 0
- * k₋₁ = 0 k₋₂ = 1
- *
- * \param f A continued fraction structure. If f is NULL, a new one is
- * allocated.
- * \param num Numerator to be used as initial numerator for the fraction to be
- * approximated.
- * \param den Denominator to be used as denominator for the fraction to be
- * approximated.
- *
- * \return the continued fraction fiven as input.
- */
- cf_t* cf_init(cf_t* f, BIGNUM* num, BIGNUM* den)
- {
- if (!f) f = cf_new();
- BN_zero(f->fs[0].h);
- BN_one(f->fs[0].k);
- BN_one(f->fs[1].h);
- BN_zero(f->fs[1].k);
- f->i = 2;
- if (!BN_copy(f->x.h, num)) return NULL;
- if (!BN_copy(f->x.k, den)) return NULL;
- return f;
- }
- /**
- * \brief Produces the next fraction.
- *
- * Each new approximation hᵢ/kᵢ is defined rec ursively as:
- * hᵢ = aᵢhᵢ₋₁ + hᵢ₋₂
- * kᵢ = aᵢkᵢ₋₁ + kᵢ₋₂
- * Meanwhile each new aᵢ is simply the integer part of x.
- *
- *
- * \param f The continued fraction.
- * \return NULL if the previous fraction approximates at its best the number,
- * a pointer to the next fraction in the series othw.
- */
- bigfraction_t* cf_next(cf_t *f)
- {
- bigfraction_t *ith_fs = &f->fs[f->i];
- BIGNUM* rem = BN_new();
- if (BN_is_zero(f->x.h)) return NULL;
- BN_div(f->a, rem, f->x.h, f->x.k, f->ctx);
- /* computing hᵢ */
- BN_mul(f->fs[f->i].h , f->a, f->fs[(f->i-1+3) % 3].h, f->ctx);
- BN_uadd(f->fs[f->i].h, f->fs[f->i].h, f->fs[(f->i-2+3) % 3].h);
- /* computing kᵢ */
- BN_mul(f->fs[f->i].k , f->a, f->fs[(f->i-1+3) % 3].k, f->ctx);
- BN_uadd(f->fs[f->i].k, f->fs[f->i].k, f->fs[(f->i-2+3) % 3].k);
- f->i = (f->i + 1) % 3;
- /* update x. */
- BN_copy(f->x.h, f->x.k);
- BN_copy(f->x.k, rem);
- return ith_fs;
- }
- /*
- * Weiner Attack Implementation
- */
- int wiener_question_ask_rsa(RSA *rsa)
- {
- /* key data */
- BIGNUM *n, *e, *d, *phi;
- BIGNUM *p, *q;
- /* continued fractions coefficient, and mod */
- cf_t* cf;
- bigfraction_t *it;
- size_t i;
- BIGNUM *t, *tmp, *rem;
- /* equation coefficients */
- BIGNUM *b2, *delta;
- BN_CTX *ctx;
- int bits;
- phi = BN_new();
- tmp = BN_new();
- rem = BN_new();
- n = rsa->n;
- e = rsa->e;
- b2 = BN_new();
- delta = BN_new();
- /*
- * Generate the continued fractions approximating e/N
- */
- bits = BN_num_bits(n);
- cf = cf_init(NULL, e, n);
- ctx = cf->ctx;
- for (i=0, it = cf_next(cf);
- // XXX. how many keys shall I test?
- i!=bits && it;
- i++, it = cf_next(cf)) {
- t = it->h;
- d = it->k;
- /*
- * Recovering φ(N) = (ed - 1) / t
- * TEST1: obviously the couple {t, d} is correct → (ed-1) | t
- */
- BN_mul(phi, e, d, cf->ctx);
- BN_usub(tmp, phi, BN_value_one());
- BN_div(phi, rem, tmp, t, cf->ctx);
- if (!BN_is_zero(rem)) continue;
- // XXX. check, is it possible to fall here, assuming N, e are valid?
- if (BN_is_odd(phi) && BN_cmp(n, phi) == 1) continue;
- /*
- * Recovering p, q
- * Solving the equation
- * x² + [N-φ(N)+1]x + N = 0
- * which, after a few passages, boils down to:
- * x² + (p+q)x + (pq) = 0
- *
- * TEST2: φ(N) is correct → the two roots of x are integers
- */
- BN_usub(b2, n, phi);
- BN_uadd(b2, b2, BN_value_one());
- BN_rshift(b2, b2, 1);
- if (BN_is_zero(b2)) continue;
- /* delta */
- BN_sqr(tmp, b2, ctx);
- BN_usub(delta, tmp, n);
- if (!BN_sqrtmod(tmp, rem, delta, ctx)) continue;
- /* key found :) */
- p = BN_new();
- q = BN_new();
- BN_usub(p, b2, tmp);
- BN_uadd(q, b2, tmp);
- //printf("Primes: %s %s", BN_bn2dec(p), BN_bn2dec(q));
- break;
- }
- cf_free(cf);
- BN_free(rem);
- BN_free(tmp);
- BN_free(b2);
- BN_free(delta);
- BN_free(phi);
- return i;
- }
- qa_question_t WienerQuestion = {
- .name = "wiener",
- .pretty_name = "Wiener's Attack",
- .setup = NULL,
- .teardown = NULL,
- .test = NULL,
- .ask_rsa = wiener_question_ask_rsa,
- .ask_crt = NULL,
- };
|