1  /* dsa.c


2  *


3  * Copyright (C) 20062015 wolfSSL Inc.


4  *


5  * This file is part of wolfSSL. (formerly known as CyaSSL)


6  *


7  * wolfSSL is free software; you can redistribute it and/or modify


8  * it under the terms of the GNU General Public License as published by


9  * the Free Software Foundation; either version 2 of the License, or


10  * (at your option) any later version.


11  *


12  * wolfSSL is distributed in the hope that it will be useful,


13  * but WITHOUT ANY WARRANTY; without even the implied warranty of


14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the


15  * GNU General Public License for more details.


16  *


17  * You should have received a copy of the GNU General Public License


18  * along with this program; if not, write to the Free Software


19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 021101301, USA


20  */


21 


22  #ifdef HAVE_CONFIG_H


23  #include <config.h>


24  #endif


25 


26  #include <wolfssl/wolfcrypt/settings.h>


27 


28  #ifndef NO_DSA


29 


30  #include <wolfssl/wolfcrypt/random.h>


31  #include <wolfssl/wolfcrypt/integer.h>


32  #include <wolfssl/wolfcrypt/errorcrypt.h>


33  #include <wolfssl/wolfcrypt/logging.h>


34  #include <wolfssl/wolfcrypt/sha.h>


35  #include <wolfssl/wolfcrypt/dsa.h>


36 


37 


38  enum {


39  DSA_HALF_SIZE = 20, /* r and s size */


40  DSA_SIG_SIZE = 40 /* signature size */


41  };


42 


43 


44  #ifdef min


45  #define WOLFSSL_HAVE_MIN


46  #endif


47  #ifndef WOLFSSL_HAVE_MIN


48  #define WOLFSSL_HAVE_MIN


49 


50  static INLINE word32 min(word32 a, word32 b)


51  {


52  return a > b ? b : a;


53  }


54 


55  #endif /* WOLFSSL_HAVE_MIN */


56 


57 


58  void wc_InitDsaKey(DsaKey* key)


59  {


60  key>type = 1; /* haven't decided yet */


61 


62  /* TomsFastMath doesn't use memory allocation */


63  #ifndef USE_FAST_MATH


64  key>p.dp = 0; /* public alloc parts */


65  key>q.dp = 0;


66  key>g.dp = 0;


67  key>y.dp = 0;


68 


69  key>x.dp = 0; /* private alloc parts */


70  #endif


71  }


72 


73 


74  void wc_FreeDsaKey(DsaKey* key)


75  {


76  (void)key;


77  /* TomsFastMath doesn't use memory allocation */


78  #ifndef USE_FAST_MATH


79  if (key>type == DSA_PRIVATE)


80  mp_clear(&key>x);


81  mp_clear(&key>y);


82  mp_clear(&key>g);


83  mp_clear(&key>q);


84  mp_clear(&key>p);


85  #endif


86  }


87 


88  #ifdef WOLFSSL_KEY_GEN


89 


90  int wc_MakeDsaKey(WC_RNG *rng, DsaKey *dsa)


91  {


92  unsigned char *buf;


93  int qsize, err;


94 


95  if (rng == NULL  dsa == NULL)


96  return BAD_FUNC_ARG;


97 


98  qsize = mp_unsigned_bin_size(&dsa>q);


99  if (qsize == 0)


100  return BAD_FUNC_ARG;


101 


102  /* allocate ram */


103  buf = (unsigned char *)XMALLOC(qsize, NULL,


104  DYNAMIC_TYPE_TMP_BUFFER);


105  if (buf == NULL)


106  return MEMORY_E;


107 


108  if (mp_init(&dsa>x) != MP_OKAY) {


109  XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER);


110  return MP_INIT_E;


111  }


112 


113  do {


114  /* make a random exponent mod q */


115  err = wc_RNG_GenerateBlock(rng, buf, qsize);


116  if (err != MP_OKAY) {


117  mp_clear(&dsa>x);


118  XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER);


119  return err;


120  }


121 


122  err = mp_read_unsigned_bin(&dsa>x, buf, qsize);


123  if (err != MP_OKAY) {


124  mp_clear(&dsa>x);


125  XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER);


126  return err;


127  }


128  } while (mp_cmp_d(&dsa>x, 1) != MP_GT);


129 


130  XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER);


131 


132  if (mp_init(&dsa>y) != MP_OKAY) {


133  mp_clear(&dsa>x);


134  return MP_INIT_E;


135  }


136 


137  /* public key : y = g^x mod p */


138  err = mp_exptmod(&dsa>g, &dsa>x, &dsa>p, &dsa>y);


139  if (err != MP_OKAY) {


140  mp_clear(&dsa>x);


141  mp_clear(&dsa>y);


142  return err;


143  }


144 


145  dsa>type = DSA_PRIVATE;


146 


147  return MP_OKAY;


148  }


149 


150  /* modulus_size in bits */


151  int wc_MakeDsaParameters(WC_RNG *rng, int modulus_size, DsaKey *dsa)


152  {


153  mp_int tmp, tmp2;


154  int err, msize, qsize,


155  loop_check_prime = 0,


156  check_prime = MP_NO;


157  unsigned char *buf;


158 


159  if (rng == NULL  dsa == NULL)


160  return BAD_FUNC_ARG;


161 


162  /* set group size in bytes from modulus size


163  * FIPS 1864 defines valid values (1024, 160) (2048, 256) (3072, 256)


164  */


165  switch (modulus_size) {


166  case 1024:


167  qsize = 20;


168  break;


169  case 2048:


170  case 3072:


171  qsize = 32;


172  break;


173  default:


174  return BAD_FUNC_ARG;


175  break;


176  }


177 


178  /* modulus size in bytes */


179  msize = modulus_size / 8;


180 


181  /* allocate ram */


182  buf = (unsigned char *)XMALLOC(msize  qsize,


183  NULL, DYNAMIC_TYPE_TMP_BUFFER);


184  if (buf == NULL) {


185  return MEMORY_E;


186  }


187 


188  /* make a random string that will be multplied against q */


189  err = wc_RNG_GenerateBlock(rng, buf, msize  qsize);


190  if (err != MP_OKAY) {


191  XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER);


192  return err;


193  }


194 


195  /* force magnitude */


196  buf[0] = 0xC0;


197 


198  /* force even */


199  buf[msize  qsize  1] &= ~1;


200 


201  if (mp_init_multi(&tmp2, &dsa>p, &dsa>q, 0, 0, 0) != MP_OKAY) {


202  mp_clear(&dsa>q);


203  XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER);


204  return MP_INIT_E;


205  }


206 


207  err = mp_read_unsigned_bin(&tmp2, buf, msize  qsize);


208  if (err != MP_OKAY) {


209  mp_clear(&dsa>q);


210  mp_clear(&dsa>p);


211  mp_clear(&tmp2);


212  XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER);


213  return err;


214  }


215  XFREE(buf, NULL, DYNAMIC_TYPE_TMP_BUFFER);


216 


217  /* make our prime q */


218  err = mp_rand_prime(&dsa>q, qsize, rng, NULL);


219  if (err != MP_OKAY) {


220  mp_clear(&dsa>q);


221  mp_clear(&dsa>p);


222  mp_clear(&tmp2);


223  return err;


224  }


225 


226  /* p = random * q */


227  err = mp_mul(&dsa>q, &tmp2, &dsa>p);


228  if (err != MP_OKAY) {


229  mp_clear(&dsa>q);


230  mp_clear(&dsa>p);


231  mp_clear(&tmp2);


232  return err;


233  }


234 


235  /* p = random * q + 1, so q is a prime divisor of p1 */


236  err = mp_add_d(&dsa>p, 1, &dsa>p);


237  if (err != MP_OKAY) {


238  mp_clear(&dsa>q);


239  mp_clear(&dsa>p);


240  mp_clear(&tmp2);


241  return err;


242  }


243 


244  if (mp_init(&tmp) != MP_OKAY) {


245  mp_clear(&dsa>q);


246  mp_clear(&dsa>p);


247  mp_clear(&tmp2);


248  return MP_INIT_E;


249  }


250 


251  /* tmp = 2q */


252  err = mp_add(&dsa>q, &dsa>q, &tmp);


253  if (err != MP_OKAY) {


254  mp_clear(&dsa>q);


255  mp_clear(&dsa>p);


256  mp_clear(&tmp);


257  mp_clear(&tmp2);


258  return err;


259  }


260 


261  /* loop until p is prime */


262  while (check_prime == MP_NO) {


263  err = mp_prime_is_prime(&dsa>p, 8, &check_prime);


264  if (err != MP_OKAY) {


265  mp_clear(&dsa>q);


266  mp_clear(&dsa>p);


267  mp_clear(&tmp);


268  mp_clear(&tmp2);


269  return err;


270  }


271 


272  if (check_prime != MP_YES) {


273  /* p += 2q */


274  err = mp_add(&tmp, &dsa>p, &dsa>p);


275  if (err != MP_OKAY) {


276  mp_clear(&dsa>q);


277  mp_clear(&dsa>p);


278  mp_clear(&tmp);


279  mp_clear(&tmp2);


280  return err;


281  }


282 


283  loop_check_prime++;


284  }


285  }


286 


287  /* tmp2 += (2*loop_check_prime)


288  * to have p = (q * tmp2) + 1 prime


289  */


290  if (loop_check_prime) {


291  err = mp_add_d(&tmp2, 2*loop_check_prime, &tmp2);


292  if (err != MP_OKAY) {


293  mp_clear(&dsa>q);


294  mp_clear(&dsa>p);


295  mp_clear(&tmp);


296  mp_clear(&tmp2);


297  return err;


298  }


299  }


300 


301  if (mp_init(&dsa>g) != MP_OKAY) {


302  mp_clear(&dsa>q);


303  mp_clear(&dsa>p);


304  mp_clear(&tmp);


305  mp_clear(&tmp2);


306  return MP_INIT_E;


307  }


308 


309  /* find a value g for which g^tmp2 != 1 */


310  mp_set(&dsa>g, 1);


311 


312  do {


313  err = mp_add_d(&dsa>g, 1, &dsa>g);


314  if (err != MP_OKAY) {


315  mp_clear(&dsa>q);


316  mp_clear(&dsa>p);


317  mp_clear(&dsa>g);


318  mp_clear(&tmp);


319  mp_clear(&tmp2);


320  return err;


321  }


322 


323  err = mp_exptmod(&dsa>g, &tmp2, &dsa>p, &tmp);


324  if (err != MP_OKAY) {


325  mp_clear(&dsa>q);


326  mp_clear(&dsa>p);


327  mp_clear(&dsa>g);


328  mp_clear(&tmp);


329  mp_clear(&tmp2);


330  return err;


331  }


332 


333  } while (mp_cmp_d(&tmp, 1) == MP_EQ);


334 


335  /* at this point tmp generates a group of order q mod p */


336  mp_exch(&tmp, &dsa>g);


337 


338  mp_clear(&tmp);


339  mp_clear(&tmp2);


340 


341  return MP_OKAY;


342  }


343  #endif /* WOLFSSL_KEY_GEN */


344 


345 


346  int wc_DsaSign(const byte* digest, byte* out, DsaKey* key, WC_RNG* rng)


347  {


348  mp_int k, kInv, r, s, H;


349  int ret, sz;


350  byte buffer[DSA_HALF_SIZE];


351 


352  sz = min(sizeof(buffer), mp_unsigned_bin_size(&key>q));


353 


354  /* generate k */


355  ret = wc_RNG_GenerateBlock(rng, buffer, sz);


356  if (ret != 0)


357  return ret;


358 


359  buffer[0] = 0x0C;


360 


361  if (mp_init_multi(&k, &kInv, &r, &s, &H, 0) != MP_OKAY)


362  return MP_INIT_E;


363 


364  if (mp_read_unsigned_bin(&k, buffer, sz) != MP_OKAY)


365  ret = MP_READ_E;


366 


367  if (ret == 0 && mp_cmp_d(&k, 1) != MP_GT)


368  ret = MP_CMP_E;


369 


370  /* inverse k mod q */


371  if (ret == 0 && mp_invmod(&k, &key>q, &kInv) != MP_OKAY)


372  ret = MP_INVMOD_E;


373 


374  /* generate r, r = (g exp k mod p) mod q */


375  if (ret == 0 && mp_exptmod(&key>g, &k, &key>p, &r) != MP_OKAY)


376  ret = MP_EXPTMOD_E;


377 


378  if (ret == 0 && mp_mod(&r, &key>q, &r) != MP_OKAY)


379  ret = MP_MOD_E;


380 


381  /* generate H from sha digest */


382  if (ret == 0 && mp_read_unsigned_bin(&H, digest,SHA_DIGEST_SIZE) != MP_OKAY)


383  ret = MP_READ_E;


384 


385  /* generate s, s = (kInv * (H + x*r)) % q */


386  if (ret == 0 && mp_mul(&key>x, &r, &s) != MP_OKAY)


387  ret = MP_MUL_E;


388 


389  if (ret == 0 && mp_add(&s, &H, &s) != MP_OKAY)


390  ret = MP_ADD_E;


391 


392  if (ret == 0 && mp_mulmod(&s, &kInv, &key>q, &s) != MP_OKAY)


393  ret = MP_MULMOD_E;


394 


395  /* write out */


396  if (ret == 0) {


397  int rSz = mp_unsigned_bin_size(&r);


398  int sSz = mp_unsigned_bin_size(&s);


399 


400  if (rSz == DSA_HALF_SIZE  1) {


401  out[0] = 0;


402  out++;


403  }


404 


405  if (mp_to_unsigned_bin(&r, out) != MP_OKAY)


406  ret = MP_TO_E;


407  else {


408  if (sSz == DSA_HALF_SIZE  1) {


409  out[rSz] = 0;


410  out++;


411  }


412  ret = mp_to_unsigned_bin(&s, out + rSz);


413  }


414  }


415 


416  mp_clear(&H);


417  mp_clear(&s);


418  mp_clear(&r);


419  mp_clear(&kInv);


420  mp_clear(&k);


421 


422  return ret;


423  }


424 


425 


426  int wc_DsaVerify(const byte* digest, const byte* sig, DsaKey* key, int* answer)


427  {


428  mp_int w, u1, u2, v, r, s;


429  int ret = 0;


430 


431  if (mp_init_multi(&w, &u1, &u2, &v, &r, &s) != MP_OKAY)


432  return MP_INIT_E;


433 


434  /* set r and s from signature */


435  if (mp_read_unsigned_bin(&r, sig, DSA_HALF_SIZE) != MP_OKAY 


436  mp_read_unsigned_bin(&s, sig + DSA_HALF_SIZE, DSA_HALF_SIZE) != MP_OKAY)


437  ret = MP_READ_E;


438 


439  /* sanity checks */


440  if (ret == 0) {


441  if (mp_iszero(&r) == MP_YES  mp_iszero(&s) == MP_YES 


442  mp_cmp(&r, &key>q) != MP_LT  mp_cmp(&s, &key>q) != MP_LT) {


443  ret = MP_ZERO_E;


444  }


445  }


446 


447  /* put H into u1 from sha digest */


448  if (ret == 0 && mp_read_unsigned_bin(&u1,digest,SHA_DIGEST_SIZE) != MP_OKAY)


449  ret = MP_READ_E;


450 


451  /* w = s invmod q */


452  if (ret == 0 && mp_invmod(&s, &key>q, &w) != MP_OKAY)


453  ret = MP_INVMOD_E;


454 


455  /* u1 = (H * w) % q */


456  if (ret == 0 && mp_mulmod(&u1, &w, &key>q, &u1) != MP_OKAY)


457  ret = MP_MULMOD_E;


458 


459  /* u2 = (r * w) % q */


460  if (ret == 0 && mp_mulmod(&r, &w, &key>q, &u2) != MP_OKAY)


461  ret = MP_MULMOD_E;


462 


463  /* verify v = ((g^u1 * y^u2) mod p) mod q */


464  if (ret == 0 && mp_exptmod(&key>g, &u1, &key>p, &u1) != MP_OKAY)


465  ret = MP_EXPTMOD_E;


466 


467  if (ret == 0 && mp_exptmod(&key>y, &u2, &key>p, &u2) != MP_OKAY)


468  ret = MP_EXPTMOD_E;


469 


470  if (ret == 0 && mp_mulmod(&u1, &u2, &key>p, &v) != MP_OKAY)


471  ret = MP_MULMOD_E;


472 


473  if (ret == 0 && mp_mod(&v, &key>q, &v) != MP_OKAY)


474  ret = MP_MULMOD_E;


475 


476  /* do they match */


477  if (ret == 0 && mp_cmp(&r, &v) == MP_EQ)


478  *answer = 1;


479  else


480  *answer = 0;


481 


482  mp_clear(&s);


483  mp_clear(&r);


484  mp_clear(&u1);


485  mp_clear(&u2);


486  mp_clear(&w);


487  mp_clear(&v);


488 


489  return ret;


490  }


491 


492 


493  #endif /* NO_DSA */


494 

