使用硬币和杯子生成加密安全的随机数

通常，生成您自己的随机性是一个坏主意。无论您是从大脑中随机抽取事物，还是使用硬币等物理设备，都可能会引入某种形式的偏见和可预测性，这会大大降低您需要随机性的任何内容（例如密码短语或比特币种子）的安全性）。

但是事实证明，有一些巧妙的数学技巧可以使我们仅使用一些硬币，杯子，铅笔和纸来生成加密等级的随机数。整个过程非常简单，八岁的孩子就可以成功完成任务。

在开始我的技术之前，我想介绍一种叫做“冯·诺伊曼技巧”的东西，这是一种用来将有偏见的硬币变成公平的硬币的策略。技巧很简单：掷硬币两次。如果出现正面或反面，则丢弃结果并重新开始。如果是正面朝上，则将结果接受为“正面”。如果是尾巴，则将结果接受为“尾巴”。

快速证明：达到正面的概率为p²。产生尾巴的概率为（1-p）²。获得正面的概率为p *（1-p），获得正面的概率为（1-p）* p。对于所有'p'值，即使'heads-heads'的概率可能与'tails-heads'的概率显着不同，'heads-tails'的概率与'tails-heads'的概率相同。尾巴。

尽管从数学上讲是纯净的，但这种技巧在现实世界中是不足的。诀窍取决于硬币翻转，每个翻转的偏差都完全相同，也取决于硬币翻转是完全独立的。然而，在现实世界中，硬币正面朝上的概率不仅取决于硬币本身的功能，还取决于环境和掷硬币的人的功能。偏差可能不是一成不变的，硬币翻转可能也不是独立的。

举一个退化的例子，想象一个人抛硬币，随着时间的推移，拇指会累了，最终他们以某种模式结束，这种模式几乎总是导致硬币在空中精确地翻转3次，使得最终的翻转模式为正-头-尾巴等在这种情况下，使用冯·诺依曼（Von Neumann）技巧生成一个较大的随机数不会产生加密安全的随机数，而是会得到结果“ heads-heads-heads-heads-etc”。

如果我们想手工生成安全的密码，我们需要一种既能稳定偏差又能稳定硬币翻转相关性/模式的技术。

我们要做的是取5个硬币，最好是所有形状和大小都不同的硬币，并将它们放入一个大杯子中。您希望杯子很大，以便在摇动硬币时，硬币会以高度随机的方式混杂。给杯子5个良好的摇动，让硬币在周围翻滚，然后将硬币倒出并计数头数。如果磁头数为偶数，则将随机位记录为“ 0”。如果磁头的数量为奇数，则为随机位记录一个“ 1”。

密码安全随机数的长度至少应为128位，这意味着我们将必须执行128次。从那里，我们可以将128位转换为更人性化的东西，例如比特币种子或密码短语。我将在标题为“从比特串到比特币种子短语”的部分中对此进行说明。

我使用龙卷风技术生成了16个随机位，并得到以下结果：

1 1 1 1 0 0 1 0 0 1 0 1 1 0 1 1

跆拳道龙卷风所做的第一件事是，我们每位使用5个硬币，而不是每位使用1个硬币。生成随机数时，我们要收集的基本信息是熵。 5个硬币比1个硬币产生的熵要多得多，这使我们有更好的机会获得公正的结果。

我们要做的第二件事是将所有硬币倒入一个大杯子中。这为硬币创造了一个混乱的环境，在这些环境中，它们将以随机的方式相互反弹，并通常减少了人类一致性的影响。如果您连续多次抛硬币，则随着练习的进行，您很可能会开始以一致的方式抛硬币，不仅会给您的抛硬币带来偏差，而且会引起抛硬币之间的相关性，这对随机性非常不利。当使用诸如摇动杯子之类的湍流技术时，人类产生一致或相关结果的可能性要小得多。

第三，我们计算出杯子的明显摇动次数。实际数字并不重要，关键是您选择一个较大的数字并坚持下去。如果您不进行大量摇动，则主要的风险是您会变得懒惰，并且每次试验仅摇动杯子几次，从而无法在结果中引入熵。延迟摇动会大大降低生成的随机数的安全性。

将硬币从杯子中倒出后，我们需要某种方法来收集熵并将其组合为一个模拟的抛硬币。我们将使用模块化算法来做到这一点，它具有保留熵的特性。

碰巧的是，确定磁头的总数是偶数还是奇数是模块化算法。当我们说“头数是偶数”时，我们实际上是在说“ mod 2的头数等于零”。

当我们说“熵保留”时，我们的意思是，当我们组合多个结果时，随机性的总量只会增加。因此，例如，如果其中一个硬币已经完全无偏，则意味着将该硬币与所有其他硬币组合在一起的结果也将完全无偏，无论其他硬币有多坏或无随机性！

这也意味着当将两个有偏向的硬币组合在一起时，结果将模拟第三个比任何一个原始硬币具有更小的偏向的硬币。实际上，随着您增加组合在一起的物理硬币数量，模拟硬币中的偏差量呈指数下降。通过使用5个硬币，我们确保即使每个单独的硬币都有很高的偏差，模拟的硬币仍将具有很强的随机性。

这种组合熵的方法还可以巧妙地处理相关的硬币翻转。由于我们的方法并不关心将硬币添加到什么顺序，因此硬币之间的任何相关性都有效地降低了附加偏差。相关的硬币翻转是可预测的，因此对随机性的贡献不大，但是它们也不会干扰其他硬币产生的熵，并且不会导致退化的情况，例如使用Von时可能发生的情况诺伊曼的把戏。

*这是假设其他硬币不知道无偏硬币的结果。如果您的有感知力的硬币知道所有其他硬币的状态，并且可能在最后一秒以恶意方式翻转自身，则龙卷风将无法产生随机性。幸运的是，就我们所知，硬币不是以这种方式感知的。

如果我们知道每次抛硬币会引入多少随机性或偏差，我们就可以计算出最终结果中存在多少偏差。实际上，我们不知道每次抛硬币的确切偏差和依赖性，但是我们可以对它们在最坏情况下的严重程度做出一些合理的假设，然后使用该假设来计算最终结果的随机性下限。

当使用模块化算术来组合硬币的结果时，确定结果偏差的公式是取每个硬币“与未浸蚀的距离”的乘积两倍，然后将其乘以0.5。

举例来说，假设有2个硬币的偏差为75％。每个硬币的“无偏距离”为0.25。对于每个硬币，我们将其加倍以得到0.5，然后将它们相乘得到0.125。最后，我们加0.5得到62.5％。完整的等式为（0.5 +（2 * 0.25）*（2 * 0.25））= 62.5％。

再举一个例子，让我们以偏差为60％，70％和80％的3个硬币为例。使用模块化加法来组合这些硬币翻转的方程式为（0.5 +（2 * 0.1）*（2 * 0.2）*（2 * 0.3））=模拟硬币偏差为54.8％。

在我自己的实验中，似乎每个硬币的偏差最多为55％。这意味着合并5个硬币的偏差为50.001％，几乎是完美的。

我们产生安全随机性的主要原因是为了保护自己免受试图猜测我们机密的攻击者的侵害。而且，我们可以使用称为Shannon熵的数学概念来确定攻击者正确猜测的难度。

随机事件的香农熵可以通过将每个结果的概率通过等式p * log2（1 / p）求和并将结果加在一起来计算。在一个完全公平的硬币的示例中，我们将正面概率的香农熵与反面概率的香农熵相加，以得到公平硬币产生的熵的总量：0.5 * log2（1 / 0.5）+ 0.5 * log2（1 / 0.5）=1。一个完全公平的硬币每次掷硬币会产生1位熵。偏差为75％的硬币产生的公式为0.75 * log2（1 / 0.75）+ 0.25 * log2（1 / 0.25）=每次硬币翻转约〜0.811位熵。

假设硬币翻转之间完全独立，我们可以简单地将每个硬币翻转的位相加，以计算总熵。因此，如果我们使用偏差为75％的硬币来创建128位的“随机”数，那么熵的总量实际上为0.811 * 128 =〜103.8位的熵。如果抛硬币不是独立的，我们可以将相关性转换为附加偏差。因此，例如，如果翻转之间的相关性意味着有效偏差为85％，则来自128个硬币翻转的总熵为〜78位熵。

当我们说一个随机数具有78位熵时，我们真正的意思是，攻击者有2分之三的机会猜测随机数。如果我们使用随机数来创建比特币种子，那么拥有非常快的超级计算机的攻击者每秒可能会猜2次，这意味着攻击者可以在5分钟内猜出我们的比特币种子。在密码术中，我们通常认为数字具有128位的熵是安全的，尽管这在某种程度上是任意的，实际上120位以上的任何事物都是非常安全的。

如果我们将此数学应用于龙卷风，并假设每个龙卷风试验的总偏差为53.125％（将5个硬币各占75％的偏差相结合的结果），则最终128位数字中的熵总量将不断增加是〜127.6位。尽管硬币不完美，但最终的随机数却几乎是完美的。即使我们假设龙卷风中的各个硬币的偏差为85％，我们在最终随机数中仍会获得约117.3位的熵，对于大多数人来说，这是绰绰有余的。

有时人们在检查随机数时会犯错误。第二次世界大战的一个著名故事是，由于操作员“看上去”不够随机，他们正在手动调整机器产生的随机数。有时会连续出现多个相同数字的长字符串，并且运算符会通过插入一些看起来更随机的变量来“修复”这些出现。

我无法弄清楚那个故事是否属实，但它可以说明一个问题：真正的随机性有时不能“足够”随机。如果生成长度为128位的随机字符串，则很有可能会找到零或至少8个长度的游程，而找到15个或更长的游程并不常见，但仍然很有可能且并非如此要担心的事情。

（可选）我们可以使用骰子代替硬币。如果可能的话，这实际上是优选的，因为骰子比硬币更混乱，并且通常更不受人类可能引入的一致性和相关性的影响。为了使硬币从一种结果变为另一种，它需要旋转整整180度，并且这种旋转必须沿右轴进行。对于6面模具来说，更改值只需旋转90度即可，并且该旋转可以沿任何轴发生。骰子更好的随机性是您在赌场看到骰子的主要原因之一，但通常不会在赌场看到硬币翻转。

您可以执行相同的模块化算术来组合掷骰子的结果，而掷骰子的结果将用于组合硬币掷的结果。当您投掷多个骰子时，将这些值相加，如果和为偶数，则将结果计数为“ 0”，如果和为奇数，则将结果计数为“ 1”。

如果我们愿意使用计算机来帮助我们得出随机数，那么我们可以做得更好。从香农熵中我们知道，2个偏差为75％的硬币各自具有0.811位的熵。总共，这意味着最多可以从这两次掷硬币中提取1.622位熵。利用我们的模块化加法，我们能够模拟偏差为62.5％的硬币，从而使我们能够提取约0.954位的熵。

我们可以通过将抛硬币的结果输入到安全的哈希函数（如sha256）中来提取全部熵。应该注意的是，为了提取全部熵，您还需要记录哪个硬币产生了哪个结果，这意味着您需要能够在扔硬币后将它们分开。例如，如果一个硬币是一分钱，另一个硬币是镍，则可以通过将诸如“ pH-nT”之类的字符串输入到sha256中来提取这两个抛物的全部熵。结果输出将具有完整的1.622位随机性。

如果您多次抛硬币，则可以使用“ pH-nT：pH-nH：pT-nH”之类的字符串来表示所有试验。生成的哈希函数将一直具有越来越多的熵，直到达到256位的上限为止，这是sha256可以产生的最大熵量。

如果我们愿意将摄像机混入我们的设置中，则每次抛硬币可以提取更多的熵。我们可以扔硬币，然后给它们照相。在图片中，我们不仅将捕获抛硬币的结果，还将捕获硬币的物理位置，其本身是随机的并增加了熵。而且，从拍摄照片的角度，房间的光线等方面，我们甚至可以得到更多的熵，而且由于摄像头传感器的不完善，我们甚至可以从噪声/模糊之类的事物中获得熵的提升。

最好的部分是，我们不需要任何幻想的算法即可提取所有这些熵。我们可以将整个图像放入sha256中，哈希函数会自动吸收图片的全部熵，包括我们甚至不知道的熵源。实际上，仅拍摄一张空白墙的图片很可能会产生超过128位的熵，因此硬币的纪念性超过了所需。

有人可能想手工生成比特币种子的原因是因为他们不信任计算机。这种不信任来自我们在本博文前面提到的一个主要警告：只有在系统中没有感觉时，组合熵的来源才是安全的。对于计算机而言，恶意软件和/或开发人员的无能代表了潜在的情感，可能破坏您的随机数并给您带来不安全的比特币种子。

如果我们使用的是摄像头，则摄像头中的某些恶意元素理论上可​​能会在拍摄后修改图像，从而在此处或此处添加一些噪点，从而破坏结果并确保最终图像具有可预测的sha256哈希。

另一个攻击媒介可能是计算出不正确的sha256哈希的恶意软件。由于我们无法通过手工或头脑来验证对图像进行哈希处理的结果，因此我们必须信任计算机提供给我们的输出，并且可能会撒满被恶意软件感染的计算机，以便我们使用不安全的种子。

实际上，您可能会认为在密钥生成设置中存在此类恶意软件的可能性很小，并且您可能是对的。手工做事的许多优势归结为乐趣和学习。

至此，我们已经生成了一个安全的128位字符串，由1和0组成，现在我们需要将其转换为实际可用的密码。比特币种子短语是将位串转换为人类友好的一组单词的最简单方法之一。

您需要做的第一件事是将您的位串分成每个11位大的片段。您将得到11个字符串，每个字符串长11位，最后有1个字符串，只有7位长。为了简洁起见，我将使用一个18位长的示例-一串11，一串7：

1 1 1 1 0 0 1 0 0 1 0 :::: 1 1 0 1 1 1 0

要将这些位串转换为种子词，我们将需要做一些数学运算，并使用此查找表。我们将以二进制形式查看位串，并将其转换为数字，然后为该数字查找相应的单词。对于最后一个词，我们需要做一些特别的事情，我们将在后面解释。

对于前11个位串，我们可以通过将与1对应的值相加来将它们转换为二进制。位串中的第一个数字为“ 1024”，其后的每个数字为前一个数字的一​​半。下表显示了我的字符串和与每个数字相对应的值：

1 1 1 1 0 0 1 0 0 1 0 | | | | | | | | | | | 1024 512 256 128 64 32 16 8 4 2 1

由于我们忽略了零，因此我的字符串将为1024 + 512 + 256 + 128 + 16 + 2 =1938。然后，由于查找表将列表从“ 1”而不是“ 0”开始，因此我们将需要在我们的号码上加1以纠正查找表的对齐方式。所以我的最终数字是“ 1939”，它对应于“冒险”一词。

最终的位串只有7位，因为其余的4位是校验和。如果您不关心校验和，则可以假装其余4位为“ 0”，并使用上述方法查找相应的字。这不会影响密码短语的整体安全性。

如果您特别想制作有效的比特币种子，则需要计算校验和。不幸的是，校验和是使用sha256计算的，这很难手动完成。值得庆幸的是，校验和只有16种可能的选择，因此实际上可以尝试所有16种选择，然后等到您的钱包接受其中一种。为了找出要使用的16个字，我们进行了相同的处理，只是将最后4位保留为空。

1 1 0 1 1 1 0：----| | | | | | | | | | | 1024 512 256 128 64 32 16：----

对于我的校验和字，值是1024 + 512 + 128 + 64 + 32 =1760。然后我们必须加1以说明表的对齐方式，所以我的最终数字是'1761'，而我可能的字集是16以'swing'开头的单词。可以保证，以swing开头的16个单词中的一个恰好会产生有效的比特币种子。您可以将每个尝试的种子提供给离线比特币钱包，然后使用钱包接受的任何种子作为您真正的比特币种子。

用机器验证的校验和结束这一旅程并不令我满意，所以我走了很长一段距离，还创建了一种校验和算法，该算法既有用又可以轻松地手动计算。此校验和的最大挑战是任何钱包都不支持它，因此纯粹是为了娱乐。

如果有任何钱包希望在种子短语中支持此校验和，则它们将需要能够区分使用sha256校验的种子和使用人类友好方法校验的种子。我建议使用人类可计算校验和（可以称为Taek4）的种子在种子的最后一个词后加上“ -t”。以我的短种子为例，完整的结果将是“冒险人才-t”。

在介绍将用于创建校验和的算法之前，我想介绍一些有助于使校验和有用的属性。 首先，种子短语中的每个单词都应影响我们校验和的每一位。 这样可以确保 ......