No.1
- 回答日時:
構成できなくはありませんが、ちょっと考えたところ、使い道が見当たりません。
一応、一つ考えてみました。
離散対数問題というのがあります。これは、自然数nで割ったあまりしか考えない世界で、n,aがわかっているとき、a^kからkを求めることがとても難しくなるという問題です。
例えば、n=7,a=5,k=3としましょうか。
5^3 mod 7=125 mod 7 = 55 mod 7 =13 mod 7 = 6 mod 7
(mod 7は、7で割ったあまり。9 mod 7 = 2)
で、a=5 mod 7 = 5ですから、この問題は、n=7,a=6がわかっているとき、5を与えられて、k=3を求める問題です。
この問題は、困難で、実際に、Diffie-Helman鍵交換という、共通鍵をやりとりする方法に用いられています。最初に、nとaをばれてもいい方法でやりとりしておいて、kに共通鍵を入れておけば、a^kを計算してやりとりすれば、たとえa^kが盗聴されても大丈夫、というものです。
なので・・・
a^kからkを求めることを一般化して、y=log(a,x) mod nとおけば、yを求めることはとても困難になるはずです。
この回答への補足
回答ありがとうございます。しかし、のっけから理解力不足で申し訳ありません。
xを元の値、yを変換値として、変換式(困難)と復元式(容易)を教えて頂けませんでしょうか?
また、その他のどの要素(n,a,kなど?)が既知・未知であるので困難・容易という簡単な根拠もあれば嬉しいです。
y = x^k mod n (nは既知だがkが未知なので困難)
x = log(x,y) mod n (難易不明…)
mod演算子が絡んだ時の移項について知らない(知識は高校数学レベルです…)ので、復元が理解できませんでした。
No.2
- 回答日時:
公開鍵暗号系を使ったデジタル署名?
正にこれかもしれません!
デジタル署名について、もう少し調べてみます。ありがとうございました!
しかし、No.1さんの考え方にも興味があります。
No.3
- 回答日時:
前処理のハッシュ関数を除いたRSAデジタル署名で実現できますね。
# DSA等は元の値を計算することはできないのでダメ
RSAの秘密鍵・公開鍵のペアを(k,p)として、xを秘密鍵kで演算した結果をz、y=(z,p)とすれば、zを公開鍵pで演算する処理をf'とすればxが計算できます。
使い道はなさそうですけど。
No.4ベストアンサー
- 回答日時:
No.1です。
mod関連の四則演算は、普通にできます。つまり・・・
a = b(mod n)
a*c = b*c (mod n)
a+c = b+c (mod n)
a-c = b-c (mod n)
c=bとおけば、
a-b = b-b = 0 (mod n)
ですので、以降できます。
自分で、あまりを確かめながらやると、楽しかったりします。
それでですね、ハッシュ関数の逆関数の演算が困難ということについて、ちょっと細くします。逆関数の演算が困難なのはおっしゃる通りなんですが、実は、y=f(x)の逆関数f'(y)の結果は、一つだけじゃなくて、何通りもあるんですよ。関数というのは、結果が一つに定まるものの事をいいますから、厳密には、f'(y)は関数ですらありません。
このことは、次のように考えればわかります。ハッシュ関数の文字数(今、一番使われているSHA1で、確か、160bit=日本語の文字80文字分)は、決まっています。
世の中には、色んな長さの文章があるのに、どんなに長い文章
xを入力しても、ハッシュ関数fを通してf(x)を計算すると、20文字分の長さしか出てこない。
ということは、あるハッシュ関数の値yをとってきたときに、原文に対応するxは、複数あるはずなんです。(もっとも、そのうち、意味のあるものは、一つに絞れるでしょうが)
で、f(x)を求めるのが困難な場合について話しましょうか。No.2さんやNo.3さんのおっしゃった方法でも、作れますね。
基本的に、暗号にできるようないい性質をもった困難な問題というのは限られているので・・・よく知られている中では、No.1で述べた離散対数問題か、RSAで使われている素因数分解の困難性の問題か、どっちかですね。
で、使い道ですが・・・時限暗号というのがあります。これは、指定された時刻になるまで、誰も解けない暗号です。そっちに、ちょっと使えるかもしれませんね。
日本で、研究している有名な人がいて、一般向けのPDFとかもあるので、書いておきます
http://homepage1.nifty.com/herumi/mtt/tc.html
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
この産み分けの計算でハズレの...
-
エクセル関数で源泉徴収額を計...
-
エクセルで60進法計算の仕方...
-
中学受験の算数の問題
-
100以下の自然数のうち、次のよ...
-
経費率の計算方法を教えて下さい。
-
Excelで勤務の過不足時間を計算...
-
工事の共通仮設費率の計算がで...
-
log[2]47って・・・
-
10分の1は「10/1 それとも1/10...
-
1億x1億はいくらでしょうか?
-
実績を積むという表現
-
【機械図面】 最大値・最小値...
-
50以下は“50”も入るのですか?
-
5進法を10進法への直し方
-
16進小数0.Cを10進数小数に変換...
-
「最大300字程度」
-
「充足に達しましたので」これ...
-
Excel 16進数
-
HEX2BIN関数の使い方。
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
100以下の自然数のうち、次のよ...
-
エクセルで60進法計算の仕方...
-
エクセル関数で源泉徴収額を計...
-
工事の共通仮設費率の計算がで...
-
この産み分けの計算でハズレの...
-
エクセルでのシグマ計算
-
3桁の自然数の中で、次の個数を...
-
Excelで勤務の過不足時間を計算...
-
ラプラス変換の「s」とは?
-
○+○=5
-
経費率の計算方法を教えて下さい。
-
勝率50%の事象を100回やって勝...
-
最小公倍数と最大公約数の求め...
-
99の10乗の下位5桁の数を求める...
-
端数を習うのは小学何年生の頃...
-
文字を含む三角関数の定積分の...
-
X-0.3X=Y でYを求めるには?
-
◯ヶ月を△年◇月というように変換...
-
数学というより算数なのですが...
-
ローン支払いにおける金利の計...
おすすめ情報