هل من الممكن الحصول على تقريب إلى بذرة بناءً على تسلسل محدود من الأرقام العشوائية الزائفة؟

Question

لنفترض أن لدي بعض الأرقام التي تشكل سلسلة على سبيل المثال: 652،328،1،254 وأريد الحصول على بذرة إذا كنت ، على سبيل المثال ، أفعل

srand(my_seed);

سأحصل على نوع من التقريب مع خطأ محدد في تسلسلي الأصلي ، عندما تظهر جميع الأرقام بنفس الترتيب.

Answer 1

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

إذا كانت الخوارزمية أكثر تعقيدًا ، فقد يكون هذا مستحيلًا.

لاحظ أن الخوارزمية المستخدمة في المكتبة القياسية C غير مقيدة وفقًا للمعايير ، فقد يكون للمنصات المختلفة تطبيقات مختلفة.

Answer 2

لا يمكن أن يكون لديك خطأ ملزم بشكل عام. إما أن الخوارزمية تعمل أو لا. والسبب في ذلك هو أن وجود خطأ معقول من الواضح أن Rand_Max. وهذا بدوره يعني أن البتات المنخفضة ليست عشوائية مثل البتات الأعلى. لكن PRNG جيد يتأكد من أن جميع البتات عشوائية على قدم المساواة.

النظر في هذا مثال بطيء ولكنه سليم من الناحية الرياضية لخوارزمية RNG:

int rand() {
  state = AES_encrypt(state);
  return state % RAND_MAX;
}
void srand(int seed) {
  state = AES_encrypt(seed);
}

إذا تمكنت من العثور على أي ارتباط مهم بين تسلسل الإخراج والما السابق state, ، يجب اعتبار خوارزمية AES مكسورة.

Answer 3

ألق نظرة على هذا سؤال.

كما يقول جاستن ، من الممكن أن يتراجع عن مولد متطابق خطي (الذي rand() غالبًا ما تكون التطبيقات) عندما يكون لديك سلسلة من الأرقام التي تم إنشاؤها. أعتقد أن المشكلة هي معرفة أي من القيم السابقة هي البذرة الأصلية ...

Answer 4

إن تعريف PRNG Crytographic هو التعريف الذي لا يمكن حسابه عن ذلك عن طريق الحساب - ومع ذلك ، كما ذكر ، هناك PRNG الأضعف (وأسرع بكثير) والتي يمكن أن يكون ذلك ممكنًا. لذلك يعتمد على الخوارزمية الخاصة بك.