155714Skris/* crypto/bn/bn_gcd.c */ 255714Skris/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 355714Skris * All rights reserved. 455714Skris * 555714Skris * This package is an SSL implementation written 655714Skris * by Eric Young (eay@cryptsoft.com). 755714Skris * The implementation was written so as to conform with Netscapes SSL. 8280297Sjkim * 955714Skris * This library is free for commercial and non-commercial use as long as 1055714Skris * the following conditions are aheared to. The following conditions 1155714Skris * apply to all code found in this distribution, be it the RC4, RSA, 1255714Skris * lhash, DES, etc., code; not just the SSL code. The SSL documentation 1355714Skris * included with this distribution is covered by the same copyright terms 1455714Skris * except that the holder is Tim Hudson (tjh@cryptsoft.com). 15280297Sjkim * 1655714Skris * Copyright remains Eric Young's, and as such any Copyright notices in 1755714Skris * the code are not to be removed. 1855714Skris * If this package is used in a product, Eric Young should be given attribution 1955714Skris * as the author of the parts of the library used. 2055714Skris * This can be in the form of a textual message at program startup or 2155714Skris * in documentation (online or textual) provided with the package. 22280297Sjkim * 2355714Skris * Redistribution and use in source and binary forms, with or without 2455714Skris * modification, are permitted provided that the following conditions 2555714Skris * are met: 2655714Skris * 1. Redistributions of source code must retain the copyright 2755714Skris * notice, this list of conditions and the following disclaimer. 2855714Skris * 2. Redistributions in binary form must reproduce the above copyright 2955714Skris * notice, this list of conditions and the following disclaimer in the 3055714Skris * documentation and/or other materials provided with the distribution. 3155714Skris * 3. All advertising materials mentioning features or use of this software 3255714Skris * must display the following acknowledgement: 3355714Skris * "This product includes cryptographic software written by 3455714Skris * Eric Young (eay@cryptsoft.com)" 3555714Skris * The word 'cryptographic' can be left out if the rouines from the library 3655714Skris * being used are not cryptographic related :-). 37280297Sjkim * 4. If you include any Windows specific code (or a derivative thereof) from 3855714Skris * the apps directory (application code) you must include an acknowledgement: 3955714Skris * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 40280297Sjkim * 4155714Skris * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 4255714Skris * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 4355714Skris * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 4455714Skris * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 4555714Skris * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 4655714Skris * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 4755714Skris * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 4855714Skris * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 4955714Skris * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 5055714Skris * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 5155714Skris * SUCH DAMAGE. 52280297Sjkim * 5355714Skris * The licence and distribution terms for any publically available version or 5455714Skris * derivative of this code cannot be changed. i.e. this code cannot simply be 5555714Skris * copied and put under another distribution licence 5655714Skris * [including the GNU Public Licence.] 5755714Skris */ 58109998Smarkm/* ==================================================================== 59109998Smarkm * Copyright (c) 1998-2001 The OpenSSL Project. All rights reserved. 60109998Smarkm * 61109998Smarkm * Redistribution and use in source and binary forms, with or without 62109998Smarkm * modification, are permitted provided that the following conditions 63109998Smarkm * are met: 64109998Smarkm * 65109998Smarkm * 1. Redistributions of source code must retain the above copyright 66280297Sjkim * notice, this list of conditions and the following disclaimer. 67109998Smarkm * 68109998Smarkm * 2. Redistributions in binary form must reproduce the above copyright 69109998Smarkm * notice, this list of conditions and the following disclaimer in 70109998Smarkm * the documentation and/or other materials provided with the 71109998Smarkm * distribution. 72109998Smarkm * 73109998Smarkm * 3. All advertising materials mentioning features or use of this 74109998Smarkm * software must display the following acknowledgment: 75109998Smarkm * "This product includes software developed by the OpenSSL Project 76109998Smarkm * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 77109998Smarkm * 78109998Smarkm * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 79109998Smarkm * endorse or promote products derived from this software without 80109998Smarkm * prior written permission. For written permission, please contact 81109998Smarkm * openssl-core@openssl.org. 82109998Smarkm * 83109998Smarkm * 5. Products derived from this software may not be called "OpenSSL" 84109998Smarkm * nor may "OpenSSL" appear in their names without prior written 85109998Smarkm * permission of the OpenSSL Project. 86109998Smarkm * 87109998Smarkm * 6. Redistributions of any form whatsoever must retain the following 88109998Smarkm * acknowledgment: 89109998Smarkm * "This product includes software developed by the OpenSSL Project 90109998Smarkm * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 91109998Smarkm * 92109998Smarkm * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 93109998Smarkm * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 94109998Smarkm * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 95109998Smarkm * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 96109998Smarkm * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 97109998Smarkm * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 98109998Smarkm * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 99109998Smarkm * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 100109998Smarkm * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 101109998Smarkm * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 102109998Smarkm * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 103109998Smarkm * OF THE POSSIBILITY OF SUCH DAMAGE. 104109998Smarkm * ==================================================================== 105109998Smarkm * 106109998Smarkm * This product includes cryptographic software written by Eric Young 107109998Smarkm * (eay@cryptsoft.com). This product includes software written by Tim 108109998Smarkm * Hudson (tjh@cryptsoft.com). 109109998Smarkm * 110109998Smarkm */ 11155714Skris 11255714Skris#include "cryptlib.h" 11355714Skris#include "bn_lcl.h" 11455714Skris 11555714Skrisstatic BIGNUM *euclid(BIGNUM *a, BIGNUM *b); 11659191Skris 117109998Smarkmint BN_gcd(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx) 118280297Sjkim{ 119280297Sjkim BIGNUM *a, *b, *t; 120280297Sjkim int ret = 0; 12155714Skris 122280297Sjkim bn_check_top(in_a); 123280297Sjkim bn_check_top(in_b); 12455714Skris 125280297Sjkim BN_CTX_start(ctx); 126280297Sjkim a = BN_CTX_get(ctx); 127280297Sjkim b = BN_CTX_get(ctx); 128280297Sjkim if (a == NULL || b == NULL) 129280297Sjkim goto err; 13055714Skris 131280297Sjkim if (BN_copy(a, in_a) == NULL) 132280297Sjkim goto err; 133280297Sjkim if (BN_copy(b, in_b) == NULL) 134280297Sjkim goto err; 135280297Sjkim a->neg = 0; 136280297Sjkim b->neg = 0; 13755714Skris 138280297Sjkim if (BN_cmp(a, b) < 0) { 139280297Sjkim t = a; 140280297Sjkim a = b; 141280297Sjkim b = t; 142280297Sjkim } 143280297Sjkim t = euclid(a, b); 144280297Sjkim if (t == NULL) 145280297Sjkim goto err; 14655714Skris 147280297Sjkim if (BN_copy(r, t) == NULL) 148280297Sjkim goto err; 149280297Sjkim ret = 1; 150280297Sjkim err: 151280297Sjkim BN_CTX_end(ctx); 152280297Sjkim bn_check_top(r); 153280297Sjkim return (ret); 154280297Sjkim} 15555714Skris 15655714Skrisstatic BIGNUM *euclid(BIGNUM *a, BIGNUM *b) 157280297Sjkim{ 158280297Sjkim BIGNUM *t; 159280297Sjkim int shifts = 0; 16055714Skris 161280297Sjkim bn_check_top(a); 162280297Sjkim bn_check_top(b); 16355714Skris 164280297Sjkim /* 0 <= b <= a */ 165280297Sjkim while (!BN_is_zero(b)) { 166280297Sjkim /* 0 < b <= a */ 16755714Skris 168280297Sjkim if (BN_is_odd(a)) { 169280297Sjkim if (BN_is_odd(b)) { 170280297Sjkim if (!BN_sub(a, a, b)) 171280297Sjkim goto err; 172280297Sjkim if (!BN_rshift1(a, a)) 173280297Sjkim goto err; 174280297Sjkim if (BN_cmp(a, b) < 0) { 175280297Sjkim t = a; 176280297Sjkim a = b; 177280297Sjkim b = t; 178280297Sjkim } 179280297Sjkim } else { /* a odd - b even */ 180109998Smarkm 181280297Sjkim if (!BN_rshift1(b, b)) 182280297Sjkim goto err; 183280297Sjkim if (BN_cmp(a, b) < 0) { 184280297Sjkim t = a; 185280297Sjkim a = b; 186280297Sjkim b = t; 187280297Sjkim } 188280297Sjkim } 189280297Sjkim } else { /* a is even */ 19055714Skris 191280297Sjkim if (BN_is_odd(b)) { 192280297Sjkim if (!BN_rshift1(a, a)) 193280297Sjkim goto err; 194280297Sjkim if (BN_cmp(a, b) < 0) { 195280297Sjkim t = a; 196280297Sjkim a = b; 197280297Sjkim b = t; 198280297Sjkim } 199280297Sjkim } else { /* a even - b even */ 200109998Smarkm 201280297Sjkim if (!BN_rshift1(a, a)) 202280297Sjkim goto err; 203280297Sjkim if (!BN_rshift1(b, b)) 204280297Sjkim goto err; 205280297Sjkim shifts++; 206280297Sjkim } 207280297Sjkim } 208280297Sjkim /* 0 <= b <= a */ 209280297Sjkim } 210280297Sjkim 211280297Sjkim if (shifts) { 212280297Sjkim if (!BN_lshift(a, a, shifts)) 213280297Sjkim goto err; 214280297Sjkim } 215280297Sjkim bn_check_top(a); 216280297Sjkim return (a); 217280297Sjkim err: 218280297Sjkim return (NULL); 219280297Sjkim} 220280297Sjkim 22155714Skris/* solves ax == 1 (mod n) */ 222194206Ssimonstatic BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in, 223280297Sjkim const BIGNUM *a, const BIGNUM *n, 224280297Sjkim BN_CTX *ctx); 225246772Sjkim 226109998SmarkmBIGNUM *BN_mod_inverse(BIGNUM *in, 227280297Sjkim const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx) 228280297Sjkim{ 229280297Sjkim BIGNUM *A, *B, *X, *Y, *M, *D, *T, *R = NULL; 230280297Sjkim BIGNUM *ret = NULL; 231280297Sjkim int sign; 23255714Skris 233280297Sjkim if ((BN_get_flags(a, BN_FLG_CONSTTIME) != 0) 234280297Sjkim || (BN_get_flags(n, BN_FLG_CONSTTIME) != 0)) { 235280297Sjkim return BN_mod_inverse_no_branch(in, a, n, ctx); 236280297Sjkim } 237194206Ssimon 238280297Sjkim bn_check_top(a); 239280297Sjkim bn_check_top(n); 24055714Skris 241280297Sjkim BN_CTX_start(ctx); 242280297Sjkim A = BN_CTX_get(ctx); 243280297Sjkim B = BN_CTX_get(ctx); 244280297Sjkim X = BN_CTX_get(ctx); 245280297Sjkim D = BN_CTX_get(ctx); 246280297Sjkim M = BN_CTX_get(ctx); 247280297Sjkim Y = BN_CTX_get(ctx); 248280297Sjkim T = BN_CTX_get(ctx); 249280297Sjkim if (T == NULL) 250280297Sjkim goto err; 25159191Skris 252280297Sjkim if (in == NULL) 253280297Sjkim R = BN_new(); 254280297Sjkim else 255280297Sjkim R = in; 256280297Sjkim if (R == NULL) 257280297Sjkim goto err; 25855714Skris 259280297Sjkim BN_one(X); 260280297Sjkim BN_zero(Y); 261280297Sjkim if (BN_copy(B, a) == NULL) 262280297Sjkim goto err; 263280297Sjkim if (BN_copy(A, n) == NULL) 264280297Sjkim goto err; 265280297Sjkim A->neg = 0; 266280297Sjkim if (B->neg || (BN_ucmp(B, A) >= 0)) { 267280297Sjkim if (!BN_nnmod(B, B, A, ctx)) 268280297Sjkim goto err; 269280297Sjkim } 270280297Sjkim sign = -1; 271280297Sjkim /*- 272280297Sjkim * From B = a mod |n|, A = |n| it follows that 273280297Sjkim * 274280297Sjkim * 0 <= B < A, 275280297Sjkim * -sign*X*a == B (mod |n|), 276280297Sjkim * sign*Y*a == A (mod |n|). 277280297Sjkim */ 27855714Skris 279280297Sjkim if (BN_is_odd(n) && (BN_num_bits(n) <= (BN_BITS <= 32 ? 450 : 2048))) { 280280297Sjkim /* 281280297Sjkim * Binary inversion algorithm; requires odd modulus. This is faster 282280297Sjkim * than the general algorithm if the modulus is sufficiently small 283280297Sjkim * (about 400 .. 500 bits on 32-bit sytems, but much more on 64-bit 284280297Sjkim * systems) 285280297Sjkim */ 286280297Sjkim int shift; 28755714Skris 288280297Sjkim while (!BN_is_zero(B)) { 289280297Sjkim /*- 290280297Sjkim * 0 < B < |n|, 291280297Sjkim * 0 < A <= |n|, 292280297Sjkim * (1) -sign*X*a == B (mod |n|), 293280297Sjkim * (2) sign*Y*a == A (mod |n|) 294280297Sjkim */ 295109998Smarkm 296280297Sjkim /* 297280297Sjkim * Now divide B by the maximum possible power of two in the 298280297Sjkim * integers, and divide X by the same value mod |n|. When we're 299280297Sjkim * done, (1) still holds. 300280297Sjkim */ 301280297Sjkim shift = 0; 302280297Sjkim while (!BN_is_bit_set(B, shift)) { /* note that 0 < B */ 303280297Sjkim shift++; 304109998Smarkm 305280297Sjkim if (BN_is_odd(X)) { 306280297Sjkim if (!BN_uadd(X, X, n)) 307280297Sjkim goto err; 308280297Sjkim } 309280297Sjkim /* 310280297Sjkim * now X is even, so we can easily divide it by two 311280297Sjkim */ 312280297Sjkim if (!BN_rshift1(X, X)) 313280297Sjkim goto err; 314280297Sjkim } 315280297Sjkim if (shift > 0) { 316280297Sjkim if (!BN_rshift(B, B, shift)) 317280297Sjkim goto err; 318280297Sjkim } 319109998Smarkm 320280297Sjkim /* 321280297Sjkim * Same for A and Y. Afterwards, (2) still holds. 322280297Sjkim */ 323280297Sjkim shift = 0; 324280297Sjkim while (!BN_is_bit_set(A, shift)) { /* note that 0 < A */ 325280297Sjkim shift++; 326109998Smarkm 327280297Sjkim if (BN_is_odd(Y)) { 328280297Sjkim if (!BN_uadd(Y, Y, n)) 329280297Sjkim goto err; 330280297Sjkim } 331280297Sjkim /* now Y is even */ 332280297Sjkim if (!BN_rshift1(Y, Y)) 333280297Sjkim goto err; 334280297Sjkim } 335280297Sjkim if (shift > 0) { 336280297Sjkim if (!BN_rshift(A, A, shift)) 337280297Sjkim goto err; 338280297Sjkim } 339109998Smarkm 340280297Sjkim /*- 341280297Sjkim * We still have (1) and (2). 342280297Sjkim * Both A and B are odd. 343280297Sjkim * The following computations ensure that 344280297Sjkim * 345280297Sjkim * 0 <= B < |n|, 346280297Sjkim * 0 < A < |n|, 347280297Sjkim * (1) -sign*X*a == B (mod |n|), 348280297Sjkim * (2) sign*Y*a == A (mod |n|), 349280297Sjkim * 350280297Sjkim * and that either A or B is even in the next iteration. 351280297Sjkim */ 352280297Sjkim if (BN_ucmp(B, A) >= 0) { 353280297Sjkim /* -sign*(X + Y)*a == B - A (mod |n|) */ 354280297Sjkim if (!BN_uadd(X, X, Y)) 355280297Sjkim goto err; 356280297Sjkim /* 357280297Sjkim * NB: we could use BN_mod_add_quick(X, X, Y, n), but that 358280297Sjkim * actually makes the algorithm slower 359280297Sjkim */ 360280297Sjkim if (!BN_usub(B, B, A)) 361280297Sjkim goto err; 362280297Sjkim } else { 363280297Sjkim /* sign*(X + Y)*a == A - B (mod |n|) */ 364280297Sjkim if (!BN_uadd(Y, Y, X)) 365280297Sjkim goto err; 366280297Sjkim /* 367280297Sjkim * as above, BN_mod_add_quick(Y, Y, X, n) would slow things 368280297Sjkim * down 369280297Sjkim */ 370280297Sjkim if (!BN_usub(A, A, B)) 371280297Sjkim goto err; 372280297Sjkim } 373280297Sjkim } 374280297Sjkim } else { 375280297Sjkim /* general inversion algorithm */ 37655714Skris 377280297Sjkim while (!BN_is_zero(B)) { 378280297Sjkim BIGNUM *tmp; 379194206Ssimon 380280297Sjkim /*- 381280297Sjkim * 0 < B < A, 382280297Sjkim * (*) -sign*X*a == B (mod |n|), 383280297Sjkim * sign*Y*a == A (mod |n|) 384280297Sjkim */ 385194206Ssimon 386280297Sjkim /* (D, M) := (A/B, A%B) ... */ 387280297Sjkim if (BN_num_bits(A) == BN_num_bits(B)) { 388280297Sjkim if (!BN_one(D)) 389280297Sjkim goto err; 390280297Sjkim if (!BN_sub(M, A, B)) 391280297Sjkim goto err; 392280297Sjkim } else if (BN_num_bits(A) == BN_num_bits(B) + 1) { 393280297Sjkim /* A/B is 1, 2, or 3 */ 394280297Sjkim if (!BN_lshift1(T, B)) 395280297Sjkim goto err; 396280297Sjkim if (BN_ucmp(A, T) < 0) { 397280297Sjkim /* A < 2*B, so D=1 */ 398280297Sjkim if (!BN_one(D)) 399280297Sjkim goto err; 400280297Sjkim if (!BN_sub(M, A, B)) 401280297Sjkim goto err; 402280297Sjkim } else { 403280297Sjkim /* A >= 2*B, so D=2 or D=3 */ 404280297Sjkim if (!BN_sub(M, A, T)) 405280297Sjkim goto err; 406280297Sjkim if (!BN_add(D, T, B)) 407280297Sjkim goto err; /* use D (:= 3*B) as temp */ 408280297Sjkim if (BN_ucmp(A, D) < 0) { 409280297Sjkim /* A < 3*B, so D=2 */ 410280297Sjkim if (!BN_set_word(D, 2)) 411280297Sjkim goto err; 412280297Sjkim /* 413280297Sjkim * M (= A - 2*B) already has the correct value 414280297Sjkim */ 415280297Sjkim } else { 416280297Sjkim /* only D=3 remains */ 417280297Sjkim if (!BN_set_word(D, 3)) 418280297Sjkim goto err; 419280297Sjkim /* 420280297Sjkim * currently M = A - 2*B, but we need M = A - 3*B 421280297Sjkim */ 422280297Sjkim if (!BN_sub(M, M, B)) 423280297Sjkim goto err; 424280297Sjkim } 425280297Sjkim } 426280297Sjkim } else { 427280297Sjkim if (!BN_div(D, M, A, B, ctx)) 428280297Sjkim goto err; 429280297Sjkim } 430280297Sjkim 431280297Sjkim /*- 432280297Sjkim * Now 433280297Sjkim * A = D*B + M; 434280297Sjkim * thus we have 435280297Sjkim * (**) sign*Y*a == D*B + M (mod |n|). 436280297Sjkim */ 437280297Sjkim 438280297Sjkim tmp = A; /* keep the BIGNUM object, the value does not 439280297Sjkim * matter */ 440280297Sjkim 441280297Sjkim /* (A, B) := (B, A mod B) ... */ 442280297Sjkim A = B; 443280297Sjkim B = M; 444280297Sjkim /* ... so we have 0 <= B < A again */ 445280297Sjkim 446280297Sjkim /*- 447280297Sjkim * Since the former M is now B and the former B is now A, 448280297Sjkim * (**) translates into 449280297Sjkim * sign*Y*a == D*A + B (mod |n|), 450280297Sjkim * i.e. 451280297Sjkim * sign*Y*a - D*A == B (mod |n|). 452280297Sjkim * Similarly, (*) translates into 453280297Sjkim * -sign*X*a == A (mod |n|). 454280297Sjkim * 455280297Sjkim * Thus, 456280297Sjkim * sign*Y*a + D*sign*X*a == B (mod |n|), 457280297Sjkim * i.e. 458280297Sjkim * sign*(Y + D*X)*a == B (mod |n|). 459280297Sjkim * 460280297Sjkim * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at 461280297Sjkim * -sign*X*a == B (mod |n|), 462280297Sjkim * sign*Y*a == A (mod |n|). 463280297Sjkim * Note that X and Y stay non-negative all the time. 464280297Sjkim */ 465280297Sjkim 466280297Sjkim /* 467280297Sjkim * most of the time D is very small, so we can optimize tmp := 468280297Sjkim * D*X+Y 469280297Sjkim */ 470280297Sjkim if (BN_is_one(D)) { 471280297Sjkim if (!BN_add(tmp, X, Y)) 472280297Sjkim goto err; 473280297Sjkim } else { 474280297Sjkim if (BN_is_word(D, 2)) { 475280297Sjkim if (!BN_lshift1(tmp, X)) 476280297Sjkim goto err; 477280297Sjkim } else if (BN_is_word(D, 4)) { 478280297Sjkim if (!BN_lshift(tmp, X, 2)) 479280297Sjkim goto err; 480280297Sjkim } else if (D->top == 1) { 481280297Sjkim if (!BN_copy(tmp, X)) 482280297Sjkim goto err; 483280297Sjkim if (!BN_mul_word(tmp, D->d[0])) 484280297Sjkim goto err; 485280297Sjkim } else { 486280297Sjkim if (!BN_mul(tmp, D, X, ctx)) 487280297Sjkim goto err; 488280297Sjkim } 489280297Sjkim if (!BN_add(tmp, tmp, Y)) 490280297Sjkim goto err; 491280297Sjkim } 492280297Sjkim 493280297Sjkim M = Y; /* keep the BIGNUM object, the value does not 494280297Sjkim * matter */ 495280297Sjkim Y = X; 496280297Sjkim X = tmp; 497280297Sjkim sign = -sign; 498280297Sjkim } 499280297Sjkim } 500280297Sjkim 501280297Sjkim /*- 502280297Sjkim * The while loop (Euclid's algorithm) ends when 503280297Sjkim * A == gcd(a,n); 504280297Sjkim * we have 505280297Sjkim * sign*Y*a == A (mod |n|), 506280297Sjkim * where Y is non-negative. 507280297Sjkim */ 508280297Sjkim 509280297Sjkim if (sign < 0) { 510280297Sjkim if (!BN_sub(Y, n, Y)) 511280297Sjkim goto err; 512280297Sjkim } 513280297Sjkim /* Now Y*a == A (mod |n|). */ 514280297Sjkim 515280297Sjkim if (BN_is_one(A)) { 516280297Sjkim /* Y*a == 1 (mod |n|) */ 517280297Sjkim if (!Y->neg && BN_ucmp(Y, n) < 0) { 518280297Sjkim if (!BN_copy(R, Y)) 519280297Sjkim goto err; 520280297Sjkim } else { 521280297Sjkim if (!BN_nnmod(R, Y, n, ctx)) 522280297Sjkim goto err; 523280297Sjkim } 524280297Sjkim } else { 525280297Sjkim BNerr(BN_F_BN_MOD_INVERSE, BN_R_NO_INVERSE); 526280297Sjkim goto err; 527280297Sjkim } 528280297Sjkim ret = R; 529280297Sjkim err: 530280297Sjkim if ((ret == NULL) && (in == NULL)) 531280297Sjkim BN_free(R); 532280297Sjkim BN_CTX_end(ctx); 533280297Sjkim bn_check_top(ret); 534280297Sjkim return (ret); 535280297Sjkim} 536280297Sjkim 537280297Sjkim/* 538280297Sjkim * BN_mod_inverse_no_branch is a special version of BN_mod_inverse. It does 539280297Sjkim * not contain branches that may leak sensitive information. 540194206Ssimon */ 541194206Ssimonstatic BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in, 542280297Sjkim const BIGNUM *a, const BIGNUM *n, 543280297Sjkim BN_CTX *ctx) 544280297Sjkim{ 545280297Sjkim BIGNUM *A, *B, *X, *Y, *M, *D, *T, *R = NULL; 546280297Sjkim BIGNUM local_A, local_B; 547280297Sjkim BIGNUM *pA, *pB; 548280297Sjkim BIGNUM *ret = NULL; 549280297Sjkim int sign; 550194206Ssimon 551280297Sjkim bn_check_top(a); 552280297Sjkim bn_check_top(n); 553194206Ssimon 554280297Sjkim BN_CTX_start(ctx); 555280297Sjkim A = BN_CTX_get(ctx); 556280297Sjkim B = BN_CTX_get(ctx); 557280297Sjkim X = BN_CTX_get(ctx); 558280297Sjkim D = BN_CTX_get(ctx); 559280297Sjkim M = BN_CTX_get(ctx); 560280297Sjkim Y = BN_CTX_get(ctx); 561280297Sjkim T = BN_CTX_get(ctx); 562280297Sjkim if (T == NULL) 563280297Sjkim goto err; 564194206Ssimon 565280297Sjkim if (in == NULL) 566280297Sjkim R = BN_new(); 567280297Sjkim else 568280297Sjkim R = in; 569280297Sjkim if (R == NULL) 570280297Sjkim goto err; 571194206Ssimon 572280297Sjkim BN_one(X); 573280297Sjkim BN_zero(Y); 574280297Sjkim if (BN_copy(B, a) == NULL) 575280297Sjkim goto err; 576280297Sjkim if (BN_copy(A, n) == NULL) 577280297Sjkim goto err; 578280297Sjkim A->neg = 0; 579194206Ssimon 580280297Sjkim if (B->neg || (BN_ucmp(B, A) >= 0)) { 581280297Sjkim /* 582280297Sjkim * Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked, 583280297Sjkim * BN_div_no_branch will be called eventually. 584280297Sjkim */ 585280297Sjkim pB = &local_B; 586291719Sjkim local_B.flags = 0; 587280297Sjkim BN_with_flags(pB, B, BN_FLG_CONSTTIME); 588280297Sjkim if (!BN_nnmod(B, pB, A, ctx)) 589280297Sjkim goto err; 590280297Sjkim } 591280297Sjkim sign = -1; 592280297Sjkim /*- 593280297Sjkim * From B = a mod |n|, A = |n| it follows that 594280297Sjkim * 595280297Sjkim * 0 <= B < A, 596280297Sjkim * -sign*X*a == B (mod |n|), 597280297Sjkim * sign*Y*a == A (mod |n|). 598280297Sjkim */ 599194206Ssimon 600280297Sjkim while (!BN_is_zero(B)) { 601280297Sjkim BIGNUM *tmp; 602194206Ssimon 603280297Sjkim /*- 604280297Sjkim * 0 < B < A, 605280297Sjkim * (*) -sign*X*a == B (mod |n|), 606280297Sjkim * sign*Y*a == A (mod |n|) 607280297Sjkim */ 608194206Ssimon 609280297Sjkim /* 610280297Sjkim * Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked, 611280297Sjkim * BN_div_no_branch will be called eventually. 612280297Sjkim */ 613280297Sjkim pA = &local_A; 614291719Sjkim local_A.flags = 0; 615280297Sjkim BN_with_flags(pA, A, BN_FLG_CONSTTIME); 616194206Ssimon 617280297Sjkim /* (D, M) := (A/B, A%B) ... */ 618280297Sjkim if (!BN_div(D, M, pA, B, ctx)) 619280297Sjkim goto err; 620194206Ssimon 621280297Sjkim /*- 622280297Sjkim * Now 623280297Sjkim * A = D*B + M; 624280297Sjkim * thus we have 625280297Sjkim * (**) sign*Y*a == D*B + M (mod |n|). 626280297Sjkim */ 627280297Sjkim 628280297Sjkim tmp = A; /* keep the BIGNUM object, the value does not 629280297Sjkim * matter */ 630280297Sjkim 631280297Sjkim /* (A, B) := (B, A mod B) ... */ 632280297Sjkim A = B; 633280297Sjkim B = M; 634280297Sjkim /* ... so we have 0 <= B < A again */ 635280297Sjkim 636280297Sjkim /*- 637280297Sjkim * Since the former M is now B and the former B is now A, 638280297Sjkim * (**) translates into 639280297Sjkim * sign*Y*a == D*A + B (mod |n|), 640280297Sjkim * i.e. 641280297Sjkim * sign*Y*a - D*A == B (mod |n|). 642280297Sjkim * Similarly, (*) translates into 643280297Sjkim * -sign*X*a == A (mod |n|). 644280297Sjkim * 645280297Sjkim * Thus, 646280297Sjkim * sign*Y*a + D*sign*X*a == B (mod |n|), 647280297Sjkim * i.e. 648280297Sjkim * sign*(Y + D*X)*a == B (mod |n|). 649280297Sjkim * 650280297Sjkim * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at 651280297Sjkim * -sign*X*a == B (mod |n|), 652280297Sjkim * sign*Y*a == A (mod |n|). 653280297Sjkim * Note that X and Y stay non-negative all the time. 654280297Sjkim */ 655280297Sjkim 656280297Sjkim if (!BN_mul(tmp, D, X, ctx)) 657280297Sjkim goto err; 658280297Sjkim if (!BN_add(tmp, tmp, Y)) 659280297Sjkim goto err; 660280297Sjkim 661280297Sjkim M = Y; /* keep the BIGNUM object, the value does not 662280297Sjkim * matter */ 663280297Sjkim Y = X; 664280297Sjkim X = tmp; 665280297Sjkim sign = -sign; 666280297Sjkim } 667280297Sjkim 668280297Sjkim /*- 669280297Sjkim * The while loop (Euclid's algorithm) ends when 670280297Sjkim * A == gcd(a,n); 671280297Sjkim * we have 672280297Sjkim * sign*Y*a == A (mod |n|), 673280297Sjkim * where Y is non-negative. 674280297Sjkim */ 675280297Sjkim 676280297Sjkim if (sign < 0) { 677280297Sjkim if (!BN_sub(Y, n, Y)) 678280297Sjkim goto err; 679280297Sjkim } 680280297Sjkim /* Now Y*a == A (mod |n|). */ 681280297Sjkim 682280297Sjkim if (BN_is_one(A)) { 683280297Sjkim /* Y*a == 1 (mod |n|) */ 684280297Sjkim if (!Y->neg && BN_ucmp(Y, n) < 0) { 685280297Sjkim if (!BN_copy(R, Y)) 686280297Sjkim goto err; 687280297Sjkim } else { 688280297Sjkim if (!BN_nnmod(R, Y, n, ctx)) 689280297Sjkim goto err; 690280297Sjkim } 691280297Sjkim } else { 692280297Sjkim BNerr(BN_F_BN_MOD_INVERSE_NO_BRANCH, BN_R_NO_INVERSE); 693280297Sjkim goto err; 694280297Sjkim } 695280297Sjkim ret = R; 696280297Sjkim err: 697280297Sjkim if ((ret == NULL) && (in == NULL)) 698280297Sjkim BN_free(R); 699280297Sjkim BN_CTX_end(ctx); 700280297Sjkim bn_check_top(ret); 701280297Sjkim return (ret); 702280297Sjkim} 703