PHP 种子、确定性、加密安全 PRNG（伪随机数生成器）。可能吗？

Question

我需要在 PHP 中创建一个可证明公平（确定性和种子）加密安全 (CS) 随机数生成器。我们运行ning PHP 5 和 PHP 7 现在不是一个真正的选择。但是，我找到了 PHP 7 的新 CS 函数的 polyfill，所以我已经实现了该解决方案 (https://github.com/paragonie/random_compat)。

我认为 srand() 可以用来为 random_int() 提供种子，但现在我不确定是否是这样。 CSPRNG 甚至可以播种吗？如果可以播种，输出是否是确定性的（相同的随机结果，给定相同的种子）？

这是我的代码：

require_once($_SERVER['DOCUMENT_ROOT']."/lib/assets/random_compat/lib/random.php");

$seed_a = 8138707157292429635;
$seed_b = 'JuxJ1XLnBKk7gPASR80hJfq5Ey8QWEIc8Bt';

class CSPRNG{
    private static $RNGseed = 0;

    public function generate_seed_a(){
        return random_int(0, PHP_INT_MAX);
    }

    public function generate_seed_b($length = 35){
        $characters = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
        $randomString = '';
        for($i = 0; $i < $length; $i++){
            $randomString .= $characters[random_int(0, strlen($characters) - 1)];
        }
        return $randomString;
    }

    public function seed($s = 0) {
        if($s == 0){
            $this->RNGseed = $this->generate_seed_a();
        }else{
            $this->RNGseed = $s;
        }
        srand($this->RNGseed);
    }

    public function generate_random_integer($min=0, $max=PHP_INT_MAX, $pad_zeros = true){
        if($this->RNGseed == 0){
            $this->seed();
        }
        $rnd_num = random_int($min, $max);
        if($pad_zeros == true){
            $num_digits = strlen((string)$max);
            $format_str = "%0".$num_digits."d";
            return sprintf($format_str, $rnd_num);
        }else{
            return $rnd_num;
        }
    }

    public function drawing_numbers($seed_a, $num_of_balls = 6){
        $this->seed($seed_a);
        $draw_numbers = array();
        for($i = 0; $i < $num_of_balls; $i++) {
            $number = ($this->generate_random_integer(1, 49));
            if(in_array($number, $draw_numbers)){
                $i = $i-1;
            }else{
                array_push($draw_numbers, $number);
            }
        }
        sort($draw_numbers);
        return $draw_numbers;
    }
}

$CSPRNG= new CSPRNG();

echo '<p>Seed A: '.$seed_a.'</p>';
echo '<p>Seed B: '.$seed_b.'</p>';
$hash = hash('sha1', $seed_a.$seed_b);
echo '<p>Hash: '.$hash.'</p>';

$drawNumbers = $CSPRNG->drawing_numbers($seed_a);
$draw_str = implode("-", $drawNumbers);
echo "<br>Drawing: $draw_str<br>";

当此代码为运行时，每个运行上的绘图 ($draw_str) 应该相同，但事实并非如此。

为了证明抽奖的公平性，在中奖号码被选中并显示之前，先选择一个种子（种子A）。还会生成另一个随机数（种子 B）。种子 B 用作盐并与种子 A 结合，结果被散列。此散列在绘图之前显示给用户。他们还将获得源代码，以便在中奖号码被选中时，两个种子都会被显示出来。他们可以验证哈希是否匹配并且一切都公平地完成了。

Answer 1

首先，您不应该实现自己的用户空间 CSPRNG。您安装 PHP 5 的操作系统已经提供了 CSPRNG，您应该使用它来实现所有随机性，除非您知道可以使用它，或者性能是一个问题。您应该使用 random_int()、random_bytes() 或 openssl_random_pseudo_bytes().

但是，如果您必须实现用户空间 CSPRNG，那么这可以通过简单地使用 AES 库（例如：libsodium）和加密计数器来完成。伪代码为：

Uint-128 n = 0;
while true:
    output = AES-ECB(key, n);
    n++;

在这种情况下，他们的 AES 密钥需要足够的熵来抵御复杂的攻击，否则您的用户空间 CSPRNG 的安全性当然会崩溃。密钥可以是用户提供的密码的 bcrypt()。

假设以 128 位无符号整数表示的计数器始终是唯一的，每次生成器 "seeded" 使用新计数器时，您将始终获得唯一的输出。如果它使用以前使用的计数器作为种子，但使用不同的密钥，那么输出也会不同。最好的情况是每次调用生成器时更改密钥和更改计数器。

您可能想在计数器中使用高精度时间戳，例如使用微秒精度。这很好，除了你运行某人或某物操纵系统时钟的风险。因此，如果时钟可以被操纵，那么 CSPRNG 生成器就可以被破坏。最好在每次调用生成器时提供一个新密钥，并使用 128 位零开始加密。

另外，请注意我们使用的是带有 AES 的 ECB 模式。不要惊慌失措。 ECB 在维护明文提供的密文结构方面存在问题。一般而言，您不应使用 ECB 模式。然而，对于 128 位的数据，您只会加密单个 ECB 块，因此不会有结构化数据的泄漏。对于用户空间 CSPRNG，ECB 优于 CTR，因为您不必跟踪密钥、计数器对象和要加密的数据。只需要一个密钥和数据。只要确保您永远不会加密超过 128 位的数据，并且您永远不会需要超过 1 个块。

Can a CSPRNG even be seeded?

是的，它应该始终被播种。如果您查看 GNU/Linux 操作系统，您可能会注意到 /var/lib/urandom/random-seed 中的一个文件。当操作系统关闭时，它会从 CSPRNG 创建该文件。在下次启动时，此文件用于为内核空间 CSPRNG 播种，以防止重复使用生成器的先前状态。每次关机时，该文件都应该更改。

If it can be seeded, will the output be deterministic (same random result, given same seed)?

是的。提供相同的种子、密钥等，输出是确定性的，因此输出将是相同的。如果您的变量之一发生变化，则输出将不同。这就是为什么每次调用生成器时都应该重新输入密钥。

Answer 2

Duskwuff 问：

How do you intend to prove that the seed was chosen fairly? A suspicious user can easily claim that you picked a seed that would result in a favorable outcome for specific users, or that you revealed the seed to specific users ahead of time.

在调查解决方案之前，您要解决的问题到底是什么？您的威胁模型是什么？

听起来你想要SeedSpring (version 0.3.0 supports PHP 5.6)。

$prng = new \ParagonIE\SeedSpring\SeedSpring('JuxJ1XLnBKk7gPAS');
$byte = $prng->getBytes(16);
\var_dump(bin2hex($byte));

这应该总是 return:

string(32) "76482c186f7c5d1cb3f895e044e3c649"

这些数字应该是公正的，但由于它基于预先共享的种子，因此根据严格的定义，它不是密码安全的。

请记住，SeedSpring 是作为概念玩具 implementation/proof 创建的，而不是 Paragon Initiative Enterprises 官方开源安全解决方案，因此请随意分叉并调整它以适合您的目的。（我怀疑我们的分支会达到 "stable 1.0.0 release"）。

（此外，如果您要 accept/award 悬赏这些答案中的任何一个，Aaron Toponce 的答案更正确。使用 ECB 模式加密随机数比加密一长串 NUL 的性能更高具有 AES-CTR 的字节，以获得大致相同的安全优势。这是 ECB 模式正常的极少数情况之一。)

PHP 种子、确定性、加密安全 PRNG（伪随机数生成器）。可能吗？

PHP Seeded, Deterministic, Cryptographically Secure PRNG (PseudoRandom Number Generator). Is it possible?

php

security

random

cryptography

numbers