بلام بلام شاب

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

بلام بلام شاب یک الگوریتم مولد اعداد شبه تصادفی میباشد که در سال ۱۹۸۶ توسط لنور بلام و مانوئل بلام و مایکل شاب ارائه شد.

ساختار این الگوریتم به صورت زیر میباشد :

x_{n+1} = x_n^2 \bmod M

که در آن "M=p*q" میباشد که p و q اعداد اول بزرگ میباشند.در هر مرحله از این الگوریتم مقدار خروجی در xn+1 قرار گرفته میشود.و نتیجه این مولد میتواند از بیت همزادی زوج و یا فرد و یا بیت های کم ارزش این عدد به دست بیاید.یعنی همانطور که در مثال خواهید دید به ازای هر بیت یک عدد که قصد ساخت آن را داریم یک بار این رابطه را اجرا کنیم و با استفاده از عدد به دست آمده بیت مورد نظر را دریافت کنیم. عدد x0 که نیز به عنوان نقطه شروع برای این الگوریتم باید قرار داده شود باید نسبت به M اول باشد.همچنین ۱ نمی‌تواند به عنوان نقطه شروع در نظر گرفته شود.همچنین باید بزرگ ترین مقسوم علیه مشترک نتیجه تابع اویلر بر دو عدد p , q عددی کوچک شود. هر دو عدد p , q باید با عدد ۳ بهپیمانه ۴متجانس باشند.

یکی از جذابیت های الگوریتم بلام بلام شام این است که عدد xi را میتوان به طور مستقیم با استفاده از قضیه اویلر به دست آورد.

x_i = \left( x_0^{2^i \bmod \lambda(M)} \right) \bmod M

که در آن \lambda یک تابع کارمیکال میباشد.

\lambda(M) = \lambda(p\cdot q) = \operatorname{lcm}(p-1, q-1)).

امنیت[ویرایش]

این روش برای تولید اعداد تصادفی برای مصارف شبیه سازی مناسب نمی‌باشد و تنها برای مصارف رمزنگاری مناسب میباشد.زیرا این الگوریتم بسیار کند میباشد.

از آنجایی که پیچیدگی محاسباتی الگوریتم های تجزیه و شکستن آنها به عوامل اول بالاست این الگوریتم از لحاظ امنیتی دارای رتبه بالایی میباشد.برای پیش بینی بیت های عددی که با استفاده از این الگوریتم به دست می آید باید محاسباتی با پیچیدگی معادل تجزیه عدد M به عوامل اول را انجام داد.

از آنجایی که با رشد M پیچیدگی محاسباتی افزایش میابد میتوان نتیجه گرفت که برای مقادیر بزرگ M نمیتوان روشی غیر تصادفی که اعدادی معادل خروجی این الگوریتم به ما بدهد یافت.این روش امنیتی در امنیت روش های رمز نگاری دیگر مانند رمز نگاری آر اس ای را دارا میباشد.

مثال[ویرایش]

p=11، q=19 s=3

برای شروع هسته انجام عملیات را برابر ۳ قرار میدهیم که x0 در مرحله اول از همین هسته تولید خواهد شد.

میتوانیم انتظار سیکل تولید اعداد تصادفی طولانی را با همین اعداد p , q کوچک داشته باشیم زیرا :

{\rm gcd}(\varphi(p-1), \varphi(q-1))=2.

x_1، x_2، \ldots x_5 = 9, 81, 82, 36, 42, 92

Even parity bit Odd parity bit Least significant bit
0 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 0 0

منابع[ویرایش]

بلام بلام شاب ([۱])

  • Lenore Blum, Manuel Blum, and Michael Shub. "A Simple Unpredictable Pseudo-Random Number Generator", SIAM Journal on Computing, volume 15, pages 364–383, May 1986.
  • Lenore Blum, Manuel Blum, and Michael Shub. "Comparison of two pseudo-random number generators", Advances in Cryptology: Proceedings of Crypto '82. Available as PDF.
  • Martin Geisler, Mikkel Krøigård, and Andreas Danielsen. "About Random Bits", December 2004. Available as PDF and Gzipped Postscript.

پیوند به بیرون[ویرایش]