123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280 |
- #include <assert.h>
- #include <stdlib.h>
- #include <strings.h>
- #include <openssl/bn.h>
- #include "qa/questions/qarith.h"
- #include "qa/questions/qstrings.h"
- #include "qa/questions/questions.h"
- #define EPOCHS 100
- #define REPOP_EPOCHS 50
- #define BPOOL_EXTEND_STEP 42
- #define BPOOL_STARTING_BITS 7
- #define RPOOL_EXTEND_STEP 42
- #define U_SIZE 10
- #define qa_rand rand
- static BIGNUM* zero;
- typedef struct dixon_number {
- BIGNUM *r;
- BIGNUM *s;
- BIGNUM **v;
- } dixon_number_t;
- dixon_number_t *R_pool = NULL;
- static size_t R_size = 0;
- static BIGNUM** B_pool = NULL;
- static size_t B_size = 0;
- static void extend_B_pool(int max_bits)
- {
- size_t i, j, old_B_size;
- int bits;
- old_B_size = B_size;
- B_size += BPOOL_EXTEND_STEP;
-
- assert(old_B_size < B_size);
- B_pool = realloc(B_pool, B_size * sizeof(BIGNUM*));
- for (i=old_B_size; i!=B_size; i++) {
- bits = 1 + qa_rand() % max_bits;
- B_pool[i] = BN_generate_prime(NULL, bits, 0, NULL, NULL, NULL, NULL);
- }
-
- for (i=0; i!=R_size; i++) {
- R_pool[i].v = realloc(R_pool[i].v, sizeof(BIGNUM*) * B_size);
- for (j=old_B_size; j!=B_size; j++) R_pool[i].v[j] = NULL;
- }
- }
- #define B_pool_free() free(B_pool)
- static void extend_R_pool(BIGNUM* N)
- {
- const size_t old_R_size = R_size;
- size_t i, j;
- int e_bits;
- BN_CTX *ctx = BN_CTX_new();
- BIGNUM
- *e,
- *tmp = BN_new(),
- *rem = BN_new(),
- *t = BN_new();
- dixon_number_t *d;
- R_size += RPOOL_EXTEND_STEP;
-
- assert(R_size > old_R_size);
- R_pool = realloc(R_pool, sizeof(dixon_number_t));
-
- e_bits = BN_num_bits(N) / 5;
- for (i=old_R_size; i!= R_size; i++) {
- d = &R_pool[i];
- d->s = BN_new();
- d->r = BN_new();
-
- for (j=0; j != B_size && BN_cmp(N, d->s) == 1; j++) {
- e = d->v[j] = BN_new();
-
- BN_pseudo_rand(e, e_bits, -1, 0);
- BN_exp(tmp, B_pool[j], e, ctx);
- BN_mul(d->s, tmp, d->s, ctx);
- }
-
- BN_sqr(tmp, N, ctx);
- BN_one(t);
- for (BN_add(t, t, N); BN_cmp(tmp, t) == 1; BN_add(t, t, N))
- if (BN_sqrtmod(d->r, rem, t, ctx)) break;
- }
- BN_CTX_free(ctx);
- BN_free(rem);
- BN_free(tmp);
- BN_free(t);
- }
- #define R_pool_free() free(R_pool)
- int dixon_question_setup(void)
- {
- extern BIGNUM* zero;
- zero = BN_new();
- BN_zero(zero);
- extend_B_pool(BPOOL_STARTING_BITS);
- return 0;
- }
- int dixon_question_teardown(void) {
- BN_free(zero);
- B_pool_free();
- R_pool_free();
- return 0;
- }
- int dixon_question_ask_rsa(RSA *rsa) {
-
- BIGNUM
- *n,
- *p, *q;
-
- BIGNUM
- *x, *x2,
- *y, *y2;
- BN_CTX *ctx;
-
- ssize_t *U_bucket;
-
- int epoch;
- BIGNUM *tmp;
- char *even_powers;
- size_t i, j, k;
- n = rsa->n;
- U_bucket = malloc(sizeof(ssize_t) * U_SIZE);
- even_powers = malloc(sizeof(char) * B_size);
- ctx = BN_CTX_new();
- x = BN_new();
- y = BN_new();
- x2 = BN_new();
- y2 = BN_new();
- tmp = BN_new();
-
- for (epoch=0; epoch < EPOCHS; epoch++) {
-
- if (epoch % REPOP_EPOCHS) extend_R_pool(n);
-
- for (i=0; i!=U_SIZE; i++) U_bucket[i] = -1;
- bzero(even_powers, B_size * sizeof(char));
- j = 0;
-
- do {
- for (i=0; i!=B_size && j < U_SIZE; i++) {
-
- if (qa_rand() % 2) continue;
-
- U_bucket[j++] = i;
- for (k=0; k!=B_size; k++)
- even_powers[k] ^= BN_is_odd(R_pool[i].v[j]);
- }
- } while (!is_vzero(even_powers, B_size * sizeof(char)));
-
- BN_one(x);
- BN_one(y2);
- for (i=0; i != U_SIZE; i++) {
- if (U_bucket[i] == -1) continue;
- j = U_bucket[i];
- BN_mul(x, x, R_pool[j].r, ctx);
- BN_mul(y2, y2, R_pool[j].s, ctx);
- }
-
- BN_sqr(x2, x, ctx);
-
-
- if (!BN_sqrtmod(y, tmp, y2, ctx)) continue;
-
- if (!BN_cmp(x, y)) continue;
-
- p = BN_new();
- q = BN_new();
- BN_uadd(tmp, x, y);
- BN_gcd(p, tmp, n, ctx);
- assert(!BN_is_one(p) && BN_cmp(p, n));
- BN_usub(tmp, x, y);
- BN_gcd(q, tmp, n, ctx);
- assert(!BN_is_one(q) && BN_cmp(q, n));
- }
- BN_free(x);
- BN_free(x2);
- BN_free(y);
- BN_free(y2);
- free(U_bucket);
- free(even_powers);
- return 0;
- }
- qa_question_t DixonQuestion = {
- .name = "dixon",
- .pretty_name = "Dixon's Factorization",
- .setup = dixon_question_setup,
- .teardown = dixon_question_teardown,
- .test = NULL,
- .ask_rsa = dixon_question_ask_rsa,
- .ask_crt = NULL
- };
|