← Back to branch summary

~ubuntu-branches/ubuntu/hardy/openssl/hardy-security

« back to all changes in this revision

Viewing changes to crypto/bn/bn_sqrt.c

  • Committer: Bazaar Package Importer
  • Author(s): Kurt Roeckx
  • Date: 2005-12-13 21:37:42 UTC
  • mfrom: (1.1.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20051213213742-7em5nrw5c7ceegyd
Tags: 0.9.8a-5
http://bugs.debian.org/335912
Stop ssh from crashing randomly on sparc (Closes: #335912)
Patch from upstream cvs.

Show diffs side-by-side

added added

removed removed

Lines of Context:
crypto/bn/bn_sqrt.c
1
 
/* crypto/bn/bn_mod.c */
 
1
/* crypto/bn/bn_sqrt.c */
2
2
/* Written by Lenka Fibikova <fibikova@exp-math.uni-essen.de>
3
3
 * and Bodo Moeller for the OpenSSL project. */
4
4
/* ====================================================================
65
65
 * using the Tonelli/Shanks algorithm (cf. Henri Cohen, "A Course
66
66
 * in Algebraic Computational Number Theory", algorithm 1.5.1).
67
67
 * 'p' must be prime!
68
 
 * If 'a' is not a square, this is not necessarily detected by
69
 
 * the algorithms; a bogus result must be expected in this case.
70
68
 */
71
69
        {
72
70
        BIGNUM *ret = in;
73
71
        int err = 1;
74
72
        int r;
75
 
        BIGNUM *b, *q, *t, *x, *y;
 
73
        BIGNUM *A, *b, *q, *t, *x, *y;
76
74
        int e, i, j;
77
75
        
78
76
        if (!BN_is_odd(p) || BN_abs_is_word(p, 1))
85
83
                                goto end;
86
84
                        if (!BN_set_word(ret, BN_is_bit_set(a, 0)))
87
85
                                {
88
 
                                BN_free(ret);
 
86
                                if (ret != in)
 
87
                                        BN_free(ret);
89
88
                                return NULL;
90
89
                                }
 
90
                        bn_check_top(ret);
91
91
                        return ret;
92
92
                        }
93
93
 
103
103
                        goto end;
104
104
                if (!BN_set_word(ret, BN_is_one(a)))
105
105
                        {
106
 
                        BN_free(ret);
 
106
                        if (ret != in)
 
107
                                BN_free(ret);
107
108
                        return NULL;
108
109
                        }
 
110
                bn_check_top(ret);
109
111
                return ret;
110
112
                }
111
113
 
112
 
#if 0 /* if BN_mod_sqrt is used with correct input, this just wastes time */
113
 
        r = BN_kronecker(a, p, ctx);
114
 
        if (r < -1) return NULL;
115
 
        if (r == -1)
116
 
                {
117
 
                BNerr(BN_F_BN_MOD_SQRT, BN_R_NOT_A_SQUARE);
118
 
                return(NULL);
119
 
                }
120
 
#endif
121
 
 
122
114
        BN_CTX_start(ctx);
 
115
        A = BN_CTX_get(ctx);
123
116
        b = BN_CTX_get(ctx);
124
117
        q = BN_CTX_get(ctx);
125
118
        t = BN_CTX_get(ctx);
131
124
                ret = BN_new();
132
125
        if (ret == NULL) goto end;
133
126
 
 
127
        /* A = a mod p */
 
128
        if (!BN_nnmod(A, a, p, ctx)) goto end;
 
129
 
134
130
        /* now write  |p| - 1  as  2^e*q  where  q  is odd */
135
131
        e = 1;
136
132
        while (!BN_is_bit_set(p, e))
149
145
                if (!BN_rshift(q, p, 2)) goto end;
150
146
                q->neg = 0;
151
147
                if (!BN_add_word(q, 1)) goto end;
152
 
                if (!BN_mod_exp(ret, a, q, p, ctx)) goto end;
 
148
                if (!BN_mod_exp(ret, A, q, p, ctx)) goto end;
153
149
                err = 0;
154
 
                goto end;
 
150
                goto vrfy;
155
151
                }
156
152
        
157
153
        if (e == 2)
182
178
                 * November 1992.)
183
179
                 */
184
180
 
185
 
                /* make sure that  a  is reduced modulo p */
186
 
                if (a->neg || BN_ucmp(a, p) >= 0)
187
 
                        {
188
 
                        if (!BN_nnmod(x, a, p, ctx)) goto end;
189
 
                        a = x; /* use x as temporary variable */
190
 
                        }
191
 
 
192
181
                /* t := 2*a */
193
 
                if (!BN_mod_lshift1_quick(t, a, p)) goto end;
 
182
                if (!BN_mod_lshift1_quick(t, A, p)) goto end;
194
183
 
195
184
                /* b := (2*a)^((|p|-5)/8) */
196
185
                if (!BN_rshift(q, p, 3)) goto end;
205
194
                if (!BN_sub_word(t, 1)) goto end;
206
195
 
207
196
                /* x = a*b*t */
208
 
                if (!BN_mod_mul(x, a, b, p, ctx)) goto end;
 
197
                if (!BN_mod_mul(x, A, b, p, ctx)) goto end;
209
198
                if (!BN_mod_mul(x, x, t, p, ctx)) goto end;
210
199
 
211
200
                if (!BN_copy(ret, x)) goto end;
212
201
                err = 0;
213
 
                goto end;
 
202
                goto vrfy;
214
203
                }
215
204
        
216
205
        /* e > 2, so we really have to use the Tonelli/Shanks algorithm.
297
286
        /* x := a^((q-1)/2) */
298
287
        if (BN_is_zero(t)) /* special case: p = 2^e + 1 */
299
288
                {
300
 
                if (!BN_nnmod(t, a, p, ctx)) goto end;
 
289
                if (!BN_nnmod(t, A, p, ctx)) goto end;
301
290
                if (BN_is_zero(t))
302
291
                        {
303
292
                        /* special case: a == 0  (mod p) */
304
 
                        if (!BN_zero(ret)) goto end;
 
293
                        BN_zero(ret);
305
294
                        err = 0;
306
295
                        goto end;
307
296
                        }
310
299
                }
311
300
        else
312
301
                {
313
 
                if (!BN_mod_exp(x, a, t, p, ctx)) goto end;
 
302
                if (!BN_mod_exp(x, A, t, p, ctx)) goto end;
314
303
                if (BN_is_zero(x))
315
304
                        {
316
305
                        /* special case: a == 0  (mod p) */
317
 
                        if (!BN_zero(ret)) goto end;
 
306
                        BN_zero(ret);
318
307
                        err = 0;
319
308
                        goto end;
320
309
                        }
322
311
 
323
312
        /* b := a*x^2  (= a^q) */
324
313
        if (!BN_mod_sqr(b, x, p, ctx)) goto end;
325
 
        if (!BN_mod_mul(b, b, a, p, ctx)) goto end;
 
314
        if (!BN_mod_mul(b, b, A, p, ctx)) goto end;
326
315
        
327
316
        /* x := a*x    (= a^((q+1)/2)) */
328
 
        if (!BN_mod_mul(x, x, a, p, ctx)) goto end;
 
317
        if (!BN_mod_mul(x, x, A, p, ctx)) goto end;
329
318
 
330
319
        while (1)
331
320
                {
342
331
                        {
343
332
                        if (!BN_copy(ret, x)) goto end;
344
333
                        err = 0;
345
 
                        goto end;
 
334
                        goto vrfy;
346
335
                        }
347
336
 
348
337
 
373
362
                e = i;
374
363
                }
375
364
 
 
365
 vrfy:
 
366
        if (!err)
 
367
                {
 
368
                /* verify the result -- the input might have been not a square
 
369
                 * (test added in 0.9.8) */
 
370
                
 
371
                if (!BN_mod_sqr(x, ret, p, ctx))
 
372
                        err = 1;
 
373
                
 
374
                if (!err && 0 != BN_cmp(x, A))
 
375
                        {
 
376
                        BNerr(BN_F_BN_MOD_SQRT, BN_R_NOT_A_SQUARE);
 
377
                        err = 1;
 
378
                        }
 
379
                }
 
380
 
376
381
 end:
377
382
        if (err)
378
383
                {
383
388
                ret = NULL;
384
389
                }
385
390
        BN_CTX_end(ctx);
 
391
        bn_check_top(ret);
386
392
        return ret;
387
393
        }