加密无序播放和选择

我正在实现一个加密安全的shuffle例程，有几个问题：

我使用的方法是加权排序，其中每个权重都是一个加密的强随机数。

我使用列表(X)中的项目数计算每个权重所需的位数，并将其插入公式=log10(X!) / log10(2)中。例如，52副牌组每重量将需要log10(52!) / log10(2) = 225.58100312370276194634244437667比特。我总是把它四舍五入，因为一位的分数无法表示。我总是四舍五入是正确的，还是这给了我太多的信息？
从硬件rng中检索位可能不太实际，因此必须检索字节。与前面的例子226 / 8 = 28.25一样，我们有28个完整的字节，还有一个额外的字节来获得剩余的2位。我正在做的是丢弃最后一个字节中未使用的高位6位，这样只会在数字后面追加2位。我简单地丢弃这些比特是正确的吗？还是我这样做破坏了熵？
我按照(左填充，全大写，ASCII)分配给每个数字的十六进制权重字符串进行排序。这似乎产生了正确的排序顺序。以这种方式对字符串进行排序是否有我应该注意的问题？
我应该使用一个硬件rng来测试它生成的数字的熵，但我一直在使用MS RNGCryptoServiceProvider。有更好的加密RNG可供使用吗。NET？
要从加密加权和排序列表中"挑选"一个数字，我只需选择索引0。有没有更好的加密随机方法来选择列表中的项目？

让我知道我是否可以帮助澄清，或者如果这是错误的网站，请让我知道什么是更好的网站。

以下是我的代码，如果它有助于说明我所说的VB.NET控制台应用程序：

Imports System.Security.Cryptography
Module Module1
Public Class Ball
Public Weight As String
Public Value As Integer
Public Sub New(ByVal _Weight As String, ByVal _Value As Integer)
Weight = _Weight
Value = _Value
End Sub
End Class
Public Class BallComparer_Weight
Implements IComparer(Of Ball)
Public Function Compare(x As Ball, y As Ball) As Integer Implements System.Collections.Generic.IComparer(Of Ball).Compare
If x.Weight > y.Weight Then
Return 1
ElseIf x.Weight < y.Weight Then
Return -1
Else
Return 0
End If
End Function
End Class
Public Class BallComparer_Value
Implements IComparer(Of Ball)
Public Function Compare(x As Ball, y As Ball) As Integer Implements System.Collections.Generic.IComparer(Of Ball).Compare
If x.Value > y.Value Then
Return 1
ElseIf x.Value < y.Value Then
Return -1
Else
Return 0
End If
End Function
End Class
Public Function Weight(ByVal rng As RNGCryptoServiceProvider, ByVal bits As Integer) As String
' generate a "cryptographically" random string of length 'bits' (should be using hardware rng)
Dim remainder As Integer = bits Mod 8
Dim quotient As Integer = bits  8
Dim byteCount As Integer = quotient + If(remainder <> 0, 1, 0)
Dim bytes() As Byte = New Byte(byteCount - 1) {}
Dim result As String = String.Empty
rng.GetBytes(bytes)
For index As Integer = bytes.Length - 1 To 0 Step -1
If index = bytes.Length - 1 Then
' remove upper `remainder` bits from upper byte
Dim value As Byte = (bytes(0) << remainder) >> remainder
result &= value.ToString("X2")
Else
result &= bytes(index).ToString("X2")
End If
Next
Return result
End Function
Public Function ContainsValue(ByVal lst As List(Of Ball), ByVal value As Integer) As Boolean
For i As Integer = 0 To lst.Count - 1
If lst(i).Value = value Then
Return True
End If
Next
Return False
End Function
Sub Main()
Dim valueComparer As New BallComparer_Value()
Dim weightComparer As New BallComparer_Weight()
Dim picks As New List(Of Ball)
Dim balls As New List(Of Ball)
' number of bits after each "ball" is drawn
Dim bits() As Integer = New Integer() {364, 358, 351, 345, 339}
Using rng As New RNGCryptoServiceProvider
While True
picks.Clear()
' simulate random balls
'log10(75!) / log10(2) = number of bits required for weighted random shuffle (reduces each time ball is pulled) = 363.40103411549404253061653790169 = 364
For i As Integer = 0 To 4
balls.Clear()
For value As Integer = 1 To 75
' do not add previous picks
If Not ContainsValue(picks, value) Then
balls.Add(New Ball(Weight(rng, bits(i)), value))
End If
Next
balls.Sort(weightComparer)
'For Each x As Ball In balls
'    Console.WriteLine(x.Weight)
'Next
'Console.ReadLine()
' choose first ball in sorted list
picks.Add(balls(0))
Next
picks.Sort(valueComparer)
' simulate random balls
'log10(15!) / log10(2) = number of bits required for weighted random shuffle = 40.250140469882621763813506287601 = 41 bits required for megaball
balls.Clear()
For value As Integer = 1 To 15
balls.Add(New Ball(Weight(rng, 41), value))
Next
balls.Sort(weightComparer)
' print to stdout
For i As Integer = 0 To 4
Console.Write(picks(i).Value.ToString("D2") & " "c)
Next
Console.WriteLine(balls(0).Value.ToString("D2"))
End While
End Using
End Sub
End Module

你的基本想法似乎很合理。但是：

你的权重不需要那么多比特。您所需要的只是使碰撞不太可能发生，即关于⌈log₂n²⌉每个项目的位数，加上一些以便于衡量。对于52张卡，每个卡的最小值约为12位，16位将使冲突的概率降至约4%。这应该是足够的，至少只要你明确地检查碰撞。
应该检查冲突(即两个项目具有相同的随机排序键)，如果找到一个，则重新启动洗牌。或者，可以增加排序键的长度，使发生碰撞的概率小到可以忽略不计。
是的，用十六进制编码排序键应该是可以的。事实上，如何编码它们并不重要，只要它是确定性的(即总是对相同的随机数进行相同的编码)。也就是说，既然你知道随机比特串的长度，为什么不把它们存储在原始二进制中呢？(特别是，如果每个密钥需要少于64位，则可以将每个密钥存储在大小适当的整数变量中。)
如果你想避免侧信道攻击，你应该选择一种可证明在恒定时间内运行的排序方法，并且具有恒定的功耗，而不管最终的顺序是什么。这说起来容易做起来难，因为大多数常见的排序算法都离恒定时间不远。也就是说，根据你的应用程序，这种攻击可能很重要，也可能无关紧要(但在你考虑这个问题之前，不要排除它们！)。

安全搅乱数组的另一种方法是使用Fisher–耶茨用加密安全的RNG洗牌。这种方法可以减少比特的浪费，更容易在恒定时间内实现(或者至少在与输出无关的时间内实现；见下文)，但它确实要求生成器能够从任何整数范围返回无偏样本，而不仅仅是从长度为2的幂的范围返回。(拒绝采样是实现这一点的一种方法—它不是恒定的时间，但可以表明所需的时间不会透露任何关于最终输出的信息，所以它仍然可以。)

最后，如果您只需要从混洗数组中选择一个元素，那么所有这些都是不必要的：只需为数组选择一个随机索引(统一地，例如使用上面提到的拒绝采样方法)并返回相应的元素。

相关内容

最新更新

热门标签：