mphell_tuto_ecdsa.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"

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

typedef struct ecdsa_sig ecdsa_sig_t;

typedef ecdsa_sig_t ecdsa_sig[1];

#define PRECOMP_WIN_SIZE 9
#define PRECOMP_SIZE 256

struct ecdsa_precomp 
{
    ec_point prec_G[2*PRECOMP_SIZE]; 
    ec_point prec_K[2*PRECOMP_SIZE]; 
};

typedef struct ecdsa_precomp ecdsa_precomp_t;

typedef ecdsa_precomp_t ecdsa_precomp[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
ecdsa_precal(ecdsa_precomp *precomp, ec_point *key, ec_curve_ptr E)
{
    ec_set_fast_dedicated_coordinates(E);
    uint16_t i;
    uint16_t pr = 2*PRECOMP_SIZE;
    
    /* Allocate */
    for(i = 0; i < pr; i++)
    {
        ec_point_alloc(((*precomp)->prec_G)[i], E->k);
        ec_point_alloc(((*precomp)->prec_K)[i], E->k);
        ec_point_init(((*precomp)->prec_G)[i], E->k);
        ec_point_init(((*precomp)->prec_K)[i], E->k);
    }
    ec_point_set_neutral(((*precomp)->prec_K)[0], E, STACK_1);
    ec_point_set_neutral(((*precomp)->prec_G)[0], E, STACK_1);
    
    ec_point_copy(((*precomp)->prec_G)[1], E->G, E->k);      /* G[0] = G     */
    ec_point_copy(((*precomp)->prec_K)[1], *key, E->k);      /* K[0] = K     */
    
    for(i = 2; i < pr; i++)
    {
        /* tab[i]=(i)* P1 */
        ec_point_add(((*precomp)->prec_G)[i], E->G, ((*precomp)->prec_G)[i-1], E, STACK_1);
        ec_point_add(((*precomp)->prec_K)[i], *key, ((*precomp)->prec_K)[i-1], E, STACK_1);
    }
}

void
ecdsa_precal_free(ecdsa_precomp *precomp, ec_curve_ptr E)
{
    uint16_t i;
    uint16_t pr = 2*PRECOMP_SIZE;
    for(i = 0; i < pr; i++)
    {
        ec_point_free(((*precomp)->prec_G)[i], E->k);
        ec_point_free(((*precomp)->prec_K)[i], E->k);
    }
}

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);
}

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;
}

int8_t 
ecdsa_verify(unsigned char *hash, ecdsa_sig *sig, ec_point *pub_key, ec_curve *curve, ecdsa_precomp precomp)
{
    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_2mul_with_precomp(x, u1, precomp->prec_G, u2, precomp->prec_K, PRECOMP_WIN_SIZE, *curve, STACK_1);
    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;
}

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(&n);
    number_free(&h);

    /* Create public key */
    ec_point pub_key;
    ec_point_alloc(pub_key, E->k);
    ec_point_init(pub_key, E->k);
    ec_point_set_aff_str(pub_key, "CBE2BCC92CDA44BB7851833F41684935DAD703C9AFB5D209F2922F8F739BA2D7", "8B620F0C41F572563648CC9C1C782F71C952B87782B61431640505AA317FCC07", false, 16, WEIERSTRASS, k, STACK_1);

    /* Set private key */
    number priv_key;
    number_init(&priv_key,bits_to_nblock(256));
    number_set_str(priv_key, "5A23E08CF6E463BFEDFBA98F0CCE0B3B0A18EFED7DD31834577721A96D10BB8B", 16);
    
    /* 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("The signature is: (");
    number_print(*(sig->r), 16);
    printf(", ");
    number_print(*(sig->s), 16);
    printf(")\n");
    
    /* Verify the public key */
    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");
    }
    
    /* Precomputation (to speed up verification) */
    printf("-> Precomputation \n");
    ecdsa_precomp precomp;
    ecdsa_precal(&precomp, &pub_key, E);
    
    /* Verify the signature */
    printf("-> Verify ECDSA signature \n");
    ret = ecdsa_verify((unsigned char *)digest , &sig, &pub_key, &E, precomp);
    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);
    ecdsa_precal_free(&precomp, E);
    field_free(k);
    ec_free(E);
    
    free_mphell();

    return 0;
}