1.\" $OpenBSD: BN_add.3,v 1.17 2022/11/16 14:19:22 schwarze 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: November 16 2022 $ 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 sometimes fail 322and sometimes silently produce wrong results. 323.Fa r 324may be the same 325.Vt BIGNUM 326as 327.Fa a 328or 329.Fa b . 330.Pp 331.Fn BN_mul 332multiplies 333.Fa a 334and 335.Fa b 336and places the result in 337.Fa r 338.Pq Li r=a*b . 339.Fa r 340may be the same 341.Vt BIGNUM 342as 343.Fa a 344or 345.Fa b . 346For multiplication by powers of 2, use 347.Xr BN_lshift 3 . 348.Pp 349.Fn BN_sqr 350takes the square of 351.Fa a 352and places the result in 353.Fa r 354.Pq Li r=a^2 . 355.Fa r 356and 357.Fa a 358may be the same 359.Vt BIGNUM . 360This function is faster than 361.Fn BN_mul r a a . 362.Pp 363.Fn BN_div 364divides 365.Fa a 366by 367.Fa d 368and places the result in 369.Fa dv 370and the remainder in 371.Fa rem 372.Pq Li dv=a/d , rem=a%d . 373If the flag 374.Dv BN_FLG_CONSTTIME 375is set on 376.Fa a 377or 378.Fa d , 379it operates in constant time. 380Either of 381.Fa dv 382and 383.Fa rem 384may be 385.Dv NULL , 386in which case the respective value is not returned. 387The result is rounded towards zero; thus if 388.Fa a 389is negative, the remainder will be zero or negative. 390For division by powers of 2, use 391.Fn BN_rshift 3 . 392.Pp 393.Fn BN_mod 394corresponds to 395.Fn BN_div 396with 397.Fa dv 398set to 399.Dv NULL . 400It is implemented as a macro. 401.Pp 402.Fn BN_nnmod 403reduces 404.Fa a 405modulo 406.Fa m 407and places the non-negative remainder in 408.Fa r . 409.Pp 410.Fn BN_mod_add 411adds 412.Fa a 413to 414.Fa b 415modulo 416.Fa m 417and places the non-negative result in 418.Fa r . 419.Pp 420.Fn BN_mod_add_quick 421is a variant of 422.Fn BN_mod_add 423that requires 424.Fa a 425and 426.Fa b 427to both be non-negative and smaller than 428.Fa m . 429If any of these constraints are violated, 430it silently produces wrong results. 431.Pp 432.Fn BN_mod_sub 433subtracts 434.Fa b 435from 436.Fa a 437modulo 438.Fa m 439and places the non-negative result in 440.Fa r . 441.Pp 442.Fn BN_mod_sub_quick 443is a variant of 444.Fn BN_mod_sub 445that requires 446.Fa a 447and 448.Fa b 449to both be non-negative and smaller than 450.Fa m . 451If any of these constraints are violated, 452it silently produces wrong results. 453.Pp 454.Fn BN_mod_mul 455multiplies 456.Fa a 457by 458.Fa b 459and finds the non-negative remainder respective to modulus 460.Fa m 461.Pq Li r=(a*b)%m . 462.Fa r 463may be the same 464.Vt BIGNUM 465as 466.Fa a 467or 468.Fa b . 469For more efficient algorithms for repeated computations using the same 470modulus, see 471.Xr BN_mod_mul_montgomery 3 472and 473.Xr BN_mod_mul_reciprocal 3 . 474.Pp 475.Fn BN_mod_sqr 476takes the square of 477.Fa a 478modulo 479.Fa m 480and places the result in 481.Fa r . 482.Pp 483.Fn BN_mod_lshift 484shifts 485.Fa a 486left by 487.Fa n 488bits, reduces the result modulo 489.Fa m , 490and places the non-negative remainder in 491.Fa r 492.Pq Li r=a*2^n mod m . 493.Pp 494.Fn BN_mod_lshift1 495shifts 496.Fa a 497left by one bit, reduces the result modulo 498.Fa m , 499and places the non-negative remainder in 500.Fa r 501.Pq Li r=a*2 mod m . 502.Pp 503.Fn BN_mod_lshift_quick 504and 505.Fn BN_mod_lshift1_quick 506are variants of 507.Fn BN_mod_lshift 508and 509.Fn BN_mod_lshift1 , 510respectively, that require 511.Fa a 512to be non-negative and less than 513.Fa m . 514If either of these constraints is violated, they sometimes fail 515and sometimes silently produce wrong results. 516.Pp 517.Fn BN_exp 518raises 519.Fa a 520to the 521.Fa p Ns -th 522power and places the result in 523.Fa r 524.Pq Li r=a^p . 525This function is faster than repeated applications of 526.Fn BN_mul . 527.Pp 528.Fn BN_mod_exp 529computes 530.Fa a 531to the 532.Fa p Ns -th 533power modulo 534.Fa m 535.Pq Li r=(a^p)%m . 536If the flag 537.Dv BN_FLG_CONSTTIME 538is set on 539.Fa p , 540it operates in constant time. 541This function uses less time and space than 542.Fn BN_exp . 543.Pp 544.Fn BN_gcd 545computes the greatest common divisor of 546.Fa a 547and 548.Fa b 549and places the result in 550.Fa r . 551.Fa r 552may be the same 553.Vt BIGNUM 554as 555.Fa a 556or 557.Fa b . 558.Pp 559For all functions, 560.Fa ctx 561is a previously allocated 562.Vt BN_CTX 563used for temporary variables; see 564.Xr BN_CTX_new 3 . 565.Pp 566Unless noted otherwise, the result 567.Vt BIGNUM 568must be different from the arguments. 569.Sh RETURN VALUES 570For all functions, 1 is returned for success, 0 on error. 571The return value should always be checked, for example: 572.Pp 573.Dl if (!BN_add(r,a,b)) goto err; 574.Pp 575The error codes can be obtained by 576.Xr ERR_get_error 3 . 577.Sh SEE ALSO 578.Xr BN_add_word 3 , 579.Xr BN_CTX_new 3 , 580.Xr BN_new 3 , 581.Xr BN_set_bit 3 , 582.Xr BN_set_flags 3 , 583.Xr BN_set_negative 3 584.Sh HISTORY 585.Fn BN_add , 586.Fn BN_sub , 587.Fn BN_mul , 588.Fn BN_sqr , 589.Fn BN_div , 590.Fn BN_mod , 591.Fn BN_mod_mul , 592.Fn BN_mod_exp , 593and 594.Fn BN_gcd 595first appeared in SSLeay 0.5.1. 596.Fn BN_exp 597first appeared in SSLeay 0.9.0. 598All these functions have been available since 599.Ox 2.4 . 600.Pp 601.Fn BN_uadd , 602.Fn BN_usub , 603and the 604.Fa ctx 605argument to 606.Fn BN_mul 607first appeared in SSLeay 0.9.1 and have been available since 608.Ox 2.6 . 609.Pp 610.Fn BN_nnmod , 611.Fn BN_mod_add , 612.Fn BN_mod_add_quick , 613.Fn BN_mod_sub , 614.Fn BN_mod_sub_quick , 615.Fn BN_mod_sqr , 616.Fn BN_mod_lshift , 617.Fn BN_mod_lshift_quick , 618.Fn BN_mod_lshift1 , 619and 620.Fn BN_mod_lshift1_quick 621first appeared in OpenSSL 0.9.7 and have been available since 622.Ox 3.2 . 623.Sh BUGS 624Even if the 625.Dv BN_FLG_CONSTTIME 626flag is set on 627.Fa a 628or 629.Fa b , 630.Fn BN_gcd 631neither fails nor operates in constant time, potentially allowing 632timing side-channel attacks. 633.Pp 634Even if the 635.Dv BN_FLG_CONSTTIME 636flag is set on 637.Fa p , 638if the modulus 639.Fa m 640is even, 641.Fn BN_mod_exp 642does not operate in constant time, potentially allowing 643timing side-channel attacks. 644.Pp 645If 646.Dv BN_FLG_CONSTTIME 647is set on 648.Fa p , 649.Fn BN_exp 650fails instead of operating in constant time. 651