الرقم العشوائي الزائف هو رقم خاص يتم إنشاؤه بواسطة مولد خاص. مولد البت العشوائي المحدد (PRNG) ، المعروف أيضًا باسم مولد البت العشوائي المحدد (DRBG) ، هو خوارزمية لتوليد سلسلة من الأرقام التي تقارب خصائصها خصائص تسلسل الأرقام العشوائية. تسلسل PRNG الذي تم إنشاؤه ليس عشوائيًا حقًا ، حيث يتم تحديده بالكامل بواسطة قيمة أولية تسمى بذرة PRNG ، والتي قد تتضمن قيمًا عشوائية حقًا. على الرغم من أنه يمكن إنشاء التسلسلات الأقرب إلى العشوائية باستخدام مولدات الأرقام العشوائية للأجهزة ، إلا أن مولدات الأرقام العشوائية الزائفة مهمة في الممارسة العملية لسرعة توليد الأرقام وإمكانية تكرار نتائجها.
التطبيق
PRNGs أساسية لتطبيقات مثل المحاكاة (على سبيل المثال لمونتي كارلو) والألعاب الإلكترونية (على سبيل المثال للإنشاء الإجرائي) والتشفير. تتطلب تطبيقات التشفير أن الناتجلم تكن البيانات متوقعة من المعلومات السابقة. الخوارزميات الأكثر تعقيدًا مطلوبة والتي لا ترث الخطية لـ PRNGs البسيطة.
الشروط والأحكام
الخصائص الإحصائية الجيدة هي مطلب مركزي للحصول على PRNG. بشكل عام ، هناك حاجة إلى تحليل رياضي دقيق للتأكد من أن RNG يولد أرقامًا قريبة بما يكفي للعشوائية لتكون مناسبة للاستخدام المقصود.
حذر جون فون نيومان من إساءة تفسير PRNG على أنه مولد عشوائي حقًا وقال مازحا أن "أي شخص يفكر في الأساليب الحسابية لتوليد أرقام عشوائية هو بالتأكيد في حالة خطيئة."
استخدم
يمكن إطلاق PRNG من حالة أولية تعسفية. سيولد دائمًا نفس التسلسل عند التهيئة بهذه الحالة. يتم تعريف فترة PRNG على النحو التالي: الحد الأقصى على جميع الحالات الأولية لطول بادئة التسلسل غير المتكرر. الفترة محدودة بعدد الحالات ، وعادة ما تقاس بالبتات. نظرًا لأنه من المحتمل أن يتضاعف طول الفترة مع إضافة كل بت "حالة" ، فمن السهل إنشاء PRNGs بفترات كبيرة بما يكفي للعديد من التطبيقات العملية.
إذا كانت الحالة الداخلية لـ PRNG تحتوي على n بت ، فلا يمكن أن تكون فترتها أكثر من 2n من النتائج ، فهي أقصر بكثير. بالنسبة لبعض PRNGs ، يمكن حساب المدة دون تجاوز الفترة بأكملها. عادةً ما تكون سجلات تحويل الملاحظات الخطية (LFSR)تم اختيارهم بحيث يكون لديهم فترات تساوي 2n - 1.
للمولدات المتطابقة الخطية فترات يمكن حسابها باستخدام العوملة. على الرغم من أن PPP سوف يكرر نتائجه بعد وصوله إلى نهاية الفترة ، إلا أن النتيجة المتكررة لا تعني الوصول إلى نهاية الفترة ، حيث قد تكون حالتها الداخلية أكبر من الناتج ؛ هذا واضح بشكل خاص لـ PRNGs ذات الإخراج بت واحد.
أخطاء محتملة
الأخطاء التي تم العثور عليها بواسطة PRNGs المعيبة تتراوح من دقيقة (وغير معروفة) إلى أخطاء واضحة. مثال على ذلك هو خوارزمية الأرقام العشوائية RANDU ، والتي تم استخدامها في الحواسيب المركزية لعقود. لقد كان عيبًا خطيرًا ، لكن لم يتم ملاحظته لفترة طويلة من الزمن.
في العديد من المجالات ، تعد الدراسات البحثية التي استخدمت الاختيار العشوائي أو محاكاة مونت كارلو أو طرق أخرى تعتمد على RNG أقل موثوقية مما يمكن أن تكون نتيجة GNPG ذات الجودة الرديئة. حتى اليوم ، الحذر مطلوب في بعض الأحيان ، كما يتضح من التحذير في الموسوعة الدولية للعلوم الإحصائية (2010).
دراسة حالة ناجحة
كتوضيح ، ضع في اعتبارك لغة برمجة Java المستخدمة على نطاق واسع. اعتبارًا من عام 2017 ، لا تزال Java تعتمد على Linear Congruential Generator (LCG) من أجل PRNG.
التاريخ
أول PRNG لتجنب المشاكل الخطيرة ولا يزال يعمل بسرعة كبيرة ،كانت Mersenne Twister (التي تمت مناقشتها أدناه) ، والتي تم نشرها في عام 1998. منذ ذلك الحين ، تم تطوير PRNGs أخرى عالية الجودة.
لكن تاريخ الأرقام العشوائية الزائفة لا ينتهي عند هذا الحد. في النصف الثاني من القرن العشرين ، اشتملت الفئة القياسية من الخوارزميات المستخدمة في PRNGs على المولدات المتطابقة الخطية. من المعروف أن جودة LCG غير كافية ، لكن الأساليب الأفضل لم تكن متاحة. وصف Press et al (2007) النتيجة على النحو التالي: "إذا اختفت جميع الأوراق العلمية التي كانت نتائجها محل شك بسبب [LCGs وما يتصل بها] من أرفف المكتبة ، فستكون هناك فجوة بحجم قبضة اليد على كل رف."
كان الإنجاز الرئيسي في إنشاء المولدات شبه العشوائية هو إدخال طرق تعتمد على التكرار الخطي في حقل مكون من عنصرين ؛ تقترن مثل هذه المذبذبات بسجلات تحول التغذية المرتدة الخطية. لقد كانت بمثابة الأساس لاختراع مجسات الأرقام العشوائية الزائفة.
على وجه الخصوص ، تجنب اختراع Mersen Twister في عام 1997 العديد من المشاكل مع المولدات السابقة. تحتوي Mersenne Twister على فترة 219937−1 تكرار (≈4.3 × 106001). لقد ثبت أنه موزع بشكل موحد (حتى) 623 بعدًا (لقيم 32 بت) ، وفي وقت تقديمه كان أسرع من مولدات الصوت الإحصائي الأخرى التي تنتج تسلسلات رقمية شبه عشوائية.
في عام 2003 ، قدم جورج مارساجليا عائلة من مولدات xorshift التي تعتمد أيضًا على التكرار الخطي. هذه المولدات للغايةسريعة و- مقترنة بعملية غير خطية- اجتازوا اختبارات إحصائية صارمة.
في عام 2006 ، تم تطوير عائلة المولدات WELL. تعمل مولدات WELL بشكل ما على تحسين جودة Twister Mersenne ، التي تحتوي على مساحة حالة كبيرة جدًا واسترداد بطيء جدًا منها ، مما يؤدي إلى إنشاء أرقام شبه عشوائية بها الكثير من الأصفار.
تشفير
PRNG المناسب لتطبيقات التشفير يسمى PRNG الآمن تشفيرًا (CSPRNG). مطلب CSPRNG هو أن المهاجم الذي لا يعرف البذرة لديه ميزة هامشية فقط في التمييز بين تسلسل خرج المولد من التسلسل العشوائي. بمعنى آخر ، في حين أن PRNG مطلوب فقط لاجتياز اختبارات إحصائية معينة ، يجب على CSPRNG اجتياز جميع الاختبارات الإحصائية التي تقتصر على وقت متعدد الحدود في حجم البذرة.
على الرغم من أن إثبات هذه الخاصية يتجاوز المستوى الحالي لنظرية التعقيد الحسابي ، يمكن تقديم أدلة قوية عن طريق تقليل CSPRNG إلى مشكلة تعتبر صعبة ، مثل عامل العدد الصحيح. بشكل عام ، قد تكون هناك حاجة لسنوات من المراجعة قبل أن يتم اعتماد خوارزمية على أنها CSPRNG.
لقد ثبت أنه من المحتمل أن NSA أدخلت بابًا خلفيًا غير متماثل في مولد الأرقام العشوائية المزيفة Dual_EC_DRBG المعتمد من NIST.
خوارزميات عشوائية زائفةأرقام
تنتج معظم خوارزميات PRNG تسلسلات يتم توزيعها بالتساوي من خلال أي من الاختبارات العديدة. هذا هو سؤال مفتوح. إنه أحد العناصر المركزية في نظرية وممارسة التشفير: هل هناك طريقة للتمييز بين ناتج PRNG عالي الجودة من تسلسل عشوائي حقيقي؟ في هذا الإعداد ، يعرف المحلل أنه تم استخدام خوارزمية PRNG معروفة (ولكن ليس الحالة التي تمت تهيئتها بها) ، أو تم استخدام خوارزمية عشوائية بالفعل. يجب أن يفرق بينهما
يعتمد أمان معظم خوارزميات وبروتوكولات التشفير التي تستخدم PRNGs على افتراض أنه من المستحيل التمييز بين استخدام PRNG المناسب واستخدام تسلسل عشوائي حقيقي. أبسط الأمثلة على هذه التبعية هي الأصفار المتدفقة ، والتي غالبًا ما تعمل عن طريق حذف أو إرسال رسالة نص عادي مع إخراج PRNG ، مما ينتج عنه نص مشفر. يعد تصميم PRNGs الملائمة للتشفير أمرًا صعبًا للغاية حيث يجب أن تفي بمعايير إضافية. حجم فترتها هو عامل مهم في ملاءمة التشفير لـ PRNG ، ولكن ليس الوحيد.
يُعرف الكمبيوتر المبكر PRNG الذي اقترحه جون فون نيومان في عام 1946 باسم طريقة المربعات المتوسطة. الخوارزمية كالتالي: خذ أي رقم ، قم بتربيعه ، قم بإزالة الأرقام الوسطى من الرقم الناتج كـ "رقم عشوائي" ، ثم استخدم هذا الرقم كرقم بداية للتكرار التالي. على سبيل المثال ، ينتج عن تربيع الرقم 1111الرقم 1234321 ، والذي يمكن كتابته بالشكل 01234321 ، الرقم المكون من 8 أرقام هو مربع الرقم المكون من 4 أرقام. هذا يعطي 2343 كرقم "عشوائي". نتيجة تكرار هذا الإجراء هي 4896 وهكذا. استخدم Von Neumann أرقامًا مكونة من 10 أرقام ، لكن العملية كانت هي نفسها.
عيوب "المربع الأوسط"
مشكلة طريقة "المربع المتوسط" هي أن جميع المتتاليات تتكرر في النهاية ، بعضها سريع جدًا ، على سبيل المثال: 0000. عرف فون نيومان بهذا ، لكنه وجد نهجًا كافيًا لأغراضه ، وكان قلقًا من أن "التصحيحات" الرياضية ستخفي الأخطاء بدلاً من إزالتها.
وجد Von Neumann أن مولدات الأرقام العشوائية والعشوائية الزائفة غير مناسبة: إذا لم يسجلوا المخرجات التي تم إنشاؤها ، فلا يمكن التحقق من وجود أخطاء فيها لاحقًا. إذا كان عليهم كتابة نتائجهم ، فسوف يستنفدون ذاكرة الكمبيوتر المحدودة المتاحة وبالتالي قدرة الكمبيوتر على قراءة الأرقام وكتابتها. إذا كانت الأرقام مكتوبة على بطاقات ، فستستغرق وقتًا أطول للكتابة والقراءة. على كمبيوتر ENIAC الذي استخدمه ، طريقة "المربع الأوسط" ونفذ عملية الحصول على أرقام شبه عشوائية أسرع بمئات المرات من قراءة الأرقام من البطاقات المثقوبة.
تم استبدال المربع المتوسط بمولدات أكثر تعقيدًا.
طريقة مبتكرة
ابتكار حديث هو الجمع بين المربع المتوسط مع تسلسل Weil. تضمن هذه الطريقة منتجات عالية الجودة في الداخلفترة طويلة. يساعد في الحصول على أفضل صيغ الأرقام العشوائية الزائفة.
