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