2012年1月3日

ぽよ @Poyo_FさんのＲＳＡ暗号と素数の話の続き

ＲＳＡ暗号と素数の話の続きですが、何故、２つの鍵を作るのに素因数分解が必要なのか。モジュロという世界 #変な箱の原理

数学素数モジュロ RSA暗号

ＲＳＡ暗号と素数の話の続きですが、何故、２つの鍵を作るのに素因数分解が必要なのかということが知りたくなりますよね。やはり。そのためにはモジュロという世界の言葉を操る必要があります。というわけで、次の数ツィで、 #変な箱の原理的な部分を書いてみます。この時期でないと時間無いし。。

2012-01-02 23:14:36

モジュロ４は、「数を４で割った余りで分類しているよ」という合図。例えば、数君たちを、４で割った余りでクラス分けして、クラスの代表生徒の名で、クラスを呼称することにする。例えば余りが１になる数｛１、５、．．｝のクラスは、１君に代表をお願いして「１（君）のクラス」と呼ぶ。 #変な箱

2012-01-02 23:18:16

モジュロの概念が便利なのは、計算は皆、代表君の数の計算だけでクラスの数どうしの計算の性質を確認できる点だ。例えば、１のクラスの数である５を１０回掛け合わせた数５^10＝９７６５６２５も（１^10＝１だから）１のクラスの数になることはすぐに分かる。 #変な箱

2012-01-02 23:19:00

例えばルービックキューブ上面の９０度時計回転操作を「ｔを掛ける」と表現すると、ｔを４回掛けると元に戻るので、「ｔ×ｔ×ｔ×ｔ×」という操作は「１×」という操作と等しい。このことをt^4＝1と書く。例えば、d＝t^3ということにしたら、e=tであれば、ed=1になる。 #変な箱

2012-01-02 23:21:00

モジュロ４の世界とは、このルービックキューブ上面の９０度回転操作回数の計算と対応している。例えば３回の「ｔ×」（＝ｔ^3×）の後、１回「ｔ×」をやると、元の配置に戻る。つまり０回「ｔ×」をやったのと同じ。これを「モジュロ４で３＋１＝０」と書く。これはｔの指数の計算だ。 #変な箱

2012-01-02 23:24:19

普通は足し算をすると数は大きくなるが、モジュロの世界では小さくなることもある。３回回したキューブを元に戻すには３回逆に回せばよい（３－３＝０）が、１回だけ更に回す事（３＋１＝０）でも戻せる。暗号とは、３回の操作を暗号化★に使い、１回の操作を復号化●に使うということだ。 #変な箱

2012-01-02 23:26:05

実際には大きな２つの素数ＰとＱについて、★型鍵の数eと●型鍵の数dについて、モジュロ（Ｐ－１）×（Ｑ－１）でed＝1になるようにする。メッセージＭを暗号化する時は、Ｍをe乗しC=M^eとすればよい。元のメッセージに戻す時はCをd乗する。これをモジュロＰＱでやるのだ。 #変な箱

2012-01-02 23:29:36

Ｃ＝Ｍ^eで暗文を得て、Ｃ^d＝Ｍ^ed＝Ｍ^1＝Ｍとやって復号する。この暗号化と復号化の計算をモジュロＮでやる（但しＮ＝Ｐ×Ｑ）。指数のed=1のところは、モジュロ（Ｐ－１）×（Ｑ－１）での計算になる。これらの性質は、フェルマーの小定理とかオイラーの定理から導ける。 #変な箱

2012-01-02 23:30:21

ところがdの値を大事にしまっておいて、Ｎ＝Ｐ×Ｑの計算結果Ｎとeの値しか教えないので、ＮからＰとＱの値を求められないとdが何なのか分からず、dを知らない人には（Ｃ^dによって）復号できないのだ。（逆に言えばＮの値の素因数分解によってＰとＱがバレたら解読されてしまう。） #変な箱

2012-01-02 23:31:03

フェルマーの定理やオイラーの定理については、またいつか。 #変な箱。。。それにしても、つい数式に頼ってしまうなぁ。やはり数式無しで説明できなければ、マダマダだな。

2012-01-02 23:34:23