mphell_tuto_ecdsa_fips.c

Go to the documentation of this file.

/* 
  MPHELL-4.0 
  Author(s): The MPHELL team

 (C) Copyright 2015-2018 - Institut Fourier / Univ. Grenoble Alpes (France)

 This file is part of the MPHELL Library.
 MPHELL is free software: you can redistribute it and/or modify
 it under the terms of the GNU Lesser General Public License as published by
 the Free Software Foundation, version 3 of the License.
 
 MPHELL is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU Lesser General Public License for more details.

 You should have received a copy of the GNU Lesser General Public License
 along with MPHELL.  If not, see <http://www.gnu.org/licenses/>.
*/

#include <stdio.h>
#include "mphell/mphell.h"
#if MPHELL_USE_MULTITHREADING == 1
#include <omp.h>
#endif

struct ecdsa_sig 
{
    number *r; 
    number *s; 
};

typedef struct ecdsa_sig ecdsa_sig_t;

typedef ecdsa_sig_t ecdsa_sig[1];

void
ecdsa_sign_alloc(ecdsa_sig *sig, uint8_t size)
{
    (*sig)->r = (number*)malloc(sizeof(number));
    (*sig)->s = (number*)malloc(sizeof(number));
    number_init((*sig)->r, size);
    number_init((*sig)->s, size);
    number_set_ui(*((*sig)->r), (block)0);
    number_set_ui(*((*sig)->s), (block)0);    
}

void 
ecdsa_sign_free(ecdsa_sig *sig)
{
    if ((*sig)->r)
    {
        number_free((*sig)->r);
        free((*sig)->r);
    }
    if ((*sig)->s)
    {
        number_free((*sig)->s);
        free((*sig)->s);
    }
}

void
ec_point_mul_ecdsa(ec_point dst, number_srcptr u1, ec_point_srcptr G,   
                        number_srcptr u2, ec_point_srcptr key, ec_curve_srcptr E)
{
#if MPHELL_USE_MULTITHREADING == 1
    omp_set_num_threads(2);
    ec_point tmp;
    ec_point_get_pool_elt(tmp, E->k, STACK_1);
    #pragma omp parallel
    {
        #pragma omp sections
        {
          #pragma omp section 
          {
              ec_point_mul(tmp, u2, key, E, STACK_1);
          }
          #pragma omp section
          {
              ec_point_mul(dst, u1, G, E, STACK_2);
          }
      }
    }
    ec_point_add(dst, dst, tmp, E, STACK_1);
    ec_point_relax_pool_elt(tmp, E->k, STACK_1);
#else
    ec_point tmp;
    ec_point_get_pool_elt(tmp, E->k, STACK_1);
    ec_point_mul(tmp, u2, key, E, STACK_1);
    ec_point_mul(dst, u1, G, E, STACK_1);
    ec_point_add(dst, dst, tmp, E, STACK_1);
    ec_point_relax_pool_elt(tmp, E->k, STACK_1);
#endif
}

void
ecdsa_sign(unsigned char *hash, ecdsa_sig *sig, number_ptr priv_key, ec_curve *curve)
{
    ec_set_fast_unified_coordinates(*curve);
    number *rr = (*sig)->r;
    number *ss = (*sig)->s;
    
    uint8_t size = (*curve)->k->size;
    
    number k; number_tmp_alloc(&k, size, STACK_1);
    number h; number_tmp_alloc(&h, (strlen((char *)hash)/(BLOCK_SIZE/4)), STACK_1);
    number t; number_tmp_alloc(&t, size, STACK_1);
    number tt; number_tmp_alloc(&tt, 2*size+1, STACK_1);
        
    number abs;
    number_tmp_alloc(&abs, size, STACK_1);
        
    ec_point x;
    ec_point_get_pool_elt(x, (*curve)->k, STACK_1);
    
    field_elt xx;
    field_elt_get_pool_elt(&xx, (*curve)->k, STACK_1);
    
    bool newk = true;
    number_set_str(h , (char*)hash, 16);
    
    while(newk)
    {
        /* Choose k randomly in [1, n-1] */
        number_random1(k, (*curve)->n, STACK_1);
            
        /* Compute (x,y) = kG  */
        ec_point_mul_unified(x, k, (*curve)->G, *curve, STACK_1);
        ec_point_get_x_affine(xx, x, *curve, STACK_1);
            
        /* r = x mod n */
        field_elt_get_number(abs, xx, 1, (*curve)->k, STACK_1);
        number_mod(*rr, abs, (*curve)->n);
                
        /* if r == 0 --> new k */
        if(!number_iszero(*rr)) 
        {
            /* s = k^-1 (hash + r*priv_key) mod n */
            number_mul(tt, *rr, priv_key);
            number_add(tt, tt, h);
            number_mod(tt, tt, (*curve)->n);            /* To keep the multiplication small */
            number_invmod(t, k, (*curve)->n);
            number_mul(tt, tt, t);
            number_mod(*ss, tt, (*curve)->n);

            /* if s == 0 --> new k */
            if(!number_iszero(*ss))
            {
                newk = false;
            } 
        }
    }
    (*sig)->r = rr;
    (*sig)->s = ss;
    
    /* Free memory */
    ec_point_relax_pool_elt(x, (*curve)->k, STACK_1);
    field_elt_relax_pool_elt(&xx, (*curve)->k, STACK_1);
    number_tmp_free(&tt, 2*size+1, STACK_1);
    number_tmp_free(&t, size, STACK_1);
    number_tmp_free(&h, (strlen((char *)hash)/(BLOCK_SIZE/4)), STACK_1);
    number_tmp_free(&k, size, STACK_1);
    number_tmp_free(&abs, size, STACK_1);
}


/* For the hash several functions can be used, the interested reader can refer to [FIPS-180] */

int8_t 
ecdsa_verify(unsigned char *hash, ecdsa_sig *sig, ec_point *pub_key, ec_curve *curve)
{
    ec_set_fast_dedicated_coordinates(*curve);

    if( number_iszero(*((*sig)->r)) || number_cmp(*((*sig)->r),(*curve)->n)>=0 ||  number_iszero(*((*sig)->s)) || number_cmp(*((*sig)->s),(*curve)->n)>=0)
    {
        return false;
    } 
    uint8_t size = (*curve)->k->size;
    
    number w; number_tmp_alloc(&w, size, STACK_1);
    number u1; number_tmp_alloc(&u1, size, STACK_1);
    number u2; number_tmp_alloc(&u2, size, STACK_1);
    number tt2; number_tmp_alloc(&tt2, 2*size, STACK_1);
    
    number abs;
    number_tmp_alloc(&abs, size, STACK_1);
    
    ec_point x;
    ec_point_get_pool_elt(x, (*curve)->k, STACK_1);
    number h; number_tmp_alloc(&h, (strlen((char *)hash)/(BLOCK_SIZE/4)), STACK_1);
    number_set_str(h , (char*)hash, 16);
    
    field_elt xx;
    field_elt_get_pool_elt(&xx, (*curve)->k, STACK_1);
    
    /* w = s^-1 mod n */
    number_invmod(w, *((*sig)->s), (*curve)->n);
    
    /* u1 = hash * w mod n */
    number_mod(u1, h, (*curve)->n);
    number_mul(tt2, u1, w);
    number_mod(u1, tt2, (*curve)->n);

    /* u2 = r*w mod n */
    number_mul(tt2, *((*sig)->r), w);
    number_mod(u2, tt2, (*curve)->n);

    /* x = u1*G + u2*Q */
    ec_point_mul_ecdsa(x, u1, (*curve)->G, u2, *pub_key, *curve);
    ec_point_get_x_affine(xx, x, *curve, STACK_1);
    
    /* Get the result, by comparing x value with r */
    field_elt_get_number(abs, xx, 1, (*curve)->k, STACK_1);
    number_mod(w, abs, (*curve)->n);
    bool result = number_cmp(w, *((*sig)->r)) == 0;

    /* Free memory */
    number_tmp_free(&h, (strlen((char *)hash)/(BLOCK_SIZE/4)), STACK_1);
    ec_point_relax_pool_elt(x, (*curve)->k, STACK_1);
    field_elt_relax_pool_elt(&xx, (*curve)->k, STACK_1);
    number_tmp_free(&tt2, 2*size, STACK_1);
    number_tmp_free(&u2, size, STACK_1);
    number_tmp_free(&u1, size, STACK_1);
    number_tmp_free(&w, size, STACK_1);
    number_tmp_free(&abs, size, STACK_1);

    return result;
}

int8_t 
ecdsa_pub_key_validation(ec_point *pub_key, ec_curve *curve)
{    
    if(!ec_belongs(*pub_key, *curve, STACK_1))
    {
        /* pubkey does not belong  to the curve */
        return false;   
    }   
    if(ec_point_is_neutral(*pub_key, *curve, STACK_1))
    {
        /* pubkey is the neutral element */
        return false;
    }
    /* We finally test the order of the curve */
    ec_point x;
    ec_point_get_pool_elt(x, (*curve)->k, STACK_1);    
    ec_point_mul(x, (*curve)->n, *pub_key, *curve, STACK_1);
    if(!ec_point_is_neutral(x, *curve, STACK_1))
    {
        /* pubkey is the neutral element */
        return false;
    }
    ec_point_relax_pool_elt(x, (*curve)->k, STACK_1);
    
    return true;
}

int main()
{
    /* Initialise MPHELL with 256 bits of security strength for the entropy, RANDOM_AES256 as DRBG and DEVURANDOM as entropy source */
    
    init_mphell(256, RANDOM_AES256, DEVURANDOM);
    
    /* Allocate a field of size 4*block_SIZE = 4*64 = 256 on 64 bits architecture */
    
    field k;
    field_alloc(k, FP, bits_to_nblock(256), NULL);
    
    /* Allocate a number of size 4*block_SIZE = 4*64 = 256 on 64 bits architecture */
    
    number p;
    number_init(&p, bits_to_nblock(256));
    
    /* Set the number p from a string in base 16 */
    
    number_set_str(p, "ffffffff00000001000000000000000000000000ffffffffffffffffffffffff", 16);
    
    /* Create the field of characteristic p */
    
    field_create(k, "", STACK_1, 1, p);
    
    /* Allocate curve */
    
    ec_curve E;
    ec_alloc (E, k);
    ec_init(E, k);
    
    /* Create curve */
    
    field_elt a, b;
    ec_point G;
    number n, h;
    
    field_elt_alloc(&a, k);
    field_elt_init(a, k);
    field_elt_alloc(&b, k);
    field_elt_init(b, k);
    ec_point_alloc(G, k);
    ec_point_init(G, k);
    number_init(&n, bits_to_nblock(256));
    number_init(&h, bits_to_nblock(256));
    
    field_elt_set_str(a, "ffffffff00000001000000000000000000000000fffffffffffffffffffffffc", 16, false, k, STACK_1);
    field_elt_set_str(b, "5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b", 16, false, k, STACK_1);
    ec_point_set_aff_str(G, "6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296", "4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5", false, 16, WEIERSTRASS, k, STACK_1);
    number_set_str(h, "1", 16);
    number_set_str(n, "ffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551", 16);
    
    ec_create (E, "Weierstrass_nist_256", k, a, b, G, h, n, WEIERSTRASS, JACOBIAN, STACK_1);
    
    printf("E: \n"); ec_curve_print(E, 16, STACK_1); printf("\n");
    
    field_elt_free(&a, k);
    field_elt_free(&b, k);
    ec_point_free(G, k);
    number_free(&h);
    number_free(&n);

    /* Get private key from random value between 0 and the size of the group generated by G:E->n */
    number priv_key;
    number_init(&priv_key, bits_to_nblock(256));
    number_random1(priv_key, E->n, STACK_1);
       
    /* Test that the value is not equal to p-1 and change it until it is the case */
    number test;
    number_init(&test, bits_to_nblock(256));
    number_dec(test, E->n);  
    while(number_cmp(test, priv_key)<=0)
    {
       number_random1(priv_key, E->n, STACK_1); 
    }
    number_free(&test);
    number_inc(priv_key, priv_key);
    printf("\nThe private key has been created its value is:\n");
    number_print(priv_key, 16);
    
    /* Computation of the public key */
    ec_point pub_key;
    ec_point_alloc(pub_key, E->k);
    ec_point_init(pub_key, E->k);
    ec_point_mul_unified(pub_key, priv_key, E->G, E, STACK_1);

    /* Print the public key */
    ec_point_norm(pub_key, E, STACK_1);  
    printf("\nThe pubkey has been computed:\n");  
    ec_point_print(pub_key, 16, true, k, STACK_1); 
    
    /* This test is optional.*/
    printf("\nThe validity of the public key is a:\n");
    int ret = ecdsa_pub_key_validation(&pub_key, &E);
    if( ret < 1 )
    {
        printf("ERROR\n");
    }
    else
    {
        printf("SUCCESS\n");
    }

    /* Digest to sign */
    char * digest = "982c20c2493fc9ae405b74b65a022662c014a38ef3d707217e56e57afac05994";
    
    /* Allocate ecdsa_sig structure */
    ecdsa_sig sig;
    ecdsa_sign_alloc(&sig, bits_to_nblock(256));
    
    /* Sign the digest */
    ecdsa_sign((unsigned char *)digest, &sig, priv_key, &E);
    
    printf("\nThe ECDSA signature is: (");
    number_print(*(sig->r), 16);
    printf(", ");
    number_print(*(sig->s), 16);
    printf(")\n");
    
    /* Verify the signature */
    printf("\n-> Verify ECDSA signature \n");
    ret = ecdsa_verify((unsigned char *)digest, &sig, &pub_key, &E);
    if( ret < 1 )
    {
        printf("ERROR\n");
    }
    else
    {
        printf("SUCCESS\n");
    }
    
    /* Free memory */
    
    ec_point_free(pub_key, k);
    number_free(&priv_key);
    ecdsa_sign_free(&sig);
    number_free(&p);;
    field_free(k);
    ec_free(E);
    
    free_mphell();

    return 0;
}