1.\" $OpenBSD: BN_add.3,v 1.20 2023/04/27 09:47:03 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_simple , 99.\" .Nm BN_mod_exp2_mont r \(== (a1 ^ p1) * (a2 ^ p2) (mod m) 100.\" Maybe they should be deleted from <openssl/bn.h>. 101.Nm BN_gcd 102.Nd arithmetic operations on BIGNUMs 103.Sh SYNOPSIS 104.In openssl/bn.h 105.Ft int 106.Fo BN_add 107.Fa "BIGNUM *r" 108.Fa "const BIGNUM *a" 109.Fa "const BIGNUM *b" 110.Fc 111.Ft int 112.Fo BN_uadd 113.Fa "BIGNUM *r" 114.Fa "const BIGNUM *a" 115.Fa "const BIGNUM *b" 116.Fc 117.Ft int 118.Fo BN_sub 119.Fa "BIGNUM *r" 120.Fa "const BIGNUM *a" 121.Fa "const BIGNUM *b" 122.Fc 123.Ft int 124.Fo BN_usub 125.Fa "BIGNUM *r" 126.Fa "const BIGNUM *a" 127.Fa "const BIGNUM *b" 128.Fc 129.Ft int 130.Fo BN_mul 131.Fa "BIGNUM *r" 132.Fa "const BIGNUM *a" 133.Fa "const BIGNUM *b" 134.Fa "BN_CTX *ctx" 135.Fc 136.Ft int 137.Fo BN_sqr 138.Fa "BIGNUM *r" 139.Fa "const BIGNUM *a" 140.Fa "BN_CTX *ctx" 141.Fc 142.Ft int 143.Fo BN_div 144.Fa "BIGNUM *dv" 145.Fa "BIGNUM *rem" 146.Fa "const BIGNUM *a" 147.Fa "const BIGNUM *d" 148.Fa "BN_CTX *ctx" 149.Fc 150.Ft int 151.Fo BN_mod 152.Fa "BIGNUM *rem" 153.Fa "const BIGNUM *a" 154.Fa "const BIGNUM *m" 155.Fa "BN_CTX *ctx" 156.Fc 157.Ft int 158.Fo BN_nnmod 159.Fa "BIGNUM *r" 160.Fa "const BIGNUM *a" 161.Fa "const BIGNUM *m" 162.Fa "BN_CTX *ctx" 163.Fc 164.Ft int 165.Fo BN_mod_add 166.Fa "BIGNUM *r" 167.Fa "const BIGNUM *a" 168.Fa "const BIGNUM *b" 169.Fa "const BIGNUM *m" 170.Fa "BN_CTX *ctx" 171.Fc 172.Ft int 173.Fo BN_mod_add_quick 174.Fa "BIGNUM *r" 175.Fa "const BIGNUM *a" 176.Fa "const BIGNUM *b" 177.Fa "const BIGNUM *m" 178.Fc 179.Ft int 180.Fo BN_mod_sub 181.Fa "BIGNUM *r" 182.Fa "const BIGNUM *a" 183.Fa "const BIGNUM *b" 184.Fa "const BIGNUM *m" 185.Fa "BN_CTX *ctx" 186.Fc 187.Ft int 188.Fo BN_mod_sub_quick 189.Fa "BIGNUM *r" 190.Fa "const BIGNUM *a" 191.Fa "const BIGNUM *b" 192.Fa "const BIGNUM *m" 193.Fc 194.Ft int 195.Fo BN_mod_mul 196.Fa "BIGNUM *r" 197.Fa "const BIGNUM *a" 198.Fa "const BIGNUM *b" 199.Fa "const BIGNUM *m" 200.Fa "BN_CTX *ctx" 201.Fc 202.Ft int 203.Fo BN_mod_sqr 204.Fa "BIGNUM *r" 205.Fa "const BIGNUM *a" 206.Fa "const BIGNUM *m" 207.Fa "BN_CTX *ctx" 208.Fc 209.Ft int 210.Fo BN_mod_lshift 211.Fa "BIGNUM *r" 212.Fa "const BIGNUM *a" 213.Fa "int n" 214.Fa "const BIGNUM *m" 215.Fa "BN_CTX *ctx" 216.Fc 217.Ft int 218.Fo BN_mod_lshift_quick 219.Fa "BIGNUM *r" 220.Fa "const BIGNUM *a" 221.Fa "int n" 222.Fa "const BIGNUM *m" 223.Fc 224.Ft int 225.Fo BN_mod_lshift1 226.Fa "BIGNUM *r" 227.Fa "const BIGNUM *a" 228.Fa "const BIGNUM *m" 229.Fa "BN_CTX *ctx" 230.Fc 231.Ft int 232.Fo BN_mod_lshift1_quick 233.Fa "BIGNUM *r" 234.Fa "const BIGNUM *a" 235.Fa "const BIGNUM *m" 236.Fc 237.Ft int 238.Fo BN_exp 239.Fa "BIGNUM *r" 240.Fa "const BIGNUM *a" 241.Fa "const BIGNUM *p" 242.Fa "BN_CTX *ctx" 243.Fc 244.Ft int 245.Fo BN_mod_exp 246.Fa "BIGNUM *r" 247.Fa "const BIGNUM *a" 248.Fa "const BIGNUM *p" 249.Fa "const BIGNUM *m" 250.Fa "BN_CTX *ctx" 251.Fc 252.Ft int 253.Fo BN_gcd 254.Fa "BIGNUM *r" 255.Fa "const BIGNUM *a" 256.Fa "const BIGNUM *b" 257.Fa "BN_CTX *ctx" 258.Fc 259.Sh DESCRIPTION 260.Fn BN_add 261adds 262.Fa a 263and 264.Fa b 265and places the result in 266.Fa r 267.Pq Li r=a+b . 268.Fa r 269may be the same 270.Vt BIGNUM 271as 272.Fa a 273or 274.Fa b . 275.Pp 276.Fn BN_uadd 277adds the absolute values of 278.Fa a 279and 280.Fa b 281and places the result in 282.Fa r 283.Pq Li r=|a|+|b|\& . 284.Fa r 285may be the same 286.Vt BIGNUM 287as 288.Fa a 289or 290.Fa b . 291.Pp 292.Fn BN_sub 293subtracts 294.Fa b 295from 296.Fa a 297and places the result in 298.Fa r 299.Pq Li r=a-b . 300.Fa r 301may be the same 302.Vt BIGNUM 303as 304.Fa a 305or 306.Fa b . 307.Pp 308.Fn BN_usub 309subtracts the absolute value of 310.Fa b 311from the absolute value of 312.Fa a 313and places the result in 314.Fa r 315.Pq Li r=|a|-|b|\& . 316It requires the absolute value of 317.Fa a 318to be greater than the absolute value of 319.Fa b ; 320otherwise it will fail. 321.Fa r 322may be the same 323.Vt BIGNUM 324as 325.Fa a 326or 327.Fa b . 328.Pp 329.Fn BN_mul 330multiplies 331.Fa a 332and 333.Fa b 334and places the result in 335.Fa r 336.Pq Li r=a*b . 337.Fa r 338may be the same 339.Vt BIGNUM 340as 341.Fa a 342or 343.Fa b . 344For multiplication by powers of 2, use 345.Xr BN_lshift 3 . 346.Pp 347.Fn BN_sqr 348takes the square of 349.Fa a 350and places the result in 351.Fa r 352.Pq Li r=a^2 . 353.Fa r 354and 355.Fa a 356may be the same 357.Vt BIGNUM . 358This function is faster than 359.Fn BN_mul r a a . 360.Pp 361.Fn BN_div 362divides 363.Fa a 364by 365.Fa d 366and places the result in 367.Fa dv 368and the remainder in 369.Fa rem 370.Pq Li dv=a/d , rem=a%d . 371If the flag 372.Dv BN_FLG_CONSTTIME 373is set on 374.Fa a 375or 376.Fa d , 377it operates in constant time. 378Either of 379.Fa dv 380and 381.Fa rem 382may be 383.Dv NULL , 384in which case the respective value is not returned. 385The result is rounded towards zero; thus if 386.Fa a 387is negative, the remainder will be zero or negative. 388For division by powers of 2, use 389.Fn BN_rshift 3 . 390.Pp 391.Fn BN_mod 392corresponds to 393.Fn BN_div 394with 395.Fa dv 396set to 397.Dv NULL . 398It is implemented as a macro. 399.Pp 400.Fn BN_nnmod 401reduces 402.Fa a 403modulo 404.Fa m 405and places the non-negative remainder in 406.Fa r . 407.Pp 408.Fn BN_mod_add 409adds 410.Fa a 411to 412.Fa b 413modulo 414.Fa m 415and places the non-negative result in 416.Fa r . 417.Pp 418.Fn BN_mod_add_quick 419is a variant of 420.Fn BN_mod_add 421that requires 422.Fa a 423and 424.Fa b 425to both be non-negative and smaller than 426.Fa m . 427If any of these constraints are violated, 428it silently produces wrong results. 429.Pp 430.Fn BN_mod_sub 431subtracts 432.Fa b 433from 434.Fa a 435modulo 436.Fa m 437and places the non-negative result in 438.Fa r . 439.Pp 440.Fn BN_mod_sub_quick 441is a variant of 442.Fn BN_mod_sub 443that requires 444.Fa a 445and 446.Fa b 447to both be non-negative and smaller than 448.Fa m . 449If any of these constraints are violated, 450it silently produces wrong results. 451.Pp 452.Fn BN_mod_mul 453multiplies 454.Fa a 455by 456.Fa b 457and finds the non-negative remainder respective to modulus 458.Fa m 459.Pq Li r=(a*b)%m . 460.Fa r 461may be the same 462.Vt BIGNUM 463as 464.Fa a 465or 466.Fa b . 467For a more efficient algorithm for repeated computations using the same 468modulus, see 469.Xr BN_mod_mul_montgomery 3 . 470.Pp 471.Fn BN_mod_sqr 472takes the square of 473.Fa a 474modulo 475.Fa m 476and places the result in 477.Fa r . 478.Pp 479.Fn BN_mod_lshift 480shifts 481.Fa a 482left by 483.Fa n 484bits, reduces the result modulo 485.Fa m , 486and places the non-negative remainder in 487.Fa r 488.Pq Li r=a*2^n mod m . 489.Pp 490.Fn BN_mod_lshift1 491shifts 492.Fa a 493left by one bit, reduces the result modulo 494.Fa m , 495and places the non-negative remainder in 496.Fa r 497.Pq Li r=a*2 mod m . 498.Pp 499.Fn BN_mod_lshift_quick 500and 501.Fn BN_mod_lshift1_quick 502are variants of 503.Fn BN_mod_lshift 504and 505.Fn BN_mod_lshift1 , 506respectively, that require 507.Fa a 508to be non-negative and less than 509.Fa m . 510If either of these constraints is violated, they sometimes fail 511and sometimes silently produce wrong results. 512.Pp 513.Fn BN_exp 514raises 515.Fa a 516to the 517.Fa p Ns -th 518power and places the result in 519.Fa r 520.Pq Li r=a^p . 521This function is faster than repeated applications of 522.Fn BN_mul . 523.Pp 524.Fn BN_mod_exp 525computes 526.Fa a 527to the 528.Fa p Ns -th 529power modulo 530.Fa m 531.Pq Li r=(a^p)%m . 532If the flag 533.Dv BN_FLG_CONSTTIME 534is set on 535.Fa p , 536it operates in constant time. 537This function uses less time and space than 538.Fn BN_exp . 539.Pp 540.Fn BN_gcd 541computes the greatest common divisor of 542.Fa a 543and 544.Fa b 545and places the result in 546.Fa r . 547.Fa r 548may be the same 549.Vt BIGNUM 550as 551.Fa a 552or 553.Fa b . 554.Pp 555For all functions, 556.Fa ctx 557is a previously allocated 558.Vt BN_CTX 559used for temporary variables; see 560.Xr BN_CTX_new 3 . 561.Pp 562Unless noted otherwise, the result 563.Vt BIGNUM 564must be different from the arguments. 565.Sh RETURN VALUES 566For all functions, 1 is returned for success, 0 on error. 567The return value should always be checked, for example: 568.Pp 569.Dl if (!BN_add(r,a,b)) goto err; 570.Pp 571The error codes can be obtained by 572.Xr ERR_get_error 3 . 573.Sh SEE ALSO 574.Xr BN_add_word 3 , 575.Xr BN_CTX_new 3 , 576.Xr BN_new 3 , 577.Xr BN_set_bit 3 , 578.Xr BN_set_flags 3 , 579.Xr BN_set_negative 3 580.Sh HISTORY 581.Fn BN_add , 582.Fn BN_sub , 583.Fn BN_mul , 584.Fn BN_sqr , 585.Fn BN_div , 586.Fn BN_mod , 587.Fn BN_mod_mul , 588.Fn BN_mod_exp , 589and 590.Fn BN_gcd 591first appeared in SSLeay 0.5.1. 592.Fn BN_exp 593first appeared in SSLeay 0.9.0. 594All these functions have been available since 595.Ox 2.4 . 596.Pp 597.Fn BN_uadd , 598.Fn BN_usub , 599and the 600.Fa ctx 601argument to 602.Fn BN_mul 603first appeared in SSLeay 0.9.1 and have been available since 604.Ox 2.6 . 605.Pp 606.Fn BN_nnmod , 607.Fn BN_mod_add , 608.Fn BN_mod_add_quick , 609.Fn BN_mod_sub , 610.Fn BN_mod_sub_quick , 611.Fn BN_mod_sqr , 612.Fn BN_mod_lshift , 613.Fn BN_mod_lshift_quick , 614.Fn BN_mod_lshift1 , 615and 616.Fn BN_mod_lshift1_quick 617first appeared in OpenSSL 0.9.7 and have been available since 618.Ox 3.2 . 619.Sh BUGS 620Even if the 621.Dv BN_FLG_CONSTTIME 622flag is set on 623.Fa a 624or 625.Fa b , 626.Fn BN_gcd 627neither fails nor operates in constant time, potentially allowing 628timing side-channel attacks. 629.Pp 630Even if the 631.Dv BN_FLG_CONSTTIME 632flag is set on 633.Fa p , 634if the modulus 635.Fa m 636is even, 637.Fn BN_mod_exp 638does not operate in constant time, potentially allowing 639timing side-channel attacks. 640.Pp 641If 642.Dv BN_FLG_CONSTTIME 643is set on 644.Fa p , 645.Fn BN_exp 646fails instead of operating in constant time. 647