- ベストアンサー
一方向関数
chisetazaの回答
素因数分解の他の代表的な一方向性関数は，離散対数です． 離散対数問題とは以下のような問題です． ｐを素数とします．また，ｇをｐとは互いに素な数の一つとします．このとき，ｙ＝ｆ（ｘ）＝ｇ^ｘ ｍｏｄ ｐとしたとき，ｙを求めるのは容易だが，逆にｙからｘを求めるのは難しいということです． 離散対数問題を利用した暗号にElGamal暗号があります． また，楕円曲線の性質を利用することで，この離散対数問題の構成が可能であることを利用した暗号が，近年最も注目を浴びている楕円曲線暗号です． これらのことについては，「現代暗号」，岡本龍明・山本博資著，産業図書に詳しく載っています．
関連するQ&A
- 素因数分解はなぜ困難？
今暗号について勉強しています。その中に素因数分解が困難であることを利用してつくられた暗号がいくつかありますが、なぜ素因数分解が困難であるのかがわかりません。それを証明する方法などがありましたらなんでもいいので教えてください。
- ベストアンサー
- 数学・算数
- RSA暗号解読の素因数分解による方法について。
下記の通りで正しいでしょうか。： Microsoft Bing AI （＝ Bing Chat）生成人工知能の回答を、まとめ、且つ、補足しますと、次の通りです。 自然数 N を、√N （＝ Nの平方根）未満の自然数であって末位の数字が１，３，７，９のもので以て、割ってゆき、N を素因数分解する、という計算の、時間計算量は、O(Nの４乗根）です。 実際には、RSA暗号による暗号文の暗号は、巨大素数を２つ掛け合わせて作りますので、Nの平方根未満の自然数で、末位が１，３，７，９のもので、しかも、大きいもの順に取ったもので順に割っていけば、N の素因数分解は、時間計算量を、それよりも遥かに小さくして済ませらせます。 上記の様に、問題サイズ N に対する、N の４乗根のオーダーの時間を上界（この場合は、自然数の計算ですので上限）とする、普通の割り算の単純作業だけで、つまり、ごくごく短時間に、N の素因数分解が出来てしまいますので、RSA暗号も、いとも簡単に解けてしまう、ということです。
- ベストアンサー
- セキュリティ対策
- 学校でRSA暗号について勉強して分からないところがありましたので質問し
学校でRSA暗号について勉強して分からないところがありましたので質問します。 暗号文の作成者をAさん、復号者をBさんとします。 Aさんは暗号文と公開鍵｛e,n｝を一般に公開しますよね？ 暗号文を復号化するには秘密鍵が必要ですが、Bさんはeとnしか分からない（一般の人と得られる情報が同じ）のにどうやって秘密鍵を作成するのですか？nのもとになっている2つの素数がわからないことには秘密鍵が作成できないとおもうのですが… RSA暗号はnの素因数分解が計算量的に困難だから安全なんですよね？Bさんはどうやって２つの素数を特定するのでしょうか？ 教えてください。
- ベストアンサー
- ネットワーク
- すばやく素因数分解する方法は？
「暗号解読」（サイモン・シン（著）青木薫（訳） 新潮社）という本を読んで、急に素数のことに関心を持ちました。 数十桁もある数（合成数）を素因数分解するのは、えらく時間がかかることが書かれていました。 中学生が計算する素因数分解や、「エラトステネスのふるい」のほかに、手計算や計算機を使って、合成数から素数を見つける方法（素因数分解）を知りたいので、ご存知の方教えてください。 できれば、計算機科学における現在、最速の素因数分解の方法（アルゴリズム）を知りたいです。
- ベストアンサー
- 数学・算数
- どんな素因数も一瞬で分解できる人がいたと思いますか
人類史上どんな素因数も一瞬で分解できるという人はいたことありますか？ (大量の素因数を持つものについて、分解したことを私たちに証明するためにそれらの数字を書き出す作業時間は考慮しない。) 私自身は今現在はいないという立場であります。 理由としては、RSA暗号など素因数を利用した高度な暗号を解読したとのことで不正アクセスの罪で捕まった人の中で「私はどんな素因数も一瞬で分解出来る自分の脳に酔って魔が差したんだ」といった供述をした人を古今東西で見たことがないからです。 それぞれの分野には秀でた人がいるものですが、トップと次席、それ以降に続いていく人達の実力差は連続的なものです。 油断してれば上位の者は下位の者追い抜かされ序列が塗り替わるということもあるでしょう。 ノーベル賞を取るような人についてだって、実は陰ではもっと前から同じような実績を残していたという事実が往々にして科学史にはあります。 ようするにどんな分野のものさしで測っても私たちはどっこいどっこいの者同士の連続体でしかないのです。ある人を除き。 私はそれこそ「あらゆる素因数を一瞬で分解できる人」と考えます。 リーマン予想も肯定的に解決されてないなかでその能力は人知を超越しているというほかありません。 コンピュータでも最低で一年以上かかるとされる３００桁の数字の素数判定ないし素因数分解も、一瞬で。もうラマヌジャンがすごいとかいうレベルではありません。 そういう人は「素因数を分解する能力」というものさしで測ったとき、まさにその他の全人類から群を抜いているということになるでしょう。 その次席の人がいくら頑張って努力しても、連続的でないその能力差という壁は越えられない ・・・そういう人、「ある分野のものさしで測ったとき絶対的にずば抜けている人」を、ちなみにですが、私は真の天才と呼んでいます。 その頭脳の稀少性は数理科学者の権威とも比較にもならないでしょう。 それだけのギフトの持ち主がいたらならば、自惚れもするでしょうよ。自分の能力を試してみないわけにはいかなくなるでしょうよ。 そういうことが私の狭い見聞のもとでは今まで犯罪史になかったと推測されるので、 そのようなことで己惚れるだけの能力を持っていた人が過去いなかったと考えるのです。 質問に至る背景説明が長くなってしまいましたが、 貴方はそのような人がいたと思いますか？いなかったと思いますか？
- ベストアンサー
- 数学・算数
- 公開鍵暗号方式の復号に関して質問します。
暗号方式は、発信者Aさんが正当な受信者Bさんに暗号化した電文を送付し、途中で不正に傍受したCさんには電文の復号ができず、正当な受信者Bさんには復号ができるという考えかたです。 正当なる受信者Bさんには復号が可能で、不正なる傍受者Cさんには復号が不可能であるためには、BさんとCさんの間に情報格差を維持しないと駄目だと思うのですが、公開鍵方式の場合に正当なる受信者Bさんと不正な傍受者Cさんの間にどのような情報格差が存在するのでしょうか。 ＝＝＝ RSA暗号の例題を考えます ＝＝＝ A：暗号の発信者 B:正当なる暗号の受信者 C:不正なる暗号傍受者 Aさんは 素数P=3 素数Q=11 を選んで、 33を法とする世界（Mod33）を利用します。 Aさんは原文を3乗し、Mod33を取った暗号文をBさんに送付しますが、ここで、公開鍵情報として、「33を法とする」および「3乗した」という二つの情報を開示して暗号を送付します。 暗号を不正に傍受したCさんは、33の素因数分解ができないために、P=3、Q=11という二つの素数を特定できず、3xD=｛nｘ（p-1｝X(Q-1)+1｝において、N=1の場合でもP,Qが分からないので、復号することがきません。 ところが正当なる受信者Bさんは、3xD=1x（3-1）ｘ（11-1）+1=21より、D=7を求め、受診した暗号を7乗することで受信電文の復号が可能となります。 ＝＝＝＝ 以上例題おわり ＝＝＝＝ 不正なる傍受者Cさんは素因数分解が困難であることから二つの素数P、Qの特定ができずに復号ができないことは良く理解できます。 しかし、正当なる受信者Bさんは、なぜP,Qを特定し、D=7を求めることが出来るのでしょうか。 質問１：なぜBさんだけが復号可能なのでしょうか？ 質問2：Bさんは素因数分解をせずとも、P=3、Q=11という二つの素数を知ることができるのでしょうか？ 質問3：素数P、Qの値を特定できなくてもD=7を知ることができるのでしょうか？ 公開鍵暗号方式の根本原理が分かっていないと思われるので、公開鍵暗号方式、あるいはRSA暗号方式の考え方をご存じの方ご教示いただけると助かります。
- ベストアンサー
- 科学
- （難）オイラーのφ関数で、n≠2,6ならばφ(n)≧√n
http://mathworld.wolfram.com/TotientFunction.html の（12）によるとオイラーのφ関数で、 n≠2,6ならばφ(n)≧√n となるようなのですが、 nを素因数分解した素数たちをp_kとすると、オイラーの関数は、 φ(n)= n (1 - 1/p_1)(1 - 1/p_2)(1 - 1/p_3)....(1 - 1/p_k) という事実を使って考えたのですが解けそうにありません。 証明のためのアイデアがありましたら教えていただけないでしょうか?
- ベストアンサー
- 数学・算数
お礼
参考文献に凄く詳しく載っていて とても助かりました。ありがとうございました。