如何生成周期性的、不可预测的、可验证的随机数?

How to generate a periodic, unpredictable, verifiable random number?

提问人:Freddie 提问时间:8/4/2023 最后编辑:Sam MasonFreddie 更新时间:8/5/2023 访问量:102

问:

我想要一个具有以下品质的程序的随机数:

  1. 周期性:随机数需要在某个时间窗口内是随机的。最好每小时一次,但可以更多。一旦周期结束,就可以生成下一个随机数,并且可以根据公开可用的种子值重新生成先前生成的值。

  2. 不可预测:下一个随机数不容易确定。公开可用的种子不得公开。

  3. 可验证:随机数的种子应来自某些公开可用的来源。也许科学研究组织或政府机构正在发布每日或每小时的数字。例如,记录的一组温度。或者,例如,它可以像发布每小时或每天随机数的网站一样简单。

  4. 种子应至少为 64 位整数。如果它太小,那么可以从一个小集合中猜测随机数。

  5. 不需要工业强度或严格的随机性。对极端、高精度的随机性不感兴趣。

我看到 https://avkg.com/ 生成了大量的每日随机数,这实际上非常接近,如果没有其他看起来更好的,我可能会使用它。特别是因为它存档了过去的结果,因此满足了可验证的要求。问题是该网站没有一个干净且有据可查的 API,而且它不是每小时一次。此信息的 HTML 抓取并不理想。

我的另一个想法是使用特定人群的最新推文(X)的哈希值。做这样的事情可以进行验证。问题是我不知道他们是每天还是每小时发推文。此外,Elon 现在已将 Twitter (X) 设置为非公开,因此您需要登录才能收集此信息。

另一个想法是创建一个我自己的AVKG版本。

当然,日期是行不通的,因为这不能满足上述不可预测的要求。

有什么想法吗?

非常感谢。

密码学 随机种子

评论

0赞 President James K. Polk 8/4/2023
所以你最终会在用它来生成随机数后发布种子吗?周期性是必需的,还是仅仅不取消资格?
0赞 Freddie 8/5/2023
是的。世界会在时期开始的那一刻知道种子,但在此之前不会。
0赞 Freddie 8/5/2023
对于第二个问题:是的。周期性是必需的。该应用程序的目的是生成一个周期性随机数,其过去的值可以被验证为随机数。

答:

2赞 Sam Mason 8/5/2023 #1

鉴于您所写的内容,我想我只会在计数器模式下使用对称密码(例如 ChaCha20)来生成请求的数据,并使用 KDF(例如 Argon2)在密钥之间转换。

您的私有状态将是:

  • key此期间使用的私钥
  • salt用于过渡到此键的盐

您的公共状态为:

  • ctr当前计数器值
  • log以前使用的私钥和盐

当有人提出请求时,你会以原子的方式:

  1. 使用 和 生成新的随机数据块,keyctrdata
  2. 响应 , ,i = len(log)ctrdata
  3. 增加ctr

当您进入下一个时期时,您将以原子方式:

  1. 追加 和keysaltlog
  2. 重置为零ctr
  3. 生成 16 个随机字节salt
  4. 使用 KDF 生成一个新的,将其与上一周期的keysaltkey

当用户想要验证他们的 时,他们会:data

  1. 请求公共状态
  2. 验证密钥是否来自并生成其log[i]ctrdata

如果用户想要验证其是否安全生成,他们将:key

  1. 请求公共状态
  2. 验证将 from 与 in 组合在一起是否会生成 inkeylog[i-1]saltlog[i]keylog[i]

用户可以匿名(例如,来自多个不相关的主机)请求公共状态来验证:

  • 这些不会意外改变
  • 在执行数据请求时,这些数据是一致的

评论

0赞 Sam Mason 8/5/2023
您可能希望允许用户在请求中传递某些状态,并在生成 .这样一来,您就可以确信服务器不会对返回的随机值产生重大影响,因为它们无法完全控制密码状态data
0赞 Freddie 8/5/2023
Thank you, Sam. The question I have regarding your solution is how would the public know the key was generated in a "cryptographically secure manner?" Seems this is not really verifiably random?
0赞 Sam Mason 8/5/2023
good point! have defined some key transition function. you'd want to pick a reasonable KDF such that users would know it couldn't be exhaustively evaluated over even a small proportion (e.g. 2^-64) of the key space between periods
0赞 Freddie 8/11/2023
Thanks, Sam. Please correct me if I am wrong, but the "generation" of the "16 random bytes in salt" is server-side? In that case, how could the anonymous user check the public state to verify it was actually randomly chosen instead of made up to suit the server owner's needs?
1赞 Sam Mason 8/11/2023
Because it's being passed through a KDF in a way that can be checked. Basically KDFs, like hashes, are one way functions. I.e. it's easy to go one way, but it's computationally infeasible to go back. So unless the attacker had perfect knowledge of every time users would request state they couldn't predict the output. If you allowed users to pass some state in (like in my first comment) then even that's avoided