1.\" $OpenBSD: BN_add.3,v 1.18 2023/01/31 05:16:52 jsing Exp $ 2.\" full merge up to: OpenSSL e9b77246 Jan 20 19:58:49 2017 +0100 3.\" 4.\" This file is a derived work. 5.\" The changes are covered by the following Copyright and license: 6.\" 7.\" Copyright (c) 2021 Ingo Schwarze <schwarze@openbsd.org> 8.\" 9.\" Permission to use, copy, modify, and distribute this software for any 10.\" purpose with or without fee is hereby granted, provided that the above 11.\" copyright notice and this permission notice appear in all copies. 12.\" 13.\" THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 14.\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 15.\" MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 16.\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 17.\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 18.\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 19.\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 20.\" 21.\" The original file was written by Ulf Moeller <ulf@openssl.org> 22.\" and Bodo Moeller <bodo@openssl.org>. 23.\" Copyright (c) 2000, 2015 The OpenSSL Project. All rights reserved. 24.\" 25.\" Redistribution and use in source and binary forms, with or without 26.\" modification, are permitted provided that the following conditions 27.\" are met: 28.\" 29.\" 1. Redistributions of source code must retain the above copyright 30.\" notice, this list of conditions and the following disclaimer. 31.\" 32.\" 2. Redistributions in binary form must reproduce the above copyright 33.\" notice, this list of conditions and the following disclaimer in 34.\" the documentation and/or other materials provided with the 35.\" distribution. 36.\" 37.\" 3. All advertising materials mentioning features or use of this 38.\" software must display the following acknowledgment: 39.\" "This product includes software developed by the OpenSSL Project 40.\" for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 41.\" 42.\" 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 43.\" endorse or promote products derived from this software without 44.\" prior written permission. For written permission, please contact 45.\" openssl-core@openssl.org. 46.\" 47.\" 5. Products derived from this software may not be called "OpenSSL" 48.\" nor may "OpenSSL" appear in their names without prior written 49.\" permission of the OpenSSL Project. 50.\" 51.\" 6. Redistributions of any form whatsoever must retain the following 52.\" acknowledgment: 53.\" "This product includes software developed by the OpenSSL Project 54.\" for use in the OpenSSL Toolkit (http://www.openssl.org/)" 55.\" 56.\" THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 57.\" EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 58.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 59.\" PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 60.\" ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 61.\" SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 62.\" NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 63.\" LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 64.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 65.\" STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 66.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 67.\" OF THE POSSIBILITY OF SUCH DAMAGE. 68.\" 69.Dd $Mdocdate: January 31 2023 $ 70.Dt BN_ADD 3 71.Os 72.Sh NAME 73.Nm BN_add , 74.Nm BN_uadd , 75.Nm BN_sub , 76.Nm BN_usub , 77.Nm BN_mul , 78.Nm BN_sqr , 79.Nm BN_div , 80.Nm BN_mod , 81.Nm BN_nnmod , 82.Nm BN_mod_add , 83.Nm BN_mod_add_quick , 84.Nm BN_mod_sub , 85.Nm BN_mod_sub_quick , 86.Nm BN_mod_mul , 87.Nm BN_mod_sqr , 88.Nm BN_mod_lshift , 89.Nm BN_mod_lshift_quick , 90.Nm BN_mod_lshift1 , 91.Nm BN_mod_lshift1_quick , 92.Nm BN_exp , 93.Nm BN_mod_exp , 94.\" The following are public, but intentionally undocumented for now: 95.\" .Nm BN_mod_exp_mont , r \(== a ^ p (mod m) 96.\" .Nm BN_mod_exp_mont_consttime , 97.\" .Nm BN_mod_exp_mont_word , 98.\" .Nm BN_mod_exp_recp , 99.\" .Nm BN_mod_exp_simple , 100.\" .Nm BN_mod_exp2_mont r \(== (a1 ^ p1) * (a2 ^ p2) (mod m) 101.\" Maybe they should be deleted from <openssl/bn.h>. 102.Nm BN_gcd 103.Nd arithmetic operations on BIGNUMs 104.Sh SYNOPSIS 105.In openssl/bn.h 106.Ft int 107.Fo BN_add 108.Fa "BIGNUM *r" 109.Fa "const BIGNUM *a" 110.Fa "const BIGNUM *b" 111.Fc 112.Ft int 113.Fo BN_uadd 114.Fa "BIGNUM *r" 115.Fa "const BIGNUM *a" 116.Fa "const BIGNUM *b" 117.Fc 118.Ft int 119.Fo BN_sub 120.Fa "BIGNUM *r" 121.Fa "const BIGNUM *a" 122.Fa "const BIGNUM *b" 123.Fc 124.Ft int 125.Fo BN_usub 126.Fa "BIGNUM *r" 127.Fa "const BIGNUM *a" 128.Fa "const BIGNUM *b" 129.Fc 130.Ft int 131.Fo BN_mul 132.Fa "BIGNUM *r" 133.Fa "const BIGNUM *a" 134.Fa "const BIGNUM *b" 135.Fa "BN_CTX *ctx" 136.Fc 137.Ft int 138.Fo BN_sqr 139.Fa "BIGNUM *r" 140.Fa "const BIGNUM *a" 141.Fa "BN_CTX *ctx" 142.Fc 143.Ft int 144.Fo BN_div 145.Fa "BIGNUM *dv" 146.Fa "BIGNUM *rem" 147.Fa "const BIGNUM *a" 148.Fa "const BIGNUM *d" 149.Fa "BN_CTX *ctx" 150.Fc 151.Ft int 152.Fo BN_mod 153.Fa "BIGNUM *rem" 154.Fa "const BIGNUM *a" 155.Fa "const BIGNUM *m" 156.Fa "BN_CTX *ctx" 157.Fc 158.Ft int 159.Fo BN_nnmod 160.Fa "BIGNUM *r" 161.Fa "const BIGNUM *a" 162.Fa "const BIGNUM *m" 163.Fa "BN_CTX *ctx" 164.Fc 165.Ft int 166.Fo BN_mod_add 167.Fa "BIGNUM *r" 168.Fa "const BIGNUM *a" 169.Fa "const BIGNUM *b" 170.Fa "const BIGNUM *m" 171.Fa "BN_CTX *ctx" 172.Fc 173.Ft int 174.Fo BN_mod_add_quick 175.Fa "BIGNUM *r" 176.Fa "const BIGNUM *a" 177.Fa "const BIGNUM *b" 178.Fa "const BIGNUM *m" 179.Fc 180.Ft int 181.Fo BN_mod_sub 182.Fa "BIGNUM *r" 183.Fa "const BIGNUM *a" 184.Fa "const BIGNUM *b" 185.Fa "const BIGNUM *m" 186.Fa "BN_CTX *ctx" 187.Fc 188.Ft int 189.Fo BN_mod_sub_quick 190.Fa "BIGNUM *r" 191.Fa "const BIGNUM *a" 192.Fa "const BIGNUM *b" 193.Fa "const BIGNUM *m" 194.Fc 195.Ft int 196.Fo BN_mod_mul 197.Fa "BIGNUM *r" 198.Fa "const BIGNUM *a" 199.Fa "const BIGNUM *b" 200.Fa "const BIGNUM *m" 201.Fa "BN_CTX *ctx" 202.Fc 203.Ft int 204.Fo BN_mod_sqr 205.Fa "BIGNUM *r" 206.Fa "const BIGNUM *a" 207.Fa "const BIGNUM *m" 208.Fa "BN_CTX *ctx" 209.Fc 210.Ft int 211.Fo BN_mod_lshift 212.Fa "BIGNUM *r" 213.Fa "const BIGNUM *a" 214.Fa "int n" 215.Fa "const BIGNUM *m" 216.Fa "BN_CTX *ctx" 217.Fc 218.Ft int 219.Fo BN_mod_lshift_quick 220.Fa "BIGNUM *r" 221.Fa "const BIGNUM *a" 222.Fa "int n" 223.Fa "const BIGNUM *m" 224.Fc 225.Ft int 226.Fo BN_mod_lshift1 227.Fa "BIGNUM *r" 228.Fa "const BIGNUM *a" 229.Fa "const BIGNUM *m" 230.Fa "BN_CTX *ctx" 231.Fc 232.Ft int 233.Fo BN_mod_lshift1_quick 234.Fa "BIGNUM *r" 235.Fa "const BIGNUM *a" 236.Fa "const BIGNUM *m" 237.Fc 238.Ft int 239.Fo BN_exp 240.Fa "BIGNUM *r" 241.Fa "const BIGNUM *a" 242.Fa "const BIGNUM *p" 243.Fa "BN_CTX *ctx" 244.Fc 245.Ft int 246.Fo BN_mod_exp 247.Fa "BIGNUM *r" 248.Fa "const BIGNUM *a" 249.Fa "const BIGNUM *p" 250.Fa "const BIGNUM *m" 251.Fa "BN_CTX *ctx" 252.Fc 253.Ft int 254.Fo BN_gcd 255.Fa "BIGNUM *r" 256.Fa "const BIGNUM *a" 257.Fa "const BIGNUM *b" 258.Fa "BN_CTX *ctx" 259.Fc 260.Sh DESCRIPTION 261.Fn BN_add 262adds 263.Fa a 264and 265.Fa b 266and places the result in 267.Fa r 268.Pq Li r=a+b . 269.Fa r 270may be the same 271.Vt BIGNUM 272as 273.Fa a 274or 275.Fa b . 276.Pp 277.Fn BN_uadd 278adds the absolute values of 279.Fa a 280and 281.Fa b 282and places the result in 283.Fa r 284.Pq Li r=|a|+|b|\& . 285.Fa r 286may be the same 287.Vt BIGNUM 288as 289.Fa a 290or 291.Fa b . 292.Pp 293.Fn BN_sub 294subtracts 295.Fa b 296from 297.Fa a 298and places the result in 299.Fa r 300.Pq Li r=a-b . 301.Fa r 302may be the same 303.Vt BIGNUM 304as 305.Fa a 306or 307.Fa b . 308.Pp 309.Fn BN_usub 310subtracts the absolute value of 311.Fa b 312from the absolute value of 313.Fa a 314and places the result in 315.Fa r 316.Pq Li r=|a|-|b|\& . 317It requires the absolute value of 318.Fa a 319to be greater than the absolute value of 320.Fa b ; 321otherwise it will fail. 322.Fa r 323may be the same 324.Vt BIGNUM 325as 326.Fa a 327or 328.Fa b . 329.Pp 330.Fn BN_mul 331multiplies 332.Fa a 333and 334.Fa b 335and places the result in 336.Fa r 337.Pq Li r=a*b . 338.Fa r 339may be the same 340.Vt BIGNUM 341as 342.Fa a 343or 344.Fa b . 345For multiplication by powers of 2, use 346.Xr BN_lshift 3 . 347.Pp 348.Fn BN_sqr 349takes the square of 350.Fa a 351and places the result in 352.Fa r 353.Pq Li r=a^2 . 354.Fa r 355and 356.Fa a 357may be the same 358.Vt BIGNUM . 359This function is faster than 360.Fn BN_mul r a a . 361.Pp 362.Fn BN_div 363divides 364.Fa a 365by 366.Fa d 367and places the result in 368.Fa dv 369and the remainder in 370.Fa rem 371.Pq Li dv=a/d , rem=a%d . 372If the flag 373.Dv BN_FLG_CONSTTIME 374is set on 375.Fa a 376or 377.Fa d , 378it operates in constant time. 379Either of 380.Fa dv 381and 382.Fa rem 383may be 384.Dv NULL , 385in which case the respective value is not returned. 386The result is rounded towards zero; thus if 387.Fa a 388is negative, the remainder will be zero or negative. 389For division by powers of 2, use 390.Fn BN_rshift 3 . 391.Pp 392.Fn BN_mod 393corresponds to 394.Fn BN_div 395with 396.Fa dv 397set to 398.Dv NULL . 399It is implemented as a macro. 400.Pp 401.Fn BN_nnmod 402reduces 403.Fa a 404modulo 405.Fa m 406and places the non-negative remainder in 407.Fa r . 408.Pp 409.Fn BN_mod_add 410adds 411.Fa a 412to 413.Fa b 414modulo 415.Fa m 416and places the non-negative result in 417.Fa r . 418.Pp 419.Fn BN_mod_add_quick 420is a variant of 421.Fn BN_mod_add 422that requires 423.Fa a 424and 425.Fa b 426to both be non-negative and smaller than 427.Fa m . 428If any of these constraints are violated, 429it silently produces wrong results. 430.Pp 431.Fn BN_mod_sub 432subtracts 433.Fa b 434from 435.Fa a 436modulo 437.Fa m 438and places the non-negative result in 439.Fa r . 440.Pp 441.Fn BN_mod_sub_quick 442is a variant of 443.Fn BN_mod_sub 444that requires 445.Fa a 446and 447.Fa b 448to both be non-negative and smaller than 449.Fa m . 450If any of these constraints are violated, 451it silently produces wrong results. 452.Pp 453.Fn BN_mod_mul 454multiplies 455.Fa a 456by 457.Fa b 458and finds the non-negative remainder respective to modulus 459.Fa m 460.Pq Li r=(a*b)%m . 461.Fa r 462may be the same 463.Vt BIGNUM 464as 465.Fa a 466or 467.Fa b . 468For more efficient algorithms for repeated computations using the same 469modulus, see 470.Xr BN_mod_mul_montgomery 3 471and 472.Xr BN_mod_mul_reciprocal 3 . 473.Pp 474.Fn BN_mod_sqr 475takes the square of 476.Fa a 477modulo 478.Fa m 479and places the result in 480.Fa r . 481.Pp 482.Fn BN_mod_lshift 483shifts 484.Fa a 485left by 486.Fa n 487bits, reduces the result modulo 488.Fa m , 489and places the non-negative remainder in 490.Fa r 491.Pq Li r=a*2^n mod m . 492.Pp 493.Fn BN_mod_lshift1 494shifts 495.Fa a 496left by one bit, reduces the result modulo 497.Fa m , 498and places the non-negative remainder in 499.Fa r 500.Pq Li r=a*2 mod m . 501.Pp 502.Fn BN_mod_lshift_quick 503and 504.Fn BN_mod_lshift1_quick 505are variants of 506.Fn BN_mod_lshift 507and 508.Fn BN_mod_lshift1 , 509respectively, that require 510.Fa a 511to be non-negative and less than 512.Fa m . 513If either of these constraints is violated, they sometimes fail 514and sometimes silently produce wrong results. 515.Pp 516.Fn BN_exp 517raises 518.Fa a 519to the 520.Fa p Ns -th 521power and places the result in 522.Fa r 523.Pq Li r=a^p . 524This function is faster than repeated applications of 525.Fn BN_mul . 526.Pp 527.Fn BN_mod_exp 528computes 529.Fa a 530to the 531.Fa p Ns -th 532power modulo 533.Fa m 534.Pq Li r=(a^p)%m . 535If the flag 536.Dv BN_FLG_CONSTTIME 537is set on 538.Fa p , 539it operates in constant time. 540This function uses less time and space than 541.Fn BN_exp . 542.Pp 543.Fn BN_gcd 544computes the greatest common divisor of 545.Fa a 546and 547.Fa b 548and places the result in 549.Fa r . 550.Fa r 551may be the same 552.Vt BIGNUM 553as 554.Fa a 555or 556.Fa b . 557.Pp 558For all functions, 559.Fa ctx 560is a previously allocated 561.Vt BN_CTX 562used for temporary variables; see 563.Xr BN_CTX_new 3 . 564.Pp 565Unless noted otherwise, the result 566.Vt BIGNUM 567must be different from the arguments. 568.Sh RETURN VALUES 569For all functions, 1 is returned for success, 0 on error. 570The return value should always be checked, for example: 571.Pp 572.Dl if (!BN_add(r,a,b)) goto err; 573.Pp 574The error codes can be obtained by 575.Xr ERR_get_error 3 . 576.Sh SEE ALSO 577.Xr BN_add_word 3 , 578.Xr BN_CTX_new 3 , 579.Xr BN_new 3 , 580.Xr BN_set_bit 3 , 581.Xr BN_set_flags 3 , 582.Xr BN_set_negative 3 583.Sh HISTORY 584.Fn BN_add , 585.Fn BN_sub , 586.Fn BN_mul , 587.Fn BN_sqr , 588.Fn BN_div , 589.Fn BN_mod , 590.Fn BN_mod_mul , 591.Fn BN_mod_exp , 592and 593.Fn BN_gcd 594first appeared in SSLeay 0.5.1. 595.Fn BN_exp 596first appeared in SSLeay 0.9.0. 597All these functions have been available since 598.Ox 2.4 . 599.Pp 600.Fn BN_uadd , 601.Fn BN_usub , 602and the 603.Fa ctx 604argument to 605.Fn BN_mul 606first appeared in SSLeay 0.9.1 and have been available since 607.Ox 2.6 . 608.Pp 609.Fn BN_nnmod , 610.Fn BN_mod_add , 611.Fn BN_mod_add_quick , 612.Fn BN_mod_sub , 613.Fn BN_mod_sub_quick , 614.Fn BN_mod_sqr , 615.Fn BN_mod_lshift , 616.Fn BN_mod_lshift_quick , 617.Fn BN_mod_lshift1 , 618and 619.Fn BN_mod_lshift1_quick 620first appeared in OpenSSL 0.9.7 and have been available since 621.Ox 3.2 . 622.Sh BUGS 623Even if the 624.Dv BN_FLG_CONSTTIME 625flag is set on 626.Fa a 627or 628.Fa b , 629.Fn BN_gcd 630neither fails nor operates in constant time, potentially allowing 631timing side-channel attacks. 632.Pp 633Even if the 634.Dv BN_FLG_CONSTTIME 635flag is set on 636.Fa p , 637if the modulus 638.Fa m 639is even, 640.Fn BN_mod_exp 641does not operate in constant time, potentially allowing 642timing side-channel attacks. 643.Pp 644If 645.Dv BN_FLG_CONSTTIME 646is set on 647.Fa p , 648.Fn BN_exp 649fails instead of operating in constant time. 650