cryptlib
3.4.1
Main Page
Namespaces
Classes
Files
File List
File Members
All
Classes
Namespaces
Files
Functions
Variables
Typedefs
Enumerations
Enumerator
Properties
Macros
bn
bn_ctx.c
Go to the documentation of this file.
1
/* crypto/bn/bn_ctx.c */
2
/* Written by Ulf Moeller for the OpenSSL project. */
3
/* ====================================================================
4
* Copyright (c) 1998-2004 The OpenSSL Project. All rights reserved.
5
*
6
* Redistribution and use in source and binary forms, with or without
7
* modification, are permitted provided that the following conditions
8
* are met:
9
*
10
* 1. Redistributions of source code must retain the above copyright
11
* notice, this list of conditions and the following disclaimer.
12
*
13
* 2. Redistributions in binary form must reproduce the above copyright
14
* notice, this list of conditions and the following disclaimer in
15
* the documentation and/or other materials provided with the
16
* distribution.
17
*
18
* 3. All advertising materials mentioning features or use of this
19
* software must display the following acknowledgment:
20
* "This product includes software developed by the OpenSSL Project
21
* for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
22
*
23
* 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
24
* endorse or promote products derived from this software without
25
* prior written permission. For written permission, please contact
26
*
[email protected]
.
27
*
28
* 5. Products derived from this software may not be called "OpenSSL"
29
* nor may "OpenSSL" appear in their names without prior written
30
* permission of the OpenSSL Project.
31
*
32
* 6. Redistributions of any form whatsoever must retain the following
33
* acknowledgment:
34
* "This product includes software developed by the OpenSSL Project
35
* for use in the OpenSSL Toolkit (http://www.openssl.org/)"
36
*
37
* THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
38
* EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
39
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
40
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
41
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
42
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
43
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
44
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
45
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
46
* STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
47
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
48
* OF THE POSSIBILITY OF SUCH DAMAGE.
49
* ====================================================================
50
*
51
* This product includes cryptographic software written by Eric Young
52
* (
[email protected]
). This product includes software written by Tim
53
* Hudson (
[email protected]
).
54
*
55
*/
56
57
/* Removed NDEBUG redefinition - pcg */
58
/* Added proper initialisation of data in all BN_X_init() functions - pcg */
59
60
#include <stdio.h>
61
#include <assert.h>
62
63
#if defined( _WIN32_WCE ) && _WIN32_WCE < 400
64
#define assert( x )
65
#else
66
#include <assert.h>
67
#endif
/* Systems without assert() */
68
#if defined( INC_ALL )
69
#include "
bn_lcl.h
"
70
#else
71
#include "
bn/bn_lcl.h
"
72
#endif
/* Compiler-specific includes */
73
74
/* TODO list
75
*
76
* 1. Check a bunch of "(words+1)" type hacks in various bignum functions and
77
* check they can be safely removed.
78
* - Check +1 and other ugliness in BN_from_montgomery()
79
*
80
* 2. Consider allowing a BN_new_ex() that, at least, lets you specify an
81
* appropriate 'block' size that will be honoured by bn_expand_internal() to
82
* prevent piddly little reallocations. OTOH, profiling bignum expansions in
83
* BN_CTX doesn't show this to be a big issue.
84
*/
85
86
/* How many bignums are in each "pool item"; */
87
#define BN_CTX_POOL_SIZE 16
88
/* The stack frame info is resizing, set a first-time expansion size; */
89
#define BN_CTX_START_FRAMES 32
90
91
/***********/
92
/* BN_POOL */
93
/***********/
94
95
/* A bundle of bignums that can be linked with other bundles */
96
typedef
struct
bignum_pool_item
97
{
98
/* The bignum values */
99
BIGNUM
vals
[
BN_CTX_POOL_SIZE
];
100
/* Linked-list admin */
101
struct
bignum_pool_item
*
prev
, *
next
;
102
}
BN_POOL_ITEM
;
103
/* A linked-list of bignums grouped in bundles */
104
typedef
struct
bignum_pool
105
{
106
/* Linked-list admin */
107
BN_POOL_ITEM
*
head
, *
current
, *
tail
;
108
/* Stack depth and allocation size */
109
unsigned
used
,
size
;
110
}
BN_POOL
;
111
static
void
BN_POOL_init(
BN_POOL
*);
112
static
void
BN_POOL_finish(
BN_POOL
*);
113
#ifndef OPENSSL_NO_DEPRECATED
114
static
void
BN_POOL_reset(
BN_POOL
*);
115
#endif
116
static
BIGNUM
* BN_POOL_get(
BN_POOL
*);
117
static
void
BN_POOL_release(
BN_POOL
*,
unsigned
int
);
118
119
/************/
120
/* BN_STACK */
121
/************/
122
123
/* A wrapper to manage the "stack frames" */
124
typedef
struct
bignum_ctx_stack
125
{
126
/* Array of indexes into the bignum stack */
127
unsigned
int
*
indexes
;
128
/* Number of stack frames, and the size of the allocated array */
129
unsigned
int
depth
,
size
;
130
}
BN_STACK
;
131
static
void
BN_STACK_init(
BN_STACK
*);
132
static
void
BN_STACK_finish(
BN_STACK
*);
133
#ifndef OPENSSL_NO_DEPRECATED
134
static
void
BN_STACK_reset(
BN_STACK
*);
135
#endif
136
static
int
BN_STACK_push(
BN_STACK
*,
unsigned
int
);
137
static
unsigned
int
BN_STACK_pop(
BN_STACK
*);
138
139
/**********/
140
/* BN_CTX */
141
/**********/
142
143
/* The opaque BN_CTX type */
144
struct
bignum_ctx
145
{
146
/* The bignum bundles */
147
BN_POOL
pool
;
148
/* The "stack frames", if you will */
149
BN_STACK
stack
;
150
/* The number of bignums currently assigned */
151
unsigned
int
used
;
152
/* Depth of stack overflow */
153
int
err_stack
;
154
/* Block "gets" until an "end" (compatibility behaviour) */
155
int
too_many
;
156
};
157
158
/* Enable this to find BN_CTX bugs */
159
#ifdef BN_CTX_DEBUG
160
static
const
char
*ctxdbg_cur = NULL;
161
static
void
ctxdbg(
BN_CTX
*ctx)
162
{
163
unsigned
int
bnidx = 0, fpidx = 0;
164
BN_POOL_ITEM
*item = ctx->
pool
.
head
;
165
BN_STACK
*stack = &ctx->
stack
;
166
fprintf(stderr,
"(%08x): "
, (
unsigned
int
)ctx);
167
while
(bnidx < ctx->used)
168
{
169
fprintf(stderr,
"%02x "
, item->
vals
[bnidx++ %
BN_CTX_POOL_SIZE
].
dmax
);
170
if
(!(bnidx %
BN_CTX_POOL_SIZE
))
171
item = item->
next
;
172
}
173
fprintf(stderr,
"\n"
);
174
bnidx = 0;
175
fprintf(stderr,
" : "
);
176
while
(fpidx < stack->depth)
177
{
178
while
(bnidx++ < stack->
indexes
[fpidx])
179
fprintf(stderr,
" "
);
180
fprintf(stderr,
"^^ "
);
181
bnidx++;
182
fpidx++;
183
}
184
fprintf(stderr,
"\n"
);
185
}
186
#define CTXDBG_ENTRY(str, ctx) do { \
187
ctxdbg_cur = (str); \
188
fprintf(stderr,"Starting %s\n", ctxdbg_cur); \
189
ctxdbg(ctx); \
190
} while(0)
191
#define CTXDBG_EXIT(ctx) do { \
192
fprintf(stderr,"Ending %s\n", ctxdbg_cur); \
193
ctxdbg(ctx); \
194
} while(0)
195
#define CTXDBG_RET(ctx,ret)
196
#else
197
#define CTXDBG_ENTRY(str, ctx)
198
#define CTXDBG_EXIT(ctx)
199
#define CTXDBG_RET(ctx,ret)
200
#endif
201
202
/* This function is an evil legacy and should not be used. This implementation
203
* is WYSIWYG, though I've done my best. */
204
#ifndef OPENSSL_NO_DEPRECATED
205
void
BN_CTX_init
(
BN_CTX
*ctx)
206
{
207
/* Assume the caller obtained the context via BN_CTX_new() and so is
208
* trying to reset it for use. Nothing else makes sense, least of all
209
* binary compatibility from a time when they could declare a static
210
* variable. */
211
BN_POOL_reset(&ctx->
pool
);
212
BN_STACK_reset(&ctx->
stack
);
213
ctx->
used
= 0;
214
ctx->
err_stack
= 0;
215
ctx->
too_many
= 0;
216
}
217
#endif
218
219
BN_CTX
*
BN_CTX_new
(
void
)
220
{
221
BN_CTX
*ret =
clBnAlloc
(
"BN_CTX_new"
,
sizeof
(
BN_CTX
));
/* pcg */
222
if
(!ret)
223
{
224
BNerr
(
BN_F_BN_CTX_NEW
,ERR_R_MALLOC_FAILURE);
225
return
NULL;
226
}
227
memset( ret, 0,
sizeof
(
BN_CTX
) );
/* pcg */
228
/* Initialise the structure */
229
BN_POOL_init(&ret->
pool
);
230
BN_STACK_init(&ret->
stack
);
231
ret->
used
= 0;
232
ret->
err_stack
= 0;
233
ret->
too_many
= 0;
234
return
ret;
235
}
236
237
void
BN_CTX_free
(
BN_CTX
*ctx)
238
{
239
if
(ctx == NULL)
240
return
;
241
#ifdef BN_CTX_DEBUG
242
{
243
BN_POOL_ITEM
*pool = ctx->
pool
.
head
;
244
fprintf(stderr,
"BN_CTX_free, stack-size=%d, pool-bignums=%d\n"
,
245
ctx->
stack
.
size
, ctx->
pool
.
size
);
246
fprintf(stderr,
"dmaxs: "
);
247
while
(pool) {
248
unsigned
loop = 0;
249
while
(loop <
BN_CTX_POOL_SIZE
)
250
fprintf(stderr,
"%02x "
, pool->
vals
[loop++].
dmax
);
251
pool = pool->
next
;
252
}
253
fprintf(stderr,
"\n"
);
254
}
255
#endif
256
BN_STACK_finish(&ctx->
stack
);
257
BN_POOL_finish(&ctx->
pool
);
258
OPENSSL_free
(ctx);
259
}
260
261
void
BN_CTX_start
(
BN_CTX
*ctx)
262
{
263
CTXDBG_ENTRY
(
"BN_CTX_start"
, ctx);
264
/* If we're already overflowing ... */
265
if
(ctx->
err_stack
|| ctx->
too_many
)
266
ctx->
err_stack
++;
267
/* (Try to) get a new frame pointer */
268
else
if
(!BN_STACK_push(&ctx->
stack
, ctx->
used
))
269
{
270
BNerr
(
BN_F_BN_CTX_START
,
BN_R_TOO_MANY_TEMPORARY_VARIABLES
);
271
ctx->
err_stack
++;
272
}
273
CTXDBG_EXIT
(ctx);
274
}
275
276
void
BN_CTX_end
(
BN_CTX
*ctx)
277
{
278
CTXDBG_ENTRY
(
"BN_CTX_end"
, ctx);
279
if
(ctx->
err_stack
)
280
ctx->
err_stack
--;
281
else
282
{
283
unsigned
int
fp = BN_STACK_pop(&ctx->
stack
);
284
/* Does this stack frame have anything to release? */
285
if
(fp < ctx->used)
286
BN_POOL_release(&ctx->
pool
, ctx->
used
- fp);
287
ctx->
used
= fp;
288
/* Unjam "too_many" in case "get" had failed */
289
ctx->
too_many
= 0;
290
}
291
CTXDBG_EXIT
(ctx);
292
}
293
294
BIGNUM
*
BN_CTX_get
(
BN_CTX
*ctx)
295
{
296
BIGNUM
*ret;
297
CTXDBG_ENTRY
(
"BN_CTX_get"
, ctx);
298
if
(ctx->
err_stack
|| ctx->
too_many
)
return
NULL;
299
if
((ret = BN_POOL_get(&ctx->
pool
)) == NULL)
300
{
301
/* Setting too_many prevents repeated "get" attempts from
302
* cluttering the error stack. */
303
ctx->
too_many
= 1;
304
BNerr
(
BN_F_BN_CTX_GET
,
BN_R_TOO_MANY_TEMPORARY_VARIABLES
);
305
return
NULL;
306
}
307
/* OK, make sure the returned bignum is "zero" */
308
BN_zero
(ret);
309
ctx->
used
++;
310
CTXDBG_RET
(ctx, ret);
311
return
ret;
312
}
313
314
/* Added to handle resetting of bnCTX after use - pcg */
315
316
void
BN_CTX_clear
(
BN_CTX
*bnCTX )
317
{
318
BN_POOL_ITEM
*item = bnCTX->
pool
.
head
;
319
320
/* Reset the bignum pool */
321
while
( item != NULL )
322
{
323
unsigned
int
loop = 0;
324
BIGNUM
*bn = item->
vals
;
325
326
while
( loop++ <
BN_CTX_POOL_SIZE
)
327
{
328
if
( bn->
d
!= NULL )
329
BN_clear
( bn );
330
bn++;
331
}
332
item = item->
next
;
333
}
334
bnCTX->
pool
.
current
= bnCTX->
pool
.
head
;
335
bnCTX->
pool
.
used
= 0;
336
337
/* Reset the pool stack */
338
bnCTX->
stack
.
depth
= 0;
339
}
340
341
/************/
342
/* BN_STACK */
343
/************/
344
345
static
void
BN_STACK_init(
BN_STACK
*st)
346
{
347
memset( st, 0,
sizeof
(
BN_STACK
) );
/* pcg */
348
st->
indexes
= NULL;
349
st->
depth
= st->
size
= 0;
350
}
351
352
static
void
BN_STACK_finish(
BN_STACK
*st)
353
{
354
if
(st->
size
)
OPENSSL_free
(st->
indexes
);
355
}
356
357
#ifndef OPENSSL_NO_DEPRECATED
358
static
void
BN_STACK_reset(
BN_STACK
*st)
359
{
360
st->
depth
= 0;
361
}
362
#endif
363
364
static
int
BN_STACK_push(
BN_STACK
*st,
unsigned
int
idx
)
365
{
366
if
(st->
depth
== st->
size
)
367
/* Need to expand */
368
{
369
unsigned
int
newsize = (st->
size
?
370
(st->
size
* 3 / 2) :
BN_CTX_START_FRAMES
);
371
unsigned
int
*newitems =
clBnAlloc
(
"BN_STACK_push"
,newsize *
372
sizeof
(
unsigned
int
));
373
if
(!newitems)
return
0;
374
if
(st->
depth
)
375
memcpy(newitems, st->
indexes
, st->
depth
*
376
sizeof
(
unsigned
int
));
377
if
(st->
size
)
OPENSSL_free
(st->
indexes
);
378
st->
indexes
= newitems;
379
st->
size
= newsize;
380
}
381
st->
indexes
[(st->
depth
)++] = idx;
382
return
1;
383
}
384
385
static
unsigned
int
BN_STACK_pop(
BN_STACK
*st)
386
{
387
return
st->
indexes
[--(st->
depth
)];
388
}
389
390
/***********/
391
/* BN_POOL */
392
/***********/
393
394
static
void
BN_POOL_init(
BN_POOL
*
p
)
395
{
396
memset( p, 0,
sizeof
(
BN_POOL
) );
/* pcg */
397
p->
head
= p->
current
= p->
tail
= NULL;
398
p->
used
= p->
size
= 0;
399
}
400
401
static
void
BN_POOL_finish(
BN_POOL
*p)
402
{
403
while
(p->
head
)
404
{
405
unsigned
int
loop = 0;
406
BIGNUM
*bn = p->
head
->
vals
;
407
while
(loop++ <
BN_CTX_POOL_SIZE
)
408
{
409
if
(bn->
d
)
BN_clear_free
(bn);
410
bn++;
411
}
412
p->
current
= p->
head
->
next
;
413
OPENSSL_free
(p->
head
);
414
p->
head
= p->
current
;
415
}
416
}
417
418
#ifndef OPENSSL_NO_DEPRECATED
419
static
void
BN_POOL_reset(
BN_POOL
*p)
420
{
421
BN_POOL_ITEM
*item = p->
head
;
422
while
(item)
423
{
424
unsigned
int
loop = 0;
425
BIGNUM
*bn = item->
vals
;
426
while
(loop++ <
BN_CTX_POOL_SIZE
)
427
{
428
if
(bn->
d
)
BN_clear
(bn);
429
bn++;
430
}
431
item = item->
next
;
432
}
433
p->
current
= p->
head
;
434
p->
used
= 0;
435
}
436
#endif
437
438
static
BIGNUM
*BN_POOL_get(
BN_POOL
*p)
439
{
440
if
(p->
used
== p->
size
)
441
{
442
BIGNUM
*bn;
443
unsigned
int
loop = 0;
444
BN_POOL_ITEM
*item =
clBnAlloc
(
"BN_POOL_get"
,
sizeof
(
BN_POOL_ITEM
));
445
if
(!item)
return
NULL;
446
/* Initialise the structure */
447
bn = item->
vals
;
448
while
(loop++ <
BN_CTX_POOL_SIZE
)
449
BN_init
(bn++);
450
item->
prev
= p->
tail
;
451
item->
next
= NULL;
452
/* Link it in */
453
if
(!p->
head
)
454
p->
head
= p->
current
= p->
tail
= item;
455
else
456
{
457
p->
tail
->
next
= item;
458
p->
tail
= item;
459
p->
current
= item;
460
}
461
p->
size
+=
BN_CTX_POOL_SIZE
;
462
p->
used
++;
463
/* Return the first bignum from the new pool */
464
return
item->
vals
;
465
}
466
if
(!p->
used
)
467
p->
current
= p->
head
;
468
else
if
((p->
used
%
BN_CTX_POOL_SIZE
) == 0)
469
p->
current
= p->
current
->
next
;
470
return
p->
current
->
vals
+ ((p->
used
++) %
BN_CTX_POOL_SIZE
);
471
}
472
473
static
void
BN_POOL_release(
BN_POOL
*p,
unsigned
int
num)
474
{
475
unsigned
int
offset
= (p->
used
- 1) %
BN_CTX_POOL_SIZE
;
476
p->
used
-= num;
477
while
(num--)
478
{
479
bn_check_top
(p->
current
->
vals
+ offset);
480
if
(!offset)
481
{
482
offset =
BN_CTX_POOL_SIZE
- 1;
483
p->
current
= p->
current
->
prev
;
484
}
485
else
486
offset--;
487
}
488
}
489
Generated on Thu Jan 10 2013 10:00:43 for cryptlib by
1.8.2