← Back to branch summary

~ubuntu-branches/ubuntu/lucid/openssl/lucid

« back to all changes in this revision

Viewing changes to crypto/bn/bn_x931p.c

  • Committer: Bazaar Package Importer
  • Author(s): Nicolas Valcárcel Scerpella (Canonical)
  • Date: 2009-12-06 20:16:24 UTC
  • mfrom: (11.1.9 sid)
  • Revision ID: james.westby@ubuntu.com-20091206201624-u126qjpqm2n2uuhu
Tags: 0.9.8k-7ubuntu1
https://launchpad.net/bugs/493392
* Merge from debian unstable, remaining changes (LP: #493392):
  - Link using -Bsymbolic-functions
  - Add support for lpia
  - Disable SSLv2 during compile
  - Ship documentation in openssl-doc, suggested by the package.
  - Use a different priority for libssl0.9.8/restart-services
    depending on whether a desktop, or server dist-upgrade is being
    performed.
  - Display a system restart required notification bubble on libssl0.9.8
    upgrade.
  - Replace duplicate files in the doc directory with symlinks.
  - Move runtime libraries to /lib, for the benefit of wpasupplicant
* Strip the patches out of the source into quilt patches
* Disable CVE-2009-3555.patch

Show diffs side-by-side

added added

removed removed

Lines of Context:
crypto/bn/bn_x931p.c
 
1
/* bn_x931p.c */
 
2
/* Written by Dr Stephen N Henson (steve@openssl.org) for the OpenSSL
 
3
 * project 2005.
 
4
 */
 
5
/* ====================================================================
 
6
 * Copyright (c) 2005 The OpenSSL Project.  All rights reserved.
 
7
 *
 
8
 * Redistribution and use in source and binary forms, with or without
 
9
 * modification, are permitted provided that the following conditions
 
10
 * are met:
 
11
 *
 
12
 * 1. Redistributions of source code must retain the above copyright
 
13
 *    notice, this list of conditions and the following disclaimer. 
 
14
 *
 
15
 * 2. Redistributions in binary form must reproduce the above copyright
 
16
 *    notice, this list of conditions and the following disclaimer in
 
17
 *    the documentation and/or other materials provided with the
 
18
 *    distribution.
 
19
 *
 
20
 * 3. All advertising materials mentioning features or use of this
 
21
 *    software must display the following acknowledgment:
 
22
 *    "This product includes software developed by the OpenSSL Project
 
23
 *    for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)"
 
24
 *
 
25
 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
 
26
 *    endorse or promote products derived from this software without
 
27
 *    prior written permission. For written permission, please contact
 
28
 *    licensing@OpenSSL.org.
 
29
 *
 
30
 * 5. Products derived from this software may not be called "OpenSSL"
 
31
 *    nor may "OpenSSL" appear in their names without prior written
 
32
 *    permission of the OpenSSL Project.
 
33
 *
 
34
 * 6. Redistributions of any form whatsoever must retain the following
 
35
 *    acknowledgment:
 
36
 *    "This product includes software developed by the OpenSSL Project
 
37
 *    for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)"
 
38
 *
 
39
 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
 
40
 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 
41
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 
42
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
 
43
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 
44
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 
45
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 
46
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 
47
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 
48
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 
49
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 
50
 * OF THE POSSIBILITY OF SUCH DAMAGE.
 
51
 * ====================================================================
 
52
 *
 
53
 * This product includes cryptographic software written by Eric Young
 
54
 * (eay@cryptsoft.com).  This product includes software written by Tim
 
55
 * Hudson (tjh@cryptsoft.com).
 
56
 *
 
57
 */
 
58
 
 
59
#include <stdio.h>
 
60
#include <openssl/bn.h>
 
61
 
 
62
/* X9.31 routines for prime derivation */
 
63
 
 
64
/* X9.31 prime derivation. This is used to generate the primes pi
 
65
 * (p1, p2, q1, q2) from a parameter Xpi by checking successive odd
 
66
 * integers.
 
67
 */
 
68
 
 
69
static int bn_x931_derive_pi(BIGNUM *pi, const BIGNUM *Xpi, BN_CTX *ctx,
 
70
                        BN_GENCB *cb)
 
71
        {
 
72
        int i = 0;
 
73
        if (!BN_copy(pi, Xpi))
 
74
                return 0;
 
75
        if (!BN_is_odd(pi) && !BN_add_word(pi, 1))
 
76
                return 0;
 
77
        for(;;)
 
78
                {
 
79
                i++;
 
80
                BN_GENCB_call(cb, 0, i);
 
81
                /* NB 27 MR is specificed in X9.31 */
 
82
                if (BN_is_prime_fasttest_ex(pi, 27, ctx, 1, cb))
 
83
                        break;
 
84
                if (!BN_add_word(pi, 2))
 
85
                        return 0;
 
86
                }
 
87
        BN_GENCB_call(cb, 2, i);
 
88
        return 1;
 
89
        }
 
90
 
 
91
/* This is the main X9.31 prime derivation function. From parameters
 
92
 * Xp1, Xp2 and Xp derive the prime p. If the parameters p1 or p2 are
 
93
 * not NULL they will be returned too: this is needed for testing.
 
94
 */
 
95
 
 
96
int BN_X931_derive_prime_ex(BIGNUM *p, BIGNUM *p1, BIGNUM *p2,
 
97
                        const BIGNUM *Xp, const BIGNUM *Xp1, const BIGNUM *Xp2,
 
98
                        const BIGNUM *e, BN_CTX *ctx, BN_GENCB *cb)
 
99
        {
 
100
        int ret = 0;
 
101
 
 
102
        BIGNUM *t, *p1p2, *pm1;
 
103
 
 
104
        /* Only even e supported */
 
105
        if (!BN_is_odd(e))
 
106
                return 0;
 
107
 
 
108
        BN_CTX_start(ctx);
 
109
        if (!p1)
 
110
                p1 = BN_CTX_get(ctx);
 
111
 
 
112
        if (!p2)
 
113
                p2 = BN_CTX_get(ctx);
 
114
 
 
115
        t = BN_CTX_get(ctx);
 
116
 
 
117
        p1p2 = BN_CTX_get(ctx);
 
118
 
 
119
        pm1 = BN_CTX_get(ctx);
 
120
 
 
121
        if (!bn_x931_derive_pi(p1, Xp1, ctx, cb))
 
122
                goto err;
 
123
 
 
124
        if (!bn_x931_derive_pi(p2, Xp2, ctx, cb))
 
125
                goto err;
 
126
 
 
127
        if (!BN_mul(p1p2, p1, p2, ctx))
 
128
                goto err;
 
129
 
 
130
        /* First set p to value of Rp */
 
131
 
 
132
        if (!BN_mod_inverse(p, p2, p1, ctx))
 
133
                goto err;
 
134
 
 
135
        if (!BN_mul(p, p, p2, ctx))
 
136
                goto err;
 
137
 
 
138
        if (!BN_mod_inverse(t, p1, p2, ctx))
 
139
                goto err;
 
140
 
 
141
        if (!BN_mul(t, t, p1, ctx))
 
142
                goto err;
 
143
 
 
144
        if (!BN_sub(p, p, t))
 
145
                goto err;
 
146
 
 
147
        if (p->neg && !BN_add(p, p, p1p2))
 
148
                goto err;
 
149
 
 
150
        /* p now equals Rp */
 
151
 
 
152
        if (!BN_mod_sub(p, p, Xp, p1p2, ctx))
 
153
                goto err;
 
154
 
 
155
        if (!BN_add(p, p, Xp))
 
156
                goto err;
 
157
 
 
158
        /* p now equals Yp0 */
 
159
 
 
160
        for (;;)
 
161
                {
 
162
                int i = 1;
 
163
                BN_GENCB_call(cb, 0, i++);
 
164
                if (!BN_copy(pm1, p))
 
165
                        goto err;
 
166
                if (!BN_sub_word(pm1, 1))
 
167
                        goto err;
 
168
                if (!BN_gcd(t, pm1, e, ctx))
 
169
                        goto err;
 
170
                if (BN_is_one(t)
 
171
                /* X9.31 specifies 8 MR and 1 Lucas test or any prime test
 
172
                 * offering similar or better guarantees 50 MR is considerably 
 
173
                 * better.
 
174
                 */
 
175
                        && BN_is_prime_fasttest_ex(p, 50, ctx, 1, cb))
 
176
                        break;
 
177
                if (!BN_add(p, p, p1p2))
 
178
                        goto err;
 
179
                }
 
180
 
 
181
        BN_GENCB_call(cb, 3, 0);
 
182
 
 
183
        ret = 1;
 
184
 
 
185
        err:
 
186
 
 
187
        BN_CTX_end(ctx);
 
188
 
 
189
        return ret;
 
190
        }
 
191
 
 
192
/* Generate pair of paramters Xp, Xq for X9.31 prime generation.
 
193
 * Note: nbits paramter is sum of number of bits in both.
 
194
 */
 
195
 
 
196
int BN_X931_generate_Xpq(BIGNUM *Xp, BIGNUM *Xq, int nbits, BN_CTX *ctx)
 
197
        {
 
198
        BIGNUM *t;
 
199
        int i;
 
200
        /* Number of bits for each prime is of the form
 
201
         * 512+128s for s = 0, 1, ...
 
202
         */
 
203
        if ((nbits < 1024) || (nbits & 0xff))
 
204
                return 0;
 
205
        nbits >>= 1;
 
206
        /* The random value Xp must be between sqrt(2) * 2^(nbits-1) and
 
207
         * 2^nbits - 1. By setting the top two bits we ensure that the lower
 
208
         * bound is exceeded.
 
209
         */
 
210
        if (!BN_rand(Xp, nbits, 1, 0))
 
211
                return 0;
 
212
 
 
213
        BN_CTX_start(ctx);
 
214
        t = BN_CTX_get(ctx);
 
215
 
 
216
        for (i = 0; i < 1000; i++)
 
217
                {
 
218
                if (!BN_rand(Xq, nbits, 1, 0))
 
219
                        return 0;
 
220
                /* Check that |Xp - Xq| > 2^(nbits - 100) */
 
221
                BN_sub(t, Xp, Xq);
 
222
                if (BN_num_bits(t) > (nbits - 100))
 
223
                        break;
 
224
                }
 
225
 
 
226
        BN_CTX_end(ctx);
 
227
 
 
228
        if (i < 1000)
 
229
                return 1;
 
230
 
 
231
        return 0;
 
232
 
 
233
        }
 
234
 
 
235
/* Generate primes using X9.31 algorithm. Of the values p, p1, p2, Xp1
 
236
 * and Xp2 only 'p' needs to be non-NULL. If any of the others are not NULL
 
237
 * the relevant parameter will be stored in it.
 
238
 *
 
239
 * Due to the fact that |Xp - Xq| > 2^(nbits - 100) must be satisfied Xp and Xq
 
240
 * are generated using the previous function and supplied as input.
 
241
 */
 
242
 
 
243
int BN_X931_generate_prime_ex(BIGNUM *p, BIGNUM *p1, BIGNUM *p2,
 
244
                        BIGNUM *Xp1, BIGNUM *Xp2,
 
245
                        const BIGNUM *Xp,
 
246
                        const BIGNUM *e, BN_CTX *ctx,
 
247
                        BN_GENCB *cb)
 
248
        {
 
249
        int ret = 0;
 
250
 
 
251
        BN_CTX_start(ctx);
 
252
        if (!Xp1)
 
253
                Xp1 = BN_CTX_get(ctx);
 
254
        if (!Xp2)
 
255
                Xp2 = BN_CTX_get(ctx);
 
256
 
 
257
        if (!BN_rand(Xp1, 101, 0, 0))
 
258
                goto error;
 
259
        if (!BN_rand(Xp2, 101, 0, 0))
 
260
                goto error;
 
261
        if (!BN_X931_derive_prime_ex(p, p1, p2, Xp, Xp1, Xp2, e, ctx, cb))
 
262
                goto error;
 
263
 
 
264
        ret = 1;
 
265
 
 
266
        error:
 
267
        BN_CTX_end(ctx);
 
268
 
 
269
        return ret;
 
270
 
 
271
        }
 
272