rsa.pl

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

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 extended_euclid {
  $_[1] or return $_[0], 1, 0;
  my ($d, $x, $y) = extended_euclid ($_[1], $_[0] % $_[1]);
  $d, $y, $x - $y * ($_[0] / $_[1])	
}

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

sub RSA {
  modexp $_[0], $_[1], $_[2]
}

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

my $z = defined $r->param('z') ? $r->param('z') : 16777216;
my $e = defined $r->param('e') ? $r->param('e') : 2**16+1;
my $p = defined $r->param('p') ? $r->param('p') : 8999;
my $q = defined $r->param('q') ? $r->param('q') : 9001;

($z, $e, $p, $q) = map { $_ =~ tr/0-9//cd;
                         $_ = length($_) <= 300 ? $_ : 1; 
                         new Math::BigInt ($_) } 
                   $z, $e, $p, $q;

my $PHIn = ($p-1)*($q-1);
my $d = [solve_mod_eq ($e, 1, $PHIn)]->[0];
my $n = $p*$q;
my $x = RSA ($z, $d, $n);
my $y = RSA ($z, $e, $n);

sub bl {
  my $f = shift; my $r;
  while ($_ = substr $f,0,80,'') {
    $r .= $_."<br />\n"
  }
  $r
}

($d, $x, $y, $n, $PHIn) = map { my $a = bl "$_"; length $a > 80 ? 
                         "<br />\n".$a : $a }
                   $d, $x, $y, $n, $PHIn;

print <<HEAD
<html>
 <head>
 </head>
 <body>
  <h1>rsa (x,e,n) and rsa (y,d,n)</h1>
  (Input parameters are limited to 300 digits)
  <table borders="0" width="100%">
   <tr>
    <td width="50%" align="left">
     <form method="post" enctype="multipart/form-data">
      <table borders="0">
       <tr><td>x/y:</td><td><input type="text" size="50" maxlength="400" name="z" value="$z"></td></tr>
       <tr><td>e:</td><td><input type="text" size="50" maxlength="400" name="e" value="$e"></td></tr>
       <tr><td>p:</td><td><input type="text" size="50" maxlength="400" name="p" value="$p"></td></tr>
       <tr><td>q:</td><td><input type="text" size="50" maxlength="400" name="q" value="$q"></td></tr>
      </table>
      <input type="submit" />
     </form>
    </td>
    <td width="50%" align="center">
     example with 210-digit p and 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="p" value="643808006803554439230129854961492699151386107534013432918073439524138264842370630061369715394739134090922937332590384720397133335969549256322620979036686633213903952966175107096769180017646161851573147596390153">
      <input type="hidden" name="q" value="449417999055441493994709297093108513015373787049558499205492347871729927573118262811508386655998299074566974373711472560655026288668094291699357843464363003144674940345912431129144354948751003607115263071543163">
      <input type="submit" />
     </form>
    </td>
   </tr>
  </table> 
  <p>
   n = p*q = $n
   &Phi;(n) = $PHIn
   d = solve_mod_eq (e, 1, &Phi;(n)) = $d
   e_RSA(x,e,n) = <b>$y</b>
   d_RSA(y,d,n) = <b>$x</b>
  </p>
  <p><a href="http://a.wirebrain.de/krypto/">Back to Exercises</a></p>
 </body>
</html>
HEAD
;