1 /* mpicoder.c - Coder for the external representation of MPIs 2 * Copyright (C) 1998, 1999 Free Software Foundation, Inc. 3 * 4 * This file is part of GnuPG. 5 * 6 * GnuPG is free software; you can redistribute it and/or modify 7 * it under the terms of the GNU General Public License as published by 8 * the Free Software Foundation; either version 2 of the License, or 9 * (at your option) any later version. 10 * 11 * GnuPG is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 * GNU General Public License for more details. 15 * 16 * You should have received a copy of the GNU General Public License 17 * along with this program; if not, write to the Free Software 18 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA 19 */ 20 21 #include <linux/bitops.h> 22 #include <linux/count_zeros.h> 23 #include <linux/byteorder/generic.h> 24 #include <linux/scatterlist.h> 25 #include <linux/string.h> 26 #include "mpi-internal.h" 27 28 #define MAX_EXTERN_SCAN_BYTES (16*1024*1024) 29 #define MAX_EXTERN_MPI_BITS 16384 30 31 /** 32 * mpi_read_raw_data - Read a raw byte stream as a positive integer 33 * @xbuffer: The data to read 34 * @nbytes: The amount of data to read 35 */ 36 MPI mpi_read_raw_data(const void *xbuffer, size_t nbytes) 37 { 38 const uint8_t *buffer = xbuffer; 39 int i, j; 40 unsigned nbits, nlimbs; 41 mpi_limb_t a; 42 MPI val = NULL; 43 44 while (nbytes > 0 && buffer[0] == 0) { 45 buffer++; 46 nbytes--; 47 } 48 49 nbits = nbytes * 8; 50 if (nbits > MAX_EXTERN_MPI_BITS) { 51 pr_info("MPI: mpi too large (%u bits)\n", nbits); 52 return NULL; 53 } 54 if (nbytes > 0) 55 nbits -= count_leading_zeros(buffer[0]) - (BITS_PER_LONG - 8); 56 57 nlimbs = DIV_ROUND_UP(nbytes, BYTES_PER_MPI_LIMB); 58 val = mpi_alloc(nlimbs); 59 if (!val) 60 return NULL; 61 val->nbits = nbits; 62 val->sign = 0; 63 val->nlimbs = nlimbs; 64 65 if (nbytes > 0) { 66 i = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB; 67 i %= BYTES_PER_MPI_LIMB; 68 for (j = nlimbs; j > 0; j--) { 69 a = 0; 70 for (; i < BYTES_PER_MPI_LIMB; i++) { 71 a <<= 8; 72 a |= *buffer++; 73 } 74 i = 0; 75 val->d[j - 1] = a; 76 } 77 } 78 return val; 79 } 80 EXPORT_SYMBOL_GPL(mpi_read_raw_data); 81 82 MPI mpi_read_from_buffer(const void *xbuffer, unsigned *ret_nread) 83 { 84 const uint8_t *buffer = xbuffer; 85 unsigned int nbits, nbytes; 86 MPI val; 87 88 if (*ret_nread < 2) 89 return ERR_PTR(-EINVAL); 90 nbits = buffer[0] << 8 | buffer[1]; 91 92 if (nbits > MAX_EXTERN_MPI_BITS) { 93 pr_info("MPI: mpi too large (%u bits)\n", nbits); 94 return ERR_PTR(-EINVAL); 95 } 96 97 nbytes = DIV_ROUND_UP(nbits, 8); 98 if (nbytes + 2 > *ret_nread) { 99 pr_info("MPI: mpi larger than buffer nbytes=%u ret_nread=%u\n", 100 nbytes, *ret_nread); 101 return ERR_PTR(-EINVAL); 102 } 103 104 val = mpi_read_raw_data(buffer + 2, nbytes); 105 if (!val) 106 return ERR_PTR(-ENOMEM); 107 108 *ret_nread = nbytes + 2; 109 return val; 110 } 111 EXPORT_SYMBOL_GPL(mpi_read_from_buffer); 112 113 /**************** 114 * Fill the mpi VAL from the hex string in STR. 115 */ 116 int mpi_fromstr(MPI val, const char *str) 117 { 118 int sign = 0; 119 int prepend_zero = 0; 120 int i, j, c, c1, c2; 121 unsigned int nbits, nbytes, nlimbs; 122 mpi_limb_t a; 123 124 if (*str == '-') { 125 sign = 1; 126 str++; 127 } 128 129 /* Skip optional hex prefix. */ 130 if (*str == '0' && str[1] == 'x') 131 str += 2; 132 133 nbits = strlen(str); 134 if (nbits > MAX_EXTERN_SCAN_BYTES) { 135 mpi_clear(val); 136 return -EINVAL; 137 } 138 nbits *= 4; 139 if ((nbits % 8)) 140 prepend_zero = 1; 141 142 nbytes = (nbits+7) / 8; 143 nlimbs = (nbytes+BYTES_PER_MPI_LIMB-1) / BYTES_PER_MPI_LIMB; 144 145 if (val->alloced < nlimbs) 146 mpi_resize(val, nlimbs); 147 148 i = BYTES_PER_MPI_LIMB - (nbytes % BYTES_PER_MPI_LIMB); 149 i %= BYTES_PER_MPI_LIMB; 150 j = val->nlimbs = nlimbs; 151 val->sign = sign; 152 for (; j > 0; j--) { 153 a = 0; 154 for (; i < BYTES_PER_MPI_LIMB; i++) { 155 if (prepend_zero) { 156 c1 = '0'; 157 prepend_zero = 0; 158 } else 159 c1 = *str++; 160 161 if (!c1) { 162 mpi_clear(val); 163 return -EINVAL; 164 } 165 c2 = *str++; 166 if (!c2) { 167 mpi_clear(val); 168 return -EINVAL; 169 } 170 if (c1 >= '0' && c1 <= '9') 171 c = c1 - '0'; 172 else if (c1 >= 'a' && c1 <= 'f') 173 c = c1 - 'a' + 10; 174 else if (c1 >= 'A' && c1 <= 'F') 175 c = c1 - 'A' + 10; 176 else { 177 mpi_clear(val); 178 return -EINVAL; 179 } 180 c <<= 4; 181 if (c2 >= '0' && c2 <= '9') 182 c |= c2 - '0'; 183 else if (c2 >= 'a' && c2 <= 'f') 184 c |= c2 - 'a' + 10; 185 else if (c2 >= 'A' && c2 <= 'F') 186 c |= c2 - 'A' + 10; 187 else { 188 mpi_clear(val); 189 return -EINVAL; 190 } 191 a <<= 8; 192 a |= c; 193 } 194 i = 0; 195 val->d[j-1] = a; 196 } 197 198 return 0; 199 } 200 EXPORT_SYMBOL_GPL(mpi_fromstr); 201 202 MPI mpi_scanval(const char *string) 203 { 204 MPI a; 205 206 a = mpi_alloc(0); 207 if (!a) 208 return NULL; 209 210 if (mpi_fromstr(a, string)) { 211 mpi_free(a); 212 return NULL; 213 } 214 mpi_normalize(a); 215 return a; 216 } 217 EXPORT_SYMBOL_GPL(mpi_scanval); 218 219 static int count_lzeros(MPI a) 220 { 221 mpi_limb_t alimb; 222 int i, lzeros = 0; 223 224 for (i = a->nlimbs - 1; i >= 0; i--) { 225 alimb = a->d[i]; 226 if (alimb == 0) { 227 lzeros += sizeof(mpi_limb_t); 228 } else { 229 lzeros += count_leading_zeros(alimb) / 8; 230 break; 231 } 232 } 233 return lzeros; 234 } 235 236 /** 237 * mpi_read_buffer() - read MPI to a buffer provided by user (msb first) 238 * 239 * @a: a multi precision integer 240 * @buf: buffer to which the output will be written to. Needs to be at 241 * least mpi_get_size(a) long. 242 * @buf_len: size of the buf. 243 * @nbytes: receives the actual length of the data written on success and 244 * the data to-be-written on -EOVERFLOW in case buf_len was too 245 * small. 246 * @sign: if not NULL, it will be set to the sign of a. 247 * 248 * Return: 0 on success or error code in case of error 249 */ 250 int mpi_read_buffer(MPI a, uint8_t *buf, unsigned buf_len, unsigned *nbytes, 251 int *sign) 252 { 253 uint8_t *p; 254 #if BYTES_PER_MPI_LIMB == 4 255 __be32 alimb; 256 #elif BYTES_PER_MPI_LIMB == 8 257 __be64 alimb; 258 #else 259 #error please implement for this limb size. 260 #endif 261 unsigned int n = mpi_get_size(a); 262 int i, lzeros; 263 264 if (!buf || !nbytes) 265 return -EINVAL; 266 267 if (sign) 268 *sign = a->sign; 269 270 lzeros = count_lzeros(a); 271 272 if (buf_len < n - lzeros) { 273 *nbytes = n - lzeros; 274 return -EOVERFLOW; 275 } 276 277 p = buf; 278 *nbytes = n - lzeros; 279 280 for (i = a->nlimbs - 1 - lzeros / BYTES_PER_MPI_LIMB, 281 lzeros %= BYTES_PER_MPI_LIMB; 282 i >= 0; i--) { 283 #if BYTES_PER_MPI_LIMB == 4 284 alimb = cpu_to_be32(a->d[i]); 285 #elif BYTES_PER_MPI_LIMB == 8 286 alimb = cpu_to_be64(a->d[i]); 287 #else 288 #error please implement for this limb size. 289 #endif 290 memcpy(p, (u8 *)&alimb + lzeros, BYTES_PER_MPI_LIMB - lzeros); 291 p += BYTES_PER_MPI_LIMB - lzeros; 292 lzeros = 0; 293 } 294 return 0; 295 } 296 EXPORT_SYMBOL_GPL(mpi_read_buffer); 297 298 /* 299 * mpi_get_buffer() - Returns an allocated buffer with the MPI (msb first). 300 * Caller must free the return string. 301 * This function does return a 0 byte buffer with nbytes set to zero if the 302 * value of A is zero. 303 * 304 * @a: a multi precision integer. 305 * @nbytes: receives the length of this buffer. 306 * @sign: if not NULL, it will be set to the sign of the a. 307 * 308 * Return: Pointer to MPI buffer or NULL on error 309 */ 310 void *mpi_get_buffer(MPI a, unsigned *nbytes, int *sign) 311 { 312 uint8_t *buf; 313 unsigned int n; 314 int ret; 315 316 if (!nbytes) 317 return NULL; 318 319 n = mpi_get_size(a); 320 321 if (!n) 322 n++; 323 324 buf = kmalloc(n, GFP_KERNEL); 325 326 if (!buf) 327 return NULL; 328 329 ret = mpi_read_buffer(a, buf, n, nbytes, sign); 330 331 if (ret) { 332 kfree(buf); 333 return NULL; 334 } 335 return buf; 336 } 337 EXPORT_SYMBOL_GPL(mpi_get_buffer); 338 339 /** 340 * mpi_write_to_sgl() - Funnction exports MPI to an sgl (msb first) 341 * 342 * This function works in the same way as the mpi_read_buffer, but it 343 * takes an sgl instead of u8 * buf. 344 * 345 * @a: a multi precision integer 346 * @sgl: scatterlist to write to. Needs to be at least 347 * mpi_get_size(a) long. 348 * @nbytes: the number of bytes to write. Leading bytes will be 349 * filled with zero. 350 * @sign: if not NULL, it will be set to the sign of a. 351 * 352 * Return: 0 on success or error code in case of error 353 */ 354 int mpi_write_to_sgl(MPI a, struct scatterlist *sgl, unsigned nbytes, 355 int *sign) 356 { 357 u8 *p, *p2; 358 #if BYTES_PER_MPI_LIMB == 4 359 __be32 alimb; 360 #elif BYTES_PER_MPI_LIMB == 8 361 __be64 alimb; 362 #else 363 #error please implement for this limb size. 364 #endif 365 unsigned int n = mpi_get_size(a); 366 struct sg_mapping_iter miter; 367 int i, x, buf_len; 368 int nents; 369 370 if (sign) 371 *sign = a->sign; 372 373 if (nbytes < n) 374 return -EOVERFLOW; 375 376 nents = sg_nents_for_len(sgl, nbytes); 377 if (nents < 0) 378 return -EINVAL; 379 380 sg_miter_start(&miter, sgl, nents, SG_MITER_ATOMIC | SG_MITER_TO_SG); 381 sg_miter_next(&miter); 382 buf_len = miter.length; 383 p2 = miter.addr; 384 385 while (nbytes > n) { 386 i = min_t(unsigned, nbytes - n, buf_len); 387 memset(p2, 0, i); 388 p2 += i; 389 nbytes -= i; 390 391 buf_len -= i; 392 if (!buf_len) { 393 sg_miter_next(&miter); 394 buf_len = miter.length; 395 p2 = miter.addr; 396 } 397 } 398 399 for (i = a->nlimbs - 1; i >= 0; i--) { 400 #if BYTES_PER_MPI_LIMB == 4 401 alimb = a->d[i] ? cpu_to_be32(a->d[i]) : 0; 402 #elif BYTES_PER_MPI_LIMB == 8 403 alimb = a->d[i] ? cpu_to_be64(a->d[i]) : 0; 404 #else 405 #error please implement for this limb size. 406 #endif 407 p = (u8 *)&alimb; 408 409 for (x = 0; x < sizeof(alimb); x++) { 410 *p2++ = *p++; 411 if (!--buf_len) { 412 sg_miter_next(&miter); 413 buf_len = miter.length; 414 p2 = miter.addr; 415 } 416 } 417 } 418 419 sg_miter_stop(&miter); 420 return 0; 421 } 422 EXPORT_SYMBOL_GPL(mpi_write_to_sgl); 423 424 /* 425 * mpi_read_raw_from_sgl() - Function allocates an MPI and populates it with 426 * data from the sgl 427 * 428 * This function works in the same way as the mpi_read_raw_data, but it 429 * takes an sgl instead of void * buffer. i.e. it allocates 430 * a new MPI and reads the content of the sgl to the MPI. 431 * 432 * @sgl: scatterlist to read from 433 * @nbytes: number of bytes to read 434 * 435 * Return: Pointer to a new MPI or NULL on error 436 */ 437 MPI mpi_read_raw_from_sgl(struct scatterlist *sgl, unsigned int nbytes) 438 { 439 struct sg_mapping_iter miter; 440 unsigned int nbits, nlimbs; 441 int x, j, z, lzeros, ents; 442 unsigned int len; 443 const u8 *buff; 444 mpi_limb_t a; 445 MPI val = NULL; 446 447 ents = sg_nents_for_len(sgl, nbytes); 448 if (ents < 0) 449 return NULL; 450 451 sg_miter_start(&miter, sgl, ents, SG_MITER_ATOMIC | SG_MITER_FROM_SG); 452 453 lzeros = 0; 454 len = 0; 455 while (nbytes > 0) { 456 while (len && !*buff) { 457 lzeros++; 458 len--; 459 buff++; 460 } 461 462 if (len && *buff) 463 break; 464 465 sg_miter_next(&miter); 466 buff = miter.addr; 467 len = miter.length; 468 469 nbytes -= lzeros; 470 lzeros = 0; 471 } 472 473 miter.consumed = lzeros; 474 475 nbytes -= lzeros; 476 nbits = nbytes * 8; 477 if (nbits > MAX_EXTERN_MPI_BITS) { 478 sg_miter_stop(&miter); 479 pr_info("MPI: mpi too large (%u bits)\n", nbits); 480 return NULL; 481 } 482 483 if (nbytes > 0) 484 nbits -= count_leading_zeros(*buff) - (BITS_PER_LONG - 8); 485 486 sg_miter_stop(&miter); 487 488 nlimbs = DIV_ROUND_UP(nbytes, BYTES_PER_MPI_LIMB); 489 val = mpi_alloc(nlimbs); 490 if (!val) 491 return NULL; 492 493 val->nbits = nbits; 494 val->sign = 0; 495 val->nlimbs = nlimbs; 496 497 if (nbytes == 0) 498 return val; 499 500 j = nlimbs - 1; 501 a = 0; 502 z = BYTES_PER_MPI_LIMB - nbytes % BYTES_PER_MPI_LIMB; 503 z %= BYTES_PER_MPI_LIMB; 504 505 while (sg_miter_next(&miter)) { 506 buff = miter.addr; 507 len = min_t(unsigned, miter.length, nbytes); 508 nbytes -= len; 509 510 for (x = 0; x < len; x++) { 511 a <<= 8; 512 a |= *buff++; 513 if (((z + x + 1) % BYTES_PER_MPI_LIMB) == 0) { 514 val->d[j--] = a; 515 a = 0; 516 } 517 } 518 z += x; 519 } 520 521 return val; 522 } 523 EXPORT_SYMBOL_GPL(mpi_read_raw_from_sgl); 524 525 /* Perform a two's complement operation on buffer P of size N bytes. */ 526 static void twocompl(unsigned char *p, unsigned int n) 527 { 528 int i; 529 530 for (i = n-1; i >= 0 && !p[i]; i--) 531 ; 532 if (i >= 0) { 533 if ((p[i] & 0x01)) 534 p[i] = (((p[i] ^ 0xfe) | 0x01) & 0xff); 535 else if ((p[i] & 0x02)) 536 p[i] = (((p[i] ^ 0xfc) | 0x02) & 0xfe); 537 else if ((p[i] & 0x04)) 538 p[i] = (((p[i] ^ 0xf8) | 0x04) & 0xfc); 539 else if ((p[i] & 0x08)) 540 p[i] = (((p[i] ^ 0xf0) | 0x08) & 0xf8); 541 else if ((p[i] & 0x10)) 542 p[i] = (((p[i] ^ 0xe0) | 0x10) & 0xf0); 543 else if ((p[i] & 0x20)) 544 p[i] = (((p[i] ^ 0xc0) | 0x20) & 0xe0); 545 else if ((p[i] & 0x40)) 546 p[i] = (((p[i] ^ 0x80) | 0x40) & 0xc0); 547 else 548 p[i] = 0x80; 549 550 for (i--; i >= 0; i--) 551 p[i] ^= 0xff; 552 } 553 } 554 555 int mpi_print(enum gcry_mpi_format format, unsigned char *buffer, 556 size_t buflen, size_t *nwritten, MPI a) 557 { 558 unsigned int nbits = mpi_get_nbits(a); 559 size_t len; 560 size_t dummy_nwritten; 561 int negative; 562 563 if (!nwritten) 564 nwritten = &dummy_nwritten; 565 566 /* Libgcrypt does no always care to set clear the sign if the value 567 * is 0. For printing this is a bit of a surprise, in particular 568 * because if some of the formats don't support negative numbers but 569 * should be able to print a zero. Thus we need this extra test 570 * for a negative number. 571 */ 572 if (a->sign && mpi_cmp_ui(a, 0)) 573 negative = 1; 574 else 575 negative = 0; 576 577 len = buflen; 578 *nwritten = 0; 579 if (format == GCRYMPI_FMT_STD) { 580 unsigned char *tmp; 581 int extra = 0; 582 unsigned int n; 583 584 tmp = mpi_get_buffer(a, &n, NULL); 585 if (!tmp) 586 return -EINVAL; 587 588 if (negative) { 589 twocompl(tmp, n); 590 if (!(*tmp & 0x80)) { 591 /* Need to extend the sign. */ 592 n++; 593 extra = 2; 594 } 595 } else if (n && (*tmp & 0x80)) { 596 /* Positive but the high bit of the returned buffer is set. 597 * Thus we need to print an extra leading 0x00 so that the 598 * output is interpreted as a positive number. 599 */ 600 n++; 601 extra = 1; 602 } 603 604 if (buffer && n > len) { 605 /* The provided buffer is too short. */ 606 kfree(tmp); 607 return -E2BIG; 608 } 609 if (buffer) { 610 unsigned char *s = buffer; 611 612 if (extra == 1) 613 *s++ = 0; 614 else if (extra) 615 *s++ = 0xff; 616 memcpy(s, tmp, n-!!extra); 617 } 618 kfree(tmp); 619 *nwritten = n; 620 return 0; 621 } else if (format == GCRYMPI_FMT_USG) { 622 unsigned int n = (nbits + 7)/8; 623 624 /* Note: We ignore the sign for this format. */ 625 /* FIXME: for performance reasons we should put this into 626 * mpi_aprint because we can then use the buffer directly. 627 */ 628 629 if (buffer && n > len) 630 return -E2BIG; 631 if (buffer) { 632 unsigned char *tmp; 633 634 tmp = mpi_get_buffer(a, &n, NULL); 635 if (!tmp) 636 return -EINVAL; 637 memcpy(buffer, tmp, n); 638 kfree(tmp); 639 } 640 *nwritten = n; 641 return 0; 642 } else if (format == GCRYMPI_FMT_PGP) { 643 unsigned int n = (nbits + 7)/8; 644 645 /* The PGP format can only handle unsigned integers. */ 646 if (negative) 647 return -EINVAL; 648 649 if (buffer && n+2 > len) 650 return -E2BIG; 651 652 if (buffer) { 653 unsigned char *tmp; 654 unsigned char *s = buffer; 655 656 s[0] = nbits >> 8; 657 s[1] = nbits; 658 659 tmp = mpi_get_buffer(a, &n, NULL); 660 if (!tmp) 661 return -EINVAL; 662 memcpy(s+2, tmp, n); 663 kfree(tmp); 664 } 665 *nwritten = n+2; 666 return 0; 667 } else if (format == GCRYMPI_FMT_SSH) { 668 unsigned char *tmp; 669 int extra = 0; 670 unsigned int n; 671 672 tmp = mpi_get_buffer(a, &n, NULL); 673 if (!tmp) 674 return -EINVAL; 675 676 if (negative) { 677 twocompl(tmp, n); 678 if (!(*tmp & 0x80)) { 679 /* Need to extend the sign. */ 680 n++; 681 extra = 2; 682 } 683 } else if (n && (*tmp & 0x80)) { 684 n++; 685 extra = 1; 686 } 687 688 if (buffer && n+4 > len) { 689 kfree(tmp); 690 return -E2BIG; 691 } 692 693 if (buffer) { 694 unsigned char *s = buffer; 695 696 *s++ = n >> 24; 697 *s++ = n >> 16; 698 *s++ = n >> 8; 699 *s++ = n; 700 if (extra == 1) 701 *s++ = 0; 702 else if (extra) 703 *s++ = 0xff; 704 memcpy(s, tmp, n-!!extra); 705 } 706 kfree(tmp); 707 *nwritten = 4+n; 708 return 0; 709 } else if (format == GCRYMPI_FMT_HEX) { 710 unsigned char *tmp; 711 int i; 712 int extra = 0; 713 unsigned int n = 0; 714 715 tmp = mpi_get_buffer(a, &n, NULL); 716 if (!tmp) 717 return -EINVAL; 718 if (!n || (*tmp & 0x80)) 719 extra = 2; 720 721 if (buffer && 2*n + extra + negative + 1 > len) { 722 kfree(tmp); 723 return -E2BIG; 724 } 725 if (buffer) { 726 unsigned char *s = buffer; 727 728 if (negative) 729 *s++ = '-'; 730 if (extra) { 731 *s++ = '0'; 732 *s++ = '0'; 733 } 734 735 for (i = 0; i < n; i++) { 736 unsigned int c = tmp[i]; 737 738 *s++ = (c >> 4) < 10 ? '0'+(c>>4) : 'A'+(c>>4)-10; 739 c &= 15; 740 *s++ = c < 10 ? '0'+c : 'A'+c-10; 741 } 742 *s++ = 0; 743 *nwritten = s - buffer; 744 } else { 745 *nwritten = 2*n + extra + negative + 1; 746 } 747 kfree(tmp); 748 return 0; 749 } else 750 return -EINVAL; 751 } 752 EXPORT_SYMBOL_GPL(mpi_print); 753