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

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

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

となる。

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

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

$a^{p - 1} \equiv 1 mod p$

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

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

$E x = x^{11} mod 15$
$D x = x^{3} mod 15$

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

k 1 * k 2 \equiv 1 mod 8

なk2だが、ここでは使わない)

7をメッセージとして、暗号化したら y になったとする。y を求め、以下の式を検算せよ。

   D(E(7)) = 7
   E(D(y)) = y

ただし、、

7^{2} \equiv 4 mod 15, 4^{2} \equiv 1 mod 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";