素因数分解を使った暗号化
Menu二重鍵暗号には二つの関数EとDを使う。
E(D(x)) = x D(E(x)) = xとなる。
E/D にはフェルマーの小定理を使った方式がある。mod は剰余類による演算を表す。剰余類では可換則や分配則がそのまま成り立つことを思い出そう。
p が素数で, a が p の倍数でない正の整数のとき
\(
\)
\(
a ^ {p − 1} ≡ 1 \bmod p \)
\(
\)
二つの素数3,5を使った以下の関数
\(
\)
\(
E x = x^{11} \bmod 15\)
\(
D x = x^3 \bmod 15\)
\(
\)
7をメッセージとして、暗号化したら y になったとする。y を求め、以下の式を検算せよ。
D(E(7)) = 7 E(D(y)) = yただし、、\(7^2 ≡ 4 \bmod 15,4^2 ≡ 1 \bmod 15\) に注意する。
以下の Perl script を使っても良い。
#!/usr/bin/perl sub modpow { # b^e mod m my ($b, $e, $m) = @_; my $result = 1; while ($e > 0) { if (($e & 1) == 1) { $result = ($result * $b) % $m; } $e >>= 1; $b = ($b * $b) % $m; } return $result; } print &modpow(@ARGV),"\n";