単純なRSA暗号の解き方

以下のような感じで"ABCD"を暗号化する。

use strict;
use warnings;
use Crypt::RSA;
use Crypt::RSA::Primitives;

my $rsa = Crypt::RSA->new; 
my ($public, $private) = $rsa->keygen(Size => 48) or die;
print $public->serialize, "\n";

my $prim = Crypt::RSA::Primitives->new;
my $message = unpack "L", "ABCD";
my $ctxt = $prim->core_encrypt (Key => $public, Plaintext => $message); 
print $ctxt, "\n";

__END__
$VAR1 = bless( {
                 'e' => 65537,
                 'n' => '194139431103601',
                 'Version' => '1.99'
               }, 'Crypt::RSA::Key::Public' );

24691280678209

公開鍵(65537, 194139431103601) を使って"ABCD" を暗号化し、24691280678209という暗号を得たという状況だ。$privateキーを持ってる人なら、もちろん復号できる。

my $prim = Crypt::RSA::Primitives->new;
my $ptxt = $prim->core_decrypt (Key => $private, Cyphertext => 24691280678209);
print pack("L", $ptxt), "\n";

__END__
ABCD

しかし、こんな貧弱なキーであれば秘密鍵を持っていなくとも、自分で破ることができる。

まず、公開鍵の"法"である194139431103601を以下のスクリプトで分離する。

sub gcd($$) {
  my ($n, $m) = @_;
  ($n, $m) = ($m, $n) if $n > $m;
  while ($n) {
    ($n, $m) = ($m % $n, $n);
  }
  return $m;
}

sub pollard_rho($) {
    my $n = shift;
    return 2 if $n % 2 == 0;

    my $x = int(rand($n - 1)) + 1;
    my $y = $x;
    my $c = int(rand($n - 1)) + 1;
    my $g = 1;
    while ($g == 1) {            
        $x = (($x * $x) % $n + $c) % $n;
        $y = (($y * $y) % $n + $c) % $n;
        $y = (($y * $y) % $n + $c) % $n;
        $g = gcd(abs($x - $y), $n);
    } 
    return $g;
}

print pollard_rho(194139431103601), "\n";

__END__
14726531

14726531 と 13182971 に素因数分解できることがわかった。そしたら次は、公開鍵 65537 を使い、以下のスクリプトで秘密鍵を求める。

sub ex_gcd($$) {
    my ($x, $y) = @_;
    my $r0 = $x;
    my $r1 = $y;
    my $a0 = 1; 
    my $a1 = 0;
    my $b0 = 0;
    my $b1 = 1;
    while ($r1 > 0){
        $q1 = int($r0 / $r1);
        $r2 = $r0 % $r1;
        $a2 = $a0 - $q1 * $a1;
        $b2 = $b0 - $q1 * $b1;
        $r0 = $r1;
        $r1 = $r2;
        $a0 = $a1;
        $a1 = $a2;
        $b0 = $b1;
        $b1 = $b2;
    }
    return $a0, $b0, $r0;
}

print join(',', ex_gcd(65537, (14726531 - 1) * (13182971 - 1))), "\n";

__END__
76190021669473,-25720,1

秘密鍵 76190021669473 を得た。これで暗号 24691280678209 を解読できる。要は$privateを使っているのと同じことだが、以下のスクリプトで解読ができる。

use Crypt::RSA::Primitives;
my $orig = Crypt::RSA::Primitives::mod_exp(
    24691280678209, 76190021669473, 194139431103601
);
print pack("L", $orig), "\n";

__END__
ABCD

このエントリのコードは、こちらとかここを読んで実装している。