crypto/bn/bn_x931p.c

   1 /* bn_x931p.c */
   2 /*
   3  * Written by Dr Stephen N Henson (steve@openssl.org) for the OpenSSL project
   4  * 2005.
   5  */
   6 /* ====================================================================
   7  * Copyright (c) 2005 The OpenSSL Project.  All rights reserved.
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  *
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  *
  16  * 2. Redistributions in binary form must reproduce the above copyright
  17  *    notice, this list of conditions and the following disclaimer in
  18  *    the documentation and/or other materials provided with the
  19  *    distribution.
  20  *
  21  * 3. All advertising materials mentioning features or use of this
  22  *    software must display the following acknowledgment:
  23  *    "This product includes software developed by the OpenSSL Project
  24  *    for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)"
  25  *
  26  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
  27  *    endorse or promote products derived from this software without
  28  *    prior written permission. For written permission, please contact
  29  *    licensing@OpenSSL.org.
  30  *
  31  * 5. Products derived from this software may not be called "OpenSSL"
  32  *    nor may "OpenSSL" appear in their names without prior written
  33  *    permission of the OpenSSL Project.
  34  *
  35  * 6. Redistributions of any form whatsoever must retain the following
  36  *    acknowledgment:
  37  *    "This product includes software developed by the OpenSSL Project
  38  *    for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)"
  39  *
  40  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
  41  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  42  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  43  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
  44  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  45  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  46  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  47  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  48  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  49  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  50  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
  51  * OF THE POSSIBILITY OF SUCH DAMAGE.
  52  * ====================================================================
  53  *
  54  * This product includes cryptographic software written by Eric Young
  55  * (eay@cryptsoft.com).  This product includes software written by Tim
  56  * Hudson (tjh@cryptsoft.com).
  57  *
  58  */
  59
  60 #include <stdio.h>
  61 #include <openssl/bn.h>
  62 #include "bn_lcl.h"
  63
  64 /* X9.31 routines for prime derivation */
  65
  66 /*
  67  * X9.31 prime derivation. This is used to generate the primes pi (p1, p2,
  68  * q1, q2) from a parameter Xpi by checking successive odd integers.
  69  */
  70
  71 static int bn_x931_derive_pi(BIGNUM *pi, const BIGNUM *Xpi, BN_CTX *ctx,
  72                              BN_GENCB *cb)
  73 {
  74     int i = 0;
  75     if (!BN_copy(pi, Xpi))
  76         return 0;
  77     if (!BN_is_odd(pi) && !BN_add_word(pi, 1))
  78         return 0;
  79     for (;;) {
  80         i++;
  81         BN_GENCB_call(cb, 0, i);
  82         /* NB 27 MR is specificed in X9.31 */
  83         if (BN_is_prime_fasttest_ex(pi, 27, ctx, 1, cb))
  84             break;
  85         if (!BN_add_word(pi, 2))
  86             return 0;
  87     }
  88     BN_GENCB_call(cb, 2, i);
  89     return 1;
  90 }
  91
  92 /*
  93  * This is the main X9.31 prime derivation function. From parameters Xp1, Xp2
  94  * and Xp derive the prime p. If the parameters p1 or p2 are not NULL they
  95  * will be returned too: this is needed for testing.
  96  */
  97
  98 int BN_X931_derive_prime_ex(BIGNUM *p, BIGNUM *p1, BIGNUM *p2,
  99                             const BIGNUM *Xp, const BIGNUM *Xp1,
 100                             const BIGNUM *Xp2, const BIGNUM *e, BN_CTX *ctx,
 101                             BN_GENCB *cb)
 102 {
 103     int ret = 0;
 104
 105     BIGNUM *t, *p1p2, *pm1;
 106
 107     /* Only even e supported */
 108     if (!BN_is_odd(e))
 109         return 0;
 110
 111     BN_CTX_start(ctx);
 112     if (!p1)
 113         p1 = BN_CTX_get(ctx);
 114
 115     if (!p2)
 116         p2 = BN_CTX_get(ctx);
 117
 118     t = BN_CTX_get(ctx);
 119
 120     p1p2 = BN_CTX_get(ctx);
 121
 122     pm1 = BN_CTX_get(ctx);
 123
 124     if (!bn_x931_derive_pi(p1, Xp1, ctx, cb))
 125         goto err;
 126
 127     if (!bn_x931_derive_pi(p2, Xp2, ctx, cb))
 128         goto err;
 129
 130     if (!BN_mul(p1p2, p1, p2, ctx))
 131         goto err;
 132
 133     /* First set p to value of Rp */
 134
 135     if (!BN_mod_inverse(p, p2, p1, ctx))
 136         goto err;
 137
 138     if (!BN_mul(p, p, p2, ctx))
 139         goto err;
 140
 141     if (!BN_mod_inverse(t, p1, p2, ctx))
 142         goto err;
 143
 144     if (!BN_mul(t, t, p1, ctx))
 145         goto err;
 146
 147     if (!BN_sub(p, p, t))
 148         goto err;
 149
 150     if (p->neg && !BN_add(p, p, p1p2))
 151         goto err;
 152
 153     /* p now equals Rp */
 154
 155     if (!BN_mod_sub(p, p, Xp, p1p2, ctx))
 156         goto err;
 157
 158     if (!BN_add(p, p, Xp))
 159         goto err;
 160
 161     /* p now equals Yp0 */
 162
 163     for (;;) {
 164         int i = 1;
 165         BN_GENCB_call(cb, 0, i++);
 166         if (!BN_copy(pm1, p))
 167             goto err;
 168         if (!BN_sub_word(pm1, 1))
 169             goto err;
 170         if (!BN_gcd(t, pm1, e, ctx))
 171             goto err;
 172         if (BN_is_one(t)
 173             /*
 174              * X9.31 specifies 8 MR and 1 Lucas test or any prime test
 175              * offering similar or better guarantees 50 MR is considerably
 176              * better.
 177              */
 178             && BN_is_prime_fasttest_ex(p, 50, ctx, 1, cb))
 179             break;
 180         if (!BN_add(p, p, p1p2))
 181             goto err;
 182     }
 183
 184     BN_GENCB_call(cb, 3, 0);
 185
 186     ret = 1;
 187
 188  err:
 189
 190     BN_CTX_end(ctx);
 191
 192     return ret;
 193 }
 194
 195 /*
 196  * Generate pair of parameters Xp, Xq for X9.31 prime generation. Note: nbits
 197  * parameter is sum of number of bits in both.
 198  */
 199
 200 int BN_X931_generate_Xpq(BIGNUM *Xp, BIGNUM *Xq, int nbits, BN_CTX *ctx)
 201 {
 202     BIGNUM *t;
 203     int i;
 204     /*
 205      * Number of bits for each prime is of the form 512+128s for s = 0, 1,
 206      * ...
 207      */
 208     if ((nbits < 1024) || (nbits & 0xff))
 209         return 0;
 210     nbits >>= 1;
 211     /*
 212      * The random value Xp must be between sqrt(2) * 2^(nbits-1) and 2^nbits
 213      * - 1. By setting the top two bits we ensure that the lower bound is
 214      * exceeded.
 215      */
 216     if (!BN_rand(Xp, nbits, 1, 0))
 217         goto err;
 218
 219     BN_CTX_start(ctx);
 220     t = BN_CTX_get(ctx);
 221
 222     for (i = 0; i < 1000; i++) {
 223         if (!BN_rand(Xq, nbits, 1, 0))
 224             goto err;
 225         /* Check that |Xp - Xq| > 2^(nbits - 100) */
 226         BN_sub(t, Xp, Xq);
 227         if (BN_num_bits(t) > (nbits - 100))
 228             break;
 229     }
 230
 231     BN_CTX_end(ctx);
 232
 233     if (i < 1000)
 234         return 1;
 235
 236     return 0;
 237
 238  err:
 239     BN_CTX_end(ctx);
 240     return 0;
 241 }
 242
 243 /*
 244  * Generate primes using X9.31 algorithm. Of the values p, p1, p2, Xp1 and
 245  * Xp2 only 'p' needs to be non-NULL. If any of the others are not NULL the
 246  * relevant parameter will be stored in it. Due to the fact that |Xp - Xq| >
 247  * 2^(nbits - 100) must be satisfied Xp and Xq are generated using the
 248  * previous function and supplied as input.
 249  */
 250
 251 int BN_X931_generate_prime_ex(BIGNUM *p, BIGNUM *p1, BIGNUM *p2,
 252                               BIGNUM *Xp1, BIGNUM *Xp2,
 253                               const BIGNUM *Xp,
 254                               const BIGNUM *e, BN_CTX *ctx, BN_GENCB *cb)
 255 {
 256     int ret = 0;
 257
 258     BN_CTX_start(ctx);
 259     if (!Xp1)
 260         Xp1 = BN_CTX_get(ctx);
 261     if (!Xp2)
 262         Xp2 = BN_CTX_get(ctx);
 263
 264     if (!BN_rand(Xp1, 101, 0, 0))
 265         goto error;
 266     if (!BN_rand(Xp2, 101, 0, 0))
 267         goto error;
 268     if (!BN_X931_derive_prime_ex(p, p1, p2, Xp, Xp1, Xp2, e, ctx, cb))
 269         goto error;
 270
 271     ret = 1;
 272
 273  error:
 274     BN_CTX_end(ctx);
 275
 276     return ret;
 277
 278 }