crypto/libressl/crypto/gost/gostr341001.c

   1 /* $OpenBSD: gostr341001.c,v 1.3 2015/02/11 03:19:37 doug Exp $ */
   2 /*
   3  * Copyright (c) 2014 Dmitry Eremin-Solenikov <dbaryshkov@gmail.com>
   4  * Copyright (c) 2005-2006 Cryptocom LTD
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  *
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  *
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in
  15  *    the documentation and/or other materials provided with the
  16  *    distribution.
  17  *
  18  * 3. All advertising materials mentioning features or use of this
  19  *    software must display the following acknowledgment:
  20  *    "This product includes software developed by the OpenSSL Project
  21  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
  22  *
  23  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
  24  *    endorse or promote products derived from this software without
  25  *    prior written permission. For written permission, please contact
  26  *    openssl-core@openssl.org.
  27  *
  28  * 5. Products derived from this software may not be called "OpenSSL"
  29  *    nor may "OpenSSL" appear in their names without prior written
  30  *    permission of the OpenSSL Project.
  31  *
  32  * 6. Redistributions of any form whatsoever must retain the following
  33  *    acknowledgment:
  34  *    "This product includes software developed by the OpenSSL Project
  35  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
  36  *
  37  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
  38  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  39  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  40  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
  41  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  42  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  43  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  44  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  45  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  46  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  47  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  48  * OF THE POSSIBILITY OF SUCH DAMAGE.
  49  * ====================================================================
  50  */
  51
  52 #include <string.h>
  53
  54 #include <openssl/opensslconf.h>
  55
  56 #ifndef OPENSSL_NO_GOST
  57 #include <openssl/bn.h>
  58 #include <openssl/err.h>
  59 #include <openssl/gost.h>
  60 #include "gost_locl.h"
  61
  62 /* Convert little-endian byte array into bignum */
  63 BIGNUM *
  64 GOST_le2bn(const unsigned char *buf, size_t len, BIGNUM *bn)
  65 {
  66         unsigned char temp[64];
  67         int i;
  68
  69         if (len > 64)
  70                 return NULL;
  71
  72         for (i = 0; i < len; i++) {
  73                 temp[len - 1 - i] = buf[i];
  74         }
  75
  76         return BN_bin2bn(temp, len, bn);
  77 }
  78
  79 int
  80 GOST_bn2le(BIGNUM *bn, unsigned char *buf, int len)
  81 {
  82         unsigned char temp[64];
  83         int i, bytes;
  84
  85         bytes = BN_num_bytes(bn);
  86         if (len > 64 || bytes > len)
  87                 return 0;
  88
  89         BN_bn2bin(bn, temp);
  90
  91         for (i = 0; i < bytes; i++) {
  92                 buf[bytes - 1 - i] = temp[i];
  93         }
  94
  95         memset(buf + bytes, 0, len - bytes);
  96
  97         return 1;
  98 }
  99
 100 int
 101 gost2001_compute_public(GOST_KEY *ec)
 102 {
 103         const EC_GROUP *group = GOST_KEY_get0_group(ec);
 104         EC_POINT *pub_key = NULL;
 105         const BIGNUM *priv_key = NULL;
 106         BN_CTX *ctx = NULL;
 107         int ok = 0;
 108
 109         if (group == NULL) {
 110                 GOSTerr(GOST_F_GOST2001_COMPUTE_PUBLIC,
 111                     GOST_R_KEY_IS_NOT_INITIALIZED);
 112                 return 0;
 113         }
 114         ctx = BN_CTX_new();
 115         if (ctx == NULL) {
 116                 GOSTerr(GOST_F_GOST2001_COMPUTE_PUBLIC,
 117                     ERR_R_MALLOC_FAILURE);
 118                 return 0;
 119         }
 120         BN_CTX_start(ctx);
 121         if ((priv_key = GOST_KEY_get0_private_key(ec)) == NULL)
 122                 goto err;
 123
 124         pub_key = EC_POINT_new(group);
 125         if (pub_key == NULL)
 126                 goto err;
 127         if (EC_POINT_mul(group, pub_key, priv_key, NULL, NULL, ctx) == 0)
 128                 goto err;
 129         if (GOST_KEY_set_public_key(ec, pub_key) == 0)
 130                 goto err;
 131         ok = 1;
 132
 133         if (ok == 0) {
 134 err:
 135                 GOSTerr(GOST_F_GOST2001_COMPUTE_PUBLIC, ERR_R_EC_LIB);
 136         }
 137         EC_POINT_free(pub_key);
 138         if (ctx != NULL) {
 139                 BN_CTX_end(ctx);
 140                 BN_CTX_free(ctx);
 141         }
 142         return ok;
 143 }
 144
 145 ECDSA_SIG *
 146 gost2001_do_sign(BIGNUM *md, GOST_KEY *eckey)
 147 {
 148         ECDSA_SIG *newsig = NULL;
 149         BIGNUM *order = NULL;
 150         const EC_GROUP *group;
 151         const BIGNUM *priv_key;
 152         BIGNUM *r = NULL, *s = NULL, *X = NULL, *tmp = NULL, *tmp2 = NULL, *k =
 153             NULL, *e = NULL;
 154         EC_POINT *C = NULL;
 155         BN_CTX *ctx = BN_CTX_new();
 156         int ok = 0;
 157
 158         if (ctx == NULL) {
 159                 GOSTerr(GOST_F_GOST2001_DO_SIGN, ERR_R_MALLOC_FAILURE);
 160                 return NULL;
 161         }
 162         BN_CTX_start(ctx);
 163         newsig = ECDSA_SIG_new();
 164         if (newsig == NULL) {
 165                 GOSTerr(GOST_F_GOST2001_DO_SIGN, ERR_R_MALLOC_FAILURE);
 166                 goto err;
 167         }
 168         s = newsig->s;
 169         r = newsig->r;
 170         group = GOST_KEY_get0_group(eckey);
 171         if ((order = BN_CTX_get(ctx)) == NULL)
 172                 goto err;
 173         if (EC_GROUP_get_order(group, order, ctx) == 0)
 174                 goto err;
 175         priv_key = GOST_KEY_get0_private_key(eckey);
 176         if ((e = BN_CTX_get(ctx)) == NULL)
 177                 goto err;
 178         if (BN_mod(e, md, order, ctx) == 0)
 179                 goto err;
 180         if (BN_is_zero(e))
 181                 BN_one(e);
 182         if ((k = BN_CTX_get(ctx)) == NULL)
 183                 goto err;
 184         if ((X = BN_CTX_get(ctx)) == NULL)
 185                 goto err;
 186         if ((C = EC_POINT_new(group)) == NULL)
 187                 goto err;
 188         do {
 189                 do {
 190                         if (!BN_rand_range(k, order)) {
 191                                 GOSTerr(GOST_F_GOST2001_DO_SIGN,
 192                                         GOST_R_RANDOM_NUMBER_GENERATOR_FAILED);
 193                                 goto err;
 194                         }
 195                         /*
 196                          * We do not want timing information to leak the length
 197                          * of k, so we compute G*k using an equivalent scalar
 198                          * of fixed bit-length.
 199                          */
 200                         if (BN_add(k, k, order) == 0)
 201                                 goto err;
 202                         if (BN_num_bits(k) <= BN_num_bits(order))
 203                                 if (BN_add(k, k, order) == 0)
 204                                         goto err;
 205
 206                         if (EC_POINT_mul(group, C, k, NULL, NULL, ctx) == 0) {
 207                                 GOSTerr(GOST_F_GOST2001_DO_SIGN, ERR_R_EC_LIB);
 208                                 goto err;
 209                         }
 210                         if (EC_POINT_get_affine_coordinates_GFp(group, C, X,
 211                             NULL, ctx) == 0) {
 212                                 GOSTerr(GOST_F_GOST2001_DO_SIGN, ERR_R_EC_LIB);
 213                                 goto err;
 214                         }
 215                         if (BN_nnmod(r, X, order, ctx) == 0)
 216                                 goto err;
 217                 } while (BN_is_zero(r));
 218                 /* s = (r*priv_key+k*e) mod order */
 219                 if (tmp == NULL) {
 220                         if ((tmp = BN_CTX_get(ctx)) == NULL)
 221                                 goto err;
 222                 }
 223                 if (BN_mod_mul(tmp, priv_key, r, order, ctx) == 0)
 224                         goto err;
 225                 if (tmp2 == NULL) {
 226                         if ((tmp2 = BN_CTX_get(ctx)) == NULL)
 227                                 goto err;
 228                 }
 229                 if (BN_mod_mul(tmp2, k, e, order, ctx) == 0)
 230                         goto err;
 231                 if (BN_mod_add(s, tmp, tmp2, order, ctx) == 0)
 232                         goto err;
 233         } while (BN_is_zero(s));
 234         ok = 1;
 235
 236 err:
 237         EC_POINT_free(C);
 238         if (ctx != NULL) {
 239                 BN_CTX_end(ctx);
 240                 BN_CTX_free(ctx);
 241         }
 242         if (ok == 0) {
 243                 ECDSA_SIG_free(newsig);
 244                 newsig = NULL;
 245         }
 246         return newsig;
 247 }
 248
 249 int
 250 gost2001_do_verify(BIGNUM *md, ECDSA_SIG *sig, GOST_KEY *ec)
 251 {
 252         BN_CTX *ctx = BN_CTX_new();
 253         const EC_GROUP *group = GOST_KEY_get0_group(ec);
 254         BIGNUM *order;
 255         BIGNUM *e = NULL, *R = NULL, *v = NULL, *z1 = NULL, *z2 = NULL;
 256         BIGNUM *X = NULL, *tmp = NULL;
 257         EC_POINT *C = NULL;
 258         const EC_POINT *pub_key = NULL;
 259         int ok = 0;
 260
 261         if (ctx == NULL)
 262                 goto err;
 263         BN_CTX_start(ctx);
 264         if ((order = BN_CTX_get(ctx)) == NULL)
 265                 goto err;
 266         if ((e = BN_CTX_get(ctx)) == NULL)
 267                 goto err;
 268         if ((z1 = BN_CTX_get(ctx)) == NULL)
 269                 goto err;
 270         if ((z2 = BN_CTX_get(ctx)) == NULL)
 271                 goto err;
 272         if ((tmp = BN_CTX_get(ctx)) == NULL)
 273                 goto err;
 274         if ((X = BN_CTX_get(ctx)) == NULL)
 275                 goto err;
 276         if ((R = BN_CTX_get(ctx)) == NULL)
 277                 goto err;
 278         if ((v = BN_CTX_get(ctx)) == NULL)
 279                 goto err;
 280
 281         if (EC_GROUP_get_order(group, order, ctx) == 0)
 282                 goto err;
 283         pub_key = GOST_KEY_get0_public_key(ec);
 284         if (BN_is_zero(sig->s) || BN_is_zero(sig->r) ||
 285             BN_cmp(sig->s, order) >= 1 || BN_cmp(sig->r, order) >= 1) {
 286                 GOSTerr(GOST_F_GOST2001_DO_VERIFY,
 287                     GOST_R_SIGNATURE_PARTS_GREATER_THAN_Q);
 288                 goto err;
 289         }
 290
 291         if (BN_mod(e, md, order, ctx) == 0)
 292                 goto err;
 293         if (BN_is_zero(e))
 294                 BN_one(e);
 295         if ((v = BN_mod_inverse(v, e, order, ctx)) == NULL)
 296                 goto err;
 297         if (BN_mod_mul(z1, sig->s, v, order, ctx) == 0)
 298                 goto err;
 299         if (BN_sub(tmp, order, sig->r) == 0)
 300                 goto err;
 301         if (BN_mod_mul(z2, tmp, v, order, ctx) == 0)
 302                 goto err;
 303         if ((C = EC_POINT_new(group)) == NULL)
 304                 goto err;
 305         if (EC_POINT_mul(group, C, z1, pub_key, z2, ctx) == 0) {
 306                 GOSTerr(GOST_F_GOST2001_DO_VERIFY, ERR_R_EC_LIB);
 307                 goto err;
 308         }
 309         if (EC_POINT_get_affine_coordinates_GFp(group, C, X, NULL, ctx) == 0) {
 310                 GOSTerr(GOST_F_GOST2001_DO_VERIFY, ERR_R_EC_LIB);
 311                 goto err;
 312         }
 313         if (BN_mod(R, X, order, ctx) == 0)
 314                 goto err;
 315         if (BN_cmp(R, sig->r) != 0) {
 316                 GOSTerr(GOST_F_GOST2001_DO_VERIFY, GOST_R_SIGNATURE_MISMATCH);
 317         } else {
 318                 ok = 1;
 319         }
 320 err:
 321         EC_POINT_free(C);
 322         if (ctx != NULL) {
 323                 BN_CTX_end(ctx);
 324                 BN_CTX_free(ctx);
 325         }
 326         return ok;
 327 }
 328
 329 /* Implementation of CryptoPro VKO 34.10-2001 algorithm */
 330 int
 331 VKO_compute_key(BIGNUM *X, BIGNUM *Y, const GOST_KEY *pkey, GOST_KEY *priv_key,
 332     const BIGNUM *ukm)
 333 {
 334         BIGNUM *p = NULL, *order = NULL;
 335         const BIGNUM *key = GOST_KEY_get0_private_key(priv_key);
 336         const EC_GROUP *group = GOST_KEY_get0_group(priv_key);
 337         const EC_POINT *pub_key = GOST_KEY_get0_public_key(pkey);
 338         EC_POINT *pnt;
 339         BN_CTX *ctx = NULL;
 340         int ok = 0;
 341
 342         pnt = EC_POINT_new(group);
 343         if (pnt == NULL)
 344                 goto err;
 345         ctx = BN_CTX_new();
 346         if (ctx == NULL)
 347                 goto err;
 348         BN_CTX_start(ctx);
 349         if ((p = BN_CTX_get(ctx)) == NULL)
 350                 goto err;
 351         if ((order = BN_CTX_get(ctx)) == NULL)
 352                 goto err;
 353         if (EC_GROUP_get_order(group, order, ctx) == 0)
 354                 goto err;
 355         if (BN_mod_mul(p, key, ukm, order, ctx) == 0)
 356                 goto err;
 357         if (EC_POINT_mul(group, pnt, NULL, pub_key, p, ctx) == 0)
 358                 goto err;
 359         if (EC_POINT_get_affine_coordinates_GFp(group, pnt, X, Y, ctx) == 0)
 360                 goto err;
 361         ok = 1;
 362
 363 err:
 364         if (ctx != NULL) {
 365                 BN_CTX_end(ctx);
 366                 BN_CTX_free(ctx);
 367         }
 368         EC_POINT_free(pnt);
 369         return ok;
 370 }
 371
 372 int
 373 gost2001_keygen(GOST_KEY *ec)
 374 {
 375         BIGNUM *order = BN_new(), *d = BN_new();
 376         const EC_GROUP *group = GOST_KEY_get0_group(ec);
 377         int rc = 0;
 378
 379         if (order == NULL || d == NULL)
 380                 goto err;
 381         if (EC_GROUP_get_order(group, order, NULL) == 0)
 382                 goto err;
 383
 384         do {
 385                 if (BN_rand_range(d, order) == 0) {
 386                         GOSTerr(GOST_F_GOST2001_KEYGEN,
 387                                 GOST_R_RANDOM_NUMBER_GENERATOR_FAILED);
 388                         goto err;
 389                 }
 390         } while (BN_is_zero(d));
 391
 392         if (GOST_KEY_set_private_key(ec, d) == 0)
 393                 goto err;
 394         rc = gost2001_compute_public(ec);
 395
 396 err:
 397         BN_free(d);
 398         BN_free(order);
 399         return rc;
 400 }
 401 #endif