بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
ارائه روش جدید تولید کلید رمزنگاری جویباری به کمک آتوماتای سلولی و
الگوریتم مورچگان
چکیده
رمزنگاری عبارت است از یک نظام یا الگوی ریاضی/منطقی که بر اساس آن اطلاعات و مفاهیم آشکار و قابل فهم برای همگان، طبق روالی برگشت پذیر به اطلاعاتی نا مفهوم و گنگ تبدیل میشود. طبق اصل کرکهف چون قرار نیست هیچ نکته ای در بطن الگوریتم رمزنگاری و روال معکوس آن (یعنی رمزگشایی) مخفی بماند لذا در تمام الگوریتم های رمزنگاری، به پارامتری به نام کلید رمز احتیاج است که با تغییر آن ماهیت گنگ و مبهم اطلاعات رمزشده به نحو غیرقابل پیش بینی تغییر میکند.در رمزنگاری، آتوماتای سلولی به عنوان مولد کلید در رمزنگاری جویباری استفاده میشود. در این مقاله یک طرح برای یافتن قوانین بهینه در زمینه تولید اعداد تصادفی مبتنی بر آتوماتای سلولی مطرح شده است که از الگوریتم بهینه سازی کلونی مورچگان استفاده می کند. نتایج ارزیابی طرح پیشنهادی نشان دهنده کیفیت بالای مولد مطرح شده میباشد. این مولد به حداکثر بی نظمی، کیفیت بالای اعداد تولید شده و همچنین سرعت بالا دست یافته است.معیار اصلی ارزیابی دنبالههای تولیدی توسط هر یک از روشهای فوق، طول دوره تناوب آنها و میزان تصادفی بودن الگوی موجود دردنبالههاست. این دو معیار، از طریق انجام مجموعهای از آزمونها قابل ارزیابی هستند و شرط کارایی هر یک از این روشها، آن است که دنباله تولیدی آنها، حداقل برخی آزمونها را با موفقیت سپری نماید.مولدهای اعداد شبه تصادفی، آزمونهای اعداد شبه تصادفی، مفاهیم موردنیاز مقاله از جمله آتوماتای یادگیر، آتوماتای یادگیر سلولی، الگوریتم ژنتیک و الگوریتم کلونی مورچگان پرداخته شده است.
واژگان کلیدی: آتوماتای سلولی، مولد اعداد تصادفی، رمزنگاری جویباری، الگوریتم بهینه سازی کلونی مورچگان.
1
مقدمه
رفتارهای پیچیده کلونی مورچگان، انسان ها را تشویق کرده است که مطالعات متعددی در خصوص رفتارهای اجتماعی
و فردی آنها داشته باشند. در این مقاله، با الهام گرفتن از روشهای ارائه شده قبلی، مدلی معرفی میشود که با استفاده از الگوریتم بهینه سازی مورچگان (ACO)، به تعیین ترکیبی از قوانین بهینه جهت استفاده روی یک آتوماتای سلولی غیریکنواخت کمک خواهد کرد.
چالش اصلی در مولدهای آتوماتای سلولی غیریکنواخت ، یافتن بهترین ترکیب قوانین، جهت رسیدن به بهترین دنباله یا دنبالههای اعداد تصادفی است؛ چرا که استفاده از قوانین مناسب، تأثیر بسزایی در میزان تصادفی بودن دنباله یا دنبالههای تصادفی داشته و نتایج حاصل از آزمونهای مذکور را تحت تأثیر قرار میدهد.
در رمزنگاری، دنبالهای از بیتها یا بایتها بدون توجه به محتویات زبان شناختی آنها، طبق روالی معلوم و غیرسلیقه ای درهم رمز میشود. در روال رمزنگاری دنبالهی دادهها، کلید رمز به عنوان پارامتر، در متن دادهها تزریق میشود و چگونگی درهم شدن دادهها به مقدار کلید وابسته است. منظور از تزریق کلید در داده ها، جمع کلید با داده ها یا عملیاتی نظیر چهار عمل اصلی، XOR یا نظائر آنها است.
فرض کنید بخواهید یک فایل چند صد مگابایتی را رمز کنید. برای این کار به کلیدی چند صد مگابایتی نیاز دارید که قبل از ارسال، با گیرنده توافق شده باشد و گیرنده نسخهای از آن را به روشی امن در جایی ذخیره کرده باشد؛ چنین الزامی به شدت از عملی بودن روش خواهد کاست. در رمزنگاری جویباری، یکی از روشهایی که میتواند دنباله بزرگ کلیدها را با کلیدی کوتاه جایگزین و روش مبتنی بر xor را در عمل امکان پذیر کند استفاده از الگوریتمهای مولد دنباله های شبه تصادفی است. در این روش الگوریتمی طراحی میشود که به یک پارامتر کوچک به نام کلید کار خود را آغاز
و در روالی نامحدود، دنبالهای از بیتهای شبه تصادفی را تولید کند. الگوی چنین روشی در شکل 1 آمده است.
شکل : 1 الگوی رمزنگاری جویباری
2
روش مبتنی بر آتوماتای سلولی
آتوماتای سلولی را میتوان سیستمهای دینامیکی گسستهای در نظر گرفت که رفتارشان کاملاً بر اساس ارتباط محلی استوار است. در جایی که نیاز به تعداد زیادی اعداد تصادفی باشد، آتوماتای سلولی به علت سادگی و موازی بودن، بسیار سریع عمل میکند. در سال1986، Wolfram با استفاده از آتوماتای سلولی یک بعدی، مولد اعداد تصادفی تولید کرد که این کار توانایی آتوماتای سلولی را برای تولید بیتهای تصادفی آشکار کرد(.(Wolfram, 1986 آتوماتای سلولی به دلیل داشتن الگوریتم و پیادهسازی ساده سخت افزاری از اهمیت ویژهای در تولید اعداد شبه تصادفی برخوردار است. آتوماتای سلولی، ساده، سریع و منظم است و عملیات آن بصورت محلی انجام میشود. همچنین ذاتا قابلیت موازی شدن را دارد. این مشخصات، باعث میشود که نسبت به سایر مدلها، برای پیادهسازی سخت افزاری آسانتر باشد.
در این روش مجموعهای سلول تشکیل یک آتوماتای سلولی را میدهند که هر سلول به همراه سلولهای همسایه، بر اساس قانون تعریف شدهای مقدار خود را به روز میکند. برای نامگذاری قوانین از نامگذاری استاندارد Wolfram استفاده میشود. در این نامگذاری، اگر هر سلول دو حالت ممکن صفر و یک داشته باشد و همسایگی استفاده شده، همسایگی سلولی باشد، در نتیجه الگوی ممکن از همسایگی وجود دارد. به ازای این تعداد الگو، قانون مختلف وجود دارد. به عنوان مثال در شکل2، از قانون 90 در همسایگی سه سلولی برای به روز کردن1 مقدار آتوماتای سلولی در زمان استفاده شده است(. (Maiti et al, 2010
شکل :2 آتوماتای سلولی یک بعدی با شعاع یک
در بحث اتوماتاها از آتوماتای یادگیر نیز می توان نام برد، این مدل مدلی از یادگیری کامپیوتری است که جهت مدل-سازی سیستمهای یادگیر زیست شناختی، جهت یافتن عمل بهینه ارائه شده توسط یک محیط احتمالی، استفاده میگردد
.(Esnaashari and Meybodi , 2008)
3
آتوماتای یادگیر، ماشینی است که میتواند تعدادی متناهی عمل را انجام دهد. هر عمل انتخاب شده توسط یک محیط احتمالی ارزیابی میشود و نتیجه ارزیابی در قالب پاسخی مثبت یا منفی به آتوماتا داده میشود و آتوماتا از این پاسخ در انتخاب عمل بعدی تاثیر میگیرد. هدف نهایی این است که آتوماتا یاد بگیرد تا از بین اعمال خود بهترین عمل را انتخاب کند(.. (Chowdhury et al ,1998 بهترین عمل، عملی است که احتمال دریافت پاداش از محیط را به حداکثر برساند.
آتوماتای سلولی براساس معیارهای مورد بررسی به دستههای مختلف تقسیم میگردد. براساس معیار بعد شبکه، آتوماتای سلولی به آتوماتای سلولی یک بعدی، دوبعدی و غیره تقسیم شده است.
بر اساس مرز، میتوان سلولهای واقع در مرز مقابل را بعنوان همسایه در نظر گرفت. در صورتیکه همسایگی را بدین صورت در نظر گیریم، آن را آتوماتای سلولی با مرز چرخشی2 و در غیر اینصورت با مرز غیر چرخشی3 میگویند.
از آنجا که به راحتی نمیتوان عملکرد آتوماتای سلولی را در مرحله بعد حدس زد از آن برای تولید اعداد شبه تصادفی استفاده میگردد. مشکل آتوماتا، تولید دنباله کوتاهی از اعداد است به طوری که مجموعهای از اعداد تولید شده مرتبا تکرار میگردد. برای رفع این مشکل قانونهای ترکیبی یا به عبارتی آتوماتای ترکیبی ارائه شده است که تا حد قابل توجهای وضعیت تولید اعداد تصادفی را بهبود میبخشد. در این روش تمام سلولها از یک قانون یکنواخت تبعیت نمی-کنند بلکه هر سلول میتواند از یک قانون برای تولید سلول متناظر خودش استفاده کند. چالش اصلی در این نوع مولدها، یافتن بهترین الگوی پیکربندی قوانین جهت رسیدن به بهترین دنباله یا دنبالههای اعداد تصادفی است.
آتوماتای سلولی، توانایی خوبی در تولید اعداد تصادفی ندارد زیرا اکثر قوانین نمیتوانند دنباله طولانی از اعداد را تولید کنند. طول دنباله اعداد تصادفی ایجاد شده با آتوماتای سلولی در مقایسه با روش همنهشتی خطی بسیار ضعیف به نظر میرسد. این روش با استفاده از آتوماتای سلولی ترکیبی (آتوماتای سلولی غیر یکنواخت) بسیار بهتر پاسخ میدهد.
تحقیقاتی برای افزایش پیچیدگی آتوماتای سلولی با ترکیب حالت سلولها (Guan and Zhang, 2002) و افزایش ابعاد آتوماتای سلولی صورت گرفته است. مولدهای اعداد تصادفی، با استفاده از آتوماتای سلولی یک بعدی، در(Xuewen et al, 2009),(Anghelescu, 2011 )، آتوماتای سلولی دو بعدی در (Kang et al, 2008) و
آتوماتای سلولی سه بعدی در((Shin et al, 2008 مورد مطالعه قرار گرفتهاند. Hortensius اولین آتوماتای سلولی غیرهمگن یا آتوماتای سلولی قابل برنامه ریزی (PCA) را در سال 1989 با ترکیب قوانین 90 و 150ارائه کرد که این مولد دوره تناوب مساوی با LFSR داشت(. (Hortensius et al, 1989 او همچنین در ( Hortensius et al, 1989) یک مولد دیگر با ترکیب قوانین 30 و 45 ارائه کرد که نسبت به قوانین 90 و 150، بیتهای خروجی در آن، دارای وابستگی بیشتری به یکدیگر بودند. اخیراً مطالعاتی بر روی PCA برای ایجاد اعداد تصادفی انجام شده است .(Ray and Das, 2010) در آتوماتای سلولی قابل برنامه ریزی، هر سلول میتواند چندین سیگنال کنترلی را بکار گیرد. با نسبت دادن مقادیر به سیگنالهای کنترلی، آتوماتای سلولی قابل برنامه ریزی میتواند توابع دینامیکی مختلفی را
4
پیاده سازی کند. اولین کار بر روی آتوماتای سلولی دو بعدی توسط Chowdhury و همکاران در سال 1994 ارائه شد .(Chowdhury et al, 1994) نتیجه کار آنها نشان داد که مولد تولید شده بوسیله این آتوماتای سلولی نسبت به آتوماتای سلولی یک بعدی با سایز یکسان، بهتر عمل میکند. بر طبق این دستاورد، Tomassini و همکاران، یک آتوماتای سلولی دوبعدی 8*8 را برای تولید عدد تصادفی با استفاده از ترکیب قوانین 47، 15، 63 و 31 توسعه دادند .(Tomassini et al, 2000نتایج به دست آمده نشان داد که برخی از توسعههای آتوماتای سلولی میتوانند تمامی قسمتهای آزمون Diehard را با موفقیت سپری کنند. مطالعاتی نیز برای تولید اعداد تصادفی به وسیله آتوماتای سلولی و الگوریتمهای تکاملی انجام شده است.
در (Szaban et al, 2006 ) ,(Seredynski et al, 2004) از الگوریتم ژنتیک برای پیدا کردن جدول قوانین برای آتوماتای سلولی غیرهمگن استفاده شده است و در (Wang et al, 2008) از الگوریتم PSO برای این منظور استفاده شده است. هدف نهایی الگوریتمهای تکاملی، پیدا کردن جدول قانون مناسب برای یک آتوماتای سلولی غیرهمگن است. برای مثال قوانینی که موجب تولید عدد تصادفی با کیفیت بالا شوند .(Tomassini et al, 2000) برای این کار جدول قانون هر سلول به یک رشته بیت(ژن) تبدیل میشود و تکامل قوانین به وسیله اندازه گیری بهینه محلی به دست میآید. اگر بهینه اندازگیری شده مناسب نبود عملگرهای تکاملی همانند ترکیب و جهش به صورت محلی بین ژنها اجرا میشود.
در (Ghalambor Dezfuly et al, 2012) نیز یک مولد اعداد تصادفی با استفاده از آتوماتای یادگیر سلولی بیان شده است. آتوماتای یادگیر سلولی، مدلی برای سیستم هایی است که از اجزاء سادهای تشکیل شدهاند و رفتار هر جزء بر اساس رفتار همسایگانش و نیز تجربیات گذشتهاش تعیین و اصلاح میشود. اجزاء ساده تشکیل دهنده این مدل، از طریق تعامل با یکدیگر میتوانند رفتار پیچیدهای از خود نشان دهند. همچنین Stephen wolfram، نوعی رمزنگاری جویباری، مبتنی بر آتوماتای سلولی یک بعدی را مورد بررسی قرار داد. این آتوماتا دارای مقادیر صفر و یک و مرز چرخشی است و مقادیر سلولها، در مراحل زمانی مختلف، به صورت همزمان و براساس قوانین زیر بروزرسانی میشوند.
الگوریتم بهینه سازی مورچگان
اولین الگوریتم مورچه که توسعه داده شد، سیستم مورچه4 بود و از آن موقع توسعه های متعدد در سیستم مورچه بوجود آمده است. این الگوریتم ها دارای فرایندهای تصمیم گیری نسبتاً پیچیده ای می باشند.
حال با الهام گرفتن از روشهای ارائه شده قبلی، مدلی معرفی میشود که با استفاده از الگوریتم بهینه سازی مورچگان (ACO)، به تعیین ترکیبی از قوانین بهینه جهت استفاده روی یک آتوماتای سلولی غیریکنواخت کمک خواهد کرد. دوریگو و دی کارو ( (Dorigo and Di Caro, 1999 در آزمایشات خود در یافتند که:
SACO • برای گراف های ساده خیلی خوب عمل می نماید و کوتاه ترین مسیر در اغلب مواقع انتخاب می گردد.
5
· برای گراف های بزرگ تر، انتخاب پارامترها باید با حساسیت صورت گیرد و در صورت استفاده از پارامترهای نامناسب، کیفیت الگوریتم نزول خواهد کرد.
· تبخیر در گراف های پیچیده نقش مهمی را ایفا می کند. اگر و تبخیر وجود نداشته باشد، الگوریتم به سمت جواب خوبی همگرا نخواهد شد. اگر تبخیر فرومون زیاد باشد، الگوریتم در اغلب مواقع برای مسایل پیچیده به سمت یک راه حل بهینه محلی همگرا می شود.
· برای مقادیر کم ، الگوریتم به طور کلی به سمت کوتاه ترین مسیر همگرا می شود. برای مسایل پیچده، مقدار بالای منجر به همگرایی نامناسب الگوریتم می گردد.
مدل پیشنهادی
در این مدل، آتوماتای سلولی یک بعدی با مرز چرخشی و شعاع همسایگی یک (همسایگی سه سلولی) مورد توجه قرار گرفته است. با توجه به همسایگی سه سلولی، الگوی مختلف و در نتیجه قانون مختلف وجود دارد. تابع پردازش استفاده شده، مقدار محاسبه شده توسط آزمون آنتروپی است. همانطور که گفته شد، آزمون آنتروپی برای سنجش میزان تنوع دنباله اعداد تصادفی تولید شده مورد استفاده قرار میگیرد. فرمول تولید این عدد در رابطه 1 نمایش داده شده است. در این تست، هر چه عدد تولید شده بزرگتر باشد، نشان دهنده تنوع بیشتری است. هر چه تنوع در دنباله اعداد تولید شده بیشتر باشد مولد بهتری خواهد بود.
(1)
در فرمول 1، نشان دهنده احتمال رخداد عدد ام در دنباله اعداد تصادفی و ، آنتروپی یا درجه تنوع دنباله اعداد
تصادفی خواهد بود. برای محاسبه ، ابتدا دنبالهای از اعداد تصادفی تولید شده و نسبت تعداد هر عدد تولید شده به کل اعداد تولید شده، احتمال تولید عدد توسط مولد خواهد بود. شمارنده عددی است که مولد میتوانسته است تولید کند و تعداد کل اعدادی است که مولد باید بتواند تولید کند. هر چه مقدار بزرگتر باشد مولد بهتر عمل میکند. اگر مولد بتواند همه اعداد تصادفی را تولید کند، آنگاه احتمال تولید هر عدد برابر خواهد بود که در این صورت، مقدار حداکثر و مساوی است با:
از بین 256 قانون، برخی از قوانین، بعد از چند مرحله اجرا، منجر به حالت جزئی (وضعیت صفر یا یک در تمام سلولها) میشوند و میتوانند کارایی و عملکرد مدل را تحت تاثیر قرار دهند. برخی دیگر نیز، با در نظر گرفتن آنتروپی، به عنوان یک معیار ارزیابی کیفیت دنباله تولیدی، قوانین مطلوبی نخواهند بود. به همین دلیل، از قوانین 90 ،105، 165 و 150 که در (Tomassini et al, 1999) به عنوان قوانین برتر به دست آمدند، استفاده شده است.
در این طرح هر سلول آن، مجهز به چهار قانون برتر میباشد. در ادامه، این مدل پیشنهادی، تحت عنوان ACO-RAND مورد استفاده قرار خواهد گرفت. در این طرح، چهار قانون برتر به دست آمده در ( (Tomassini et al, 1999 به عنوان انتخابهای هر مورچه در نظر گرفته میشود. در آغاز الگوریتم، به هر کدام از قوانین در سلولها
