暗号理論第4回―公開鍵暗号の主流方式RSA暗号の数論的解説

現在の主流な暗号方式である公開鍵暗号のアルゴリズムの図式化したもの。

https://www.ipa.go.jp/security/pki/022.htmlより引用

公開鍵暗号は複雑な経緯があるが、話をはしょってしまえば簡単だ。要するに共通の鍵ではなく、二つの鍵を使い、また公開鍵方式だから一方の鍵を公開してしまうものだ。このとき、アリス(A)とボブ(B)の間の介入者は暗号文を公開鍵では複合できないのである。この経緯で離散対数が使われているので、その応用事例を簡潔に言っていこう。参考書は「暗号技術入門」結城とする。

公開鍵暗号には有限体(ガウス体)を使う、楕円曲線暗号なども含まれたり、ElGamal暗号などの整数的位数の応用なども考えられるが、現在主流なのはRSA暗号である。これは発明者の頭文字を三つとって命名されたもので、それ以外のスペル文字列の短縮ではない。RSA暗号のアルゴリズムは、素数の組み合わせが天文学的に多い性質を利用しているので、素数の組み合わせの枯渇や、誰かの素数の組み合いがほかの誰かのものと一致したりすることは考えなくてよい(限りなく等価である)。ただ、この素数性質の証明をブレイクできれば問題はまた変わる。

暗号文=平文^E modN(暗号化)・・・(1)
平文=暗号文^D modN (復号化)・・・(2)

二種のやり方があって、このときに「EとNの組が公開鍵」結城p132なのだそうだ。ちょっと離散対数を復習しておこう。次は結城p131およびp152よりの例題である。合同式とごっちゃになりがちだが、modにはきちんとした意味があるので覚えておこう。

7^16 mod12 この値を考えよ。

左の7^16をこれは12で割ったときの余りを指すものだからその通りに計算すればよい。RSA暗号は数論の基礎に支えられているのである。ここからすでに勉強した「ユークリッド互除法」や「中国人の剰余定理」を使えば発展的に解釈できる。答えは…

7^16 mod12=1である。

追って説明しよう。RSA暗号は素数の合成が複雑なことを利用している巧妙な暗号である。p,q素数の時、Nをp*qとする。このとき、EとNが公開鍵かつDとNがプライベート鍵になる(プライベート鍵は受信者の複号のために使われる)。NはいいとしてもE・Dがわからんと思ったあなたは頭が良い。さらにLまで関係してくる、このLは鍵生成のときに仲介してくれる数である。(L=lcm(p-1,q-1)という最小公倍数を持ち出した定義)

1<E<Lおよび1<D<Lを満たすようなふたつのE・Dを求めればいいのだが、ここでさらに…最大公約数gcdの関係を持ち出して併用することによってgcd(E,L)=1かつE*D modL=1となるようなEDを探すのである。この双方は実はユークリッド互除法によって簡単に求まることがわかるので、結城p137より自分で具体的に鍵ペアの生成法をみていこうか。

p=17,q=19(互いに素数)のときに、N=p*qだからN=323
L=lcm(17-1,19-1)=lcm(16,18)=144であるから、gcd(E,144)=1の条件により...
E=5とできる。

また、さらに、5*D mod144=1となるようなDを考えると…
単純に離散対数の性質を考えていってD=(144+1)/5の答えより…
D=29となる。

これで必要な数がすべてそろったといえる。(E,N)=(5,323)・・・暗号鍵 (L,N)=(29,323)・・・プライベート鍵となる。 これを暗号文(1)と複号文(2)に代入して…まあ平文の仮定が必要なので、結城p140にならって、平文=123とするときに…

暗号文=123^5 mod323(暗号化)より暗号文=225

(2)に代入して…

平文=225^29 mod323 (復号化)より平文=123

となる。ここでは計算にWIndows付属の関数電卓を使った。この関数電卓にもmodの除算機能がついているので、簡潔に答えは求まるだろう。これで暗号化と復号化が可能になった。簡単な素数関係上で具体的な暗号理論を検証することの理解を求めるものである。次回はこの暗号の弱点とかを合わせてもっと発展的な暗号および暗号とは別な概念である認証技術を学ぶ。

(なお、例題は「暗号技術入門」結城p140にならった)

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA