2 ''' $RCSfile$$Revision$$Date$
20 .ie \\n(.$>=3 .ne \\$3
36 ''' Set up \*(-- to give an unbreakable dash;
37 ''' string Tr holds user defined translation string.
38 ''' Bell System Logo is used as a dummy character.
44 .if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch
45 .if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\" diablo 12 pitch
48 ''' \*(M", \*(S", \*(N" and \*(T" are the equivalent of
49 ''' \*(L" and \*(R", except that they are used on ".xx" lines,
50 ''' such as .IP and .SH, which do another additional levels of
51 ''' double-quote interpretation
80 .\" If the F register is turned on, we'll generate
81 .\" index entries out stderr for the following things:
86 .\" X<> Xref (embedded
87 .\" Of course, you have to process the output yourself
88 .\" in some meaninful fashion.
91 .tm Index:\\$1\t\\n%\t"\\$2"
96 .TH BN_mod_mul_montgomery 3 "0.9.7d" "2/Sep/2004" "OpenSSL"
100 .ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p'
101 .de CQ \" put $1 in typewriter font
107 \\&\\$2 \\$3 \\$4 \\$5 \\$6 \\$7
110 .\" @(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2
111 . \" AM - accent mark definitions
113 . \" fudge factors for nroff and troff
122 . ds #H ((1u-(\\\\n(.fu%2u))*.13m)
128 . \" simple accents for nroff and troff
141 . ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u"
142 . ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u'
143 . ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u'
144 . ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u'
145 . ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u'
146 . ds ? \s-2c\h'-\w'c'u*7/10'\u\h'\*(#H'\zi\d\s+2\h'\w'c'u*8/10'
147 . ds ! \s-2\(or\s+2\h'-\w'\(or'u'\v'-.8m'.\v'.8m'
148 . ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u'
149 . ds q o\h'-\w'o'u*8/10'\s-4\v'.4m'\z\(*i\v'-.4m'\s+4\h'\w'o'u*8/10'
151 . \" troff and (daisy-wheel) nroff accents
152 .ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V'
153 .ds 8 \h'\*(#H'\(*b\h'-\*(#H'
154 .ds v \\k:\h'-(\\n(.wu*9/10-\*(#H)'\v'-\*(#V'\*(#[\s-4v\s0\v'\*(#V'\h'|\\n:u'\*(#]
155 .ds _ \\k:\h'-(\\n(.wu*9/10-\*(#H+(\*(#F*2/3))'\v'-.4m'\z\(hy\v'.4m'\h'|\\n:u'
156 .ds . \\k:\h'-(\\n(.wu*8/10)'\v'\*(#V*4/10'\z.\v'-\*(#V*4/10'\h'|\\n:u'
157 .ds 3 \*(#[\v'.2m'\s-2\&3\s0\v'-.2m'\*(#]
158 .ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#]
159 .ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H'
160 .ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u'
161 .ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#]
162 .ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#]
163 .ds ae a\h'-(\w'a'u*4/10)'e
164 .ds Ae A\h'-(\w'A'u*4/10)'E
165 .ds oe o\h'-(\w'o'u*4/10)'e
166 .ds Oe O\h'-(\w'O'u*4/10)'E
167 . \" corrections for vroff
168 .if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u'
169 .if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u'
170 . \" for low resolution devices (crt and lpr)
171 .if \n(.H>23 .if \n(.V>19 \
175 . ds v \h'-1'\o'\(aa\(ga'
191 BN_mod_mul_montgomery, BN_MONT_CTX_new, BN_MONT_CTX_init,
192 BN_MONT_CTX_free, BN_MONT_CTX_set, BN_MONT_CTX_copy,
193 BN_from_montgomery, BN_to_montgomery \- Montgomery multiplication
197 \& #include <openssl/bn.h>
200 \& BN_MONT_CTX *BN_MONT_CTX_new(void);
201 \& void BN_MONT_CTX_init(BN_MONT_CTX *ctx);
202 \& void BN_MONT_CTX_free(BN_MONT_CTX *mont);
205 \& int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *m, BN_CTX *ctx);
206 \& BN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to, BN_MONT_CTX *from);
209 \& int BN_mod_mul_montgomery(BIGNUM *r, BIGNUM *a, BIGNUM *b,
210 \& BN_MONT_CTX *mont, BN_CTX *ctx);
213 \& int BN_from_montgomery(BIGNUM *r, BIGNUM *a, BN_MONT_CTX *mont,
217 \& int BN_to_montgomery(BIGNUM *r, BIGNUM *a, BN_MONT_CTX *mont,
221 These functions implement Montgomery multiplication. They are used
222 automatically when BN_mod_exp(3) is called with suitable input,
223 but they may be useful when several operations are to be performed
224 using the same modulus.
226 \fIBN_MONT_CTX_new()\fR allocates and initializes a \fBBN_MONT_CTX\fR structure.
227 \fIBN_MONT_CTX_init()\fR initializes an existing uninitialized \fBBN_MONT_CTX\fR.
229 \fIBN_MONT_CTX_set()\fR sets up the \fImont\fR structure from the modulus \fIm\fR
230 by precomputing its inverse and a value R.
232 \fIBN_MONT_CTX_copy()\fR copies the \fBBN_MONT_CTX\fR \fIfrom\fR to \fIto\fR.
234 \fIBN_MONT_CTX_free()\fR frees the components of the \fBBN_MONT_CTX\fR, and, if
235 it was created by \fIBN_MONT_CTX_new()\fR, also the structure itself.
237 \fIBN_mod_mul_montgomery()\fR computes \fIMont\fR\|(\fIa\fR,\fIb\fR):=\fIa\fR*\fIb\fR*R^\-1 and places
238 the result in \fIr\fR.
240 \fIBN_from_montgomery()\fR performs the Montgomery reduction \fIr\fR = \fIa\fR*R^\-1.
242 \fIBN_to_montgomery()\fR computes \fIMont\fR\|(\fIa\fR,R^2), i.e. \fIa\fR*R.
243 Note that \fIa\fR must be non-negative and smaller than the modulus.
245 For all functions, \fIctx\fR is a previously allocated \fBBN_CTX\fR used for
248 The \fBBN_MONT_CTX\fR structure is defined as follows:
251 \& typedef struct bn_mont_ctx_st
253 \& int ri; /* number of bits in R */
254 \& BIGNUM RR; /* R^2 (used to convert to Montgomery form) */
255 \& BIGNUM N; /* The modulus */
256 \& BIGNUM Ni; /* R*(1/R mod N) - N*Ni = 1
257 \& * (Ni is only stored for bignum algorithm) */
258 \& BN_ULONG n0; /* least significant word of Ni */
262 \fIBN_to_montgomery()\fR is a macro.
264 \fIBN_MONT_CTX_new()\fR returns the newly allocated \fBBN_MONT_CTX\fR, and NULL
267 \fIBN_MONT_CTX_init()\fR and \fIBN_MONT_CTX_free()\fR have no return values.
269 For the other functions, 1 is returned for success, 0 on error.
270 The error codes can be obtained by ERR_get_error(3).
272 The inputs must be reduced modulo \fBm\fR, otherwise the result will be
273 outside the expected range.
275 bn(3), ERR_get_error(3), BN_add(3),
278 \fIBN_MONT_CTX_new()\fR, \fIBN_MONT_CTX_free()\fR, \fIBN_MONT_CTX_set()\fR,
279 \fIBN_mod_mul_montgomery()\fR, \fIBN_from_montgomery()\fR and \fIBN_to_montgomery()\fR
280 are available in all versions of SSLeay and OpenSSL.
282 \fIBN_MONT_CTX_init()\fR and \fIBN_MONT_CTX_copy()\fR were added in SSLeay 0.9.1b.
285 .IX Title "BN_mod_mul_montgomery 3"
286 .IX Name "BN_mod_mul_montgomery, BN_MONT_CTX_new, BN_MONT_CTX_init,
287 BN_MONT_CTX_free, BN_MONT_CTX_set, BN_MONT_CTX_copy,
288 BN_from_montgomery, BN_to_montgomery - Montgomery multiplication"
292 .IX Header "SYNOPSIS"
294 .IX Header "DESCRIPTION"
296 .IX Header "RETURN VALUES"
300 .IX Header "SEE ALSO"