1.Dd $Mdocdate: February 23 2015 $ 2.Dt BN_MOD_MUL_MONTGOMERY 3 3.Os 4.Sh NAME 5.Nm BN_mod_mul_montgomery , 6.Nm BN_MONT_CTX_new , 7.Nm BN_MONT_CTX_init , 8.Nm BN_MONT_CTX_free , 9.Nm BN_MONT_CTX_set , 10.Nm BN_MONT_CTX_copy , 11.Nm BN_from_montgomery , 12.Nm BN_to_montgomery 13.Nd Montgomery multiplication 14.Sh SYNOPSIS 15.In openssl/bn.h 16.Ft BN_MONT_CTX * 17.Fo BN_MONT_CTX_new 18.Fa void 19.Fc 20.Ft void 21.Fo BN_MONT_CTX_init 22.Fa "BN_MONT_CTX *ctx" 23.Fc 24.Ft void 25.Fo BN_MONT_CTX_free 26.Fa "BN_MONT_CTX *mont" 27.Fc 28.Ft int 29.Fo BN_MONT_CTX_set 30.Fa "BN_MONT_CTX *mont" 31.Fa "const BIGNUM *m" 32.Fa "BN_CTX *ctx" 33.Fc 34.Ft BN_MONT_CTX * 35.Fo BN_MONT_CTX_copy 36.Fa "BN_MONT_CTX *to" 37.Fa "BN_MONT_CTX *from" 38.Fc 39.Ft int 40.Fo BN_mod_mul_montgomery 41.Fa "BIGNUM *r" 42.Fa "BIGNUM *a" 43.Fa "BIGNUM *b" 44.Fa "BN_MONT_CTX *mont" 45.Fa "BN_CTX *ctx" 46.Fc 47.Ft int 48.Fo BN_from_montgomery 49.Fa "BIGNUM *r" 50.Fa "BIGNUM *a" 51.Fa "BN_MONT_CTX *mont" 52.Fa "BN_CTX *ctx" 53.Fc 54.Ft int 55.Fo BN_to_montgomery 56.Fa "BIGNUM *r" 57.Fa "BIGNUM *a" 58.Fa "BN_MONT_CTX *mont" 59.Fa "BN_CTX *ctx" 60.Fc 61.Sh DESCRIPTION 62These functions implement Montgomery multiplication. 63They are used automatically when 64.Xr BN_mod_exp 3 65is called with suitable input, but they may be useful when several 66operations are to be performed using the same modulus. 67.Pp 68.Fn BN_MONT_CTX_new 69allocates and initializes a 70.Vt BN_MONT_CTX 71structure. 72.Fn BN_MONT_CTX_init 73initializes an existing uninitialized 74.Vt BN_MONT_CTX . 75.Pp 76.Fn BN_MONT_CTX_set 77sets up the 78.Fa mont 79structure from the modulus 80.Fa m 81by precomputing its inverse and a value R. 82.Pp 83.Fn BN_MONT_CTX_copy 84copies the 85.Vt BN_MONT_CTX 86.Fa from 87to 88.Fa to . 89.Pp 90.Fn BN_MONT_CTX_free 91frees the components of the 92.Vt BN_MONT_CTX , 93and, if it was created by 94.Fn BN_MONT_CTX_new , 95also the structure itself. 96.Pp 97.Fn BN_mod_mul_montgomery 98computes 99.Pp 100.D1 Mont Ns Po Fa a , Fa b Pc := Fa a No * Fa b No * R^-1 101.Pp 102and places the result in 103.Fa r . 104.Pp 105.Fn BN_from_montgomery 106performs the Montgomery reduction 107.Pp 108.D1 Fa r No = Fa a No * R^-1. 109.Pp 110.Fn BN_to_montgomery 111computes 112.Pp 113.D1 Mont Ns Po Fa a , No R^2 Pc = Fa a No * R . 114.Pp 115Note that 116.Fa a 117must be non-negative and smaller than the modulus. 118.Pp 119For all functions, 120.Fa ctx 121is a previously allocated 122.Vt BN_CTX 123used for temporary variables. 124.Pp 125The 126.Vt BN_MONT_CTX 127structure is defined as follows: 128.Bd -literal 129typedef struct bn_mont_ctx_st { 130 int ri; /* number of bits in R */ 131 BIGNUM RR; /* R^2 (used to convert to Montgomery form) */ 132 BIGNUM N; /* The modulus */ 133 BIGNUM Ni; /* R*(1/R mod N) - N*Ni = 1 134 * (Ni is only stored for bignum algorithm) */ 135 BN_ULONG n0; /* least significant word of Ni */ 136 int flags; 137} BN_MONT_CTX; 138.Ed 139.Pp 140.Fn BN_to_montgomery 141is a macro. 142.Pp 143.Sy Warning: 144The inputs must be reduced modulo 145.Fa m , 146otherwise the result will be outside the expected range. 147.Sh RETURN VALUES 148.Fn BN_MONT_CTX_new 149returns the newly allocated 150.Vt BN_MONT_CTX , 151and 152.Dv NULL 153on error. 154.Pp 155.Fn BN_MONT_CTX_init 156and 157.Fn BN_MONT_CTX_free 158return no values. 159.Pp 160For the other functions, 1 is returned for success, 0 on error. 161The error codes can be obtained by 162.Xr ERR_get_error 3 . 163.Sh SEE ALSO 164.Xr bn 3 , 165.Xr BN_add 3 , 166.Xr BN_CTX_new 3 , 167.Xr ERR_get_error 3 168.Sh HISTORY 169.Fn BN_MONT_CTX_new , 170.Fn BN_MONT_CTX_free , 171.Fn BN_MONT_CTX_set , 172.Fn BN_mod_mul_montgomery , 173.Fn BN_from_montgomery 174and 175.Fn BN_to_montgomery 176are available in all versions of SSLeay and OpenSSL. 177.Pp 178.Fn BN_MONT_CTX_init 179and 180.Fn BN_MONT_CTX_copy 181were added in SSLeay 0.9.1b. 182