1.\" $OpenBSD: bn_dump.3,v 1.6 2016/12/10 21:32:14 schwarze Exp $ 2.\" OpenSSL crypto/bn/README.pod aebb9aac Jul 19 09:27:53 2016 -0400 3.\" 4.\" This file was written by Ulf Moeller <ulf@openssl.org>. 5.\" Copyright (c) 2000, 2003, 2006, 2009 The OpenSSL Project. 6.\" All rights reserved. 7.\" 8.\" Redistribution and use in source and binary forms, with or without 9.\" modification, are permitted provided that the following conditions 10.\" are met: 11.\" 12.\" 1. Redistributions of source code must retain the above copyright 13.\" notice, this list of conditions and the following disclaimer. 14.\" 15.\" 2. Redistributions in binary form must reproduce the above copyright 16.\" notice, this list of conditions and the following disclaimer in 17.\" the documentation and/or other materials provided with the 18.\" distribution. 19.\" 20.\" 3. All advertising materials mentioning features or use of this 21.\" software must display the following acknowledgment: 22.\" "This product includes software developed by the OpenSSL Project 23.\" for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 24.\" 25.\" 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 26.\" endorse or promote products derived from this software without 27.\" prior written permission. For written permission, please contact 28.\" openssl-core@openssl.org. 29.\" 30.\" 5. Products derived from this software may not be called "OpenSSL" 31.\" nor may "OpenSSL" appear in their names without prior written 32.\" permission of the OpenSSL Project. 33.\" 34.\" 6. Redistributions of any form whatsoever must retain the following 35.\" acknowledgment: 36.\" "This product includes software developed by the OpenSSL Project 37.\" for use in the OpenSSL Toolkit (http://www.openssl.org/)" 38.\" 39.\" THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 40.\" EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 41.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 42.\" PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 43.\" ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 44.\" SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 45.\" NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 46.\" LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 47.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 48.\" STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 49.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 50.\" OF THE POSSIBILITY OF SUCH DAMAGE. 51.\" 52.Dd $Mdocdate: December 10 2016 $ 53.Dt BN_DUMP 3 54.Os 55.Sh NAME 56.Nm bn_mul_words , 57.Nm bn_mul_add_words , 58.Nm bn_sqr_words , 59.Nm bn_div_words , 60.Nm bn_add_words , 61.Nm bn_sub_words , 62.Nm bn_mul_comba4 , 63.Nm bn_mul_comba8 , 64.Nm bn_sqr_comba4 , 65.Nm bn_sqr_comba8 , 66.Nm bn_cmp_words , 67.Nm bn_mul_normal , 68.Nm bn_mul_low_normal , 69.Nm bn_mul_recursive , 70.Nm bn_mul_part_recursive , 71.Nm bn_mul_low_recursive , 72.Nm bn_mul_high , 73.Nm bn_sqr_normal , 74.Nm bn_sqr_recursive , 75.Nm bn_expand , 76.Nm bn_wexpand , 77.Nm bn_expand2 , 78.Nm bn_fix_top , 79.Nm bn_check_top , 80.Nm bn_print , 81.Nm bn_dump , 82.Nm bn_set_max , 83.Nm bn_set_high , 84.Nm bn_set_low , 85.Nm mul , 86.Nm mul_add , 87.Nm sqr 88.Nd BIGNUM library internal functions 89.Sh SYNOPSIS 90.In openssl/bn.h 91.Ft BN_ULONG 92.Fo bn_mul_words 93.Fa "BN_ULONG *rp" 94.Fa "BN_ULONG *ap" 95.Fa "int num" 96.Fa "BN_ULONG w" 97.Fc 98.Ft BN_ULONG 99.Fo bn_mul_add_words 100.Fa "BN_ULONG *rp" 101.Fa "BN_ULONG *ap" 102.Fa "int num" 103.Fa "BN_ULONG w" 104.Fc 105.Ft void 106.Fo bn_sqr_words 107.Fa "BN_ULONG *rp" 108.Fa "BN_ULONG *ap" 109.Fa "int num" 110.Fc 111.Ft BN_ULONG 112.Fo bn_div_words 113.Fa "BN_ULONG h" 114.Fa "BN_ULONG l" 115.Fa "BN_ULONG d" 116.Fc 117.Ft BN_ULONG 118.Fo bn_add_words 119.Fa "BN_ULONG *rp" 120.Fa "BN_ULONG *ap" 121.Fa "BN_ULONG *bp" 122.Fa "int num" 123.Fc 124.Ft BN_ULONG 125.Fo bn_sub_words 126.Fa "BN_ULONG *rp" 127.Fa "BN_ULONG *ap" 128.Fa "BN_ULONG *bp" 129.Fa "int num" 130.Fc 131.Ft void 132.Fo bn_mul_comba4 133.Fa "BN_ULONG *r" 134.Fa "BN_ULONG *a" 135.Fa "BN_ULONG *b" 136.Fc 137.Ft void 138.Fo bn_mul_comba8 139.Fa "BN_ULONG *r" 140.Fa "BN_ULONG *a" 141.Fa "BN_ULONG *b" 142.Fc 143.Ft void 144.Fo bn_sqr_comba4 145.Fa "BN_ULONG *r" 146.Fa "BN_ULONG *a" 147.Fc 148.Ft void 149.Fo bn_sqr_comba8 150.Fa "BN_ULONG *r" 151.Fa "BN_ULONG *a" 152.Fc 153.Ft int 154.Fo bn_cmp_words 155.Fa "BN_ULONG *a" 156.Fa "BN_ULONG *b" 157.Fa "int n" 158.Fc 159.Ft void 160.Fo bn_mul_normal 161.Fa "BN_ULONG *r" 162.Fa "BN_ULONG *a" 163.Fa "int na" 164.Fa "BN_ULONG *b" 165.Fa "int nb" 166.Fc 167.Ft void 168.Fo bn_mul_low_normal 169.Fa "BN_ULONG *r" 170.Fa "BN_ULONG *a" 171.Fa "BN_ULONG *b" 172.Fa "int n" 173.Fc 174.Ft void 175.Fo bn_mul_recursive 176.Fa "BN_ULONG *r" 177.Fa "BN_ULONG *a" 178.Fa "BN_ULONG *b" 179.Fa "int n2" 180.Fa "int dna" 181.Fa "int dnb" 182.Fa "BN_ULONG *tmp" 183.Fc 184.Ft void 185.Fo bn_mul_part_recursive 186.Fa "BN_ULONG *r" 187.Fa "BN_ULONG *a" 188.Fa "BN_ULONG *b" 189.Fa "int n" 190.Fa "int tna" 191.Fa "int tnb" 192.Fa "BN_ULONG *tmp" 193.Fc 194.Ft void 195.Fo bn_mul_low_recursive 196.Fa "BN_ULONG *r" 197.Fa "BN_ULONG *a" 198.Fa "BN_ULONG *b" 199.Fa "int n2" 200.Fa "BN_ULONG *tmp" 201.Fc 202.Ft void 203.Fo bn_mul_high 204.Fa "BN_ULONG *r" 205.Fa "BN_ULONG *a" 206.Fa "BN_ULONG *b" 207.Fa "BN_ULONG *l" 208.Fa "int n2" 209.Fa "BN_ULONG *tmp" 210.Fc 211.Ft void 212.Fo bn_sqr_normal 213.Fa "BN_ULONG *r" 214.Fa "BN_ULONG *a" 215.Fa "int n" 216.Fa "BN_ULONG *tmp" 217.Fc 218.Ft void 219.Fo bn_sqr_recursive 220.Fa "BN_ULONG *r" 221.Fa "BN_ULONG *a" 222.Fa "int n2" 223.Fa "BN_ULONG *tmp" 224.Fc 225.Ft void 226.Fo mul 227.Fa "BN_ULONG r" 228.Fa "BN_ULONG a" 229.Fa "BN_ULONG w" 230.Fa "BN_ULONG c" 231.Fc 232.Ft void 233.Fo mul_add 234.Fa "BN_ULONG r" 235.Fa "BN_ULONG a" 236.Fa "BN_ULONG w" 237.Fa "BN_ULONG c" 238.Fc 239.Ft void 240.Fo sqr 241.Fa "BN_ULONG r0" 242.Fa "BN_ULONG r1" 243.Fa "BN_ULONG a" 244.Fc 245.Ft BIGNUM * 246.Fo bn_expand 247.Fa "BIGNUM *a" 248.Fa "int bits" 249.Fc 250.Ft BIGNUM * 251.Fo bn_wexpand 252.Fa "BIGNUM *a" 253.Fa "int n" 254.Fc 255.Ft BIGNUM * 256.Fo bn_expand2 257.Fa "BIGNUM *a" 258.Fa "int n" 259.Fc 260.Ft void 261.Fo bn_fix_top 262.Fa "BIGNUM *a" 263.Fc 264.Ft void 265.Fo bn_check_top 266.Fa "BIGNUM *a" 267.Fc 268.Ft void 269.Fo bn_print 270.Fa "BIGNUM *a" 271.Fc 272.Ft void 273.Fo bn_dump 274.Fa "BN_ULONG *d" 275.Fa "int n" 276.Fc 277.Ft void 278.Fo bn_set_max 279.Fa "BIGNUM *a" 280.Fc 281.Ft void 282.Fo bn_set_high 283.Fa "BIGNUM *r" 284.Fa "BIGNUM *a" 285.Fa "int n" 286.Fc 287.Ft void 288.Fo bn_set_low 289.Fa "BIGNUM *r" 290.Fa "BIGNUM *a" 291.Fa "int n" 292.Fc 293.Sh DESCRIPTION 294This page documents the internal functions used by the OpenSSL 295.Vt BIGNUM 296implementation. 297They are described here to facilitate debugging and extending the 298library. 299They are 300.Em not 301to be used by applications. 302.Ss The BIGNUM structure 303.Bd -literal 304typedef struct bignum_st BIGNUM; 305 306struct bignum_st { 307 BN_ULONG *d; /* Pointer to an array of 'BN_BITS2' bit chunks. */ 308 int top; /* Index of last used d +1. */ 309 /* The next are internal book keeping for bn_expand. */ 310 int dmax; /* Size of the d array. */ 311 int neg; /* one if the number is negative */ 312 int flags; 313}; 314.Ed 315.Pp 316The integer value is stored in 317.Fa d , 318a 319.Xr malloc 3 Ap ed 320array of words 321.Pq Vt BN_ULONG , 322least significant word first. 323A 324.Vt BN_ULONG 325can be either 16, 32 or 64 bits in size, depending on the 'number of 326bits' 327.Pq Dv BITS2 328specified in 329.In openssl/bn.h . 330.Pp 331.Fa dmax 332is the size of the 333.Fa d 334array that has been allocated. 335.Fa top 336is the number of words being used, so for a value of 4, bn.d[0]=4 and 337bn.top=1. 338.Fa neg 339is 1 if the number is negative. 340When a 341.Vt BIGNUM 342is 0, the 343.Fa d 344field can be 345.Dv NULL 346and 347.Fa top 348== 0. 349.Pp 350.Fa flags 351is a bit field of flags which are defined in 352.In openssl/bn.h . 353The flags begin with 354.Dv BN_FLG_ . 355The macros 356.Fn BN_set_flags b n 357and 358.Fn BN_get_flags b n 359exist to enable or fetch flag(s) 360.Fa n 361from a 362.Vt BIGNUM 363structure 364.Fa b . 365.Pp 366Various routines in this library require the use of temporary 367.Vt BIGNUM 368variables during their execution. 369Since dynamic memory allocation to create 370.Vt BIGNUM Ns s 371is rather expensive when used in conjunction with repeated subroutine 372calls, the 373.Vt BN_CTX 374structure is used. 375This structure contains BN_CTX_NUM 376.Vt BIGNUM Ns s ; 377see 378.Xr BN_CTX_start 3 . 379.Ss Low level arithmetic operations 380These functions are implemented in C and for several platforms in 381assembly language: 382.Pp 383.Fn bn_mul_words rp ap num w 384operates on the 385.Fa num 386word arrays 387.Fa rp 388and 389.Fa ap . 390It computes 391.Fa ap 392* 393.Fa w , 394places the result in 395.Fa rp , 396and returns the high word (carry). 397.Pp 398.Fn bn_mul_add_words rp ap num w 399operates on the 400.Fa num 401word arrays 402.Fa rp 403and 404.Fa ap . 405It computes 406.Fa ap 407* 408.Fa w 409+ 410.Fa rp , 411places the result in 412.Fa rp , 413and returns the high word (carry). 414.Pp 415.Fn bn_sqr_words rp ap num 416operates on the 417.Fa num 418word array 419.Fa ap 420and the 421.Pf 2* Fa num 422word array 423.Fa ap . 424It computes 425.Fa ap 426* 427.Fa ap 428word-wise, and places the low and high bytes of the result in 429.Fa rp . 430.Pp 431.Fn bn_div_words h l d 432divides the two word number 433.Pq Fa h , Fa l 434by 435.Fa d 436and returns the result. 437.Pp 438.Fn bn_add_words rp ap bp num 439operates on the 440.Fa num 441word arrays 442.Fa ap , 443.Fa bp 444and 445.Fa rp . 446It computes 447.Fa ap 448+ 449.Fa bp , 450places the result in 451.Fa rp , 452and returns the high word (carry). 453.Pp 454.Fn bn_sub_words rp ap bp num 455operates on the 456.Fa num 457word arrays 458.Fa ap , 459.Fa bp 460and 461.Fa rp . 462It computes 463.Fa ap 464- 465.Fa bp , 466places the result in 467.Fa rp , 468and returns the carry (1 if 469.Fa bp 470\(ra 471.Fa ap , 4720 otherwise). 473.Pp 474.Fn bn_mul_comba4 r a b 475operates on the 4 word arrays 476.Fa a 477and 478.Fa b 479and the 8-word array 480.Fa r . 481It computes 482.Fa a Ns * Ns Fa b 483and places the result in 484.Fa r . 485.Pp 486.Fn bn_mul_comba8 r a b 487operates on the 8-word arrays 488.Fa a 489and 490.Fa b 491and the 16-word array 492.Fa r . 493It computes 494.Fa a Ns * Ns Fa b 495and places the result in 496.Fa r . 497.Pp 498.Fn bn_sqr_comba4 r a b 499operates on the 4-word arrays 500.Fa a 501and 502.Fa b 503and the 8-word array 504.Fa r . 505.Pp 506.Fn bn_sqr_comba8 r a b 507operates on the 8-word arrays 508.Fa a 509and 510.Fa b 511and the 16 word array 512.Fa r . 513.Pp 514The following functions are implemented in C: 515.Pp 516.Fn bn_cmp_words a b n 517operates on the 518.Fa n 519word arrays 520.Fa a 521and 522.Fa b . 523It returns 1, 0 and -1 if 524.Fa a 525is greater than, equal and less than 526.Fa b . 527.Pp 528.Fn bn_mul_normal r a na b nb 529operates on the 530.Fa na 531word array 532.Fa a , 533the 534.Fa nb 535word array 536.Fa b 537and the 538.Fa na Ns + Ns Fa nb 539word array 540.Fa r . 541It computes 542.Fa a Ns * Ns Fa b 543and places the result in 544.Fa r . 545.Pp 546.Fn bn_mul_low_normal r a b n 547operates on the 548.Fa n 549word arrays 550.Fa r , 551.Fa a 552and 553.Fa b . 554It computes the 555.Fa n 556low words of 557.Fa a Ns * Ns Fa b 558and places the result in 559.Fa r . 560.Pp 561.Fn bn_mul_recursive r a b n2 dna dnb t 562operates on the word arrays 563.Fa a 564and 565.Fa b 566of length 567.Fa n2 Ns + Ns Fa dna 568and 569.Fa n2 Ns + Ns Fa dnb 570.Pf ( Fa dna 571and 572.Fa dnb 573are currently allowed to be 0 or negative) and the 574.Pf 2* Fa n2 575word arrays 576.Fa r 577and 578.Sy t . 579.Fa n2 580must be a power of 2. 581It computes 582.Fa a Ns * Ns Fa b 583and places the result in 584.Fa r . 585.Pp 586.Fn bn_mul_part_recursive r a b n tna tnb tmp 587operates on the word arrays 588.Fa a 589and 590.Fa b 591of length 592.Fa n Ns + Ns Fa tna 593and 594.Fa n Ns + Ns Fa tnb 595and the 596.Pf 4* Fa n 597word arrays 598.Fa r 599and 600.Fa tmp . 601.Pp 602.Fn bn_mul_low_recursive r a b n2 tmp 603operates on the 604.Fa n2 605word arrays 606.Fa r 607and 608.Fa tmp 609and the 610.Fa n2 Ns /2 611word arrays 612.Fa a 613and 614.Fa b . 615.Pp 616.Fn bn_mul_high r a b l n2 tmp 617operates on the 618.Fa n2 619word arrays 620.Fa r , 621.Fa a , 622.Fa b 623and 624.Fa l 625(?) and the 626.Pf 3* Fa n2 627word array 628.Fa tmp . 629.Pp 630.Xr BN_mul 3 631calls 632.Fn bn_mul_normal , 633or an optimized implementation if the factors have the same size: 634.Fn bn_mul_comba8 635is used if they are 8 words long, 636.Fn bn_mul_recursive 637if they are larger than 638.Dv BN_MULL_SIZE_NORMAL 639and the size is an exact multiple of the word size, and 640.Fn bn_mul_part_recursive 641for others that are larger than 642.Dv BN_MULL_SIZE_NORMAL . 643.Pp 644.Fn bn_sqr_normal r a n tmp 645operates on the 646.Fa n 647word array 648.Fa a 649and the 650.Pf 2* Fa n 651word arrays 652.Fa tmp 653and 654.Fa r . 655.Pp 656The implementations use the following macros which, depending on the 657architecture, may use 658.Vt long long 659C operations or inline assembler. 660They are defined in 661.Pa bn_lcl.h . 662.Pp 663.Fn mul r a w c 664computes 665.Fa w Ns * Ns Fa a Ns + Ns Fa c 666and places the low word of the result in 667.Fa r 668and the high word in 669.Fa c . 670.Pp 671.Fn mul_add r a w c 672computes 673.Fa w Ns * Ns Fa a Ns + Ns Fa r Ns + Ns Fa c 674and places the low word of the result in 675.Fa r 676and the high word in 677.Fa c . 678.Pp 679.Fn sqr r0 r1 a 680computes 681.Fa a Ns * Ns Fa a 682and places the low word of the result in 683.Fa r0 684and the high word in 685.Fa r1 . 686.Ss Size changes 687.Fn bn_expand 688ensures that 689.Fa b 690has enough space for a 691.Fa bits 692bit number. 693.Fn bn_wexpand 694ensures that 695.Fa b 696has enough space for an 697.Fa n 698word number. 699If the number has to be expanded, both macros call 700.Fn bn_expand2 , 701which allocates a new 702.Fa d 703array and copies the data. 704They return 705.Dv NULL 706on error, 707.Fa b 708otherwise. 709.Pp 710The 711.Fn bn_fix_top 712macro reduces 713.Fa a Ns -> Ns Fa top 714to point to the most significant non-zero word plus one when 715.Fa a 716has shrunk. 717.Ss Debugging 718.Fn bn_check_top 719verifies that 720.Ql ((a)-\(ratop \(ra= 0 && (a)-\(ratop \(la= (a)-\(radmax) . 721A violation will cause the program to abort. 722.Pp 723.Fn bn_print 724prints 725.Fa a 726to 727.Dv stderr . 728.Fn bn_dump 729prints 730.Fa n 731words at 732.Fa d 733(in reverse order, i.e.\& 734most significant word first) to 735.Dv stderr . 736.Pp 737.Fn bn_set_max 738makes 739.Fa a 740a static number with a 741.Fa dmax 742of its current size. 743This is used by 744.Fn bn_set_low 745and 746.Fn bn_set_high 747to make 748.Fa r 749a read-only 750.Vt BIGNUM 751that contains the 752.Fa n 753low or high words of 754.Fa a . 755.Pp 756If 757.Dv BN_DEBUG 758is not defined, 759.Fn bn_check_top , 760.Fn bn_print , 761.Fn bn_dump 762and 763.Fn bn_set_max 764are defined as empty macros. 765.Sh SEE ALSO 766.Xr BN_new 3 767