PHP
md5
@puchida

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

PHPmd5

表題の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文字）


結論


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

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

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

Edit request
2