1193645Ssimon/* bn_x931p.c */ 2296465Sdelphij/* 3296465Sdelphij * Written by Dr Stephen N Henson (steve@openssl.org) for the OpenSSL project 4296465Sdelphij * 2005. 5193645Ssimon */ 6193645Ssimon/* ==================================================================== 7193645Ssimon * Copyright (c) 2005 The OpenSSL Project. All rights reserved. 8193645Ssimon * 9193645Ssimon * Redistribution and use in source and binary forms, with or without 10193645Ssimon * modification, are permitted provided that the following conditions 11193645Ssimon * are met: 12193645Ssimon * 13193645Ssimon * 1. Redistributions of source code must retain the above copyright 14296465Sdelphij * notice, this list of conditions and the following disclaimer. 15193645Ssimon * 16193645Ssimon * 2. Redistributions in binary form must reproduce the above copyright 17193645Ssimon * notice, this list of conditions and the following disclaimer in 18193645Ssimon * the documentation and/or other materials provided with the 19193645Ssimon * distribution. 20193645Ssimon * 21193645Ssimon * 3. All advertising materials mentioning features or use of this 22193645Ssimon * software must display the following acknowledgment: 23193645Ssimon * "This product includes software developed by the OpenSSL Project 24193645Ssimon * for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)" 25193645Ssimon * 26193645Ssimon * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 27193645Ssimon * endorse or promote products derived from this software without 28193645Ssimon * prior written permission. For written permission, please contact 29193645Ssimon * licensing@OpenSSL.org. 30193645Ssimon * 31193645Ssimon * 5. Products derived from this software may not be called "OpenSSL" 32193645Ssimon * nor may "OpenSSL" appear in their names without prior written 33193645Ssimon * permission of the OpenSSL Project. 34193645Ssimon * 35193645Ssimon * 6. Redistributions of any form whatsoever must retain the following 36193645Ssimon * acknowledgment: 37193645Ssimon * "This product includes software developed by the OpenSSL Project 38193645Ssimon * for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)" 39193645Ssimon * 40193645Ssimon * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 41193645Ssimon * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 42193645Ssimon * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 43193645Ssimon * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 44193645Ssimon * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 45193645Ssimon * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 46193645Ssimon * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 47193645Ssimon * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 48193645Ssimon * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 49193645Ssimon * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 50193645Ssimon * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 51193645Ssimon * OF THE POSSIBILITY OF SUCH DAMAGE. 52193645Ssimon * ==================================================================== 53193645Ssimon * 54193645Ssimon * This product includes cryptographic software written by Eric Young 55193645Ssimon * (eay@cryptsoft.com). This product includes software written by Tim 56193645Ssimon * Hudson (tjh@cryptsoft.com). 57193645Ssimon * 58193645Ssimon */ 59193645Ssimon 60193645Ssimon#include <stdio.h> 61193645Ssimon#include <openssl/bn.h> 62193645Ssimon 63193645Ssimon/* X9.31 routines for prime derivation */ 64193645Ssimon 65296465Sdelphij/* 66296465Sdelphij * X9.31 prime derivation. This is used to generate the primes pi (p1, p2, 67296465Sdelphij * q1, q2) from a parameter Xpi by checking successive odd integers. 68193645Ssimon */ 69193645Ssimon 70193645Ssimonstatic int bn_x931_derive_pi(BIGNUM *pi, const BIGNUM *Xpi, BN_CTX *ctx, 71296465Sdelphij BN_GENCB *cb) 72296465Sdelphij{ 73296465Sdelphij int i = 0; 74296465Sdelphij if (!BN_copy(pi, Xpi)) 75296465Sdelphij return 0; 76296465Sdelphij if (!BN_is_odd(pi) && !BN_add_word(pi, 1)) 77296465Sdelphij return 0; 78296465Sdelphij for (;;) { 79296465Sdelphij i++; 80296465Sdelphij BN_GENCB_call(cb, 0, i); 81296465Sdelphij /* NB 27 MR is specificed in X9.31 */ 82296465Sdelphij if (BN_is_prime_fasttest_ex(pi, 27, ctx, 1, cb)) 83296465Sdelphij break; 84296465Sdelphij if (!BN_add_word(pi, 2)) 85296465Sdelphij return 0; 86296465Sdelphij } 87296465Sdelphij BN_GENCB_call(cb, 2, i); 88296465Sdelphij return 1; 89296465Sdelphij} 90193645Ssimon 91296465Sdelphij/* 92296465Sdelphij * This is the main X9.31 prime derivation function. From parameters Xp1, Xp2 93296465Sdelphij * and Xp derive the prime p. If the parameters p1 or p2 are not NULL they 94296465Sdelphij * will be returned too: this is needed for testing. 95193645Ssimon */ 96193645Ssimon 97193645Ssimonint BN_X931_derive_prime_ex(BIGNUM *p, BIGNUM *p1, BIGNUM *p2, 98296465Sdelphij const BIGNUM *Xp, const BIGNUM *Xp1, 99296465Sdelphij const BIGNUM *Xp2, const BIGNUM *e, BN_CTX *ctx, 100296465Sdelphij BN_GENCB *cb) 101296465Sdelphij{ 102296465Sdelphij int ret = 0; 103193645Ssimon 104296465Sdelphij BIGNUM *t, *p1p2, *pm1; 105193645Ssimon 106296465Sdelphij /* Only even e supported */ 107296465Sdelphij if (!BN_is_odd(e)) 108296465Sdelphij return 0; 109193645Ssimon 110296465Sdelphij BN_CTX_start(ctx); 111296465Sdelphij if (!p1) 112296465Sdelphij p1 = BN_CTX_get(ctx); 113193645Ssimon 114296465Sdelphij if (!p2) 115296465Sdelphij p2 = BN_CTX_get(ctx); 116193645Ssimon 117296465Sdelphij t = BN_CTX_get(ctx); 118193645Ssimon 119296465Sdelphij p1p2 = BN_CTX_get(ctx); 120193645Ssimon 121296465Sdelphij pm1 = BN_CTX_get(ctx); 122193645Ssimon 123296465Sdelphij if (!bn_x931_derive_pi(p1, Xp1, ctx, cb)) 124296465Sdelphij goto err; 125193645Ssimon 126296465Sdelphij if (!bn_x931_derive_pi(p2, Xp2, ctx, cb)) 127296465Sdelphij goto err; 128193645Ssimon 129296465Sdelphij if (!BN_mul(p1p2, p1, p2, ctx)) 130296465Sdelphij goto err; 131193645Ssimon 132296465Sdelphij /* First set p to value of Rp */ 133193645Ssimon 134296465Sdelphij if (!BN_mod_inverse(p, p2, p1, ctx)) 135296465Sdelphij goto err; 136193645Ssimon 137296465Sdelphij if (!BN_mul(p, p, p2, ctx)) 138296465Sdelphij goto err; 139193645Ssimon 140296465Sdelphij if (!BN_mod_inverse(t, p1, p2, ctx)) 141296465Sdelphij goto err; 142193645Ssimon 143296465Sdelphij if (!BN_mul(t, t, p1, ctx)) 144296465Sdelphij goto err; 145193645Ssimon 146296465Sdelphij if (!BN_sub(p, p, t)) 147296465Sdelphij goto err; 148193645Ssimon 149296465Sdelphij if (p->neg && !BN_add(p, p, p1p2)) 150296465Sdelphij goto err; 151193645Ssimon 152296465Sdelphij /* p now equals Rp */ 153193645Ssimon 154296465Sdelphij if (!BN_mod_sub(p, p, Xp, p1p2, ctx)) 155296465Sdelphij goto err; 156193645Ssimon 157296465Sdelphij if (!BN_add(p, p, Xp)) 158296465Sdelphij goto err; 159193645Ssimon 160296465Sdelphij /* p now equals Yp0 */ 161193645Ssimon 162296465Sdelphij for (;;) { 163296465Sdelphij int i = 1; 164296465Sdelphij BN_GENCB_call(cb, 0, i++); 165296465Sdelphij if (!BN_copy(pm1, p)) 166296465Sdelphij goto err; 167296465Sdelphij if (!BN_sub_word(pm1, 1)) 168296465Sdelphij goto err; 169296465Sdelphij if (!BN_gcd(t, pm1, e, ctx)) 170296465Sdelphij goto err; 171296465Sdelphij if (BN_is_one(t) 172296465Sdelphij /* 173296465Sdelphij * X9.31 specifies 8 MR and 1 Lucas test or any prime test 174296465Sdelphij * offering similar or better guarantees 50 MR is considerably 175296465Sdelphij * better. 176296465Sdelphij */ 177296465Sdelphij && BN_is_prime_fasttest_ex(p, 50, ctx, 1, cb)) 178296465Sdelphij break; 179296465Sdelphij if (!BN_add(p, p, p1p2)) 180296465Sdelphij goto err; 181296465Sdelphij } 182193645Ssimon 183296465Sdelphij BN_GENCB_call(cb, 3, 0); 184193645Ssimon 185296465Sdelphij ret = 1; 186193645Ssimon 187296465Sdelphij err: 188193645Ssimon 189296465Sdelphij BN_CTX_end(ctx); 190193645Ssimon 191296465Sdelphij return ret; 192296465Sdelphij} 193193645Ssimon 194296465Sdelphij/* 195296465Sdelphij * Generate pair of paramters Xp, Xq for X9.31 prime generation. Note: nbits 196296465Sdelphij * paramter is sum of number of bits in both. 197193645Ssimon */ 198193645Ssimon 199193645Ssimonint BN_X931_generate_Xpq(BIGNUM *Xp, BIGNUM *Xq, int nbits, BN_CTX *ctx) 200296465Sdelphij{ 201296465Sdelphij BIGNUM *t; 202296465Sdelphij int i; 203296465Sdelphij /* 204296465Sdelphij * Number of bits for each prime is of the form 512+128s for s = 0, 1, 205296465Sdelphij * ... 206296465Sdelphij */ 207296465Sdelphij if ((nbits < 1024) || (nbits & 0xff)) 208296465Sdelphij return 0; 209296465Sdelphij nbits >>= 1; 210296465Sdelphij /* 211296465Sdelphij * The random value Xp must be between sqrt(2) * 2^(nbits-1) and 2^nbits 212296465Sdelphij * - 1. By setting the top two bits we ensure that the lower bound is 213296465Sdelphij * exceeded. 214296465Sdelphij */ 215296465Sdelphij if (!BN_rand(Xp, nbits, 1, 0)) 216296465Sdelphij return 0; 217193645Ssimon 218296465Sdelphij BN_CTX_start(ctx); 219296465Sdelphij t = BN_CTX_get(ctx); 220193645Ssimon 221296465Sdelphij for (i = 0; i < 1000; i++) { 222296465Sdelphij if (!BN_rand(Xq, nbits, 1, 0)) 223296465Sdelphij return 0; 224296465Sdelphij /* Check that |Xp - Xq| > 2^(nbits - 100) */ 225296465Sdelphij BN_sub(t, Xp, Xq); 226296465Sdelphij if (BN_num_bits(t) > (nbits - 100)) 227296465Sdelphij break; 228296465Sdelphij } 229193645Ssimon 230296465Sdelphij BN_CTX_end(ctx); 231193645Ssimon 232296465Sdelphij if (i < 1000) 233296465Sdelphij return 1; 234193645Ssimon 235296465Sdelphij return 0; 236193645Ssimon 237296465Sdelphij} 238193645Ssimon 239296465Sdelphij/* 240296465Sdelphij * Generate primes using X9.31 algorithm. Of the values p, p1, p2, Xp1 and 241296465Sdelphij * Xp2 only 'p' needs to be non-NULL. If any of the others are not NULL the 242296465Sdelphij * relevant parameter will be stored in it. Due to the fact that |Xp - Xq| > 243296465Sdelphij * 2^(nbits - 100) must be satisfied Xp and Xq are generated using the 244296465Sdelphij * previous function and supplied as input. 245193645Ssimon */ 246193645Ssimon 247193645Ssimonint BN_X931_generate_prime_ex(BIGNUM *p, BIGNUM *p1, BIGNUM *p2, 248296465Sdelphij BIGNUM *Xp1, BIGNUM *Xp2, 249296465Sdelphij const BIGNUM *Xp, 250296465Sdelphij const BIGNUM *e, BN_CTX *ctx, BN_GENCB *cb) 251296465Sdelphij{ 252296465Sdelphij int ret = 0; 253193645Ssimon 254296465Sdelphij BN_CTX_start(ctx); 255296465Sdelphij if (!Xp1) 256296465Sdelphij Xp1 = BN_CTX_get(ctx); 257296465Sdelphij if (!Xp2) 258296465Sdelphij Xp2 = BN_CTX_get(ctx); 259193645Ssimon 260296465Sdelphij if (!BN_rand(Xp1, 101, 0, 0)) 261296465Sdelphij goto error; 262296465Sdelphij if (!BN_rand(Xp2, 101, 0, 0)) 263296465Sdelphij goto error; 264296465Sdelphij if (!BN_X931_derive_prime_ex(p, p1, p2, Xp, Xp1, Xp2, e, ctx, cb)) 265296465Sdelphij goto error; 266193645Ssimon 267296465Sdelphij ret = 1; 268193645Ssimon 269296465Sdelphij error: 270296465Sdelphij BN_CTX_end(ctx); 271193645Ssimon 272296465Sdelphij return ret; 273193645Ssimon 274296465Sdelphij} 275