RSA暗号について。

1. RSA暗号のアルゴリズム
2. RSA暗号の実験
3. あとがき
4. 付録
5. この文章の更新予定

1. RSA暗号のアルゴリズム

暗号化アルゴリズム

「互いに素」の素数a,bを探し出す。
この素数の積c=a*bは、暗号化したい数値より大きくなければならない。
そして素数の積cと互いに素の数dを適当に探す。
互いに素の素数a,bよりオイラー数e=(a-1)*(b-1)を求める。
オイラー数eを法とした先ほど探した数dの逆元fを求める。

c,dが公開鍵であり、fが秘密鍵になる。

逆元fを表示するプログラム
Ubasic: print modinv(d,e)

暗号化したい数をgとすると、
	g^d　(mod c)
Ubasic: print modpow(g,d,c)

復号アルゴリズム
暗号化された数をhとする。
	h^f　(mod c)

理論の詳細は、http://hp.vector.co.jp/authors/VA008160/cipher.htmを参照されたい。この文章はこのページを読んでコンピュータで実験した記録に過ぎないので、わからない部分はそちらで補ってください。非常にわかりやすく説明されています。

2. 暗号の実験
上記のアルゴリズムを用いて実際に2バイトの日本語文字を暗号化してみよう。例として「篠」を暗号化してみる。
この実験には、MupadおよびUbasicを用いた。（なお、上のアルゴリズムが理解しづらい人も、この実験をやりつつアルゴリズムを読むとよくわかるようになります。）

１バイトは8bitであるので、2バイト文字の上限の数値は、(2^8)^2=65536である。従って、求める素数の積は、65536よりも、大きくなくてはならない。

互いに素の素数をa=3251,b=3391とする。（適当に探した。）
検証
素数かどうかを Mupadで確かめると
 isprime(3251);を実行するとTrueが返ってくる。bも同様。
「互いに素」は、a != bであるので、明白。（aとbが互いに素でないとするとa=x*m,b=y*mでなければならず、a,bは、素数であるという仮定に反する。）
また、a*b=11024141であるので65536よりも大きい。

条件が満たされているので、簡単にオイラー関数を求めることができる
(3251-1)*(3391-1)=11017500

この数と互いに素な数、例えば78945643（適当に探した。）とすると、
秘密鍵を求めるには、オイラー関数を法としたときの78945643の逆元をもとめなければならない。
互いに素とは、最大公約数が1であることと同じなのでMupadで
 gcd(11017500,78945643);を実行すると1が返ってくる。
ubasicで計算すると、
print modinv(78945643,11017500)
2323507が返ってくる。これが秘密鍵である。

(なお、元の素数の3251,3391は秘密です。この数がわかると上記の方法によってオイラー関数を簡単に求められてしまい、そうなると秘密鍵が秘密ではなくなります。すなわちオイラー関数の計算の困難性にこの暗号は依存しているからです。)

「篠」のShiftJISでのコードは、36546である。これを、11024141と78945643で暗号化する。
36546^78945643 (mod 11024141)を計算する。
ubasicを用いて
print modpow(9018445,2323507,11024141)
9018445が返ってくる。
よって、「篠」の暗号化された数字は9018445である。

次に復号する。
秘密鍵2323507を使う。
計算自体は、9018445^2323507 (mod 11024141)だけである。
ubasicを用いて
print modpow(9018445,2323507,11024141)
36546を得る。

次に認証を実験してみよう。
（認証がわからない人は、http://hp.vector.co.jp/authors/VA008160/cipher.htm から探してください。)
　秘密鍵で「篠」を暗号化してみよう。
print modpow(36546,2323507,11024141)
413118を得る
これを公開鍵で復号する。
print modpow(413118,78945643,11024141)
36546が得られ、認証は成功した。

3. あとがき

一文字だけを暗号化したのは説明のためで、実際に使うときは何文字かまとめたほうがよい。
数字の桁数はもっと大きくなくてはならない。Mupadで上記の例の因数分解を試みると一瞬で返ってくる。
ifactor(11024141);
float(time(ifactor(11024141))/1000);
は、0.0秒であり、全く秘密を守れていない。

意外な難しさは、素数を探すことにもある。適当に数字を打ち込むだけではなかなか素数にならない。付録にMupadでの所望の桁の素数を探すプログラム(prime(n),primeproduct(n))を用意した。

桁数がどれくらい素因数分解の実行時間に影響を与えるか実験した。
付録のプログラムを用いて、45桁の合成数の素因数分解をしてみると
primeproduct(45);
ifactor(%);
Cerelon 366MHzのマシンでかなりの時間（10分）でも、答えが出なかった。40桁だと、１０秒前後だ。しかし、その合成数によって時間は結構違うみたいだ。


4. 付録


Mupadでのprime(n) （ｎ桁の素数を返す関数）

prime:=proc(n)
local b;
local a;
begin
  a:=random(0..10^n);
  b:=a();
if isprime(b) then
 return(b);
else
  prime (n);
end_if;
end_proc;

次に示すのは、任意の桁数の素数の積を返す関数である。prime(n)を必要とする。
primeproduct:=proc(n)
local a,b,c,l,m;
begin
   if ((n mod 2) = 0) then
   l:=n/2;
   m:=n/2;
  else
  l:=(n div 2)+1;
  m:=(n div 2);
   end_if;
  a:=prime(l);
  b:=prime(m);
  c:=a()*b();
  return (c);
end_proc;


5. この文章の更新予定
htmlファイルにする。