Introduction

ブログ内検索

  • このサイトの記事を検索 by Google

おすすめの一冊!

無料ブログはココログ

« 素数判定(その2) | トップページ | Apple の戦略 »

2010-04-13

RSA 暗号

多倍長計算の高速化にトライしようと思ったのですが、
その応用のひとつである RSA 暗号について調べていたら、
いつのまにかハマってしまいましたw

    ⇒ RSA暗号  --  Wikipedia

素数判定コードで(確率的)素数を生成してみたので、
それを使ってみよう、という話です。

ポイントは「拡張されたユークリッドの互除法」です。

    ⇒ ユークリッドの互除法  --  Wikipedia

「d×e + χ×φ = 1」の「d」を求める計算なのですが、
最初は係数の計算方法がぜんぜん理解できなくて、
紙に式変形を書いてみてようやくコードに起こせました。

その上、コードを書いてみると「χ」じゃなくて「d」が
負になってしまって、これを補正する方法が分からず
しばらく悩みました。

「d」が求まれば、暗号化&復号化は bmodpow() で一発です。

できたコードが↓

#!/usr/bin/perl -w ############################################################################## # RSA crypt sample ############################################################################## use strict; use warnings; use Math::BigInt lib => 'GMP'; use Math::Random::MT qw(srand rand); #============================================================================= sub rand32 { return (int(rand(0x10000)) << 16) | (int(rand(0x10000))); } sub rand_inf { my $arg = shift; if (ref($arg)) { # object of Math::BigInt my $x = substr($arg->as_hex(), 2); # 先頭の "0x" は削っておく my $ntimes = int((length($x) / 8)); my $y = '0x'; if (length($x) % 8 != 0) { my $limit = hex(substr($x, 0, length($x)-8*$ntimes)); $y .= sprintf("%x", rand32() % $limit); } for (my $i =0; $i < $ntimes; $i++) { $y .= sprintf("%08x", rand32()); } return Math::BigInt->new($y); } else { return int(rand($arg)); } } #============================================================================= sub gcd { my $m = shift; my $n = shift; $m = Math::BigInt->new($m) unless (ref($m)); $n = Math::BigInt->new($n) unless (ref($n)); if ($m->bcmp($n) < 0) { # swap my $k = $m; $m = $n; $n = $k; } while (! $n->is_zero()) { my $r = $m->copy()->bmod($n); $m = $n; $n = $r; } return $m; } sub gcd_ext { # 「拡張されたユークリッドの互除法」 by Wikipedia my $m0 = shift; my $n0 = shift; $m0 = Math::BigInt->new($m0) unless (ref($m0)); $n0 = Math::BigInt->new($n0) unless (ref($n0)); my $m = $m0; my $n = $n0; my @a = (Math::BigInt->new('0'), Math::BigInt->new('1')); my @b = (Math::BigInt->new('1'), Math::BigInt->new('0')); # die if ($m->bcmp($n) < 0); while (! $n->is_one()) { my ($q, $r) = $m->copy()->bdiv($n); die if ($r->is_zero()); # 入力は互いに素のハズ unshift(@a, $a[1] - $q * $a[0]); unshift(@b, $b[1] - $q * $b[0]); $m = $n; $n = $r; } if ($a[0] < 0) { $a[0] += $n0; $b[0] -= $m0; } die if ($a[0]->is_neg()); return +($a[0], $b[0]); } #============================================================================= { # 4096bit probable prime number my $p = Math::BigInt->new('★素数その1★'); my $q = Math::BigInt->new('★素数その2★'); my $n = $p * $q; my $e = 65537; # =2^16+1 my @coeff = gcd_ext($e, ($p-1)*($q-1)); print $coeff[0]->as_hex() . "\t" . $coeff[1]->as_hex() . "\n"; # 検算 print +($coeff[0] * $e + $coeff[1] * ($p-1)*($q-1))->as_hex() . "\n"; print +(($coeff[0] * $e)->copy()->bmod(($p-1)*($q-1)))->as_hex() . "\n"; my $d = $coeff[0]; # RSA 暗号の動作確認 my $max = Math::BigInt->new('0x1' . ('0' x (512 / 4))); foreach my $i (1..1024) { local $| = 1; print sprintf("%10d ", $i); print "running..."; my $original = rand_inf($max); print "encoding..."; my $encoded = $original->copy()->bmodpow($e, $n); print "decoding..."; my $decoded = $encoded->copy()->bmodpow($d, $n); print "comparing..."; my $is_ok = ($decoded->bcmp($original) == 0); if ($is_ok) { print "OK\n"; } else { print "ERROR\n"; die; } } } ############################################################################## ##############################################################################
素数を2個与えると、公開鍵を生成して、1024個の乱数に対して 「暗号化⇒復号化⇒比較」をやります。 コードを書いてみて、とりあえず RSA 暗号の基礎が理解できたかんじです。 充実した休日になりました♪

« 素数判定(その2) | トップページ | Apple の戦略 »