
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
No.3
- 回答日時:
前処理のハッシュ関数を除いたRSAデジタル署名で実現できますね。
# DSA等は元の値を計算することはできないのでダメ
RSAの秘密鍵・公開鍵のペアを(k,p)として、xを秘密鍵kで演算した結果をz、y=(z,p)とすれば、zを公開鍵pで演算する処理をf'とすればxが計算できます。
使い道はなさそうですけど。
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演算子が絡んだ時の移項について知らない(知識は高校数学レベルです…)ので、復元が理解できませんでした。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
100以下の自然数のうち、次のよ...
-
エクセルでのシグマ計算
-
1億x1億はいくらでしょうか?
-
10分の1は「10/1 それとも1/10...
-
「最大300字程度」
-
50以下は“50”も入るのですか?
-
実績を積むという表現
-
16進小数0.Cを10進数小数に変換...
-
偏微分の記号をタイプするため...
-
【機械図面】 最大値・最小値...
-
高窓(ハイサイド窓)を平面図...
-
機械的浮動とは遺伝的浮動と同...
-
5進法を10進法への直し方
-
対数変換する意味?
-
算数計算 大至急お願いします
-
計算量のオーダについて
-
有効数字3桁 有効数字3桁で4桁...
-
基本情報の浮動小数点について
-
フーリエ変換・逆変換の虚数成...
-
トリップフリーって何ですか? ...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
100以下の自然数のうち、次のよ...
-
エクセルで60進法計算の仕方...
-
エクセル関数で源泉徴収額を計...
-
3桁の自然数の中で、次の個数を...
-
工事の共通仮設費率の計算がで...
-
この産み分けの計算でハズレの...
-
Excelで勤務の過不足時間を計算...
-
中3の問題です
-
経費率の計算方法を教えて下さい。
-
ラプラス変換の「s」とは?
-
エクセルでのシグマ計算
-
関数電卓の使い方
-
文字を含む三角関数の定積分の...
-
小学生の割合の問題
-
最小公倍数と最大公約数の求め...
-
アルゴリズムによる整列方法に...
-
Eの数字の計算式について
-
(1)の計算のところなんですけ...
-
2次元フーリエ変換の実際について
-
A÷(B×C)=?
おすすめ情報