cangrepp

Some cryptographic attacks
Log | Files | Refs | README

wiener.c (3150B)

      1 #include "wiener.h"
      2 
      3 static int
      4 test_kd(fmpz_t r, const fmpz_t k, const fmpz_t d, const fmpz_t e,
      5         const fmpz_t N, fmpz_t phi, fmpz_t t, fmpz_t it, fmpz_t tmp)
      6 {
      7   int res = 0;
      8 
      9   if (fmpz_cmp_ui(k, 0) == 0) {
     10     return 0;
     11   }
     12 
     13   fmpz_mul(phi, e, d);
     14   fmpz_sub_ui(phi, phi, 1);
     15   fmpz_fdiv_q(phi, phi, k);
     16 
     17   fmpz_add_ui(t, N, 1);
     18   fmpz_sub(t, t, phi);
     19   fmpz_pow_ui(t, t, 2);
     20   fmpz_mul_ui(tmp, N, 4);
     21   fmpz_sub(t, t, tmp);
     22 
     23   if (fmpz_cmp_ui(t, 0) >= 0) {
     24     fmpz_sqrt(it, t);
     25     fmpz_pow_ui(tmp, it, 2);
     26 
     27     if (fmpz_cmp(tmp, t) == 0) {
     28       fmpz_add_ui(tmp, N, 1);
     29       fmpz_sub(tmp, tmp, phi);
     30       fmpz_add(tmp, tmp, it);
     31       fmpz_fdiv_q_ui(r, tmp, 2);
     32 
     33       fmpz_mod(tmp, N, r);
     34 
     35       if (fmpz_is_zero(tmp)) {
     36         res = 1;
     37       }
     38     }
     39   }
     40 
     41   return res;
     42 }
     43 
     44 /*
     45 static int
     46 test_kd(fmpz_t r, const fmpz_t k, const fmpz_t d, const fmpz_t e,
     47         const fmpz_t N)
     48 {
     49   int res = 0;
     50   fmpz_t phi, t, it, tmp;
     51 
     52   if (fmpz_cmp_ui(k, 0) == 0) {
     53     return 0;
     54   }
     55 
     56   fmpz_init(phi);
     57   fmpz_init(t);
     58   fmpz_init(it);
     59   fmpz_init(tmp);
     60 
     61   fmpz_mul(phi, e, d);
     62   fmpz_sub_ui(phi, phi, 1);
     63   fmpz_fdiv_q(phi, phi, k);
     64 
     65   fmpz_add_ui(t, N, 1);
     66   fmpz_sub(t, t, phi);
     67   fmpz_pow_ui(t, t, 2);
     68   fmpz_mul_ui(tmp, N, 4);
     69   fmpz_sub(t, t, tmp);
     70 
     71   if (fmpz_cmp_ui(t, 0) >= 0) {
     72     fmpz_sqrt(it, t);
     73     fmpz_pow_ui(tmp, it, 2);
     74 
     75     if (fmpz_cmp(tmp, t) == 0) {
     76       fmpz_add_ui(tmp, N, 1);
     77       fmpz_sub(tmp, tmp, phi);
     78       fmpz_add(tmp, tmp, it);
     79       fmpz_fdiv_q_ui(r, tmp, 2);
     80 
     81       fmpz_mod(tmp, N, r);
     82 
     83       if (fmpz_is_zero(tmp)) {
     84         res = 1;
     85       }
     86     }
     87   }
     88 
     89   fmpz_clear(phi);
     90   fmpz_clear(t);
     91   fmpz_clear(it);
     92   fmpz_clear(tmp);
     93 
     94   return res;
     95 }
     96 */
     97 
     98 int
     99 wiener_factor(ctx_t *ctx, fmpz_t res, const fmpq_t x, const fmpz_t e,
    100               const fmpz_t N)
    101 {
    102   assert(ctx->zs_alloc >= 10);
    103   assert(ctx->qs_alloc >= 4);
    104 
    105   fmpq_t xn[2] = {{ctx->qs[0]}, {ctx->qs[1]}};
    106   fmpq_t tmp = {ctx->qs[2]};
    107   fmpq_t xp = {ctx->qs[3]};
    108   fmpz_t p[2] = {{ctx->zs[0]}, {ctx->zs[1]}};
    109   fmpz_t q[2] = {{ctx->zs[2]}, {ctx->zs[3]}};
    110   fmpz_t tmpz = {ctx->zs[4]};
    111   fmpz_t xpz = {ctx->zs[5]};
    112   int ret = 0;
    113 
    114   fmpq_set(xn[0], x);
    115   fmpq_one(xn[1]);
    116 
    117   fmpz_set_ui(p[0], 0);
    118   fmpz_set_ui(p[1], 1);
    119   fmpz_set_ui(q[0], 1);
    120   fmpz_set_ui(q[1], 0);
    121 
    122   while (!fmpq_is_zero(xn[1])) {
    123     fmpq_div(tmp, xn[0], xn[1]);
    124     fmpz_fdiv_q(tmpz, fmpq_numref(tmp), fmpq_denref(tmp));
    125 
    126     fmpq_mul_fmpz(xp, xn[1], tmpz);
    127     fmpq_sub(xp, xn[0], xp);
    128     fmpq_set(xn[0], xn[1]);
    129     fmpq_set(xn[1], xp);
    130 
    131     fmpz_mul(xpz, tmpz, q[1]);
    132     fmpz_add(xpz, xpz, q[0]);
    133     fmpz_set(q[0], q[1]);
    134     fmpz_set(q[1], xpz);
    135 
    136     fmpz_mul(xpz, tmpz, p[1]);
    137     fmpz_add(xpz, xpz, p[0]);
    138     fmpz_set(p[0], p[1]);
    139     fmpz_set(p[1], xpz);
    140 
    141     ret = test_kd(res, p[1], q[1], e, N, &ctx->zs[6], &ctx->zs[7],
    142                   &ctx->zs[8], &ctx->zs[9]);
    143 
    144     if (ret != 0)
    145       break;
    146   }
    147 
    148   return ret;
    149 }
    150 
    151 int
    152 wiener_factor_small_d(ctx_t* ctx, fmpz_t res, const fmpz_t e, const fmpz_t N)
    153 {
    154   assert(ctx->qs_alloc >= 5);
    155   fmpq_t x = {ctx->qs[4]};
    156   int ret;
    157 
    158   fmpq_set_fmpz_frac(x, e, N);
    159   ret = wiener_factor(ctx, res, x, e, N);
    160 
    161   return ret;
    162 }