mphell_tuto_ecgdsa.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"
#if MPHELL_USE_MULTITHREADING == 1
#include <omp.h>
#endif
 
struct ecgdsa_sig 
{
    number *r; 
    number *s; 
};
 
typedef struct ecgdsa_sig ecgdsa_sig_t;
 
typedef ecgdsa_sig_t ecgdsa_sig[1];
 
void
ecgdsa_sign_alloc(ecgdsa_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 
ecgdsa_sign_free(ecgdsa_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
ecgdsa_sign(unsigned char *hash, ecgdsa_sig *sig, number priv_key, ec_curve *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, 2*size+1, STACK_1);
        
    number abs;
    number_tmp_alloc(&abs, size, STACK_1);
    
    field_elt xx;
    field_elt_get_pool_elt(&xx, (*curve)->k, STACK_1);
        
    ec_point x;
    ec_point_get_pool_elt(x, (*curve)->k, STACK_1);
    
    bool newk = true;
    number_set_str(h , (char*)hash, 16);
    number_mod(h, h, (*curve)->n);            /* To keep h small */            
        
    while(newk)
    {
        /* Choose k randomly in [1, n-1] */
        number_random1(k, (*curve)->n, STACK_1);
        number test; number_init(&test, bits_to_nblock(256));
        number_dec(test, (*curve)->n);    
        while(number_cmp(test, k)==0)
        {
            number_random1(k, (*curve)->n, STACK_1); 
        }
        number_free(&test);
            
        /* 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 * r - hash)*priv_key mod n */
            number_mul(t, *rr, k);
            number_mod(t, t, (*curve)->n);            /* To keep the multiplication small */    
            if (number_cmp(h,t)==1)                   /* We make sure that h<=t */
            {
                number_add(t, t, (*curve)->n);
            }            
            number_sub(t, t, h);                
            /* not useful anymore number_mod(t, t, (*curve)->n); */           /* To keep the multiplication small */
            number_mul(t, t, priv_key);
            number_mod(*ss, t, (*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(&abs, size, STACK_1);
    number_tmp_free(&t, 2*size+1, STACK_1);
    number_tmp_free(&h, (strlen((char *)hash)/(BLOCK_SIZE/4)), STACK_1);
    number_tmp_free(&k, size, STACK_1);
}
 
 
int8_t 
ecgdsa_verify(unsigned char *hash, ecgdsa_sig *sig, ec_point *pub_key, ec_curve *curve)
{
    /* Just check that r,s \in {1, ... , q-1} */
    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, size, STACK_1);
    number t; number_tmp_alloc(&t, 2*size, STACK_1);
    number f1; number_tmp_alloc(&f1, size, STACK_1);
    
    number abs;
    number_tmp_alloc(&abs, size, STACK_1);
    
    field_elt xx;
    field_elt_get_pool_elt(&xx, (*curve)->k, STACK_1);
    
    ec_point x;
    ec_point_get_pool_elt(x, (*curve)->k, STACK_1);
    
    number h; number_init(&h, (strlen((char *)hash)/(BLOCK_SIZE/4)));
    number_set_str(h , (char*)hash, 16);
 
    /* w = r^-1 mod n */
    number_invmod(w, *((*sig)->r), (*curve)->n);
    
    /* u1 = hash * w mod n */
    number_mod(tt2, h, (*curve)->n);
    number_mul(t, tt2, w);
    number_mod(u1, t, (*curve)->n);
 
    /* u2 = s*w mod n */
    number_mul(t, *((*sig)->s), w);
    number_mod(u2, t, (*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(f1, abs, (*curve)->n);
    
    bool result = number_cmp(f1, *((*sig)->r)) == 0;
 
    /* Free memory */
    number_free(&h);
    ec_point_relax_pool_elt(x, (*curve)->k, STACK_1);
    field_elt_relax_pool_elt(&xx, (*curve)->k, STACK_1);
    number_tmp_free(&abs, size, STACK_1);
    number_tmp_free(&f1, size, STACK_1);
    number_tmp_free(&t, 2*size, STACK_1);
    number_tmp_free(&tt2, size, STACK_1);
    number_tmp_free(&u2, size, STACK_1);
    number_tmp_free(&u1, size, STACK_1);
    number_tmp_free(&w, size, STACK_1);
 
    return result;
}
 
int8_t 
ecgdsa_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);
#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(&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);
    printf("\nThe private key has been created its value is:\n");
    number_print(priv_key, 16);
    
    /* Computation of the public key */
    /* Here is the main difference for ECGDSA pub_key=priv_key^{-1}*G */
    number inv_priv_key; number_init(&inv_priv_key, k->size);
    number_invmod(inv_priv_key,priv_key,E->n);
    ec_point pub_key;
    ec_point_alloc(pub_key, E->k);
    ec_point_init(pub_key, E->k);
    ec_point_mul_unified(pub_key, inv_priv_key, E->G, E, STACK_1);
    number_free(&inv_priv_key);
 
    /* 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 = ecgdsa_pub_key_validation(&pub_key, &E);
    if( ret < 1 )
    {
        printf("ERROR\n");
    }
    else
    {
        printf("SUCCESS\n");
    }
    
    /* Digest to sign */
    char * digest = "982c20c2493fc9ae405b74b65a022662c014a38ef3d707217e56e57afac05994";
    
    /* Allocate ecgdsa_sig structure */
    ecgdsa_sig sig;
    ecgdsa_sign_alloc(&sig, bits_to_nblock(256));
    
    /* Sign the digest */
    ecgdsa_sign((unsigned char *)digest, &sig, priv_key, &E);
    
    printf("\nThe ECGDSA signature is: (");
    number_print(*(sig->r), 16);
    printf(", ");
    number_print(*(sig->s), 16);
    printf(")\n");
    
    /* Verify the signature */
    printf("\n-> Verify ECGDSA signature \n");
    ret = ecgdsa_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);
    ecgdsa_sign_free(&sig);
    number_free(&p);
    field_free(k);
#if MPHELL_USE_AMNS == 1
    amns_free(&AMNS);
#endif
    ec_free(E);
    
    free_mphell();
 
    return 0;
}