逆ハッシュ関数（逆一方向関数）？

ハッシュ関数では、原文xからハッシュyを求める事 y=f(x) は容易ですが、その逆関数、yからxを求める事 x=f'(y) が困難と言われています。

逆に、原文xからyを求めることは困難だが、yからxを求める事が容易である関数というのはありませんか？

秘密鍵kを使用し、y=f(x,k) で変換（kを知らなければ困難）、x=f'(y) で逆変換（kを知らずとも復号可能）ということになると思いますが…。

No.4 ベストアンサー 回答者： betagamma 回答日時： 2006/07/25 15:19

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 回答者： rinkun 回答日時： 2006/07/25 13:05

前処理のハッシュ関数を除いたRSAデジタル署名で実現できますね。

# DSA等は元の値を計算することはできないのでダメ

RSAの秘密鍵・公開鍵のペアを(k,p)として、xを秘密鍵kで演算した結果をz、y=(z,p)とすれば、zを公開鍵pで演算する処理をf'とすればxが計算できます。

使い道はなさそうですけど。

No.2 回答者： Tacosan 回答日時： 2006/07/25 12:51

公開鍵暗号系を使ったデジタル署名?

この回答へのお礼

正にこれかもしれません！
デジタル署名について、もう少し調べてみます。ありがとうございました！

しかし、No.1さんの考え方にも興味があります。

お礼日時：2006/07/25 14:22

No.1 回答者： betagamma 回答日時： 2006/07/25 11:38

構成できなくはありませんが、ちょっと考えたところ、使い道が見当たりません。

一応、一つ考えてみました。
離散対数問題というのがあります。これは、自然数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演算子が絡んだ時の移項について知らない（知識は高校数学レベルです…）ので、復元が理解できませんでした。

補足日時：2006/07/25 14:24