1/* mpicoder.c - Coder for the external representation of MPIs 2 * Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003 3 * 2008 Free Software Foundation, Inc. 4 * 5 * This file is part of Libgcrypt. 6 * 7 * Libgcrypt is free software; you can redistribute it and/or modify 8 * it under the terms of the GNU Lesser General Public License as 9 * published by the Free Software Foundation; either version 2.1 of 10 * the License, or (at your option) any later version. 11 * 12 * Libgcrypt is distributed in the hope that it will be useful, 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 * GNU Lesser General Public License for more details. 16 * 17 * You should have received a copy of the GNU Lesser General Public 18 * License along with this program; if not, see <http://www.gnu.org/licenses/>. 19 */ 20 21#include <config.h> 22#include <stdio.h> 23#include <string.h> 24#include <stdlib.h> 25 26#include "mpi-internal.h" 27#include "g10lib.h" 28 29#define MAX_EXTERN_MPI_BITS 16384 30 31/* Helper used to scan PGP style MPIs. Returns NULL on failure. */ 32static gcry_mpi_t 33mpi_read_from_buffer (const unsigned char *buffer, unsigned *ret_nread, 34 int secure) 35{ 36 int i, j; 37 unsigned int nbits, nbytes, nlimbs, nread=0; 38 mpi_limb_t a; 39 gcry_mpi_t val = MPI_NULL; 40 41 if ( *ret_nread < 2 ) 42 goto leave; 43 nbits = buffer[0] << 8 | buffer[1]; 44 if ( nbits > MAX_EXTERN_MPI_BITS ) 45 { 46/* log_debug ("mpi too large (%u bits)\n", nbits); */ 47 goto leave; 48 } 49 buffer += 2; 50 nread = 2; 51 52 nbytes = (nbits+7) / 8; 53 nlimbs = (nbytes+BYTES_PER_MPI_LIMB-1) / BYTES_PER_MPI_LIMB; 54 val = secure? mpi_alloc_secure (nlimbs) : mpi_alloc (nlimbs); 55 i = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB; 56 i %= BYTES_PER_MPI_LIMB; 57 j= val->nlimbs = nlimbs; 58 val->sign = 0; 59 for ( ; j > 0; j-- ) 60 { 61 a = 0; 62 for (; i < BYTES_PER_MPI_LIMB; i++ ) 63 { 64 if ( ++nread > *ret_nread ) 65 { 66/* log_debug ("mpi larger than buffer"); */ 67 mpi_free (val); 68 val = NULL; 69 goto leave; 70 } 71 a <<= 8; 72 a |= *buffer++; 73 } 74 i = 0; 75 val->d[j-1] = a; 76 } 77 78 leave: 79 *ret_nread = nread; 80 return val; 81} 82 83 84/**************** 85 * Fill the mpi VAL from the hex string in STR. 86 */ 87static int 88mpi_fromstr (gcry_mpi_t val, const char *str) 89{ 90 int sign = 0; 91 int prepend_zero = 0; 92 int i, j, c, c1, c2; 93 unsigned int nbits, nbytes, nlimbs; 94 mpi_limb_t a; 95 96 if ( *str == '-' ) 97 { 98 sign = 1; 99 str++; 100 } 101 102 /* Skip optional hex prefix. */ 103 if ( *str == '0' && str[1] == 'x' ) 104 str += 2; 105 106 nbits = 4 * strlen (str); 107 if ((nbits % 8)) 108 prepend_zero = 1; 109 110 nbytes = (nbits+7) / 8; 111 nlimbs = (nbytes+BYTES_PER_MPI_LIMB-1) / BYTES_PER_MPI_LIMB; 112 113 if ( val->alloced < nlimbs ) 114 mpi_resize (val, nlimbs); 115 116 i = BYTES_PER_MPI_LIMB - (nbytes % BYTES_PER_MPI_LIMB); 117 i %= BYTES_PER_MPI_LIMB; 118 j = val->nlimbs = nlimbs; 119 val->sign = sign; 120 for (; j > 0; j--) 121 { 122 a = 0; 123 for (; i < BYTES_PER_MPI_LIMB; i++) 124 { 125 if (prepend_zero) 126 { 127 c1 = '0'; 128 prepend_zero = 0; 129 } 130 else 131 c1 = *str++; 132 133 if (!c1) 134 { 135 mpi_clear (val); 136 return 1; /* Error. */ 137 } 138 c2 = *str++; 139 if (!c2) 140 { 141 mpi_clear (val); 142 return 1; /* Error. */ 143 } 144 if ( c1 >= '0' && c1 <= '9' ) 145 c = c1 - '0'; 146 else if ( c1 >= 'a' && c1 <= 'f' ) 147 c = c1 - 'a' + 10; 148 else if ( c1 >= 'A' && c1 <= 'F' ) 149 c = c1 - 'A' + 10; 150 else 151 { 152 mpi_clear (val); 153 return 1; /* Error. */ 154 } 155 c <<= 4; 156 if ( c2 >= '0' && c2 <= '9' ) 157 c |= c2 - '0'; 158 else if( c2 >= 'a' && c2 <= 'f' ) 159 c |= c2 - 'a' + 10; 160 else if( c2 >= 'A' && c2 <= 'F' ) 161 c |= c2 - 'A' + 10; 162 else 163 { 164 mpi_clear(val); 165 return 1; /* Error. */ 166 } 167 a <<= 8; 168 a |= c; 169 } 170 i = 0; 171 val->d[j-1] = a; 172 } 173 174 return 0; /* Okay. */ 175} 176 177 178/* Dump the value of A in a format suitable for debugging to 179 Libgcrypt's logging stream. Note that one leading space but no 180 trailing space or linefeed will be printed. It is okay to pass 181 NULL for A. */ 182void 183gcry_mpi_dump (const gcry_mpi_t a) 184{ 185 int i; 186 187 log_printf (" "); 188 if (!a) 189 log_printf ("[MPI_NULL]"); 190 else 191 { 192 if (a->sign) 193 log_printf ( "-"); 194#if BYTES_PER_MPI_LIMB == 2 195# define X "4" 196#elif BYTES_PER_MPI_LIMB == 4 197# define X "8" 198#elif BYTES_PER_MPI_LIMB == 8 199# define X "16" 200#elif BYTES_PER_MPI_LIMB == 16 201# define X "32" 202#else 203# error please define the format here 204#endif 205 for (i=a->nlimbs; i > 0 ; i-- ) 206 { 207 log_printf (i != a->nlimbs? "%0" X "lX":"%lX", (ulong)a->d[i-1]); 208 } 209#undef X 210 if (!a->nlimbs) 211 log_printf ("0"); 212 } 213} 214 215/* Convience function used internally. */ 216void 217_gcry_log_mpidump (const char *text, gcry_mpi_t a) 218{ 219 log_printf ("%s:", text); 220 gcry_mpi_dump (a); 221 log_printf ("\n"); 222} 223 224 225/* Return an allocated buffer with the MPI (msb first). NBYTES 226 receives the length of this buffer. Caller must free the return 227 string. This function returns an allocated buffer with NBYTES set 228 to zero if the value of A is zero. If sign is not NULL, it will be 229 set to the sign of the A. On error NULL is returned and ERRNO set 230 appropriately. */ 231static unsigned char * 232do_get_buffer (gcry_mpi_t a, unsigned int *nbytes, int *sign, int force_secure) 233{ 234 unsigned char *p, *buffer; 235 mpi_limb_t alimb; 236 int i; 237 size_t n; 238 239 if (sign) 240 *sign = a->sign; 241 242 *nbytes = a->nlimbs * BYTES_PER_MPI_LIMB; 243 n = *nbytes? *nbytes:1; /* Allocate at least one byte. */ 244 p = buffer = (force_secure || mpi_is_secure(a))? gcry_malloc_secure (n) 245 : gcry_malloc (n); 246 if (!buffer) 247 return NULL; 248 249 for (i=a->nlimbs-1; i >= 0; i--) 250 { 251 alimb = a->d[i]; 252#if BYTES_PER_MPI_LIMB == 4 253 *p++ = alimb >> 24; 254 *p++ = alimb >> 16; 255 *p++ = alimb >> 8; 256 *p++ = alimb ; 257#elif BYTES_PER_MPI_LIMB == 8 258 *p++ = alimb >> 56; 259 *p++ = alimb >> 48; 260 *p++ = alimb >> 40; 261 *p++ = alimb >> 32; 262 *p++ = alimb >> 24; 263 *p++ = alimb >> 16; 264 *p++ = alimb >> 8; 265 *p++ = alimb ; 266#else 267# error please implement for this limb size. 268#endif 269 } 270 271 /* This is sub-optimal but we need to do the shift operation because 272 the caller has to free the returned buffer. */ 273 for (p=buffer; *nbytes && !*p; p++, --*nbytes) 274 ; 275 if (p != buffer) 276 memmove (buffer,p, *nbytes); 277 return buffer; 278} 279 280 281byte * 282_gcry_mpi_get_buffer (gcry_mpi_t a, unsigned int *nbytes, int *sign) 283{ 284 return do_get_buffer (a, nbytes, sign, 0); 285} 286 287byte * 288_gcry_mpi_get_secure_buffer (gcry_mpi_t a, unsigned *nbytes, int *sign) 289{ 290 return do_get_buffer (a, nbytes, sign, 1); 291} 292 293 294/* 295 * Use the NBYTES at BUFFER_ARG to update A. Set the sign of a to 296 * SIGN. 297 */ 298void 299_gcry_mpi_set_buffer (gcry_mpi_t a, const void *buffer_arg, 300 unsigned int nbytes, int sign) 301{ 302 const unsigned char *buffer = (const unsigned char*)buffer_arg; 303 const unsigned char *p; 304 mpi_limb_t alimb; 305 int nlimbs; 306 int i; 307 308 nlimbs = (nbytes + BYTES_PER_MPI_LIMB - 1) / BYTES_PER_MPI_LIMB; 309 RESIZE_IF_NEEDED(a, nlimbs); 310 a->sign = sign; 311 312 for (i=0, p = buffer+nbytes-1; p >= buffer+BYTES_PER_MPI_LIMB; ) 313 { 314#if BYTES_PER_MPI_LIMB == 4 315 alimb = *p-- ; 316 alimb |= *p-- << 8 ; 317 alimb |= *p-- << 16 ; 318 alimb |= *p-- << 24 ; 319#elif BYTES_PER_MPI_LIMB == 8 320 alimb = (mpi_limb_t)*p-- ; 321 alimb |= (mpi_limb_t)*p-- << 8 ; 322 alimb |= (mpi_limb_t)*p-- << 16 ; 323 alimb |= (mpi_limb_t)*p-- << 24 ; 324 alimb |= (mpi_limb_t)*p-- << 32 ; 325 alimb |= (mpi_limb_t)*p-- << 40 ; 326 alimb |= (mpi_limb_t)*p-- << 48 ; 327 alimb |= (mpi_limb_t)*p-- << 56 ; 328#else 329# error please implement for this limb size. 330#endif 331 a->d[i++] = alimb; 332 } 333 if ( p >= buffer ) 334 { 335#if BYTES_PER_MPI_LIMB == 4 336 alimb = *p--; 337 if (p >= buffer) 338 alimb |= *p-- << 8; 339 if (p >= buffer) 340 alimb |= *p-- << 16; 341 if (p >= buffer) 342 alimb |= *p-- << 24; 343#elif BYTES_PER_MPI_LIMB == 8 344 alimb = (mpi_limb_t)*p--; 345 if (p >= buffer) 346 alimb |= (mpi_limb_t)*p-- << 8; 347 if (p >= buffer) 348 alimb |= (mpi_limb_t)*p-- << 16; 349 if (p >= buffer) 350 alimb |= (mpi_limb_t)*p-- << 24; 351 if (p >= buffer) 352 alimb |= (mpi_limb_t)*p-- << 32; 353 if (p >= buffer) 354 alimb |= (mpi_limb_t)*p-- << 40; 355 if (p >= buffer) 356 alimb |= (mpi_limb_t)*p-- << 48; 357 if (p >= buffer) 358 alimb |= (mpi_limb_t)*p-- << 56; 359#else 360# error please implement for this limb size. 361#endif 362 a->d[i++] = alimb; 363 } 364 a->nlimbs = i; 365 gcry_assert (i == nlimbs); 366} 367 368 369/* Convert the external representation of an integer stored in BUFFER 370 with a length of BUFLEN into a newly create MPI returned in 371 RET_MPI. If NBYTES is not NULL, it will receive the number of 372 bytes actually scanned after a successful operation. */ 373gcry_error_t 374gcry_mpi_scan (struct gcry_mpi **ret_mpi, enum gcry_mpi_format format, 375 const void *buffer_arg, size_t buflen, size_t *nscanned) 376{ 377 const unsigned char *buffer = (const unsigned char*)buffer_arg; 378 struct gcry_mpi *a = NULL; 379 unsigned int len; 380 int secure = (buffer && gcry_is_secure (buffer)); 381 382 if (format == GCRYMPI_FMT_SSH) 383 len = 0; 384 else 385 len = buflen; 386 387 if (format == GCRYMPI_FMT_STD) 388 { 389 const unsigned char *s = buffer; 390 391 a = secure? mpi_alloc_secure ((len+BYTES_PER_MPI_LIMB-1) 392 /BYTES_PER_MPI_LIMB) 393 : mpi_alloc ((len+BYTES_PER_MPI_LIMB-1)/BYTES_PER_MPI_LIMB); 394 if (len) 395 { 396 a->sign = !!(*s & 0x80); 397 if (a->sign) 398 { 399 /* FIXME: we have to convert from 2compl to magnitude format */ 400 mpi_free (a); 401 return gcry_error (GPG_ERR_INTERNAL); 402 } 403 else 404 _gcry_mpi_set_buffer (a, s, len, 0); 405 } 406 if (ret_mpi) 407 { 408 mpi_normalize ( a ); 409 *ret_mpi = a; 410 } 411 else 412 mpi_free(a); 413 return 0; 414 } 415 else if (format == GCRYMPI_FMT_USG) 416 { 417 a = secure? mpi_alloc_secure ((len+BYTES_PER_MPI_LIMB-1) 418 /BYTES_PER_MPI_LIMB) 419 : mpi_alloc ((len+BYTES_PER_MPI_LIMB-1)/BYTES_PER_MPI_LIMB); 420 421 if (len) 422 _gcry_mpi_set_buffer (a, buffer, len, 0); 423 if (ret_mpi) 424 { 425 mpi_normalize ( a ); 426 *ret_mpi = a; 427 } 428 else 429 mpi_free(a); 430 return 0; 431 } 432 else if (format == GCRYMPI_FMT_PGP) 433 { 434 a = mpi_read_from_buffer (buffer, &len, secure); 435 if (nscanned) 436 *nscanned = len; 437 if (ret_mpi && a) 438 { 439 mpi_normalize (a); 440 *ret_mpi = a; 441 } 442 else if (a) 443 { 444 mpi_free(a); 445 a = NULL; 446 } 447 return a? 0 : gcry_error (GPG_ERR_INV_OBJ); 448 } 449 else if (format == GCRYMPI_FMT_SSH) 450 { 451 const unsigned char *s = buffer; 452 size_t n; 453 454 /* This test is not strictly necessary and an assert (!len) 455 would be sufficient. We keep this test in case we later 456 allow the BUFLEN argument to act as a sanitiy check. Same 457 below. */ 458 if (len && len < 4) 459 return gcry_error (GPG_ERR_TOO_SHORT); 460 461 n = (s[0] << 24 | s[1] << 16 | s[2] << 8 | s[3]); 462 s += 4; 463 if (len) 464 len -= 4; 465 if (len && n > len) 466 return gcry_error (GPG_ERR_TOO_LARGE); 467 468 a = secure? mpi_alloc_secure ((n+BYTES_PER_MPI_LIMB-1) 469 /BYTES_PER_MPI_LIMB) 470 : mpi_alloc ((n+BYTES_PER_MPI_LIMB-1)/BYTES_PER_MPI_LIMB); 471 if (n) 472 { 473 a->sign = !!(*s & 0x80); 474 if (a->sign) 475 { 476 /* FIXME: we have to convert from 2compl to magnitude format */ 477 mpi_free(a); 478 return gcry_error (GPG_ERR_INTERNAL); 479 } 480 else 481 _gcry_mpi_set_buffer( a, s, n, 0 ); 482 } 483 if (nscanned) 484 *nscanned = n+4; 485 if (ret_mpi) 486 { 487 mpi_normalize ( a ); 488 *ret_mpi = a; 489 } 490 else 491 mpi_free(a); 492 return 0; 493 } 494 else if (format == GCRYMPI_FMT_HEX) 495 { 496 /* We can only handle C strings for now. */ 497 if (buflen) 498 return gcry_error (GPG_ERR_INV_ARG); 499 500 a = secure? mpi_alloc_secure (0) : mpi_alloc(0); 501 if (mpi_fromstr (a, (const char *)buffer)) 502 { 503 mpi_free (a); 504 return gcry_error (GPG_ERR_INV_OBJ); 505 } 506 if (ret_mpi) 507 { 508 mpi_normalize ( a ); 509 *ret_mpi = a; 510 } 511 else 512 mpi_free(a); 513 return 0; 514 } 515 else 516 return gcry_error (GPG_ERR_INV_ARG); 517} 518 519 520/* Convert the big integer A into the external representation 521 described by FORMAT and store it in the provided BUFFER which has 522 been allocated by the user with a size of BUFLEN bytes. NWRITTEN 523 receives the actual length of the external representation unless it 524 has been passed as NULL. BUFFER may be NULL to query the required 525 length. */ 526gcry_error_t 527gcry_mpi_print (enum gcry_mpi_format format, 528 unsigned char *buffer, size_t buflen, 529 size_t *nwritten, struct gcry_mpi *a) 530{ 531 unsigned int nbits = mpi_get_nbits (a); 532 size_t len; 533 size_t dummy_nwritten; 534 535 if (!nwritten) 536 nwritten = &dummy_nwritten; 537 538 len = buflen; 539 *nwritten = 0; 540 if (format == GCRYMPI_FMT_STD) 541 { 542 unsigned char *tmp; 543 int extra = 0; 544 unsigned int n; 545 546 if (a->sign) 547 return gcry_error (GPG_ERR_INTERNAL); /* Can't handle it yet. */ 548 549 tmp = _gcry_mpi_get_buffer (a, &n, NULL); 550 if (!tmp) 551 return gpg_error_from_syserror (); 552 if (n && (*tmp & 0x80)) 553 { 554 n++; 555 extra=1; 556 } 557 558 if (buffer && n > len) 559 { 560 /* The provided buffer is too short. */ 561 gcry_free (tmp); 562 return gcry_error (GPG_ERR_TOO_SHORT); 563 } 564 if (buffer) 565 { 566 unsigned char *s = buffer; 567 568 if (extra) 569 *s++ = 0; 570 memcpy (s, tmp, n-extra); 571 } 572 gcry_free(tmp); 573 *nwritten = n; 574 return 0; 575 } 576 else if (format == GCRYMPI_FMT_USG) 577 { 578 unsigned int n = (nbits + 7)/8; 579 580 /* Note: We ignore the sign for this format. */ 581 /* FIXME: for performance reasons we should put this into 582 mpi_aprint because we can then use the buffer directly. */ 583 if (buffer && n > len) 584 return gcry_error (GPG_ERR_TOO_SHORT); 585 if (buffer) 586 { 587 unsigned char *tmp; 588 589 tmp = _gcry_mpi_get_buffer (a, &n, NULL); 590 if (!tmp) 591 return gpg_error_from_syserror (); 592 memcpy (buffer, tmp, n); 593 gcry_free (tmp); 594 } 595 *nwritten = n; 596 return 0; 597 } 598 else if (format == GCRYMPI_FMT_PGP) 599 { 600 unsigned int n = (nbits + 7)/8; 601 602 /* The PGP format can only handle unsigned integers. */ 603 if( a->sign ) 604 return gcry_error (GPG_ERR_INV_ARG); 605 606 if (buffer && n+2 > len) 607 return gcry_error (GPG_ERR_TOO_SHORT); 608 609 if (buffer) 610 { 611 unsigned char *tmp; 612 unsigned char *s = buffer; 613 614 s[0] = nbits >> 8; 615 s[1] = nbits; 616 617 tmp = _gcry_mpi_get_buffer (a, &n, NULL); 618 if (!tmp) 619 return gpg_error_from_syserror (); 620 memcpy (s+2, tmp, n); 621 gcry_free (tmp); 622 } 623 *nwritten = n+2; 624 return 0; 625 } 626 else if (format == GCRYMPI_FMT_SSH) 627 { 628 unsigned char *tmp; 629 int extra = 0; 630 unsigned int n; 631 632 if (a->sign) 633 return gcry_error (GPG_ERR_INTERNAL); /* Can't handle it yet. */ 634 635 tmp = _gcry_mpi_get_buffer (a, &n, NULL); 636 if (!tmp) 637 return gpg_error_from_syserror (); 638 if (n && (*tmp & 0x80)) 639 { 640 n++; 641 extra=1; 642 } 643 644 if (buffer && n+4 > len) 645 { 646 gcry_free(tmp); 647 return gcry_error (GPG_ERR_TOO_SHORT); 648 } 649 650 if (buffer) 651 { 652 unsigned char *s = buffer; 653 654 *s++ = n >> 24; 655 *s++ = n >> 16; 656 *s++ = n >> 8; 657 *s++ = n; 658 if (extra) 659 *s++ = 0; 660 661 memcpy (s, tmp, n-extra); 662 } 663 gcry_free (tmp); 664 *nwritten = 4+n; 665 return 0; 666 } 667 else if (format == GCRYMPI_FMT_HEX) 668 { 669 unsigned char *tmp; 670 int i; 671 int extra = 0; 672 unsigned int n = 0; 673 674 tmp = _gcry_mpi_get_buffer (a, &n, NULL); 675 if (!tmp) 676 return gpg_error_from_syserror (); 677 if (!n || (*tmp & 0x80)) 678 extra = 2; 679 680 if (buffer && 2*n + extra + !!a->sign + 1 > len) 681 { 682 gcry_free(tmp); 683 return gcry_error (GPG_ERR_TOO_SHORT); 684 } 685 if (buffer) 686 { 687 unsigned char *s = buffer; 688 689 if (a->sign) 690 *s++ = '-'; 691 if (extra) 692 { 693 *s++ = '0'; 694 *s++ = '0'; 695 } 696 697 for (i=0; i < n; i++) 698 { 699 unsigned int c = tmp[i]; 700 701 *s++ = (c >> 4) < 10? '0'+(c>>4) : 'A'+(c>>4)-10 ; 702 c &= 15; 703 *s++ = c < 10? '0'+c : 'A'+c-10 ; 704 } 705 *s++ = 0; 706 *nwritten = s - buffer; 707 } 708 else 709 { 710 *nwritten = 2*n + extra + !!a->sign + 1; 711 } 712 gcry_free (tmp); 713 return 0; 714 } 715 else 716 return gcry_error (GPG_ERR_INV_ARG); 717} 718 719 720/* 721 * Like gcry_mpi_print but this function allocates the buffer itself. 722 * The caller has to supply the address of a pointer. NWRITTEN may be 723 * NULL. 724 */ 725gcry_error_t 726gcry_mpi_aprint (enum gcry_mpi_format format, 727 unsigned char **buffer, size_t *nwritten, 728 struct gcry_mpi *a) 729{ 730 size_t n; 731 gcry_error_t rc; 732 733 *buffer = NULL; 734 rc = gcry_mpi_print (format, NULL, 0, &n, a); 735 if (rc) 736 return rc; 737 738 *buffer = mpi_is_secure(a) ? gcry_malloc_secure (n) : gcry_malloc (n); 739 if (!*buffer) 740 return gpg_error_from_syserror (); 741 rc = gcry_mpi_print( format, *buffer, n, &n, a ); 742 if (rc) 743 { 744 gcry_free(*buffer); 745 *buffer = NULL; 746 } 747 else if (nwritten) 748 *nwritten = n; 749 return rc; 750} 751