cangrepp

Some cryptographic attacks
Log | Files | Refs | README

bsgs.c (2353B)

      1 #include "bsgs.h"
      2 
      3 #define UNDEFINED SIZE_MAX
      4 
      5 // For hashing we can use mod because we expect the numbers to behave
      6 // randomly anyway
      7 size_t
      8 hash(const fmpz n)
      9 {
     10   if (COEFF_IS_MPZ(n)) {
     11     return (size_t)COEFF_TO_PTR(n)[0]._mp_d[0];
     12   } else {
     13     return (size_t)n;
     14   }
     15 }
     16 
     17 typedef struct _hashmap_integer {
     18   size_t n;
     19   size_t *table;
     20   fmpz_t *keys;
     21   size_t ntable;
     22 } hm_t;
     23 
     24 void
     25 hm_init(hm_t *hm, const size_t s)
     26 {
     27   size_t i;
     28   hm->n = 0;
     29   hm->ntable = s;
     30 
     31   hm->table = malloc(s * sizeof(*hm->table));
     32   hm->keys = malloc(s * sizeof(*hm->keys));
     33 
     34   for (i = 0; i < s; i++) {
     35     hm->table[i] = UNDEFINED;
     36   }
     37 }
     38 
     39 void
     40 hm_clear(hm_t *hm)
     41 {
     42   free(hm->table);
     43   free(hm->keys);
     44 }
     45 
     46 void
     47 hm_insert(hm_t *hm, const fmpz_t *key, const size_t val)
     48 {
     49   assert(hm->n < hm->ntable);
     50   assert(val != UNDEFINED);
     51   size_t kv;
     52 
     53   kv = hash(*key);
     54 
     55   while (hm->table[kv] != UNDEFINED) {
     56     if (fmpz_cmp(*(hm->keys[kv]), *key) == 0) {
     57       hm->keys[kv] = key;
     58       hm->table[kv] = val;
     59       return;
     60     }
     61     kv = (kv + 1) % ht->ntable;
     62   }
     63 
     64   hm->keys[kv] = key;
     65   hm->table[kv] = val;
     66 }
     67 
     68 size_t
     69 hm_key_index(const hm_t *hm, const fmpz_t *key)
     70 {
     71   size_t kv;
     72 
     73   kv = hash(*key);
     74   while (hm->table[kv] != UNDEFINED) {
     75     if (fmpz_cmp(*(hm->keys[kv]), *key) == 0) {
     76       return kv;
     77     }
     78     kv = (kv + 1) % ht->ntable;
     79   }
     80 
     81   return UNDEFINED;
     82 }
     83 
     84 size_t
     85 hm_lookup(size_t *res, const hm_t *hm, const fmpz_t *key)
     86 {
     87   size_t idx = hm_key_index(hm, key);
     88   if (idx != UNDEFINED) {
     89     *res = hm->table[idx];
     90     return 1;
     91   } else {
     92     return 0;
     93   }
     94 }
     95 
     96 // assumptoion:
     97 //   arguments g and h are already reduced
     98 uint64_t
     99 bsgs(ctx_t *ctx, fmpz_mod_ctx_t mod, const fmpz_t g, const fmpz_t h,
    100      const uint64_t gorder)
    101 {
    102   assert(ctx->zs_alloc >= 1);
    103 
    104   size_t i;
    105   size_t j;
    106   uint64_t rr = 0;
    107   hm_t hm;
    108   const size_t lmt = (size_t)(n_sqrt(gorder) + 1);
    109   fmpz *v;
    110 
    111   v = _fmpz_vec_init(nlmt);
    112   hm_init(&hm, 2 * lmt);
    113 
    114   // baby step
    115   fmpz_set_ui(&v[0], 1);
    116   hm_insert(&hm, &v[0], 0);
    117   for (i = 1; i < lmt; i++) {
    118     fmpz_mod_mul(&v[i], &v[i - 1], g, mod);
    119     hm_insert(&hm, &v[i], i);
    120   }
    121 
    122   // giantstep
    123   fmpz_set(gsc, h);
    124   gi = fmpz_mod_inverse(mod, g);
    125   for (i = 0; i < lmt; i++) {
    126     if(hm_lookup(&j, &hm, gsc) != 0) {
    127       rr = (uint64_t) (i*lmt + j);
    128     }
    129     fmpz_mod_mul(gsc, gsc, gi, mod);
    130   }
    131 
    132   hm_clear(&hm);
    133 
    134   return rr;
    135 }