- PR -

便乗・・情報の隠蔽したまま,情報が一致している事を確かめる方法

1
投稿者投稿内容
ちびらり
会議室デビュー日: 2005/09/06
投稿数: 2
投稿日時: 2005-09-06 15:59
同じ題のスレッドがあったと思いますが・・・
便乗します。

「互いにどんな情報を持っているかという事を
お互いに隠蔽したまま,共通する情報のみを明らかにする」
方法を、私も知りたいのですが、

私の場合は、
Aさんのもつ電話番号が多数入った(数十〜百件)CSVファイル(A)と、
Bさんのもつ電話番号が多数入った(数十〜百件)CSVファイル(B)と
を比較し、共通する電話番号をBさんが抽出するというかたちです。
ちなみにAさんのもつ(共通するものを除いた)電話番号の内容を、
Bさんから隠蔽したいです。

先のスレッドをみますと、どうやらハッシュ関数を付け合せるのが
良い方法に思えますが、
フリーソフトなどを駆使して、素人でもスマートにできる方法って
具体的にありますでしょうか。

当方コンピュータ、プログラミングなどはど素人ですが、なにぶん
ご教授の程、よろしくお願いいたしますm(__)m
甕星
ぬし
会議室デビュー日: 2003/03/07
投稿数: 1185
お住まい・勤務地: 湖の見える丘の上
投稿日時: 2005-09-06 16:16
ハッシュを用いた場合、コリジョン(異なるデータから生成したハッシュ値が一致する)を起こす可能性がわずかにあります。これを許容できる、わずかな確立で一致していないのに一致していると判定してしまっても構わないなら、ハッシュ値でOKです。MD5やSHA1のハッシュを生成するフリーウェアやライブラリが公開されていますから、それらを用いれば簡単に作れるでしょう。

コリジョンを許容できないのであれば、公開鍵暗号を用いる事になるでしょう。
Aさんは電話番号を公開鍵で暗号化します。暗号化された電話番号の一覧と、公開鍵をBさんに送ってください。Aさんの秘密鍵をBさんは知らないので、Bさんは暗号化された電話番号の一覧を解読できません。
Bさんも自分の持つ電話番号の一覧を、Aさんの公開鍵で暗号化します。もし同じ電話番号なら、電話番号を暗号化したデータも一致するはずです。AさんとBさんの暗号化された電話番号を比較して、同じ暗号データになっている物が無いか比較すればOKです。
ちびらり
会議室デビュー日: 2005/09/06
投稿数: 2
投稿日時: 2005-09-06 17:03
早速の回答ありがとうございます。
コリジョンは許容できます。

MD5やSHA1のフリーウェアはみつけましたが、
ファイルのハッシュ値を出すものが殆どでした。
CSVの一行一行ごとのハッシュをまとめて出してくれる
ものってないでしょうか?
それとも作らなきゃだめでしょうか。

勝手ばかりいいますが・・
甕星
ぬし
会議室デビュー日: 2003/03/07
投稿数: 1185
お住まい・勤務地: 湖の見える丘の上
投稿日時: 2005-09-06 17:23
http://www.vector.co.jp/soft/dl/win95/util/se224884.html
コマンドライン引数で与えた文字列をからハッシュ値を算出できます。電話番号一覧をテキストエディタなどで整形して、BATファイルにしては如何です?出力はファイルにリダイレクトするなり、コンソールの内容をコピーするなりした上で、テキストエディタで整形。

_________________
甕星 <mikahosi@abox9.so-net.ne.jp>
http://blogs.msmvp.jp/mikahosi/
cn009
ベテラン
会議室デビュー日: 2004/05/13
投稿数: 72
投稿日時: 2005-09-06 22:24
面白そうなのでPerlとmd5sumで適当に作ってみました。
まだあまりテストしていませんし、無保証ですが参考程度にどうぞ。

mkhashlist.pl
コード:

#!/usr/bin/perl

if ($#ARGV != 2)
{
print STDERR "usage: mkhashlist.pl datafile hashlist datalist\n\n";
exit(-1);
}

open(DATAFILE, "<$ARGV[0]") or die "cannot open $ARGV[0]\n\n";
open(HASHLIST, ">$ARGV[1]") or die "cannot open $ARGV[1]\n\n";
open(DATALIST, ">$ARGV[2]") or die "cannot open $ARGV[2]\n\n";

while (<DATAFILE>)
{
chomp;
if ($_ =~ /^\s*$/){ next;}
($hash) = split(/\s/, `echo '$_' | md5sum`, 2);
print HASHLIST "$hash\n";
print DATALIST "$hash\t$_\n";
}

close(DATAFILE);
close(HASHLIST);
close(DATALIST);

exit(0);



cmphashlist.pl
コード:

#!/usr/bin/perl

if ($#ARGV != 2)
{
printf STDERR "usage: cmphashlist.pl hashlist datalist outputfile\n\n";
exit(-1);
}

open(DATALIST, "<$ARGV[1]") or die "cannot open $ARGV[1]\n\n";
chomp(@datalist = <DATALIST>);
close(DATALIST);

open(HASHLIST, "<$ARGV[0]") or die "cannot open $ARGV[0]\n\n";
open(OUTFILE, ">$ARGV[2]") or die "cannot open $ARGV[2]\n\n";

while (<HASHLIST>)
{
($hash) = split(/\s/, $_, 2);
@tmp = grep(/^$hash\t/, @datalist);
foreach (@tmp)
{
(undef, $data) = split(/\t/, $_, 2);
print OUTFILE "$data\n";
}
}
close(HASHLIST);
close(OUTFILE);

exit(0);



使い方としては、まずAさんが
 mkhashlist.pl phone-a.csv hashlist-a.txt datalist-a.txt
として、phone-a.csvから、ハッシュが入っているhashlist-a.txtと、ハッシュと元データが入っているdatalist-a.txtを作ります。

ハッシュが入っているhashlist-a.txtをBさんに渡します。
Bさんは
 mkhashlist.pl phone-b.csv hashlist-b.txt datalist-b.txt
として、phone-b.csvから、ハッシュの入っているhashlist-b.txtと、ハッシュと元データが入っているdatalist-b.txtを作ります。
 cmphashlist.pl hashlist-a.txt datalist-b.txt phone-c.csv
と実行すると、phone-a.csvとphone-b.csvのハッシュの一致する行が含まれるphone-c.csvが出来ます。

かなり適当ですが、とりあえずLinuxでもWindowsでも動いているようです。
# でもechoコマンドの挙動の違いで、ハッシュのリストに互換性は無いです
WindowsではActivePerlGNU utilities for Win32の中のmd5sum.exeを使いました。

p.s. スクリプトの貼り付けに失敗していたので修正しました

[ メッセージ編集済み 編集者: cn009 編集日時 2005-09-06 22:27 ]

[ メッセージ編集済み 編集者: cn009 編集日時 2005-09-06 22:32 ]

[ メッセージ編集済み 編集者: cn009 編集日時 2005-09-06 22:39 ]
cn009
ベテラン
会議室デビュー日: 2004/05/13
投稿数: 72
投稿日時: 2005-09-07 19:26
この前のPerlスクリプトはサニタイジングを全くしてないので問題ありすぎですね。

シングルクォートに用心すればいいかとも思いましたが、
windowsのcmd.exeのechoだと、クォートされていてもイロイロ起こりますね。
シングルクォートはcmd.exeでは意味が無いのでしょうか?

コード:
C:\>echo '| echo hoge'
hoge'

C:\>echo "| echo hoge"
"| echo hoge"

C:\>echo '%windir%'
'C:\WINDOWS'

C:\>echo "%windir%"
"C:\WINDOWS"



サニタイジングは面倒だし、抜けが起こりそうなので、シェルを経由せずにmd5sumを使うようにしてみました。
ついでに改行コードの扱いも変更して、LinuxでもWindowsでも同じハッシュになるようにしました。

mkhashlist.pl
コード:
#!/usr/bin/perl

if ($#ARGV != 2)
{
	print STDERR "usage: mkhashlist.pl datafile hashlist datalist\n\n";
	exit(-1);
}

open(DATAFILE, "<$ARGV[0]")		or die "cannot open $ARGV[0]\n\n";
binmode(DATAFILE);
open(HASHLIST, ">$ARGV[1]")		or die "cannot open $ARGV[1]\n\n";
binmode(HASHLIST);
open(DATALIST, ">$ARGV[2]")		or die "cannot open $ARGV[2]\n\n";
binmode(DATALIST);

while (<DATAFILE>)
{
	if ($_ =~ /^\s*$/){ next;}

	pipe(P_IN_R, P_IN_W);
	pipe(P_OUT_R, P_OUT_W);

	if ($pid = fork){
		close(P_IN_R);
		close(P_OUT_W);

		print P_IN_W "$_";
		close(P_IN_W);

		$rin = "";
		vec($rin, fileno(P_OUT_R), 1) = 1;
		select($rin, undef, undef, undef);

		($hash) = split(/\s/, <P_OUT_R>, 2);
		close(P_OUT_R);
		waitpid($pid, 0);

		print HASHLIST "$hash\n";
		print DATALIST "$hash\t$_";
	}
	else {
		close(P_IN_W);
		close(P_OUT_R);
		open(STDIN, ">&P_IN_R");
		open(STDOUT, ">&P_OUT_W");
		
		exec('md5sum', '-b');
	}
}

close(DATAFILE);
close(HASHLIST);
close(DATALIST);

exit(0);



cmphashlist.pl
コード:
#!/usr/bin/perl

if ($#ARGV != 2)
{
	printf STDERR "usage: cmphashlist.pl hashlist datalist outputfile\n\n";
	exit(-1);
}

open(DATALIST, "<$ARGV[1]")		or die "cannot open $ARGV[1]\n\n";
binmode(DATALIST);
@datalist = <DATALIST>;
close(DATALIST);

open(HASHLIST, "<$ARGV[0]")		or die "cannot open $ARGV[0]\n\n";
binmode(HASHLIST);
open(OUTFILE, ">$ARGV[2]")		or die "cannot open $ARGV[2]\n\n";
binmode(OUTFILE);

while (<HASHLIST>)
{
	($hash) = split(/\s/, $_, 2);
	@tmp = grep(/^$hash\t/, @datalist);
	foreach (@tmp)
	{
		(undef, $data) = split(/\t/, $_, 2);
		print OUTFILE "$data";
	}
}
close(HASHLIST);
close(OUTFILE);
		
exit(0);



もうシンプルとはいえないコードになってしまいました。
angel
ぬし
会議室デビュー日: 2005/03/17
投稿数: 711
投稿日時: 2005-09-07 23:38
こんばんは。

…えーと、Perlであれば、Digest::SHA1というモジュールがあります。( Windows でも Active Perl で使えるようです )
それを使えば、シンプルにいけそうな気がするのですが…。

以下、csv ではなく、1行1データの単純なファイルを読み込み、各行のデータのハッシュ値を出力する例です。
プログラムの引数として、対象のファイル名を指定します。
コード:
use Digest::SHA1 qw(sha1_hex);

while ( <> )
{
chomp;
print sha1_hex($_), "\n";
}



もしくは、ワンライナーで
コード:
perl -pnM'Digest::SHA1 qw(sha1_hex)' -e 'chomp;$_=sha1_hex($_)."\n";' ファイル名



※類似で md5 のモジュールもあります。

以上、ご参考まで。

[ メッセージ編集済み 編集者: angel 編集日時 2005-09-07 23:47 ]
cn009
ベテラン
会議室デビュー日: 2004/05/13
投稿数: 72
投稿日時: 2005-09-08 01:18
Digest::SHA1というのもあるのですね。勉強になります。
Digest::MD5はあるのは知っていましたが、使ったことはありませんでした。
私のマシンのActivePerlには両方ともありましたが、これって標準ライブラリでしたっけ?

Digest::SHA1やDigest::MD5を使うと、シェルのサニタイジングとか考えなくて済みますし、かなりシンプルになりますね。

ただ、1回目の投稿で伝えたかったのは、外部コマンドを使ったものであれば
ちょっとしたスクリプトでも目的を果たせますね、ということだったんです。
だから言語依存のライブラリを使いたくなかったというのもあります。
結局サニタイジングとかを考えるとあまりシンプルではなくなりましたが。

# 2回目の投稿のスクリプトはデータの各行のハッシュの計算というより、
# ActivePerlでcmd.exeを経由せずに外部コマンドを利用するサンプルかもしれませんね

##「open(HOGE, '|-') or exec 'md5sum', '-b';」とかだと、Windowsでは使えませんでした

サニタイジング or 直接サブプロセス起動以外の処理は、ハッシュの計算と
ハッシュの一致する行の検索がメインのつもりですが、どうでしょうか?
初めから日本語で説明した方が良かった気もしますが、巧く伝えられる自信が無いです。
# やっぱり説明力が不足しているのだろうなぁ

AさんはCSVファイルAから各行のハッシュのリストを作成してBさんに渡します。
BさんはCSVファイルBから各行のハッシュを計算し、ハッシュを各行のデータと対応付けたものを用意します。
BさんはAさんから貰ったハッシュリストを読み、自分の作成した
ハッシュと各行のデータを対応付けた表からハッシュの一致するものを探し、
その行のデータを出力したものを得ます。
これが、AさんとBさんの両方が共に持っているデータ(の行)ということになります。

話がタイトルからずれますが、
引用:

perl -pnM'Digest::SHA1 qw(sha1_hex)' -e 'chomp;$_=sha1_hex($_)."\n";' ファイル名


というのはcme.exeでは
 perl -pnM"Digest::SHA1 qw(sha1_hex)" -e "chomp;$_=sha1_hex($_).qq(\n);" ファイル名
としないとエラーになるんですよね。
WindowsでPerlのワンライナーを使うときに結構不便に感じています。
1

スキルアップ/キャリアアップ(JOB@IT)