11196

11196

يك روش تكاملي براي بهبود حل دستگاه معادلات تحليل رمز جبري

كارشناسي ارشد

برق - مخابرات امن

خرداد 1391

خرداد 1391

دكتر محمد عبداللهي ازگمي

چكيده روش‌هاي زيادي براي حل و يا ساده‌سازي دستگاه‌هاي معادلات روي GF(2) ارائه شده است. ولي حل اين دستگاه‌ها يك مسئله‌ي ان‌پي-كامل(NP-Complete) محسوب مي‌شود و راه‌حلي از درجه‌ي چندجمله‌اي براي آن وجود ندارد. در اين تحقيق ابتدا تاثير حدس تصادفي تعدادي از مجهولات در ساده‌تر شدن حل دستگاه معادلات به روش XL را اثبات كرده‌ايم. در اين بررسي به دنبال پيدا كردن متغير‌هايي بوديم كه تأثير بيشتري در ساده‌تر شدن حل دستگاه معادلات داشته باشد.در اين تحقيق روشي براي پيدا كردن اين متغير‌ها ارئه شده است.در آزمايش روش، روي الگوريتم A5/2 مشخص شد با حدس 16 بيت از وضعيت داخلي اين الگوريتم ساير بيت‌هاي وضعيت داخلي را مي‌توان بدست آورد.با حدس اين 16 بيت تعداد تك جمله‌اي‌هاي ممكن در دستگاه معادلات از 264 تك جمله‌اي به 3742 تك جمله‌اي كاهش يافت. در قسمت بعد به بررسي امكان حل دستگاه معادلات توسط الگوريتم‌هاي ژنتيك پرداخته‌ايم. روشي نيز بدين منظور بر اساس الگوريتم ژنتيك سلولي ارائه شده است. دستگاه معادلات ورودي به شكل مسئله‌ي صدق‌پذيري دودويي فرض شده است. پس از پياده‌سازي نرم‌افزاري روش، در انتها نرم‌افزاري نوشته شده را با مسائل مسابقات جهاني حل صدق‌پذيري محك زده و امكان حل اين دستگاه‌ها با استفاده از الگوريتم ژنتيك اثبات گرديد.نرم‌افزار ما 36 مسئله از 71 مسئله‌ي اين مسابقات را با زمان 72250 ثانيه حل نمود و MiniSATتعداد 70 مسئله از همين مسائل را در زمان 196190 ثانيه حل كرد. قابل ذكر است كه اگر 35 مسئله‌ي حل نشده توسط نرم‌افزار ما را حذف نماييم، كل زمان حل توسط نرم‌افزار ما به 18341 ثانيه كاهش مي‌يابد. كل زمان حل برايMiniSAT نيز به 50342 ثانيه كاهش مي‌يابد كه باز هم نرم‌افزار ما بيش از 2.5 برابر سريعتر از MiniSAT مسائل را حل نموده است. واژه‌هاي كليدي:رمزنگاري، تحليل الگوريتم‌هاي رمز، حمله‌ي جبري، الگوريتم‌هاي بهينه‌سازي تكاملي، الگوريتم ژنتيك.