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