PHP
md5

md5と同程度の衝突耐性でもうちょっと短い文字列を得る

表題のphpコードです。

md5は0-9a-fの16記号で生成されるのを、0-9a-zA-Zの62記号を使ってもっと短くします。

全角文字とか使えばもっと短くできます。

    function short_md5($string, $characters)

{
$characters = preg_split('//u', $characters, -1, PREG_SPLIT_NO_EMPTY);
$base = sizeof($characters);

$md5 = md5($string);
$md5s = str_split($md5, 8); //巨大すぎるので8桁4パーツに分ける。これにより完全な進数変換にはならない
krsort($md5s);

$reminders = [];
foreach ($md5s as $md5) {

$hex = eval("return 0x{$md5};");

while ($hex > $base) {
$reminder = $hex % $base;
$hex = ($hex - $reminder) / $base;
$reminders[] = $reminder;
}
$reminders[] = $hex;
}

krsort($reminders);
$ret = '';

foreach($reminders as $r){
$ret .= $characters[$r];
}

return $ret;
}

使ってみます。

$str = 'abc';

echo md5($str);
//-> 900150983cd24fb0d6963f7d28e17f72

echo short_md5($str, '0123456789abcdef'); //16進数
//-> 900150983cd24fb0d6963f7d28e17f72 (32文字 結果は一緒)

echo short_md5($str, '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'); //62進数
//-> 2DvjkY173yNi3VDWUdKpPiO (23文字)

echo short_md5($str, '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ-_'); //64進数
//-> 2g0l2oYQA-M3mBzZZEUnZO (22文字)

echo short_md5($str, '亜..(省略)..腕'); //常用漢字全部 1994進数
//-> 江段析課段拠処小踊滑食恨 (12文字)


結論


  • 進数変換時に8桁で分割しちゃってるので擬似的だが、md5と同等の衝突耐性が得られてるっぽい

  • bcmathを使えば、衝突耐性は完全にいっしょにできるはず

  • md5の32文字を半分の16文字にするだけでも0xf * 0xf =256進数にする必要があり、それだけの記号が必要。同等の衝突耐性で文字数を減らすのは結構大変