bntests.pl 4.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156
  1. #! /usr/bin/env perl
  2. # Copyright 2008-2016 The OpenSSL Project Authors. All Rights Reserved.
  3. #
  4. # Licensed under the OpenSSL license (the "License"). You may not use
  5. # this file except in compliance with the License. You can obtain a copy
  6. # in the file LICENSE in the source distribution or at
  7. # https://www.openssl.org/source/license.html
  8. # Run the tests specified in bntests.txt, as a check against OpenSSL.
  9. use strict;
  10. use warnings;
  11. use Math::BigInt;
  12. my $EXPECTED_FAILURES = 0;
  13. my $failures = 0;
  14. sub bn
  15. {
  16. my $x = shift;
  17. my ($sign, $hex) = ($x =~ /^([+\-]?)(.*)$/);
  18. $hex = '0x' . $hex if $hex !~ /^0x/;
  19. return Math::BigInt->from_hex($sign.$hex);
  20. }
  21. sub evaluate
  22. {
  23. my $lineno = shift;
  24. my %s = @_;
  25. if ( defined $s{'Sum'} ) {
  26. # Sum = A + B
  27. my $sum = bn($s{'Sum'});
  28. my $a = bn($s{'A'});
  29. my $b = bn($s{'B'});
  30. return if $sum == $a + $b;
  31. } elsif ( defined $s{'LShift1'} ) {
  32. # LShift1 = A * 2
  33. my $lshift1 = bn($s{'LShift1'});
  34. my $a = bn($s{'A'});
  35. return if $lshift1 == $a->bmul(2);
  36. } elsif ( defined $s{'LShift'} ) {
  37. # LShift = A * 2**N
  38. my $lshift = bn($s{'LShift'});
  39. my $a = bn($s{'A'});
  40. my $n = bn($s{'N'});
  41. return if $lshift == $a->blsft($n);
  42. } elsif ( defined $s{'RShift'} ) {
  43. # RShift = A / 2**N
  44. my $rshift = bn($s{'RShift'});
  45. my $a = bn($s{'A'});
  46. my $n = bn($s{'N'});
  47. return if $rshift == $a->brsft($n);
  48. } elsif ( defined $s{'Square'} ) {
  49. # Square = A * A
  50. my $square = bn($s{'Square'});
  51. my $a = bn($s{'A'});
  52. return if $square == $a->bmul($a);
  53. } elsif ( defined $s{'Product'} ) {
  54. # Product = A * B
  55. my $product = bn($s{'Product'});
  56. my $a = bn($s{'A'});
  57. my $b = bn($s{'B'});
  58. return if $product == $a->bmul($b);
  59. } elsif ( defined $s{'Quotient'} ) {
  60. # Quotient = A / B
  61. # Remainder = A - B * Quotient
  62. my $quotient = bn($s{'Quotient'});
  63. my $remainder = bn($s{'Remainder'});
  64. my $a = bn($s{'A'});
  65. my $b = bn($s{'B'});
  66. # First the remainder test.
  67. $b->bmul($quotient);
  68. my $rempassed = $remainder == $a->bsub($b) ? 1 : 0;
  69. # Math::BigInt->bdiv() is documented to do floored division,
  70. # i.e. 1 / -4 = -1, while OpenSSL BN_div does truncated
  71. # division, i.e. 1 / -4 = 0. We need to make the operation
  72. # work like OpenSSL's BN_div to be able to verify.
  73. $a = bn($s{'A'});
  74. $b = bn($s{'B'});
  75. my $neg = $a->is_neg() ? !$b->is_neg() : $b->is_neg();
  76. $a->babs();
  77. $b->babs();
  78. $a->bdiv($b);
  79. $a->bneg() if $neg;
  80. return if $rempassed && $quotient == $a;
  81. } elsif ( defined $s{'ModMul'} ) {
  82. # ModMul = (A * B) mod M
  83. my $modmul = bn($s{'ModMul'});
  84. my $a = bn($s{'A'});
  85. my $b = bn($s{'B'});
  86. my $m = bn($s{'M'});
  87. $a->bmul($b);
  88. return if $modmul == $a->bmod($m);
  89. } elsif ( defined $s{'ModExp'} ) {
  90. # ModExp = (A ** E) mod M
  91. my $modexp = bn($s{'ModExp'});
  92. my $a = bn($s{'A'});
  93. my $e = bn($s{'E'});
  94. my $m = bn($s{'M'});
  95. return if $modexp == $a->bmodpow($e, $m);
  96. } elsif ( defined $s{'Exp'} ) {
  97. my $exp = bn($s{'Exp'});
  98. my $a = bn($s{'A'});
  99. my $e = bn($s{'E'});
  100. return if $exp == $a ** $e;
  101. } elsif ( defined $s{'ModSqrt'} ) {
  102. # (ModSqrt * ModSqrt) mod P = A mod P
  103. my $modsqrt = bn($s{'ModSqrt'});
  104. my $a = bn($s{'A'});
  105. my $p = bn($s{'P'});
  106. $modsqrt->bmul($modsqrt);
  107. $modsqrt->bmod($p);
  108. $a->bmod($p);
  109. return if $modsqrt == $a;
  110. } else {
  111. print "# Unknown test: ";
  112. }
  113. $failures++;
  114. print "# #$failures Test (before line $lineno) failed\n";
  115. foreach ( keys %s ) {
  116. print "$_ = $s{$_}\n";
  117. }
  118. print "\n";
  119. }
  120. my $infile = shift || 'bntests.txt';
  121. die "No such file, $infile" unless -f $infile;
  122. open my $IN, $infile || die "Can't read $infile, $!\n";
  123. my %stanza = ();
  124. my $l = 0;
  125. while ( <$IN> ) {
  126. $l++;
  127. s|\R$||;
  128. next if /^#/;
  129. if ( /^$/ ) {
  130. if ( keys %stanza ) {
  131. evaluate($l, %stanza);
  132. %stanza = ();
  133. }
  134. next;
  135. }
  136. # Parse 'key = value'
  137. if ( ! /\s*([^\s]*)\s*=\s*(.*)\s*/ ) {
  138. print "Skipping $_\n";
  139. next;
  140. }
  141. $stanza{$1} = $2;
  142. };
  143. evaluate($l, %stanza) if keys %stanza;
  144. die "Got $failures, expected $EXPECTED_FAILURES"
  145. if $infile eq 'bntests.txt' and $failures != $EXPECTED_FAILURES;
  146. close($IN)