ネットワークをシンプルに考える。

宇宙、芸術、情報技術、哲学など。

RSA:公開鍵で復号できない理由、簡単なまとめ。

どうしてRSAの公開鍵で復号ができないのだろうか。

厳密にはオイラー関数などの理解が必要だが、ここではその構造理解は置いて、シンプルに納得してもらうためのわかりやすい解説を考えてみた。

 

1.登場人物と前提

<登場人物>

・大統領A:受信者

・役人B:送信者

・スパイC:解読者

 

<前提>

・公開鍵は二つの数で構成:E,N(全員に公開)

秘密鍵も二つの数で構成:D,N(大統領Aのみ※受信者のみ)

・原文情報(数a)は非公開

・暗号化の方法、復号化のアルゴリズムは世間に公開。

f:id:hirotsugu-furukawa:20170729192243p:plain

2.スパイCは公開された情報と暗号からなぜ復号できないのか?

スパイは数aから公開鍵(E, N)で暗号化された暗号をどうして復号できないのか。

ここには実は簡単なポイントがある

-----

①暗号化は割り算を用いること

②数a(平文)を割った余りを暗号として送信すること

③送信者(役人B)は商は誰にも教えないままにしていること

-----

暗号化(暗号文の作り方)は以下の式で行われる。

b = a^E mod N

※このbのみを暗号として送るわけだ。

 

余りだけを送るので、たとえここでEやNが公開されていたとしても、

商がわからない限り、数aはわからない。(当然特定ができない。)

(例)x÷5=yあまり1のとき、xがわかるだろうか。

   このとき、yが特定されない限り、xは判別不可能だ。

 

え?それならどうして受信者は復号できるの?という疑問が出てくるだろう。

それは綿密に作成された秘密鍵があるからに他ならない。

RSAの凄みは実は”秘匿性”よりも、この復号方法にある。

 

公開鍵と秘密鍵の関係を細かく見なければその点は理解できない。

(大学で数学専攻していればわかる範囲)

 

いずれにしても、取り急ぎ公開鍵では復号できないことはご理解いただけただろう。