rsacomp.pl

#!/usr/local/bin/perl -w
use strict; $|=1; no strict 'refs'; use Math::BigInt lib => 'GMP';
use CGI; use Benchmark;

sub extended_euclid {
  $_[1] or return $_[0], 1, 0;
  my ($d, $x, $y) = extended_euclid ($_[1], $_[0] % $_[1]);
  $d, $y, $x - $y * ($_[0] / $_[1]);
}

sub modexp {
  my ($a, $b, $n) = @_;
  my $d = new Math::BigInt (1);
  my @b = split //, sprintf "%0b", $b;

  for my $i (0..@b-1) {
    $d = $d*$d % $n;
    $d = $d*$a % $n if $b[$i]
  }
  $d    
}

sub loese_mod_eq {
  my ($d, $x, $y) = extended_euclid ($_[0], $_[2]);
  $_[1] % $d ? undef : map { ($x * $_[1] / $d % $_[2] + $_ * $_[2] / $d) % $_[2] } 0..$d-1
}

my $r = new CGI;
print $r->header();

my $y = defined $r->param('y') ? $r->param('y') : 16777216;
my $e = defined $r->param('e') ? $r->param('e') : 0;
my $d = defined $r->param('d') ? $r->param('d') : 80964007;
my $p = defined $r->param('p') ? $r->param('p') : 8999;
my $q = defined $r->param('q') ? $r->param('q') : 9001;
my $i = defined $r->param('i') ? $r->param('i') : 100;
my $m = 0;

$y =~ tr/0-9//cd; $m = length ($y) > $m ? length($y) : $m;
$e =~ tr/0-9//cd; $m = length ($e) > $m ? length($e) : $m;
$d =~ tr/0-9//cd; $m = length ($d) > $m ? length($d) : $m;
$p =~ tr/0-9//cd; $m = length ($p) > $m ? length($p) : $m;
$q =~ tr/0-9//cd; $m = length ($q) > $m ? length($y) : $m;
$i =~ tr/0-9//cd; $i = $m < 50 && $i > 0 && $i <= 300 ? $i : $i < 101 && $i > 0 ? $ i : 100; 

($y, $e, $d, $p, $q) = map { $_ = length($_) < 250 ? $_ : 1; new Math::BigInt ($_) } $y, $e, $d, $p, $q;

$d = $d == 0 ? [loese_mod_eq ($e, 1, (($p-1) * ($q-1)))]->[0] : $d;

my (undef, $Xp, $Xq) = extended_euclid ($p, $q);
my $n = $p*$q;
my $t1 = $Xq*$q;
my $t2 = $Xp*$p;  
my $c2 = [loese_mod_eq ($p,1,$q)]->[0];

sub RSA {
  modexp ($y, $d, $n);
}
  
sub RSASRC {
  my ($xp, $xq) = map { $y->copy()->bmodpow ($d % ($_-1) , $_);  } $p, $q;
  ($xp*$t1 + $xq*$t2) % $n
}

sub RSAMRC {
  my ($xp, $xq) = map { $y->copy()->bmodpow ($d % ($_-1) , $_);  } $p, $q;
  $xp + (($xq-$xp) * $c2 % $q) * $p
}
  
my $fx = RSASRC();

my $fd = $d; my $ffd; my $x;
while ($_ = substr $fd,0,80,'') {
   $ffd .= $_."<br />\n";
}
while ($_ = substr $fx,0,80,'') {
   $x .= $_."<br />\n";
}

my $sd = $r->param('d');
my $se = $r->param('e');
if ((! defined $sd) && (! defined $se)) { $sd = 80964007 }

print <<HEAD
<html>
 <head>
 </head>
 <body>
  <h1>Vergleich von RSA, RSASRC, RSAMRC</h1>
  (Eingabeparameter sind auf max 250 Ziffern beschr&auml;nkt)
HEAD
;
print <<BLERX
  <table borders="0" width="100%">
   <tr>
    <td width="50%" align="left">
  <form method="post" enctype="multipart/form-data">
   y:<input type="text" size="50" maxlength="400" name="y" value="$y"><br />
   d:<input type="text" size="50" maxlength="400" name="d" value="$sd"><br />
   e:<input type="text" size="50" maxlength="400" name="e" value="$se"><br />
   p:<input type="text" size="50" maxlength="400" name="p" value="$p"><br />
   q:<input type="text" size="50" maxlength="400" name="q" value="$q"><br />
   Anzahl der Durchl&auml;ufe (<=300 wenn maxlength < 50, ansonsten <=100):<input type="text" size="5" maxlength="3" name="i" value="$i"><br />
   (entweder d oder e angeben (und die jeweils andere Variable als 0); im Zweifel wird d verwendet)<br />
   <input type="submit" />
  </form>
    </td>
    <td width="50%" align="center">
    210-stellige p und q<br />
  <form method="post" enctype="multipart/form-data">
   <input type="hidden" name="y" value="16777216">
   <input type="hidden" name="e" value="65537">
   <input type="hidden" name="d" value="0">
   <input type="hidden" name="p" value="643808006803554439230129854961492699151386107534013432918073439524138264842370630061369715394739134090922937332590384720397133335969549256322620979036686633213903952966175107096769180017646161851573147596390153">
   <input type="hidden" name="q" value="449417999055441493994709297093108513015373787049558499205492347871729927573118262811508386655998299074566974373711472560655026288668094291699357843464363003144674940345912431129144354948751003607115263071543163">
   <input type="hidden" name="i" value="50">
   <input type="submit" />
  </form>
    </td>
   </tr>
  </table>
  <pre>
BLERX
;
timethis ($i, 'RSA', 'RSA');
timethis ($i, 'RSASRC', 'RSASRC');
timethis ($i, 'RSAMRC', 'RSAMRC');
print <<FOOTER
</pre>
<br />
mit 
<br />d =<br /> $ffd und <br />x = <br /><b>$x</b><br />

 </body>
</html>
FOOTER
;