نزيد عشوائية حقيقة أنه [على الأرجح] [تقريبًا] عن طريق الصدفة

أرقام عشوائية ألذ إذا القليل من الفلفل

سنجمع بين النظرية والتطبيق - سنوضح أن تحسين إنتروبيا التسلسلات العشوائية أمر ممكن ، وبعد ذلك سنلقي نظرة على رموز المصدر التي تفعل ذلك.

كنت أرغب حقًا في الكتابة عن حقيقة أن إنشاء عدد عشوائي عشوائي عالي الجودة ، أي أنه من الأنتروبيا بشكل كبير ، أمر حاسم في حل عدد كبير من المشاكل ، ولكن ربما يكون هذا غير ضروري. آمل أن يعرف الجميع ذلك جيدًا.

سعياً وراء أرقام عشوائية عالية الجودة ، يخترع الناس أجهزة ذكية جدًا (انظر ، على سبيل المثال ، هنا وهنا ). من حيث المبدأ ، يتم تضمين مصادر عشوائية جيدة جدًا في واجهة برمجة التطبيقات لأنظمة التشغيل ، ولكن هذه مسألة خطيرة ، ودودة من الشك دائمًا ما تأكلنا قليلاً: هل RNG الذي أستخدمه جيدًا بما فيه الكفاية وهل هو مدلل ... دعنا نقول ، من قبل أطراف ثالثة؟

القليل من النظرية

بادئ ذي بدء ، نوضح أنه مع النهج الصحيح ، لا يمكن أن تتدهور جودة RNG الحالية. أبسط نهج صحيح هو تراكب أي تسلسل آخر من خلال عملية XOR على التسلسل الرئيسي . قد يكون التسلسل الرئيسي ، على سبيل المثال ، RNG نظامي ، والذي نعتبره جيدًا بالفعل ، ولكن لا تزال هناك بعض الشكوك ، وكان لدينا رغبة في تشغيله بأمان. قد يكون هناك تسلسل إضافي ، على سبيل المثال ، مولد أرقام عشوائية زائفة ، والذي يبدو ناتجه جيدًا ، لكننا نعلم أن إنتروبيا الحقيقية منخفضة جدًا. سيكون التسلسل الناتج نتيجة تطبيق عملية XOR على بتات التسلسلين الأساسي والثانوي. فارق بسيط هام: يجب أن يكون التسلسلان الأساسي والثانوي مستقلان عن بعضهما البعض. أي أنه يجب أخذ إنتروبيا من مصادر مختلفة جوهريًا ، لا يمكن حساب ترابطها.

اشر ب x للقطعة التالية من التسلسل الرئيسي ، و y - البتة المقابلة للجزء الإضافي. يُشار إلى بت التسلسل الناتج بواسطة r :
ص = س س

المحاولة الأولى لإثبات. دعنا نحاول البحث في إنتروبيا المعلوماتية لـ x و y و r . نشير إلى احتمال صفر x كـ p _x0 واحتمال صفر y كـ p _y0 . يتم حساب إنتروبي المعلومات x و y وفقًا لصيغة شانون:

H _x = - (p _x0 log ₂ p _x0 + (1 - p _x0 ) log ₂ (1 - p _x0 ))
H _y = - (p _y0 log ₂ p _y0 + (1 - p _y0 ) log ₂ (1 - p _y0 ))

يظهر صفر في التسلسل الناتج عندما يكون هناك صفرين أو وحدتين عند الإدخال. احتمال الصفر ص:

p _r0 = p _x0 p _y0 + (1 - p _x0 ) (1 - p _y0 )
H _r = - (p _r0 log ₂ p _r0 + (1 - p _r0 ) log ₂ (1 - p _r0 ))

من أجل إثبات ثبات التسلسل الرئيسي ، من الضروري إثبات ذلك
Hr - Hx ≥ 0 لأي قيم p _x0 و p _y0 . لم أستطع إثبات ذلك تحليليًا ، لكن الحساب التصوري يظهر أن الزيادة في الإنتروبيا تشكل سطحًا أملسًا ، والذي لن يتحول إلى سالب في أي مكان:


على سبيل المثال ، إذا أضفنا إشارة إضافية شديدة الانحراف مع p _y0 = 0.1 إلى الإشارة الرئيسية المنحرفة c p _x0 = 0.3 (إنتروبيا 0.881) ، نحصل على النتيجة p _r0 = 0.66 مع الكون 0.925.

لذا ، لا يمكن إفساد الكون ، ولكن هذا ليس دقيقًا بعد. لذلك ، هناك حاجة إلى محاولة ثانية. ومع ذلك ، من خلال الكون يمكن للمرء أن يثبت أيضًا. مخطط (جميع الخطوات بسيطة للغاية ، يمكنك القيام بذلك بنفسك):

1. نثبت أن الكون له حد أقصى عند النقطة p ₀ = 1/2.
2. نثبت أنه بالنسبة لأي من p _x0 و p _{y0 ،} لا يمكن أن تكون قيمة p _r0 أبعد من 1/2 من p _x0 .

المحاولة الثانية لإثبات. من خلال القدرة على التخمين. افترض أن أحد المهاجمين لديه بعض المعلومات عن التسلسلين الأساسي والثانوي. يتم التعبير عن امتلاك المعلومات في القدرة مع بعض الاحتمال على تخمين قيم x و y ، ونتيجة لذلك ، ص . يُشار إلى احتمالات التخمين x و y بواسطة g _x و g y ، على التوالي (من كلمة guess). يتم تخمين جزء من التسلسل الناتج إما عندما يتم تخمين كلتا القيمتين بشكل صحيح ، أو عندما يكون كلاهما غير صحيحين ، لذا فإن احتمال التخمين هو:
g _r = g _x g _y + (1 - g _x ) (1 - g _y ) = 2 g _x g _y - g _x - g _y + 1

عندما يكون لدينا أداة التخمين المثالية ، يكون لدينا g = 1. إذا لم نكن نعرف أي شيء ، فإن g هي ... لا ، لا صفر ، ولكن 1/2. هذا هو بالضبط احتمال التخمين الذي يتضح إذا اتخذنا قرارًا بإلقاء عملة معدنية. حالة مثيرة جدا للاهتمام عندما g <1/2. من ناحية ، يمتلك مثل هذا التخمين في مكان ما بداخله بيانات عن القيمة المتوقعة ، ولكن لسبب ما يعكس مخرجاته ، وبالتالي تصبح العملة أسوأ . يرجى تذكر عبارة "أسوأ من العملة" ، وسوف تكون مفيدة لنا أدناه. من وجهة نظر النظرية الرياضية للتواصل (ونتيجة لذلك ، النظرية الكمية للمعلومات المألوفة لنا) ، هذا الموقف سخيف ، لأنه لن يكون نظرية معلومات ، بل نظرية تضليل ، ولكن في الحياة لدينا هذا الموقف في كثير من الأحيان أكثر مما نود .

النظر في الحالات المقيدة:

• g _x = 1 ، أي أن التسلسل x يمكن التنبؤ به تمامًا:
  g _r = g _x g _y + (1 - g _x ) (1 - g _y ) = 1 g _y + (1−1) (1 - g _y ) = g _y
  أي أن احتمال تخمين النتيجة يساوي احتمال تخمين التسلسل الإضافي.
• g _y = 1 : مشابه لما سبق. يساوي احتمال تخمين النتيجة احتمال تخمين التسلسل الرئيسي.
• g _x = 1/2 ، أي أن التسلسل x غير متوقع تمامًا:
  g _r = 2 g _x g _y - g _x - g _y + 1 = 2/2 g _y - 1/2 - g _y +1 = g _y - g _y + 1/2 = 1/2
  وهذا يعني أن إضافة أي تسلسل إضافي لا يضعف عدم القدرة على التنبؤ الكامل للتسلسل الرئيسي.
• g _y = 1/2 : مشابه لما سبق. إن إضافة تسلسل إضافي غير متوقع تمامًا يجعل النتيجة غير متوقعة تمامًا.

من أجل إثبات أن إضافة تسلسل إضافي إلى التسلسل الرئيسي لن يساعد المهاجم ، نحتاج إلى معرفة الظروف التي قد تكون فيها g _r أكبر من g _x ، أي

2 جم _x g _y - g _x - g _y + 1> g _x

انقل g _x من الجانب الأيمن إلى اليسار ، و g _y و 1 إلى اليمين:

2 جم _x g _y - g _x - g _x > g _y - 1
2 جم _x g _y - 2 g _x > g _y - 1
نخرج على الجانب الأيسر 2g _x من الأقواس:
2 جم _x (g _y - 1)> g _y - 1
نظرًا لأن لدينا g _y أقل من واحد (الحالة المقيدة عندما يكون g _y = 1 ، قد أخذنا بعين الاعتبار بالفعل) ، فإننا نحول g _y −1 إلى 1 - g _y ، مع تذكر تغيير "المزيد" إلى "أقل":
2 جم _x (1 - g _y ) <1 - g _y

قم بتقليل "1 - g _y " واحصل على الحالة التي تؤدي بموجبها إضافة تسلسل إضافي إلى تحسين وضع المهاجم للتخمين:

2 جم _× <1
ز _× <1/2

أي أن g _r يمكن أن تكون أكبر من g _x فقط عندما يكون التخمين من التسلسل الرئيسي أسوأ من العملة المعدنية . ثم ، عندما ينخرط المتنبئ في التخريب الواعي.

بعض الاعتبارات الإضافية حول الكون.

1. الانتروبيا مفهوم أسطوري للغاية. المعلومات - بما في ذلك. هذا أمر مزعج للغاية. في كثير من الأحيان ، يتم تمثيل الإنتروبيا الإعلامية كنوع من المادة الدقيقة التي تكون إما موضوعية في البيانات أو لا. في الواقع ، فإن الكون الإعلامي ليس شيئًا موجودًا في الإشارة نفسها ، ولكنه تقييم كمي للوعي المسبق لمستلم الرسالة فيما يتعلق بالرسالة نفسها. أي أنه لا يتعلق فقط بالإشارة ، ولكن أيضًا حول المستلم. إذا كان المستلم لا يعرف أي شيء على الإطلاق عن الإشارة مقدمًا ، فإن الانتروبيا الإعلامية للوحدة الثنائية المرسلة هي 1 بت بالضبط ، بغض النظر عن كيفية استقبال الإشارة وما هي.
2. لدينا نظرية إضافة الإنتروبيا والتي بموجبها يكون الإنتروبيا الكلية للمصادر المستقلة مساوية لمجموع إنتروبيا هذه المصادر. إذا قمنا بدمج التسلسل الرئيسي مع التسلسل الإضافي من خلال التسلسل ، فإننا قد حافظنا على إنتروبيا المصادر ، لكننا حصلنا على نتيجة سيئة ، لأنه في مهمتنا نحتاج إلى تقييم ليس الكون الكامل ، ولكن التسلسل المحدد ، من حيث بت منفصل. تسلسل المصادر يعطينا الإنتروبيا المحددة للنتيجة مساوية للمتوسط ​​الحسابي لإنتروبيا المصادر ، والتسلسل الإضافي الضعيف للإنتروبيا يفاقم النتيجة بشكل طبيعي. يؤدي تطبيق عملية XOR إلى حقيقة أننا نفقد بعضًا من الإنتروبيا ، ولكننا نضمن أن الإنتروبيا الناتجة ليست أسوأ من الإنتروبيا القصوى للمصطلحات.
3. المبرمجون لديهم عقيدة: استخدام مولدات الأرقام العشوائية الزائفة هو غطرسة لا تغتفر. لأن هذه المولدات لديها إنتروبيا صغيرا محددا. لكننا اكتشفنا للتو أنه إذا تم عمل كل شيء بشكل صحيح ، فإن الإنتروبيا تصبح برميلًا من العسل لا يمكن أن يفسد بأي كمية من القطران.
4. إذا كان لدينا فقط 10 بايت من الإنتروبيا الحقيقية ، موزعة على كيلوبايت من البيانات ، من وجهة نظر رسمية ، لدينا 1 ٪ فقط من الإنتروبيا المحددة ، وهو أمر سيئ للغاية. ولكن إذا تم تلطيخ هذه البايت العشر بشكل نوعي ، وبصرف النظر عن القوة الغاشمة ، فلا توجد طريقة لحساب هذه البايت العشرة ، فإن كل شيء لا يبدو سيئًا للغاية. 10 بايت هي 2 ⁸⁰ ، وإذا بحثت قوتنا الغاشمة في الثانية من خلال تريليون من الخيارات ، فسوف نحتاج إلى متوسط ​​19 ألف سنة لتعلم كيفية تخمين الشخصية التالية.

كما ذكر أعلاه ، فإن الكون الإعلامي هو قيمة نسبية. حيث ، بالنسبة لموضوع واحد ، فإن الإنتروبيا المحددة هي 1 ، وبالنسبة لموضوع آخر قد تكون 0. علاوة على ذلك ، قد لا يكون لدى الشخص الذي لديه 1 أي طريقة لمعرفة الحالة الحقيقية. ينتج نظام RNG تيارًا لا يمكن تمييزه عننا عشوائيًا حقًا ، ولكن لا يسعنا إلا أن نأمل أنه عشوائي حقًا للجميع . وصدق. إذا كان البارانويا يشير إلى أن جودة RNG الرئيسية قد تكون غير مرضية فجأة ، فمن المنطقي التحوط بمساعدة واحد إضافي.

تنفيذ جمع RNG في بيثون

from random import Random, SystemRandom from random import BPF as _BPF, RECIP_BPF as _RECIP_BPF from functools import reduce as _reduce from operator import xor as _xor class CompoundRandom(SystemRandom): def __new__(cls, *sources): """Positional arguments must be descendants of Random""" if not all(isinstance(src, Random) for src in sources): raise TypeError("all the sources must be descendants of Random") return super().__new__(cls) def __init__(self, *sources): """Positional arguments must be descendants of Random""" self.sources = sources super().__init__() def getrandbits(self, k): """getrandbits(k) -> x. Generates an int with k random bits.""" ########         : return _reduce(_xor, (src.getrandbits(k) for src in self.sources), 0) def random(self): """Get the next random number in the range [0.0, 1.0).""" ########  ,   SystemRandom   .  ... return self.getrandbits(_BPF) * _RECIP_BPF 

مثال للاستخدام:

 >>> import random_xe # <<<    >>> from random import Random, SystemRandom >>> #  : >>> myrandom1 = random_xe.CompoundRandom(SystemRandom(), Random()) >>> #    Random: >>> myrandom1.random() 0.4092251189581082 >>> myrandom1.randint(100, 200) 186 >>> myrandom1.gauss(20, 10) 19.106991205743107 

SystemRandom ، الذي يعتبر صحيحا ، يؤخذ على أنه التيار الرئيسي ، وتيار ثانوي - المعيار PRNG Random. النقطة في هذا ، بالطبع ، ليست كبيرة. إن PRNG القياسي ليس بالتأكيد نوع المكمل الذي كان يستحق البدء به. بدلاً من ذلك ، يمكنك الزواج من مجموعتي RNG نظامية معًا:

 >>> myrandom2 = random_xe.CompoundRandom(SystemRandom(), SystemRandom()) 

المعنى ، الحقيقة في هذا أقل حتى (على الرغم من أنه لسبب ما يوصي بروس شناير في التشفير التطبيقي لسبب ما) ، لأن الحسابات المذكورة أعلاه صالحة فقط للمصادر المستقلة. إذا تم اختراق النظام RNG ، سيتم اختراق النتيجة أيضًا. من حيث المبدأ ، فإن رحلة الهوى في البحث عن مصدر للانتروبيا الإضافية لا يقتصر على أي شيء (في عالمنا ، الفوضى أكثر شيوعًا من النظام) ، ولكن كحل بسيط سأقدم HashRandom PRSP ، والذي يتم تنفيذه أيضًا في مكتبة random_xe.

أوراق استراتيجية الحد من الفقر بناء على التجزئة الدائرية

في أبسط الحالات ، يمكنك أخذ كمية صغيرة نسبيًا من البيانات الأولية (على سبيل المثال ، اطلب من المستخدم أن يطبل على لوحة المفاتيح) ، وحساب التجزئة ، ثم قم بإضافة التجزئة بشكل دوري إلى إدخال خوارزمية التجزئة وأخذ التجزئة. من الناحية التخطيطية ، يمكن تمثيل ذلك على النحو التالي:



تعتمد قوة التشفير لهذه العملية على افتراضين:

1. إن مهمة استعادة البيانات الأصلية من قيمة التجزئة غير معقدة.
2. باستخدام قيمة التجزئة ، من المستحيل استعادة الحالة الداخلية لخوارزمية التجزئة.

بعد التشاور مع جنون الارتياب الداخلي ، اعترف بأن الافتراض الثاني غير ضروري ، وبالتالي ، في التنفيذ النهائي لـ PRNG ، يكون المخطط معقدًا بعض الشيء:



الآن ، إذا تمكن أحد المهاجمين من الحصول على قيمة "Hash 1r" ، فلن يتمكن من حساب قيمة "Hash 2r" التي تتبعه ، نظرًا لأنه ليس لديه قيمة "Hash 2h" التي لا يمكنه التعرف عليها بدون حساب وظيفة التجزئة "ضد الصوف". وبالتالي ، فإن قوة التشفير لهذا المخطط تتوافق مع قوة التشفير لخوارزمية التجزئة المستخدمة.

مثال للاستخدام:

 >>> #  ,  HashRandom     '123': >>> myrandom3 = random_xe.CompoundRandom(SystemRandom(), random_xe.HashRandom('123')) >>> #    Random: >>> myrandom3.random() 0.8257149881148604 

بشكل افتراضي ، يتم استخدام خوارزمية SHA-256. إذا كنت تريد شيئًا آخر ، فيمكنك نقل النوع المطلوب من خوارزمية التجزئة إلى المُنشئ باستخدام المعلمة الثانية. على سبيل المثال ، لنقم بإنشاء RNG مركب ، يلخص ما يلي في كومة:

1. RNG الجهازية (هذا مقدس).
2. معالجة إدخال المستخدم بواسطة خوارزمية SHA3-512.
3. الوقت الذي يقضيه في هذا الإدخال معالجة SHA-256.

 >>> from getpass import getpass >>> from time import perf_counter >>> from hashlib import sha3_512 #    : >>> def super_myrandom(): t_start = perf_counter() return random_xe.CompoundRandom(SystemRandom(), random_xe.HashRandom( getpass('  :'), sha3_512), random_xe.HashRandom(perf_counter() - t_start)) >>> myrandom4 = super_myrandom()   : >>> myrandom4.random() 0.35381173716740766 

الاستنتاجات:

1. إذا لم نكن متأكدين من مولد الأرقام العشوائية الخاص بنا ، فيمكننا حل هذه المشكلة بسهولة وبشكل مذهل.
2. لحل هذه المشكلة ، لا يمكننا أن نفعل ما هو أسوأ. فقط أفضل. وقد ثبت ذلك رياضيا.
3. يجب ألا ننسى محاولة التأكد من أن مصادر الإنتروبيا المستخدمة مستقلة.

مصادر المكتبة موجودة على GitHub .