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