データ変換、暗号、通信の分野に詳しい人に質問です。

あるいは詳しくない人もなぞなぞ感覚で答えてみてください。

データを送る人と受け取る人がいると設定します。
送る側は、一意(ユニーク、重複しない)の番号の羅列を持っています。
これにある処理を施して、処理後のデータを送ります。
受け取り側は、受け取ったデータから、処理前のデータ(番号)が一意であることが判断できなければなりません。
ただし、処理前のデータが推測できるようなことがあってもいけません。

どのような処理が考えられるでしょうか?

補足
・複数の段階を経た処理でもかまいません。
・途中で通信のようなものがあってもかまいません。
・受け取り側は、データの蓄積やコンピュータによる解析処理ができるものと仮定します。
・できれば第三者には登場してほしくないです。

説明が分かりにくいようでしたら、申し訳ないです。よろしくお願いします。

この条件では無理、と論理的に説明していただくだけでも結構です。

回答の条件
  • 1人2回まで
  • 13歳以上
  • 登録:2010/04/22 12:04:11
  • 終了:2010/04/26 10:08:14

ベストアンサー

id:t-wata No.6

t-wata回答回数82ベストアンサー獲得回数132010/04/22 19:09:20

ポイント60pt

処理後の値が一意である(処理元のデータが異なるのに処理後のデータが一緒な場合は処理元データの一意性を保証できない)

元データが推測できない(逆処理が存在しない)

この2つを同時に満たすことは数学的に不可能です。

元数値データが異なる場合に必ず異なる処理後数値データにするためにはその処理自体が単射(1対1)でないといけません。

しかし、単射なら左逆写像が存在することになり、つまり、処理後のデータを元に戻すための処理が存在する事を許すことになります。

なので上記いずれかについてある程度妥協が必要です。前者を妥協するならハッシュ関数があるので、後者を妥協する場合について以下に述べます。

元数値データのとりうる値が最大何桁の数値かが分かっていて、ある値の処理後データが分かっている場合、少なくとも総当りで元データを割り出すことが可能ですよね。

そのため総当り以外では元に戻せない、というものがこの場合期待される処理になります。

が、別にそんな複雑な処理じゃなく、元データをキー(鍵長が足りなければ適当なパディングを入れて)にしてAESや3DESなどでの暗号化処理、というので十分です。

id:ha34-13

わかりやすいですね。

問題に無理があるのはなんとなく分かっていました。やはり妥協点を探るとすればこのあたりですね。

2010/04/23 09:52:11

その他の回答(6件)

id:HowManyFiles No.1

HowManyFiles回答回数24ベストアンサー獲得回数72010/04/22 12:55:06

ポイント40pt

やや難のある解決方法ですが、以下のような感じでいかがでしょうか。

1.一意の番号の羅列(A)に、別のID(別の一意な番号(B))をそれぞれ割り振る。

2.(A)のMD5値を算出し、(C)とする。

3.(B),(C) の羅列を受け取る側に渡す。

こうすれば、データを受け取った側は(B)の部分からそのデータが一意であることを判断できますし、(C)の値から(A)を推測することはほぼ不可能です。

id:ha34-13

説明不足で申し訳ないです。自分でも問題をきちんと理解していないのに質問しました。

送り側が持っているIDは第三者機関が認めている正当なIDです。

こちらが独自に一意なIDを割り当てるといっても誰がそれを証明するのか?というような問題があるわけです。

その第三者機関とやり取りをすればいい話なのですが、そこをうまく回避したいな、と。

とりあえず一意であることだけ確認できればいいです。

あと、私も「ハッシュ関数でいいんじゃない」と思ったのですが、数値とハッシュ値の対照表を作れば解析出来ると言われました。

2010/04/22 14:08:50
id:kick_m No.2

kick_m回答回数1372ベストアンサー獲得回数542010/04/22 14:08:02

ポイント10pt

説明がいまいちわかりませんが、いわゆる暗号というものはそういう風にできています。

http://www

id:ha34-13

たしかに説明がよくわからない無茶な問題になっていることは認めます。

質問者ですらよく分かっていない問題に対してパーフェクトな回答を提示してくれるエスパーを希望しています。

2010/04/22 15:42:09
id:raywhite No.3

raywhite回答回数32ベストアンサー獲得回数42010/04/22 15:12:48

ポイント50pt

ハッシュ関数でもコリジョンが起こる可能性がある以上、「一意であることを保証」することはできません。

あくまでも「確率的に一意と言える可能性が高い」方法なだけです。


目的のことは公開鍵方式の暗号を使えばできます。


最初に受け取り側Aの秘密鍵Aと公開鍵Aを用意し、送り手側Bの秘密鍵Bと公開鍵Bも用意します。

送り側Bは送る文書Xを公開鍵Bを使って暗号化しデータXを得ます。

次にその暗号化したデータXを公開鍵Aを使って暗号化しデータYを得ます。

データYを受け取り側Aに送ります。


受け取り側AはデータYを秘密鍵Aを使って復号しデータZを得ます。


得られたデータZは送り側Aの秘密鍵が無ければ復号できない一意性が保たれたデータになります。

id:ha34-13

復号できないデータを渡した相手に対して、それが正当なデータだと言い張るには?

ただのゴミを渡したんじゃないの?という問いにどう答えるか。

このあたりで悩んでいます。「一意」という言葉がまずかったかもしれません。

2010/04/22 16:03:37
id:taknt No.4

きゃづみぃ回答回数13539ベストアンサー獲得回数11982010/04/22 17:20:41

ポイント30pt

>ですけど、復元せずにどうやって正しいことを判断するのか、という禅問答のようになっています。

通常、送信データが正しいかどうかの判断に CRCを使います。

それは 元のデータに CRC用のデータを付加して 送付するのです。

それで 受け取った側は、そのCRCを判断して データが正しいかどうか判断します。

http://www.cdwavmp3.com/dl/other/crc.html

また、WinRarの場合、

WinRAR は書庫にリカバリレコードを付加することで壊れた書庫を修復したり、変更を防止するためロックをかけたりする機能を提供します。

このような機能があります。

http://www.diana.dti.ne.jp/~winrar/winrar.html

元のデータが正しいかどうか判断するには なんらかの付与データが必要となります。

id:ha34-13

やはりハッシュですかね...天文学的な確率で衝突が起こるのは無視するとして...

でも、元データが推測できてしまうのが問題です。

2010/04/22 17:46:48
id:ko8820 No.5

ko8820回答回数1221ベストアンサー獲得回数692010/04/22 17:30:47

ポイント20pt

RSA暗号

暗号化のライブラリがうってますから、それをつかえば条件を満たすものはたくさんあります。

自前で実装するとミスる可能性があって、テストも十分行えないので不良を作りこむ結果になることが多いです。

id:ha34-13

暗号化すればいい、というのとは違うんです。

2010/04/22 17:59:53
id:t-wata No.6

t-wata回答回数82ベストアンサー獲得回数132010/04/22 19:09:20ここでベストアンサー

ポイント60pt

処理後の値が一意である(処理元のデータが異なるのに処理後のデータが一緒な場合は処理元データの一意性を保証できない)

元データが推測できない(逆処理が存在しない)

この2つを同時に満たすことは数学的に不可能です。

元数値データが異なる場合に必ず異なる処理後数値データにするためにはその処理自体が単射(1対1)でないといけません。

しかし、単射なら左逆写像が存在することになり、つまり、処理後のデータを元に戻すための処理が存在する事を許すことになります。

なので上記いずれかについてある程度妥協が必要です。前者を妥協するならハッシュ関数があるので、後者を妥協する場合について以下に述べます。

元数値データのとりうる値が最大何桁の数値かが分かっていて、ある値の処理後データが分かっている場合、少なくとも総当りで元データを割り出すことが可能ですよね。

そのため総当り以外では元に戻せない、というものがこの場合期待される処理になります。

が、別にそんな複雑な処理じゃなく、元データをキー(鍵長が足りなければ適当なパディングを入れて)にしてAESや3DESなどでの暗号化処理、というので十分です。

id:ha34-13

わかりやすいですね。

問題に無理があるのはなんとなく分かっていました。やはり妥協点を探るとすればこのあたりですね。

2010/04/23 09:52:11
id:freemann No.7

freemann回答回数305ベストアンサー獲得回数482010/04/25 05:40:12

ポイント20pt

#3の回答と似ていますが、普通公開鍵のときは、受け取り側が、非公開の秘密鍵と、公開鍵を用意します。

公開鍵は、ある機関で受け取り側のものであることを保証します。

送り側はその公開鍵を入手し、それを使って暗号化します。そして、その暗号化されたものを受け取り側に送ります。

受け取り側は自分の秘密鍵で複合して、暗号化する前のデータを入手します。

id:ha34-13

そうですね。普通の使い方ならこうなりますね。

2010/04/26 10:01:29
  • id:australiagc
    いくつか質問です;

    >> 受け取り側は、受け取ったデータから、処理前のデータ(番号)が一意であることが判断できなければなりません。

    (1) 『一意であるデータ』と『一意でないデータ』が存在し、「一意であるデータ」を受信した場合に、受け取り側はそれが「一意であるデータ」であることを判断できなくてはいけないということでしょうか?

    >> 処理前のデータが推測できるようなことがあってもいけません。

    (2) 受け信り側は「『一意であるデータ』だということ」は判断できても、「そのデータが何なのか」については判断できてはいけないということでしょうか?
    (言い換えると、一意であることだけは分かるけど、その内容自体は分からない)
  • id:ha34-13
    中身が分かってはいけないので、受け取りデータ(あるいは受け取った後になんらかの処理を加えたデータ)に衝突・重複が起こった場合は、どちらかが間違っている、としか判断できないと思います。これぐらいのレベルでいいです。
  • id:taknt
    可能性からして できない。

    たとえば 1234を ある処理を ほどこして 4567とした場合、
    この4567も一意の数である。これが どうやって 1234と判断できるのだろうか?

    また 1234ではなく 3456などに 復元される恐れもある。

  • id:ha34-13
    復元する必要はないんです。むしろできてはいけない。

    ですけど、復元せずにどうやって正しいことを判断するのか、という禅問答のようになっています。
  • id:ha34-13
    おそらく証明機関のような第三者や、最初のIDの発行元などが介在しないとダメなんでしょうね。

    でもそういった既成概念にとらわれない斬新な発想を期待しています。
  • id:raywhite
    >やはりハッシュですかね...天文学的な確率で衝突が起こるのは無視するとして...
    >でも、元データが推測できてしまうのが問題です。

    ハッシュを使うことにしたとしても、

    >ただのゴミを渡したんじゃないの?という問いにどう答えるか。

    という疑念が生じるのなら意味がありませんよ。

    どういう状況で何を実現したいのかの説明をした方がよりよいアイデアが出てくるのでは?

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません