暗号のしくみと素因数分解〜何度聞いても､よく判らない数学のお話

　｢リーマン予想の探求｣(黒川信重 著)の中に､素数と暗号について述べられてますが。とても難解な内容ですが､出来るだけ砕いて説明する事にします。
　素因数分解は私達の生活において､安全性を保つ為に色んな場面で使われ､クレジットカードやスイカなどのパスワードの暗号化には欠かせません。
　この素数の概念は､2500年も前のギリシャの時代に発見され､現代社会において実用化されました。

簡単なケースとRSAアルゴリズム

　まずは､簡単な説明(イラスト参照)からです。
　Aさん(送り手)がBさん(受け手)に､”abc”という文章を”bcd”という暗号にして送るとします。一文字ずつズラしただけの超簡単な暗号化です。
　Aさんは､”公開鍵(共通鍵)”を使い､ロック(暗号化)するのですが。Bさんは､送られた暗号(金庫)を､Aさんが送る”秘密の鍵”を使い､ロックを外し(金庫を開け)､”bcd”から元の”abc”を得る事が出来ます。
　勿論､この”秘密鍵”は､盗まれたら一巻の終わり。それに､盗まれなくとも､この秘密鍵が簡単過ぎると､暗号の意味はなくなります。

　そこで､素因数分解を使った”秘密の鍵”の登場です。超簡単な例ですが､Aさんは､事前にBさんへ共通鍵”6”を送ります。次に､”6”を素因数分解して得られた秘密鍵(複合鍵)､”2”と”3”を送ります。勿論､同時に送ってはアウトです。
　Aさんは､この共通鍵を使って､元の文章に鍵(暗号化)をかけますが､暗号化タイプをアルゴリズムを使い､非常に複雑な”ものにします。
　解除に必要なのは､秘密鍵”2”と”3”という2つの鍵。しかし､6という数字から､2と3を解読するのは､誰でも出来ます。そこで､秘密鍵の素数の桁数を100程にする。つまり､複合鍵を超複雑にします。
　この2×3=6という素数の積と､1をその積で割った余りを使ったアルゴリズムをRSA暗号と呼びます。

　スパコンを駆使しても､100桁の素数の素因数分解には10万年以上かかります。故に､共通鍵が漏れても全く心配ない。逆に100桁の複合鍵(複合鍵)が漏れてしまったとしても､絶対に複合出来ない。
　つまり､素数というより素因数分解の困難さに暗号システムは守られてるんですね。

超複雑な暗号の仕組み

　さて､上の事を頭に入れ､少し本格的な暗号システムの具体的なお話をします。
　まず､A=[1､2､3､､､n]という単純なn桁のパスワードを例に取ります。そこでfという関数と､g=f⁻¹(fの逆関数)を用意します。
　例えば､f=x²という単純な関数にして､B=f(A)=[f(1)､f(2)､f(3)､､､f(n)]＝[1､2²､3²､､､n²]が暗号となる。
　そこで､暗号を受け取った人は､fの逆関数g=f⁻¹を解読し､g(B)=[g(1)､g(2²)､g(3²)､､､g(n²)]を作りさえすれば､g=f⁻¹=√xよりg(n²)=nとなり､元のパスワードのg(B)=A=[1､2､3､､､n]を得る。
　fの逆関数g=f⁻¹が､”同型写像”(全単射)である事が､暗号解読の鍵となる事に注意です。

　しかし､上で使った様な単純な関数だと簡単に解読され､暗号の安全性を保つにはある工夫が必要です。

　そこでまず､大きな”素数”を使う。
　暗号を受け取る側は､”公開鍵”sとNを受け取り､予め､A=[1､2､3､､､n]の各要素をs乗し､Nで割った余りを計算しときます。
　N=pqとし､pとqは互いに異なる素数ですが､実際には200桁ほどの素数にする。故にNは普通400桁ほどの大きな自然数を使う。
　大半のサイトでは､このpとqの素数の積が暗号解読の2つの鍵となってると紹介してますが､実際にはややこしくなります。

mods演算と暗号システム

　秘密鍵rと公開鍵sを､”mod”(余りを答えとする演算)を使い､rs=1mod(p−1)(q−1)という､”ややこしい数式”を作ります。
　ここでrsは､1を(p−1)と(q−1)の積で割った余りになり､言い換えれば､rsに1を足せば､(p−1)(q−1)で割り切れる。つまり､rs+1は､(p−1)(q−1)の倍数になる。
　　因みに､秘密鍵rは､”オイラーのφ関数”と”ユーグリッドの互助法”(拡張された一次方程式の解法)を使い､割り出します。
　φ(N)=(p−1)(q−1)とすると､rsをφ(N)で割った余りをx(整数商)とした時､rs−xφ(N)=1が成立し､gcd(s,φ(N))=1なるsがとれるので､”拡張された一次方程式の解法”より､秘密鍵rが求まる(ウィキ)。但し､gcdは最大公約数。
　これは､どんな数も､p−1とq−1の最小公倍数の倍数に1を足した数(秘密鍵)の分だけ､掛け合わせれば､元の数に戻るという法則を利用してます。

　そこで､暗号を受け取る人は､自然数Nと共通鍵sのみを公開。p､qと秘密鍵rは絶対に公開してはいけない。
　前述した様に､暗号を送りたい人は､A=[1､2､3､､､n]というパスワードを元に､B=As'=[1s'､2s'､3s'､､､ns']という暗号列を作ります。
　但し､B=As'は､Aの各要素をs乗したAs=[1ˢ､2ˢ､3ˢ､､､nˢ]の各要素を､Nで割った余り(ns'=nˢ mod(N))とすると､上述した様に､B=f(A)からf(n)=nˢ mod(N)になります。
　Asがs乗写像fになってる事に注意です。

　この時送り手は､暗号列B=As'=[1s'､2s'､3s'､､､ns']を受取人に送ります。これで暗号送信は終了。暗号作成もコンピュータを使えば､nˢ mod(N)の簡単な演算作業です。
　次に今度は､受取人が､Br'=As'r'=[1s'r'､2s'r'､3s'r'､､､ns'r']を作れば､A=[1､2､3､､､n]に戻るのです。
　Br'は､暗号列B=As'の各要素を､”ややこしい数式”rs=1mod(p−1)(q−1)を使い､fの逆写像gより､A=G(B)g(n)=ns'^r mod(N)となります。
　割り出した秘密鍵でr乗した､Br=[1s'^r､2s'^r､3s'^r､､､ns'^r]の各要素Brは､r乗写像gという”fの逆写像g”になってる事に注意です。

最後に

　上述した様に､fの逆写像gよりA=G(B)となり､g(n)=ns'^r mod(N)となってます。
　元のパスワードA=[1､2､3､､､n]に､すんなり戻るのは､s乗写像fとr乗写像g(fの逆写像)を使ってるからで。つまり､fは同型写像(全単射)で､ある暗号に置き換えても(置換)､逆写像で元に戻る。

　このs乗写像fとr乗写像gの関係が非常に解り辛いですが､累乗とmod演算(余り)のアルゴリズムだけでも理解すれば､良しとしますか。
　今回は､数の列を使って説明しましたが。具体的にpとqの値を決めて説明した方が､ずっとわかり易いですね。
　｢暗号の仕組み”その2”｣(Click)では､RSA暗号システムを簡単な例を上げて説明してます。宜しかったらどうぞです。

　Nとsを公開しても安全な訳は､たとえNが200桁ほどの2つの素数の積である事を知ってたとしても､N=pqなるpとqを求めるには､現在の技術では数千年程度の時間が掛かる。
　つまり､大きな桁の自然数を素因数分解する事が困難である事と､同型写像やmod演算を使った”ややこしい”RSAアルゴリズムが､大きな鍵となってる。
　という事で､何度聞いても､よく判らない暗号のお話でした。