安全地生成一致隨機的BigInteger

我想安全地生成一個範圍[0，N）的隨機數，其中N是一個參數。但是，System.Security.Cryptography.RandomNumberGenerator只提供一個GetBytes（）方法來填充具有隨機值的數組。安全地生成一致隨機的BigInteger

（我需要在SRP稍加修改的版本中使用隨機數的隨機整數。「稍微修改」部分是在我的掌握，唯一的原因，我甚至感動加密的東西。）

我已經寫了一個方法來做到這一點，但我正在尋找更好的方法，或者至少確認我做得對。

using System.Numerics 

///<summary>Generates a uniformly random integer in the range [0, bound).</summary> 
public static BigInteger RandomIntegerBelow(this System.Security.Cryptography.RandomNumberGenerator source, BigInteger bound) { 
    Contract.Requires<ArgumentException>(source != null); 
    Contract.Requires<ArgumentException>(bound > 0); 
    Contract.Ensures(Contract.Result<BigInteger>() >= 0); 
    Contract.Ensures(Contract.Result<BigInteger>() < bound); 

    //Get a byte buffer capable of holding any value below the bound 
    var buffer = (bound << 16).ToByteArray(); // << 16 adds two bytes, which decrease the chance of a retry later on 

    //Compute where the last partial fragment starts, in order to retry if we end up in it 
    var generatedValueBound = BigInteger.One << (buffer.Length * 8 - 1); //-1 accounts for the sign bit 
    Contract.Assert(generatedValueBound >= bound); 
    var validityBound = generatedValueBound - generatedValueBound % bound; 
    Contract.Assert(validityBound >= bound); 

    while (true) { 
     //generate a uniformly random value in [0, 2^(buffer.Length * 8 - 1)) 
     source.GetBytes(buffer); 
     buffer[buffer.Length - 1] &= 0x7F; //force sign bit to positive 
     var r = new BigInteger(buffer); 

     //return unless in the partial fragment 
     if (r >= validityBound) continue; 
     return r % bound; 
    } 
}

來源

2011-03-16 Craig Gidney

這是一些漂亮的代碼。 – Amy 2011-03-16 19:56:49

您的代碼看起來正確無偏。但是，如果您是在性能之後，並且取決於您使用的隨機源的速度，您可能需要稍微更改一下。這個想法是掩蓋掉更多的位，使得隨機值r小於2*bound。如果比特長度的結合是x（長度不含符號位），則生成的n = ((x+8)/8)字節的緩衝器，並且屏蔽掉在上(n*8-x)位。在C＃中，這應該是這樣的：

var x = BitLength(bound); 
var n = ((x + 8)/8); 
var buffer = new Byte[n]; 
var mask = 0xFF >> (8 * n - x); 
while (true) { 
    source.GetBytes(buffer); 
    buffer[n - 1] &= mask; 
    var r = new BigInteger(buffer); 
    if (r < bound) 
     return r; 
}

有了這樣的代碼，你可能必須從源頭提出更多的隨機字節，但你避免模塊化減少（在%運營商）。一個合適的PRNG應該比在大整數上劃分要快得多，所以這應該是一個更好的折衷 - 但這取決於隨機源的性能，並且由於它是一個性能問題，它不能完全沒有嘗試就回答。很可能，作爲整個SRP實施的一部分，無論如何它都不會有明顯的差別。

我上面一個BitLength()函數，它似乎並沒有在C＃中存在使用（Java的BigInteger類有一個bitLength()方法，但顯然微軟忘了，包括一個在他們的大整數實現 - 這是一種恥辱，因爲它似乎該實施確實包括一個名爲_bits的私人字段，該字段保持該值）。位長度可以通過bound值的表示（以字節爲單位）進行有效計算。

var buffer = bound.ToByteArray(); 
var n = buffer.length; 
var msb = buffer[n - 1]; 
var mask = 0; 
while (mask < msb) 
    mask = (mask << 1) + 1; 
while (true) { 
    source.GetBytes(buffer); 
    buffer[n - 1] &= mask; 
    var r = new BigInteger(buffer); 
    if (r < bound) 
     return r; 
}

我使用的事實，長度，以字節爲單位的bound編碼的，由ToByteArray()返回的，恰恰是n我需要的值：因此，代碼會變得這樣的事情。

來源

2011-03-17 12:41:34

我也很驚訝，沒有一個BitLength成員。我並不特別擔心Mod操作的成本，因爲無論如何我必須對結果值使用ModPow。 – 2011-03-17 12:53:29

該實現在範圍內生成無偏整數看起來是正確的。

另一種方法是將隨機字節作爲二進制小數0.xxxxxx...中的無限數字，將其乘以bound並向下取整。它實際上並不需要無限的數字，就像確定向下舍入的結果所需的數量一樣多。我認爲這更復雜。

但是，對於您的協議，在整個範圍內生成數字可能是不必要的。 RFC 5054 3.1節只需要256位私有指數。該數字來自加倍哈希輸出的位長，並要求使用安全的素數。該RFC的早期草案提到On Diffie-Hellman key agreement with short exponents作爲解釋，該解釋在第4節的第一段中。

如果您更喜歡更多的隨機位，請將位長減去range減去1.這就是OpenSSL does for Diffie-Hellman（搜索BN_rand及其之前的行）。這樣比較容易產生，並且少於全量程的兩倍，如果這有所改變，你應該使用更大的素數。

來源

2011-03-16 22:02:09 aaz

安全地生成一致隨機的BigInteger

回答

相關問題