#!/usr/bin/perl
#this does 16 bit RSA showing 1:Many keys
#use "perl rsa.pl 1" for a fast demo
#other values get very slow but you can use bc to show the calculations do work

$|=1;		# dont buffer output 
$arg=shift;	# takes an arg as data to encrypt
$wanted_keys=10;	# how many keys do we want
# we decrypt with the last key

#require bigint;
use Math::BigInt ':constant';

$p=61;	# common example  Should be prime
#$p=67;


$q=53;	# common example  Should be prime
#$q=123;	# 
$e=17;	# commonly a Mersenne Prime # if its too big this gets very slow
#$e=65537;


$pq=$p*$q;

$t=5;	#default data to decrypt
$t=$arg if($arg);	#if number on a command line use it

#encrypt data into et
$et=($t ** $e) % ($pq);
print "$et=($t ^ $e) % ($pq);\n";

##########
# find other key

#now we find a $d that works... There may be several
$x=$dd=$count=1;
while($dd ||  $count<$wanted_keys+1) {
	#$ff=($d=($x*($p-1)*($q-1)+1)/$e))*$e;
	# This is just another way to do the Euclidian algorithm for people
	# that don't want to do the hard math route.
	$ff=($d=($x*($p-1)*($q-1)+1)/$e)*$e;;
	$ee=($x*($p-1)*($q-1)+1);
	$dd=$ff-$ee;
	print "x=$x d=$d ff=$ff ee=$ee $dd\n" unless $dd;
	$count++ unless $dd;
	#print "$count is count\n";
	$x++;
}

print "solving ($et ^ $d) % ($pq) so it might take a long time\n";
$dt=($et ** $d) % ($pq);
print "$dt=($et ** $d) % ($pq);\n";

print $dt,"\n";

print "P: $p  Q: $q\n";
print "Private Exponent $e\n";
print "Public Exponent $d\n";
print "Moduls: $pq\n";
print "Plain Text: $t\n";
print "Encrtyped Text: $et\n";
print "Decrtyped Text: $dt\n";