Perl - RSA 暗号の仕組みを見てみる

ssh-keygen すると作られる id_rsa, id_rsa.pub でその名を知ってる RSA 暗号の仕組みを Perl を使って見てみる。
RSA 暗号の説明は

にある。簡単に流れを書くと、

  1. 大きな２つの素数 p, q を用意する。今回使った Crypt::Primes では Ueli Maurer's algorithm というのを使って生成しているらしい。
  2. n = pq、 e を (p-1)(q-1) と互いに素な数(実際には素数にとってる)、 d を e の (p-1)(q-1) を法としたときの逆元とする。
  3. このときペア (n, e) が公開鍵、ペア (n, d) が秘密鍵になる。公開鍵はみんなに公開して、秘密鍵は直隠しにしておく。
  4. さて友達が自分にメッセージ x を秘密裏に送りたいとする。ここで x は適当な変換規則のもと正の整数であるとしていいだろう。この整数 x を送りたい。
  5. このときその友達は皆に公開されている公開鍵 (n, e) を使って x から次のように y を作る。すなわち n を法として x^e を計算し、その結果を y とする。それを自分に送ってもらう。
  6. 届いた y から自分だけが知っている秘密鍵 (n, d) を使って次のように z を作る。すなわち n を法として y^d を計算し、その結果を z とする。
  7. すると・・・・ z=x で友達のメッセージになってる！

という感じ。 なぜ z=x になるかは上記２つに説明があるし、途中の経路で y が盗聴されたとき x が分かることがないのかについてもコメントがある。

#!/usr/bin/env perl
use Math::Pari qw|Mod lift|;
use Crypt::Primes qw(rsaparams);
use strict;
use warnings;

my $hash_ref = rsaparams(
    # $p, $q のビット数を指定
    Size => 512,
    Verbosity => 1
);
print "\n";

my ($p, $q, $e) = @{$hash_ref}{qw|p q e|};
my $n = $p * $q;
my $d = 1 / Mod($e, ($p - 1) * ($q - 1));

print '$p = ', $p, "\n\n";
print '$q = ', $q, "\n\n";
print '$n = ', $n, "\n";
print 'The number of digits of $n is ', int(log($n) / log(10)) + 1, "\n\n";

print '$e = ', $e, "\n\n";
print '$d = ', lift($d), "\n\n";

print "Write a message:\n";
chomp(my $text = <STDIN>);
my $x = "1";
for (split //, $text) {
    $x .= sprintf "%03d", unpack("C", $_);
}
print "\n";
print '$x = ', $x, "\n\n";

my $y = Mod($x, $n) ** $e;
print '$y = ', lift($y), "\n\n";

my $z =  Mod(lift($y), $n) ** lift($d);
print '$z = ', lift($z), "\n\n";

print "The decoded message:\n";
my @result = split //, lift($z);
shift @result;
while (@result) {
    print chr( join "", splice(@result, 0, 3) );
}
print "\n";

これを保存して実行すると例えば以下のようになる。メッセージの入力は英数字しか想定してないので注意。

.+(35)...+...+.+....+...........+........+(64)...+.+.....+.................................+..............+...+.......+..........................+......+.....+.+(98)..........................+.+.......................+.....+..+......+.+.+.......+..........+..+.....+..............+........+.....+...+.............+.......+....+.......+(178)..+.......+.......+....+...................+...................+....................+.........+................................+.....................+..+..+..+.+..+..+.....+..+........................+.......+...........+(335).+.............+......+..+..............+....................................+......................+.......+.+...........+.+.+.........+.+......+..+....................+.........+(512)
.+.+.........+....+...................+..+(23)...+(42).+(61)......+...+....+..+(105).........+(137)........+...................+....+..+..........................................+.+.+(260).....+.........+...+.+..........+......+..........+(347)...........+...+......+..+.....+....+(512)

$p = 9716480492314544783214255257421609472287343537071096370008628437355733043309155501183135337132693841382455184809339273332061060216695454792837240639850491

$q = 8373931916657071101048618535703527170288087424118653295456688995988406457501574406296157144980498012603226154076328024847997291100486008418450601188178711

$n = 81365146112168577806571694199042228401433182884518773329974304497493222741372435847405480377925426566904280811304956159449751025191292152813099255904201126103634298831669101395006897902379422443915124549934965314592864719715581810043624047703042869120255773748653537522116895556027760831874485498971629097101
The number of digits of $n is 308

$e = 65537

$d = 68103286540168261220066379072714061354053698630243638113061941700260779917878220980658675650870489560515957762853554024850330233102954530151861691603597231793723953923329099986010367617615281286688416941925395169629427470089047762597523877506771903908517022207799338198209875926957921730370789734829565551973

Write a message:
I wish you every happiness.

$x = 1073032119105115104032121111117032101118101114121032104097112112105110101115115046

$y = 29865452171438440322003352910164666780856731167390025140995817875585459662603776230337727876626022195156107128833954820071974911773362893459220472426641334902535129147241506824115607076710603117479619452903992913573678566089745319283461914477703194635316988605105747678890341691772785326210316690554593947888

$z = 1073032119105115104032121111117032101118101114121032104097112112105110101115115046

The decoded message:
I wish you every happiness.

少しは分かった気になったぜ。