象が転んだ

たかがブロク、されどブロク

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

2018年07月29日 14時14分46秒 | 数学のお話

 「リーマン予想の探求」(黒川信重 著)の中に、素数と暗号について述べられてますが。とても難解な内容ですが、出来るだけ砕いて説明する事にします。
 素因数分解は私達の生活において、安全性を保つ為に色んな場面で使われ、クレジットカードやスイカなどのパスワードの暗号化には欠かせません。
 この素数の概念は、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⁻¹が、”同型写像”(全単射)である事が、暗号解読の鍵となる事に注意です。
 しかし、上で使った様な単純な関数だと簡単に解読され、暗号の安全性を保つにはある工夫が必要です。

 そこでまず、大きな”素数”を使う。
 暗号を受け取る側は、”公開鍵”sNを受け取り、予め、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アルゴリズムが、大きな鍵となってる。
 という事で、何度聞いても、よく判らない暗号のお話でした。



4 コメント

コメント日が  古い順  |   新しい順
RSA暗号の複雑さと難解さ (paulkuroneko)
2018-08-04 14:02:48
続けてコメントです。

インパール作戦の事を思い出したら興奮してきました。

少しサイトで調べたんですが。中々上手く説明してる者には見当たりません。一応私なりにざっとではありますが、纏めてみました。

n=pq(互いに素)は共通ですが。事前に公開する共通鍵eとnは、e=65537=2^16+1が主に使われるみたいです。平文をe乗し、modnで暗号文にするんですが。
秘密鍵dは、de=1mod(p-1)(q-1)で計算されるので、秘密裏に保管します。

ここで、復号化は暗号文をd乗し、modnで元に戻すんです。故に、pとqは絶対に漏らしてはなりません。

秘密鍵dの生成ですが。φ(n)=(p-1)(q-1)とすると、上で述べたように、de=1modφ(n)となります。φ(n)はオイラーのφ関数です(nより小さい整数の内で、nと互いに素な数の個数)。故に拡張されたユーグリッドの互助法(一次方程式の解法:整数m,nの最大公約数をgcd(m,n)とするとmx+ny=gcd(m,n)なる整数解(x,y)を得られる)を使えばdが得られるのですが。

例えば、deをφ(n)で割った余りをx(整数商)とした時、de-xφ(n)=1が成立し、gcd(e,φ(n))=1なるeがとれるので、拡張された一次方程式の解法から、dとxが求まるのです。

サイトで潜った程度なので、確信は持てませんが。後は転んださんにバトンタッチです。
返信する
Re:RSA暗号の複雑さと難解さ (lemonwater2017)
2018-08-05 15:33:32
続けてコメント返しです。
全く流石ですね。

 私も一応調べたんですが。オイラーの∮関数と拡張されたユーグリッドの互助法で頓挫しました。でも、paulさんが簡潔に判りやすく説明されてたんで、何とか理解できました。このシンプルに判り易くというのが出来ないんですよね。
 
 というのも、同型写像の見地で暗号解読を説明したんですが。やはり難解すぎて、RSA暗号表を使って暗号解読を説明する方がずっと判りやすく、暗号ブログを更新しようかと思ってた矢先だったので、非常に助かります。

 RSA暗号というのは、mod演算と素数の素因数分解の困難さを利用した比較的シンプルなアルゴリズムなんですね。だから200桁ほどの大きな素数が必要なわけですね。

 暗号解読のブログを近々更新するつもりですが、paulさんのコメントを利用させて頂きます。毎回毎回ホントに助かります。
返信する
意外とシンプル (tomas)
2018-08-10 05:08:06
おはようございます。
RSA暗号というのは噂には聞いてたんですが。
素因数分解がカギとなってるんですね。
平文を公開カギ乗しNの余りをとって暗号化し、復元する時は暗号文を秘密カギ乗しNの余りをとるんですか。

転んださん言う通り、暗号のアルゴリズムとしては意外にシンプルです。ただ桁数を非常に大きくして計算をややこしくしてる。色々と勉強になります。
返信する
Re:意外とシンプル (lemonwater2017)
2018-08-10 19:37:03
こんばんわです。

暗号ブログに興味を持って下さって有難うです。ホント、意外に単純ですね。また、単純なものほど難解なものはない訳で、人生と同じですね。中々当たり前の事が出来ない。

リーマンブログの方も宜しくお願いします。
返信する

コメントを投稿