null

Museum H1：【ちょっと得する知識シリーズ(1)】『素因数分解を知れば暗号が分かる』
数学が嫌いな人も原理が分かれば、面白くなります。また数学に造詣のある人は、今後ひょっとしたら画期的な理論を考案してITの世界に革新をもたらすかもしれません。例えば、スパース
モデリングはCTスキャンや宇宙観測の領域に革命をもたらしました。暗号も言わば関数 y=f(x)と捉えることができます。あるデータ x(数値や文字)を入れると関数f(x)によって意味不明の
値yに変換され、それを見ても真の意味は理解されませんが、別の関数 x=g(y) で伝えたい情報データxが復元されるというという仕組みです。
【暗号クイズ】
下記のような規則がある時に
2581の値を求めよ。
8809=6
7111=0
2172=0
6666=4
1111=0
3213=0
7662=2
9313=1
0000=4
2222=0
3333=0
5555=0
8193=3
8096=5
1012=1
7777=0
9999=4
7756=1
6855=3
9881=5
5531=0
2581=???
【正解】
2581の値は 2 となります
何故2になるのかを考えてくだ
さい
【素因数分解と暗号の関係】
前回に続いて暗号を特集してみたいと思います。私も公開鍵と秘密鍵の関係が中々分からなかったのでその点を重点的に書きたいと思います。私の場合、「公開鍵で暗号化されたものがどうして秘密鍵で再
現できるのか?」というカラクリがj全く理解できませんでした。Webを見ても、身近な文献を読んでも概念的で具体的に書いてなかったからです。
左記に非常に単純な暗号クイズがあります。頭のリフレッシュの意味でみなさんもチャレンジしてみてください。問題を見た時に条件式の値が0から6までに着目した人は理科系の人かもしれません。
私も最初はこれは7で割った余りなのかなと直感しましたが、全く違っていました。最終的には4桁が同じ「0000」「6666」「9999」は4なのに対して「1111」「2222」「3333」「5555」「7777」はゼロというこ
とからやっと解けました。特に前者の3つの数値に共通するものを考えると簡単かもしれません。私の場合、それでも10分以上かかったので我ながら頭が固いなあと思い知らされました。事ほど左様に暗号に潜
むアルゴリズムを解析するのは難しいのです。この問題はコンピューターを使っても解けないかもしれません。(視覚的解法といったところでしょうか)
みなさんは素数を小学校の時に習いましたよね。素数の定義は1とその数自身でしか割れない自然数(正の整数)です。従って2という数字の例外を除くと奇数しか素数にはなりえません。1は素数に加えませ
んので小さい順に「2、3、5、7、11、13、17、19、23、・・・」といった感じになります。 RSA暗号ではこの素数の持つある特性を利用しています。下図右にあるように素数と素数の掛け算は電卓を叩けば直
ぐ答えが出ますが、ある数を素数に分解するのは困難(桁数が多いと実質不可能)という特性があります。2つの素数をP、Qとしたときに A = P x Q の式を素因数分解と言います。
たとえばA=34,579を素因数分解しようとすると人力ではとても解く気になりません。凄く原始的ですが、Aを3割ってみたり、7で割ってみたりと順番に素数で割っていき確かめるしかないのです。
因みに 34,579 = 151 x 229 です。5桁の数値Aでこれくらいですから10の160乗規模の数値になると人力はおろかコンピューターと言えど、解くのに何か月あるいは何年かかるか分かりません。現代の進
化した数学の理論をもってしても素因数分解を効率的に解析するアルゴリズムはまだ発見されていないのです。ちょうど半導体のように片方向には電流を通すけど、反対向きには電流を通さないというのと似て
います。ではこんな面倒くさい素因数分解を何に使うのという疑問が湧きますよね。そう、この素因数分解は暗号化における公開鍵に活用されるのです。それは2つの理由からです。
【理由1】
桁数の多い整数Aから素因数分解で素数PQを求めるのは極めて困難である。
この性質は暗号の世界では極めて有用なのです。
仮に数年後に解読された時には情報の価値がなくなっているのです。
【理由2】
公開鍵
秘密鍵
素数の積が持つ面白い特性が活用できるのです。 (詳細は後述)
理由2を理解する上で最低限知っておいた方が良い決まりがあります。
平
文
暗
号
化
復
号
化
平
文
暗号送受信では送りたいメッセー
ジ(平文)を何らかの加工をして
全く意味不明の数値(暗号化)
にして送信し、受信者はあるロ
ジックで元の平文に返還(復合
化)して判読する
数学でいう法(ほう)について簡単にご説明しますので頭に入れておいてください。
決して難しい内容ではありませんので。
一言でいうと全ての数を「割り算の余り」だけで表すという約束事です。
ある整数Xを整数Yで割った余りをZ(整数)とします。当然余りZはゼロから
Y-１までの整数となります。この時に余りZを作り出すことをY(割る数)を法とする
世界と言います。法の表現方法と定義は数学の世界の決め事なのでそのように
覚えてください。
【法の例】
15を法とした時の21の値は21÷15=1・・・余り6 ですから 6を指します。
15で割った余りで表すので、全ての値はゼロから14までになりますよね。
10の
80乗規模
の任意の
素数P
整数
A=PxQ
10の
160乗
規模の値
10の
80乗規模
の任意の
素数Q
Aを求めるのは
簡単
10の
80乗規模
での任意
の素数P
10の
80乗規模
の任意の
素数Q
天文学的素数マトリックス
素数
P1
P2
・・
∞
Q1
A11
A12
A1m
Q2
A21
A22
A2m
An1
An2
Anm
・
∞
PとQを求める
のは困難
絞り込みなしで順次に演算をしていく場合、演算回数のべき数
を推定すると最大10の80乗程度必要になる
一方CPUの1秒当たりの演算処理回数を10の10乗と仮定す
ると必要な演算時間は10の70乗程度(秒)となる
注. Loop処理やディスクへの書き込み時間は無視
上記のような天文学的な素数のマトリックス
があれば値Aを検索して割り出すことができる
のでしょうが、検索自体も恐ろしく時間がかか
ることでしょう
Museum H2
【暗号の複号化を検証】
では具体的に公開鍵と秘密鍵の関係を例を基に見てみましょう。
ここでは紙面の関係で便宜的に素数3と素数5の積である15という極めて小さい数値を法とする世界で検証します。
法Y=P x Q =15=3 x 5 (実際の運用では法は10の160乗程度の数値のようです)
法を15とした場合、全ての自然数は下表左の通り0から14の値しかとり得ません。
下表左で値2の行(青点線の行)を例にとると、2を1乗した2を15で割った余りは2、2乗した4を15で割った余りは4、3乗した8を15で割った余りは8、4乗した16を15で割った余りは1となることを示した表になります。
右に行くにしたがってべき乗数が増えることを表しています。ここでは紙面の関係で10乗までしか書いておりません。また縦方向には、例えば47の3乗の103,823を15で割ると余りは8になるので8行目に相当します。
さてここで下表の配列で何か面白い特性に気づきませんか? そうです、縦の列で周期的に元の数値に戻っていますよね。たとえば5列目(5乗した値の列)は上から順に0、1、2、3、4、・・・・14になり、また9列目でも
同様になっています。法の世界では (p-1)と(q-1)の最小公倍数に1を加えた数値をべき乗する毎に元の数値に戻るという大変素晴らしい特性があります。この原理さえ理解すればRSA暗号化は99%理解できたこ
とになります。『ほんまかいね?』という人のために下表右に検証用の例を用意しました。更に原理を極めたい人はオイラーの定理を調べると良いでしょう。
仮に平文の数値を「2」、「5」、「9」、「13」としましょう。ここで受信者は法を15にして、平文を3乗 (公開鍵)した暗号文で送るように依頼します。送信者は言われた通り元の数値を3乗し法15で割った余りの
「8」、「5」、「9」、「7」を送信します。受信者は元に戻る周期が4n+1が分かっていますから、ここでは簡単なn=1を入れた「5」として自分の秘密鍵を5-3(公開鍵)+1=3として「8」、「5」、「9」、「7」をそれぞれ3乗して
15で割った余りを求めます。すると、どうでしょう。それぞれが元の「2」「5」「9」「13」にもどるではありませんか。これがRSA暗号の暗号化と復号化における公開鍵と秘密鍵の原理なのです。

Download Report