计算PHP中各种随机函数的香农熵

calc-shannon-entropy.php

<?php
/**
 * 计算PHP中各种随机函数的香农熵
 */

define('DATA_MAX_BITS', 1 * 1024);
define('DATA_MAX_BYTES', DATA_MAX_BITS / 8);
define('TEST_TIMES', 100);

/**
 * Calc the average of an array
 * @param $arr array<int|float>
 * @return float|int
 */
function avg($arr)
{
    return array_sum($arr) / count($arr);
}


/**
 * calc the shannon entropy of the given data
 * @param $data string
 * @return float|int
 */
function calc_entropy($data)
{
    $dataLen = strlen($data);

    // H(X) = E[I(X)] = E[-ln(P(X))]
    // H(X) = SUM(P(x) * I(x)) = - SUM(P(x) * log(P(x), 2))        (in bits)


    // the count of each byte
    $bytesCount = array_fill(0, 256, 0);

    for ($i = 0; $i < $dataLen; $i++){
        $b = ord($data[$i]);
        $bytesCount[$b] = $bytesCount[$b] + 1;
    }

    // calc P(x)
    $bytesPossibilities = [];
    for ($b = 0; $b < 256; $b++) {
        $bytesPossibilities[$b] = $bytesCount[$b] / $dataLen;
    }

//    var_dump($bytesPossibilities);die;

    $h = 0;
    foreach ($bytesPossibilities as $b => $px) {
        if ($px > 0){
            $h += $px * log($px, 2);
        }
    }

    return -$h;
}


$dataSet = [
    'rand' => function(){
        srand(time());

        $randMax = getrandmax();
        $bytes = [];

        for ($i = 0; $i < DATA_MAX_BYTES; $i++){
            $x = rand();
            for ($j = $randMax; $i < DATA_MAX_BYTES && $j & 0xff === 0xff; $j >>= 8, $i++){
                $bytes[] = chr($x & 0xff);
            }
        }

        return implode($bytes);
    },
    'mt_rand' => function(){
        mt_srand(time());

        $randMax = mt_getrandmax();
        $bytes = [];

        for ($i = 0; $i < DATA_MAX_BYTES; $i++){
            $x = rand();
            for ($j = $randMax; $i < DATA_MAX_BYTES && $j & 0xff === 0xff; $j >>= 8, $i++){
                $bytes[] = chr($x & 0xff);
            }
        }

        return implode($bytes);
    },
    'random_bytes' => function(){
        return random_bytes(DATA_MAX_BYTES);
    },
    'openssl_random_pseudo_bytes' => function(){
        return openssl_random_pseudo_bytes(DATA_MAX_BYTES);
    },
    'mcrypt_create_iv(n, MCRYPT_RAND)' => function(){
        return mcrypt_create_iv(DATA_MAX_BYTES, MCRYPT_RAND);
    },
    'mcrypt_create_iv(n, MCRYPT_DEV_RANDOM)' => function(){
        return mcrypt_create_iv(DATA_MAX_BYTES, MCRYPT_DEV_RANDOM);
    },
    'mcrypt_create_iv(n, MCRYPT_DEV_URANDOM)' => function(){
        return mcrypt_create_iv(DATA_MAX_BYTES, MCRYPT_DEV_URANDOM);
    },
];

$results = [];

foreach ($dataSet as $algo => $genData) {
    // 忽略第一次（预热）
    $genData();

    $algoResult = [
        'name' => $algo,
        'time' => [],
        'entropy' => [],
    ];

    for ($i = 0; $i < TEST_TIMES; $i++){
        $beginTime = microtime(true);

        $data = $genData();

        $algoResult['time'][] = microtime(true) - $beginTime;
        $algoResult['entropy'][] = calc_entropy($data);
    }

    $algoResult['maxTime'] = max($algoResult['time']);
    $algoResult['minTime'] = min($algoResult['time']);
    $algoResult['avgTime'] = avg($algoResult['time']);

    $algoResult['maxEntropy'] = max($algoResult['entropy']);
    $algoResult['minEntropy'] = min($algoResult['entropy']);
    $algoResult['avgEntropy'] = avg($algoResult['entropy']);

    $results[] = $algoResult;
}


echo sprintf("%-40s %10s %10s %10s %10s %10s %10s\n", 'Algo', 'AvgEnt', 'MinEnt', 'MaxEnt', 'AvgTime', 'MinTime', 'MaxTime');

foreach ($results as $ar) {
    echo sprintf("%-40s %10.3f %10.3f %10.3f %10.6f %10.6f %10.6f\n",
        $ar['name'],
        round($ar['avgEntropy'], 3), round($ar['minEntropy'], 3), round($ar['maxEntropy'], 3),
        round($ar['avgTime'] * 1000, 3), round($ar['minTime'] * 1000, 3), round($ar['maxTime'] * 1000, 3));
}

echo "Note1: `xxxEnt` means shannon entropy in bits.\n";
echo "Note2: `xxxTime` means the time to generate the random bytes, in milliseconds.\n";
echo "Note3: " . DATA_MAX_BITS . " random bits generated each time. Every algo tested " . TEST_TIMES . " times.\n";

results.txt

==========================================================================================================
1k:
==========================================================================================================
[root@f4d5945f1d7c tools]# php calc-shannon-entropy.php                                                      
Algo                                         AvgEnt     MinEnt     MaxEnt    AvgTime    MinTime    MaxTime   
rand                                          4.621      4.621      4.621   0.010000   0.009000   0.019000   
mt_rand                                       4.621      4.621      4.621   0.010000   0.009000   0.024000   
random_bytes                                  6.537      6.359      6.670   0.002000   0.001000   0.010000   
openssl_random_pseudo_bytes                   6.551      6.390      6.707   0.005000   0.004000   0.014000   
mcrypt_create_iv(n, MCRYPT_RAND)              6.548      6.402      6.691   0.002000   0.001000   0.003000   
mcrypt_create_iv(n, MCRYPT_DEV_RANDOM)        6.557      6.336      6.775   1.821000   0.048000  18.804000   
mcrypt_create_iv(n, MCRYPT_DEV_URANDOM)       6.562      6.412      6.691   0.002000   0.001000   0.012000   
Note1: `xxxEnt` means shannon entropy in bits.                                                               
Note2: `xxxTime` means the time to generate the random bytes, in milliseconds.                               
Note3: 1024 random bits generated each time. Every algo tested 100 times.                 
==========================================================================================================
2k:
==========================================================================================================                   
Algo                                         AvgEnt     MinEnt     MaxEnt    AvgTime    MinTime    MaxTime   
rand                                          5.611      5.611      5.611   0.022000   0.021000   0.026000   
mt_rand                                       5.611      5.611      5.611   0.022000   0.021000   0.059000   
random_bytes                                  7.171      7.061      7.274   0.002000   0.002000   0.003000   
openssl_random_pseudo_bytes                   7.167      7.042      7.304   0.007000   0.006000   0.073000   
mcrypt_create_iv(n, MCRYPT_RAND)              7.171      7.063      7.274   0.004000   0.002000   0.041000   
mcrypt_create_iv(n, MCRYPT_DEV_RANDOM)        7.173      7.049      7.324   9.092000   0.093000  21.971000   
mcrypt_create_iv(n, MCRYPT_DEV_URANDOM)       7.176      7.001      7.262   0.002000   0.002000   0.011000   
Note1: `xxxEnt` means shannon entropy in bits.                                                               
Note2: `xxxTime` means the time to generate the random bytes, in milliseconds.                               
Note3: 2048 random bits generated each time. Every algo tested 100 times.                                    
==========================================================================================================
4k:
==========================================================================================================
Algo                                         AvgEnt     MinEnt     MaxEnt    AvgTime    MinTime    MaxTime   
rand                                          6.318      6.318      6.318   0.040000   0.036000   0.092000   
mt_rand                                       6.318      6.318      6.318   0.038000   0.036000   0.056000   
random_bytes                                  7.589      7.493      7.656   0.003000   0.003000   0.004000   
openssl_random_pseudo_bytes                   7.592      7.512      7.673   0.014000   0.011000   0.161000   
mcrypt_create_iv(n, MCRYPT_RAND)              7.592      7.486      7.670   0.006000   0.005000   0.015000   
mcrypt_create_iv(n, MCRYPT_DEV_RANDOM)        7.589      7.501      7.667  20.011000   0.212000  55.325000   
mcrypt_create_iv(n, MCRYPT_DEV_URANDOM)       7.586      7.508      7.679   0.004000   0.003000   0.013000   
Note1: `xxxEnt` means shannon entropy in bits.                                                               
Note2: `xxxTime` means the time to generate the random bytes, in milliseconds.                               
Note3: 4096 random bits generated each time. Every algo tested 100 times.                                    
==========================================================================================================
8k:
==========================================================================================================
Algo                                         AvgEnt     MinEnt     MaxEnt    AvgTime    MinTime    MaxTime   
rand                                          7.030      7.030      7.030   0.083000   0.073000   0.170000   
mt_rand                                       7.030      7.030      7.030   0.079000   0.069000   0.434000   
random_bytes                                  7.809      7.770      7.847   0.006000   0.005000   0.036000   
openssl_random_pseudo_bytes                   7.807      7.755      7.844   0.022000   0.020000   0.064000   
mcrypt_create_iv(n, MCRYPT_RAND)              7.806      7.774      7.851   0.012000   0.010000   0.042000   
mcrypt_create_iv(n, MCRYPT_DEV_RANDOM)        7.811      7.767      7.856  37.136000  30.348000  65.694000   
mcrypt_create_iv(n, MCRYPT_DEV_URANDOM)       7.809      7.770      7.847   0.006000   0.005000   0.014000   
Note1: `xxxEnt` means shannon entropy in bits.                                                               
Note2: `xxxTime` means the time to generate the random bytes, in milliseconds.                               
Note3: 8192 random bits generated each time. Every algo tested 100 times.                                    
==========================================================================================================
16k:
==========================================================================================================
Algo                                         AvgEnt     MinEnt     MaxEnt    AvgTime    MinTime    MaxTime   
rand                                          7.449      7.449      7.449   0.157000   0.139000   0.340000   
mt_rand                                       7.449      7.449      7.449   0.160000   0.136000   0.311000   
random_bytes                                  7.908      7.891      7.928   0.011000   0.009000   0.045000   
openssl_random_pseudo_bytes                   7.907      7.891      7.923   0.043000   0.038000   0.123000   
mcrypt_create_iv(n, MCRYPT_RAND)              7.905      7.884      7.926   0.026000   0.020000   0.094000   
mcrypt_create_iv(n, MCRYPT_DEV_RANDOM)        7.909      7.889      7.927  42.443000  16.107000 102.861000   
mcrypt_create_iv(n, MCRYPT_DEV_URANDOM)       7.908      7.885      7.930   0.011000   0.009000   0.028000   
Note1: `xxxEnt` means shannon entropy in bits.                                                               
Note2: `xxxTime` means the time to generate the random bytes, in milliseconds.                               
Note3: 16384 random bits generated each time. Every algo tested 100 times.                                   
==========================================================================================================
32k:
==========================================================================================================
Algo                                         AvgEnt     MinEnt     MaxEnt    AvgTime    MinTime    MaxTime   
rand                                          7.778      7.778      7.778   0.243000   0.220000   0.392000   
mt_rand                                       7.778      7.778      7.778   0.278000   0.220000   1.454000   
random_bytes                                  7.955      7.945      7.964   0.020000   0.018000   0.055000   
openssl_random_pseudo_bytes                   7.955      7.946      7.965   0.083000   0.074000   0.458000   
mcrypt_create_iv(n, MCRYPT_RAND)              7.953      7.943      7.963   0.043000   0.040000   0.094000   
mcrypt_create_iv(n, MCRYPT_DEV_RANDOM)        7.955      7.945      7.965  82.432000  33.241000 204.162000   
mcrypt_create_iv(n, MCRYPT_DEV_URANDOM)       7.954      7.941      7.962   0.022000   0.018000   0.072000   
Note1: `xxxEnt` means shannon entropy in bits.                                                               
Note2: `xxxTime` means the time to generate the random bytes, in milliseconds.                               
Note3: 32768 random bits generated each time. Every algo tested 100 times.                                   
==========================================================================================================
64k:
==========================================================================================================
Algo                                         AvgEnt     MinEnt     MaxEnt    AvgTime    MinTime    MaxTime   
rand                                          7.886      7.886      7.886   0.497000   0.453000   0.900000   
mt_rand                                       7.886      7.886      7.886   0.475000   0.441000   0.869000   
random_bytes                                  7.977      7.973      7.982   0.035000   0.035000   0.039000   
openssl_random_pseudo_bytes                   7.978      7.972      7.983   0.149000   0.148000   0.154000   
mcrypt_create_iv(n, MCRYPT_RAND)              7.975      7.968      7.981   0.093000   0.081000   0.572000   
mcrypt_create_iv(n, MCRYPT_DEV_RANDOM)        7.977      7.974      7.981 144.593000  79.811000 370.020000   
mcrypt_create_iv(n, MCRYPT_DEV_URANDOM)       7.978      7.973      7.981   0.039000   0.035000   0.221000   
Note1: `xxxEnt` means shannon entropy in bits.                                                               
Note2: `xxxTime` means the time to generate the random bytes, in milliseconds.                               
Note3: 65536 random bits generated each time. Every algo tested 100 times.                                   
==========================================================================================================
128k:
==========================================================================================================
Algo                                         AvgEnt     MinEnt     MaxEnt    AvgTime    MinTime    MaxTime   
rand                                          7.940      7.938      7.942   0.938000   0.882000   1.346000   
mt_rand                                       7.938      7.938      7.938   0.959000   0.884000   1.364000   
random_bytes                                  7.989      7.986      7.992   0.075000   0.069000   0.153000   
openssl_random_pseudo_bytes                   7.989      7.986      7.991   0.296000   0.294000   0.311000   
mcrypt_create_iv(n, MCRYPT_RAND)              7.987      7.984      7.990   0.163000   0.161000   0.178000   
mcrypt_create_iv(n, MCRYPT_DEV_RANDOM)        7.989      7.987      7.991 265.398000 175.803000 717.382000   
mcrypt_create_iv(n, MCRYPT_DEV_URANDOM)       7.989      7.986      7.991   0.074000   0.070000   0.133000   
Note1: `xxxEnt` means shannon entropy in bits.                                                               
Note2: `xxxTime` means the time to generate the random bytes, in milliseconds.                               
Note3: 131072 random bits generated each time. Every algo tested 100 times.                                  

fix bug: $bytesPossibilities[$b] = $bytesCount[$b] / 256.0; is incorrect! P(x) is the possibility of x, so it should be: $bytesPossibilities[$b] = $bytesCount[$b] / $dataLen;

Conclusion: rand and mt_rand are unsafe. random_bytes and openssl_random_pseudo_bytes is recommended to generate random bytes. mcrypt_create_iv is deprecated in PHP7.1.

Longer is better.