Q&A
電子計算機で解けないことが証明された暗号があるんですか？
非常に眉唾な話だと思いますが、その暗号の情報はどこで公開されていますか？
実装中の暗号方式のリンク
リンク先からの引用です。
「The security level of the McEliece system has remained remarkably stable, despite dozens of attack papers over 40 years. The original McEliece parameters were designed for only 264 security, but the system easily scales up to "overkill" parameters that provide ample security margin against advances in computer technology, including quantum computers.」
いまこの暗号を実装しています。公開鍵暗号の一つですがとてもマイナーです。
teratail内で暗号を検索すると結構出てきます。
Q1.需要として暗号技術というものは、どういうときに必要とされるのでしょうか？
Q2.公開鍵暗号のニーズについて知りたいです。
よろしくお願いします。
追記：
暗号方式は私が発明したものではありませんが、量子計算機でも解けないと言われています。
ここにあります。
これはまたあんまりな展開。
まさかのどんでん返しとは…
すみません。書く必要のある情報の優先順位がわかりませんでした。
＞質問者Goldwasserさん
（更なる質問への追記を読んで）質問当初の主旨は「公開鍵暗号のニーズについて知りたい」だったと思います。ひととおり回答をいただいた後に別テーマとなる新たな質問を追加するのは（言葉はきついかもしれませんが）反則です。一度BAが付いた回答者さんにも失礼だと思います。ここはteratailの既存の質問回答を探して閲覧するか、新たな質問を立てるのが正当かと思われます。（以降、私からはコメントを控えます）
https://en.wikipedia.org/wiki/McEliece_cryptosystem#Information_set_decoding
Information_set_decoding を読んでみてください。量子計算機で決して解けないし、40 年間解けなかったと書いてありますか？
発案された当時のパラメータの暗号は解読されているということですね。当時の秘密鍵は56ビットだったので、鍵の総探索でも解けるかもしれないです。ISD(infomation set deboding)の存在は知っていましたが、私は現在推奨中のパラメータの方法を考えていました。でも電子計算機でも解けるのですね。ありがとうこざいます。
https://classic.mceliece.org/
私はこのサイトで言われていることを信じました。
公開鍵暗号というのは「因数分解には時間がかかる」という「現在の」状況において、解読までに一定以上の時間がかかることを目的とした暗号です。
現在のどの公開鍵暗号も「解けないことを目的としている」のではなく、「現実的な費用では解くのに時間がかかることを目的としている」ことに注意してください。
したがって理論的には、無限の時間あるいは無限の計算リソースがあれば解読できてしまいます。そうでなくとも、因数分解を解く画期的なアルゴリズムが発見されれば、現実的な時間とお金で解読できてしまいます。
このような脆弱性があるため、現在のアルゴリズムに寄らない新アルゴリズムが求められています。
残念ながら、提示された暗号アルゴリズムはこの問題を解決しません。したがって、現在使われている暗号システムを塗り替えるほどのメリットはありません。ましてやアルゴリズムがいかに優れていようと、素人が実装したものなどどこにどんな脆弱性が含まれているかわからないので、使用しようと思う人はほとんどいないでしょう。
「残念ながら、提示された暗号アルゴリズムはこの問題を解決しません。」
そんなことないですよ？私の言葉が誤解を与えた部分ではありますが、McEliece暗号はアメリカで進んでいるRSAの次世代暗号の候補に残っています。詳しくはpost quantum cryptography で検索していただければ、今どの暗号アルゴリズムが量子計算に対しても安全な方式なのかが解ると思います。そしてその中の一つが私の提示した暗号なのです。ちなみに因数分解問題はShorのアリゴリズムという方法を使って量子計算機で解けると噂されています。この事実を持って次世代暗号の選定が進んでいるものと思われます。Shorのアルゴリズムについてはこちらのサイトをご覧ください。
https://qiita.com/kyamaz/items/eebd0f7734c8a33de2ad
「使用しようと思う人はほとんどいないでしょう。」
とても残念ですがそれが現実でしょう。私はプロのレベルではないので2022年に次世代暗号の規格が決まったら、その時プロが実装することになるのだと思います。ただ私のコードは論文を読んで理解したことの集大成なので、誰かに使ってもらうというよりは自分の理解度を確認する程度の意味しかありません。
いいえ、解決しません。RSA の次世代暗号の候補というのは、量子コンピューターの出現に合わせてより長いキーを用いてより速く暗号化できるアルゴリズムです。因数分解を用いている以上、問題を先延ばしにしているすぎません。
私はMcEliece暗号のことを言っているのですが、この方式は素因数分解とは全く異なる問題に基づいています。一般線形符号の復号問題と言われている問題です。ですので、素因数分解を使っているとの認識は誤解だと思います。。
因数分解はアタックに使うアルゴリズムの一部であって、暗号化アルゴリズムではありません。
だんだん話が噛み合わなくなってきたようですｗ
因数分解問題はRSA暗号の安全性を保証する根拠となる問題です。つまり因数分解が解ければRSAはもう使えません。そしてその素因数分解は攻撃法であると同時に、量子計算機で実現できそうだと言われています。そこで次世代の暗号規格が決められようとしているのでしょう。
一方、McEliece暗号は誤り訂正符号のどの種類の符号を使ったのかわからなければ安全だという問題に基づいています。そしてどのような線形符号でも複合できる効率的なアルゴリズムは知られていない（NP-hardな問題と言われている）という事実によって安全性が保証されています。毎月いろんな解読法や改良案が何本も論文になって出てきているようなので、あくまで現時点で安全そうだというものです。
最初から噛み合っていないと思いますが、今初めてかみ合っていないと感じたのですか？
何を聞きたいのかもフラフラ迷走しているようですが、それには気づいていますか？
まあ使われることを期待していた私が間違っているのでしょうね。
自分だけで使う分には全く問題ないですけど、使ってもらうのは叶わぬ望みですね。
結局のところ、質問は何なのでしょうか。
「暗号化技術のニーズについて」
「公開するに当たって注意すべき点がありましたら教えてください。」
「需要として暗号技術というものは、どういうときに必要とされるのでしょうか？」
「公開鍵暗号のニーズについて知りたいです。」
「フリーソフトとして公開することでコードの信頼性が高まると思うのですが違いますか？」
質問の内容をわかりやすくしました。
回答8件
0
一応GitHubでソースを公開しているのですが、どういう公開の仕方が一番使われるでしょうか？
厳しいことを言うようですが、個人で作った程度の暗号化方式でしたら、期待しないのが正解です。
AESやRSAなど第一線で使われるような暗号化方式は、多くの暗号科学者の研究対象となって、徹底的に弱点を探し回られています。個人で作った暗号化プログラムが、それに比肩するような強度を持つことは、およそ考えられません。
投稿2020/03/03 14:26
総合スコア145183
なにかの暗号化方式を策定する会議の場で、ある専門家チームが提案した暗号が、その場で別なチームに脆弱性を指摘されてしまう、そんな事が起きるぐらいに、安全な暗号方式の策定はシビアで困難な仕事です。
> ここにあります。
そういう重要な条件を後出しするのはやめてください。回答の前提をひっくり返すような話です。
現在アメリカを中心に、RSA暗号にかわる次世代暗号の選定が進められています。その候補の一つが私の実装している暗号です。オリジナルではありませんし、コードにも自信がありません。なので少しでも頑張っていいコードを書けるようになりたいです。
0
質問者さんの追記を受けて、恐らく私のような一般的な素人が思うであろう意見を回答のひとつとして記しておこうと思います。
発表から40年間誰も解読に成功していないという暗号です。
初出が40年も前であれば、もしかしたら同時代以降に出た暗号化手法と比べて、単純に注目を浴びずに40年間過ごしてしまっただけ、と言うことも考えられます。他の暗号化手法と同等に評価されたとは限りません。PGPやGnuGPなど、有名な公開鍵暗号方式を使うソフトでは、注目を浴び、使われる機会が多かったが故、有識者や利用者に検証され、研ぎ澄まされてきたと言えると思います。それが、それらの暗号化手法の現時点の制限事項を含めた「信用」や「信頼性」だと思います。
量子計算機でも解けないと言われています。
「そう言ったのはどなたでしょうか。」と言う疑問が出るのが正直なところです。数年前までは不可能だと思われていたようなことが、少なくとも要素の部分では機械学習、いわゆるAIの分野でも日々発明、発表されています。これらソフトウェアの進歩と、量子計算機と言うハードウェアの進歩を併せて考えると、いち論者の言うことを鵜呑みにはできないと考えます。
暗号技術について私を含む一般的な利用者は、暗号技術を使うこと自体が仕事ではないです。その暗号技術が100%ではないと言われているとしても、「1. それを超えるものは自分では到底作れないから、今あるものを利用するしかない」「2. 世間で充分に認知され、現実的に相手も使っていて利便性が高いから使わせてもらう」「3. 現実的な時間で突破されることは無いと言われているし、現実的に信頼できるものだそうなので使わせてもらう」と言うことだと思います。（少なくとも私はそうです）
が、新しい、あるいは昔から存在するけど知られていない技術を世に知らしめると言うことは、私自身は大変有意義なことだと思います。そのためには既にいくつか回答をいただいているように、知ってもらうための努力はどうしても必要になります。それは当然のこと、仕方の無いことだと思います。
暗号技術はセキュリティの分野でも国家レベルでも大変に重要な技術のひとつだと思いますが、背景に求められる理論や技術の高さの割に大変地味な（関係者の方々には失礼します、、、）ものなので、民間で興味を持つ方はそうそう居ないというのが私の印象です。ダイヤモンドの原石のように、黙っていても世間が取り上げ、勝手に磨き上げてくれる、と言う訳にはいかないことだと思います。
投稿2020/03/04 01:39
編集2020/03/04 01:43総合スコア9183
post quantum cryptographyで検索すれば、割と注目されている暗号なので、ぜひ調べてみてください。
英語が読めればですが。
暗号方式というのは、暗号理論の対になっている技術です。現在最も安全とされているレベルの暗号を達成できることが知られているのですが、そういう専門性の高い研究者が解けないと言っているので安心かなと思った次第です。自分のプログラミング能力では到底誰かに使ってもらうことは出来ないかもしれません。でもないよりあったほうがいいと思いますし、誰も使ってくれないなら自分で使おうと思います。
検索キーワードのご案内、どうもありがとうございます。
質問者であるGoldwasserさんの本意ではないかもしれませんので積極的な助言と言う訳ではありませんが、オープンソースとは反対にクローズドになるものの、企業に訴えると言う方向もあります。いわゆるプロプライエタリな製品では、製品の独自性を売りにすることが多いです。データベースの暗号化などで、一般的な暗号技術に加えて質問者さんご提示のような暗号技術をプラスすることが製品の優位性に繋がることもあります。
0
誰かわからん個人が書いたソースコードを公開したよ ← 他者はわざわざ積極的に採用を考えるか？
っていうのがまずあるかな，と．
（失礼ながら…… それを書いた人物に関して「分割コンパイルがうまくできない的な質問をしていた」ということを知っている状態ならば，なおさら避けます．）
「暗号化処理が欲しいです」という場面では，
「十分にテストされてきた/使われてきた 実績みたいなのがあるっぽいやつ」を探すんじゃないかなぁとか，素人ながらに思います．
投稿2020/03/04 01:25
総合スコア11656
暗号で検索すると、teratailないでも結構質問があるようなので、暗号を使うニーズ（データベースなど）は結構多いと思い、そのトレンドについて質問したつもりでした。
そういう仕事で暗号を実装する必要がある人のために、これから頑張ってコードを直しておこうと思っています。世界規格が決まるのにあと2年は掛かりそうです。
例えば誰か別の謎の人物が「俺もその暗号を実装してみた」とかいうコードをどこぞに公開した場合，
Goldwasserさんはそれを無条件に使いますか？
どのような条件を満たしていれば真面目に取り合うに値するでしょうか？
みたいな逆方向で考えてみるのも良いかもしれませんね．
とりあえず使い勝手のいいものを選んで使うというのはよくあります。
0
ここで質問するよりも、どこかの学会に所属し研究発表会に参加することで交流を深めたり、議論したり、あるいは論文として発表した方が有益かもしれません。
CiNiiを使えば論文検索もできますし、学会によっては PDF で論文を公開していますから（必ずしも最新の論文とはいかない場合もありますけど）、関連研究や動向を知るには良いかと思います。
投稿2020/03/03 14:15
総合スコア5086
0
一応GitHubでソースを公開しているのですが、どういう公開の仕方が一番使われるでしょうか？
暗号化ソフトか、暗号化ライブラリか、あるいは今のままソースで置いておくのがいいか。
他の人に使ってもらうことを想定するなら、以下の要件は抑えて置く必要があると思います。
- ライブラリの概要、ビルド方法、API 仕様、サンプルコードなどのドキュメントが整備されている。
→ ソースコードを読んでまで使う人はほぼいないので、ドキュメントを読むだけで、そのライブラリの使い方がわかるようにする必要があります。
→ GitHub で人気のライブラリを見ると、ドキュメントが丁寧に整備されています。
- CMake などのビルドツールでビルドできるようなっている
→ C/C++ などコンパイルが必要が言語では、ビルドがかんたんにできるようになっていたほうがよいです。
公開鍵暗号のニーズについて知りたいです。
質問者さんが作ったソフトのニーズはわかりませんが、上記2点が抑えられていれば、使いたいと思った人がいれば、使ってくれると思います。
投稿2020/03/03 14:20
総合スコア21956
ありがとうございます。参考にします。
0
フリーソフトとして公開することでコードの信頼性が高まると思うのですが違いますか？
違います。コードに変化が無いのに、公開しただけで信頼性が上がるわけがありません。
一応GitHubでソースを公開しているのですが、公開するに当たって注意すべき点がありましたら教えてください。
少しは進歩したことはわかったが、品質に大した変化はありません。私が指摘したことで対応できていないことが山ほどあります。さらに対応できた上で設計を見直すべきなのに。先は長い。
見ただけで、素人臭いコードの字面に大した変化なし、そのうえ
- -Wall でる警告が山のように出る
- 分割コンパイルになってない。
言ったでしょ、このコード品質では無謀だと。いかにも素人がやっつけ仕事で書いてみましたとわかるコードを、世の中の人が相手にすると思ってますか。何か勘違いしてるんじゃありませんか。
最低限、分割コンパイルの形になおして、-Wallの警告を全て消してみなさい。話はそれから。そこからでも道のりは遠いのですよ。
投稿2020/03/04 10:13
総合スコア1380
体に無理のない範囲で少しずつ勧めていきます。道のりは長いのですね。ありがとうございました。
私の質問である、暗号が必要とされる場面についての内容とは違うようですが、コードを修正する指針になっていると思います。
あら、退会しちゃった・・・。俺が引導を渡しちゃった格好だな orz
(1)コードを公開
(2)他者がそのコード見た結果，良くない点があれば指摘してくれる
(3)なるほど良くないな，と思えばコードを修正して(1)に戻る
みたいなサイクルが生まれれば「コードの信頼性が高まる」かもしれない．
上記(2)を，
【わざわざ労力かけて「ポジティブな」意見をくれている】と捉えれるか，
【わざわざ悪い点を指摘する「ネガティブな」意見が来る】と捉えるか．
今回は後者側であった模様？
0
質問に関係あるコードもまとめずにGitHubのリンク貼っただけなので一般論として質問のみを見て答えます。
需要として暗号技術というものは、どういうときに必要とされるのでしょうか？
どこでも暗号技術自体は使われています。
平文で保存・通信等するべきでない情報を暗号化する。それ以上でも以下でもないです。
公開鍵暗号のニーズについて知りたいです。
ニーズとは？どう言う分野でのニーズですか？
公開鍵暗号方式で有名なRSA暗号はOpenSSLなどに採用され今も開発が続けられています。そこらへんも察するにある程度のニーズはあるでしょう。
ただし、個人がそこら辺で開発した暗号方式はただの趣味の範疇を超えないと思ってください。「暗号方式開発して一攫千金〜！」的な思想をお持ちなら論文を書き、しかるべきところに提出するべきです。teratailで解決できるような問題ではありません。
論文新たに書ける内容を自分以外が知り得るわけないから。
あともう一言、他の人に見てもらいたいからスパゲッティは改善しましょう。
以上です。
投稿2020/03/04 10:26
総合スコア10429
0
公開鍵暗号のニーズに関して私はあえて、何も述べませんが
質問者さんの考えたアルゴリズムが目から鱗になりうる可能性も
あるかと思います。
まずは、どこでもいいのでフリーソフトとして公開し
readme 等で、解読できた方はご連絡下さいみたいな
一文をそえて公開してみてはいかがでしょうか？
私は決して1人のちからを馬鹿には絶対しない人種です。
投稿2020/03/04 01:53
編集2020/03/04 03:46
総合スコア1015
ありがとうございます。その言葉を信じて精進します。
＞質問者さん
ご質問の主旨は「公開鍵暗号のニーズについて知りたい」ではなかったのでしたっけ。まぁ、いいのですけど。
あなたの回答
tips
プレビュー
