Cryptopals 40 - Implement an E=3 RSA Broadcast attack

TL;DR

Challenge 40 in Cryptopals.

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!

ETOOBUSY 🚀 minimal blogging for the impatient