secure/lib/libcrypto/man/BN_mod_mul_montgomery.3

   1 .\" Automatically generated by Pod::Man version 1.15
   2 .\" Wed Feb 19 16:42:48 2003
   3 .\"
   4 .\" Standard preamble:
   5 .\" ======================================================================
   6 .de Sh \" Subsection heading
   7 .br
   8 .if t .Sp
   9 .ne 5
  10 .PP
  11 \fB\\$1\fR
  12 .PP
  13 ..
  14 .de Sp \" Vertical space (when we can't use .PP)
  15 .if t .sp .5v
  16 .if n .sp
  17 ..
  18 .de Ip \" List item
  19 .br
  20 .ie \\n(.$>=3 .ne \\$3
  21 .el .ne 3
  22 .IP "\\$1" \\$2
  23 ..
  24 .de Vb \" Begin verbatim text
  25 .ft CW
  26 .nf
  27 .ne \\$1
  28 ..
  29 .de Ve \" End verbatim text
  30 .ft R
  31
  32 .fi
  33 ..
  34 .\" Set up some character translations and predefined strings.  \*(-- will
  35 .\" give an unbreakable dash, \*(PI will give pi, \*(L" will give a left
  36 .\" double quote, and \*(R" will give a right double quote.  | will give a
  37 .\" real vertical bar.  \*(C+ will give a nicer C++.  Capital omega is used
  38 .\" to do unbreakable dashes and therefore won't be available.  \*(C` and
  39 .\" \*(C' expand to `' in nroff, nothing in troff, for use with C<>
  40 .tr \(*W-|\(bv\*(Tr
  41 .ds C+ C\v'-.1v'\h'-1p'\s-2+\h'-1p'+\s0\v'.1v'\h'-1p'
  42 .ie n \{\
  43 .    ds -- \(*W-
  44 .    ds PI pi
  45 .    if (\n(.H=4u)&(1m=24u) .ds -- \(*W\h'-12u'\(*W\h'-12u'-\" diablo 10 pitch
  46 .    if (\n(.H=4u)&(1m=20u) .ds -- \(*W\h'-12u'\(*W\h'-8u'-\"  diablo 12 pitch
  47 .    ds L" ""
  48 .    ds R" ""
  49 .    ds C` ""
  50 .    ds C' ""
  51 'br\}
  52 .el\{\
  53 .    ds -- \|\(em\|
  54 .    ds PI \(*p
  55 .    ds L" ``
  56 .    ds R" ''
  57 'br\}
  58 .\"
  59 .\" If the F register is turned on, we'll generate index entries on stderr
  60 .\" for titles (.TH), headers (.SH), subsections (.Sh), items (.Ip), and
  61 .\" index entries marked with X<> in POD.  Of course, you'll have to process
  62 .\" the output yourself in some meaningful fashion.
  63 .if \nF \{\
  64 .    de IX
  65 .    tm Index:\\$1\t\\n%\t"\\$2"
  66 ..
  67 .    nr % 0
  68 .    rr F
  69 .\}
  70 .\"
  71 .\" For nroff, turn off justification.  Always turn off hyphenation; it
  72 .\" makes way too many mistakes in technical documents.
  73 .hy 0
  74 .if n .na
  75 .\"
  76 .\" Accent mark definitions (@(#)ms.acc 1.5 88/02/08 SMI; from UCB 4.2).
  77 .\" Fear.  Run.  Save yourself.  No user-serviceable parts.
  78 .bd B 3
  79 .    \" fudge factors for nroff and troff
  80 .if n \{\
  81 .    ds #H 0
  82 .    ds #V .8m
  83 .    ds #F .3m
  84 .    ds #[ \f1
  85 .    ds #] \fP
  86 .\}
  87 .if t \{\
  88 .    ds #H ((1u-(\\\\n(.fu%2u))*.13m)
  89 .    ds #V .6m
  90 .    ds #F 0
  91 .    ds #[ \&
  92 .    ds #] \&
  93 .\}
  94 .    \" simple accents for nroff and troff
  95 .if n \{\
  96 .    ds ' \&
  97 .    ds ` \&
  98 .    ds ^ \&
  99 .    ds , \&
 100 .    ds ~ ~
 101 .    ds /
 102 .\}
 103 .if t \{\
 104 .    ds ' \\k:\h'-(\\n(.wu*8/10-\*(#H)'\'\h"|\\n:u"
 105 .    ds ` \\k:\h'-(\\n(.wu*8/10-\*(#H)'\`\h'|\\n:u'
 106 .    ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'^\h'|\\n:u'
 107 .    ds , \\k:\h'-(\\n(.wu*8/10)',\h'|\\n:u'
 108 .    ds ~ \\k:\h'-(\\n(.wu-\*(#H-.1m)'~\h'|\\n:u'
 109 .    ds / \\k:\h'-(\\n(.wu*8/10-\*(#H)'\z\(sl\h'|\\n:u'
 110 .\}
 111 .    \" troff and (daisy-wheel) nroff accents
 112 .ds : \\k:\h'-(\\n(.wu*8/10-\*(#H+.1m+\*(#F)'\v'-\*(#V'\z.\h'.2m+\*(#F'.\h'|\\n:u'\v'\*(#V'
 113 .ds 8 \h'\*(#H'\(*b\h'-\*(#H'
 114 .ds o \\k:\h'-(\\n(.wu+\w'\(de'u-\*(#H)/2u'\v'-.3n'\*(#[\z\(de\v'.3n'\h'|\\n:u'\*(#]
 115 .ds d- \h'\*(#H'\(pd\h'-\w'~'u'\v'-.25m'\f2\(hy\fP\v'.25m'\h'-\*(#H'
 116 .ds D- D\\k:\h'-\w'D'u'\v'-.11m'\z\(hy\v'.11m'\h'|\\n:u'
 117 .ds th \*(#[\v'.3m'\s+1I\s-1\v'-.3m'\h'-(\w'I'u*2/3)'\s-1o\s+1\*(#]
 118 .ds Th \*(#[\s+2I\s-2\h'-\w'I'u*3/5'\v'-.3m'o\v'.3m'\*(#]
 119 .ds ae a\h'-(\w'a'u*4/10)'e
 120 .ds Ae A\h'-(\w'A'u*4/10)'E
 121 .    \" corrections for vroff
 122 .if v .ds ~ \\k:\h'-(\\n(.wu*9/10-\*(#H)'\s-2\u~\d\s+2\h'|\\n:u'
 123 .if v .ds ^ \\k:\h'-(\\n(.wu*10/11-\*(#H)'\v'-.4m'^\v'.4m'\h'|\\n:u'
 124 .    \" for low resolution devices (crt and lpr)
 125 .if \n(.H>23 .if \n(.V>19 \
 126 \{\
 127 .    ds : e
 128 .    ds 8 ss
 129 .    ds o a
 130 .    ds d- d\h'-1'\(ga
 131 .    ds D- D\h'-1'\(hy
 132 .    ds th \o'bp'
 133 .    ds Th \o'LP'
 134 .    ds ae ae
 135 .    ds Ae AE
 136 .\}
 137 .rm #[ #] #H #V #F C
 138 .\" ======================================================================
 139 .\"
 140 .IX Title "BN_mod_mul_montgomery 3"
 141 .TH BN_mod_mul_montgomery 3 "0.9.7a" "2003-02-19" "OpenSSL"
 142 .UC
 143 .SH "NAME"
 144 BN_mod_mul_montgomery, BN_MONT_CTX_new, BN_MONT_CTX_init,
 145 BN_MONT_CTX_free, BN_MONT_CTX_set, BN_MONT_CTX_copy,
 146 BN_from_montgomery, BN_to_montgomery \- Montgomery multiplication
 147 .SH "SYNOPSIS"
 148 .IX Header "SYNOPSIS"
 149 .Vb 1
 150 \& #include <openssl/bn.h>
 151 .Ve
 152 .Vb 3
 153 \& BN_MONT_CTX *BN_MONT_CTX_new(void);
 154 \& void BN_MONT_CTX_init(BN_MONT_CTX *ctx);
 155 \& void BN_MONT_CTX_free(BN_MONT_CTX *mont);
 156 .Ve
 157 .Vb 2
 158 \& int BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *m, BN_CTX *ctx);
 159 \& BN_MONT_CTX *BN_MONT_CTX_copy(BN_MONT_CTX *to, BN_MONT_CTX *from);
 160 .Ve
 161 .Vb 2
 162 \& int BN_mod_mul_montgomery(BIGNUM *r, BIGNUM *a, BIGNUM *b,
 163 \&         BN_MONT_CTX *mont, BN_CTX *ctx);
 164 .Ve
 165 .Vb 2
 166 \& int BN_from_montgomery(BIGNUM *r, BIGNUM *a, BN_MONT_CTX *mont,
 167 \&         BN_CTX *ctx);
 168 .Ve
 169 .Vb 2
 170 \& int BN_to_montgomery(BIGNUM *r, BIGNUM *a, BN_MONT_CTX *mont,
 171 \&         BN_CTX *ctx);
 172 .Ve
 173 .SH "DESCRIPTION"
 174 .IX Header "DESCRIPTION"
 175 These functions implement Montgomery multiplication. They are used
 176 automatically when BN_mod_exp(3) is called with suitable input,
 177 but they may be useful when several operations are to be performed
 178 using the same modulus.
 179 .PP
 180 \&\fIBN_MONT_CTX_new()\fR allocates and initializes a \fB\s-1BN_MONT_CTX\s0\fR structure.
 181 \&\fIBN_MONT_CTX_init()\fR initializes an existing uninitialized \fB\s-1BN_MONT_CTX\s0\fR.
 182 .PP
 183 \&\fIBN_MONT_CTX_set()\fR sets up the \fImont\fR structure from the modulus \fIm\fR
 184 by precomputing its inverse and a value R.
 185 .PP
 186 \&\fIBN_MONT_CTX_copy()\fR copies the \fB\s-1BN_MONT_CTX\s0\fR \fIfrom\fR to \fIto\fR.
 187 .PP
 188 \&\fIBN_MONT_CTX_free()\fR frees the components of the \fB\s-1BN_MONT_CTX\s0\fR, and, if
 189 it was created by \fIBN_MONT_CTX_new()\fR, also the structure itself.
 190 .PP
 191 \&\fIBN_mod_mul_montgomery()\fR computes Mont(\fIa\fR,\fIb\fR):=\fIa\fR*\fIb\fR*R^\-1 and places
 192 the result in \fIr\fR.
 193 .PP
 194 \&\fIBN_from_montgomery()\fR performs the Montgomery reduction \fIr\fR = \fIa\fR*R^\-1.
 195 .PP
 196 \&\fIBN_to_montgomery()\fR computes Mont(\fIa\fR,R^2), i.e. \fIa\fR*R.
 197 Note that \fIa\fR must be non-negative and smaller than the modulus.
 198 .PP
 199 For all functions, \fIctx\fR is a previously allocated \fB\s-1BN_CTX\s0\fR used for
 200 temporary variables.
 201 .PP
 202 The \fB\s-1BN_MONT_CTX\s0\fR structure is defined as follows:
 203 .PP
 204 .Vb 10
 205 \& typedef struct bn_mont_ctx_st
 206 \&        {
 207 \&        int ri;         /* number of bits in R */
 208 \&        BIGNUM RR;      /* R^2 (used to convert to Montgomery form) */
 209 \&        BIGNUM N;       /* The modulus */
 210 \&        BIGNUM Ni;      /* R*(1/R mod N) - N*Ni = 1
 211 \&                         * (Ni is only stored for bignum algorithm) */
 212 \&        BN_ULONG n0;    /* least significant word of Ni */
 213 \&        int flags;
 214 \&        } BN_MONT_CTX;
 215 .Ve
 216 \&\fIBN_to_montgomery()\fR is a macro.
 217 .SH "RETURN VALUES"
 218 .IX Header "RETURN VALUES"
 219 \&\fIBN_MONT_CTX_new()\fR returns the newly allocated \fB\s-1BN_MONT_CTX\s0\fR, and \s-1NULL\s0
 220 on error.
 221 .PP
 222 \&\fIBN_MONT_CTX_init()\fR and \fIBN_MONT_CTX_free()\fR have no return values.
 223 .PP
 224 For the other functions, 1 is returned for success, 0 on error.
 225 The error codes can be obtained by ERR_get_error(3).
 226 .SH "WARNING"
 227 .IX Header "WARNING"
 228 The inputs must be reduced modulo \fBm\fR, otherwise the result will be
 229 outside the expected range.
 230 .SH "SEE ALSO"
 231 .IX Header "SEE ALSO"
 232 bn(3), ERR_get_error(3), BN_add(3),
 233 BN_CTX_new(3)
 234 .SH "HISTORY"
 235 .IX Header "HISTORY"
 236 \&\fIBN_MONT_CTX_new()\fR, \fIBN_MONT_CTX_free()\fR, \fIBN_MONT_CTX_set()\fR,
 237 \&\fIBN_mod_mul_montgomery()\fR, \fIBN_from_montgomery()\fR and \fIBN_to_montgomery()\fR
 238 are available in all versions of SSLeay and OpenSSL.
 239 .PP
 240 \&\fIBN_MONT_CTX_init()\fR and \fIBN_MONT_CTX_copy()\fR were added in SSLeay 0.9.1b.