#!/usr/bin/perl
$|=1;

# Usage: check.pl flag key1 key2 ...
#
# flag is encrypted text with one of the keys
# keys must be RSA private key files as generated by OpenSSL, either DER or PEM
#
# this will test output of generate-keys-and-flag.pl
# the algorithm is quite inefficient for large number of keys
# see facthacks.cr.yp.to for scripts that work with arbitrary amount of keys

use strict;
use Math::BigInt;
use Convert::ASN1;
use MIME::Base64;
use File::Temp;
use Data::Dumper;

# ASN.1 templates: OpenSSL Public key file
my $asn = Convert::ASN1->new;
$asn->prepare(q<
    SEQUENCE {
      SEQUENCE {
         oid OBJECT_IDENTIFIER,
         null NULL
      },
      key BIT_STRING
    }
  >);

# Bit String contains another ASN.1 object
my $innerasn = Convert::ASN1->new;
$innerasn->prepare(q<
    SEQUENCE {
      n INTEGER,
      e INTEGER
    }
  >);

# OpenSSL private key file
my $privasn = Convert::ASN1->new;
$privasn->prepare(q<
    SEQUENCE {
      id INTEGER,
      n INTEGER,
      e INTEGER,
      d INTEGER,
      p INTEGER,
      q INTEGER,
      e1 INTEGER,
      e2 INTEGER,
      coef INTEGER
    }
  >);

# Read Public key file
# Parameters: file name
# Returns: modulus of the key

sub readkey {
	open(my $fh, "<", $_[0]) or die "unable to open $_[0]: $!";
	my $der = do { local $/; <$fh> };
	close($fh);
	$der = decode_base64($der =~ s/^-.*?\n//gmr) if $der =~ m/^-----BEGIN (RSA )?PUBLIC KEY----/;
	my $bstr = $asn->decode($der);
	die "unable to parse RSA public key $_[0]: ".$asn->error() if (not $bstr);
	my $key = $bstr->{'key'}[0];
	my $decoded = $innerasn->decode($key);
	die "unable to parse RSA public key $_[0]: ".$asn->error() if (not $decoded);
	return($decoded->{'n'});
}


# Entry point is here
die "must specify flag and at least two public key files as arguments" if $#ARGV < 2;

# consume first command line argument
my $flag = shift;
die "$flag: $!" unless -s $flag;

# everything else is expected to be public keys
print "Reading public keys\n";
my %moduli = map { $_ => readkey($_) } @ARGV;

print Dumper (keys %moduli);

# run the attack
print "Computing gcd-s ";
my $i = 0;
for my $key1 (keys %moduli) {
	my $j = 0;
	my $n1 = Math::BigInt->new($moduli{$key1});
	for my $key2 (keys %moduli) {
		next unless $j++ > $i+1;
		
		my $n2=Math::BigInt->new($moduli{$key2});
		my $p=$n1->copy()->bgcd($n2);
		next if $p == 1;

		print "\nPrime $p found in $key1 and $key2\n";

		# try to decrypt the message with both of them
		for my $q ($n1->copy()->bdiv($p), $n2->copy()->bdiv($p)) {
			my $p1=$p->copy()->bsub(1);
			my $q1=$q->copy()->bsub(1);
			my $e=Math::BigInt->new(65537);
			my $n=$p->copy()->bmul($q);
			my $d=$e->copy()->bmodinv($p1->copy()->bmul($q1));
			my $e1=$d->copy()->bmod($p1);
			my $e2=$d->copy()->bmod($q1);
			my $qinv = $q->copy()->bmodinv($p);

			# save the recovered key to a temporary file and call openssl
			my $fh = File::Temp->new() or die "tempfile: $!";
			print $fh $privasn->encode(id => 0,
				n=>$n, e=>$e, d=>$d, p=>$p, q=>$q, e1=>$e1, e2=>$e2, coef=>$qinv);
			$fh->flush();
			my $rc = system("openssl rsautl -decrypt -in $flag -keyform der -inkey ".$fh->filename." ");
			close($fh);

			# stop if found
			exit(0) if $rc == 0;
		}
	}
	$i++;
	print ".";
}

die "\nUnable to decrypt the flag! ***** ";