1.\" $OpenBSD: BN_add.3,v 1.19 2023/04/27 09:45:56 tb 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: April 27 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 a more efficient algorithm for repeated computations using the same 469modulus, see 470.Xr BN_mod_mul_montgomery 3 . 471.Pp 472.Fn BN_mod_sqr 473takes the square of 474.Fa a 475modulo 476.Fa m 477and places the result in 478.Fa r . 479.Pp 480.Fn BN_mod_lshift 481shifts 482.Fa a 483left by 484.Fa n 485bits, reduces the result modulo 486.Fa m , 487and places the non-negative remainder in 488.Fa r 489.Pq Li r=a*2^n mod m . 490.Pp 491.Fn BN_mod_lshift1 492shifts 493.Fa a 494left by one bit, reduces the result modulo 495.Fa m , 496and places the non-negative remainder in 497.Fa r 498.Pq Li r=a*2 mod m . 499.Pp 500.Fn BN_mod_lshift_quick 501and 502.Fn BN_mod_lshift1_quick 503are variants of 504.Fn BN_mod_lshift 505and 506.Fn BN_mod_lshift1 , 507respectively, that require 508.Fa a 509to be non-negative and less than 510.Fa m . 511If either of these constraints is violated, they sometimes fail 512and sometimes silently produce wrong results. 513.Pp 514.Fn BN_exp 515raises 516.Fa a 517to the 518.Fa p Ns -th 519power and places the result in 520.Fa r 521.Pq Li r=a^p . 522This function is faster than repeated applications of 523.Fn BN_mul . 524.Pp 525.Fn BN_mod_exp 526computes 527.Fa a 528to the 529.Fa p Ns -th 530power modulo 531.Fa m 532.Pq Li r=(a^p)%m . 533If the flag 534.Dv BN_FLG_CONSTTIME 535is set on 536.Fa p , 537it operates in constant time. 538This function uses less time and space than 539.Fn BN_exp . 540.Pp 541.Fn BN_gcd 542computes the greatest common divisor of 543.Fa a 544and 545.Fa b 546and places the result in 547.Fa r . 548.Fa r 549may be the same 550.Vt BIGNUM 551as 552.Fa a 553or 554.Fa b . 555.Pp 556For all functions, 557.Fa ctx 558is a previously allocated 559.Vt BN_CTX 560used for temporary variables; see 561.Xr BN_CTX_new 3 . 562.Pp 563Unless noted otherwise, the result 564.Vt BIGNUM 565must be different from the arguments. 566.Sh RETURN VALUES 567For all functions, 1 is returned for success, 0 on error. 568The return value should always be checked, for example: 569.Pp 570.Dl if (!BN_add(r,a,b)) goto err; 571.Pp 572The error codes can be obtained by 573.Xr ERR_get_error 3 . 574.Sh SEE ALSO 575.Xr BN_add_word 3 , 576.Xr BN_CTX_new 3 , 577.Xr BN_new 3 , 578.Xr BN_set_bit 3 , 579.Xr BN_set_flags 3 , 580.Xr BN_set_negative 3 581.Sh HISTORY 582.Fn BN_add , 583.Fn BN_sub , 584.Fn BN_mul , 585.Fn BN_sqr , 586.Fn BN_div , 587.Fn BN_mod , 588.Fn BN_mod_mul , 589.Fn BN_mod_exp , 590and 591.Fn BN_gcd 592first appeared in SSLeay 0.5.1. 593.Fn BN_exp 594first appeared in SSLeay 0.9.0. 595All these functions have been available since 596.Ox 2.4 . 597.Pp 598.Fn BN_uadd , 599.Fn BN_usub , 600and the 601.Fa ctx 602argument to 603.Fn BN_mul 604first appeared in SSLeay 0.9.1 and have been available since 605.Ox 2.6 . 606.Pp 607.Fn BN_nnmod , 608.Fn BN_mod_add , 609.Fn BN_mod_add_quick , 610.Fn BN_mod_sub , 611.Fn BN_mod_sub_quick , 612.Fn BN_mod_sqr , 613.Fn BN_mod_lshift , 614.Fn BN_mod_lshift_quick , 615.Fn BN_mod_lshift1 , 616and 617.Fn BN_mod_lshift1_quick 618first appeared in OpenSSL 0.9.7 and have been available since 619.Ox 3.2 . 620.Sh BUGS 621Even if the 622.Dv BN_FLG_CONSTTIME 623flag is set on 624.Fa a 625or 626.Fa b , 627.Fn BN_gcd 628neither fails nor operates in constant time, potentially allowing 629timing side-channel attacks. 630.Pp 631Even if the 632.Dv BN_FLG_CONSTTIME 633flag is set on 634.Fa p , 635if the modulus 636.Fa m 637is even, 638.Fn BN_mod_exp 639does not operate in constant time, potentially allowing 640timing side-channel attacks. 641.Pp 642If 643.Dv BN_FLG_CONSTTIME 644is set on 645.Fa p , 646.Fn BN_exp 647fails instead of operating in constant time. 648