सुरक्षित रूप से एक समान यादृच्छिक BigInteger

Question

उत्पन्न करना मैं सुरक्षित रूप से श्रेणी [0, एन) में यादृच्छिक संख्या उत्पन्न करना चाहता हूं, जहां एन पैरामीटर है। हालांकि, System.Security.Cryptography.RandomNumberGenerator केवल यादृच्छिक मानों के साथ सरणी भरने के लिए GetBytes() विधि प्रदान करता है।

(मैं SRP का एक थोड़ा संशोधित संस्करण में प्रयोग किया जाता nonces के लिए यादृच्छिक पूर्णांकों की जरूरत है। "थोड़ा संशोधित" भाग मेरे नियंत्रण से बाहर है, और एकमात्र कारण मैं भी छू क्रिप्टो सामान कर रहा हूँ।)

मैंने ऐसा करने के लिए एक विधि लिखी है, लेकिन मैं एक बेहतर तरीका ढूंढ रहा हूं या कम से कम पुष्टि कर रहा हूं कि मैं इसे सही कर रहा हूं।

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; 
    } 
} 

Answer 1

आपका कोड सही और निष्पक्ष दिखता है। हालांकि, यदि आप प्रदर्शन के बाद हैं, और यादृच्छिक स्रोत की गति के आधार पर आप इसे थोड़ा बदलना चाहते हैं। विचार कुछ और बिट्स को मास्क करना है ताकि यादृच्छिक मान r2*bound से छोटा हो। बिट्स में लंबाई तो बाध्य की, x (लंबाई संकेत बिट को छोड़कर) है तो आप n = ((x+8)/8) बाइट्स की एक बफर उत्पन्न, और ऊपरी (n*8-x) बिट्स बाहर मुखौटा।

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; 
} 

कोड के इस प्रकार के साथ

, आप स्रोत से अधिक यादृच्छिक बाइट्स पूछना पड़ सकता है, लेकिन आप मॉड्यूलर कमी (% ऑपरेटर) से बचने: सी # में, इस तरह दिखना चाहिए। एक पूर्ण पीआरएनजी बड़े पूर्णांक पर विभाजन से बहुत तेज होना चाहिए, इसलिए यह एक बेहतर व्यापार-बंद होना चाहिए - लेकिन यह वास्तव में यादृच्छिक स्रोत के प्रदर्शन पर निर्भर करता है, और चूंकि यह प्रदर्शन का सवाल है, यह पूरी तरह से नहीं हो सकता है कोशिश किए बिना जवाब दिया। संभावना है कि, एक समग्र एसआरपी कार्यान्वयन के हिस्से के रूप में, यह वैसे भी कोई ध्यान देने योग्य अंतर नहीं करेगा।

मैं एक BitLength() समारोह जो सी # में मौजूद प्रतीत नहीं होता है इसके बाद के संस्करण का इस्तेमाल किया है (जावा के 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 है कि मैं जरूरत का मूल्य है उपयोग कर रहा हूँ।

Answer 2

यह कार्यान्वयन एक सीमा में निष्पक्ष पूर्णांक उत्पन्न करने के लिए सही दिखता है।

एक अन्य दृष्टिकोण बाइनरी अंश 0.xxxxxx... में अनंत अंकों के रूप में यादृच्छिक बाइट्स लेना होगा, इसे bound से गुणा करें और गोल करें। यह वास्तव में असीमित अंक नहीं लेगा, जितना आवश्यक है उतना ही निर्धारित करने के लिए कि गोल-डाउन परिणाम क्या है। मुझे लगता है कि हालांकि यह अधिक जटिल है।

लेकिन पूर्ण श्रेणी में संख्याएं उत्पन्न करना आपके प्रोटोकॉल के लिए अनावश्यक हो सकता है। RFC 5054 अनुभाग 3.1 केवल 256-बिट निजी एक्सपोनेंट की आवश्यकता है। यह संख्या हैश आउटपुट की बिट-लम्बाई को दोगुना करने से आती है और इसके लिए एक सुरक्षित प्राइम का उपयोग किया जाता है। उस आरएफसी के पहले ड्राफ्ट ने स्पष्टीकरण के लिए On Diffie-Hellman key agreement with short exponents को संदर्भित किया, जो धारा 4 के पहले पैराग्राफ में है।

यदि आप अधिक यादृच्छिक बिट्स पसंद करते हैं, तो range शून्य 1 की थोड़ी लंबाई लें। ओपनएसएसएल does for Diffie-Hellman (BN_rand और इसके पहले की रेखा के लिए खोजें)। यह अभी भी आसान है और कम सीमा से दो गुना कम है, और यदि इससे कोई फर्क पड़ता है तो आपको एक बड़ा प्राइम का उपयोग करना चाहिए।