ちょっと変わったマニアな作品が集結

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

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

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

このQ&Aに関連する最新のQ&A

A 回答 (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
    • good
    • 0

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


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

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

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

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

    • good
    • 0
この回答へのお礼

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

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

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

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



一応、一つ考えてみました。
離散対数問題というのがあります。これは、自然数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
    • good
    • 0

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q法(mod)の四則演算について

とても困ってます。
情報セキュリティの課題で

・整数は素数を法とする演算では、四則演算が実行できる。その例を示せ。
・整数は合成数を法とする演算では、四則演算の一部で、解が一意に定まる場合と定まらない場合がある。その例を示せ。

この2つの問題が分かりません。
答えを教えていただけませんか?お願いします。

Aベストアンサー

以下、剰余算の計算式を「13 mod 7 = 6」(13÷7の余りが6という意味)のように表します。suryaさんの読みやすいように適宜読み替えて下さい。

・法が素数の場合
2つの整数(5, 13)を7で割ったときの剰余の四則演算の例を以下に示します。

1. 加算
13 mod 7 = 6, 5 mod 7 = 5なので、(13 mod 7) + (5 mod 7) = 11 mod 7 = 4 … (1)
また、(13 + 5) mod 7 = 18 mod 7 = 4 … (2)
(1)と(2)は同じ値になるので、(13 mod 7) + (5 mod 7) = (13 + 5) mod 7

2. 減算
13 mod 7 = 6, 5 mod 7 = 5なので、(13 mod 7) - (5 mod 7) = 1 mod 7 = 1 … (1)
また、(13 - 5) mod 7 = 8 mod 7 = 1 … (2)
(1)と(2)は同じ値になるので、(13 mod 7) - (5 mod 7) = (13 - 5) mod 7

3. 乗算
13 mod 7 = 6, 5 mod 7 = 5なので、(13 mod 7) × (5 mod 7) = 30 mod 7 = 2 … (1)
また、(13 × 5) mod 7 = 65 mod 7 = 2 … (2)
(1)と(2)は同じ値になるので、(13 mod 7) × (5 mod 7) = (13 × 5) mod 7

4. 除算
剰余の除算は整数や実数といった一般的な数値の除算と異なるので注意して下さい。
剰余での除算は「逆数を掛ける」ことで定義されます。「aをbで割る」はa×b^-1で表されます。

(3 mod 7) × (5 mod 7) = 1なので、(5 mod 7)^-1 = (3 mod 7)
また、3.乗算の結果から、(13 × 5^-1) mod 7 = (13 mod 7) × (5 mod 7)^-1が言える。これを計算すると、
(13 × 5^-1) mod 7 = (13 mod 7) × (5 mod 7)^-1 = (13 mod 7) × (3 mod 7) = 4


・法が合成数の場合
良い例かどうかは分かりませんが…。
法が8のときの除算を例に挙げてみます。

例えば、(5 mod 8) × (3 mod 8)^-1は(3 mod 8) × (3 mod 8) = 1だから、
(5 mod 8) × (3 mod 8)^-1 = (5 mod 8) × (3 mod 8) = 7のように計算できます。
しかし、(5 mod 8) × (4 mod 8)^-1は、4 mod 8の逆数を求めることができないため計算できません。

以下、剰余算の計算式を「13 mod 7 = 6」(13÷7の余りが6という意味)のように表します。suryaさんの読みやすいように適宜読み替えて下さい。

・法が素数の場合
2つの整数(5, 13)を7で割ったときの剰余の四則演算の例を以下に示します。

1. 加算
13 mod 7 = 6, 5 mod 7 = 5なので、(13 mod 7) + (5 mod 7) = 11 mod 7 = 4 … (1)
また、(13 + 5) mod 7 = 18 mod 7 = 4 … (2)
(1)と(2)は同じ値になるので、(13 mod 7) + (5 mod 7) = (13 + 5) mod 7

2. 減算
13 mod 7 = 6, 5 mod 7 = 5なので、(13 mod 7...続きを読む


人気Q&Aランキング