2 years, 5 months ago.

Query on ecdsa_sign and barrett reduction-based hardware accelerator

Hi, I am using hardware accelerator (barrett reduction) for mpi_mod_mpi in ECDSA and it failed during ecdsa_sign step 6 because t(e+rd)/(kt) is larger than power(n,2)

         * Step 6: compute s = (e + r * d) / k = t (e + rd) / (kt) mod n
        MPI_CHK( mpi_mul_mpi( s, r, d ) );
        MPI_CHK( mpi_add_mpi( &e, &e, s ) );
        MPI_CHK( mpi_mul_mpi( &e, &e, &t ) );
        MPI_CHK( mpi_mul_mpi( &k, &k, &t ) );
        MPI_CHK( mpi_inv_mod( s, &k, &grp->N ) );
        MPI_CHK( mpi_mul_mpi( s, s, &e ) );
        MPI_CHK( mpi_mod_mpi( s, s, &grp->N ) );

Performing mod on results of each of first 4 operation allows my hardware accelerator to work again while providing same result. Questions:

  1. Is there a reason for not performing mod after each operation?
  2. I assumed (without basis) that barrett-reduction-based hardware accelerator would work because ECC is using modular arithmetic. Is this a valid assumption?
  3. Are there more calculations - similar to step 6 - that does not perform mod on result of each operation?


posted by Lynn L 13 Feb 2019
Be the first to answer this question.