解読不可能暗号と公開鍵暗号

昨日の続き。公開暗号鍵調べてたらふと思いついたので。

公開鍵暗号すごいな。よくこんなもん思いついたな、てかよくこんな関数瞬時に思いつくな。
というかそんな関数を知っていたから暗号に使えることに気づいたんだろうけど。
以下公開鍵暗号概要。

  1. Sender,Recieverが共に秘密鍵を非公開にしたまま、公開鍵を全世界に向けて公開する。
    • 公開鍵とは暗号鍵であり、秘密鍵とは複合鍵である
    • 平文の暗号化には暗号鍵を、暗号分の平文化には復号鍵を用いる
    • 公開されている暗号鍵だけを用いて暗号の復号化は困難（因数分解の困難性により）
  2. SenderはRecieverの公開鍵を取得、それを用いて送信したい平文を暗号化。
  3. 送信。
  4. 送られた暗号文はRecieverの公開鍵によって暗号化されているわけだから、自身の秘密鍵を用いて復元。

なんとわかりやすい。

例の記事の解読不可能性の証明を簡単にできるような気がしたけど気のせいだった。
とりあえずRSA暗号を利用してみようと思ったのだが。

  • \color{white}{n=pq,\quad\quad p,q\in {\rm prime number}}
  • 平文mから暗号文cを作成する：\color{white}{c = m^e({\rm mod}\quad n)}
  • 暗号文cから元の平文mを得る：\color{white}{m = c^{1 / e~~({\rm mod}~(p - 1)(q - 1))}({\rm mod}\quad pq)}

暗号化にはeとnがあれば十分であるが、複合化にはpとqが必要である。そのため公開鍵としてeとnを、秘密鍵をp,qとすれば、RSA暗号の出来上がり。
もちろん、nを因数分解できればp,qが手に入るので、暗号は破られるということになる。


此処に陽関数\color{white}{f:{\mathbb R}\to{\mathbb R}}でも加えればとりあえず暗号解読不可能性は示せそうな気はしたんだが、公開鍵として関数fは晒せない。どうするんだろう。


CADはRSAを含むといっているのだから、おそらくこんな感じだな。

  • \color{white}{n=f(x),\quad\quad f:{\mathbb Z}\to{\mathbb Z},\quad x\in {\mathbb Z}}
  • 平文mから暗号文cを作成する：\color{white}{c = m^e({\rm mod}\quad n)}
  • 暗号文cから元の平文mを得る：\color{white}{m = c^{1 / e...}???

公開鍵e,n、暗号鍵f,xてところか。これで下の式がc,e,n,f,xを用いて求まるなら数学的には証明されたことになるんじゃね。関数fは無限の元を持つ関数集合からとってこれるからな。
nからfとx推測するのはほぼ不可能だろ。これならRSAよりは数段強そうだ。