mphell_tuto_ecdsa.c

Go to the documentation of this file.

/* 
  MPHELL-5.0 
  Author(s): The MPHELL team
 
 (C) Copyright 2015-2021 - 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);
#if MPHELL_USE_AMNS == 1
    amns AMNS;
#if MPHELL_USE_AMNS_32 == 0
    amns_alloc_init_str(&AMNS, "[4, 5, [-3, 0, 0, 0, 0, 1], 55, 71533969486545864413516767253794911064875612240194438086363842467605348744666, [281003535425591, -579833024021834, -91487654138292, -1407285223270225, 1257806506188213], [10138092101046066474, 10662180220582548599, 13438525377408553810, 2956505949806397541, 1582018761247275305], [-1488511254885447, 1691948961301838, 368225590485535, 364881739107280, -1251317625290732], [1396607582108050, -3787438073044259, 594275210547971, 1341450284833267, -604094026418167]]", p);
#else
    amns_alloc_init_str(&AMNS, "[1, 13, [-2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1], 24, 12283929623108920300809241648376276210021878764342577833737044552429073849048, [339101, 37569, 167801, -196152, -417739, -294951, 49819, 364997, 286578, 400226, 258890, -193421, 198477], [2979672525, 235065897, 2631974852, 2919389277, 2172036204, 3746829531, 2056633047, 794426671, 2257704876, 1726773529, 1568503618, 66995355, 3378284366], [954133, 569228, 1096741, 836659, 630615, 1288006, 872327, 1504995, 1367932, 401997, 700080, 158946, 137905], [803354, 622540, 375011, -650534, 854552, 1546271, 1126099, 1770152, 1141472, 187022, 247179, 639661, 675036]]", p);
#endif
    field_set_amns(k, AMNS);
#endif
    
    /* 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);
#if MPHELL_USE_AMNS == 1
    amns_free(&AMNS);
#endif
    ec_free(E);
    
    free_mphell();
 
    return 0;
}