Entries

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
この記事にトラックバックする(FC2ブログユーザー)
http://ysrken.blog.fc2.com/tb.php/31-8536d15b

トラックバック

コメント

[C23] 山村正和のコメント

すごいですね!
  • 2012-11-29 07:27
  • 山村正和
  • URL
  • 編集

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

自力で12桁トリップを計算してみる

○そもそもトリップって?
 2ちゃんねるなどの掲示板では、成りすましを防止するための仕組みが存在します。『一人用キャップ(通称トリップ)』はそのうちの一つです。
 具体的には、名前欄に「#」を入力すると、その文字以降が一方向性関数によって自動的に変換されます。2ちゃんねるの場合、「#」以降の文字列長が
  1~11バイト→10桁トリップ (使用されるのは先頭8バイトのみ)
  12~1024バイト→12桁トリップ (全てのバイトを使用)
となります。

 変換例:
  「トリップ1#test」→「トリップ1◆.CzKQna1OU」
  「トリップ2#testtesttest」→「トリップ2◆AHGHfSCmXALZ」


○計算アルゴリズム(Perl)
 ・10桁の場合

$tripkey = "hogehoge"; # ←トリップキー
$salt = substr($tripkey.'H.',1,2);
$salt =~ s/[^\.-z]/\./go;
$salt =~ tr/:;<=>?@[\\]^_`/ABCDEFGabcdef/;
$trip = substr(crypt($tripkey,$salt),-10);
print "◆$trip";

 ・12桁の場合

use Digest::SHA1 qw( sha1_base64 );
$tripkey = "hogehogehoge"; # ←トリップキー
$trip = substr( sha1_base64( $tripkey ), 0, 12 );
$trip =~ tr/+/./;
print "◆$trip";



○計算速度
 一方向性関数(だと考えられていた)ので、トリップにある特定の文字列を出したい場合、ブルートフォース式(シラミ潰し)に探すしかありません。最初の頃は毎秒数十万個ほどが限界でしたが、最近では毎秒三十億個計算することも可能になりました。アルゴリズムの都合上、12桁トリップの方が速度が出やすいので、今後は12桁が主流になっていく事でしょう。

○実装
 今回は、12桁トリップの方を、HSPで計算してみることにしました。まあ、Win32APIを叩いてもとりあえず作れるのですが、練習にもなるので、HSPの基本機能のみでフルスクラッチしてみることにしました。最初、HSPにunsigned long相当ないじゃんオワタwwwとか思っていたのですが、試してみると普通に32bit使えた(C言語でのlong型と思いねぇ)ので、それほど難しくはありませんでした。
 ただ、HSPは算術シフトなので、巡回シフトを実装する際はよく気をつける必要があります。私の場合、前もってフィルタを作成して論理演算することで対処しました。

 ここで、自分が書いたコードを公開します。参考になるでしょうか?
 Base64を計算するコード
 SHA-1ハッシュを計算するコード
 12桁トリップを計算するコード(Win32API利用)
 12桁トリップを計算するコード(HSP3基本機能のみ)

 ……ちなみに、私の環境の場合、API版は6264[trip/s]、上にあるフルスクラッチコードで1992[trip/s]、それを自力で最適化させたコードで3536[trip/s]出せました。ええ、遅いですとも。
関連記事
スポンサーサイト
この記事にトラックバックする(FC2ブログユーザー)
http://ysrken.blog.fc2.com/tb.php/31-8536d15b

トラックバック

コメント

[C23] 山村正和のコメント

すごいですね!
  • 2012-11-29 07:27
  • 山村正和
  • URL
  • 編集

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

Appendix

プロフィール

YSR

Author:YSR
「YSR」「YSRKEN」「◆YSRKENkO6Y(~2013/08/25)」「◆YSRKEN.ceVZZ(2013/08/26~)」として活動しています。
プログラミングと艦これが趣味です。
プロフ画像はCrystalDiskInfoの水晶雫ちゃんです。
主な創作物についてはhttp://ysrken.blog.fc2.com/blog-entry-76.htmlをご覧ください。

カレンダー(月別)

06 ≪│2017/07│≫ 08
- - - - - - 1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31 - - - - -

全記事表示リンク

全ての記事を表示する

QRコード

QR

総アクセス数

アクセス数

現在の閲覧者数:
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。