بلام بلام شاب

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

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

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

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

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

$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.

پیوند به بیرون

• GMPBBS (archived 2009-05-24 at the ماشین برگشت به گذشته), a GPL'ed GMP-based implementation of Blum Blum Shub by Mark Rossmiller. Retrieved 2011-09-05.
• An implementation in Java (Note: this is not a correct implementation because it does not enforce p and q as being prime; it just enforces p congruent to 3 (mod 4).)
• Randomness tests