cangrepp

Some cryptographic attacks
Log | Files | Refs | README

hnp.c (2145B)

      1 #include "hnp.h"
      2 
      3 int
      4 hidden_number_problem(fmpz *res, const slong nres, const fmpz *t,
      5                       const fmpz *a, const slong m, const fmpz_t n,
      6                       const fmpz_t B)
      7 {
      8   if (nres < m + 1)
      9     return (-1);
     10 
     11   // initialise a zero matrix
     12   fmpz_mat_t A;
     13   fmpz_mat_init(A, m + 2, m + 2);
     14   fmpz_mat_zero(A);
     15 
     16   // set up n^2's on the diagonal
     17   slong i;
     18   fmpz_t n_squared;
     19   fmpz_init_set(n_squared, n);
     20   fmpz_pow_ui(n_squared, n_squared, 2);
     21   for (i = 0; i < m; i++) {
     22     fmpz *m_i_i = fmpz_mat_entry(A, i, i);
     23     fmpz_set(m_i_i, n_squared);
     24   }
     25   fmpz_clear(n_squared);
     26 
     27   // setting up last two diagonal entries
     28   fmpz *m_i_i = fmpz_mat_entry(A, m, m);
     29   fmpz_set(m_i_i, B);
     30   m_i_i = fmpz_mat_entry(A, m + 1, m + 1);
     31   fmpz_mul(m_i_i, B, n);
     32 
     33   // columnwise setup
     34   for (i = 0; i < m; i++) {
     35     // t[i]*n
     36     fmpz *tmp = fmpz_mat_entry(A, m, i);
     37     fmpz_mul(tmp, &t[i], n);
     38 
     39     // a[i]*n
     40     tmp = fmpz_mat_entry(A, m + 1, i);
     41     fmpz_mul(tmp, &a[i], n);
     42   }
     43 
     44   // use LLL for lattice reduction (delta = 0.99, eta = 0.501)
     45   fmpq_t delta, eta;
     46   fmpq_init(delta);
     47   fmpq_init(eta);
     48   fmpq_set_ui(delta, 99, 100);
     49   fmpq_set_ui(eta, 501, 1000);
     50 
     51   fmpz_mat_lll_original(A, delta, eta);
     52 
     53   fmpq_clear(delta);
     54   fmpq_clear(eta);
     55 
     56   // extract the potential solution
     57   fmpz_t Bn;
     58   fmpz_init(Bn);
     59   fmpz_mul(Bn, B, n);
     60   for (i = 0; i < m + 2; i++) {
     61     if (fmpz_cmpabs(fmpz_mat_entry(A, i, m + 1), Bn) == 0)
     62       break;
     63   }
     64   fmpz_clear(Bn);
     65   if (i >= m + 2) {
     66     fmpz_mat_clear(A);
     67     return 1;
     68   }
     69 
     70   slong r = i;
     71 
     72   for (i = 0; i < m; i++) {
     73     fmpz *tmp = fmpz_mat_entry(A, r, i);
     74     fmpz_tdiv_q(&res[i], tmp, n);
     75   }
     76   fmpz_tdiv_q(&res[m], fmpz_mat_entry(A, r, m), B);
     77 
     78   fmpz_mat_clear(A);
     79 
     80   // test that the solution is a solution to original HNP
     81   fmpz_t tmp;
     82   fmpz_init(tmp);
     83 
     84   for (i = 0; i < m; i++) {
     85     // tmp <- t[i]*alpha - a[i] mod n
     86     fmpz_mul(tmp, &t[i], &res[m]);
     87     fmpz_add(tmp, tmp, &a[i]);
     88     fmpz_sub(tmp, tmp, &res[i]);
     89     fmpz_mod(tmp, tmp, n);
     90 
     91     if (fmpz_cmp_ui(tmp, 0) != 0) {
     92       fmpz_clear(tmp);
     93       return 1;
     94     }
     95   }
     96 
     97   fmpz_clear(tmp);
     98 
     99   return 0;
    100 }