← Back to branch summary

~ubuntu-branches/ubuntu/utopic/openssl/utopic-security

« back to all changes in this revision

Viewing changes to .pc/CVE-2014-3570.patch/crypto/bn/bntest.c

  • Committer: Package Import Robot
  • Author(s): Marc Deslauriers
  • Date: 2015-01-09 09:47:17 UTC
  • Revision ID: package-import@ubuntu.com-20150109094717-8etwd95qlawwgkc7
Tags: 1.0.1f-1ubuntu9.1
* SECURITY UPDATE: denial of service via unexpected handshake when
  no-ssl3 build option is used (not the default)
  - debian/patches/CVE-2014-3569.patch: keep the old method for now in
    ssl/s23_srvr.c.
  - CVE-2014-3569
* SECURITY UPDATE: bignum squaring may produce incorrect results
  - debian/patches/CVE-2014-3570.patch: fix bignum logic in
    crypto/bn/asm/mips.pl, crypto/bn/asm/x86_64-gcc.c,
    crypto/bn/bn_asm.c, removed crypto/bn/asm/mips3.s, added test to
    crypto/bn/bntest.c.
  - CVE-2014-3570
* SECURITY UPDATE: DTLS segmentation fault in dtls1_get_record
  - debian/patches/CVE-2014-3571-1.patch: fix crash in ssl/d1_pkt.c,
    ssl/s3_pkt.c.
  - debian/patches/CVE-2014-3571-2.patch: make code more obvious in
    ssl/d1_pkt.c.
  - CVE-2014-3571
* SECURITY UPDATE: ECDHE silently downgrades to ECDH [Client]
  - debian/patches/CVE-2014-3572.patch: don't skip server key exchange in
    ssl/s3_clnt.c.
  - CVE-2014-3572
* SECURITY UPDATE: certificate fingerprints can be modified
  - debian/patches/CVE-2014-8275.patch: fix various fingerprint issues in
    crypto/asn1/a_bitstr.c, crypto/asn1/a_type.c, crypto/asn1/a_verify.c,
    crypto/asn1/asn1.h, crypto/asn1/asn1_err.c, crypto/asn1/x_algor.c,
    crypto/dsa/dsa_asn1.c, crypto/ecdsa/ecs_vrf.c, crypto/x509/x509.h,
    crypto/x509/x_all.c.
  - CVE-2014-8275
* SECURITY UPDATE: RSA silently downgrades to EXPORT_RSA [Client]
  - debian/patches/CVE-2015-0204.patch: only allow ephemeral RSA keys in
    export ciphersuites in ssl/d1_srvr.c, ssl/s3_clnt.c, ssl/s3_srvr.c,
    ssl/ssl.h, adjust documentation in doc/ssl/SSL_CTX_set_options.pod,
    doc/ssl/SSL_CTX_set_tmp_rsa_callback.pod.
  - CVE-2015-0204
* SECURITY UPDATE: DH client certificates accepted without verification
  - debian/patches/CVE-2015-0205.patch: prevent use of DH client
    certificates without sending certificate verify message in
    ssl/s3_srvr.c.
  - CVE-2015-0205
* SECURITY UPDATE: DTLS memory leak in dtls1_buffer_record
  - debian/patches/CVE-2015-0206.patch: properly handle failures in
    ssl/d1_pkt.c.
  - CVE-2015-0206

Show diffs side-by-side

added added

removed removed

Lines of Context:
.pc/CVE-2014-3570.patch/crypto/bn/bntest.c
 
1
/* crypto/bn/bntest.c */
 
2
/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
 
3
 * All rights reserved.
 
4
 *
 
5
 * This package is an SSL implementation written
 
6
 * by Eric Young (eay@cryptsoft.com).
 
7
 * The implementation was written so as to conform with Netscapes SSL.
 
8
 * 
 
9
 * This library is free for commercial and non-commercial use as long as
 
10
 * the following conditions are aheared to.  The following conditions
 
11
 * apply to all code found in this distribution, be it the RC4, RSA,
 
12
 * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
 
13
 * included with this distribution is covered by the same copyright terms
 
14
 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
 
15
 * 
 
16
 * Copyright remains Eric Young's, and as such any Copyright notices in
 
17
 * the code are not to be removed.
 
18
 * If this package is used in a product, Eric Young should be given attribution
 
19
 * as the author of the parts of the library used.
 
20
 * This can be in the form of a textual message at program startup or
 
21
 * in documentation (online or textual) provided with the package.
 
22
 * 
 
23
 * Redistribution and use in source and binary forms, with or without
 
24
 * modification, are permitted provided that the following conditions
 
25
 * are met:
 
26
 * 1. Redistributions of source code must retain the copyright
 
27
 *    notice, this list of conditions and the following disclaimer.
 
28
 * 2. Redistributions in binary form must reproduce the above copyright
 
29
 *    notice, this list of conditions and the following disclaimer in the
 
30
 *    documentation and/or other materials provided with the distribution.
 
31
 * 3. All advertising materials mentioning features or use of this software
 
32
 *    must display the following acknowledgement:
 
33
 *    "This product includes cryptographic software written by
 
34
 *     Eric Young (eay@cryptsoft.com)"
 
35
 *    The word 'cryptographic' can be left out if the rouines from the library
 
36
 *    being used are not cryptographic related :-).
 
37
 * 4. If you include any Windows specific code (or a derivative thereof) from 
 
38
 *    the apps directory (application code) you must include an acknowledgement:
 
39
 *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
 
40
 * 
 
41
 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
 
42
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 
43
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 
44
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 
45
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 
46
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 
47
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 
48
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 
49
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 
50
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 
51
 * SUCH DAMAGE.
 
52
 * 
 
53
 * The licence and distribution terms for any publically available version or
 
54
 * derivative of this code cannot be changed.  i.e. this code cannot simply be
 
55
 * copied and put under another distribution licence
 
56
 * [including the GNU Public Licence.]
 
57
 */
 
58
/* ====================================================================
 
59
 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
 
60
 *
 
61
 * Portions of the attached software ("Contribution") are developed by 
 
62
 * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project.
 
63
 *
 
64
 * The Contribution is licensed pursuant to the Eric Young open source
 
65
 * license provided above.
 
66
 *
 
67
 * The binary polynomial arithmetic software is originally written by 
 
68
 * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems Laboratories.
 
69
 *
 
70
 */
 
71
 
 
72
/* Until the key-gen callbacks are modified to use newer prototypes, we allow
 
73
 * deprecated functions for openssl-internal code */
 
74
#ifdef OPENSSL_NO_DEPRECATED
 
75
#undef OPENSSL_NO_DEPRECATED
 
76
#endif
 
77
 
 
78
#include <stdio.h>
 
79
#include <stdlib.h>
 
80
#include <string.h>
 
81
 
 
82
#include "e_os.h"
 
83
 
 
84
#include <openssl/bio.h>
 
85
#include <openssl/bn.h>
 
86
#include <openssl/rand.h>
 
87
#include <openssl/x509.h>
 
88
#include <openssl/err.h>
 
89
 
 
90
const int num0 = 100; /* number of tests */
 
91
const int num1 = 50;  /* additional tests for some functions */
 
92
const int num2 = 5;   /* number of tests for slow functions */
 
93
 
 
94
int test_add(BIO *bp);
 
95
int test_sub(BIO *bp);
 
96
int test_lshift1(BIO *bp);
 
97
int test_lshift(BIO *bp,BN_CTX *ctx,BIGNUM *a_);
 
98
int test_rshift1(BIO *bp);
 
99
int test_rshift(BIO *bp,BN_CTX *ctx);
 
100
int test_div(BIO *bp,BN_CTX *ctx);
 
101
int test_div_word(BIO *bp);
 
102
int test_div_recp(BIO *bp,BN_CTX *ctx);
 
103
int test_mul(BIO *bp);
 
104
int test_sqr(BIO *bp,BN_CTX *ctx);
 
105
int test_mont(BIO *bp,BN_CTX *ctx);
 
106
int test_mod(BIO *bp,BN_CTX *ctx);
 
107
int test_mod_mul(BIO *bp,BN_CTX *ctx);
 
108
int test_mod_exp(BIO *bp,BN_CTX *ctx);
 
109
int test_mod_exp_mont_consttime(BIO *bp,BN_CTX *ctx);
 
110
int test_exp(BIO *bp,BN_CTX *ctx);
 
111
int test_gf2m_add(BIO *bp);
 
112
int test_gf2m_mod(BIO *bp);
 
113
int test_gf2m_mod_mul(BIO *bp,BN_CTX *ctx);
 
114
int test_gf2m_mod_sqr(BIO *bp,BN_CTX *ctx);
 
115
int test_gf2m_mod_inv(BIO *bp,BN_CTX *ctx);
 
116
int test_gf2m_mod_div(BIO *bp,BN_CTX *ctx);
 
117
int test_gf2m_mod_exp(BIO *bp,BN_CTX *ctx);
 
118
int test_gf2m_mod_sqrt(BIO *bp,BN_CTX *ctx);
 
119
int test_gf2m_mod_solve_quad(BIO *bp,BN_CTX *ctx);
 
120
int test_kron(BIO *bp,BN_CTX *ctx);
 
121
int test_sqrt(BIO *bp,BN_CTX *ctx);
 
122
int rand_neg(void);
 
123
static int results=0;
 
124
 
 
125
static unsigned char lst[]="\xC6\x4F\x43\x04\x2A\xEA\xCA\x6E\x58\x36\x80\x5B\xE8\xC9"
 
126
"\x9B\x04\x5D\x48\x36\xC2\xFD\x16\xC9\x64\xF0";
 
127
 
 
128
static const char rnd_seed[] = "string to make the random number generator think it has entropy";
 
129
 
 
130
static void message(BIO *out, char *m)
 
131
        {
 
132
        fprintf(stderr, "test %s\n", m);
 
133
        BIO_puts(out, "print \"test ");
 
134
        BIO_puts(out, m);
 
135
        BIO_puts(out, "\\n\"\n");
 
136
        }
 
137
 
 
138
int main(int argc, char *argv[])
 
139
        {
 
140
        BN_CTX *ctx;
 
141
        BIO *out;
 
142
        char *outfile=NULL;
 
143
 
 
144
        results = 0;
 
145
 
 
146
        RAND_seed(rnd_seed, sizeof rnd_seed); /* or BN_generate_prime may fail */
 
147
 
 
148
        argc--;
 
149
        argv++;
 
150
        while (argc >= 1)
 
151
                {
 
152
                if (strcmp(*argv,"-results") == 0)
 
153
                        results=1;
 
154
                else if (strcmp(*argv,"-out") == 0)
 
155
                        {
 
156
                        if (--argc < 1) break;
 
157
                        outfile= *(++argv);
 
158
                        }
 
159
                argc--;
 
160
                argv++;
 
161
                }
 
162
 
 
163
 
 
164
        ctx=BN_CTX_new();
 
165
        if (ctx == NULL) EXIT(1);
 
166
 
 
167
        out=BIO_new(BIO_s_file());
 
168
        if (out == NULL) EXIT(1);
 
169
        if (outfile == NULL)
 
170
                {
 
171
                BIO_set_fp(out,stdout,BIO_NOCLOSE);
 
172
                }
 
173
        else
 
174
                {
 
175
                if (!BIO_write_filename(out,outfile))
 
176
                        {
 
177
                        perror(outfile);
 
178
                        EXIT(1);
 
179
                        }
 
180
                }
 
181
 
 
182
        if (!results)
 
183
                BIO_puts(out,"obase=16\nibase=16\n");
 
184
 
 
185
        message(out,"BN_add");
 
186
        if (!test_add(out)) goto err;
 
187
        (void)BIO_flush(out);
 
188
 
 
189
        message(out,"BN_sub");
 
190
        if (!test_sub(out)) goto err;
 
191
        (void)BIO_flush(out);
 
192
 
 
193
        message(out,"BN_lshift1");
 
194
        if (!test_lshift1(out)) goto err;
 
195
        (void)BIO_flush(out);
 
196
 
 
197
        message(out,"BN_lshift (fixed)");
 
198
        if (!test_lshift(out,ctx,BN_bin2bn(lst,sizeof(lst)-1,NULL)))
 
199
            goto err;
 
200
        (void)BIO_flush(out);
 
201
 
 
202
        message(out,"BN_lshift");
 
203
        if (!test_lshift(out,ctx,NULL)) goto err;
 
204
        (void)BIO_flush(out);
 
205
 
 
206
        message(out,"BN_rshift1");
 
207
        if (!test_rshift1(out)) goto err;
 
208
        (void)BIO_flush(out);
 
209
 
 
210
        message(out,"BN_rshift");
 
211
        if (!test_rshift(out,ctx)) goto err;
 
212
        (void)BIO_flush(out);
 
213
 
 
214
        message(out,"BN_sqr");
 
215
        if (!test_sqr(out,ctx)) goto err;
 
216
        (void)BIO_flush(out);
 
217
 
 
218
        message(out,"BN_mul");
 
219
        if (!test_mul(out)) goto err;
 
220
        (void)BIO_flush(out);
 
221
 
 
222
        message(out,"BN_div");
 
223
        if (!test_div(out,ctx)) goto err;
 
224
        (void)BIO_flush(out);
 
225
 
 
226
        message(out,"BN_div_word");
 
227
        if (!test_div_word(out)) goto err;
 
228
        (void)BIO_flush(out);
 
229
 
 
230
        message(out,"BN_div_recp");
 
231
        if (!test_div_recp(out,ctx)) goto err;
 
232
        (void)BIO_flush(out);
 
233
 
 
234
        message(out,"BN_mod");
 
235
        if (!test_mod(out,ctx)) goto err;
 
236
        (void)BIO_flush(out);
 
237
 
 
238
        message(out,"BN_mod_mul");
 
239
        if (!test_mod_mul(out,ctx)) goto err;
 
240
        (void)BIO_flush(out);
 
241
 
 
242
        message(out,"BN_mont");
 
243
        if (!test_mont(out,ctx)) goto err;
 
244
        (void)BIO_flush(out);
 
245
 
 
246
        message(out,"BN_mod_exp");
 
247
        if (!test_mod_exp(out,ctx)) goto err;
 
248
        (void)BIO_flush(out);
 
249
 
 
250
        message(out,"BN_mod_exp_mont_consttime");
 
251
        if (!test_mod_exp_mont_consttime(out,ctx)) goto err;
 
252
        (void)BIO_flush(out);
 
253
 
 
254
        message(out,"BN_exp");
 
255
        if (!test_exp(out,ctx)) goto err;
 
256
        (void)BIO_flush(out);
 
257
 
 
258
        message(out,"BN_kronecker");
 
259
        if (!test_kron(out,ctx)) goto err;
 
260
        (void)BIO_flush(out);
 
261
 
 
262
        message(out,"BN_mod_sqrt");
 
263
        if (!test_sqrt(out,ctx)) goto err;
 
264
        (void)BIO_flush(out);
 
265
#ifndef OPENSSL_NO_EC2M
 
266
        message(out,"BN_GF2m_add");
 
267
        if (!test_gf2m_add(out)) goto err;
 
268
        (void)BIO_flush(out);
 
269
 
 
270
        message(out,"BN_GF2m_mod");
 
271
        if (!test_gf2m_mod(out)) goto err;
 
272
        (void)BIO_flush(out);
 
273
 
 
274
        message(out,"BN_GF2m_mod_mul");
 
275
        if (!test_gf2m_mod_mul(out,ctx)) goto err;
 
276
        (void)BIO_flush(out);
 
277
 
 
278
        message(out,"BN_GF2m_mod_sqr");
 
279
        if (!test_gf2m_mod_sqr(out,ctx)) goto err;
 
280
        (void)BIO_flush(out);
 
281
 
 
282
        message(out,"BN_GF2m_mod_inv");
 
283
        if (!test_gf2m_mod_inv(out,ctx)) goto err;
 
284
        (void)BIO_flush(out);
 
285
 
 
286
        message(out,"BN_GF2m_mod_div");
 
287
        if (!test_gf2m_mod_div(out,ctx)) goto err;
 
288
        (void)BIO_flush(out);
 
289
 
 
290
        message(out,"BN_GF2m_mod_exp");
 
291
        if (!test_gf2m_mod_exp(out,ctx)) goto err;
 
292
        (void)BIO_flush(out);
 
293
 
 
294
        message(out,"BN_GF2m_mod_sqrt");
 
295
        if (!test_gf2m_mod_sqrt(out,ctx)) goto err;
 
296
        (void)BIO_flush(out);
 
297
 
 
298
        message(out,"BN_GF2m_mod_solve_quad");
 
299
        if (!test_gf2m_mod_solve_quad(out,ctx)) goto err;
 
300
        (void)BIO_flush(out);
 
301
#endif
 
302
        BN_CTX_free(ctx);
 
303
        BIO_free(out);
 
304
 
 
305
/**/
 
306
        EXIT(0);
 
307
err:
 
308
        BIO_puts(out,"1\n"); /* make sure the Perl script fed by bc notices
 
309
                              * the failure, see test_bn in test/Makefile.ssl*/
 
310
        (void)BIO_flush(out);
 
311
        ERR_load_crypto_strings();
 
312
        ERR_print_errors_fp(stderr);
 
313
        EXIT(1);
 
314
        return(1);
 
315
        }
 
316
 
 
317
int test_add(BIO *bp)
 
318
        {
 
319
        BIGNUM a,b,c;
 
320
        int i;
 
321
 
 
322
        BN_init(&a);
 
323
        BN_init(&b);
 
324
        BN_init(&c);
 
325
 
 
326
        BN_bntest_rand(&a,512,0,0);
 
327
        for (i=0; i<num0; i++)
 
328
                {
 
329
                BN_bntest_rand(&b,450+i,0,0);
 
330
                a.neg=rand_neg();
 
331
                b.neg=rand_neg();
 
332
                BN_add(&c,&a,&b);
 
333
                if (bp != NULL)
 
334
                        {
 
335
                        if (!results)
 
336
                                {
 
337
                                BN_print(bp,&a);
 
338
                                BIO_puts(bp," + ");
 
339
                                BN_print(bp,&b);
 
340
                                BIO_puts(bp," - ");
 
341
                                }
 
342
                        BN_print(bp,&c);
 
343
                        BIO_puts(bp,"\n");
 
344
                        }
 
345
                a.neg=!a.neg;
 
346
                b.neg=!b.neg;
 
347
                BN_add(&c,&c,&b);
 
348
                BN_add(&c,&c,&a);
 
349
                if(!BN_is_zero(&c))
 
350
                    {
 
351
                    fprintf(stderr,"Add test failed!\n");
 
352
                    return 0;
 
353
                    }
 
354
                }
 
355
        BN_free(&a);
 
356
        BN_free(&b);
 
357
        BN_free(&c);
 
358
        return(1);
 
359
        }
 
360
 
 
361
int test_sub(BIO *bp)
 
362
        {
 
363
        BIGNUM a,b,c;
 
364
        int i;
 
365
 
 
366
        BN_init(&a);
 
367
        BN_init(&b);
 
368
        BN_init(&c);
 
369
 
 
370
        for (i=0; i<num0+num1; i++)
 
371
                {
 
372
                if (i < num1)
 
373
                        {
 
374
                        BN_bntest_rand(&a,512,0,0);
 
375
                        BN_copy(&b,&a);
 
376
                        if (BN_set_bit(&a,i)==0) return(0);
 
377
                        BN_add_word(&b,i);
 
378
                        }
 
379
                else
 
380
                        {
 
381
                        BN_bntest_rand(&b,400+i-num1,0,0);
 
382
                        a.neg=rand_neg();
 
383
                        b.neg=rand_neg();
 
384
                        }
 
385
                BN_sub(&c,&a,&b);
 
386
                if (bp != NULL)
 
387
                        {
 
388
                        if (!results)
 
389
                                {
 
390
                                BN_print(bp,&a);
 
391
                                BIO_puts(bp," - ");
 
392
                                BN_print(bp,&b);
 
393
                                BIO_puts(bp," - ");
 
394
                                }
 
395
                        BN_print(bp,&c);
 
396
                        BIO_puts(bp,"\n");
 
397
                        }
 
398
                BN_add(&c,&c,&b);
 
399
                BN_sub(&c,&c,&a);
 
400
                if(!BN_is_zero(&c))
 
401
                    {
 
402
                    fprintf(stderr,"Subtract test failed!\n");
 
403
                    return 0;
 
404
                    }
 
405
                }
 
406
        BN_free(&a);
 
407
        BN_free(&b);
 
408
        BN_free(&c);
 
409
        return(1);
 
410
        }
 
411
 
 
412
int test_div(BIO *bp, BN_CTX *ctx)
 
413
        {
 
414
        BIGNUM a,b,c,d,e;
 
415
        int i;
 
416
 
 
417
        BN_init(&a);
 
418
        BN_init(&b);
 
419
        BN_init(&c);
 
420
        BN_init(&d);
 
421
        BN_init(&e);
 
422
 
 
423
        for (i=0; i<num0+num1; i++)
 
424
                {
 
425
                if (i < num1)
 
426
                        {
 
427
                        BN_bntest_rand(&a,400,0,0);
 
428
                        BN_copy(&b,&a);
 
429
                        BN_lshift(&a,&a,i);
 
430
                        BN_add_word(&a,i);
 
431
                        }
 
432
                else
 
433
                        BN_bntest_rand(&b,50+3*(i-num1),0,0);
 
434
                a.neg=rand_neg();
 
435
                b.neg=rand_neg();
 
436
                BN_div(&d,&c,&a,&b,ctx);
 
437
                if (bp != NULL)
 
438
                        {
 
439
                        if (!results)
 
440
                                {
 
441
                                BN_print(bp,&a);
 
442
                                BIO_puts(bp," / ");
 
443
                                BN_print(bp,&b);
 
444
                                BIO_puts(bp," - ");
 
445
                                }
 
446
                        BN_print(bp,&d);
 
447
                        BIO_puts(bp,"\n");
 
448
 
 
449
                        if (!results)
 
450
                                {
 
451
                                BN_print(bp,&a);
 
452
                                BIO_puts(bp," % ");
 
453
                                BN_print(bp,&b);
 
454
                                BIO_puts(bp," - ");
 
455
                                }
 
456
                        BN_print(bp,&c);
 
457
                        BIO_puts(bp,"\n");
 
458
                        }
 
459
                BN_mul(&e,&d,&b,ctx);
 
460
                BN_add(&d,&e,&c);
 
461
                BN_sub(&d,&d,&a);
 
462
                if(!BN_is_zero(&d))
 
463
                    {
 
464
                    fprintf(stderr,"Division test failed!\n");
 
465
                    return 0;
 
466
                    }
 
467
                }
 
468
        BN_free(&a);
 
469
        BN_free(&b);
 
470
        BN_free(&c);
 
471
        BN_free(&d);
 
472
        BN_free(&e);
 
473
        return(1);
 
474
        }
 
475
 
 
476
static void print_word(BIO *bp,BN_ULONG w)
 
477
        {
 
478
#ifdef SIXTY_FOUR_BIT
 
479
        if (sizeof(w) > sizeof(unsigned long))
 
480
                {
 
481
                unsigned long   h=(unsigned long)(w>>32),
 
482
                                l=(unsigned long)(w);
 
483
 
 
484
                if (h)  BIO_printf(bp,"%lX%08lX",h,l);
 
485
                else    BIO_printf(bp,"%lX",l);
 
486
                return;
 
487
                }
 
488
#endif
 
489
        BIO_printf(bp,BN_HEX_FMT1,w);
 
490
        }
 
491
 
 
492
int test_div_word(BIO *bp)
 
493
        {
 
494
        BIGNUM   a,b;
 
495
        BN_ULONG r,s;
 
496
        int i;
 
497
 
 
498
        BN_init(&a);
 
499
        BN_init(&b);
 
500
 
 
501
        for (i=0; i<num0; i++)
 
502
                {
 
503
                do {
 
504
                        BN_bntest_rand(&a,512,-1,0);
 
505
                        BN_bntest_rand(&b,BN_BITS2,-1,0);
 
506
                        s = b.d[0];
 
507
                } while (!s);
 
508
 
 
509
                BN_copy(&b, &a);
 
510
                r = BN_div_word(&b, s);
 
511
 
 
512
                if (bp != NULL)
 
513
                        {
 
514
                        if (!results)
 
515
                                {
 
516
                                BN_print(bp,&a);
 
517
                                BIO_puts(bp," / ");
 
518
                                print_word(bp,s);
 
519
                                BIO_puts(bp," - ");
 
520
                                }
 
521
                        BN_print(bp,&b);
 
522
                        BIO_puts(bp,"\n");
 
523
 
 
524
                        if (!results)
 
525
                                {
 
526
                                BN_print(bp,&a);
 
527
                                BIO_puts(bp," % ");
 
528
                                print_word(bp,s);
 
529
                                BIO_puts(bp," - ");
 
530
                                }
 
531
                        print_word(bp,r);
 
532
                        BIO_puts(bp,"\n");
 
533
                        }
 
534
                BN_mul_word(&b,s);
 
535
                BN_add_word(&b,r);
 
536
                BN_sub(&b,&a,&b);
 
537
                if(!BN_is_zero(&b))
 
538
                    {
 
539
                    fprintf(stderr,"Division (word) test failed!\n");
 
540
                    return 0;
 
541
                    }
 
542
                }
 
543
        BN_free(&a);
 
544
        BN_free(&b);
 
545
        return(1);
 
546
        }
 
547
 
 
548
int test_div_recp(BIO *bp, BN_CTX *ctx)
 
549
        {
 
550
        BIGNUM a,b,c,d,e;
 
551
        BN_RECP_CTX recp;
 
552
        int i;
 
553
 
 
554
        BN_RECP_CTX_init(&recp);
 
555
        BN_init(&a);
 
556
        BN_init(&b);
 
557
        BN_init(&c);
 
558
        BN_init(&d);
 
559
        BN_init(&e);
 
560
 
 
561
        for (i=0; i<num0+num1; i++)
 
562
                {
 
563
                if (i < num1)
 
564
                        {
 
565
                        BN_bntest_rand(&a,400,0,0);
 
566
                        BN_copy(&b,&a);
 
567
                        BN_lshift(&a,&a,i);
 
568
                        BN_add_word(&a,i);
 
569
                        }
 
570
                else
 
571
                        BN_bntest_rand(&b,50+3*(i-num1),0,0);
 
572
                a.neg=rand_neg();
 
573
                b.neg=rand_neg();
 
574
                BN_RECP_CTX_set(&recp,&b,ctx);
 
575
                BN_div_recp(&d,&c,&a,&recp,ctx);
 
576
                if (bp != NULL)
 
577
                        {
 
578
                        if (!results)
 
579
                                {
 
580
                                BN_print(bp,&a);
 
581
                                BIO_puts(bp," / ");
 
582
                                BN_print(bp,&b);
 
583
                                BIO_puts(bp," - ");
 
584
                                }
 
585
                        BN_print(bp,&d);
 
586
                        BIO_puts(bp,"\n");
 
587
 
 
588
                        if (!results)
 
589
                                {
 
590
                                BN_print(bp,&a);
 
591
                                BIO_puts(bp," % ");
 
592
                                BN_print(bp,&b);
 
593
                                BIO_puts(bp," - ");
 
594
                                }
 
595
                        BN_print(bp,&c);
 
596
                        BIO_puts(bp,"\n");
 
597
                        }
 
598
                BN_mul(&e,&d,&b,ctx);
 
599
                BN_add(&d,&e,&c);
 
600
                BN_sub(&d,&d,&a);
 
601
                if(!BN_is_zero(&d))
 
602
                    {
 
603
                    fprintf(stderr,"Reciprocal division test failed!\n");
 
604
                    fprintf(stderr,"a=");
 
605
                    BN_print_fp(stderr,&a);
 
606
                    fprintf(stderr,"\nb=");
 
607
                    BN_print_fp(stderr,&b);
 
608
                    fprintf(stderr,"\n");
 
609
                    return 0;
 
610
                    }
 
611
                }
 
612
        BN_free(&a);
 
613
        BN_free(&b);
 
614
        BN_free(&c);
 
615
        BN_free(&d);
 
616
        BN_free(&e);
 
617
        BN_RECP_CTX_free(&recp);
 
618
        return(1);
 
619
        }
 
620
 
 
621
int test_mul(BIO *bp)
 
622
        {
 
623
        BIGNUM a,b,c,d,e;
 
624
        int i;
 
625
        BN_CTX *ctx;
 
626
 
 
627
        ctx = BN_CTX_new();
 
628
        if (ctx == NULL) EXIT(1);
 
629
        
 
630
        BN_init(&a);
 
631
        BN_init(&b);
 
632
        BN_init(&c);
 
633
        BN_init(&d);
 
634
        BN_init(&e);
 
635
 
 
636
        for (i=0; i<num0+num1; i++)
 
637
                {
 
638
                if (i <= num1)
 
639
                        {
 
640
                        BN_bntest_rand(&a,100,0,0);
 
641
                        BN_bntest_rand(&b,100,0,0);
 
642
                        }
 
643
                else
 
644
                        BN_bntest_rand(&b,i-num1,0,0);
 
645
                a.neg=rand_neg();
 
646
                b.neg=rand_neg();
 
647
                BN_mul(&c,&a,&b,ctx);
 
648
                if (bp != NULL)
 
649
                        {
 
650
                        if (!results)
 
651
                                {
 
652
                                BN_print(bp,&a);
 
653
                                BIO_puts(bp," * ");
 
654
                                BN_print(bp,&b);
 
655
                                BIO_puts(bp," - ");
 
656
                                }
 
657
                        BN_print(bp,&c);
 
658
                        BIO_puts(bp,"\n");
 
659
                        }
 
660
                BN_div(&d,&e,&c,&a,ctx);
 
661
                BN_sub(&d,&d,&b);
 
662
                if(!BN_is_zero(&d) || !BN_is_zero(&e))
 
663
                    {
 
664
                    fprintf(stderr,"Multiplication test failed!\n");
 
665
                    return 0;
 
666
                    }
 
667
                }
 
668
        BN_free(&a);
 
669
        BN_free(&b);
 
670
        BN_free(&c);
 
671
        BN_free(&d);
 
672
        BN_free(&e);
 
673
        BN_CTX_free(ctx);
 
674
        return(1);
 
675
        }
 
676
 
 
677
int test_sqr(BIO *bp, BN_CTX *ctx)
 
678
        {
 
679
        BIGNUM a,c,d,e;
 
680
        int i;
 
681
 
 
682
        BN_init(&a);
 
683
        BN_init(&c);
 
684
        BN_init(&d);
 
685
        BN_init(&e);
 
686
 
 
687
        for (i=0; i<num0; i++)
 
688
                {
 
689
                BN_bntest_rand(&a,40+i*10,0,0);
 
690
                a.neg=rand_neg();
 
691
                BN_sqr(&c,&a,ctx);
 
692
                if (bp != NULL)
 
693
                        {
 
694
                        if (!results)
 
695
                                {
 
696
                                BN_print(bp,&a);
 
697
                                BIO_puts(bp," * ");
 
698
                                BN_print(bp,&a);
 
699
                                BIO_puts(bp," - ");
 
700
                                }
 
701
                        BN_print(bp,&c);
 
702
                        BIO_puts(bp,"\n");
 
703
                        }
 
704
                BN_div(&d,&e,&c,&a,ctx);
 
705
                BN_sub(&d,&d,&a);
 
706
                if(!BN_is_zero(&d) || !BN_is_zero(&e))
 
707
                    {
 
708
                    fprintf(stderr,"Square test failed!\n");
 
709
                    return 0;
 
710
                    }
 
711
                }
 
712
        BN_free(&a);
 
713
        BN_free(&c);
 
714
        BN_free(&d);
 
715
        BN_free(&e);
 
716
        return(1);
 
717
        }
 
718
 
 
719
int test_mont(BIO *bp, BN_CTX *ctx)
 
720
        {
 
721
        BIGNUM a,b,c,d,A,B;
 
722
        BIGNUM n;
 
723
        int i;
 
724
        BN_MONT_CTX *mont;
 
725
 
 
726
        BN_init(&a);
 
727
        BN_init(&b);
 
728
        BN_init(&c);
 
729
        BN_init(&d);
 
730
        BN_init(&A);
 
731
        BN_init(&B);
 
732
        BN_init(&n);
 
733
 
 
734
        mont=BN_MONT_CTX_new();
 
735
        if (mont == NULL)
 
736
                return 0;
 
737
 
 
738
        BN_bntest_rand(&a,100,0,0); /**/
 
739
        BN_bntest_rand(&b,100,0,0); /**/
 
740
        for (i=0; i<num2; i++)
 
741
                {
 
742
                int bits = (200*(i+1))/num2;
 
743
 
 
744
                if (bits == 0)
 
745
                        continue;
 
746
                BN_bntest_rand(&n,bits,0,1);
 
747
                BN_MONT_CTX_set(mont,&n,ctx);
 
748
 
 
749
                BN_nnmod(&a,&a,&n,ctx);
 
750
                BN_nnmod(&b,&b,&n,ctx);
 
751
 
 
752
                BN_to_montgomery(&A,&a,mont,ctx);
 
753
                BN_to_montgomery(&B,&b,mont,ctx);
 
754
 
 
755
                BN_mod_mul_montgomery(&c,&A,&B,mont,ctx);/**/
 
756
                BN_from_montgomery(&A,&c,mont,ctx);/**/
 
757
                if (bp != NULL)
 
758
                        {
 
759
                        if (!results)
 
760
                                {
 
761
#ifdef undef
 
762
fprintf(stderr,"%d * %d %% %d\n",
 
763
BN_num_bits(&a),
 
764
BN_num_bits(&b),
 
765
BN_num_bits(mont->N));
 
766
#endif
 
767
                                BN_print(bp,&a);
 
768
                                BIO_puts(bp," * ");
 
769
                                BN_print(bp,&b);
 
770
                                BIO_puts(bp," % ");
 
771
                                BN_print(bp,&(mont->N));
 
772
                                BIO_puts(bp," - ");
 
773
                                }
 
774
                        BN_print(bp,&A);
 
775
                        BIO_puts(bp,"\n");
 
776
                        }
 
777
                BN_mod_mul(&d,&a,&b,&n,ctx);
 
778
                BN_sub(&d,&d,&A);
 
779
                if(!BN_is_zero(&d))
 
780
                    {
 
781
                    fprintf(stderr,"Montgomery multiplication test failed!\n");
 
782
                    return 0;
 
783
                    }
 
784
                }
 
785
        BN_MONT_CTX_free(mont);
 
786
        BN_free(&a);
 
787
        BN_free(&b);
 
788
        BN_free(&c);
 
789
        BN_free(&d);
 
790
        BN_free(&A);
 
791
        BN_free(&B);
 
792
        BN_free(&n);
 
793
        return(1);
 
794
        }
 
795
 
 
796
int test_mod(BIO *bp, BN_CTX *ctx)
 
797
        {
 
798
        BIGNUM *a,*b,*c,*d,*e;
 
799
        int i;
 
800
 
 
801
        a=BN_new();
 
802
        b=BN_new();
 
803
        c=BN_new();
 
804
        d=BN_new();
 
805
        e=BN_new();
 
806
 
 
807
        BN_bntest_rand(a,1024,0,0); /**/
 
808
        for (i=0; i<num0; i++)
 
809
                {
 
810
                BN_bntest_rand(b,450+i*10,0,0); /**/
 
811
                a->neg=rand_neg();
 
812
                b->neg=rand_neg();
 
813
                BN_mod(c,a,b,ctx);/**/
 
814
                if (bp != NULL)
 
815
                        {
 
816
                        if (!results)
 
817
                                {
 
818
                                BN_print(bp,a);
 
819
                                BIO_puts(bp," % ");
 
820
                                BN_print(bp,b);
 
821
                                BIO_puts(bp," - ");
 
822
                                }
 
823
                        BN_print(bp,c);
 
824
                        BIO_puts(bp,"\n");
 
825
                        }
 
826
                BN_div(d,e,a,b,ctx);
 
827
                BN_sub(e,e,c);
 
828
                if(!BN_is_zero(e))
 
829
                    {
 
830
                    fprintf(stderr,"Modulo test failed!\n");
 
831
                    return 0;
 
832
                    }
 
833
                }
 
834
        BN_free(a);
 
835
        BN_free(b);
 
836
        BN_free(c);
 
837
        BN_free(d);
 
838
        BN_free(e);
 
839
        return(1);
 
840
        }
 
841
 
 
842
int test_mod_mul(BIO *bp, BN_CTX *ctx)
 
843
        {
 
844
        BIGNUM *a,*b,*c,*d,*e;
 
845
        int i,j;
 
846
 
 
847
        a=BN_new();
 
848
        b=BN_new();
 
849
        c=BN_new();
 
850
        d=BN_new();
 
851
        e=BN_new();
 
852
 
 
853
        for (j=0; j<3; j++) {
 
854
        BN_bntest_rand(c,1024,0,0); /**/
 
855
        for (i=0; i<num0; i++)
 
856
                {
 
857
                BN_bntest_rand(a,475+i*10,0,0); /**/
 
858
                BN_bntest_rand(b,425+i*11,0,0); /**/
 
859
                a->neg=rand_neg();
 
860
                b->neg=rand_neg();
 
861
                if (!BN_mod_mul(e,a,b,c,ctx))
 
862
                        {
 
863
                        unsigned long l;
 
864
 
 
865
                        while ((l=ERR_get_error()))
 
866
                                fprintf(stderr,"ERROR:%s\n",
 
867
                                        ERR_error_string(l,NULL));
 
868
                        EXIT(1);
 
869
                        }
 
870
                if (bp != NULL)
 
871
                        {
 
872
                        if (!results)
 
873
                                {
 
874
                                BN_print(bp,a);
 
875
                                BIO_puts(bp," * ");
 
876
                                BN_print(bp,b);
 
877
                                BIO_puts(bp," % ");
 
878
                                BN_print(bp,c);
 
879
                                if ((a->neg ^ b->neg) && !BN_is_zero(e))
 
880
                                        {
 
881
                                        /* If  (a*b) % c  is negative,  c  must be added
 
882
                                         * in order to obtain the normalized remainder
 
883
                                         * (new with OpenSSL 0.9.7, previous versions of
 
884
                                         * BN_mod_mul could generate negative results)
 
885
                                         */
 
886
                                        BIO_puts(bp," + ");
 
887
                                        BN_print(bp,c);
 
888
                                        }
 
889
                                BIO_puts(bp," - ");
 
890
                                }
 
891
                        BN_print(bp,e);
 
892
                        BIO_puts(bp,"\n");
 
893
                        }
 
894
                BN_mul(d,a,b,ctx);
 
895
                BN_sub(d,d,e);
 
896
                BN_div(a,b,d,c,ctx);
 
897
                if(!BN_is_zero(b))
 
898
                    {
 
899
                    fprintf(stderr,"Modulo multiply test failed!\n");
 
900
                    ERR_print_errors_fp(stderr);
 
901
                    return 0;
 
902
                    }
 
903
                }
 
904
        }
 
905
        BN_free(a);
 
906
        BN_free(b);
 
907
        BN_free(c);
 
908
        BN_free(d);
 
909
        BN_free(e);
 
910
        return(1);
 
911
        }
 
912
 
 
913
int test_mod_exp(BIO *bp, BN_CTX *ctx)
 
914
        {
 
915
        BIGNUM *a,*b,*c,*d,*e;
 
916
        int i;
 
917
 
 
918
        a=BN_new();
 
919
        b=BN_new();
 
920
        c=BN_new();
 
921
        d=BN_new();
 
922
        e=BN_new();
 
923
 
 
924
        BN_bntest_rand(c,30,0,1); /* must be odd for montgomery */
 
925
        for (i=0; i<num2; i++)
 
926
                {
 
927
                BN_bntest_rand(a,20+i*5,0,0); /**/
 
928
                BN_bntest_rand(b,2+i,0,0); /**/
 
929
 
 
930
                if (!BN_mod_exp(d,a,b,c,ctx))
 
931
                        return(0);
 
932
 
 
933
                if (bp != NULL)
 
934
                        {
 
935
                        if (!results)
 
936
                                {
 
937
                                BN_print(bp,a);
 
938
                                BIO_puts(bp," ^ ");
 
939
                                BN_print(bp,b);
 
940
                                BIO_puts(bp," % ");
 
941
                                BN_print(bp,c);
 
942
                                BIO_puts(bp," - ");
 
943
                                }
 
944
                        BN_print(bp,d);
 
945
                        BIO_puts(bp,"\n");
 
946
                        }
 
947
                BN_exp(e,a,b,ctx);
 
948
                BN_sub(e,e,d);
 
949
                BN_div(a,b,e,c,ctx);
 
950
                if(!BN_is_zero(b))
 
951
                    {
 
952
                    fprintf(stderr,"Modulo exponentiation test failed!\n");
 
953
                    return 0;
 
954
                    }
 
955
                }
 
956
        BN_free(a);
 
957
        BN_free(b);
 
958
        BN_free(c);
 
959
        BN_free(d);
 
960
        BN_free(e);
 
961
        return(1);
 
962
        }
 
963
 
 
964
int test_mod_exp_mont_consttime(BIO *bp, BN_CTX *ctx)
 
965
        {
 
966
        BIGNUM *a,*b,*c,*d,*e;
 
967
        int i;
 
968
 
 
969
        a=BN_new();
 
970
        b=BN_new();
 
971
        c=BN_new();
 
972
        d=BN_new();
 
973
        e=BN_new();
 
974
 
 
975
        BN_bntest_rand(c,30,0,1); /* must be odd for montgomery */
 
976
        for (i=0; i<num2; i++)
 
977
                {
 
978
                BN_bntest_rand(a,20+i*5,0,0); /**/
 
979
                BN_bntest_rand(b,2+i,0,0); /**/
 
980
 
 
981
                if (!BN_mod_exp_mont_consttime(d,a,b,c,ctx,NULL))
 
982
                        return(00);
 
983
 
 
984
                if (bp != NULL)
 
985
                        {
 
986
                        if (!results)
 
987
                                {
 
988
                                BN_print(bp,a);
 
989
                                BIO_puts(bp," ^ ");
 
990
                                BN_print(bp,b);
 
991
                                BIO_puts(bp," % ");
 
992
                                BN_print(bp,c);
 
993
                                BIO_puts(bp," - ");
 
994
                                }
 
995
                        BN_print(bp,d);
 
996
                        BIO_puts(bp,"\n");
 
997
                        }
 
998
                BN_exp(e,a,b,ctx);
 
999
                BN_sub(e,e,d);
 
1000
                BN_div(a,b,e,c,ctx);
 
1001
                if(!BN_is_zero(b))
 
1002
                    {
 
1003
                    fprintf(stderr,"Modulo exponentiation test failed!\n");
 
1004
                    return 0;
 
1005
                    }
 
1006
                }
 
1007
        BN_free(a);
 
1008
        BN_free(b);
 
1009
        BN_free(c);
 
1010
        BN_free(d);
 
1011
        BN_free(e);
 
1012
        return(1);
 
1013
        }
 
1014
 
 
1015
int test_exp(BIO *bp, BN_CTX *ctx)
 
1016
        {
 
1017
        BIGNUM *a,*b,*d,*e,*one;
 
1018
        int i;
 
1019
 
 
1020
        a=BN_new();
 
1021
        b=BN_new();
 
1022
        d=BN_new();
 
1023
        e=BN_new();
 
1024
        one=BN_new();
 
1025
        BN_one(one);
 
1026
 
 
1027
        for (i=0; i<num2; i++)
 
1028
                {
 
1029
                BN_bntest_rand(a,20+i*5,0,0); /**/
 
1030
                BN_bntest_rand(b,2+i,0,0); /**/
 
1031
 
 
1032
                if (BN_exp(d,a,b,ctx) <= 0)
 
1033
                        return(0);
 
1034
 
 
1035
                if (bp != NULL)
 
1036
                        {
 
1037
                        if (!results)
 
1038
                                {
 
1039
                                BN_print(bp,a);
 
1040
                                BIO_puts(bp," ^ ");
 
1041
                                BN_print(bp,b);
 
1042
                                BIO_puts(bp," - ");
 
1043
                                }
 
1044
                        BN_print(bp,d);
 
1045
                        BIO_puts(bp,"\n");
 
1046
                        }
 
1047
                BN_one(e);
 
1048
                for( ; !BN_is_zero(b) ; BN_sub(b,b,one))
 
1049
                    BN_mul(e,e,a,ctx);
 
1050
                BN_sub(e,e,d);
 
1051
                if(!BN_is_zero(e))
 
1052
                    {
 
1053
                    fprintf(stderr,"Exponentiation test failed!\n");
 
1054
                    return 0;
 
1055
                    }
 
1056
                }
 
1057
        BN_free(a);
 
1058
        BN_free(b);
 
1059
        BN_free(d);
 
1060
        BN_free(e);
 
1061
        BN_free(one);
 
1062
        return(1);
 
1063
        }
 
1064
#ifndef OPENSSL_NO_EC2M
 
1065
int test_gf2m_add(BIO *bp)
 
1066
        {
 
1067
        BIGNUM a,b,c;
 
1068
        int i, ret = 0;
 
1069
 
 
1070
        BN_init(&a);
 
1071
        BN_init(&b);
 
1072
        BN_init(&c);
 
1073
 
 
1074
        for (i=0; i<num0; i++)
 
1075
                {
 
1076
                BN_rand(&a,512,0,0);
 
1077
                BN_copy(&b, BN_value_one());
 
1078
                a.neg=rand_neg();
 
1079
                b.neg=rand_neg();
 
1080
                BN_GF2m_add(&c,&a,&b);
 
1081
#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
 
1082
                if (bp != NULL)
 
1083
                        {
 
1084
                        if (!results)
 
1085
                                {
 
1086
                                BN_print(bp,&a);
 
1087
                                BIO_puts(bp," ^ ");
 
1088
                                BN_print(bp,&b);
 
1089
                                BIO_puts(bp," = ");
 
1090
                                }
 
1091
                        BN_print(bp,&c);
 
1092
                        BIO_puts(bp,"\n");
 
1093
                        }
 
1094
#endif
 
1095
                /* Test that two added values have the correct parity. */
 
1096
                if((BN_is_odd(&a) && BN_is_odd(&c)) || (!BN_is_odd(&a) && !BN_is_odd(&c)))
 
1097
                        {
 
1098
                    fprintf(stderr,"GF(2^m) addition test (a) failed!\n");
 
1099
                        goto err;
 
1100
                        }
 
1101
                BN_GF2m_add(&c,&c,&c);
 
1102
                /* Test that c + c = 0. */
 
1103
                if(!BN_is_zero(&c))
 
1104
                    {
 
1105
                    fprintf(stderr,"GF(2^m) addition test (b) failed!\n");
 
1106
                        goto err;
 
1107
                    }
 
1108
                }
 
1109
        ret = 1;
 
1110
  err:
 
1111
        BN_free(&a);
 
1112
        BN_free(&b);
 
1113
        BN_free(&c);
 
1114
        return ret;
 
1115
        }
 
1116
 
 
1117
int test_gf2m_mod(BIO *bp)
 
1118
        {
 
1119
        BIGNUM *a,*b[2],*c,*d,*e;
 
1120
        int i, j, ret = 0;
 
1121
        int p0[] = {163,7,6,3,0,-1};
 
1122
        int p1[] = {193,15,0,-1};
 
1123
 
 
1124
        a=BN_new();
 
1125
        b[0]=BN_new();
 
1126
        b[1]=BN_new();
 
1127
        c=BN_new();
 
1128
        d=BN_new();
 
1129
        e=BN_new();
 
1130
 
 
1131
        BN_GF2m_arr2poly(p0, b[0]);
 
1132
        BN_GF2m_arr2poly(p1, b[1]);
 
1133
 
 
1134
        for (i=0; i<num0; i++)
 
1135
                {
 
1136
                BN_bntest_rand(a, 1024, 0, 0);
 
1137
                for (j=0; j < 2; j++)
 
1138
                        {
 
1139
                        BN_GF2m_mod(c, a, b[j]);
 
1140
#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
 
1141
                        if (bp != NULL)
 
1142
                                {
 
1143
                                if (!results)
 
1144
                                        {
 
1145
                                        BN_print(bp,a);
 
1146
                                        BIO_puts(bp," % ");
 
1147
                                        BN_print(bp,b[j]);
 
1148
                                        BIO_puts(bp," - ");
 
1149
                                        BN_print(bp,c);
 
1150
                                        BIO_puts(bp,"\n");
 
1151
                                        }
 
1152
                                }
 
1153
#endif
 
1154
                        BN_GF2m_add(d, a, c);
 
1155
                        BN_GF2m_mod(e, d, b[j]);
 
1156
                        /* Test that a + (a mod p) mod p == 0. */
 
1157
                        if(!BN_is_zero(e))
 
1158
                                {
 
1159
                                fprintf(stderr,"GF(2^m) modulo test failed!\n");
 
1160
                                goto err;
 
1161
                                }
 
1162
                        }
 
1163
                }
 
1164
        ret = 1;
 
1165
  err:
 
1166
        BN_free(a);
 
1167
        BN_free(b[0]);
 
1168
        BN_free(b[1]);
 
1169
        BN_free(c);
 
1170
        BN_free(d);
 
1171
        BN_free(e);
 
1172
        return ret;
 
1173
        }
 
1174
 
 
1175
int test_gf2m_mod_mul(BIO *bp,BN_CTX *ctx)
 
1176
        {
 
1177
        BIGNUM *a,*b[2],*c,*d,*e,*f,*g,*h;
 
1178
        int i, j, ret = 0;
 
1179
        int p0[] = {163,7,6,3,0,-1};
 
1180
        int p1[] = {193,15,0,-1};
 
1181
 
 
1182
        a=BN_new();
 
1183
        b[0]=BN_new();
 
1184
        b[1]=BN_new();
 
1185
        c=BN_new();
 
1186
        d=BN_new();
 
1187
        e=BN_new();
 
1188
        f=BN_new();
 
1189
        g=BN_new();
 
1190
        h=BN_new();
 
1191
 
 
1192
        BN_GF2m_arr2poly(p0, b[0]);
 
1193
        BN_GF2m_arr2poly(p1, b[1]);
 
1194
 
 
1195
        for (i=0; i<num0; i++)
 
1196
                {
 
1197
                BN_bntest_rand(a, 1024, 0, 0);
 
1198
                BN_bntest_rand(c, 1024, 0, 0);
 
1199
                BN_bntest_rand(d, 1024, 0, 0);
 
1200
                for (j=0; j < 2; j++)
 
1201
                        {
 
1202
                        BN_GF2m_mod_mul(e, a, c, b[j], ctx);
 
1203
#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
 
1204
                        if (bp != NULL)
 
1205
                                {
 
1206
                                if (!results)
 
1207
                                        {
 
1208
                                        BN_print(bp,a);
 
1209
                                        BIO_puts(bp," * ");
 
1210
                                        BN_print(bp,c);
 
1211
                                        BIO_puts(bp," % ");
 
1212
                                        BN_print(bp,b[j]);
 
1213
                                        BIO_puts(bp," - ");
 
1214
                                        BN_print(bp,e);
 
1215
                                        BIO_puts(bp,"\n");
 
1216
                                        }
 
1217
                                }
 
1218
#endif
 
1219
                        BN_GF2m_add(f, a, d);
 
1220
                        BN_GF2m_mod_mul(g, f, c, b[j], ctx);
 
1221
                        BN_GF2m_mod_mul(h, d, c, b[j], ctx);
 
1222
                        BN_GF2m_add(f, e, g);
 
1223
                        BN_GF2m_add(f, f, h);
 
1224
                        /* Test that (a+d)*c = a*c + d*c. */
 
1225
                        if(!BN_is_zero(f))
 
1226
                                {
 
1227
                                fprintf(stderr,"GF(2^m) modular multiplication test failed!\n");
 
1228
                                goto err;
 
1229
                                }
 
1230
                        }
 
1231
                }
 
1232
        ret = 1;
 
1233
  err:
 
1234
        BN_free(a);
 
1235
        BN_free(b[0]);
 
1236
        BN_free(b[1]);
 
1237
        BN_free(c);
 
1238
        BN_free(d);
 
1239
        BN_free(e);
 
1240
        BN_free(f);
 
1241
        BN_free(g);
 
1242
        BN_free(h);
 
1243
        return ret;
 
1244
        }
 
1245
 
 
1246
int test_gf2m_mod_sqr(BIO *bp,BN_CTX *ctx)
 
1247
        {
 
1248
        BIGNUM *a,*b[2],*c,*d;
 
1249
        int i, j, ret = 0;
 
1250
        int p0[] = {163,7,6,3,0,-1};
 
1251
        int p1[] = {193,15,0,-1};
 
1252
 
 
1253
        a=BN_new();
 
1254
        b[0]=BN_new();
 
1255
        b[1]=BN_new();
 
1256
        c=BN_new();
 
1257
        d=BN_new();
 
1258
 
 
1259
        BN_GF2m_arr2poly(p0, b[0]);
 
1260
        BN_GF2m_arr2poly(p1, b[1]);
 
1261
 
 
1262
        for (i=0; i<num0; i++)
 
1263
                {
 
1264
                BN_bntest_rand(a, 1024, 0, 0);
 
1265
                for (j=0; j < 2; j++)
 
1266
                        {
 
1267
                        BN_GF2m_mod_sqr(c, a, b[j], ctx);
 
1268
                        BN_copy(d, a);
 
1269
                        BN_GF2m_mod_mul(d, a, d, b[j], ctx);
 
1270
#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
 
1271
                        if (bp != NULL)
 
1272
                                {
 
1273
                                if (!results)
 
1274
                                        {
 
1275
                                        BN_print(bp,a);
 
1276
                                        BIO_puts(bp," ^ 2 % ");
 
1277
                                        BN_print(bp,b[j]);
 
1278
                                        BIO_puts(bp, " = ");
 
1279
                                        BN_print(bp,c);
 
1280
                                        BIO_puts(bp,"; a * a = ");
 
1281
                                        BN_print(bp,d);
 
1282
                                        BIO_puts(bp,"\n");
 
1283
                                        }
 
1284
                                }
 
1285
#endif
 
1286
                        BN_GF2m_add(d, c, d);
 
1287
                        /* Test that a*a = a^2. */
 
1288
                        if(!BN_is_zero(d))
 
1289
                                {
 
1290
                                fprintf(stderr,"GF(2^m) modular squaring test failed!\n");
 
1291
                                goto err;
 
1292
                                }
 
1293
                        }
 
1294
                }
 
1295
        ret = 1;
 
1296
  err:
 
1297
        BN_free(a);
 
1298
        BN_free(b[0]);
 
1299
        BN_free(b[1]);
 
1300
        BN_free(c);
 
1301
        BN_free(d);
 
1302
        return ret;
 
1303
        }
 
1304
 
 
1305
int test_gf2m_mod_inv(BIO *bp,BN_CTX *ctx)
 
1306
        {
 
1307
        BIGNUM *a,*b[2],*c,*d;
 
1308
        int i, j, ret = 0;
 
1309
        int p0[] = {163,7,6,3,0,-1};
 
1310
        int p1[] = {193,15,0,-1};
 
1311
 
 
1312
        a=BN_new();
 
1313
        b[0]=BN_new();
 
1314
        b[1]=BN_new();
 
1315
        c=BN_new();
 
1316
        d=BN_new();
 
1317
 
 
1318
        BN_GF2m_arr2poly(p0, b[0]);
 
1319
        BN_GF2m_arr2poly(p1, b[1]);
 
1320
 
 
1321
        for (i=0; i<num0; i++)
 
1322
                {
 
1323
                BN_bntest_rand(a, 512, 0, 0); 
 
1324
                for (j=0; j < 2; j++)
 
1325
                        {
 
1326
                        BN_GF2m_mod_inv(c, a, b[j], ctx);
 
1327
                        BN_GF2m_mod_mul(d, a, c, b[j], ctx);
 
1328
#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
 
1329
                        if (bp != NULL)
 
1330
                                {
 
1331
                                if (!results)
 
1332
                                        {
 
1333
                                        BN_print(bp,a);
 
1334
                                        BIO_puts(bp, " * ");
 
1335
                                        BN_print(bp,c);
 
1336
                                        BIO_puts(bp," - 1 % ");
 
1337
                                        BN_print(bp,b[j]);
 
1338
                                        BIO_puts(bp,"\n");
 
1339
                                        }
 
1340
                                }
 
1341
#endif
 
1342
                        /* Test that ((1/a)*a) = 1. */
 
1343
                        if(!BN_is_one(d))
 
1344
                                {
 
1345
                                fprintf(stderr,"GF(2^m) modular inversion test failed!\n");
 
1346
                                goto err;
 
1347
                                }
 
1348
                        }
 
1349
                }
 
1350
        ret = 1;
 
1351
  err:
 
1352
        BN_free(a);
 
1353
        BN_free(b[0]);
 
1354
        BN_free(b[1]);
 
1355
        BN_free(c);
 
1356
        BN_free(d);
 
1357
        return ret;
 
1358
        }
 
1359
 
 
1360
int test_gf2m_mod_div(BIO *bp,BN_CTX *ctx)
 
1361
        {
 
1362
        BIGNUM *a,*b[2],*c,*d,*e,*f;
 
1363
        int i, j, ret = 0;
 
1364
        int p0[] = {163,7,6,3,0,-1};
 
1365
        int p1[] = {193,15,0,-1};
 
1366
 
 
1367
        a=BN_new();
 
1368
        b[0]=BN_new();
 
1369
        b[1]=BN_new();
 
1370
        c=BN_new();
 
1371
        d=BN_new();
 
1372
        e=BN_new();
 
1373
        f=BN_new();
 
1374
 
 
1375
        BN_GF2m_arr2poly(p0, b[0]);
 
1376
        BN_GF2m_arr2poly(p1, b[1]);
 
1377
 
 
1378
        for (i=0; i<num0; i++)
 
1379
                {
 
1380
                BN_bntest_rand(a, 512, 0, 0); 
 
1381
                BN_bntest_rand(c, 512, 0, 0);
 
1382
                for (j=0; j < 2; j++)
 
1383
                        {
 
1384
                        BN_GF2m_mod_div(d, a, c, b[j], ctx);
 
1385
                        BN_GF2m_mod_mul(e, d, c, b[j], ctx);
 
1386
                        BN_GF2m_mod_div(f, a, e, b[j], ctx);
 
1387
#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
 
1388
                        if (bp != NULL)
 
1389
                                {
 
1390
                                if (!results)
 
1391
                                        {
 
1392
                                        BN_print(bp,a);
 
1393
                                        BIO_puts(bp, " = ");
 
1394
                                        BN_print(bp,c);
 
1395
                                        BIO_puts(bp," * ");
 
1396
                                        BN_print(bp,d);
 
1397
                                        BIO_puts(bp, " % ");
 
1398
                                        BN_print(bp,b[j]);
 
1399
                                        BIO_puts(bp,"\n");
 
1400
                                        }
 
1401
                                }
 
1402
#endif
 
1403
                        /* Test that ((a/c)*c)/a = 1. */
 
1404
                        if(!BN_is_one(f))
 
1405
                                {
 
1406
                                fprintf(stderr,"GF(2^m) modular division test failed!\n");
 
1407
                                goto err;
 
1408
                                }
 
1409
                        }
 
1410
                }
 
1411
        ret = 1;
 
1412
  err:
 
1413
        BN_free(a);
 
1414
        BN_free(b[0]);
 
1415
        BN_free(b[1]);
 
1416
        BN_free(c);
 
1417
        BN_free(d);
 
1418
        BN_free(e);
 
1419
        BN_free(f);
 
1420
        return ret;
 
1421
        }
 
1422
 
 
1423
int test_gf2m_mod_exp(BIO *bp,BN_CTX *ctx)
 
1424
        {
 
1425
        BIGNUM *a,*b[2],*c,*d,*e,*f;
 
1426
        int i, j, ret = 0;
 
1427
        int p0[] = {163,7,6,3,0,-1};
 
1428
        int p1[] = {193,15,0,-1};
 
1429
 
 
1430
        a=BN_new();
 
1431
        b[0]=BN_new();
 
1432
        b[1]=BN_new();
 
1433
        c=BN_new();
 
1434
        d=BN_new();
 
1435
        e=BN_new();
 
1436
        f=BN_new();
 
1437
 
 
1438
        BN_GF2m_arr2poly(p0, b[0]);
 
1439
        BN_GF2m_arr2poly(p1, b[1]);
 
1440
 
 
1441
        for (i=0; i<num0; i++)
 
1442
                {
 
1443
                BN_bntest_rand(a, 512, 0, 0);
 
1444
                BN_bntest_rand(c, 512, 0, 0);
 
1445
                BN_bntest_rand(d, 512, 0, 0);
 
1446
                for (j=0; j < 2; j++)
 
1447
                        {
 
1448
                        BN_GF2m_mod_exp(e, a, c, b[j], ctx);
 
1449
                        BN_GF2m_mod_exp(f, a, d, b[j], ctx);
 
1450
                        BN_GF2m_mod_mul(e, e, f, b[j], ctx);
 
1451
                        BN_add(f, c, d);
 
1452
                        BN_GF2m_mod_exp(f, a, f, b[j], ctx);
 
1453
#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
 
1454
                        if (bp != NULL)
 
1455
                                {
 
1456
                                if (!results)
 
1457
                                        {
 
1458
                                        BN_print(bp,a);
 
1459
                                        BIO_puts(bp, " ^ (");
 
1460
                                        BN_print(bp,c);
 
1461
                                        BIO_puts(bp," + ");
 
1462
                                        BN_print(bp,d);
 
1463
                                        BIO_puts(bp, ") = ");
 
1464
                                        BN_print(bp,e);
 
1465
                                        BIO_puts(bp, "; - ");
 
1466
                                        BN_print(bp,f);
 
1467
                                        BIO_puts(bp, " % ");
 
1468
                                        BN_print(bp,b[j]);
 
1469
                                        BIO_puts(bp,"\n");
 
1470
                                        }
 
1471
                                }
 
1472
#endif
 
1473
                        BN_GF2m_add(f, e, f);
 
1474
                        /* Test that a^(c+d)=a^c*a^d. */
 
1475
                        if(!BN_is_zero(f))
 
1476
                                {
 
1477
                                fprintf(stderr,"GF(2^m) modular exponentiation test failed!\n");
 
1478
                                goto err;
 
1479
                                }
 
1480
                        }
 
1481
                }
 
1482
        ret = 1;
 
1483
  err:
 
1484
        BN_free(a);
 
1485
        BN_free(b[0]);
 
1486
        BN_free(b[1]);
 
1487
        BN_free(c);
 
1488
        BN_free(d);
 
1489
        BN_free(e);
 
1490
        BN_free(f);
 
1491
        return ret;
 
1492
        }
 
1493
 
 
1494
int test_gf2m_mod_sqrt(BIO *bp,BN_CTX *ctx)
 
1495
        {
 
1496
        BIGNUM *a,*b[2],*c,*d,*e,*f;
 
1497
        int i, j, ret = 0;
 
1498
        int p0[] = {163,7,6,3,0,-1};
 
1499
        int p1[] = {193,15,0,-1};
 
1500
 
 
1501
        a=BN_new();
 
1502
        b[0]=BN_new();
 
1503
        b[1]=BN_new();
 
1504
        c=BN_new();
 
1505
        d=BN_new();
 
1506
        e=BN_new();
 
1507
        f=BN_new();
 
1508
 
 
1509
        BN_GF2m_arr2poly(p0, b[0]);
 
1510
        BN_GF2m_arr2poly(p1, b[1]);
 
1511
 
 
1512
        for (i=0; i<num0; i++)
 
1513
                {
 
1514
                BN_bntest_rand(a, 512, 0, 0);
 
1515
                for (j=0; j < 2; j++)
 
1516
                        {
 
1517
                        BN_GF2m_mod(c, a, b[j]);
 
1518
                        BN_GF2m_mod_sqrt(d, a, b[j], ctx);
 
1519
                        BN_GF2m_mod_sqr(e, d, b[j], ctx);
 
1520
#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
 
1521
                        if (bp != NULL)
 
1522
                                {
 
1523
                                if (!results)
 
1524
                                        {
 
1525
                                        BN_print(bp,d);
 
1526
                                        BIO_puts(bp, " ^ 2 - ");
 
1527
                                        BN_print(bp,a);
 
1528
                                        BIO_puts(bp,"\n");
 
1529
                                        }
 
1530
                                }
 
1531
#endif
 
1532
                        BN_GF2m_add(f, c, e);
 
1533
                        /* Test that d^2 = a, where d = sqrt(a). */
 
1534
                        if(!BN_is_zero(f))
 
1535
                                {
 
1536
                                fprintf(stderr,"GF(2^m) modular square root test failed!\n");
 
1537
                                goto err;
 
1538
                                }
 
1539
                        }
 
1540
                }
 
1541
        ret = 1;
 
1542
  err:
 
1543
        BN_free(a);
 
1544
        BN_free(b[0]);
 
1545
        BN_free(b[1]);
 
1546
        BN_free(c);
 
1547
        BN_free(d);
 
1548
        BN_free(e);
 
1549
        BN_free(f);
 
1550
        return ret;
 
1551
        }
 
1552
 
 
1553
int test_gf2m_mod_solve_quad(BIO *bp,BN_CTX *ctx)
 
1554
        {
 
1555
        BIGNUM *a,*b[2],*c,*d,*e;
 
1556
        int i, j, s = 0, t, ret = 0;
 
1557
        int p0[] = {163,7,6,3,0,-1};
 
1558
        int p1[] = {193,15,0,-1};
 
1559
 
 
1560
        a=BN_new();
 
1561
        b[0]=BN_new();
 
1562
        b[1]=BN_new();
 
1563
        c=BN_new();
 
1564
        d=BN_new();
 
1565
        e=BN_new();
 
1566
 
 
1567
        BN_GF2m_arr2poly(p0, b[0]);
 
1568
        BN_GF2m_arr2poly(p1, b[1]);
 
1569
 
 
1570
        for (i=0; i<num0; i++)
 
1571
                {
 
1572
                BN_bntest_rand(a, 512, 0, 0);
 
1573
                for (j=0; j < 2; j++)
 
1574
                        {
 
1575
                        t = BN_GF2m_mod_solve_quad(c, a, b[j], ctx);
 
1576
                        if (t)
 
1577
                                {
 
1578
                                s++;
 
1579
                                BN_GF2m_mod_sqr(d, c, b[j], ctx);
 
1580
                                BN_GF2m_add(d, c, d);
 
1581
                                BN_GF2m_mod(e, a, b[j]);
 
1582
#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
 
1583
                                if (bp != NULL)
 
1584
                                        {
 
1585
                                        if (!results)
 
1586
                                                {
 
1587
                                                BN_print(bp,c);
 
1588
                                                BIO_puts(bp, " is root of z^2 + z = ");
 
1589
                                                BN_print(bp,a);
 
1590
                                                BIO_puts(bp, " % ");
 
1591
                                                BN_print(bp,b[j]);
 
1592
                                                BIO_puts(bp, "\n");
 
1593
                                                }
 
1594
                                        }
 
1595
#endif
 
1596
                                BN_GF2m_add(e, e, d);
 
1597
                                /* Test that solution of quadratic c satisfies c^2 + c = a. */
 
1598
                                if(!BN_is_zero(e))
 
1599
                                        {
 
1600
                                        fprintf(stderr,"GF(2^m) modular solve quadratic test failed!\n");
 
1601
                                        goto err;
 
1602
                                        }
 
1603
 
 
1604
                                }
 
1605
                        else 
 
1606
                                {
 
1607
#if 0 /* make test uses ouput in bc but bc can't handle GF(2^m) arithmetic */
 
1608
                                if (bp != NULL)
 
1609
                                        {
 
1610
                                        if (!results)
 
1611
                                                {
 
1612
                                                BIO_puts(bp, "There are no roots of z^2 + z = ");
 
1613
                                                BN_print(bp,a);
 
1614
                                                BIO_puts(bp, " % ");
 
1615
                                                BN_print(bp,b[j]);
 
1616
                                                BIO_puts(bp, "\n");
 
1617
                                                }
 
1618
                                        }
 
1619
#endif
 
1620
                                }
 
1621
                        }
 
1622
                }
 
1623
        if (s == 0)
 
1624
                {       
 
1625
                fprintf(stderr,"All %i tests of GF(2^m) modular solve quadratic resulted in no roots;\n", num0);
 
1626
                fprintf(stderr,"this is very unlikely and probably indicates an error.\n");
 
1627
                goto err;
 
1628
                }
 
1629
        ret = 1;
 
1630
  err:
 
1631
        BN_free(a);
 
1632
        BN_free(b[0]);
 
1633
        BN_free(b[1]);
 
1634
        BN_free(c);
 
1635
        BN_free(d);
 
1636
        BN_free(e);
 
1637
        return ret;
 
1638
        }
 
1639
#endif
 
1640
static int genprime_cb(int p, int n, BN_GENCB *arg)
 
1641
        {
 
1642
        char c='*';
 
1643
 
 
1644
        if (p == 0) c='.';
 
1645
        if (p == 1) c='+';
 
1646
        if (p == 2) c='*';
 
1647
        if (p == 3) c='\n';
 
1648
        putc(c, stderr);
 
1649
        fflush(stderr);
 
1650
        return 1;
 
1651
        }
 
1652
 
 
1653
int test_kron(BIO *bp, BN_CTX *ctx)
 
1654
        {
 
1655
        BN_GENCB cb;
 
1656
        BIGNUM *a,*b,*r,*t;
 
1657
        int i;
 
1658
        int legendre, kronecker;
 
1659
        int ret = 0;
 
1660
 
 
1661
        a = BN_new();
 
1662
        b = BN_new();
 
1663
        r = BN_new();
 
1664
        t = BN_new();
 
1665
        if (a == NULL || b == NULL || r == NULL || t == NULL) goto err;
 
1666
 
 
1667
        BN_GENCB_set(&cb, genprime_cb, NULL);
 
1668
        
 
1669
        /* We test BN_kronecker(a, b, ctx) just for  b  odd (Jacobi symbol).
 
1670
         * In this case we know that if  b  is prime, then BN_kronecker(a, b, ctx)
 
1671
         * is congruent to $a^{(b-1)/2}$, modulo $b$ (Legendre symbol).
 
1672
         * So we generate a random prime  b  and compare these values
 
1673
         * for a number of random  a's.  (That is, we run the Solovay-Strassen
 
1674
         * primality test to confirm that  b  is prime, except that we
 
1675
         * don't want to test whether  b  is prime but whether BN_kronecker
 
1676
         * works.) */
 
1677
 
 
1678
        if (!BN_generate_prime_ex(b, 512, 0, NULL, NULL, &cb)) goto err;
 
1679
        b->neg = rand_neg();
 
1680
        putc('\n', stderr);
 
1681
 
 
1682
        for (i = 0; i < num0; i++)
 
1683
                {
 
1684
                if (!BN_bntest_rand(a, 512, 0, 0)) goto err;
 
1685
                a->neg = rand_neg();
 
1686
 
 
1687
                /* t := (|b|-1)/2  (note that b is odd) */
 
1688
                if (!BN_copy(t, b)) goto err;
 
1689
                t->neg = 0;
 
1690
                if (!BN_sub_word(t, 1)) goto err;
 
1691
                if (!BN_rshift1(t, t)) goto err;
 
1692
                /* r := a^t mod b */
 
1693
                b->neg=0;
 
1694
                
 
1695
                if (!BN_mod_exp_recp(r, a, t, b, ctx)) goto err;
 
1696
                b->neg=1;
 
1697
 
 
1698
                if (BN_is_word(r, 1))
 
1699
                        legendre = 1;
 
1700
                else if (BN_is_zero(r))
 
1701
                        legendre = 0;
 
1702
                else
 
1703
                        {
 
1704
                        if (!BN_add_word(r, 1)) goto err;
 
1705
                        if (0 != BN_ucmp(r, b))
 
1706
                                {
 
1707
                                fprintf(stderr, "Legendre symbol computation failed\n");
 
1708
                                goto err;
 
1709
                                }
 
1710
                        legendre = -1;
 
1711
                        }
 
1712
                
 
1713
                kronecker = BN_kronecker(a, b, ctx);
 
1714
                if (kronecker < -1) goto err;
 
1715
                /* we actually need BN_kronecker(a, |b|) */
 
1716
                if (a->neg && b->neg)
 
1717
                        kronecker = -kronecker;
 
1718
                
 
1719
                if (legendre != kronecker)
 
1720
                        {
 
1721
                        fprintf(stderr, "legendre != kronecker; a = ");
 
1722
                        BN_print_fp(stderr, a);
 
1723
                        fprintf(stderr, ", b = ");
 
1724
                        BN_print_fp(stderr, b);
 
1725
                        fprintf(stderr, "\n");
 
1726
                        goto err;
 
1727
                        }
 
1728
 
 
1729
                putc('.', stderr);
 
1730
                fflush(stderr);
 
1731
                }
 
1732
 
 
1733
        putc('\n', stderr);
 
1734
        fflush(stderr);
 
1735
        ret = 1;
 
1736
 err:
 
1737
        if (a != NULL) BN_free(a);
 
1738
        if (b != NULL) BN_free(b);
 
1739
        if (r != NULL) BN_free(r);
 
1740
        if (t != NULL) BN_free(t);
 
1741
        return ret;
 
1742
        }
 
1743
 
 
1744
int test_sqrt(BIO *bp, BN_CTX *ctx)
 
1745
        {
 
1746
        BN_GENCB cb;
 
1747
        BIGNUM *a,*p,*r;
 
1748
        int i, j;
 
1749
        int ret = 0;
 
1750
 
 
1751
        a = BN_new();
 
1752
        p = BN_new();
 
1753
        r = BN_new();
 
1754
        if (a == NULL || p == NULL || r == NULL) goto err;
 
1755
 
 
1756
        BN_GENCB_set(&cb, genprime_cb, NULL);
 
1757
 
 
1758
        for (i = 0; i < 16; i++)
 
1759
                {
 
1760
                if (i < 8)
 
1761
                        {
 
1762
                        unsigned primes[8] = { 2, 3, 5, 7, 11, 13, 17, 19 };
 
1763
                        
 
1764
                        if (!BN_set_word(p, primes[i])) goto err;
 
1765
                        }
 
1766
                else
 
1767
                        {
 
1768
                        if (!BN_set_word(a, 32)) goto err;
 
1769
                        if (!BN_set_word(r, 2*i + 1)) goto err;
 
1770
                
 
1771
                        if (!BN_generate_prime_ex(p, 256, 0, a, r, &cb)) goto err;
 
1772
                        putc('\n', stderr);
 
1773
                        }
 
1774
                p->neg = rand_neg();
 
1775
 
 
1776
                for (j = 0; j < num2; j++)
 
1777
                        {
 
1778
                        /* construct 'a' such that it is a square modulo p,
 
1779
                         * but in general not a proper square and not reduced modulo p */
 
1780
                        if (!BN_bntest_rand(r, 256, 0, 3)) goto err;
 
1781
                        if (!BN_nnmod(r, r, p, ctx)) goto err;
 
1782
                        if (!BN_mod_sqr(r, r, p, ctx)) goto err;
 
1783
                        if (!BN_bntest_rand(a, 256, 0, 3)) goto err;
 
1784
                        if (!BN_nnmod(a, a, p, ctx)) goto err;
 
1785
                        if (!BN_mod_sqr(a, a, p, ctx)) goto err;
 
1786
                        if (!BN_mul(a, a, r, ctx)) goto err;
 
1787
                        if (rand_neg())
 
1788
                                if (!BN_sub(a, a, p)) goto err;
 
1789
 
 
1790
                        if (!BN_mod_sqrt(r, a, p, ctx)) goto err;
 
1791
                        if (!BN_mod_sqr(r, r, p, ctx)) goto err;
 
1792
 
 
1793
                        if (!BN_nnmod(a, a, p, ctx)) goto err;
 
1794
 
 
1795
                        if (BN_cmp(a, r) != 0)
 
1796
                                {
 
1797
                                fprintf(stderr, "BN_mod_sqrt failed: a = ");
 
1798
                                BN_print_fp(stderr, a);
 
1799
                                fprintf(stderr, ", r = ");
 
1800
                                BN_print_fp(stderr, r);
 
1801
                                fprintf(stderr, ", p = ");
 
1802
                                BN_print_fp(stderr, p);
 
1803
                                fprintf(stderr, "\n");
 
1804
                                goto err;
 
1805
                                }
 
1806
 
 
1807
                        putc('.', stderr);
 
1808
                        fflush(stderr);
 
1809
                        }
 
1810
                
 
1811
                putc('\n', stderr);
 
1812
                fflush(stderr);
 
1813
                }
 
1814
        ret = 1;
 
1815
 err:
 
1816
        if (a != NULL) BN_free(a);
 
1817
        if (p != NULL) BN_free(p);
 
1818
        if (r != NULL) BN_free(r);
 
1819
        return ret;
 
1820
        }
 
1821
 
 
1822
int test_lshift(BIO *bp,BN_CTX *ctx,BIGNUM *a_)
 
1823
        {
 
1824
        BIGNUM *a,*b,*c,*d;
 
1825
        int i;
 
1826
 
 
1827
        b=BN_new();
 
1828
        c=BN_new();
 
1829
        d=BN_new();
 
1830
        BN_one(c);
 
1831
 
 
1832
        if(a_)
 
1833
            a=a_;
 
1834
        else
 
1835
            {
 
1836
            a=BN_new();
 
1837
            BN_bntest_rand(a,200,0,0); /**/
 
1838
            a->neg=rand_neg();
 
1839
            }
 
1840
        for (i=0; i<num0; i++)
 
1841
                {
 
1842
                BN_lshift(b,a,i+1);
 
1843
                BN_add(c,c,c);
 
1844
                if (bp != NULL)
 
1845
                        {
 
1846
                        if (!results)
 
1847
                                {
 
1848
                                BN_print(bp,a);
 
1849
                                BIO_puts(bp," * ");
 
1850
                                BN_print(bp,c);
 
1851
                                BIO_puts(bp," - ");
 
1852
                                }
 
1853
                        BN_print(bp,b);
 
1854
                        BIO_puts(bp,"\n");
 
1855
                        }
 
1856
                BN_mul(d,a,c,ctx);
 
1857
                BN_sub(d,d,b);
 
1858
                if(!BN_is_zero(d))
 
1859
                    {
 
1860
                    fprintf(stderr,"Left shift test failed!\n");
 
1861
                    fprintf(stderr,"a=");
 
1862
                    BN_print_fp(stderr,a);
 
1863
                    fprintf(stderr,"\nb=");
 
1864
                    BN_print_fp(stderr,b);
 
1865
                    fprintf(stderr,"\nc=");
 
1866
                    BN_print_fp(stderr,c);
 
1867
                    fprintf(stderr,"\nd=");
 
1868
                    BN_print_fp(stderr,d);
 
1869
                    fprintf(stderr,"\n");
 
1870
                    return 0;
 
1871
                    }
 
1872
                }
 
1873
        BN_free(a);
 
1874
        BN_free(b);
 
1875
        BN_free(c);
 
1876
        BN_free(d);
 
1877
        return(1);
 
1878
        }
 
1879
 
 
1880
int test_lshift1(BIO *bp)
 
1881
        {
 
1882
        BIGNUM *a,*b,*c;
 
1883
        int i;
 
1884
 
 
1885
        a=BN_new();
 
1886
        b=BN_new();
 
1887
        c=BN_new();
 
1888
 
 
1889
        BN_bntest_rand(a,200,0,0); /**/
 
1890
        a->neg=rand_neg();
 
1891
        for (i=0; i<num0; i++)
 
1892
                {
 
1893
                BN_lshift1(b,a);
 
1894
                if (bp != NULL)
 
1895
                        {
 
1896
                        if (!results)
 
1897
                                {
 
1898
                                BN_print(bp,a);
 
1899
                                BIO_puts(bp," * 2");
 
1900
                                BIO_puts(bp," - ");
 
1901
                                }
 
1902
                        BN_print(bp,b);
 
1903
                        BIO_puts(bp,"\n");
 
1904
                        }
 
1905
                BN_add(c,a,a);
 
1906
                BN_sub(a,b,c);
 
1907
                if(!BN_is_zero(a))
 
1908
                    {
 
1909
                    fprintf(stderr,"Left shift one test failed!\n");
 
1910
                    return 0;
 
1911
                    }
 
1912
                
 
1913
                BN_copy(a,b);
 
1914
                }
 
1915
        BN_free(a);
 
1916
        BN_free(b);
 
1917
        BN_free(c);
 
1918
        return(1);
 
1919
        }
 
1920
 
 
1921
int test_rshift(BIO *bp,BN_CTX *ctx)
 
1922
        {
 
1923
        BIGNUM *a,*b,*c,*d,*e;
 
1924
        int i;
 
1925
 
 
1926
        a=BN_new();
 
1927
        b=BN_new();
 
1928
        c=BN_new();
 
1929
        d=BN_new();
 
1930
        e=BN_new();
 
1931
        BN_one(c);
 
1932
 
 
1933
        BN_bntest_rand(a,200,0,0); /**/
 
1934
        a->neg=rand_neg();
 
1935
        for (i=0; i<num0; i++)
 
1936
                {
 
1937
                BN_rshift(b,a,i+1);
 
1938
                BN_add(c,c,c);
 
1939
                if (bp != NULL)
 
1940
                        {
 
1941
                        if (!results)
 
1942
                                {
 
1943
                                BN_print(bp,a);
 
1944
                                BIO_puts(bp," / ");
 
1945
                                BN_print(bp,c);
 
1946
                                BIO_puts(bp," - ");
 
1947
                                }
 
1948
                        BN_print(bp,b);
 
1949
                        BIO_puts(bp,"\n");
 
1950
                        }
 
1951
                BN_div(d,e,a,c,ctx);
 
1952
                BN_sub(d,d,b);
 
1953
                if(!BN_is_zero(d))
 
1954
                    {
 
1955
                    fprintf(stderr,"Right shift test failed!\n");
 
1956
                    return 0;
 
1957
                    }
 
1958
                }
 
1959
        BN_free(a);
 
1960
        BN_free(b);
 
1961
        BN_free(c);
 
1962
        BN_free(d);
 
1963
        BN_free(e);
 
1964
        return(1);
 
1965
        }
 
1966
 
 
1967
int test_rshift1(BIO *bp)
 
1968
        {
 
1969
        BIGNUM *a,*b,*c;
 
1970
        int i;
 
1971
 
 
1972
        a=BN_new();
 
1973
        b=BN_new();
 
1974
        c=BN_new();
 
1975
 
 
1976
        BN_bntest_rand(a,200,0,0); /**/
 
1977
        a->neg=rand_neg();
 
1978
        for (i=0; i<num0; i++)
 
1979
                {
 
1980
                BN_rshift1(b,a);
 
1981
                if (bp != NULL)
 
1982
                        {
 
1983
                        if (!results)
 
1984
                                {
 
1985
                                BN_print(bp,a);
 
1986
                                BIO_puts(bp," / 2");
 
1987
                                BIO_puts(bp," - ");
 
1988
                                }
 
1989
                        BN_print(bp,b);
 
1990
                        BIO_puts(bp,"\n");
 
1991
                        }
 
1992
                BN_sub(c,a,b);
 
1993
                BN_sub(c,c,b);
 
1994
                if(!BN_is_zero(c) && !BN_abs_is_word(c, 1))
 
1995
                    {
 
1996
                    fprintf(stderr,"Right shift one test failed!\n");
 
1997
                    return 0;
 
1998
                    }
 
1999
                BN_copy(a,b);
 
2000
                }
 
2001
        BN_free(a);
 
2002
        BN_free(b);
 
2003
        BN_free(c);
 
2004
        return(1);
 
2005
        }
 
2006
 
 
2007
int rand_neg(void)
 
2008
        {
 
2009
        static unsigned int neg=0;
 
2010
        static int sign[8]={0,0,0,1,1,0,1,1};
 
2011
 
 
2012
        return(sign[(neg++)%8]);
 
2013
        }