1193645Ssimon/* bn_x931p.c */ 2280304Sjkim/* 3280304Sjkim * Written by Dr Stephen N Henson (steve@openssl.org) for the OpenSSL project 4280304Sjkim * 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 14280304Sjkim * 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 65280304Sjkim/* 66280304Sjkim * X9.31 prime derivation. This is used to generate the primes pi (p1, p2, 67280304Sjkim * 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, 71280304Sjkim BN_GENCB *cb) 72280304Sjkim{ 73280304Sjkim int i = 0; 74280304Sjkim if (!BN_copy(pi, Xpi)) 75280304Sjkim return 0; 76280304Sjkim if (!BN_is_odd(pi) && !BN_add_word(pi, 1)) 77280304Sjkim return 0; 78280304Sjkim for (;;) { 79280304Sjkim i++; 80280304Sjkim BN_GENCB_call(cb, 0, i); 81280304Sjkim /* NB 27 MR is specificed in X9.31 */ 82280304Sjkim if (BN_is_prime_fasttest_ex(pi, 27, ctx, 1, cb)) 83280304Sjkim break; 84280304Sjkim if (!BN_add_word(pi, 2)) 85280304Sjkim return 0; 86280304Sjkim } 87280304Sjkim BN_GENCB_call(cb, 2, i); 88280304Sjkim return 1; 89280304Sjkim} 90193645Ssimon 91280304Sjkim/* 92280304Sjkim * This is the main X9.31 prime derivation function. From parameters Xp1, Xp2 93280304Sjkim * and Xp derive the prime p. If the parameters p1 or p2 are not NULL they 94280304Sjkim * will be returned too: this is needed for testing. 95193645Ssimon */ 96193645Ssimon 97193645Ssimonint BN_X931_derive_prime_ex(BIGNUM *p, BIGNUM *p1, BIGNUM *p2, 98280304Sjkim const BIGNUM *Xp, const BIGNUM *Xp1, 99280304Sjkim const BIGNUM *Xp2, const BIGNUM *e, BN_CTX *ctx, 100280304Sjkim BN_GENCB *cb) 101280304Sjkim{ 102280304Sjkim int ret = 0; 103193645Ssimon 104280304Sjkim BIGNUM *t, *p1p2, *pm1; 105193645Ssimon 106280304Sjkim /* Only even e supported */ 107280304Sjkim if (!BN_is_odd(e)) 108280304Sjkim return 0; 109193645Ssimon 110280304Sjkim BN_CTX_start(ctx); 111280304Sjkim if (!p1) 112280304Sjkim p1 = BN_CTX_get(ctx); 113193645Ssimon 114280304Sjkim if (!p2) 115280304Sjkim p2 = BN_CTX_get(ctx); 116193645Ssimon 117280304Sjkim t = BN_CTX_get(ctx); 118193645Ssimon 119280304Sjkim p1p2 = BN_CTX_get(ctx); 120193645Ssimon 121280304Sjkim pm1 = BN_CTX_get(ctx); 122193645Ssimon 123280304Sjkim if (!bn_x931_derive_pi(p1, Xp1, ctx, cb)) 124280304Sjkim goto err; 125193645Ssimon 126280304Sjkim if (!bn_x931_derive_pi(p2, Xp2, ctx, cb)) 127280304Sjkim goto err; 128193645Ssimon 129280304Sjkim if (!BN_mul(p1p2, p1, p2, ctx)) 130280304Sjkim goto err; 131193645Ssimon 132280304Sjkim /* First set p to value of Rp */ 133193645Ssimon 134280304Sjkim if (!BN_mod_inverse(p, p2, p1, ctx)) 135280304Sjkim goto err; 136193645Ssimon 137280304Sjkim if (!BN_mul(p, p, p2, ctx)) 138280304Sjkim goto err; 139193645Ssimon 140280304Sjkim if (!BN_mod_inverse(t, p1, p2, ctx)) 141280304Sjkim goto err; 142193645Ssimon 143280304Sjkim if (!BN_mul(t, t, p1, ctx)) 144280304Sjkim goto err; 145193645Ssimon 146280304Sjkim if (!BN_sub(p, p, t)) 147280304Sjkim goto err; 148193645Ssimon 149280304Sjkim if (p->neg && !BN_add(p, p, p1p2)) 150280304Sjkim goto err; 151193645Ssimon 152280304Sjkim /* p now equals Rp */ 153193645Ssimon 154280304Sjkim if (!BN_mod_sub(p, p, Xp, p1p2, ctx)) 155280304Sjkim goto err; 156193645Ssimon 157280304Sjkim if (!BN_add(p, p, Xp)) 158280304Sjkim goto err; 159193645Ssimon 160280304Sjkim /* p now equals Yp0 */ 161193645Ssimon 162280304Sjkim for (;;) { 163280304Sjkim int i = 1; 164280304Sjkim BN_GENCB_call(cb, 0, i++); 165280304Sjkim if (!BN_copy(pm1, p)) 166280304Sjkim goto err; 167280304Sjkim if (!BN_sub_word(pm1, 1)) 168280304Sjkim goto err; 169280304Sjkim if (!BN_gcd(t, pm1, e, ctx)) 170280304Sjkim goto err; 171280304Sjkim if (BN_is_one(t) 172280304Sjkim /* 173280304Sjkim * X9.31 specifies 8 MR and 1 Lucas test or any prime test 174280304Sjkim * offering similar or better guarantees 50 MR is considerably 175280304Sjkim * better. 176280304Sjkim */ 177280304Sjkim && BN_is_prime_fasttest_ex(p, 50, ctx, 1, cb)) 178280304Sjkim break; 179280304Sjkim if (!BN_add(p, p, p1p2)) 180280304Sjkim goto err; 181280304Sjkim } 182193645Ssimon 183280304Sjkim BN_GENCB_call(cb, 3, 0); 184193645Ssimon 185280304Sjkim ret = 1; 186193645Ssimon 187280304Sjkim err: 188193645Ssimon 189280304Sjkim BN_CTX_end(ctx); 190193645Ssimon 191280304Sjkim return ret; 192280304Sjkim} 193193645Ssimon 194280304Sjkim/* 195280304Sjkim * Generate pair of paramters Xp, Xq for X9.31 prime generation. Note: nbits 196280304Sjkim * 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) 200280304Sjkim{ 201280304Sjkim BIGNUM *t; 202280304Sjkim int i; 203280304Sjkim /* 204280304Sjkim * Number of bits for each prime is of the form 512+128s for s = 0, 1, 205280304Sjkim * ... 206280304Sjkim */ 207280304Sjkim if ((nbits < 1024) || (nbits & 0xff)) 208280304Sjkim return 0; 209280304Sjkim nbits >>= 1; 210280304Sjkim /* 211280304Sjkim * The random value Xp must be between sqrt(2) * 2^(nbits-1) and 2^nbits 212280304Sjkim * - 1. By setting the top two bits we ensure that the lower bound is 213280304Sjkim * exceeded. 214280304Sjkim */ 215280304Sjkim if (!BN_rand(Xp, nbits, 1, 0)) 216291721Sjkim goto err; 217193645Ssimon 218280304Sjkim BN_CTX_start(ctx); 219280304Sjkim t = BN_CTX_get(ctx); 220193645Ssimon 221280304Sjkim for (i = 0; i < 1000; i++) { 222280304Sjkim if (!BN_rand(Xq, nbits, 1, 0)) 223291721Sjkim goto err; 224280304Sjkim /* Check that |Xp - Xq| > 2^(nbits - 100) */ 225280304Sjkim BN_sub(t, Xp, Xq); 226280304Sjkim if (BN_num_bits(t) > (nbits - 100)) 227280304Sjkim break; 228280304Sjkim } 229193645Ssimon 230280304Sjkim BN_CTX_end(ctx); 231193645Ssimon 232280304Sjkim if (i < 1000) 233280304Sjkim return 1; 234193645Ssimon 235280304Sjkim return 0; 236193645Ssimon 237291721Sjkim err: 238291721Sjkim BN_CTX_end(ctx); 239291721Sjkim return 0; 240280304Sjkim} 241193645Ssimon 242280304Sjkim/* 243280304Sjkim * Generate primes using X9.31 algorithm. Of the values p, p1, p2, Xp1 and 244280304Sjkim * Xp2 only 'p' needs to be non-NULL. If any of the others are not NULL the 245280304Sjkim * relevant parameter will be stored in it. Due to the fact that |Xp - Xq| > 246280304Sjkim * 2^(nbits - 100) must be satisfied Xp and Xq are generated using the 247280304Sjkim * previous function and supplied as input. 248193645Ssimon */ 249193645Ssimon 250193645Ssimonint BN_X931_generate_prime_ex(BIGNUM *p, BIGNUM *p1, BIGNUM *p2, 251280304Sjkim BIGNUM *Xp1, BIGNUM *Xp2, 252280304Sjkim const BIGNUM *Xp, 253280304Sjkim const BIGNUM *e, BN_CTX *ctx, BN_GENCB *cb) 254280304Sjkim{ 255280304Sjkim int ret = 0; 256193645Ssimon 257280304Sjkim BN_CTX_start(ctx); 258280304Sjkim if (!Xp1) 259280304Sjkim Xp1 = BN_CTX_get(ctx); 260280304Sjkim if (!Xp2) 261280304Sjkim Xp2 = BN_CTX_get(ctx); 262193645Ssimon 263280304Sjkim if (!BN_rand(Xp1, 101, 0, 0)) 264280304Sjkim goto error; 265280304Sjkim if (!BN_rand(Xp2, 101, 0, 0)) 266280304Sjkim goto error; 267280304Sjkim if (!BN_X931_derive_prime_ex(p, p1, p2, Xp, Xp1, Xp2, e, ctx, cb)) 268280304Sjkim goto error; 269193645Ssimon 270280304Sjkim ret = 1; 271193645Ssimon 272280304Sjkim error: 273280304Sjkim BN_CTX_end(ctx); 274193645Ssimon 275280304Sjkim return ret; 276193645Ssimon 277280304Sjkim} 278