اعداد تصادفی
اعداد تصادفی و روش ساخت آن ها در دنیای کامپیوتر ، مخصوصا دنیای رمزنگاری بسیار پراهمیت و کاربردی هستند . از استفاده هایی که هست میشه به موارد زیر اشاره کرد :
- تولید کلید برای هر نوع تایید هویت کاربر و یا فعالیت خاص
- استفاده در الگوریتم های متقارن مخصوصا روش های دنباله ای (Stream Ciphers)
- استفاده در روش های نامتقارن مانند RSA برای تولید P , Q به عنوان اعداد اول بزرگ مقدار
با توجه به مفهموم تصادفی بودن ، هر چه تکرار در یک دنباله از اعداد تصادفی تولید شده کمتر باشد ، روش ساخت انتخاب شده با توجه به ورودی های اولیه داده شده به الگوریتم قوی تر هست ، همچنین در فرآیند تولید دنباله ای از اعداد تصادفی باید کمترین تشابه رفتاری در تولید در ساخت هر دنباله به صورت جداگانه و یا هر عضو از هر دنباله وجود داشته باشد به عنوان مثال در دو دنباله زیر :
۱ ۳ ۵ ۷ ۹ ۱۱ ۱۳ ۱۵ ۱۷ ۱۹ ...
۲ ۶ ۱۰ ۱۴ ۱۸ ۲۲ ۲۶ ...
با بررسی هر دو دنباله میتوان ترتیب خاصی را پیدا کرد و حتی میتوان اعضای تولید نشده دنباله ها را حدس زد که برای یک فرآیند تصادفی سازی اصلا قابل قبول نخواهد بود .
برای ساخت دنباله ای از اعداد تصادفی حتی به مغز هم نباید رجوع کرد چون به احتمال زیاد بعد از چند بار تکرار مشاهده میشود که تاریخ تولد خود ، اقوام ، سن خود ، فرزند و ….. روی کاغذ پیاده شده است که میتوانند اطلاعات قابل حدسی باشند ، اما خب مزیتی که نسبت به دنباله های بالا دارند این است که اعضای تولید نشده غیر قابل حدسی خواهند داشت .
در طبیعت نیز همه چیز دارای یک توزیع تصادفی و نرمال هستند . در طبیعت ما این تصادفی بودن رو به اسم نویز (NOISE) ، ناخالصی و … میشناسیم . برای مثال اگر بر روی سیگنال های جاری در یک ارتباط دو طرفه هم بررسی انجام شود این تصادفی بودن مشهود است . موج دریا ، سرعت وزش باد و ….. همه تصادفی هستند و بازه زمانی تکرار بسیار متفاوتی نیز دارند .
به این بازه زمانی تکرار در اصطلاح Period گفته میشود . که در واقع فاصله بین مشاهده دو الگوی کاملا یکسان در یک روش تصادفی سازی هست . نکته این است که ما حتی اگر تمام اعداد از ۰ تا بینهایت را بتوانیم در تصادفی سازی تولید کنیم باز هم دنباله ای تولید میشود که قبلا به صورت مشابه تولید شده است . پس در واقع نمیتوان جلوی تکرار را گرفت اما میتوان رسیدن به این تکرار را سخت کرد به حدی که فقط از لحاظ تئوری قابل بررسی باشد اما از لحاظ عملی قابل پیاده سازی نباشد ، انگاه است که در واقع گفته میشود الگوریتم در جهان واقع امن است .
یک سری الگوریتم ها برای ساخت اعداد تصادفی پیاده سازی شده که از قرار زیر هستند :
- (True Random Number Generator) TRNG
- PRNG (Psudeo Random Number Generator)
- PRF (True Random Function)
TRNG در واقع ساخت اعداد تصادفی بیشتر مبتنی بر سخت افزار است و معمولا از روش های نزدیک تر به طبیعت تصادفی استفاده میکنه . به عنوان مثال از نویز تولید شده توسط هارد درایو و یا گرمای تولید شده توسط یک سخت افزار خاص استفاده میکند به این صورت اعداد تولید شده توسط خود را به بیشترین حد تصادفی بودن نزدیک میکند . اما خب استفاده از این روش به عنوان عدد اصلی تصادفی تولید کار جالبی نیست . چون معمولا اعداد تولید شده در حالت عادی بسیار بزرگ مقدار نیستند ، مگر اینکه پردازش های اضافی روی اعداد تولید شده انجام بگیرد .
PRNG الگوریتمی که در حال حاضر استفاده زیادی دارد . البته به عنوان یک مفهوم . در PRNG کار تولید اعداد تصادفی با یک SEED (دانه) عدد که به عنوان عدد تصادفی اولیه انتخاب میشود شروع میشود . این عدد به عنوان اولین ورودی الگوریتم سازنده در نظر گرفته میشود و با تولید بقیه اعضای دنباله به صورت وابسته یک دنباله از اعداد تصادفی را به عنوان خروجی برمیگرداند .
در این روش علاوه بر اینکه روش ساخت اعداد تصادفی بسیار مهم است ، روش انتخاب و یا ساخت Seed اهمیت بیشتری دارد . برای اینکه بیشترین تصادفی سازی PRNG ها بدست بیاید از یک TRNG به عنوان سازنده Seed استفاده میشود . در حقیقت هر چه TRNG پایدار تر باشد نتیجه کلی بهتر خواهد بود .
همچنین در سیستم عامل هایی مانند لینوکس با دستورات زیر میتوان اعداد تصادفی و یا حتی نویز های تصادفی تولید و از آن ها استفاده کرد :
~ $ echo $((2*$RANDOM-1)) 55003
یا روش دیگر که در واقع میتوان از برای تولید White Noise استفاده کرد :
~ $ cat /dev/urandom | aplay Playing raw data 'stdin' : Unsigned 8 bit, Rate 8000 Hz, Mono
در واقع خروجی صوتی خواهید داشت . همچنین در پرانتز باید گفت که /dev/urandom خود به عنوان seed ورودی را از /dev/random میخواند و به تولید دیتای تصادفی با PRNG میپردازد .
به مثال زیر که در آن از LCG استفاده میکنیم توجه کنید :
\[
\quicklatex{color=”#00ff00″ size=25}
\boxed{X{n+1} = (aX_n+C) mod M}
\]
در معادله بالا \[\quicklatex{color=”#00ff00″ size=25}\boxed{X_n}\] در واقع همان Seed در اولین بار اجرای الگوریتم است که بعد از چندین بار تکرار دنباله از اعداد تکراری را میسازد . در این روش با توجه به مقادیر a,M,C اعداد تولید شده دارای دوره تکرار متفاوتی هستند و هر چه این دوره تکرار طولانی تر باشد بهتر است .
دیدگاهتان را بنویسید
برای نوشتن دیدگاه باید وارد بشوید.