1 /* $OpenBSD: bn_gcd.c,v 1.9 2014/07/11 08:44:47 jsing Exp $ */ 2 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 3 * All rights reserved. 4 * 5 * This package is an SSL implementation written 6 * by Eric Young (eay@cryptsoft.com). 7 * The implementation was written so as to conform with Netscapes SSL. 8 * 9 * This library is free for commercial and non-commercial use as long as 10 * the following conditions are aheared to. The following conditions 11 * apply to all code found in this distribution, be it the RC4, RSA, 12 * lhash, DES, etc., code; not just the SSL code. The SSL documentation 13 * included with this distribution is covered by the same copyright terms 14 * except that the holder is Tim Hudson (tjh@cryptsoft.com). 15 * 16 * Copyright remains Eric Young's, and as such any Copyright notices in 17 * the code are not to be removed. 18 * If this package is used in a product, Eric Young should be given attribution 19 * as the author of the parts of the library used. 20 * This can be in the form of a textual message at program startup or 21 * in documentation (online or textual) provided with the package. 22 * 23 * Redistribution and use in source and binary forms, with or without 24 * modification, are permitted provided that the following conditions 25 * are met: 26 * 1. Redistributions of source code must retain the copyright 27 * notice, this list of conditions and the following disclaimer. 28 * 2. Redistributions in binary form must reproduce the above copyright 29 * notice, this list of conditions and the following disclaimer in the 30 * documentation and/or other materials provided with the distribution. 31 * 3. All advertising materials mentioning features or use of this software 32 * must display the following acknowledgement: 33 * "This product includes cryptographic software written by 34 * Eric Young (eay@cryptsoft.com)" 35 * The word 'cryptographic' can be left out if the rouines from the library 36 * being used are not cryptographic related :-). 37 * 4. If you include any Windows specific code (or a derivative thereof) from 38 * the apps directory (application code) you must include an acknowledgement: 39 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 40 * 41 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 42 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 43 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 44 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 45 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 46 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 47 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 48 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 49 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 50 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 51 * SUCH DAMAGE. 52 * 53 * The licence and distribution terms for any publically available version or 54 * derivative of this code cannot be changed. i.e. this code cannot simply be 55 * copied and put under another distribution licence 56 * [including the GNU Public Licence.] 57 */ 58 /* ==================================================================== 59 * Copyright (c) 1998-2001 The OpenSSL Project. All rights reserved. 60 * 61 * Redistribution and use in source and binary forms, with or without 62 * modification, are permitted provided that the following conditions 63 * are met: 64 * 65 * 1. Redistributions of source code must retain the above copyright 66 * notice, this list of conditions and the following disclaimer. 67 * 68 * 2. Redistributions in binary form must reproduce the above copyright 69 * notice, this list of conditions and the following disclaimer in 70 * the documentation and/or other materials provided with the 71 * distribution. 72 * 73 * 3. All advertising materials mentioning features or use of this 74 * software must display the following acknowledgment: 75 * "This product includes software developed by the OpenSSL Project 76 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 77 * 78 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 79 * endorse or promote products derived from this software without 80 * prior written permission. For written permission, please contact 81 * openssl-core@openssl.org. 82 * 83 * 5. Products derived from this software may not be called "OpenSSL" 84 * nor may "OpenSSL" appear in their names without prior written 85 * permission of the OpenSSL Project. 86 * 87 * 6. Redistributions of any form whatsoever must retain the following 88 * acknowledgment: 89 * "This product includes software developed by the OpenSSL Project 90 * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 91 * 92 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 93 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 94 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 95 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 96 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 97 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 98 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 99 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 100 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 101 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 102 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 103 * OF THE POSSIBILITY OF SUCH DAMAGE. 104 * ==================================================================== 105 * 106 * This product includes cryptographic software written by Eric Young 107 * (eay@cryptsoft.com). This product includes software written by Tim 108 * Hudson (tjh@cryptsoft.com). 109 * 110 */ 111 112 #include <openssl/err.h> 113 114 #include "bn_lcl.h" 115 116 static BIGNUM *euclid(BIGNUM *a, BIGNUM *b); 117 118 int 119 BN_gcd(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx) 120 { 121 BIGNUM *a, *b, *t; 122 int ret = 0; 123 124 bn_check_top(in_a); 125 bn_check_top(in_b); 126 127 BN_CTX_start(ctx); 128 if ((a = BN_CTX_get(ctx)) == NULL) 129 goto err; 130 if ((b = BN_CTX_get(ctx)) == NULL) 131 goto err; 132 133 if (BN_copy(a, in_a) == NULL) 134 goto err; 135 if (BN_copy(b, in_b) == NULL) 136 goto err; 137 a->neg = 0; 138 b->neg = 0; 139 140 if (BN_cmp(a, b) < 0) { 141 t = a; 142 a = b; 143 b = t; 144 } 145 t = euclid(a, b); 146 if (t == NULL) 147 goto err; 148 149 if (BN_copy(r, t) == NULL) 150 goto err; 151 ret = 1; 152 153 err: 154 BN_CTX_end(ctx); 155 bn_check_top(r); 156 return (ret); 157 } 158 159 static BIGNUM * 160 euclid(BIGNUM *a, BIGNUM *b) 161 { 162 BIGNUM *t; 163 int shifts = 0; 164 165 bn_check_top(a); 166 bn_check_top(b); 167 168 /* 0 <= b <= a */ 169 while (!BN_is_zero(b)) { 170 /* 0 < b <= a */ 171 172 if (BN_is_odd(a)) { 173 if (BN_is_odd(b)) { 174 if (!BN_sub(a, a, b)) 175 goto err; 176 if (!BN_rshift1(a, a)) 177 goto err; 178 if (BN_cmp(a, b) < 0) { 179 t = a; 180 a = b; 181 b = t; 182 } 183 } 184 else /* a odd - b even */ 185 { 186 if (!BN_rshift1(b, b)) 187 goto err; 188 if (BN_cmp(a, b) < 0) { 189 t = a; 190 a = b; 191 b = t; 192 } 193 } 194 } 195 else /* a is even */ 196 { 197 if (BN_is_odd(b)) { 198 if (!BN_rshift1(a, a)) 199 goto err; 200 if (BN_cmp(a, b) < 0) { 201 t = a; 202 a = b; 203 b = t; 204 } 205 } 206 else /* a even - b even */ 207 { 208 if (!BN_rshift1(a, a)) 209 goto err; 210 if (!BN_rshift1(b, b)) 211 goto err; 212 shifts++; 213 } 214 } 215 /* 0 <= b <= a */ 216 } 217 218 if (shifts) { 219 if (!BN_lshift(a, a, shifts)) 220 goto err; 221 } 222 bn_check_top(a); 223 return (a); 224 225 err: 226 return (NULL); 227 } 228 229 230 /* solves ax == 1 (mod n) */ 231 static BIGNUM *BN_mod_inverse_no_branch(BIGNUM *in, const BIGNUM *a, 232 const BIGNUM *n, BN_CTX *ctx); 233 234 BIGNUM * 235 BN_mod_inverse(BIGNUM *in, const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx) 236 { 237 BIGNUM *A, *B, *X, *Y, *M, *D, *T, *R = NULL; 238 BIGNUM *ret = NULL; 239 int sign; 240 241 if ((BN_get_flags(a, BN_FLG_CONSTTIME) != 0) || 242 (BN_get_flags(n, BN_FLG_CONSTTIME) != 0)) { 243 return BN_mod_inverse_no_branch(in, a, n, ctx); 244 } 245 246 bn_check_top(a); 247 bn_check_top(n); 248 249 BN_CTX_start(ctx); 250 if ((A = BN_CTX_get(ctx)) == NULL) 251 goto err; 252 if ((B = BN_CTX_get(ctx)) == NULL) 253 goto err; 254 if ((X = BN_CTX_get(ctx)) == NULL) 255 goto err; 256 if ((D = BN_CTX_get(ctx)) == NULL) 257 goto err; 258 if ((M = BN_CTX_get(ctx)) == NULL) 259 goto err; 260 if ((Y = BN_CTX_get(ctx)) == NULL) 261 goto err; 262 if ((T = BN_CTX_get(ctx)) == NULL) 263 goto err; 264 265 if (in == NULL) 266 R = BN_new(); 267 else 268 R = in; 269 if (R == NULL) 270 goto err; 271 272 BN_one(X); 273 BN_zero(Y); 274 if (BN_copy(B, a) == NULL) 275 goto err; 276 if (BN_copy(A, n) == NULL) 277 goto err; 278 A->neg = 0; 279 if (B->neg || (BN_ucmp(B, A) >= 0)) { 280 if (!BN_nnmod(B, B, A, ctx)) 281 goto err; 282 } 283 sign = -1; 284 /* From B = a mod |n|, A = |n| it follows that 285 * 286 * 0 <= B < A, 287 * -sign*X*a == B (mod |n|), 288 * sign*Y*a == A (mod |n|). 289 */ 290 291 if (BN_is_odd(n) && (BN_num_bits(n) <= (BN_BITS <= 32 ? 450 : 2048))) { 292 /* Binary inversion algorithm; requires odd modulus. 293 * This is faster than the general algorithm if the modulus 294 * is sufficiently small (about 400 .. 500 bits on 32-bit 295 * sytems, but much more on 64-bit systems) */ 296 int shift; 297 298 while (!BN_is_zero(B)) { 299 /* 300 * 0 < B < |n|, 301 * 0 < A <= |n|, 302 * (1) -sign*X*a == B (mod |n|), 303 * (2) sign*Y*a == A (mod |n|) 304 */ 305 306 /* Now divide B by the maximum possible power of two in the integers, 307 * and divide X by the same value mod |n|. 308 * When we're done, (1) still holds. */ 309 shift = 0; 310 while (!BN_is_bit_set(B, shift)) /* note that 0 < B */ 311 { 312 shift++; 313 314 if (BN_is_odd(X)) { 315 if (!BN_uadd(X, X, n)) 316 goto err; 317 } 318 /* now X is even, so we can easily divide it by two */ 319 if (!BN_rshift1(X, X)) 320 goto err; 321 } 322 if (shift > 0) { 323 if (!BN_rshift(B, B, shift)) 324 goto err; 325 } 326 327 328 /* Same for A and Y. Afterwards, (2) still holds. */ 329 shift = 0; 330 while (!BN_is_bit_set(A, shift)) /* note that 0 < A */ 331 { 332 shift++; 333 334 if (BN_is_odd(Y)) { 335 if (!BN_uadd(Y, Y, n)) 336 goto err; 337 } 338 /* now Y is even */ 339 if (!BN_rshift1(Y, Y)) 340 goto err; 341 } 342 if (shift > 0) { 343 if (!BN_rshift(A, A, shift)) 344 goto err; 345 } 346 347 348 /* We still have (1) and (2). 349 * Both A and B are odd. 350 * The following computations ensure that 351 * 352 * 0 <= B < |n|, 353 * 0 < A < |n|, 354 * (1) -sign*X*a == B (mod |n|), 355 * (2) sign*Y*a == A (mod |n|), 356 * 357 * and that either A or B is even in the next iteration. 358 */ 359 if (BN_ucmp(B, A) >= 0) { 360 /* -sign*(X + Y)*a == B - A (mod |n|) */ 361 if (!BN_uadd(X, X, Y)) 362 goto err; 363 /* NB: we could use BN_mod_add_quick(X, X, Y, n), but that 364 * actually makes the algorithm slower */ 365 if (!BN_usub(B, B, A)) 366 goto err; 367 } else { 368 /* sign*(X + Y)*a == A - B (mod |n|) */ 369 if (!BN_uadd(Y, Y, X)) 370 goto err; 371 /* as above, BN_mod_add_quick(Y, Y, X, n) would slow things down */ 372 if (!BN_usub(A, A, B)) 373 goto err; 374 } 375 } 376 } else { 377 /* general inversion algorithm */ 378 379 while (!BN_is_zero(B)) { 380 BIGNUM *tmp; 381 382 /* 383 * 0 < B < A, 384 * (*) -sign*X*a == B (mod |n|), 385 * sign*Y*a == A (mod |n|) 386 */ 387 388 /* (D, M) := (A/B, A%B) ... */ 389 if (BN_num_bits(A) == BN_num_bits(B)) { 390 if (!BN_one(D)) 391 goto err; 392 if (!BN_sub(M, A, B)) 393 goto err; 394 } else if (BN_num_bits(A) == BN_num_bits(B) + 1) { 395 /* A/B is 1, 2, or 3 */ 396 if (!BN_lshift1(T, B)) 397 goto err; 398 if (BN_ucmp(A, T) < 0) { 399 /* A < 2*B, so D=1 */ 400 if (!BN_one(D)) 401 goto err; 402 if (!BN_sub(M, A, B)) 403 goto err; 404 } else { 405 /* A >= 2*B, so D=2 or D=3 */ 406 if (!BN_sub(M, A, T)) 407 goto err; 408 if (!BN_add(D,T,B)) goto err; /* use D (:= 3*B) as temp */ 409 if (BN_ucmp(A, D) < 0) { 410 /* A < 3*B, so D=2 */ 411 if (!BN_set_word(D, 2)) 412 goto err; 413 /* M (= A - 2*B) already has the correct value */ 414 } else { 415 /* only D=3 remains */ 416 if (!BN_set_word(D, 3)) 417 goto err; 418 /* currently M = A - 2*B, but we need M = A - 3*B */ 419 if (!BN_sub(M, M, B)) 420 goto err; 421 } 422 } 423 } else { 424 if (!BN_div(D, M, A, B, ctx)) 425 goto err; 426 } 427 428 /* Now 429 * A = D*B + M; 430 * thus we have 431 * (**) sign*Y*a == D*B + M (mod |n|). 432 */ 433 tmp = A; /* keep the BIGNUM object, the value does not matter */ 434 435 /* (A, B) := (B, A mod B) ... */ 436 A = B; 437 B = M; 438 /* ... so we have 0 <= B < A again */ 439 440 /* Since the former M is now B and the former B is now A, 441 * (**) translates into 442 * sign*Y*a == D*A + B (mod |n|), 443 * i.e. 444 * sign*Y*a - D*A == B (mod |n|). 445 * Similarly, (*) translates into 446 * -sign*X*a == A (mod |n|). 447 * 448 * Thus, 449 * sign*Y*a + D*sign*X*a == B (mod |n|), 450 * i.e. 451 * sign*(Y + D*X)*a == B (mod |n|). 452 * 453 * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at 454 * -sign*X*a == B (mod |n|), 455 * sign*Y*a == A (mod |n|). 456 * Note that X and Y stay non-negative all the time. 457 */ 458 459 /* most of the time D is very small, so we can optimize tmp := D*X+Y */ 460 if (BN_is_one(D)) { 461 if (!BN_add(tmp, X, Y)) 462 goto err; 463 } else { 464 if (BN_is_word(D, 2)) { 465 if (!BN_lshift1(tmp, X)) 466 goto err; 467 } else if (BN_is_word(D, 4)) { 468 if (!BN_lshift(tmp, X, 2)) 469 goto err; 470 } else if (D->top == 1) { 471 if (!BN_copy(tmp, X)) 472 goto err; 473 if (!BN_mul_word(tmp, D->d[0])) 474 goto err; 475 } else { 476 if (!BN_mul(tmp, D,X, ctx)) 477 goto err; 478 } 479 if (!BN_add(tmp, tmp, Y)) 480 goto err; 481 } 482 483 M = Y; /* keep the BIGNUM object, the value does not matter */ 484 Y = X; 485 X = tmp; 486 sign = -sign; 487 } 488 } 489 490 /* 491 * The while loop (Euclid's algorithm) ends when 492 * A == gcd(a,n); 493 * we have 494 * sign*Y*a == A (mod |n|), 495 * where Y is non-negative. 496 */ 497 498 if (sign < 0) { 499 if (!BN_sub(Y, n, Y)) 500 goto err; 501 } 502 /* Now Y*a == A (mod |n|). */ 503 504 if (BN_is_one(A)) { 505 /* Y*a == 1 (mod |n|) */ 506 if (!Y->neg && BN_ucmp(Y, n) < 0) { 507 if (!BN_copy(R, Y)) 508 goto err; 509 } else { 510 if (!BN_nnmod(R, Y,n, ctx)) 511 goto err; 512 } 513 } else { 514 BNerr(BN_F_BN_MOD_INVERSE, BN_R_NO_INVERSE); 515 goto err; 516 } 517 ret = R; 518 519 err: 520 if ((ret == NULL) && (in == NULL)) 521 BN_free(R); 522 BN_CTX_end(ctx); 523 bn_check_top(ret); 524 return (ret); 525 } 526 527 528 /* BN_mod_inverse_no_branch is a special version of BN_mod_inverse. 529 * It does not contain branches that may leak sensitive information. 530 */ 531 static BIGNUM * 532 BN_mod_inverse_no_branch(BIGNUM *in, const BIGNUM *a, const BIGNUM *n, 533 BN_CTX *ctx) 534 { 535 BIGNUM *A, *B, *X, *Y, *M, *D, *T, *R = NULL; 536 BIGNUM local_A, local_B; 537 BIGNUM *pA, *pB; 538 BIGNUM *ret = NULL; 539 int sign; 540 541 bn_check_top(a); 542 bn_check_top(n); 543 544 BN_CTX_start(ctx); 545 if ((A = BN_CTX_get(ctx)) == NULL) 546 goto err; 547 if ((B = BN_CTX_get(ctx)) == NULL) 548 goto err; 549 if ((X = BN_CTX_get(ctx)) == NULL) 550 goto err; 551 if ((D = BN_CTX_get(ctx)) == NULL) 552 goto err; 553 if ((M = BN_CTX_get(ctx)) == NULL) 554 goto err; 555 if ((Y = BN_CTX_get(ctx)) == NULL) 556 goto err; 557 if ((T = BN_CTX_get(ctx)) == NULL) 558 goto err; 559 560 if (in == NULL) 561 R = BN_new(); 562 else 563 R = in; 564 if (R == NULL) 565 goto err; 566 567 BN_one(X); 568 BN_zero(Y); 569 if (BN_copy(B, a) == NULL) 570 goto err; 571 if (BN_copy(A, n) == NULL) 572 goto err; 573 A->neg = 0; 574 575 if (B->neg || (BN_ucmp(B, A) >= 0)) { 576 /* Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked, 577 * BN_div_no_branch will be called eventually. 578 */ 579 pB = &local_B; 580 BN_with_flags(pB, B, BN_FLG_CONSTTIME); 581 if (!BN_nnmod(B, pB, A, ctx)) 582 goto err; 583 } 584 sign = -1; 585 /* From B = a mod |n|, A = |n| it follows that 586 * 587 * 0 <= B < A, 588 * -sign*X*a == B (mod |n|), 589 * sign*Y*a == A (mod |n|). 590 */ 591 592 while (!BN_is_zero(B)) { 593 BIGNUM *tmp; 594 595 /* 596 * 0 < B < A, 597 * (*) -sign*X*a == B (mod |n|), 598 * sign*Y*a == A (mod |n|) 599 */ 600 601 /* Turn BN_FLG_CONSTTIME flag on, so that when BN_div is invoked, 602 * BN_div_no_branch will be called eventually. 603 */ 604 pA = &local_A; 605 BN_with_flags(pA, A, BN_FLG_CONSTTIME); 606 607 /* (D, M) := (A/B, A%B) ... */ 608 if (!BN_div(D, M, pA, B, ctx)) 609 goto err; 610 611 /* Now 612 * A = D*B + M; 613 * thus we have 614 * (**) sign*Y*a == D*B + M (mod |n|). 615 */ 616 tmp = A; /* keep the BIGNUM object, the value does not matter */ 617 618 /* (A, B) := (B, A mod B) ... */ 619 A = B; 620 B = M; 621 /* ... so we have 0 <= B < A again */ 622 623 /* Since the former M is now B and the former B is now A, 624 * (**) translates into 625 * sign*Y*a == D*A + B (mod |n|), 626 * i.e. 627 * sign*Y*a - D*A == B (mod |n|). 628 * Similarly, (*) translates into 629 * -sign*X*a == A (mod |n|). 630 * 631 * Thus, 632 * sign*Y*a + D*sign*X*a == B (mod |n|), 633 * i.e. 634 * sign*(Y + D*X)*a == B (mod |n|). 635 * 636 * So if we set (X, Y, sign) := (Y + D*X, X, -sign), we arrive back at 637 * -sign*X*a == B (mod |n|), 638 * sign*Y*a == A (mod |n|). 639 * Note that X and Y stay non-negative all the time. 640 */ 641 642 if (!BN_mul(tmp, D, X, ctx)) 643 goto err; 644 if (!BN_add(tmp, tmp, Y)) 645 goto err; 646 647 M = Y; /* keep the BIGNUM object, the value does not matter */ 648 Y = X; 649 X = tmp; 650 sign = -sign; 651 } 652 653 /* 654 * The while loop (Euclid's algorithm) ends when 655 * A == gcd(a,n); 656 * we have 657 * sign*Y*a == A (mod |n|), 658 * where Y is non-negative. 659 */ 660 661 if (sign < 0) { 662 if (!BN_sub(Y, n, Y)) 663 goto err; 664 } 665 /* Now Y*a == A (mod |n|). */ 666 667 if (BN_is_one(A)) { 668 /* Y*a == 1 (mod |n|) */ 669 if (!Y->neg && BN_ucmp(Y, n) < 0) { 670 if (!BN_copy(R, Y)) 671 goto err; 672 } else { 673 if (!BN_nnmod(R, Y, n, ctx)) 674 goto err; 675 } 676 } else { 677 BNerr(BN_F_BN_MOD_INVERSE_NO_BRANCH, BN_R_NO_INVERSE); 678 goto err; 679 } 680 ret = R; 681 682 err: 683 if ((ret == NULL) && (in == NULL)) 684 BN_free(R); 685 BN_CTX_end(ctx); 686 bn_check_top(ret); 687 return (ret); 688 } 689