素因数分解を使った暗号化

Menu

二重鍵暗号には二つの関数EとDを使う。

   E(D(x)) = x 
   D(E(x)) = x

となる。

E/D にはフェルマーの小定理を使った方式がある。mod は剰余類による演算を表す。剰余類では可換則や分配則がそのまま成り立つことを思い出そう。

p が素数で， a が p の倍数でない正の整数のとき

\( \)
\( a ^ {p − 1} ≡ 1 \bmod p \)
\( \)

つまり、剰余類で指数乗の計算をすると、素数-1の時に1に戻ることを利用する。

二つの素数3,5を使った以下の関数

\( \)
\( E x = x^{11} \bmod 15\)
\( D x = x^3 \bmod 15\)
\( \)

を二重鍵暗号として使うことができる。15は3と5の積である。11と3は、それを使って求めた鍵ペアである。(鍵ペアの条件は、 (3-1)(5-1) = 8 と互いに素な鍵k1、\(k1 * k2 ≡ 1 \bmod 8 \) なk2だが、ここでは使わない)

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";