TL;DR

This took me a bit because I messed up and used the toy RSA implementation where the default $e = 0x10001$ is used.

I already implemented the Generalized Chinese Remainder Theorem, which also proved to be overkill in this case (especially when trying out with low prime values). So I used this instead:

sub chinese_remainder_theorem {
die "no inputs" unless scalar @_;
die "need an even number of inputs" if scalar(@_) % 2 == 1;
my ($N,$R) = splice @_, 0, 2;
while (@_) {
my ($n,$r) = splice @_, 0, 2;
my ($gcd,$x, $y) = egcd($N, $n); die "not coprimes!\n" if$gcd > 1;
my $P =$N * $n; ($N, $R) = ($P, ($r *$x * $N +$R * $y *$n) % $P); } return ($N, $R); }  With big primes the chance of getting non-coprimes is definitely smaller, but still itโs better to fail fast in this case. Moreoverโฆ it works great! All in all, hereโs the total code: #!/usr/bin/env perl use v5.24; use warnings; use experimental 'signatures'; no warnings 'experimental::signatures'; use File::Basename 'dirname'; use lib dirname(__FILE__), dirname(__FILE__) . '/local/lib/perl5'; use Math::Prime::Util 'random_maurer_prime'; use Math::BigInt; use ToyRSA; use List::Util 'min'; my$n_bits = shift // 1024;
my @p1 = rsa_new_keys($n_bits); my @p2 = rsa_new_keys($n_bits);
my @p3 = rsa_new_keys($n_bits); my$min_n = min ($p1[0][1],$p2[0][1], $p3[0][1]); my$plaintext = random_bigint_upto($min_n); my$c1 = ToyRSA::toy_rsa_apply($plaintext,$p1[0]);
my $c2 = ToyRSA::toy_rsa_apply($plaintext, $p2[0]); my$c3 = ToyRSA::toy_rsa_apply($plaintext,$p3[0]);

my ($N,$R) = chinese_remainder_theorem_bi(
$p1[0][1],$c1, $p2[0][1],$c2, $p3[0][1],$c3
);

my $recovered =$R;
$recovered->broot(3); printout(plaintext =>$plaintext);
printout(recovered => $recovered); printout(difference =>$plaintext - $recovered); sub printout ($name, $value) {$value = substr($value, 0, 27) . '...' if length($value) > 30;
say "$name<$value>";
}

sub rsa_new_keys ($n_bits) { my$p = my $q = prime_2_mod_3($n_bits);
$q = prime_2_mod_3($n_bits) while $p ==$q;
ToyRSA::toy_rsa_keys($p,$q, Math::BigInt->new(3));
}

# provide a list of modulus1, reminder1, modulus2, ...
sub chinese_remainder_theorem {
die "no inputs" unless scalar @_;
die "need an even number of inputs" if scalar(@_) % 2 == 1;
my ($N,$R) = splice @_, 0, 2;
while (@_) {
my ($n,$r) = splice @_, 0, 2;
my ($gcd,$x, $y) = egcd($N, $n); die "not coprimes!\n" if$gcd > 1;
my $P =$N * $n; ($N, $R) = ($P, ($r *$x * $N +$R * $y *$n) % $P); } return ($N, $R); } sub chinese_remainder_theorem_bi { require Math::BigInt; return chinese_remainder_theorem(map { Math::BigInt->new($_) } @_);
}

sub egcd {    # https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
my ($X,$x, $Y,$y, $A,$B, $q) = (1, 0, 0, 1, @_); while ($A) {
($A,$B, $q) = ($B % $A,$A, int($B /$A));
($x,$X, $y,$Y) = ($X,$x - $q *$X, $Y,$y - $q *$Y);
}
return ($B,$x, $y); } ## end sub egcd sub prime_2_mod_3 ($n_bits) {
while ('necessary') {
my $p = random_maurer_prime($n_bits);
return $p if 2 ==$p % 3;
}
}

sub random_bigint_upto ($sup) { my$n_hex = length $sup->to_hex; while ('necessary') { my$candidate_hex = join '',
map { sprintf '%0x', int rand 16 } 1 .. $n_hex; my$candidate = Math::BigInt->from_hex($candidate_hex); return$candidate if $candidate <$sup;
}
}


Sample run:

\$ perl 40.pl
plaintext<355238216293201373596304656...>
recovered<355238216293201373596304656...>
difference<0>


The recovered plaintext is indeed the right one!

Stay safe and secure!

Comments? Octodon, , GitHub, Reddit, or drop me a line!