openssl/crypto/bn/bntest.c - Issue 2072073002: Delete bundled copy of OpenSSL and replace with README.

Side by Side Diff: openssl/crypto/bn/bntest.c

Issue 2072073002: Delete bundled copy of OpenSSL and replace with README. (Closed) Base URL: https://chromium.googlesource.com/chromium/deps/openssl@master

Patch Set: Delete bundled copy of OpenSSL and replace with README. Created 4 years, 6 months ago

Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.

Jump to:

View unified diff | Download patch

OLD	NEW
	(Empty)
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+i10,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+i10,0,0); /*/

858 BN_bntest_rand(b,425+i11,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 rem ainder

883 * (new with OpenSSL 0.9.7, previous ver sions of

884 * BN_mod_mul could generate negative re sults)

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+i5,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+i5,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+i5,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 = ac + dc. /

1225 if(!BN_is_zero(f))

1226 {

1227 fprintf(stderr,"GF(2^m) modular multiplication t est 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 aa = a^2. /

1288 if(!BN_is_zero(d))

1289 {

1290 fprintf(stderr,"GF(2^m) modular squaring test fa iled!\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 f ailed!\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 fa iled!\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^ca^d. /

1475 if(!BN_is_zero(f))

1476 {

1477 fprintf(stderr,"GF(2^m) modular exponentiation t est 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 qu adratic 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, ct x)

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 fai led\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 er r;

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 mo dulo 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 }

OLD	NEW

« no previous file with comments | « openssl/crypto/bn/bnspeed.c ('k') | openssl/crypto/bn/divtest.c » ('j') | no next file with comments »